Sequences in C and C++ are implemented using pointers. Please make sure to read the article

Pointers in C++before reading this document.

Let us review the allocation of the memory. We begin with 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;`

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)`

.

We have seen that the sequence is determined by the address of its first term. This has one very important consequence for programming. The functions are able to modify the terms of sequences. You may remember how difficult it was to make functions that modify the external variables. It will be very easy to write functions that modify the terms of sequences. Here is one example.

Create an implementation of the function

void makeAllEvenTermsZero(long* x, long len)that looks for all even terms and modifies them to \(0\).

Our next goal is to create a more advanced function. The function receives a sequence, and its task is to extend its length. Here is the precise formulation of the problem.

Create an implementation of the function

void extend(long** aX, long* aLen)that receives two pointers. The second argument

`aLen`

contains the address of the memory location that stores the length of the sequence `len`

. The first argument `aX`

contains the address of the pointer `x`

to a block of memory of size `*aLen`

. For example for the sequence \(3\), \(7\), \(12\), \(5\), \(6\) of length \(5\), the memory diagram would look like this
\begin{eqnarray*}
\begin{array}{cccc}
&\mbox{aLen}\;\boxed{\mbox{len}} & \rightarrow & \boxed{{\;}^{\; }5}
\end{array}&& \\
\begin{array}{cccccc}
&\mbox{aX}\; \boxed{\mbox{x}} & \rightarrow & \boxed{{ }^{ }} & \rightarrow & \boxed{{\;}^{\; }3}\\
& & & & & \boxed{{\;}^{\; }7}\\
& & & & & \boxed{12}\\
& & & & & \boxed{{\;}^{\; }5}\\
& & & & & \boxed{{\;}^{\; }6}
\end{array}&&
\end{eqnarray*}
The function should extend the sequence by increasing its length. The number of elements that should be added has to be equal to `x[len-1]`

. In the example above, the size of the extension should be `6`

because `x[len-1]=x[5-1]=x[4]=6`

.
The extension should consist of terms equal to \(1\). The number of ones is exactly `x[len-1]`

.

The function will be called from `main`

in the following way:

int main(){ long* x; long len; std::cin>>len; x=new long[len]; for(long i=0;i<len;++i){std::cin>>x[i];} extend(&x, &len); std::cout<<"New length is "<<len<<"\n"; for(long i=0;i<len;++i){std::cout<<x[i]<<" ";} std::cout<<"\n"; delete[] x; return 0; }

In the example above we have `n=5`

, and `x`

is the sequence \(3\), \(7\), \(12\), \(5\), \(6\). After the execution of the function `extend`

, the length `len`

must be changed to `11`

and the sequence `x`

must be changed to

In this document we have used *heap memory allocation* to construct arrays and sequences. The length of the sequence can be decided during the execution of the program. If the name of our sequence is `x`

and its desired length is stored in the variable `N`

, then we allocate the memory with the command

x = new double[N];

Once we do not need the memory, then we must return it to the operating system with the command

delete[] x;

There is another, less preferable method for making sequences. It is called *stack memory allocation*. We must know the length of the sequence in advance. The length of the sequence has to be quite small. If we want to create a sequence `y`

with 20 elements, then we can give the following command:

double y[20];

There is no need to use the operator `delete[]`

to return the memory to the operating system. Stack allocation of arrays is easier to implement because of the ability to omit the operators `new`

and `delete[]`

. However, the stack allocation is less powerful. The obtained sequences cannot be large. Thus, it is necessary to learn the heap allocation. In most C++ courses (and in particular in MTH4300), the stack allocation is illegal. Students **must** use heap allocation for arrays.

You can assume that the function `maxExponent`

is properly implemented. Its arguments are two positive integers `x`

and `b`

, such that `b>1`

. The function returns the largest exponent \(\alpha\) such that \(b^{\alpha}\) is a divisor of `x`

.

Create the implementation of the function `numZeroes`

that has three arguments: `aS`

of type `long*`

, `n`

of type `long`

, and `m`

of type `long`

. The variable `aS`

contains the address of the first element of the sequence `s[0]`

, `s[1]`

, `...`

, `s[n-1]`

of positive integers. The function has to return the number of zeroes at the end of the integer `P`

that is obtained as a product of all those elements of `s`

that are bigger than `m`

. Your code should replace the text `// ??? //`

below.

long numZeroes(long* aS, long n, long m){ // ??? // }

The user input consists of a positive integer \(n\) followed by \(n\) words \(w[0]\), \(w[1]\), \(\dots\), \(w[n-1]\) of type `std::string`

. After these \(n\) words, the user inputs two integers \(k\) and \(l\) such that \(0\leq k < l \leq n\). Create the program that reads the input from `std::cin`

and prints the words \(w[k]\), \(w[k+1]\), \(\dots\), \(w[l-1]\).

Create the function `divisibleByP`

whose arguments are the pointer to the first term of the sequence, the length of the sequence, and the integer \(p\). The output function `divisibleByP`

should create the new sequence \(y\) with the following property: \(y[0]\) should be the total number of terms of the sequence \(x\) that are divisible by \(p\). The elements \(y[1]\), \(y[2]\), \(\dots\) should be the actual terms of \(x\) that are divisible by \(p\).

Create the program that uses the function `divisibleByP`

. The user input consists of a positive integer \(n\) followed by \(n\) integers \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\). The user then inputs the integer \(p\). Use the function `divisibleByP`

to create the sequence of those terms that are divisible by \(p\) and print them on the standard output.

Create a function that starts from a sequence \( x \) of integers of length \( n \) and modifies it so that every occurrence of the number \( 5 \) is deleted, and every occurrence of number 0 is replaced with three numbers \( 1 \). For example if \( n=8 \), and \( x=(1,8,0,3,5,7,0,8) \), then the resulting sequence is \[ x=(1,8,1,1,1,3,7,1,1,1,8).\]