Transcript Monday, September 02, 2002

Thursday, January 04, 2007
I think and think for months and
years. Ninety-nine times, the
conclusion is false. The hundredth
time I am right.
- Albert Einstein
Arrays Review
Arrays used for grouping of related variables.
int a1;
int a[5];
int a2;
int a3;
int a4;
int a5;
 Individual elements of array accessed by
indices.
 Easier to use in loops.
Arrays Review
int a[5] = {10, 20, 30, 40, 50};
a[0] is 10
a[1] is 20
a[2] is 30
a[3] is 40
a[4] is 50
 No boundary checking of arrays because of
efficiency reasons.
 Error checking can slow down the program
execution.
A variable is a named memory location that may be
assigned a value.
0x0012F588
0x0012F584
50
40
a[4]
a[3]
0x0012F580
0x0012F57C
0x0012F578
30
20
10
a[2]
a[1]
a[0]
What is the difference
between two memory
addresses?
Static array declaration requires a constant
int my_array[10]; //ok
const int x=10;
int my_array[x]; //also ok
#define size 10
int main()
{
int a[size]; //also ok
return 0;
}
What is wrong here?
const int x;
 The word "algorithm" itself is quite interesting; at
first glance it may look as though someone
intended to write "logarithm" but jumbled up the
first four letters. The word did not appear in
Webster's New World Dictionary as late as 1957;
we find only the older form "algorism" with its
ancient meaning, i.e., the process of doing
arithmetic using Arabic numerals. In the middle
ages, abacists computed on the abacus and
algorists computed by algorism. Following the
middle ages, the origin of this word was in doubt,
and early linguists attempted to guess at its
derivation by making combinations like algiros
[painful] + arithmos [number]; others said no, the
word comes from "King Algor of Castile."
 Finally, historians of mathematics found the true
origin of the word algorism: it comes from the
name of a famous Persian textbook author, Abu
Ja`far Mohammed ibn Mûsa al-Khowârizmî literally, "Father of Ja´far, Mohammed, son of
Moses, native of Khowârizm." Khowârizm is
today the small Soviet city of Khiva. AlKhowârizmî wrote the celebrated book Kitab al
jabr w'al-muqabala ("Rules of restoration and
reduction"); another word, "algebra", stems from
the title of his book, although the book wasn't
really very algebraic.
 Gradually the form and meaning of "algorism"
became corrupted; and changed from "algorism"
to "algorithm”.
Sorting an array
double dArray[10]=
{34, 5.6, 0.9, 345.7, 54.1, 23.5, 2.5,
6.78, 12.4, 13.9};
Sorting an array
int main(void){
double dArray[10]={34, 5.6, 0.9, 345.7, 54.1, 23.5,
2.5, 6.78, 12.4, 13.9};
int i, j, size=10;
double temp;
for (i=0; i<size; i++){
for (j=i+1; j<size; j++){
if (dArray[j]<dArray[i]){
temp=dArray[j];
dArray[j]=dArray[i];
dArray[i]=temp;
}
}
} //in-place sorting
return 0; }
Self Test: Sorting an array
Modify the previous program so that it does not
do in-place sorting, but instead stores the sorted
list in another array.
Self Test: Sorting an array
// Using the bubble sort to order an array.
int main()
{
int nums[10];
int a, b, t;
int size;
size = 10; // number of elements to sort
// give the array some random initial values
for(t=0; t<size; t++) nums[t] = rand();
Self Test: Sorting an array (Simulate)
// This is the bubble sort.
for(a=1; a<size; a++)
for(b=size-1; b>=a; b--) {
if(nums[b-1] > nums[b]) { // if out of order
// exchange elements
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
}
} // This is the end of the bubble sort.
Two Dimensional Arrays
 C++ supports multi-dimensional arrays


type array_name[row_size][column_size]
int matrix[3][4];
row[0]
row[1]
row[2]
Accessing Array Elements
 int matrix[3][4];



matrix has 12 integer elements
matrix[0][0] element in first row, first column
matrix[2][3] element in last row, last column
Two Dimensional Arrays
int main()
{
int i, j, num[3][4];
for(i=0; i<3; ++i) {
for(j=0; j<4; ++j) {
num[i][j] = (i*4)+j+1;
cout << num[i][j] << “\t“;
}
cout << “\n”;
}
return 0;
} // output?
Output:
1
2
5
6
9
10
3
7
11
4
8
12
Two Dimensional Arrays
int main()
What happens if I change [3][4] to [2][6]?
{
int i, j, num[2][6];
for(i=0; i<2; ++i) {
for(j=0; j<6; ++j) {
num[i][j] = (i*6)+j+1;
cout << num[i][j] << “ “;
}
cout << “\n”;
}
return 0;
} // output?
Output:
1
2
7
8
3
9
4
10
5
11
6
12
Self Test: Arrays
Print the transpose of a 2-D array.
Two dimensional arrays
int E[][2]={
1,2,
3,4
};
 Matrix Multiplication
Nested Loops Review
int main()
{
int i, j;
for(i=0; i<3; i++) {
for(j=0; j <= 4; j++)
cout<<“The value of i=” <<i<<“ and j= ”<<j<<“\n”;
cout<<”Out of the inner for-loop\n";
}
return 0;
}
Nested Loops Review
The value of i=0 and j=0
The value of i=0 and j=1
The value of i=0 and j=2
The value of i=0 and j=3
The value of i=0 and j=4
Out of the inner for-loop
The value of i=1 and j=0
The value of i=1 and j=1
The value of i=1 and j=2
The value of i=1 and j=3
The value of i=1 and j=4
Out of the inner for-loop
The value of i=2 and j=0
The value of i=2 and j=1
The value of i=2 and j=2
The value of i=2 and j=3
The value of i=2 and j=4
Out of the inner for-loop
Practice Exercise!
 Write down the code to multiply two
matrices of sizes NxM and MxQ
respectively.
Strings
 One dimensional arrays is used to create
character strings
 In C++, a string is defined as a character
array that is terminated by a null
 A null is specified using ‘\0’ and is zero
 Because of the null terminator, it is
necessary to declare a character to be one
character longer than the largest string it
will hold.
Character Arrays
char word[6] = “fruit”;
//word has size 6
char list[6] = {‘f’,’r’,’u’,’i’,’t’, ‘\0’};
//list of characters, not a string
Not necessary to add null terminator at end of string
constants.
Character Arrays
char word[] = “fruit”; //word has size 6
 What is wrong with the following?
char name[5]="class";
int MyArray[];
 cout<<'3';
 cout<<',';
 cout<<'\n';
 'a' and "a" are different