Author: Mike Ware

Website: [warebiz] :: "The Programmer's Domain" - http://warebiz.tripod.com

Email: warebiz@yahoo.com

Copyright © 2003 Michael Shawn Ware, All Rights Reserved.

You are here --> [

"Jump To Articles"

--> One Dimensional Arrays

--> Two Dimensional Arrays

--> Passing Arrays to Functions

--> Insertion Into An Array

--> Deletion From An Array

--> Searching Arrays

--> Shuffling Array Elements

--> Generating Latin Squares

An array is a group of related data values all of the same type. There are a couple of reasons why a programmer might want to use an array in a program. One motivation for using an array is the reduction of identifiers. For example, a program needs to store the values of fifty test scores. Without arrays, a programmer would have to declare fifty variables in order to keep track of all of fifty individual scores (test1, test2, test3, ..., test50). With arrays, a programmer could simply declare an array that would hold fifty elements, such as

The form of declaring an array is as follows:

type arrayName[MAXARRSIZE];

where MAXARRSIZE is the maximum number of elements. In the above example,

int test[50];

would be an appropriate array declaration for fifty integer values. Array elements can be initialized using curly braces { } as follows:

int test[5] = { 1, 2, 3, 4, 5 };

This initializes test[0] to 1, test[1] to 2, test[2] = 3, test[3] = 4, and test[4] = 5.

A programmer can initialize all elements in an array to 0 as follows:

int test[50] = { 0 };

Another reason for using an array is if a progammer is faced with a problem where he needs to use/access the data involved more than once. In the above example, this type of situation could easily be accomplished using an array because we could use the index value of each test for easy accessing purposes. When processing an array, it is best (at least from my point of view) to use a

The following is a simple program demonstrating the use of a one-dimensional array:

/////////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler ///////////////////////////////////// #include <iostream.h> #include <stdlib.h> const int MAXARRSIZE = 5; int main() { int accountNumbers[MAXARRSIZE], customerNum = 1, count = 0; cout << endl; for (int k = 0; k < MAXARRSIZE; k++) { cout << "Enter customer account number (####) for customer " << k+1 << ": "; cin >> accountNumbers[k]; } cout << endl << endl; while (count < MAXARRSIZE) { cout << "Customer " << customerNum << " account number = " << accountNumbers[count] << endl; customerNum++; count++; } cout << endl << endl; system("PAUSE"); return EXIT_SUCCESS; }// end main() /////////////////////////////////////// Compiled Using Dev-C++ Compiler /////////////////////////////////////

With the very basics of a one dimensional array covered, we can now move on and talk about two dimensional arrays, which are more powerful than one dimensional arrays. Read on for more...

If you are not familiar with one-dimensional arrays, you should back up and read that section before reading this one, [see One-Dimensional Arrays]. While one-dimensional arrays allow data to be placed in an array one row at a time, two-dimensional arrays are capable of storing data in rows and columns. Each row in the array is associated with the number of columns defined for the array. The only drawback is that the entire array must contain elements of the same type, which is defined when you declare the array. Because of the capability of storing data in rows and columns, it is obvious that two-dimensional arrays can be a very powerful tool in programming compared to one-dimensional arrays. Declaring a two-dimensional array has the following form:

where

int arr[5][3];

If you wish to initialize the values in the array, use the following format:

int arr[5][3] =

{

{ 0, 1, 2 }

{ 3, 4, 5 }

{ 6, 7, 8 }

{ 9, 0, 1 }

{ 2, 3, 4 }

}

The above code initializes arr[0][0] = 0, arr[0][1] = 1, arr[1][0] = 3, arr[1][1] = 4, arr[4][0] = 2, and so on. Because 2D arrays must be filled by row and column, processing a 2D array involves using nested for loops. For instance, in order to fill an array declared numArr[10][10] with user input, you could use the following code:

for (int rows = 0; rows < 10; row++) for (int cols = 0; cols < 10; cols++) { cout << "Enter value for row " << row+1 << " col " << col+1 << ": "; cin >> numArr[row][col]; }

If you want to display the contents of the above filled array ten values per line, you could use the following code:

int row, col; for (row = 0; row < 10; row++) for (col = 0; col < 10; col++) { cout << numArr[row][col]; if (col % 10 == 9) cout << endl; }

Another common use of two dimensional arrays is for storing a collection of strings. When storing strings in a two dimensional array, the rows in the array are associated with the position of the full string value, and the columns in the array are actually associated with the individual characters of the string. For instance, if the string "c++" was stored in row 0 of stringArr, then stringArr[0][0] would hold 'c', stringArr[0][1] would hold '+', and stringArr[0][2] would hold '+'. For example, suppose we have a two dimensional array declared as follows:

char stuNames[5][26];

This array would hold 5 strings with a maximum of 25 characters per each string length (I declared the array with 26 maximum columns to have enough room for the null terminater '\0' that is attached to the end of a string). Suppose we want to fill our example array with values specified by the user during program execution and also display the contents of the array in a semi-neat fashion. Code to take care of this situation is as follows:

const int MAXSTULEN = 26; const int NUMOFSTUS = 5; const int FLUSH = 80; int main() { char stuNames[NUMOFSTUS][MAXSTULEN]; int count, index; for (count = 0; count < NUMOFSTUS; count++) { cout << "Enter the name for student " << count+1 << ": "; cin.get(stuNames[count], MAXSTULEN); cin.ignore(FLUSH, '\n'); } cout << endl << endl << "LISTING OF STUDENT NAMES" << endl; cout << "---------------------------------------->" << endl; for (index = 0; index < NUMOFSTUS; index++) cout << " " << stuNames[index] << endl; cout << endl << endl; system("PAUSE"); return EXIT_SUCCESS; }// end main()

Suppose we have a two dimensional integer array of exactly ten rows and ten columns, and we need to find the sum of the integers along the main diagonal of the array. We could use the following piece of code:

const int MAXARRSIZE = 10; int arr[MAXARRSIZE][MAXARRSIZE]; . .arrgets values . . int sum = 0, row, col; for (row = 0; row < MAXARRSIZE; row++) for (col = 0; col < MAXARRSIZE < 10; col++) if (row == col) sum += arr[row][col]; cout << "The sum of the values along the main diagonal is: " << sum << endl;

Suppose the correct answers for a true/false quiz are: T T F F T

Suppose a two dimensional array contains student answers with each row representing the responses of a particular student. The first row (0) of the array contains the above answer "key".

Write code to calculate the students' scores on the quiz and store these scores in a one-dimensional array. Assume each question is worth 4 points and there is a maximum of 50 students.

The following code could be used to accomplish this task:

const int NUMOFSTUS = 51; const int NUMOFQUIZZES = 5; const int ANSWERINDEX = 0; char quizAnswers[NUMOFSTUS][NUMOFQUIZZES]; int gradeArray[NUMOFSTUS]; // row 0 will unused . . . quizAnswers gets values . . int stuIndex, probIndex, grade; for (stuIndex = 1; stuIndex < NUMOFSTUS; stuIndex++) { grade = 0; for (probIndex = 0; probIndex < NUMOFQUIZZES; probIndex++) if (quizAnswers[stuIndex][probIndex] == quizAnswers[ANSWERINDEX][probIndex]) grade += 4; gradeArray[stuIndex] = grade; }

Now you can work with one-dimensional and two-dimensional arrays, but the most important aspect to learn concerning arrays is how to pass them to functions. Since functions are critical for accomplishing tasks and organizing programs, it is vital to learn this key aspect of arrays. Read on for more...

An array is automatically passed by reference unless the programmer explicitly declares the function parameter as constant ( const ) . If you need to pass the array by value, the function heading could look similar to the following:

void displayArray ( const int arr [ ], int MAXARRSIZE );

When you pass an array to a function, it is also a good idea to pass the size of the array for processing purposes. If you notice in the above function heading, MAXARRSIZE is passed to represent the size of the array. In the declaration section of your program, you should initialize a variable or constant to store the size of the array. The following is an example of a function that accepts an array and its size. The function displays the contents of the array to console.

void displayArray( int arr[ ], int MAXARRSIZE ) { for ( int k = 0; k < MAXARRSIZE; k++) cout << arr[k] << endl; } // end displayArray( )

The following is an example of a function that will find and return the position of the smallest value in a given array of integers:

int positionOfMin ( int arr[ ], int size ) { int positionOfMin = 0; int pos; for ( pos = 1; pos < size; pos++) if ( arr[pos] < arr[positionOfMin] ) positionOfMin = pos; return positionOfMin; } // end positionOfMin ( )

Having covered array basics, we can now move onto array manipulation. Let's begin by talking about array insertion. Read on for more...

A programmer may encounter times when he needs to insert an element into an array. There are two scenarios. The first is if he needs to insert a value into a sorted array. The second is if he simply needs to insert a value into a specified location in the array. If he needs to insert a value into a specified location, he can simply insert the value into the position and then move all other following elements to the next position and increment the size of the array. If he needs to insert a value into a sorted array, he must first find the location in the array where the value should be placed to keep the original order in tact. Next, he can insert the value and then move all other following elements to the next position and increment the size of the array. Both scenarios require enough room for the new element in the array. The following is an example of a function that will insert a value into an array previously sorted into ascending order:

void insertElement ( int arr[ ], int* size, int newElement ) { int insertPosition, k; insertPosition = 0; while ( newElement > arr[insertPosition] && insertPosition != *size - 1 ) insertPosition++; if ( newElement <= arr[insertPosition] ) { for ( k = *size - 1; k >= insertPosition; k-- ) arr[k+1] = arr[k]; arr[insertPosition] = newElement; } else arr[*size] = newElement; *size = *size + 1; }// insertElement ( )

If the programmer needs to insert an element into a specified location in the array, he could easily use the

/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler ////////////////////////////////////// #include <iostream.h> #include <stdlib.h> const int ARRSIZE = 10; void insertPosition(int arr[], int& size, int element, int position); int main() { int nums[ARRSIZE] = { 34, 12, 89, 22, 21, 45, 55, 93, 27, 76 }; int size = ARRSIZE, element, position; for (int k = 0; k < size; k++) cout << nums[k] << " "; do { cout << endl << endl << "Enter position in the array for insertion (0 - 9): "; cin >> position; } while (position < 0 || position > 9); cout << "Enter value to be inserted into position [" << position << "] of the array: "; cin >> element; insertPosition(nums, size, element, position); cout << endl << endl; for (int k = 0; k < size; k++) cout << nums[k] << " "; cout << endl << endl << endl; system("PAUSE"); return EXIT_SUCCESS; }// end main() void insertPosition(int arr[], int& size, int element, int position) { for (int k = size - 1; k >= position; k--) arr[k+1] = arr[k]; arr[position] = element; size++; }// end insertPosition() /////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler //////////////////////////////////////

We have now covered inserting an element into an array, but what if a programmer needs to delete an element from an array? Before moving on the next section, try to devise a function to handle such a situation. After you have devised a proposed solution, read on to compare your algorithm with my generalized solution...

As with inserting an element into an array, there are two scenarios a programmer could face when attempting to delete an element from an array. The first scenario is if the programmer knows the exact location of the value to be deleted. The second is if he knows the value to be deleted but has no idea of its location in the array. If he knows the exact location of the value to be deleted, he can create a

void deleteElement ( int arr[ ], int& size, int position ) { int k; if ( position >= size ) cout << "Error! Attempting to delete an element beyond size of array."; else { for ( k = position; k < size - 1; k++ ) arr[k] = arr[k+1]; --size; } }// end deleteElement ( )

The following is an example of a segment of code that will find the position of a particular value in a given array:

int k; for (k = 0; k < size; k++ ) if ( arr[k] == value ) position = k;

The following program deletes a value from a pre-initialized array.

////////////////////////////////////// Compiled with Dev C/C++ V.4 Compiler ////////////////////////////// #include <iostream.h> #include <stdlib.h> const int ARRSIZE = 10; void deleteElement(int arr[], int& size, int position); int main() { int nums[ARRSIZE] = { 13, 22, 53, 14, 35, 66, 27, 98, 29, 10 }; int size = ARRSIZE, position; for (int k = 0; k < size; k++) cout << nums[k] << " "; cout << endl << endl; cout << "Enter position of value to be deleted (0 - 9): "; cin >> position; deleteElement(nums, size, position); cout << endl << endl; for (int k = 0; k < size; k++) cout << nums[k] << " "; cout << endl << endl << endl; system("PAUSE"); return EXIT_SUCCESS; } void deleteElement(int arr[], int& size, int position) { int k; if (position >= size) { cout << "Error: Attempting to delete beyond size of array!" << endl; system("PAUSE"); exit(EXIT_FAILURE); } else { for (k = position; k < size - 1; k++) arr[k] = arr[k+1]; --size; } }// end deleteElement() ////////////////////////////////////// Compiled with Dev C/C++ V.4 Compiler //////////////////////////////

Now you know the difference between one dimensional and two dimensional arrays, the logic behind passing them to functions, and inserting and deleting array elements. Can you think of anything else you may need to know concerning arrays? What if you need to search for an element stored in an array. Can you write code to handle this situation? Read on for more...

You may face times when you need to search through an entire array to look for specific data, whether it be integer values, floating point values, or characters. Maybe you need to delete the data or you need to move it to another position in the array. Whatever the case may be, I will introduce you to two standard methods for searching arrays: a linear search, and a binary search. Let's first explore the linear search.

The definition of

The following is a function that can be used as a linear search for an array of integers:

int linearSearch(int arr[], int size, int target) { int position = 0, result = -1; bool isFound = 0; while ( !isFound && position < size ) { if (arr[position] == target) { result = position; isFound = 1; } position++; } return result; }// end linearSearch()

When this function is called, one of two values will be returned: the target's position in the array or -1, which indicates failure. For efficiency sake, for an array of size N, the worst possible case would be N "attempts" while searching the array. The average case is (n+1)/2 "attempts".

It is important to note that for a binary search to work, the array must be previously sorted into ascending or descending order. The definition of

The following function can be used to search an array of integers that was previously sorted into ascending order:

int binarySearch(int arr[], int size, int target) { int middlePosition, middleValue, result = -1; int low = 0, high = size - 1; bool isFound = 0; while ( !isFound && low <= high) { middlePosition = (low + high) / 2; middleValue = arr[middlePosition]; if (target == middleValue) { result = middlePosition; isFound = 1; } else if (target < middleValue) high = middlePosition - 1; else low = middlePosition + 1; } return result; }// end binarySearch()

You now have the ability to search arrays, but maybe the solution to a problem requires you to shuffle the contents of an array. Read on for more...

Writing code to shuffle the contents of an array can take some imagination. Basically, you have two options. One way would be to choose a number at random (which is in the proper range) and place it in the array in position 0; repeat this process and place the next random number in position 1, 2, 3, up to size (size of the array) - 1. This option could work, but you must avoid duplicating values when choosing the numbers at random (very inefficient). The second way would be to randomly choose a position (0 to size - 1) and swap the value in that position with the value in the "last" position (size - 1). Next, randomly select another position (0 to size - 2) and swap its value with the one in the next-to-last position. Repeat this process until position 1 is reached. Essentially, this type of shuffle would send the current randomly chosen position value to the end of the array, and then restrict the next shuffle so the previous "locked in" values would not be manipulated. Obviously, the second option is more efficient and would not duplicate values during the shuffling process since the values are not being randomly chosen, but rather the positions in the array are being randomly chosen and their corresponding values are being "shuffled".

The following code is designed to shuffle the contents of an integer array:

NOTE: you must use a randomize( ) function to generate random numbers; the specific functions to handle this are different for every compiler; the code is tested using Dev C/C++ V.4 compiler [rand( ) represents its randomize function].

void shuffleElements(int theArr[], int size) { int temporary, randomNum, last; for (last = size; last > 1; last--) { randomNum = rand( ) % last; temporary = theArr[randomNum]; theArr[randomNum] = theArr[last - 1]; theArr[last - 1] = temporary; } }// end shuffleElements( )

If a programmer needed to write code for an array to mimic the shuffling of cards in a deck where it is possible to shuffle the cards back into their previous positions, he could use the following piece of code:

void shuffleCards(int arrDeck[]) { int card; for (card = 0; card < 52; card++) { int randNum, temporary; randNum = rand( ) % 52; temporary = arrDeck[card]; arrDeck[card] = arrDeck[randNum]; arrDeck[randNum] = temporary; } }// end shuffleCards( )

The following is a complete program illustrating the use of a function designed to shuffle the contents of an array.

//////////////////////////////////// COMPILED USING DEV C/C++ V.4 COMPILER /////////////////////////////////////// #include <iostream.h> #include <stdlib.h> #define MAXSIZE 10 void shuffleElements(int theArr[], int size); int main() { int numArr[MAXSIZE] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }; int k; srand((unsigned)time(NULL)); shuffleElements(numArr, MAXSIZE); for (k = 0; k < MAXSIZE; k++) { cout << numArr[k]; if (k != MAXSIZE - 1) cout << " | "; } cout << endl << endl; system("PAUSE"); return EXIT_SUCCESS; } void shuffleElements(int theArr[], int size) { int temporary, randomNum, last; for (last = size; last > 1; last--) { randomNum = rand( ) % last; temporary = theArr[randomNum]; theArr[randomNum] = theArr[last - 1]; theArr[last - 1] = temporary; } }// end shuffleElements( ) //////////////////////////////////// COMPILED USING DEV C/C++ V.4 COMPILER ///////////////////////////////////////

Shuffling the elements in an array is necessary for generating latin squares. Read on for more...

Two dimensional arrays are necessary for applications involving the generation of Latin squares. A Latin square of order N is an N x N matrix in which each row and column contains each of the values 1, 2, 3, ..., N, exactly one time. The following...

5 1 2 3 4

2 3 4 5 1

4 5 1 2 3

1 2 3 4 5

3 4 5 1 2

is an example of a Latin square of order 5. The following Latin square could be generated by the algorithm depicted in this tutorial:

5 1 2 3 4

4 5 1 2 3

3 4 5 1 2

2 3 4 5 1

1 2 3 4 5

Why use Latin squares? Surprisingly, they are actually commonly used in the design of statistical experiments. For example, if we wanted to test the effects of 5 different drugs on mice, and there are 5 different groups of mice, each with 5 different sizes, then we could use a latin square of order 5. Each drug will be tested on each group and each size. It turns out that it takes 25 tests to accomplish this; if you wanted to test every drug on each group in each size, it would require 125 tests.

To generate a Latin square of order N, first generate a random permutation of the digits 1 through N. You could generate this permutation by using the "shuffle" function depicted in earlier articles, see [Shuffling Array Elements]. This ordering turns out to be the 1st row of the Latin square. You then take (1st digit - 1) of the permutation to be the index of the next digit to be placed in the matrix. Place this digit in the other rows in the order given by the permutation (always subtracting one to get the position). Next, rotate the permutation to the left 1 position and repeat this process. You must always go back to the original permutation, which is the first row of the Latin square, to find the digit to be placed throughout the Latin square.

In other words, the (1st digit - 1) of the new permutation gives the index; that position in the original permutation gives the number to be placed; the new permutation gives the ordering; repeat this process until all of the rows are filled.

For example, suppose we want to generate a Latin square of order 6, and we used the "shuffle" function mentioned earlier to generate the following random sequence:

6 3 1 4 2 5

The first digit in this permutation is 6. The index of the value we want to place in the Latin square is (6-1) =

(6-1) = position 5 in row 0

(3-1) = position 2 in row 1

(1-1) = position 0 in row 2

(4-1) = position 3 in row 3

(2-1) = position 1 in row 4

(5-1) = position 4 in row 5

We then need to rotate the permutation one place to the left. We then end up with...

3 1 4 2 5 6

The first digit in this new permutation is 3. The index of the value we want to place in the Latin square is (3-1) =

(3-1) = position 2 in row 0

(1-1) = position 0 in row 1

(4-1) = position 3 in row 2

(2-1) = position 1 in row 3

(5-1) = position 4 in row 4

(6-1) = position 5 in row 5

The new permutation would then be rotated one place to the left and the process would be repeated until all positions in the Latin square are filled. Our completed Latin square would look like this:

6 3 1 4 2 5

1 4 5 6 3 2

5 6 2 1 4 3

2 1 3 5 6 4

3 5 4 2 1 6

4 2 6 3 5 1

You may think that writing code to generate a Latin square would be quite tricky, but after evaluating the code, you will realize that it is really not that difficult. The following code will produce and display a Latin square of order

/////////////////////////////////////////////////////////////////////////////////////////////////// #include <iostream.h> #include <stdlib.h> #include <time.h> #include <iomanip.h> typedef int tRow[10]; typedef tRow tLatinSquare[10]; int getSize(); void shuffle(int arr[], int size); void rotate(tRow list, int size); int main() { tRow sequence, randomList; tLatinSquare square; int position, value, i, j, size; char ch; srand((unsigned)time(NULL)); size = getSize(); while (size != 0) { shuffle(randomList, size); for (i = 0; i < size; i++) sequence[i] = randomList[i]; for (i = 0; i < size; i++) { position = sequence[0]; value = randomList[position - 1]; for (j = 0; j < size; j++) square[j][sequence[j] - 1] = value; rotate(sequence, size); } cout << endl; cout << "A Latin Square of Order " << size << " is: " << endl << endl; for (i = 0; i < size; i++) { for (j = 0; j < size; j++) cout << setw(5) << square[i][j]; cout << endl; } cout << endl; system("PAUSE"); cout << endl << endl; size = getSize(); } cout << endl << endl; system("PAUSE"); return EXIT_SUCCESS; }// end main() int getSize() { int size; do { cout << "Enter the desired order of the Latin Square (3 - 10) or 0 to stop: "; cin >> size; } while ((size < 3 || size > 10) && size != 0); return size; }// end getSize() void shuffle(int arr[], int size) { int i, temp, ran, last; for (i = 0; i < size; i++) arr[i] = i + 1; for (last = size; last > 1; last--) { ran = rand() % last; temp = arr[ran]; arr[ran] = arr[last - 1]; arr[last - 1] = temp; } }// end shuffle() void rotate(tRow list, int size) { int temp, i; temp = list[0]; for (i = 0; i < size - 1; i++) list[i] = list[i+1]; list[size - 1] = temp; }// end rotate() \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

We are now starting to explore more interesting and challenging information. Now that we have touch-based with arrays, we can cover sorting array elements. There will be times when you will have an array that contains thousands of unsorted integers or other elements. Your job will be to sort this entire array and either put the integers into ascending or descending order. Stop and think for a minute about how you might devise a function to handle this type of situation.

I will present a few methods (standard techniques) for sorting arrays. Write a sorting function yourself before viewing the next section. Then, you can compare/contrast your method with mine. Read on for more about the first sort I will cover: the selection sort...

Move on to next set of topics: [Section 7] - Sorting Array Data

Back to Top