Computer Programming
Lecture 5: Static Arrays (1D/2D)
Example 1
Input the marks for 10 students
Store the marks in variables
Compute the average marks
Print the marks of the students and the average
100 30 44 66 50 60 80 75 80 100
The mark of the students are: 100, 30,
44, 66, 50, 60, 80, 75, 80, 100
Average mark=68
2
The program
/*define variables for storing 10 students' mark*/
int mark1, mark2, mark3, mark4, mark5,
mark6, mark7, mark8, mark9, mark10, average;
/*input marks of student*/
cin >> mark1 >> mark2 >> mark3 >> mark4 >>
mark5 >> mark6 >> mark7 >> mark8 >> mark9 >> mark10;
/*print the marks*/
cout << "The mark of the students are: " << mark1<<", "
<< mark2 <<", " << mark3 <<", " << mark4 <<", " << mark5
<<", " << mark6 <<", " << mark7 <<", " << mark8 <<", " <<
mark9 <<", " << mark10 << endl;
average=(mark1+mark2+mark3+mark4+mark5
+mark6+mark7+mark8+mark9+mark10)/10;
cout << "Average mark"<< average << endl;
Is it easy to extend the program to handle more students?
3
What is an Array?
Sequence of data items that are of the same type
Stored contiguously in physical memory
Can be accessed by integer index (constant number or variable)
int x; 5
x=5;
int a[6];
a[0]=5;
a [0] a [1] a [2] a [3] a [4] a [5]
a[1]=7;
a[2]=2;
5 7 2
4 IMPORTANT! First item is having index [0], but NOT [1] !
Array definition
Data type of the array
Size of the array
element
int mark[10];
Name of the array
mark[10]
There are ten elements in this array
mark[0], mark[1], ……, mark[9]
The ith array element is accesses as mark[i-1]. (Not mark[i]!)
The range of the index i ranges from 0 to array_size-1
The location mark[10] is invalid. Array index out of bound! (compiler will not tell you)
5
Array definition
The size of the array must be know when declared:
Ok: int mark[10];
Many compilers do NOT support variable size:
Problematic: cin>>size; int mark[ size ];
(So.. Let's consider the worse case and make sure that you declare enough!…)
The only exception is constant variable:
Ok: const int size=5; int mark[ size ];
The size could be omitted if the initial values are provided:
Ok: int fiveValues[] = {10,20,30,40,50};
Ask compiler to count for you!
The implicit size here is 5
Storing values to array elements
Suppose the mark for the first student is 30. We can use
the notation
mark[0] = 30;
Example: Reading the marks of the second student
cin >> mark[1];
Index can be constant (e.g. 1, 2, 3)
Example: Reading the marks for 10 student
for (i=0;i<10;i++)
Index can also be a variable (e.g. x, y)
cin >> mark[i]; or even an expression (e.g. x+y*3-1)
Advantage of Array:
-Can use Loops for repeated reading/writing
-Can use Loops for operations like Sum/Average/Search/find Max
7
Retrieving the values of an array element
Example: Print the mark of the second student
cout << mark[1];
Example: Sum the mark of all the students:
sum = 0; //IMPORTANT!
for (i=0;i<10;i++) {
cout << mark[i];
sum = sum + mark[i];
}
8
Summary of Array Declaration and Access
Type Variable Variable Array Array Access
Access
int int x; x=1; int x[20]; x[0]=1
float float x; x=3.4; float x[10]; x[0]=3.4;
x[1]=1.2;
double double x; x=0.7; double x[20]; x[0]=0.7;
x[3]=3.4;
char char x; x='a'; char x[5]; x[0]='c';
X[1]='s';
Note: Use single quotation mark to access
individual character in array !
9
Example 1 (Average of 10 elements with Array)
Just like normal int variable, can declare together with comma
/*define variables for storing10 students' mark*/
int marks[10], i;
double sum=0, average; Use double if you want average
with decimal places…
/*input marks of student*/
for (i=0;i<10;i++) Note: Don't write for (i=1;i<=10;)
cin >> mark[i];
since arrays start with 0 not 1 !
/*print the marks*/
cout << "The mark of the students are:";
for (i=0;i<10;i++) {
cout << mark[i] << " ";
sum=sum + mark[i];
}
/*compute and print the average*/
average=sum/10;
cout << "Average mark= " << average << endl;
10
Example 2: counting / statistics
Input a sequence of digits {0, 1, 2, …, 9}, which is
terminated by -1
Count the frequency of occurrence of each digit
Use an integer array count of 10 elements
count[i] stores the frequency of occurrence of digit i
11 9
The program: buggy version
#include <iostream>
using namespace std;
void main(){
int count[10]; //frequency of occurrence of digits
int digit; //input digit.
int i; //loop counter
//read the digits
do {
cin >> digit;
if (digit>=0 && digit<=9)
count[digit]++;
} while(digit != -1); //stop if the input number is -1
//print the frequency
for (i=0; i<10;i++){
cout << "Frequency of " << i << " is " << count[i] <<
endl;
}
}
12
The actual output (incorrect!)
3 4 1 3 1 3 -1
Frequency of 0 is 2089878893
Frequency of 1 is 2088886165 If your program
Frequency of 2 is 1376256 generates different
Frequency of 3 is 3 output in PASS and
Local PC, it could
Frequency of 4 is 1394145 be caused by this
Frequency of 5 is 1245072 problem…
Frequency of 6 is 4203110
Frequency of 7 is 1394144
Frequency of 8 is 0
Frequency of 9 is 1310720
The exact values in your system may differ.
13 but obviously the numbers are not making sense
It's a good practice to initialize arrays
Otherwise, the values of the elements in the array is
unpredictable.
A common way to initialize an array is to set all the
elements to zero
for (i=0; i<10; i++)
count[i]=0;
For information: Arrays declared in global scope are
initialized with zeroes when the program start!
14
Array initializer
int mark [10]={100, 90};
Define an array of 10 elements, set the 1st element to 100 and
the 2nd element to 90.
If we list fewer values than the array size (10).
The remaining elements are set to 0 by default
To initialize all elements to 0: int mark[10]={0};
IMPORTANT: This notation is ONLY allowed during initialization!
int X[3]; Cannot write
int X[3] = {1,2,3}; = {…} here !
X = {1,2,3};
CORRECT WRONG!
15
The program: buggy version
#include <iostream>
using namespace std;
void main(){
int count[10]; //frequency of occurrence of digits
int digit; //input digit.
int i; //loop counter
//read the digits
do {
cin >> digit;
if (digit>=0 && digit<=9)
count[digit]++;
} while(digit != -1); //stop if the input number is -1
//print the frequency
for (i=0; i<10;i++){
cout << "Frequency of " << i << " is " << count[i] <<
endl;
}
}
16
Correct program
#include<iostream>
using namespace std; Side Notes:
void main(){ By changing the if() statement a little bit,
int count[10];
int digit; you may use it to count other data:
int i;
e.g. Count only Uppercase:
//initialization if (ch>='A' && ch<='Z')
for (i=0;i<10;i++){
count[i]=0; count[ ch – 'A' ]++;
}
//read the digits
do {
cin >> digit;
if (digit>=0 && digit<=9)
count[digit]++;
} while(digit != -1); //stop if the input number is -1
//print the frequency
for (i=0; i<10;i++){
cout << "Frequency of " << i << " is " << count[i] << endl;
}
}
17
Array Initialization Summary
i.e. Ask the compiler to count for you…
Note: you MUST provide initial values
if there's no size
18
Example 3: Comparing 2 arrays
We have two integers arrays, each with 5 elements
int array1[5]={10, 5, 3, 5, 1};
int array2[5];
The user input the values of array2
Compare whether all the elements in array1 and
array2 are the same
19
Array equality
Note that you have to compare array element 1 by 1.
The following code is WRONG!
if (array1 == array2)
cout << "The arrays are equal ";
else
cout << "The arrays are not equal ";
Similarly, you cannot compare strings (i.e. char array) directly
if (name == "Alan") … //WRONG!
if ("Alan" == "Alan") … //WRONG!
Then, how to check for whether the two arrays are equal?
20
Use (for) loop to check each entry one by one !
The Program
#include <iostream>
using namespace std;
void main(){ Input 5 numbers
int array1[5]={10, 5, 3, 5, 1};
int array2[5]; 10 5 3 5 1
int i; The arrays are equal
bool arrayEqual=true;
cout << "Input 5 numbers\n"; Input 5 numbers
for (i=0;i<5;i++)
cin >> array2[i];
10 4 3 5 2
The arrays are not equal
for (i=0; i<5 && arrayEqual; i++){
if (array1[i]!=array2[i]){
arrayEqual=false;
}
}
if (arrayEqual)
cout << "The arrays are equal";
else
cout << "The arrays are not equal";
}
21
Example 4: Searching
Read 10 numbers from the user and store them in an array
User input another number x.
The program checks if x is an element of the array
If yes, output the index of the first occurrence of the element
If no (i.e. not found), output -1
22
Searching for x=15 (Case 1)
Suppose N=6
i=1
a[i]!=x
2 4 15 0 15 -7
i=0 i=2
a[i]!=x a[i]==x
Same value at i=2
break out of the loop
23
Searching for x=8 (Case 2)
i=0 i=2 i=4
a[[i] !=x a[[i] !=x a[[i] !=x
2 4 15 0 15 -7
i=1 i=3 i=5
a[[i] !=x a[[i] !=x a[[i] !=x
24
Output -1
The program
#include <iostream>
using namespace std;
const int N=10 Que: How to detect the not-found case?
void main() A few possible ways:
{
int a[N], i, x, pos;
1) Use a Boolean to signal whether there's
a match. (false in the beginning, update
for (i=0; i<N; i++)
cin >> a[i]; to true if a match is found)
cout << "Input your target: ";
cin >>x; 2) Similar to 1), but instead of Boolean, use
for (i=0, pos=-1; i<N; i++) { a "special value" to represent not found
if (a[i]==x) { (e.g. in here, pos=-1)
pos=i;
break;
}
}
if (pos == -1)
cout << "Target not found!\n");
else
cout << "Target found at position " << pos << endl;
25 }
Example 5: Sorting
One of the most common applications in CS is sorting
arranging data by their values: {1, 5, 3, 2} {1, 2, 3, 5}
There are many algorithms (methods) for sorting
Selection Sort
Bubble Sort "Classic" sorting algorithms
Insertion Sort
Quick Sort
Merge Sort Faster, more complex sorting algorithms
Heap Sort
Based on iteratively swapping two elements in the array so that
eventually the array is ordered.
The algorithms differ in how they choose the two elements.
In here, we use Bubble-Sort as an Example.
In this course, you may use whatever algorithm you want
26
Bubble Sort – Inner loop (bubbling)
The array is divided into two parts: sorted and unsorted.
Initially the whole array is unsorted.
In each pass, start from the end, we swap neighboring elements if they are
out of sequence (so called "bubbling up"). Inner Loop (Bubbling)
Outer Loop (Pass) 23 78 45 8 32 56
Bubbling
23 78 45 8 32 56
Original
23 78 45 8 32 56
23 78 8 45 32 56
After Pass 1
23 8 78 45 32 56
8 23 78 45 32 56
27 Sorted
Bubble Sort – Inner loop (bubbling)
The corresponding code (only for the inner part) is as follows:
Repeat as long as we haven’t
Starting from last item
(i.e. position n-1)
reach the front (i.e. position 0)
Moving from back to front
for(k=n-1; k>0; k--) {
If the item (i.e. a[k]) is smaller than
if (a[k]<a[k-1]) { the one before you (i.e. a[k-1])...
tmp = a[k];
a[k] = a[k-1]; Swapping items, you
a[k-1] = tmp; may refer to Lec2 p41
}
}
Bubble Sort – Outer loop
After bubbling up, the smallest element must be at [0]
If we repeat the whole bubbling again, the second smallest element is in [1]
In other words, if we repeat for N-1 times, the whole array will be sorted!
29
bubble-sort dance: [Link]
#include <iostream>
using namespace std; Bubble Sort
Demo!
const int n=10;
j=0 F void main() {
j++
j<n-1 int a[n], j, k, tmp;
Bubbling T
cout <<"Input" << n <<" numbers: ";
F for (j=0; j<n; j++)
k=n-1
k-- cin >> a[j];
k>j
T // j = pass no. = length of sorted region
for (j=0; j<n-1; j++) // outer loop, simply
// repeats n-1 times!
F a[k]< for (k=n-1; k>j; k--) // bubbling
a[k-1] if (a[k]<a[k-1]) {
tmp = a[k]; // swap neighbors
T a[k] = a[k-1];
swap a[k] a[k-1] = tmp;
and a[k-1] }
cout << "Sorted: ";
for(j=0; j<n; j++) cout << a[j];
}
30
Multi-dimensional Array
Multi-dimensional array refers to an array with more than one index.
Despite its logical representation, on physical storage, the multi-
dimensional array is still stored in contiguous memory space
To define a two-dimensional array, we specify the size of each
dimension as follows
int table[30][100]; //[row][column]
In C/C++, the array will be stored in the "row-major" order!
i.e. first block of memory stores table[0][0] to table[0][99],
then the next block for table[1][0] to table[1][99]… and so on
31
Adopted in C++:
32 Not Adopted in C++:
Multi-dimensional Array
To access an element of the array, we specify an index for each
dimension:
cin >> table[i][j]; //[row][column]
The above statement will read an integer into ith row and
jth column of the array. (not ith column and jth row!)
Higher dimensions (3D, 4D…etc) are also possible:
(However, in this course, we'll focus mainly up to 2D..)
int Cube[100][100][100];
33
Example: Print the 9x9 Multiplication Table
void main() {
int row,col,Table[10][10]; //Note: not [9][9]. Note: Index 0 not used !
//Generate Table
for (row=1;row<10;row++) {
for (col=1;col<10;col++) {
Table[row][col]=row*col;
}
}
//Output
for (row=1;row<10;row++) {
for (col=1;col<10;col++) {
cout<<Table[row][col]<<'\t'; //<Tab> after each CELL
}
cout<<endl; //<Enter> at the end of each ROW
}
}
Summary
Array is a sequence of variables of the same data type
Array elements are indexed and can be accessed by the
use of subscripts (integer). e.g. array_name[4]
The first item is [0], and the last one is [n-1] (not 1 to n!)
Array elements are stored contiguously in memory space
Sample use: Storing collection of numbers, statistics…etc.
Array Declaration, Initialization, Searching and Sorting
Array cannot be copied or compared directly. Must copy or
compare the elements one-by-one using loop.
Array can be Multi-dimensional, i.e. 1D , 2D
35