Transcript Chapter 7

Chapter 7
Arrays
Introductions
• Declare 1 variable to store a test score of 1 student.
int score;
• Declare 2 variables to store a test score of 2 students.
int score1, score2;
• Declare 100 variables to store a test score of 100
students.
int score1; … ; score100;
• Is it a smart ways? NO
• Solution: Arrays
Array
• a composite structure consisting of a list of
data of the same type.
• Syntax:
type name[size]; //1-dimensional array
type name[size1][size2]; //2-dimensional array
• Examples
int score[25]; //1-dimensional array
int matrix[2][3]; //2-dimensional array
Array Notes
• subscripts start from 0. Can be any integral type.
• may store data of any type – including structs,
objects or other arrays.
• Declaration: Square brackets after identifier
indicate array. Number in brackets indicates
number of elements in array. Must be a constant.
• Size of array is determined at compiler time
(static allocation); cannot be changed during
runtime.
Array Elements
•
Individual elements are accessed by using the name of the array and its index.
int score[8], n=4;
cin>> score[0] ; // user input and stored in score[0].
score[2]=3; // assign 3 to value stored in score[2]
score[n+1]=8; // assign 8 to value stored in score[5]
score[0]++; // increment value stored in score[3]
score[n++] = 6; // assign 6 to value stored in score[4] and increase n by 1 (n=5)
score[++n] = 10; // increment index to move to next value in the array (score[6]) and assign 10 to it.
•
•
By incrementing the subscript, we can access entire array in 1 loop.
Use a FOR loop to process.
int size=8;
for (int i=0;i<size;i++)
{
cout << “Enter the score #” << i ;
cin >> score[i];
}
•
We can use WHILE loop, too.
int n=0;
while (n<size)
{
cout << “Score[” << n << “]: ” << score[n++] << endl;
}
1020
1022
1024
1026
1028
4
5
1030
1032
1034
8
1036
1038
3
6
10
score[0]
score[1]
score[2]
score[3]
score[4]
score[5]
score[6]
score[7]
Array Memory Allocation
• Array elements are
stored contiguously.
• Need only know address
of a[0]-compiler
increments by size of
type of array to find next
value.
• Caution: index out of
range won’t produce
error, just garbage and
may overwrite good data.
int a = score[8];
score[9] = 10;
1020
1022
1024
5
1026
1028
7
1030
1032
1034
1036
1038
8
7
3
6
10
4
5
10
score[0]
score[1]
score[2]
score[3]
score[4]
score[5]
score[6]
score[7]
Array Initialization
• No array size specified. Numbers of items will be used to
determine the size
int a[] = {3,4,5,2}; // sets up array from a[0] to a[3] (4 elements)
• If number of initialized elements is less than array size then
remaining elements are initialized to zero.
int a[3] = {1}; // {1,0,0};
• Initialized all to zero.
int a[3] = {0};
Arrays in Functions
(Single element)
• An element of an array can be passed into any
function requiring a variable of that type.
• We can process each element of the array as a
single value.
• Can pass to a function as call-by-value or callby-reference.
Arrays in Functions
(Single element)
void main () {
int score[5] = {7, 10, 8, 5, 9};
addOne(score[3]);
isPass(score[4]);
}
void addOne (int& point) {
point++;
}
bool isPass (int point) {
return (++point >= 8);
}
1020
1022
1024
1026
1028
9
7
10
8
5
9
1020
7
1022
1024
1026
1028
10
1020
1022
7
1024
1026
1028
8
6
9
score[0]
score[1]
score[2]
score[3]
score[4]
score[0]
score[1]
score[2]
score[3]
score[4]
6
score[0]
score[1]
score[2]
score[3]
9
score[4]
10
8
Entire Array as Function Arguments
• Always passes in functions as call-by-reference.
– The array name is the address of the first element.
It is called the base address.
– The ampersand (&) is implied and not written.
• The [] in the formal parameter list tells the compiler
that it is an array. We also need to pass in the size of
the array.
• The function call just passes in the array name.
Entire Array as Function Arguments
void main () {
int score[5];
getScore(score, 5);
}
void getScore (int s[], int size) {
for (int i=0; i<size; i++) {
cout << “Enter score# ” << i;
cin >> s[i];
}
}
1020
1022
1024
1026
1028
?
1020
1022
1024
1026
7
1028
?
?
?
?
10
8
5
9
score[0]
score[1]
score[2]
score[3]
score[4]
score[0]
score[1]
score[2]
score[3]
score[4]
Entire Array as Function Arguments
void main () {
int score[5];
getScore(score, 5);
printScore(score, 5);
}
void getScore (int s[], int size) {
for (int i=0; i<size; i++) {
cout << “Enter score# ” << i;
cin >> s[i];
}
}
void printScore (int s[], int size) {
for (int i=0; i<size; i++) {
cout << “Score# ” << i << s[i] << endl;
s[i]--;
}
}
1020
1022
1024
1026
1028
?
1020
7
1022
1024
1026
1028
10
1020
1022
1024
1026
1028
6
?
?
?
?
8
5
9
9
7
4
8
score[0]
score[1]
score[2]
score[3]
score[4]
score[0]
score[1]
score[2]
score[3]
score[4]
score[0]
score[1]
score[2]
score[3]
score[4]
const Array Argument
• Passing in an array is a new kind of argument called an
array argument
• Since arrays are always passed-by-reference, if we want
to prevent the contents of the array from changing, use
const.
• The word const in the function declaration prevents us
from inadvertently changing the contents of the array.
• Used in both function prototype and definition, not in
function call. Failure to be consistent in using const in
both places results in a linkage error.
Entire Array as Function Arguments
void main () {
int score[5];
getScore(score, 5);
printScore(score, 5);
}
void getScore (int s[], int size) {
for (int i=0; i<size; i++) {
cout << “Enter score# ” << i;
cin >> s[i];
}
}
void printScore (const int s[], int size) {
for (int i=0; i<size; i++) {
cout << “Score# ” << i << s[i] << endl;
// s[i]--; syntax error
}
}
1020
1022
1024
1026
1028
?
1020
7
1022
1024
1026
1028
10
1020
1022
1024
1026
1028
7
?
?
?
?
8
5
9
10
8
5
9
score[0]
score[1]
score[2]
score[3]
score[4]
score[0]
score[1]
score[2]
score[3]
score[4]
score[0]
score[1]
score[2]
score[3]
score[4]
Functions that Return an Array
• Since to return an array is to return an
address, a special type of variable is used.
This is called a pointer.
• At this point, we have no way to return a
whole array.
• We can, however, omit the const modifier and
change the array that way.
Programming with Arrays
• Partially Filled Arrays
– Since array allocation is static, may not use whole
array. Choose array size to be largest possible
amount but keep track of number of valid values
entered.
– Must pass in a parameter (int size) to indicate how
many spaces have valid data.
Partially Filled Arrays
void main () {
int score[25], count=0;
getScore(score, 25, count);
int indexOf5 = search(5, count);
}
void getScore (int s[], int size, int& num_used) {
cout << “Enter up to ” << size << “non-negative numbers. \n”
<< “Enter a negative number to end.” << endl;
int next, index=0;
cin >> next;
while (next >=0 && index < size) {
s[index++] = next;
cin >> next;
}
num_used = index;
}
Notes:
•getScore must return
number_used (call-byreference)
•Process until a
sentinel value is read
or max-size-1 reached.
•Functions to process
array functions must
pass in number_used
Sequential Search of an array
• Go element by element until either target is found or
reach end of list.
//Pre-Condition: num_used cannot greater than the declared size
//
Also, s[0] through s[num_used] have values.
//Post-Condition: return the index of the first occurrence of the target.
//
Otherwise, return -1
int search (const int s[], int num_used, int target) {
for (int i=0; i<num_used; i++) {
if (s[i] == target)
return i;
}
return -1;
}
Find the smallest/largest Number
• Go element by element to find the smallest/largest
number.
//Pre-Condition: size: numbers of elements in the array
//
Also, s[0] through s[size-1] have values.
//Post-Condition: return the smallest number in the array.
int smallest (const int s[], int size) {
int theSmallest = s[0];
for (int i=0; i < size; i++) {
if (s[i] < theSmallest)
theSmallest = s[i];
}
return theSmallest;
}
Sorting an Array
• Arrange the elements of an array in a specific order.
• Sorting algorithms:
– Bubble sort
– Selection sort
– Insertion sort
– Merge sort
– Heapsort
– Quicksort
–…
Selection Sort
• Algorithm: finds the minimum value, swaps it
with the value in the first position, and
repeats these steps for the remainder of the
list.
• For Array: Finds the smallest element in an
array and swaps it with the element in
position 0. Then, finds the smallest element
in the remaining array and swaps it with the
element in position 1, etc.
Index Of Smallest
int IndexOfSmallest (const int a[], int startIndex, int num_used)
{
int min = a[startIndex], indexOfMin = startIndex;
for (int i = startIndex+1; i < num_used; i++)
if (a[i] < min) {
min = a[i]; // min is the smallest number of a[startIndex] through a[i]
indexOfMin = i;
}
return indexOfMin;
}
void swap (int& v1, int& v2)
{
int temp = v1;
v1 = v2;
v2 = temp;
}
SelectionSort()
int SelectionSort(int a[], int num_used)
{
int indexOfNextSmallest;
for (int i = 0; i < num_used-1; i++) {
indexOfNextSmallest = IndexOfSmallest (a, i, num_used);
swap (a[i], a[indexOfNextSmallest ]);
}
}
a[0]
a[1]
a[2]
a[5]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
8
6
10
2
16
4
18
14
12
20
i=0
2
6
10
8
16
4
18
14
12
20
i=1
2
4
10
8
16
6
18
14
12
20
i=2
2
4
6
8
16
10
18
14
12
20
i=3
2
4
6
8
16
10
18
14
12
20
i=4
2
4
6
8
10
16
18
14
12
20
i=5
Multidimensional Arrays
• Are arrays of arrays
• Syntax:
Type ArrayName[ROW][COL] //2-dimensional
Type ArrayName[Width][Height][Depth] //3-dimensional
• Examples:
int matrix[2][3] //2x3 matrix
int rubik[3][3][3] //cube
2-Dimensional Arrays
• Initialization:
Col 1
int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
• C++ stores all arrays as a single onedimensional array.
• The array name is a constant pointer to
the first dimensional array.
Col 3
1
2
3
Row 1
4
5
6
7
8
9
Row 2
Row 3
1020
1
matrix[0][0]
1022
1024
1026
1028
2
matrix[0][1]
matrix[0][2]
matrix[1][0]
1030
6
• if row size is unspecified, it is taken from
the number of arrays in the brackets.
Must always give column size.
int matrix[][3] = { {1,2,3}, {4,5,6} }; // 2x3
int matrix[][3] = { {1,2,3}, {4,5,6}, {7,8,9} }; // 3x3
int matrix[][2] = { {1,2}, {3,4}, {5,6} }; // 3x2
Col 2
matrix[2][3]
3
4
5
matrix[1][1]
matrix[1][2]