Composite Data Structures and Modularization

Volume 2: Composite Data Structures and Modularization

Xingni Zhou, Qiguang Miao, Lei Feng

• Publisher: De Gruyter
• Year: 2020
• ISBN:
  9783110692501
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming
• Index: Computer Science

This book covers C-Programming focussing on its practical side. Volume 2 deals mainly with composite data structures and their composition. An extensive use of figures and examples help to give a clear description of concepts and help the reader to gain a systematic understanding of the programming language.

1 Arrays

Main contents

• Concept, usage, and available methods of arrays
• Introduction of representation and nature of arrays through comparison between array/array elements and plain variables
• Storage characteristics and debugging techniques of arrays
• Programming techniques of multidimensional arrays
• Top-down algorithm design practices

Learning objectives

• Know how to define and initialize arrays as well as how to access array elements
• Be able to define and use multidimensional arrays
• Know how to deal with character arrays

1.1 Concept of arrays

Program statements and data construct programs. They are sequences of instructions created through algorithm design that conform to program control structures. However, are we able to solve all problems after learning statements, basic data types, program control structures, and algorithm implementation methods of C?

Let us look at a few problems in practice.

1.1.1 Processing data of the same type

Case study 1 Cracking Caesar code

Mr. Brown received an email from his son Daniel. However, the contents seemed a little weird for an email sent by someone in elementary school: it was a meaningless sequence “lettc fmvxlhec hehhc pszi csy”.

It later turned out that Daniel read a story of Julius Caesar and created an encrypted email using Caesar code to see whether his father could decrypt it.

During Roman times, Caesar invented the Caesar code to protect the information he exchanged with his generals on the front line from being intercepted by enemy spies. Encryption and decryption of Caesar code were done by shifting letters by a fixed number of positions. The plaintext alphabet was shifted forward or backward by a fixed number of positions to create the ciphertext alphabet. The number of positions shifted was the key for encryption and decryption of Caesar code, as shown in Figure 1.1.

Mr. Brown stared at the ciphertext and thought that it would not be hard to design an algorithm to solve the problem. He could simply shift each character in the ciphertext by one position in the alphabet and repeat this process 26 times to list all possible plaintexts, in which the one that is not nonsense would be the real plaintext. A universal algorithm could be designed using this technique to crack ciphertexts of arbitrary length.

• If the length of the ciphertext is 2, we shift letters by one position in the alphabet each time and list all 26 possible plaintexts.
• If the length of the ciphertext is 10, we shift letters by one position in the alphabet each time and list all 26 possible plaintexts.
• If the length of the ciphertext is 100, we shift letters by one position in the alphabet each time and list all 26 possible plaintexts.

Figure 1.1: Encryption and decryption of Caesar code.

Think and discuss Necessary variables in password cracking

1. How many variables are necessary for a program to handle 100 characters?
2. How should we use these variables so that the program handles data in a convenient and unified manner?

Discussion: Solving a problem with computers involves two major steps: first, we should use reasonable data structures to describe the problem to store data into computers; second, we create algorithms to solve it. To answer the earlier questions, we need to find a mechanism that describes variables of the same type and handles them consistently.

Code implementation of the algorithm that solves Caesar codes is rather complicated, so we shall introduce it later. Before that, let us consider a reversed order problem that is more trivial.

Case study 2 Reversing 100 numbers

Write a program that reads 100 numbers and outputs them in a reversed order.

We are going to focus on how to handle variables of the same type. For a simpler description, we use variables with subscripts to represent the numbers, as shown in Figure 1.2.

Figure 1.2: Representation of 100 variables of the same type.

The flow of outputting 100 numbers backward is given in Figure 1.3. The program reads the numbers in a loop starting from X₁, and outputs them using a loop starting from X₁₀₀.

Variable X_i is uniquely identified by the value of i. We use x[i] to represent X_i in programs so we can type the names using keyboards.

The code implementation is as follows:

 01 int main(void ) 02 { 03 int i; 04 int x[100]; 05...

Table of contents

• Title Page
• Copyright
• Contents
• 1 Arrays
• 2 Pointers
• 3 Composite data
• 4 Functions
• 5 Files: operations on external data
• Index