1 Introduction to C++ 2 Variables, branching, and loops 3 Functions and recursions 4 Pointers 5 Linked lists 6 Stacks 7 Sequences 8 Pointers practice 9 References 10 Merge sort 11 Object oriented programming 12 Trees in C++ 13 Balanced trees 14 Sets and maps: simplified 15 Sets and maps: standard 16 Dynamic programming 17 Multi core programming and threads 18 Representation of integers in computers 19 Floating point representation 20 Templates 21 Inheritance

# Sequences (Arrays) in C++

## 1. Pointer arithmetic

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

Pointers in C++

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;
*pX=37;
*(pX+1)=73;
*(pX+2)=17;
*(pX+6)=177;


The command pX=new int 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; 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.

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

## 2. Functions that modify terms of sequences

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.

Problem 2.

Create an implementation of the function

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

## 3. Functions that modify lengths of sequences

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.

Problem 3.

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=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

$3, 7, 12, 5, 6, 1, 1, 1, 1, 1,1$

## 4. Heap and stack memory allocation for arrays

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;

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.

## 5. Practice problems

Problem 4.

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, s, ..., 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){
// ??? //
}

Problem 5.

The user input consists of a positive integer $$n$$ followed by $$n$$ words $$w$$, $$w$$, $$\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]$$.

Problem 6.

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$$ should be the total number of terms of the sequence $$x$$ that are divisible by $$p$$. The elements $$y$$, $$y$$, $$\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$$, $$x$$, $$\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.

Problem 7.

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).$