Lab #4. Arrays, pointers, references and dynamic variables

Goal: Program problem solving using arrays, pointers and references. Learn how to use pointers to create dynamic variables

Theory

An array consists of a set of objects (called its elements), all of which are of the same type and are arranged contiguously in memory. In general, only the array itself has a symbolic name, not its elements. Each element is identified by an index which denotes the position of the element in the array. The number of elements in an array is called its dimension. The dimension of an array is fixed and predetermined; it cannot be changed during program execution. Arrays are suitable for representing composite data which consist of many similar, individual items. Examples include: a list of names, a table of world cities and their current temperatures, or the monthly transactions for a bank account.

A pointer is simply the address of an object in memory. Generally, objects can be accessed in two ways: directly by their symbolic name, or indirectly through a pointer. The act of getting to an object via a pointer to it, is called dereferencing the pointer. Pointer variables are defined to point to objects of a specific type so that when the pointer is dereferenced, a typed object is obtained. Pointers are useful for creating dynamic objects during program execution. Unlike normal (global and local) objects which are allocated storage on the runtime stack, a dynamic object is allocated memory from a different storage area called the heap. Dynamic objects do not obey the normal scope rules. Their scope is explicitly controlled by the programmer.

A reference provides an alternative symbolic name (alias) for an object. Accessing an object through a reference is exactly the same as accessing it through its original name. References offer the power of pointers and the convenience of direct access to objects. They are used to support the call-by-reference style of function parameters, especially when large objects are being passed to functions.

 

Arrays

An array variable is defined by specifying its dimension and the type of its elements. For example, an array representing 10 height measurements (each being an integer quantity) may be defined as:

 

int heights[10];

 

The individual elements of the array are accessed by indexing the array. The first array element always has the index 0. Therefore, heights[0] and heights[9] denote, respectively, the first and last element of heights. Each of heights elements can be treated as an integer variable. So, for example, to set the third element to 177, we may write:

 

heights[2] = 177;

 

Attempting to access a nonexistent array element (e.g., heights[-1] or heights[10]) leads to a serious runtime error (called ‘index out of bounds’ error).

Processing of an array usually involves a loop which goes through the array element by element. Listing 1 illustrates this using a function which takes an array of integers and returns the average of its elements.

 

Listing 1

const int size = 3;

double Average (int nums[size]) {

double average = 0;

for (register i = 0; i < size; ++i)

average += nums[i];

return average/size;

}

 

Like other variables, an array may have an initializer. Braces are used to specify a list of comma-separated initial values for array elements. For example,

 

int nums[3] = {5, 10, 15};

 

initializes the three elements of nums to 5, 10, and 15, respectively. When the number of values in the initializer is less than the number of elements, the remaining elements are initialized to zero:

 

int nums[3] = {5, 10}; // nums[2] initializes to 0

 

When a complete initializer is used, the array dimension becomes redundant, because the number of elements is implicit in the initializer. The first definition of nums can therefore be equivalently written as:

 

int nums[] = {5, 10, 15}; // no dimension needed

 

Another situation in which the dimension can be omitted is for an array function parameter, e.g.: double Average (int nums[], int size) {…}.

A C++ string is simply an array of characters. For example,

 

char str[] = "HELLO";

 

It is easy to calculate the dimension of an array using the sizeof operator. For example, given an array ar whose element type is Type, the dimension of ar is:

 

sizeof(ar) / sizeof(Type)

 

Multidimensional Arrays

An array may have more than one dimension (i.e., two, three, or higher). The organization of the array in memory is still the same (a contiguous sequence of elements), but the programmer’s perceived organization of the elements is different. For example, suppose we wish to represent the average seasonal temperature for three major Australian capital cities (see Table below).

 

	Spring	Summer	Autumn	Winter
Sydney
Melbourne
Brisbane

 

This may be represented by a two-dimensional array of integers:

 

int seasonTemp[3][4];

 

The organization of this array in memory is as 12 consecutive integer elements:

 

 

As before, elements are accessed by indexing the array. A separate index is needed for each dimension. For example, Sydney’s average summer temperature (first row, second column) is given by seasonTemp[0][1].

The array may be initialized using a nested initializer:

 

int seasonTemp[][4] = {

{26, 34, 22, 17},

{24, 32, 19, 13},

{28, 38, 25, 20}

};

 

As you may see from initializer above we can omit the first dimension (but not subsequent dimensions).

Processing a multidimensional array is similar to a one-dimensional array, but uses nested loops instead of a single loop. Listing 2 illustrates this by showing a function for finding the highest temperature in seasonTemp.

 

Listing 2

const int rows = 3;

const int columns = 4;

int seasonTemp[rows][columns] = {

{26, 34, 22, 17},

{24, 32, 19, 13},

{28, 38, 25, 20}

};

int HighestTemp (int temp[rows][columns]) {

int highest = 0;

for (register i = 0; i < rows; ++i)

for (register j = 0; j < columns; ++j)

if (temp[i][j] > highest)

highest = temp[i][j];

return highest;

}

 

Pointers

A pointer is simply the address of a memory location and provides an indirect way of accessing data in memory. A pointer variable is defined to ‘point to’ data of a specific type. For example:

 

int *ptr1; // pointer to an int

char *ptr2; // pointer to a char

 

The value of a pointer variable is the address to which it points. For example, given the definitions

 

int num;

 

we can write:

 

ptr1 = &num;

 

The symbol & is the address operator; it takes a variable as argument and returns the memory address of that variable. The effect of the above assignment is that the address of num is assigned to ptr1. Therefore, we say that ptr1 points to num.

Given that ptr1 points to num, the expression *ptr1 dereferences ptr1 to get to what it points to, and is therefore equivalent to num. The symbol * is the dereference operator; it takes a pointer as argument and returns the contents of the location to which it points.

In general, the type of a pointer must match the type of the data it is set to point to. A pointer of type void*, however, will match any type. This is useful for defining pointers which may point to data of different types, or whose type is originally unknown. A pointer may be cast (type converted) to another type. For example,

 

ptr2 = (char*) ptr1;

 

converts ptr1 to char pointer before assigning it to ptr2.

Regardless of its type, a pointer may be assigned the value 0 (called the null pointer). The null pointer is used for initializing pointers, and for marking the end of pointer-based data structures (e.g., linked lists).

 

Dynamic Memory

In addition to the program stack (which is used for storing global variables and stack frames for function calls), another memory area, called the heap, is provided. The heap is used for dynamically allocating memory blocks during program execution. As a result, it is also called dynamic memory. Similarly, the program stack is also called static memory.

Two operators are used for allocating and deallocating memory blocks on the heap. The new operator takes a type as argument and allocated a memory block for an object of that type. It returns a pointer to the allocated block. For example,

 

int *ptr = new int;

char *str = new char[10];

 

allocate, respectively, a block for storing a single integer and a block large enough for storing an array of 10 characters. Memory allocated from the heap does not obey the same scope rules as normal variables. For example, in

 

void Foo () {

char *str = new char[10];

//...

}

 

when Foo returns, the local variable str is destroyed, but the memory block pointed to by str is not. The latter remains allocated until explicitly released by the programmer. The delete operator is used for releasing memory blocks allocated by new. It takes a pointer as argument and releases the memory block to which it points. For example:

 

delete ptr; // delete an object

delete [] str; // delete an array of objects

 

Note that when the block to be deleted is an array, an additional [] should be included to indicate this.

Dynamic objects are useful for creating data which last beyond the function call which creates them. Listing 3 illustrates this using a function which takes a string parameter and returns a copy of the string.

 

Listing 3

char* CopyOf (const char *str) {

char *copy = new char[strlen(str) + 1];

strcpy(copy, str);

return copy;

}

 

Because of the limited memory resources, there is always the possibility that dynamic memory may be exhausted during program execution, especially when many large blocks are allocated and none released. Should new be unable to allocate a block of the requested size, it will return 0 instead.

 

Pointer Arithmetic

Pointer arithmetic is not the same as integer arithmetic, because the outcome depends on the size of the object pointed to. For example, suppose that an int is represented by 4 bytes. Now, given

 

char *str = "HELLO";

int nums[] = {10, 20, 30, 40};

int *ptr = &nums[0]; // pointer to first element

 

str++ advances str by one char (i.e., one byte) so that it points to the second character of "HELLO", whereas ptr++ advances ptr by one int (i.e., four bytes) so that it points to the second element of nums. Figure below illustrates this diagrammatically.

 

 

It follows, therefore, that the elements of "HELLO" can be referred to as *str, *(str + 1), *(str + 2), etc. Similarly, the elements of nums can be referred to as *ptr, *(ptr + 1), *(ptr + 2), and *(ptr + 3).

In turns out that an array variable (such as nums) is itself the address of the first element of the array it represents. Hence the elements of nums can also be referred to using pointer arithmetic on nums, that is, nums[i] is equivalent to *(nums + i). The difference between nums and ptr is that nums is a constant, so it cannot be made to point to anything else, whereas ptr is a variable and can be made to point to any other integer. Listing 4 shows how the HighestTemp function (shown earlier in Listing 2) can be improved using pointer arithmetic.

 

Listing 4

int HighestTemp (const int *temp, const int rows, const int columns) {

int highest = 0;

for (register i = 0; i < rows; ++i)

for (register j = 0; j < columns; ++j)

if (*(temp + i * columns + j) > highest)

highest = *(temp + i * columns + j);

return highest;

}

 

Instead of passing an array to the function, we pass an int pointer and two additional parameters which specify the dimensions of the array. In this way, the function is not restricted to a specific array size. The expression *(temp + i * columns + j) is equivalent to temp[i][j] in the previous version of this function.

 

References

A reference introduces an alias for an object. The notation for defining references is similar to that of pointers, except that & is used instead of *. For example,

 

double num1 = 3.14;

double &num2 = num1; // num is a reference to num1

 

defines num2 as a reference to num1. After this definition num1 and num2 both refer to the same object, as if they were the same variable. It should be emphasized that a reference does not create a copy of an object, but merely a symbolic alias for it. Hence, after

 

num1 = 0.16;

 

both num1 and num2 will denote the value 0.16.

A reference must always be initialized when it is defined: it should be an alias for something. It would be illegal to define a reference and initialize it later.

 

double &num3; // illegal: reference without an initializer

num3 = num1;

 

The most common use of references is for function parameters. Reference parameters facilitate the pass-by-reference style of arguments, as opposed to the pass-by-value style which we have used so far. To observe the differences, consider the three swap functions in Listing 5.

 

Listing 5

void Swap1 (int x, int y) { // pass-by-value (objects)

int temp = x;

x = y;

y = temp;

}

void Swap2 (int *x, int *y) { // pass-by-value (pointers)

int temp = *x;

*x = *y;

*y = temp;

}

void Swap3 (int &x, int &y) { // pass-by-reference

int temp = x;

x = y;

y = temp;

}

 

Although Swap1 swaps x and y, this has no effect on the arguments passed to the function, because Swap1 receives a copy of the arguments. What happens to the copy does not affect the original.

Swap2 overcomes the problem of Swap1 by using pointer parameters instead. By dereferencing the pointers, Swap2 gets to the original values and swaps them.

Swap3 overcomes the problem of Swap1 by using reference parameters instead. The parameters become aliases for the arguments passed to the function and therefore swap them as intended.

Swap3 has the added advantage that its call syntax is the same as Swap1 and involves no addressing or dereferencing. The following main function illustrates the differences:

 

int main (void) {

int i = 10, j = 20;

Swap1(i, j); cout << i << ", " << j << '\n';

Swap2(&i, &j); cout << i << ", " << j << '\n';

Swap3(i, j); cout << i << ", " << j << '\n';

}

 

When run, it will produce the following output:

10, 20

20, 10

10, 20

 

Lab Overview

2.1. Read the theory and try Control Exercises.

2.2. Develop the algorithm flowchart to solve a problem according to individual case from the Table below.

2.3. Write the program code according to the developed algorithm using dynamic arrays, user-defined functions and pointers/references.

2.4. Debug the program, run it and make screenshots.

2.5. Prepare the Lab Report according to the required structure.

 

#	Array type	Task
1.	2D, float	Calculate the number of items greater than 0
2.	2D, double	Calculate the sum of pair items
3.	2D, int	Calculate the number of negative items
4.	2D, unsigned int	Calculate the sum of diagonal items
5.	2D, float	Substitute 0-items by 1 and output array in reverse order
6.	2D, double	Find an average value of array items
7.	2D, int	Find maximum and minimum values in an array
8.	2D, unsigned int	Calculate an average of diagonal items
9.	2D, float	Divide array items by 10 and output items greater than 0.5
10.	2D, double	Calculate the sum of odd items
11.	2D, int	Calculate the number of items greater than 5
12.	2D, unsigned int	Substitute items greater than 5 by 1, all the rest – by 0
13.	2D, float	Calculate a per-element sum of two arrays of the same type and size
14.	2D, double	Output array with greater sum of elements (use two arrays for comparison)
15.	2D, int	Build a transposed array for a given one
16.	2D, unsigned int	Create 2D array of defined size from an inputted vector
17.	2D, float	Calculate a per-element multiplication of two arrays of the same type and size
18.	2D, double	Output array with greater average value of elements (use two arrays for comparison)
19.	2D, int	Output main diagonal elements which may be divided by 2 without remainder
20.	2D, unsigned int	Calculate a number of elements equal to 1, 2, …, 9 in an array

 

Report Structure

- Title page

- Task overview

- Algorithm’s flowchart

- Program code

- Program running screenshots

- Conclusions

 

Control Exercises

4.1. Define two functions which, respectively, input values for the elements of an array of reals and output the array elements:

void ReadArray (double nums[], const int size);

void WriteArray (double nums[], const int size);

 

4.2. Define a function which reverses the order of the elements of an array of reals:

void Reverse (double nums[], const int size);

 

4.3. Define a function which creates and returns a dynamic 2D array according to the indicated number of rows and columns:

double** CreateArray (const int rows, const int cols);

 

4.4. Define a function which releases a memory for the indicated dynamic array:

void ReleaseArray (double** arr, const int rows, const int cols);

 

References

5.1. Juan Soulié. C++ Language Tutorial. – 2007. – p. 54-76.

5.2. Sharam Hekmat. C++ Essentials. – PragSoft Corporation 2005. – p. 65-81.

5.3. Prata S. C++ Primer Plus (5th Edition). – Sams, 2004. – p. 109-176.

 

Lab #5. STRUCTURES

Goal: Study how to create C++ program which handles data structures array

Theory

Introducing Structures

Suppose you want to store information about a basketball player. You might want to store his or her name, salary, height, weight, scoring average, free-throw percentage, assists, and so on. You’d like some sort of data form that could hold all this information in one unit. An array won’t do. Although an array can hold several items, each item has to be the same type. The answer to your desire is the C++ structure. A structure is a more versatile data form than an array because a single structure can hold items of more than one data type. This enables you to unify your data representation by storing all the related basketball information in a single structure variable. If you want to keep track of a whole team, you can use an array of structures. The structure type is also a stepping stone to that bulwark of C++ OOP, the class.

A structure is a user-definable type, with a structure declaration serving to define the type’s data properties. After you define the type, you can create variables of that type. Thus, creating a structure is a two-part process. First, you define a structure description that describes and labels the different types of data that can be stored in a structure. Then, you can create structure variables, or, more generally, structure data objects, that follow the description’s plan.

For example, suppose that Bloataire, Inc., wants to create a type to describe members of its product line of designer inflatables. In particular, the type should hold the name of the item, its volume in cubic feet, and its selling price. Here is a structure description that meets those needs:

 

struct inflatable { // structure declaration

char name[20];

float volume;

double price;

};

 

The keyword struct indicates that the code defines the layout for a structure. The identifier inflatable is the name, or tag, for this form; this makes inflatable the name for the new type. Thus, you can now create variables of type inflatable just as you create variables of type char or int. Next, between braces is the list of data types to be held in the structure. Each list item is a declaration statement. You can use any of the C++ types here, including arrays and other structures. Each individual item in the list is called a structure member (See Fig. 1).

After you have the template, you can create variables of that type:

 

inflatable hat; // hat is a structure variable of type inflatable

inflatable woopie_cushion; // type inflatable variable

inflatable mainframe; // type inflatable variable

 

Fig. 1. Parts of a structure description

 

Given that hat is type inflatable, you use the membership operator (.) to access individual members. For example, hat.volume refers to the volume member of the structure, and hat.price refers to the price member. Similarly, vincent.price is the price member of the vincent variable. In short, the member names enable you to access members of a structure much as indices enable you to access elements of an array. Because the price member is declared as type double, hat.price and vincent.price are both equivalent to type double variables and can be used in any manner an ordinary type double variable can be used.