Transcript Document

Chapter 7 Single-Dimensional
Arrays and C-Strings
§7.1 Array Basics
§7.2 Array as Parameter
§7.3 Array Searching
§7.4 Array Sorting
§7.5 Character Array and C-string
Array (数组)?
• An example problem:
– Read one hundred numbers, compute their
average, and find out how many numbers are
above the average.
AnalyzeNumbers
2
§7.1 Array Basics
• Array is a data structure that represents a
collection of the same type of data.
double myList [10];
Allocated in the memory
continuously!
Array element at
index 5
3
myList[0]
5.6
myList[1]
4.5
myList[2]
3.3
myList[3]
13.2
myList[4]
4.0
myList[5]
34.33
myList[6]
34.0
myList[7]
45.45
myList[8]
99.993
myList[9]
111.23
Starting address
Element value
Ending address
Declaring Arrays
datatype arrayname[arraysize];
Example:
double mylist[10];
Note: the array size in the declaration must be
a constant expression.
int size = 4; double myList[size];
const int size = 4; double myList[size];
4
Accessing Arrays
• Each element in the array is represented as an
indexed variable:
arrayname[index];
index(下标): 0..arraysize-1
• Indexed variable can be used in the same way
as a regular variable, for example:
double mylist[10];
mylist[9]=3.1;
mylist[2]=mylist[0]+mylist[1];
5
Caution: Bound Checking
(边界检查)
• The bound of an array
– The scope of the index: 0..arraysize-1
• C++ compiler does not check array’s bound!!!
Correct in syntax!
Error in runtime!
myList[-1]
myList[10]
myList[15]
int i;
myList[i+10];
6
Initializing Arrays
• Default initialization by system
– To arbitrary values on creation
• Array Initializers
– Declaring, creating, initializing in one step
type arrayname[arraysize] =
{value0, value1, ..., valuek};
Example:
double mylist[4] = {1.9, 2.9, 3.4, 3.5};
Caution:
Do it in one statement!
7
double myList[4];
myList = {1.9, 2.9, 3.4, 3.5};
Notes
• Implicit Size
– To omit the array size when declaring and creating an array
using an initializer
– C++ automatically figures out how many elements are in
the array
Example:
double myList[] = {1.9, 2.9, 3.4, 3.5};
• Partial Initialization
– To initialize a part of the array
– The rest elements are initialized to “0” or “a”
Example:
double myList[4] = {1.9, 2.9};
double myList[4] = {};
8
Initializing arrays with random values
The following loop initializes the array myList with random
values between 0 and 99:
for (int i = 0; i < ARRAY_SIZE; i++)
{
myList[i] = rand() % 100;
}
9
Check Points
• Which is valid array declaration?
double d[30];
char[30] r;
int i[] = (3, 4, 4, 2);
float f[3] = {2.1, 3};
• What’s the printout of the following code?
int main(){
int numbers[30];
cout<<"number[0] is "<<numbers[0]<<endl;
cout<<"number[30] is "<<numbers[30]<<endl;
}
10
Processing Arrays
Printing arrays:
for (int i = 0; i < ARRAY_SIZE; i++)
{
cout << myList[i] << " ";
}
11
Processing Arrays
• Copying Arrays
int list[3], mylist[3];
…
list = myList;
for (int i = 0; i < 3; i++)
list[i] = myList[i];
• Summing All Elements
• Finding the Largest Element
double max = myList[0];
for (int i = 1; i < ARRAY_SIZE; i++) {
if (myList[i] > max)
max = myList[i];
}
12
Processing Arrays
Finding the smallest index of the largest element
double max = myList[0];
int indexOfMax = 0;
for (int i = 1; i < ARRAY_SIZE; i++)
{
if (myList[i] > max)
{
max = myList[i];
indexOfMax = i;
}
}
13
Processing Arrays
Random Shuffling:
srand(time(0));
for (int i = 0; i < ARRAY_SIZE; i++)
{
// Generate an index randomly
int index = rand() % ARRAY_SIZE;
double temp = myList[i];
myList[i] = myList[index];
myList[index] = temp;
}
14
Problem: Lotto Numbers
Your grandma likes to play the Pick-10 lotto.
Each ticket has 10 unique numbers ranging from 1 to 99.
Every time she buys a lot of tickets. She likes to have her
tickets to cover all numbers from 1 to 99.
Write a program that reads the ticket numbers from a file
and checks whether all numbers are covered. Assume the
last number in the file is 0.
LottoNumbers
15
Problem: Deck of Cards
0
.
.
.
12
13
.
.
.
25
26
.
.
.
38
39
.
.
.
51
13 Spades (♠)
13 Hearts (♥)
13 Diamonds (♦)
13 Clubs (♣)
deck
[0] 0
.
.
.
.
.
.
[12] 12
[13] 13
.
.
.
.
.
.
[25] 25
[26] 26
.
.
.
.
.
.
[38] 38
[39] 39
.
.
.
.
.
.
[51] 51
Random shuffle
deck
[0] 6
[1] 48
[2] 11
[3] 24
[4] .
[5] .
.
.
.
.
.
.
[25] .
[26] .
.
.
.
.
.
.
[38] .
[39] .
.
.
.
.
.
.
[51] .
DeckOfCards
16
Card number 6 is
5 of Spades
Card number 48 is
10 of Clubs
Card number 11 is
Queen of Spades
Card number 24 is
Queen of Hearts
§7.2 Array as Parameter
• Passing array as parameter
– Passing an array as an argument, same as passing
a simple variable/value
Caution: passing size along with array!
Otherwise, the function won’t know how
many elements are in the array!
int list[3];
…
maximum = max(list,3);
17
PassArrayDemo
Array as Parameter
• Array is passed by reference
– The starting address is passed to the function
– To avoid copying overhead in pass-by-value
EffectOfPassArrayDemo
18
Array as Parameter
• Two-direction passing
– The change on formal parameter is effective on
actual parameter
• Good!
void reverse(const int list[], list newList[], int size)
– Return array from functions
int[] reverse(int x, int y)
As “parameter” not “return value”!!!
• Not good!
ReverseArray
– Sometimes accident change may cause error
• Using “const” parameter to avoid such mistake
void reverse(const int list[], int size)
19
ConstArrayDemo
Problem: Counting Letter Occurrence
• Generate 100 lowercase
letters randomly and assign
to an array of characters.
• Count the occurrence of
each letter in the array.
chars[0]
counts[0]
chars[1]
counts[1]
…
…
…
…
…
…
…
…
chars[98]
counts[24]
chars[99]
counts[25]
CountLettersInArray
20
Check Points
• What’s the printout?
void m(int x, int y[]){
x = 3;
y[0] = x;
}
int main(){
int n = 0;
int na[1];
m(n, na);
cout<< “n is "<<n<<endl;
cout<< “na is "<<na[0]<<endl;
}
21
void reverse(int list[], int size){
for(int i = 0; i<size/2; i++){
int temp = list[i];
list[i]=list[size-1-i];
list[size-1-i]=temp;
}
}
int main(){
int list[]={1, 2, 3, 4, 5};
int size = 5;
reverse(list, size);
for(int i =0; i<size; i++)
cout<<list[i]<<" ";
cout<<endl;
}
§7.3 Array Searching
• Searching (查找)
– A common task in computer programming.
– The process of looking for a specific element in an
array, for example,
• discovering whether a certain score is included in a list
of scores.
• Searching algorithms
– Linear search (线性查找)
– Binary search(折半查找、二分查找)
–…
22
Linear Search
• Input: the key and array to search
• Output: the index of matching element or -1
• Basic idea:
– Compare the key with each element in the array sequentially
int linearSearch(int list[], int key, int arraySize)
{
for (int i = 0; i < arraySize; i++)
{
if (key == list[i])
return i;
[0] [1] [2] …
}
list
return -1;
key Compare key with list[i] for i = 0, 1, …
}
Terminate once a
matching element is found!
23
Linear Search Animation
Key
List
3
6 4 1 9 7 3 2 8
3
6 4 1 9 7 3 2 8
3
6 4 1 9 7 3 2 8
3
6 4 1 9 7 3 2 8
3
6 4 1 9 7 3 2 8
3
6 4 1 9 7 3 2 8
24
Binary Search
• Input: the key and sorted array to search
e.g., 2 4 7 10 11 45 50 59 60 66 69 70 79
• Output: the index of matching element or
(-insertionpoint -1)
Insertionpoint for “54”
• Basic idea:
– Repeatedly compare the middle to see the key should
be in which “half” of the list
25
Basic Idea
26
Example Scenario—key found
key is 11
low
key < 50
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
list
2
low
key > 7
mid
4 7 10 11 45
mid
[0] [1] [2] [3] [4] [5]
list 2 4 7 10 11 45
mid
high
[3] [4] [5]
key == 11
27
50 59 60 66 69 70 79
high
low
list
10 11 45
high
Example Scenario—key not found
key is 54
low
key > 50
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
list
2
mid
4
7 10 11 45
high
50 59 60 66 69 70 79
low
key < 66
mid
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
list
59 60 66 69 70 79
low mid
high
[7] [8]
key < 59
list
59 60
low
high
[6] [7] [8]
59 60
28
high
Source Code
int binarySearch(int list[], int key, int arraySize) {
int low = 0;
int high = arraySize - 1;
while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid]) high = mid - 1;
else if (key == list[mid]) return mid;
else low = mid + 1;
}
return -low-1;
}
29
§7.4 Array Sorting
• Sorting (排序)
– Also a common task in computer programming
– The process of placing the elements in a specific
order. For example,
• Arranging the student names in alphabetical order
• Sorting algorithms
– Selection sort (选择排序),
– Insertion sort (插入排序),
– ...
30
Selection Sort
• Input: unsorted array
• Output: sorted array
• Basic idea:
– Repeatedly finds the largest number in the
sub-array and places it last until the whole list
is sorted
31
Selection Sort
int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted
2 9 5 4 8 1 6
2 6 5 4 8 1 9
2 6 5 4 1 8 9
2 1 5 4 6 8 9
2 1 4 5 6 8 9
2 1 4 5 6 8 9
1 2 4 5 6 8 9
32
Selection Sort
for (int i = listSize - 1; i >= 1; i--)
{
select the largest element in list[0..i];
swap the largest with list[i], if necessary;
// list[i] is in its correct position.
// The next iteration apply on list[0..i-1]
}
list[0] list[1] list[2] list[3] ...
list[0] list[1] list[2] list[3] ...
list[0] list[1] list[2] list[3] ...
list[0] list[1] list[2] list[3] ...
...
list[0]
33
list[10]
list[9]
list[8]
list[7]
for (int i = listSize - 1; i >= 1; i--)
{
select the largest element in list[0..i];
swap the largest with list[i], if necessary;
// list[i] is in its correct position.
// The next iteration apply on list[0..i-1]
}
double currentMax = list[0]; if (currentMaxIndex != i) {
int currentMaxIndex = 0;
list[currentMaxIndex]=list[i];
list[i] = currentMax;
for (int j = 1; j <= i; j++) {
}
if (currentMax < list[j]) {
currentMax = list[j];
currentMaxIndex = j;
}
}
34
Insertion Sort
• Input: unsorted array
• Output: sorted array
• Basic idea:
– Repeatedly inserting an unsorted element into a
sorted sub-array until the whole list is sorted.
35
Insertion Sort
int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted
2 9 5 4 8 1 6
2 9 5 4 8 1 6
2 5 9 4 8 1 6
2 4 5 9 8 1 6
2 4 5 8 9 1 6
1 2 4 5 8 9 6
1 2 4 5 6 8 9
36
Insertion Sort
37
Step 1: Initially, the sorted sublist contains the
first element in the list. Insert 9 to the sublist.
2
9
5
4
8
1
6
Step2: The sorted sublist is {2, 9}. Insert 5 to the
sublist.
2
9
5
4
8
1
6
Step 3: The sorted sublist is {2, 5, 9}. Insert 4 to
the sublist.
2
5
9
4
8
1
6
Step 4: The sorted sublist is {2, 4, 5, 9}. Insert 8
to the sublist.
2
4
5
9
8
1
6
Step 5: The sorted sublist is {2, 4, 5, 8, 9}. Insert
1 to the sublist.
2
4
5
8
9
1
6
Step 6: The sorted sublist is {1, 2, 4, 5, 8, 9}.
Insert 6 to the sublist.
1
2
4
5
8
9
6
Step 7: The entire list is now sorted
1
2
4
5
6
8
9
How to Insert?
[0] [1] [2] [3] [4] [5] [6]
list
2
5 9
4
Step 1: Save 4 to a temporary variable currentElement
[0] [1] [2] [3] [4] [5] [6]
list
2
5
9
Step 2: Move list[2] to list[3]
[0] [1] [2] [3] [4] [5] [6]
list
2
5 9
Step 3: Move list[1] to list[2]
[0] [1] [2] [3] [4] [5] [6]
list
38
2
4
5 9
Step 4: Assign currentElement to list[1]
Source Code
void insertionsort(double list[], int arraysize){
for(int i=1; i<arraysize; i++){
double currentelement=list[i];
int k;
//locate and move
for(k=i-1; k>=0&&list[k]>currentelement; k--)
list[k+1]=list[k];
//insert
list[k+1]=currentelement;
}
}
39
§7.5 Character Array and C-string
• Initializing character array
– Character by character
char city[] = {'D', 'a', 'l', 'l', 'a', 's'};
– With a string
char city[] = "Dallas";
char
char city[6]
city[7] == "Dallas";
"Dallas";
40
Printing Character Array
• Printing character array
char city[] = "Dallas";
cout << city;
char city[]
city[] == {'D',
{'D', 'a',
'a', 'l',
'l', 'l',
'l', 'a',
'a', 's',
's'};'\0' };
char
cout <<
<< city;
city;
cout
41
Reading C-Strings
• Using “cin”: can’t read in white space
char city[10];
cin >>city;
• Using “getline” : can read any character.
– a function defined in iostream
cin.getline(char array[], int size, char delimitChar)
Where to store?
The last character is reserved for '\0'.
42
Where to stop?
delimitChar is read but not stored.
Default delimitChar is ‘\n’.
Function
Description
size_t strlen(const char s[])
Returns the length of the string, i.e., the number of the
characters before the null terminator.
strcpy(char s1[], const char s2[])
Copies string s2 to string s1.
strncpy(char s1[], const char s2[], size_t n)
C-String
Functions
Copies the first n characters from string s2 to string s1.
strcat(char s1[], const char s2[])
Appends string s2 to s1.
strncat(char s1[], const char s2[], size_t n)
Appends the first n characters from string s2 to s1.
int strcmp(char s1[], const char s2[])
Returns a value greater than 0, 0, or less than 0 if s1 is greater
than, equal to, or less than s2 based on the numeric code of the
characters.
int strncmp(char s1[], const char s2[], size_t n)
Same as strcmp, but compares up to n number of characters in s1
with those in s2.
int atoi(char s[])
Returns an int value for the string.
double atof(char s[])
Returns a double value for the string.
long atol(char s[])
Returns a long value for the string.
void itoa(int value, char s[], int radix)
Obtains an integer value to a string based on specified radix.
43
String Examples
CopyString
CombineString
CompareString
StringConversion
44
Summary
• Basic concept of array
• Basic usage of array
• Processing array
– Initializing, searching, sorting
• Character array and C-string
– Declaring, reading, printing
45
Homework Questions
Q1: What is the output?
int main ( ){
char ch[10];
cout<<sizeof(ch)<<endl;
char ch2[] = "This is true.";
for(int i =0; i<sizeof(ch2); i++)
cout<<ch2[i];
cout<<endl;
}
Q2: Using the selection sort, show the change of
the array {4, 5, 3, 23, 9, 7, 8} during sorting.
46