Algorithms and Data Structures in C++ by Alan Parker CRC Press, CRC Press LLC ISBN: 0849371716   Pub Date: 08/01/93

3.1.3 Arrays

Sequential arrays stored in memory also rely on pointers for index calculations. The array example in Code List 3.8 demonstrates the differences between pointers and arrays for the case of the multidimensional array. The output of the program is shown for two different platforms. Code List 3.9 shows the output of the program for a DOS system while Code List 3.10 shows the output of the program on a Unix system. For this program two different methodologies are used for implementing the storage of four integers. The memory allocation is illustrated in Figure 3.3. The key difference between the implementation of the pointers and the multidimensional array is that the array a[2][2] is not a variable. As a result, operations such as a=a+1 are invalid.

Figure 3.3  Memory Organization for Code List 3.8

Someone slightly familiar with C or C++ might be surprised to see that the output indicates that the values of &a, a, and *a are all equal. While this looks unusual it is correct. The declaration int a[2][2] in C and C++ declares a to be an array of arrays. In this case there are two arrays each containing two integers. The first array is located at address A4 while the second array is located at the address A5.

•  a - returns the starting address of the array of arrays which is given as A4 in Figure 3.3.

•  *a - returns the starting address of the first array in the list which is also A4 in Figure 3.3

•  &a - returns the starting address of the array a which is A4. This does not return the address of the element (if there is one) that actually points to a. When you declare an array via int a[2][2] there is no variable which points to the beginning of the array that the programmer can change. The compiler basically ignores the ampersand when the variable is declared as an array. Remember, this is the difference between pointers and arrays. The location where a points to cannot change during the program.

The output for b follows directly the addressing as illustrated in Figure 3.3

Code List 3.8 Array Example

Code List 3.9 Output of Code in Code List 3.8

Code List 3.10 Output of Code in Code List 3.8

3.1.4 Overloading in C++

An example of overloading in C++ is shown in Code List 3.11. The output of the program is shown in Code List 3.12. This program overloads the operator () which is used to index into a set of characters for a specific data bit. The packing is illustrated in Figure 3.4 for the variable e declared in the program.

Figure 3.4  Packing Bits in Memory

Code List 3.11 Operator Overloading Example

Code List 3.12 Output of Program in Code List 3.11

3.2 Arrays

This section demonstrates the creation of an array class in C++ using templates. The goal of the program is to demonstrate the implementation of a feature of C++ which is already built in; therefore, the code is for instructive purposes only. The code for a program to create an array class is illustrated in Code List 3.13, The output of the program is shown in Code List 3.14. The array class is declared in the program as a generic class with a type T which is specified later when an array variable is declared. As seen in the main function three arrays are declared: a, b, and c. The array a consists of ten integers. The array b consists of five doubles. The array c consists of 3 characters. The constructor function for the array initializes all the elements of the array to zero. The function set_data is used to assign a value to a specific element in the array. The function print_data is used to print a specific element in the array.

Code List 3.13 Creating an Array Class in C++

Code List 3.14 Output from Code List 3.13

3.3 Stacks

A stack is a data structure used to store and retrieve data. The stack supports two operations push and pop. The push operation places data on the stack and the pop operation retrieves the data from the stack. The order in which data is retrieved from the stack determines the classification of the stack.

A FIFO (First In First Out) stack retrieves data placed on the stack first. A LIFO (Last In First Out) stack retrieves data placed on the stack last. A LIFO stack push and pop operation is illustrated in Figure 3.5.

Figure 3.5  Push and Pop in a LIFO Stack

The source code to implement a LIFO stack class is shown in Code List 3.15. The output of the program is shown in Code List 3.16. Notice that templates are used again so the type used for the stack is defined at a later point.

Code List 3.15 LIFO Stack Class

Code List 3.16 Output of Program in Code List 3.15

3.4 Linked Lists

This section presents the linked list data structures. This is one of the most common structures in program design.