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

Chapter 3
Data Structures and Searching

This chapter introduces data structures and presents algorithms for searching and sorting.

3.1 Pointers and Dynamic Memory Allocation

This section investigates pointers and dynamic memory allocation in C++. As a first example consider the C++ source code in Code List 3.1.

Code List 3.1 Integer Pointer Example

At the beginning of the program there are two variables that are allocated. The first variable is a variable p which is declared as a pointer to an integer. The second variable, k, is declared as an integer. The variable p is stored at address A1. The address A1 will contain an address of a variable which will be interpreted as an integer. Initially this address is not assigned. The variable k is stored at address A3. Note that the addresses of p and k do not change during the execution of the program. These addresses are allocated initially and belong to the program for its execution life.

The statement p=new int in the program allocates room for an integer in memory and makes the pointer p point to that location. It does not assign a value to the location that p points to. In this case p now contains the address A4. The memory location at address A4 will contain an integer. The new operator is a request for memory allocation. It returns a pointer to the memory type requested. In this example room is requested for an integer.

The statement *p=7 assigns the integer 7 to the location that p points to. In this case the address A4 will now contain a 7.

The statement k=3 assigns 3 to the address where k is located. In this case the address A3 will contain the integer 3.

The statement delete p now requests to deallocate the memory granted to p with the new operator. In this case p will still point to the location but the data at the location is subject to change. It can be the case that *p is no longer 7. Note that once the memory is freed the program no longer may have a right to access the data. The memory location A4 is free to be assigned to any other program which requests memory space.

The statement p=&k assigns the address of k to p. The address of k is A3. For this case, p, located at A1 will now contain the address A3.

The statement *p=4 now assigns the integer 4 to the address that p points to. For this case the data at address A3 will now contain 4.

This statement has changed the value of k. The flow for the memory is shown in Figure 3.1.

There are a number of pitfalls to be concerned with pointers. The declaration int *p does not allocate room for the integer. It simply allocates room for a variable p which will point to an integer in memory. As a result the following code segment is invalid:

int *p;

*p=7;

For this code segment the address that p contains is not valid. Unfortunately depending on the platform you are using to develop your programs this might not generate an error on compilation and in some operating systems even on execution.

Figure 3.1  Memory Layout for C++ Program

The following code segment is acceptable

int *p, k;

p=&k;

*p=4;

For this code segment, p points to the address of k which has been allocated memory for an integer.

The code shown in Code List 3.2 is also valid. The output for the program is shown in Code List 3.3.

Code List 3.2 Pointer Example

Code List 3.3 Output of Program in Code List 3.2

The style of the output will change dramatically depending on the operating system and platform used to develop the code. It is sufficient to note that for the code in Code List 3.2 p contains an address that points to a location that contains an address that points to a location that contains an integer.