MTH 4300: Algorithms, Computers, and Programming II

Sequences in C++

Pointer arithmetic
Sequences in C and C++ are implemented using pointers. Please make sure you have read the article Pointers in C++ before reading this document.
Let us recall the allocation of the memory by reviewing the following short code:
int *pX;
pX=new int;
*pX=37;
The command pX=new int; requests a memory location to store one integer. The address of the memory location is stored in the variable pX. The command new can be used to allocate an entire block of memory instead of just one memory location. Consider the following code
int *pX;
pX=new int[7];
*pX=37;
*(pX+1)=73;
*(pX+2)=17;
*(pX+6)=177;
The command pX=new int[7] asks the computer to allocate the memory sufficient to store 7 integers. The memory is allocated as consecutive blocks, and the address of the first cell in the block is stored in pX. The command *pX=37; results in number 37 being written at the memory location of the first cell in the block.
Let us analyze the arithmetic operation pX+1. Recall that pX is an address. It contains a memory location that can store an integer. The value (pX+1) is another address. It is the address of the block that starts exactly where the integer *pX ends. The address (pX+1) is available to us because the command pX=new int[7]; secured 7 integers. Hence *(pX+1)=73; results in number 73 being written in the second memory location of the block. Similarly, *(pX+2)=17; results in the number 17 being stored in the third memory location, while *(pX+6)=177 stores the number 177 in the last memory location. Notice that (pX+7) is a place in the computer memory that we are not allowed to use. We asked for only 7 integers whose addresses are pX, (pX+1), (pX+2), \(\dots\), (pX+6), and the computer may have assigned the address (pX+7) to some other process or program.
Let us also point out that when freeing a memory block we use delete[] pX; instead of delete pX;
Problem 1. The user first enters the integer \(n\) and after it the user enters a sequence of \(n\) integers. Print the sequence of integers each of which is five times bigger than the corresponding integer that the user has entered.

Since the notation *(pX+2) is ugly the C family of languages allows us to use pX[2]. You can think of a compiler replacing every occurrence of pX[k] with *(pX+k).

Mutator functions whose arguments are sequences

We will now write a function that has to create a sequence. Let us consider the following problem:

Problem 2.

The user first enters the integer \(n\) and after it the user enters a sequence \(x\) of \(n\) integers. Create the function extendTheSequence that extends the sequence \(x\). The extension consists of terms equal to \(1\) and the number of ones is exactly \(x[n-1]\).

For example if \(n=5\), and if \(x\) is the sequence \(3\), \(7\), \(12\), \(4\), \(5\), then after the execution of extendTheSequnce the sequence \(x\) must become

\[3, 7, 12, 4, 5, 1, 1, 1, 1, 1\]