Chapter 4 - Arrays: 2003 Prentice Hall, Inc. All Rights Reserved

1

Chapter 4 - Arrays Outline 4.1 Introduction 4.2 Arrays 4.3 Declaring Arrays 4.4 Examples Using Arrays 4.5 Passing Arrays to Functions 4.6 Sorting Arrays 4.7 Case Study: Computing Mean, Median and Mode Using Arrays 4.8 Searching Arrays: Linear Search and Binary Search 4.9

Multiple-Subscripted Arrays

 2003 Prentice Hall, Inc. All rights reserved.

2

4.1 Giới thiệu • Mảng – Cấu trúc các mục dữ liệu liên quan – Tĩnh tại (cùng kích cỡ trong suốt chương trình)

• Một vài kiểu – Mảng con trỏ cơ sở (giống C) – Mảng đối tượng (C++)

 2003 Prentice Hall, Inc. All rights reserved.

3

4.2 Mảng • Mảng – Nhóm các vị trí nhớ liên tiếp – Cùng tên và kiểu (int, char, etc.)

• Xét một phần tử – Chỉ định tên mảng và vị trí số (chỉ mục) – Dạng thức: arrayname[ position number ] – Thành phần đầu tiên luôn là 0

• Mảng c có N phần tử c[ 0 ], c[ 1 ] … c[ n - 1 ]

– Phần tử thứ N là N-1

 2003 Prentice Hall, Inc. All rights reserved.

4

4.2 Mảng • Các phần tử của mảng giống các biến khác – Gán, in một mảng c nguyên c[ 0 ] = 3; cout << c[ 0 ];

• Có thể biểu diễn các toán tử bên trong dấu ngoặc vuông [] c[ 5 – 2 ] tương đương với c[3]

 2003 Prentice Hall, Inc. All rights reserved.

5

4.2 Arrays Tên của mảng (Lưu ý rằng tất cả các phần tử của mảng này có cùng tên, c)

c[0]

-45

c[1]

6

c[2]

0

c[3]

72

c[4]

1543

c[5]

-89

c[6]

0

c[7]

62

c[8]

-3

c[9]

1

c[10]

6453

c[11]

78

Vị trí số của phần tử bên trong mảng c

 2003 Prentice Hall, Inc. All rights reserved.

6

4.3 Khai báo mảng • Khi khai báo mảng, định rõ – Tên – Kiểu mảng • Bất cứ kiểu dữ liệu nào

– Số các phần tử – Kiểu Tên mảng[ Kích thước mảng ]; int c[ 10 ]; // mảng 10 số nguyên float d[ 3284 ]; // mảng 3284 số thực

• Khai báo nhiều mảng cùng kiểu – Dùng dấu phảy (,) ngăn cách, giống như các biến thông thường int b[ 100 ], x[ 27 ];

 2003 Prentice Hall, Inc. All rights reserved.

7

4.4 Các ví dụ sử dụng mảng • Khởi tạo mảng – Vòng lặp For • Thiết lập từng phần tử

– Danh sách khởi tạo • Chỉ rõ từng phần tử khi khai báo mảng int n[ 5 ] = { 1, 2, 3, 4, 5 }; • Nếu không đủ giá trị ban đầu, phần tử 0 bên phải cùng • Nếu quá nhiều lỗi cú pháp

– Cho các phần tử giá trị giống nhau int n[ 5 ] = { 0 };

– Nếu loại bỏ kích cỡ mảng, các giá trị phần tử ban đầu sẽ xác định kích thước int n[] = { 1, 2, 3, 4, 5 }; • 5 giá trị khởi tạo, vì vậy mảng có 5 phần tử  2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.3: fig04_03.cpp // Initializing an array. #include

Outline fig04_03.cpp (1 of 2)

using std::cout; using std::endl; #include using std::setw; int main() { int n[ 10 ];

Khai báo 1 mảng 10 phần tử nguyên khởi tạo // n is an array ofMảng 10 integers

bắt đầu từ 0 sử dụng vòng lặp for. Chú ý rằng nmảng to 0này chứa các phần tử từ n[0] tới n[9].

// initialize elements of array for ( int i = 0; i < 10; i++ ) n[ i ] = 0; // set element at location i to 0

cout << "Element" << setw( 13 ) << "Value" << endl; // output contents of array n in tabular format for ( int j = 0; j < 10; j++ ) cout << setw( 7 ) << j << setw( 13 ) << n[ j ] << endl;

 2003 Prentice Hall, Inc. All rights reserved.

8

26 27 28

return 0;

// indicates successful termination

Outline

} // end main

Element 0 1 2 3 4 5 6 7 8 9

Value 0 0 0 0 0 0 0 0 0 0

fig04_03.cpp (2 of 2) fig04_03.cpp output (1 of 1)

 2003 Prentice Hall, Inc. All rights reserved.

9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.4: fig04_04.cpp // Initializing an array with a declaration. #include using std::cout; using std::endl;

Outline fig04_04.cpp (1 of 1)

#include using std::setw;

Lưu ý cách dùng của danh int main() sách giá trị khởi tạo. { // use initializer list to initialize array n int n[ 10 ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; cout << "Element" << setw( 13 ) << "Value" << endl; // output contents of array n in tabular format for ( int i = 0; i < 10; i++ ) cout << setw( 7 ) << i << setw( 13 ) << n[ i ] << endl; return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

10

Element 0 1 2 3 4 5 6 7 8 9

Value 32 27 64 18 95 14 90 70 60 37

Outline fig04_04.cpp output (1 of 1)

 2003 Prentice Hall, Inc. All rights reserved.

11

12

4.4 Ví dụ sử dụng mảng • Kích cỡ mảng – Có thể được chỉ rõ bởi các hằng biến (const) • const int size = 20;

– Các hằng biến không thể thay đổi – Các hằng biến phải được gán giá trị ban đầu khi khai báo – Còn được gọi là hằng hay biến chỉ đọc

 2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// Fig. 4.5: fig04_05.cpp // Initialize array s to the even integers from 2 to 20. #include

Outline fig04_05.cpp (1 of 2)

using std::cout; using std::endl; #include using std::setw;

Lưu ý cách dùng của từ khoá

int main() const. Duy nhất các biến { const có thể chỉ ra kích // constant variable can be used to specify array size thước mảng. const int arraySize = 10; int s[ arraySize ];

// array s

for ( int i = 0; i < arraySize; s[ i ] = 2 + 2 * i; cout << "Element" << setw( 13 )

Chương trình linh hoạt hơn khi chúng ta thiết lập kích has 10 elements thước mảng dùng biến ta có thể thay i++ ) //const. set theChúng values đổi arraySize, mà tất cả các vòng lặp vẫn hoạt động << "Value" << khác, endl;chúng ta sẽ phải (mặt update (cập nhật) từng vòng lòng trong chương trình).

 2003 Prentice Hall, Inc. All rights reserved.

13

24 25 26 27 28 29 30

// output contents of array s in tabular format for ( int j = 0; j < arraySize; j++ ) cout << setw( 7 ) << j << setw( 13 ) << s[ j ] << endl; return 0;

// indicates successful termination

} // end main

Element 0 1 2 3 4 5 6 7 8 9

Value 2 4 6 8 10 12 14 16 18 20

Outline fig04_05.cpp (2 of 2) fig04_05.cpp output (1 of 1)

 2003 Prentice Hall, Inc. All rights reserved.

14

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

// Fig. 4.6: fig04_06.cpp // Using a properly initialized constant variable. #include using std::cout; using std::endl; int main() { const int x = 7;

Outline fig04_06.cpp (1 of 1)

Khởi tạo thích hợp của biến const.

fig04_06.cpp output (1 of 1)

// initialized constant variable

cout << "The value of constant variable x is: " << x << endl; return 0;

// indicates successful termination

} // end main

The value of constant variable x is: 7

 2003 Prentice Hall, Inc. All rights reserved.

15

1 2 3 4 5 6 7 8 9 10 11 12

// Fig. 4.7: fig04_07.cpp // A const object must be initialized. int main() { const int x;

// Error: x

Const không được khởi tạo gây lỗi cú pháp. Nỗ lực sửa đổi const tạo ra một lỗi must khác.be initialized

x = 7;

// Error: cannot modify a const variable

return 0;

// indicates successful termination

Outline fig04_07.cpp (1 of 1) fig04_07.cpp output (1 of 1)

} // end main

d:\cpphtp4_examples\ch04\Fig04_07.cpp(6) : error C2734: 'x' : const object must be initialized if not extern d:\cpphtp4_examples\ch04\Fig04_07.cpp(8) : error C2166: l-value specifies const object

 2003 Prentice Hall, Inc. All rights reserved.

16

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// Fig. 4.8: fig04_08.cpp // Compute the sum of the elements of the array. #include using std::cout; using std::endl; int main() { const int arraySize = 10;

Outline fig04_08.cpp (1 of 1) fig04_08.cpp output (1 of 1)

int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int total = 0; // sum contents of array a for ( int i = 0; i < arraySize; i++ ) total += a[ i ]; cout << "Total of array element values is " << total << endl; return 0;

// indicates successful termination

} // end main

Total of array element values is 55

 2003 Prentice Hall, Inc. All rights reserved.

17

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

// Fig. 4.9: fig04_09.cpp // Histogram printing program. #include

Outline fig04_09.cpp (1 of 2)

using std::cout; using std::endl; #include using std::setw; int main() { const int arraySize = 10; int n[ arraySize ] = { 19, 3, 15, 7, 11, 9, 13, 5, 17, 1 }; cout << "Element" << setw( 13 ) << "Value" << setw( 17 ) << "Histogram" << endl;

// for each element of array n, output a bar in histogram for ( int i = 0; i < arraySize; i++ ) { In các dấu sao * tương ứng cout << setw( 7 ) << i << setw( 13 ) với kích cỡ của phần tử mảng, << n[ i ] << setw( 9 );

n[i].

for ( int j = 0; j < n[ i ]; j++ ) cout << '*';

// print one bar

 2003 Prentice Hall, Inc. All rights reserved.

18

27 28 29 30 31 32 33 34

cout << endl;

// start next line of output

} // end outer for structure return 0;

// indicates successful termination

Value 19 3 15 7 11 9 13 5 17 1

fig04_09.cpp (2 of 2) fig04_09.cpp output (1 of 1)

} // end main

Element 0 1 2 3 4 5 6 7 8 9

Outline

Histogram ******************* *** *************** ******* *********** ********* ************* ***** ***************** *

 2003 Prentice Hall, Inc. All rights reserved.

19

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.10: fig04_10.cpp // Roll a six-sided die 6000 times. #include

Outline fig04_10.cpp (1 of 2)

using std::cout; using std::endl; #include using std::setw; #include #include int main() { const int arraySize = 7; int frequency[ arraySize ] = { 0 }; srand( time( 0 ) );

// seed random-number

Tái tạo một chương trình cũ – đổ xúc. Một mảng đuowcj dùng thay vì 6 biến thông thường, và phần tử tương ứng có thể được update dễ dàng generator (mà không cần 1 switch).

// roll die 6000 times Lệnh này tạo ra một số trong for ( int roll = 1; roll <= 6000; roll++ ) khoảng từ 1 tới 6, xác định chỉ ++frequency[ 1 + rand() % 6 ]; // replaces 20-line switch mục của frequency[] sẽ // of Fig. 3.8

tăng giá trị thêm 1.

 2003 Prentice Hall, Inc. All rights reserved.

20

26 27 28 29 30 31 32 33 34 35 36 Face 1 2 3 4 5 6

cout << "Face" << setw( 13 ) << "Frequency" << endl; // output frequency elements 1-6 in tabular format for ( int face = 1; face < arraySize; face++ ) cout << setw( 4 ) << face << setw( 13 ) << frequency[ face ] << endl; return 0;

// indicates successful termination

Outline fig04_10.cpp (2 of 2) fig04_10.cpp output (1 of 1)

} // end main Frequency 1003 1004 999 980 1013 1001

 2003 Prentice Hall, Inc. All rights reserved.

21

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.11: fig04_11.cpp // Student poll program. #include

Outline fig04_11.cpp (1 of 2)

using std::cout; using std::endl; #include using std::setw; int main() { // define array sizes const int responseSize = 40; const int frequencySize = 11;

// size of array responses // size of array frequency

// place survey responses in array responses int responses[ responseSize ] = { 1, 2, 6, 4, 8, 5, 9, 7, 8, 10, 1, 6, 3, 8, 6, 10, 3, 8, 2, 7, 6, 5, 7, 6, 8, 6, 7, 5, 6, 6, 5, 6, 7, 5, 6, 4, 8, 6, 8, 10 }; // initialize frequency counters to 0 int frequency[ frequencySize ] = { 0 };

 2003 Prentice Hall, Inc. All rights reserved.

22

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

// for each answer, select value of an element of array // responses and use that value as subscript in array // frequency to determine element to increment for ( int answer = 0; answer < responseSize; answer++ ) ++frequency[ responses[answer] ];

responses[answer] là Nó xác định chỉ mục trong frequency[] để tăng thêm in tabular format 1. rating < frequencySize; rating++ )

Outline fig04_11.cpp (2 of 2)

// display results sự xếp loại (từ 1 tới 10). cout << "Rating" << setw( 17 ) << "Frequency" << endl; // output frequencies for ( int rating = 1; cout << setw( 6 ) << rating << setw( 17 ) << frequency[ rating ] << endl; return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

23

Rating 1 2 3 4 5 6 7 8 9 10

Frequency 2 2 2 2 5 11 5 7 1 3

Outline fig04_11.cpp output (1 of 1)

 2003 Prentice Hall, Inc. All rights reserved.

24

25

4.4 Ví dụ sử dụng mảng • Các chuỗi (nói rõ hơn ở chapter 5) – Mảng ký tự – Mọi chuỗi đều kết thúc bằng null ('\0') – Ví dụ • char string1[] = "hello"; – Ký tự Null tự động được thêm vào – string1 có 6 phần tử

• char string1[] = { 'h', 'e', 'l', 'l', 'o', '\0’ };

– Ký hiệu tương tự String1[ 0 ] is 'h' string1[ 2 ] is 'l'

 2003 Prentice Hall, Inc. All rights reserved.

26

4.4

Ví dụ sử dụng mảng

• Nhập từ bàn phím char string2[ 10 ]; cin >> string2;

– Đưa dữ liệu nhập của người dùng vào chuỗi • Dừng ở ký tự whitespace đầu tiên • Thêm ký tự null

– If too much text entered, data written beyond array • We want to avoid this (section 5.12 explains how)

• In chuỗi ra màn hình – cout << string2 << endl; • Không dùng cho các kiểu mảng khác

– Các ký tự in ra cho tới khi gặp ký tự null  2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// Fig. 4_12: fig04_12.cpp // Treating character arrays as strings. #include using std::cout; using std::cin; using std::endl;

Outline fig04_12.cpp (1 of 2)

Hai cách khai báo chuỗi. string2 được khởi tạo, và kích cỡ của nó được xác định //tựreserves động . 20 characters

int main() { char string1[ 20 ], char string2[] = "string literal"; // reserves 15 characters

Ví dụ về đọc mảng từ bàn phímstring2 và in chúng ra màn hình. array

// read string from user into cout << "Enter the string \"hello there\": "; cin >> string1; // reads "hello" [space terminates input] // output strings cout << "string1 is: " << string1 << "\nstring2 is: " << string2; cout << "\nstring1 with spaces between characters is:\n";

 2003 Prentice Hall, Inc. All rights reserved.

27

24 25 26 27 28 29 30 31 32 33

// output characters until null character is reached for ( int i = 0; string1[ i ] != '\0'; i++ ) cout << string1[ i ] << ' ';

Outline

Có thể truy xuất các ký tự fig04_12.cpp chuỗi sử dụng chú thích (2 of 2) mảng. Vòng lặp kết thúc khi gặp ký tự null. fig04_12.cpp termination output (1 of 1)

cin >> string1; // reads "there" trong cout << "\nstring1 is: " << string1 << endl; return 0;

// indicates successful

} // end main

Enter the string "hello there": hello there string1 is: hello string2 is: string literal string1 with spaces between characters is: h e l l o string1 is: there

 2003 Prentice Hall, Inc. All rights reserved.

28

29

4.4

Ví dụ sử dụng mảng

• Gọi lại kho lưu trữ static (tĩnh) (chapter 3) – Nếu static, các biến cục bộ lưu lại các giá trị giữa các lệnh gọi hàm – Chỉ hiển thị ở thân hàm – Có thể khai báo các mảng cục bộ là static • Khởi tạo giá trị 0 static int array[3];

• Nếu ko static – Tạo (và huỷ) trong mỗi lệnh gọi hàm

 2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.13: fig04_13.cpp // Static arrays are initialized to zero. #include

fig04_13.cpp (1 of 3)

using std::cout; using std::endl; void staticArrayInit( void ); void automaticArrayInit( void );

Outline

// function prototype // function prototype

int main() { cout << "First call to each function:\n"; staticArrayInit(); automaticArrayInit(); cout << "\n\nSecond call to each function:\n"; staticArrayInit(); automaticArrayInit(); cout << endl; return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

30

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

// function to demonstrate a static local array Mảng Static, khởi tạo giá trị 0 void staticArrayInit( void ) trong lần gọi hàm thứ nhất. { // initializes elements to 0 first time function is called static int array1[ 3 ];

Outline fig04_13.cpp (2 of 3)

cout << "\nValues on entering staticArrayInit:\n"; // output contents of array1 for ( int i = 0; i < 3; i++ ) cout << "array1[" << i << "] = " << array1[ i ] << "

";

Dữ liệu mảng bị thay đổi; giá trị mới lưu lại.

cout << "\nValues on exiting staticArrayInit:\n"; // modify and output for ( int j = 0; j < cout << "array1[" << ( array1[

contents of array1 3; j++ ) << j << "] = " j ] += 5 ) << " ";

} // end function staticArrayInit

 2003 Prentice Hall, Inc. All rights reserved.

31

47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

// function to demonstrate an automatic local array void automaticArrayInit( void ) Mảng tự động, { lần gọi hàm. // initializes elements each time function is called int array2[ 3 ] = { 1, 2, 3 };

tái tạo với mỗi

Outline

fig04_13.cpp (3 of 3)

cout << "\n\nValues on entering automaticArrayInit:\n"; // output contents of array2 for ( int i = 0; i < 3; i++ ) cout << "array2[" << i << "] = " << array2[ i ] << "

";

Dù mảng thay đổi, nó sẽ bị huỷ khi hàm kết thúc và mọi thay đổi mất.

cout << "\nValues on exiting automaticArrayInit:\n"; // modify and output for ( int j = 0; j < cout << "array2[" << ( array2[

contents of array2 3; j++ ) << j << "] = " j ] += 5 ) << " ";

} // end function automaticArrayInit

 2003 Prentice Hall, Inc. All rights reserved.

32

First call to each function: Values on array1[0] Values on array1[0]

entering staticArrayInit: = 0 array1[1] = 0 array1[2] = 0 exiting staticArrayInit: = 5 array1[1] = 5 array1[2] = 5

Values on array2[0] Values on array2[0]

entering automaticArrayInit: = 1 array2[1] = 2 array2[2] = 3 exiting automaticArrayInit: = 6 array2[1] = 7 array2[2] = 8

Outline fig04_13.cpp output (1 of 1)

Second call to each function: Values on array1[0] Values on array1[0]

entering staticArrayInit: = 5 array1[1] = 5 array1[2] = 5 exiting staticArrayInit: = 10 array1[1] = 10 array1[2] = 10

Values on array2[0] Values on array2[0]

entering automaticArrayInit: = 1 array2[1] = 2 array2[2] = 3 exiting automaticArrayInit: = 6 array2[1] = 7 array2[2] = 8

 2003 Prentice Hall, Inc. All rights reserved.

33

34

4.5 Đưa mảng vào hàm • Chỉ định tên mà không dùng ngoặc – Đưa mảng myArray tới myFunction int myArray[ 24 ]; myFunction( myArray, 24 );

– Kích thước mảng thường được đưa vào, nhưng không cần thiết • Hữu ích khi lặp lại các phần tử

 2003 Prentice Hall, Inc. All rights reserved.

35

4.5

Đưa mảng vào hàm

• Chuyển mảng theo tham chiếu – Các hàm có thể sửa đổi dữ liệu mảng gốc – Gía trị của tên mảng là điạ chỉ của phần tử đầu tiên • Hàm nhận biết mảng được lưu trữ ở đâu • Có thể thay đổi vị trí nhớ gốc

• Các phần tử mảng cá thể được chuyển theo giá trị – Giống các biến thông thường – square( myArray[3] );

 2003 Prentice Hall, Inc. All rights reserved.

36

4.5

Đưa mảng vào hàm

• Hàm nhận mảng – Hàm nguyên mẫu • void modifyArray( int b[], int arraySize ); • void modifyArray( int [], int ); – Gọi tên không cần thiết trong nguyên mẫu • Nhận cả mảng ngiuên và số nguyên đơn

– Không cần kích cỡ mảng giữa các ngoặc • Được bỏ qua bởi trình biên dịch

– Nếu khai báo tham số mảng như const • Không thể sửa đổi (lỗi trình biên dịch) • void doNotModify( const int [] );

 2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.14: fig04_14.cpp // Passing arrays and individual array elements to functions. #include

fig04_14.cpp (1 of 3)

using std::cout; using std::endl; #include using std::setw; void modifyArray( int [], int ); void modifyElement( int );

Outline

Cú pháp cho việc chấp nhận một mảng trong danh sách tham số. // appears strange

int main() { const int arraySize = 5; int a[ arraySize ] = { 0, 1, 2, 3, 4 };

// size of array a // initialize a

cout << "Effects of passing entire array by reference:" << "\n\nThe values of the original array are:\n"; // output original array for ( int i = 0; i < arraySize; i++ ) cout << setw( 3 ) << a[ i ];

 2003 Prentice Hall, Inc. All rights reserved.

37

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

Đưa tên mảng (a) và kích cỡ vào hàm. Các hàm được đưa vàoreference theo tham chiếu by

cout << endl; // pass array a to modifyArray modifyArray( a, arraySize );

Outline fig04_14.cpp (2 of 3)

cout << "The values of the modified array are:\n"; // output modified array for ( int j = 0; j < arraySize; j++ ) cout << setw( 3 ) << a[ j ]; // output value of a[ 3 ] cout << "\n\n\n" << "Effects of passing array element by value:" Đưa một mảng đơn phần << "\n\nThe value of a[3] is " << a[ 3 ] << '\n'; // pass array element a[ 3 ] by modifyElement( a[ 3 ] );

tử vào hàm theo giá trị; nguyên gốc không thể thay đổi được. value

// output value of a[ 3 ] cout << "The value of a[3] is " << a[ 3 ] << endl; return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

38

52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

// in function modifyArray, "b" points to // the original array "a" in memory void modifyArray( int b[], int sizeOfArray ) { // multiply each array element by 2 for ( int k = 0; k < sizeOfArray; k++ ) b[ k ] *= 2;

Dù được đặt tên b, mảng này Outline vẫn chỉ tới mảng gốc a. Nó có thể sửa đổi dữ liệu của a. fig04_14.cpp (3 of 3)

} // end function modifyArray

Các phần tử cá thể của mảng đượccopy đưa of vào hàm theo giá trị, in function modifyElement, "e" is a local array element a[ 3 ] passed from main và không thể thay đổi gốc.

// // void modifyElement( int e ) { // multiply parameter by 2 cout << "Value in modifyElement is " << ( e *= 2 ) << endl; } // end function modifyElement

 2003 Prentice Hall, Inc. All rights reserved.

39

Effects of passing entire array by reference: The values of 0 1 2 3 The values of 0 2 4 6

the original array are: 4 the modified array are: 8

Outline fig04_14.cpp output (1 of 1)

Effects of passing array element by value: The value of a[3] is 6 Value in modifyElement is 12 The value of a[3] is 6

 2003 Prentice Hall, Inc. All rights reserved.

40

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// Fig. 4.15: fig04_15.cpp // Demonstrating the const type qualifier. #include using std::cout; using std::endl; void tryToModifyArray( const int [] );

//

Outline Tham số mảng được khai báo là const. Mảng không thể sửa đổi, ngay cả khi nó được đưa vào theo tham chiếu. function prototype

fig04_15.cpp (1 of 2)

int main() { int a[] = { 10, 20, 30 }; tryToModifyArray( a ); cout << a[ 0 ] << ' ' << a[ 1 ] << ' ' << a[ 2 ] << '\n'; return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

41

22 23 24 25 26 27 28 29 30

// In function tryToModifyArray, "b" cannot be used // to modify the original array "a" in main. void tryToModifyArray( const int b[] ) { b[ 0 ] /= 2; // error b[ 1 ] /= 2; // error b[ 2 ] /= 2; // error } // end function tryToModifyArray

Outline fig04_15.cpp (2 of 2) fig04_15.cpp output (1 of 1)

d:\cpphtp4_examples\ch04\Fig04_15.cpp(26) : error C2166: l-value specifies const object d:\cpphtp4_examples\ch04\Fig04_15.cpp(27) : error C2166: l-value specifies const object d:\cpphtp4_examples\ch04\Fig04_15.cpp(28) : error C2166: l-value specifies const object

 2003 Prentice Hall, Inc. All rights reserved.

42

43

4.6 Sắp xếp mảng • Sắp xếp dữ liệu – Ứng dụng điện toán quan trọng – Mọi tổ chức hầu như phải sắp xếp một vài dữ liệu • Những lượng lớn phải được sắp xếp, phân loại

• Loại Bubble (loại bọt hay loại chìm ) – Một vài pass xuyên suốt mảng – Các cặp phần tử liên tục được so sánh • Nếu tăng trình tự (hay đồng nhất), không thay đổi • Nếu giảm trình tự, các phần tử thay đổi

– Lặp lại những bước này cho các phần tử

 2003 Prentice Hall, Inc. All rights reserved.

44

4.6

Sắp xếp mảng

• Ví dụ: – Đi từ trái sang phải, và trao đổi các phần tử cần thiết • Mỗi pass mỗi phần tử

– – – – – – –

Ban đầu: 3 4 2 7 6 Pass 1: 3 2 4 6 7 (Các phần tử trao đổi) Pass 2: 2 3 4 6 7 Pass 3: 2 3 4 6 7 (không cần thay đổi) Pass 4: 2 3 4 6 7 Pass 5: 2 3 4 6 7 Các phần tử nhỏ "bubble" đưa lên đầu (như 2 trong ví dụ này)

 2003 Prentice Hall, Inc. All rights reserved.

45

4.6

Sắp xếp mảng

• Trao đổi biến int x = 3, y = 4; y = x; x = y;

• Điều gì đã xảy ra? – Cà x và y đều bằng 3! – Cần một biến tạm

• Giải pháp int x = 3, temp = x; x = y; y = temp;

y = 4, temp = 0; // temp gets 3 // x gets 4 // y gets 3

 2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// Fig. 4.16: fig04_16.cpp // This program sorts an array's values into ascending order. #include using std::cout; using std::endl;

Outline fig04_16.cpp (1 of 3)

#include using std::setw; int main() { const int arraySize = 10; // size of array a int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; int hold; // temporary location used to swap array elements cout << "Data items in original order\n"; // output original array for ( int i = 0; i < arraySize; i++ ) cout << setw( 4 ) << a[ i ];

 2003 Prentice Hall, Inc. All rights reserved.

46

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

// bubble sort // loop to control number of passes for ( int pass = 0; pass < arraySize - 1; pass++ ) // loop to control number of comparisons per pass for ( int j = 0; j < arraySize - 1; j++ )

Thực hiện 1 pass cho mỗi Outline phần tử trong mảng. fig04_16.cpp (2 of 3)

// compare side-by-side elements and swap them Nếu if phần tử ở bên trái (chỉ // first element is greater than second element mục j) lớn hơn phần tử ở bên if ( a[ j ] > a[ j + 1 ] ) { phải (chỉ mục j + 1), thì ta hold = a[ j ]; sẽ tráo đổi chúng. Đừng quên a[ j ] = a[ j + 1 ]; sự cần thiết của 1 biến tạm. a[ j + 1 ] = hold; } // end if

 2003 Prentice Hall, Inc. All rights reserved.

47

40 41 42 43 44 45 46 47 48 49 50

cout << "\nData items in ascending order\n"; // output sorted array for ( int k = 0; k < arraySize; k++ ) cout << setw( 4 ) << a[ k ]; cout << endl; return 0;

// indicates successful termination

Outline fig04_16.cpp (3 of 3) fig04_16.cpp output (1 of 1)

} // end main

Data items in original order 2 6 4 8 10 12 89 68 Data items in ascending order 2 4 6 8 10 12 37 45

45

37

68

89

 2003 Prentice Hall, Inc. All rights reserved.

48

4.7 Case Study: Số trung bình, Số chính giữa, và Số mẫu Điện toán sử dụng • Gía trị trung bình – Trung bình (tổng/số phần tử)

• Số chính giữa – Số ở chính giữa danh sách đã được sắp xếp – 1, 2, 3, 4, 5 (3 là số chính giữa) – Nếu một số chắn các phần tử, lấy số trung bình của 2 số ở chính giữa

• Số mẫu – Số xuất hiện nhiều nhất – 1, 1, 1, 2, 3, 3, 4, 5 (1 là số mẫu)

 2003 Prentice Hall, Inc. All rights reserved.

49

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.17: fig04_17.cpp // This program introduces the topic of survey data analysis. // It computes the mean, median, and mode of the data. #include using using using using

std::cout; std::endl; std::fixed; std::showpoint;

Outline fig04_17.cpp (1 of 8)

#include using std::setw; using std::setprecision; void void void void void

mean( const int [], int ); median( int [], int ); mode( int [], int [], int ); bubbleSort( int[], int ); printArray( const int[], int );

int main() { const int responseSize = 99;

// size of array responses

 2003 Prentice Hall, Inc. All rights reserved.

50

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

int frequency[ 10 ] = { 0 };

// initialize array frequency

// initialize array responses int response[ responseSize ] = { 6, 7, 8, 9, 8, 7, 8, 9, 7, 8, 9, 5, 9, 8, 7, 8, 6, 7, 8, 9, 3, 9, 8, 7, 7, 8, 9, 8, 9, 8, 9, 7, 6, 7, 8, 7, 8, 7, 9, 8, 7, 8, 9, 8, 9, 8, 9, 7, 5, 6, 7, 2, 5, 3, 9, 4, 7, 8, 9, 6, 8, 7, 8, 9, 7, 4, 4, 2, 5, 3, 8, 7, 4, 5, 6, 1, 6, 5, 7, 8,

8, 9, 7, 8, 8, 7, 8, 9, 9, 2, 5, 3, 6, 4, 7, 8, 5, 6, 7 };

Outline fig04_17.cpp (2 of 8)

// process responses mean( response, responseSize ); median( response, responseSize ); mode( frequency, response, responseSize ); return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

51

50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

// calculate average of all response values void mean( const int answer[], int arraySize ) { int total = 0; cout << "********\n

Mean\n********\n";

Outline fig04_17.cpp (3 of 8)

// total response values for ( int i = 0; i < arraySize; i++ ) total += answer[ i ]; // format and output results cout << fixed << setprecision( 4 ); cout << << << << << << << <<

"The mean is the average value of the data\n" "items. The mean is equal to the total of\n" "all the data items divided by the number\n" Chúng ta bố trí một double để "of data items (" << arraySize "). The mean value for\nthis run is: " nhận các giá trị thập phân cho số trung bình (thay vì một số total << " / " << arraySize << " = " nguyên). static_cast< double >( total ) / arraySize "\n\n";

} // end function mean

 2003 Prentice Hall, Inc. All rights reserved.

52

75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

// sort array and determine median element's value void median( int answer[], int size ) { cout << "\n********\n Median\n********\n" << "The unsorted array of responses is"; printArray( answer, size ); bubbleSort( answer, size );

Sắp xếp dãy bằng cách đưa nó vào một hàm. Hàm này giữa // output unsorted array chương trình theo một // module. sort array

Outline fig04_17.cpp (4 of 8)

cout << "\n\nThe sorted array is"; printArray( answer, size ); // output sorted array // display median element cout << "\n\nThe median is element " << size / 2 << " of\nthe sorted " << size << " element array.\nFor this run the median is " << answer[ size / 2 ] << "\n\n"; } // end function median

 2003 Prentice Hall, Inc. All rights reserved.

53

96 // determine most frequent response 97 void mode( int freq[], int answer[], int size ) 98 { 99 int largest = 0; // represents largest frequency 100 int modeValue = 0; // represents most frequent response 101 102 cout << "\n********\n Mode\n********\n"; 103 104 // initialize frequencies to 0 105 for ( int i = 1; i <= 9; i++ ) 106 freq[ i ] = 0; 107 108 // summarize frequencies 109 for ( int j = 0; j < size; j++ ) 110 ++freq[ answer[ j ] ]; 111 112 // output headers for result columns 113 cout << "Response" << setw( 11 ) << "Frequency" 114 << setw( 19 ) << "Histogram\n\n" << setw( 55 ) 115 << "1 1 2 2\n" << setw( 56 ) 116 << "5 0 5 0 5\n\n"; 117

Outline fig04_17.cpp (5 of 8)

 2003 Prentice Hall, Inc. All rights reserved.

54

118 // output results 119 for ( int rating = 1; rating <= 9; rating++ ) { 120 cout << setw( 8 ) << rating << setw( 11 ) Số mẫu 121 << freq[ rating ] << " "; là giá trị xuất hiện nhiều nhất (có giá trị lớn nhất 122 freq). 123 // keep track of mode value and trong largest fequency value 124 if ( freq[ rating ] > largest ) { 125 largest = freq[ rating ]; 126 modeValue = rating; 127 128 } // end if 129 130 // output histogram bar representing frequency value 131 for ( int k = 1; k <= freq[ rating ]; k++ ) 132 cout << '*'; 133 134 cout << '\n'; // begin new line of output 135 136 } // end outer for 137 138 // display the mode value 139 cout << "The mode is the most frequent value.\n" 140 << "For this run the mode is " << modeValue 141 << " which occurred " << largest << " times." << endl; 142 143 } // end function mode

Outline fig04_17.cpp (6 of 8)

 2003 Prentice Hall, Inc. All rights reserved.

55

144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165

// function that sorts an array with bubble sort algorithm void bubbleSort( int a[], int size ) { int hold; // temporary location used to swap elements

Outline fig04_17.cpp (7 of 8)

// loop to control number of passes for ( int pass = 1; pass < size; pass++ ) // loop to control number of comparisons per pass for ( int j = 0; j < size - 1; j++ ) // swap elements if out of order if ( a[ j ] > a[ j + 1 ] ) { hold = a[ j ]; a[ j ] = a[ j + 1 ]; a[ j + 1 ] = hold; } // end if } // end function bubbleSort

 2003 Prentice Hall, Inc. All rights reserved.

56

166 167 168 169 170 171 172 173 174 175 176 177 178

// output array contents (20 values per row) void printArray( const int a[], int size ) { for ( int i = 0; i < size; i++ ) { if ( i % 20 == 0 ) cout << endl;

// begin new line every 20 values

Outline fig04_17.cpp (8 of 8)

cout << setw( 2 ) << a[ i ]; } // end for } // end function printArray

 2003 Prentice Hall, Inc. All rights reserved.

57

******** Mean ******** The mean is the average value of the data items. The mean is equal to the total of all the data items divided by the number of data items (99). The mean value for this run is: 681 / 99 = 6.8788 ******** Median ******** The unsorted array of responses is 6 7 8 9 8 7 8 9 8 9 7 8 9 5 9 8 7 8 7 8 6 7 8 9 3 9 8 7 8 7 7 8 9 8 9 8 9 7 8 9 6 7 8 7 8 7 9 8 9 2 7 8 9 8 9 8 9 7 5 3 5 6 7 2 5 3 9 4 6 4 7 8 9 6 8 7 8 9 7 8 7 4 4 2 5 3 8 7 5 6 4 5 6 1 6 5 7 8 7 The sorted 1 2 2 2 3 5 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9

array 3 3 3 6 6 6 7 7 7 8 8 8 9 9 9

is 4 4 6 6 7 7 8 8 9 9

4 7 7 8 9

4 7 7 8 9

4 7 7 8 9

5 7 8 8 9

5 7 8 8 9

5 7 8 8 9

5 7 8 8 9

5 7 8 8 9

5 7 8 8 9

Outline fig04_17.cpp output (1 of 2)

5 7 8 8

The median is element 49 of the sorted 99 element array. For this run the median is 7

 2003 Prentice Hall, Inc. All rights reserved.

58

******** Mode ******** Response

Outline Frequency

Histogram

5

1 0

1 5

2 0

2 5

fig04_17.cpp output (2 of 2)

1 1 * 2 3 *** 3 4 **** 4 5 ***** 5 8 ******** 6 9 ********* 7 23 *********************** 8 27 *************************** 9 19 ******************* The mode is the most frequent value. For this run the mode is 8 which occurred 27 times.

 2003 Prentice Hall, Inc. All rights reserved.

59

4.8 Tìm kiếm mảng: Tìm tuyến tính và Tìm nhị phân • Tìm trong mảng 1 giá trị khoá • Tìm kiếm tuyến tính – So sánh mỗi phần tử của mảng với một giá trị khoá • Bắt đầu ở một đầu mút, đi tới các đầu mút khác

– Hữu ích cho các mảng nhỏ và chưa được sắp xếp • Thiếu hiệu quả • Nếu khoá tìm kiếm không hiện hữu, kiểm tra từng phần tử

 2003 Prentice Hall, Inc. All rights reserved.

60

4.8

Tìm kiếm mảng: Tìm tuyến tính và Tìm nhị phân

• Tìm kiếm nhị phân – Chỉ áp dụng cho các mảng đã được sắp xếp – So sánh phần tử giữa với khoá • Nếu tìm, tìm ra • Nếu khoá < giữa – Lặp lại tìm kiếm ở nửa đầu của mảng • Nếu khoá > giữa – Lặp lại tìm kiếm ở nửa sau

– Rất nhanh

• Nhiều nhất N bưóc, tại đóN2 > # các phần tử • Mảng 30 phần tử mất nhiều nhất 5 bước 5 2 > 30

 2003 Prentice Hall, Inc. All rights reserved.

61

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Fig. 4.19: fig04_19.cpp // Linear search of an array. #include using std::cout; using std::cin; using std::endl;

Outline Nhận mảng, khoá tìm kiếm, và kích cỡ mảng.

int linearSearch( const int [], int, int ); int main() { const int arraySize = 100; int a[ arraySize ]; int searchKey;

fig04_19.cpp (1 of 2)

// prototype

// size of array a // create array a // value to locate in a

for ( int i = 0; i < arraySize; i++ ) a[ i ] = 2 * i;

// create some data

cout << "Enter integer search key: "; cin >> searchKey; // attempt to locate searchKey in array a int element = linearSearch( a, searchKey, arraySize );

 2003 Prentice Hall, Inc. All rights reserved.

62

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

// display results if ( element != -1 ) cout << "Found value in element " << element << endl; else cout << "Value not found" << endl; return 0;

Outline fig04_19.cpp (2 of 2)

// indicates successful termination

} // end main // compare key to every element of array until location is // found or until end of array is reached; return subscript of // element if key or -1 if key not found int linearSearch( const int array[], int key, int sizeOfArray ) { for ( int j = 0; j < sizeOfArray; j++ ) if ( array[ j ] == key ) return j; return -1;

// if found, // return location of key

// key not found

} // end function linearSearch

 2003 Prentice Hall, Inc. All rights reserved.

63

Enter integer search key: 36 Found value in element 18 Enter integer search key: 37 Value not found

Outline fig04_19.cpp output (1 of 1)

 2003 Prentice Hall, Inc. All rights reserved.

64

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

// Fig. 4.20: fig04_20.cpp // Binary search of an array. #include

Outline fig04_20.cpp (1 of 6)

using std::cout; using std::cin; using std::endl; #include using std::setw; // function prototypes int binarySearch( const int [], int, int, int, int ); void printHeader( int ); void printRow( const int [], int, int, int, int ); int main() { const int arraySize = 15; int a[ arraySize ]; int key;

// size of array a // create array a // value to locate in a

for ( int i = 0; i < arraySize; i++ ) a[ i ] = 2 * i;

// create some data

 2003 Prentice Hall, Inc. All rights reserved.

65

27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

cout << "Enter a number between 0 and 28: "; cin >> key; printHeader( arraySize ); // search for key in array a int result = binarySearch( a, key, 0, arraySize - 1, arraySize );

Outline fig04_20.cpp (2 of 6)

// display results if ( result != -1 ) cout << '\n' << key << " found in array element " << result << endl; else cout << '\n' << key << " not found" << endl; return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

66

47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

// function to perform binary search of an array int binarySearch( const int b[], int searchKey, int low, int high, int size ) { int middle;

Outline fig04_20.cpp (3 of 6)

// loop until low subscript is greater than high subscript Xác định phần tử chính giữa while ( low <= high ) { // determine middle element of subarray being searched middle = ( low + high ) / 2; // display subarray used in this loop iteration printRow( b, low, middle, high, size );

 2003 Prentice Hall, Inc. All rights reserved.

67

62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

// if searchKey matches middle element, return middle if ( searchKey == b[ middle ] ) // match return middle;

Sử dụng quy tắc tìm kiếm nhị phân : Nếu key bằng middle, tìm được element,

else

// if searchKey less than middle // set new high element Nếu nhỏ hơn, tìm if ( searchKey < b[ middle ] ) high = middle - 1; // search low hạnend dướiof array

Outline fig04_20.cpp (4 of 6)

kiếm giới

Vòng lặp thiết lậo low,

// if searchKey greater than middle element, Nếu lớn và hơn, tìmlinh kiếm giớiNếu middle, high hoạt. // set new low element hạn trên giới hạn trên, thì low tìm kiếm else mới là phần tử phía trên low = middle + 1; // search high end of array

middle.

} return -1;

// searchKey not found

} // end function binarySearch

 2003 Prentice Hall, Inc. All rights reserved.

68

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

// print header for output void printHeader( int size ) { cout << "\nSubscripts:\n";

Outline fig04_20.cpp (5 of 6)

// output column heads for ( int j = 0; j < size; j++ ) cout << setw( 3 ) << j << ' '; cout << '\n';

// start new line of output

// output line of - characters for ( int k = 1; k <= 4 * size; k++ ) cout << '-'; cout << endl;

// start new line of output

} // end function printHeader

 2003 Prentice Hall, Inc. All rights reserved.

69

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126

// print one row of output showing the current // part of the array being processed void printRow( const int b[], int low, int mid, int high, int size ) { // loop through entire array for ( int m = 0; m < size; m++ )

Outline fig04_20.cpp (6 of 6)

// display spaces if outside current subarray range if ( m < low || m > high ) cout << " "; // display middle element marked with a * else if ( m == mid ) // mark middle value cout << setw( 3 ) << b[ m ] << '*'; // display other elements in subarray else cout << setw( 3 ) << b[ m ] << ' '; cout << endl;

// start new line of output

} // end function printRow

 2003 Prentice Hall, Inc. All rights reserved.

70

Enter a number between 0 and 28: 6 Subscripts: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 -----------------------------------------------------------0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 0 2 4 6* 8 10 12

Outline fig04_20.cpp output (1 of 2)

6 found in array element 3     Enter a number between 0 and 28: 25 Subscripts: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 -----------------------------------------------------------0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 16 18 20 22* 24 26 28 24 26* 28 24* 25 not found

 2003 Prentice Hall, Inc. All rights reserved.

71

Enter a number between 0 and 28: 8 Subscripts: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 -----------------------------------------------------------0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 0 2 4 6* 8 10 12 8 10* 12 8*

Outline fig04_20.cpp output (2 of 2)

8 found in array element 4

 2003 Prentice Hall, Inc. All rights reserved.

72

73

4.9 Mảng nhiều biến • Nhiều subscript – a[ i ][ j ] – Các bảng biểu với hàng và cột – Định rõ hàng, rồi tới cột – “Mảng của các mảng” • a[0] là một mảng 4 phần tử • a[0][0] là phần tử đầu tiên của mảng đó Hàng 0

Column 0 a[ 0 ][ 0 ]

Column 1 a[ 0 ][ 1 ]

Column 2 a[ 0 ][ 2 ]

Column 3 a[ 0 ][ 3 ]

Hàng 1

a[ 1 ][ 0 ]

a[ 1 ][ 1 ]

a[ 1 ][ 2 ]

a[ 1 ][ 3 ]

Hàng 2

a[ 2 ][ 0 ]

a[ 2 ][ 1 ]

a[ 2 ][ 2 ]

a[ 2 ][ 3 ]

Ký hiệu cột Tên mảng Ký hiệu hàng

 2003 Prentice Hall, Inc. All rights reserved.

74

4.9 Mảng nhiều biến • Khởi tạo – Mặc định 0 – Các giá trị khởi tạo được nhóm lại theo hàng trong các dấu 1 ngoặc 3 int b[ 2 ][ 2 ] = { {

Row 0 1, 2

},

{ Row 1 3, 4

} };

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

 2003 Prentice Hall, Inc. All rights reserved.

2 4

1

0

3

4

75

4.9 Mảng nhiều biến • Xét như thường cout << b[ 0 ][ 1 ];

– Xuất ra 0 – Không được dùng dấu phảy (,)

1

0

3

4

cout << b[ 0, 1 ]; • Lỗi cú pháp

• Các nguyên mẫu hàm – Phải định rõ kích cỡ của cácsubscript • Subscript đầu tiên không cần thiết, giống mảng đơn biến

– void printArray( int [][ 3 ] );

 2003 Prentice Hall, Inc. All rights reserved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// Fig. 4.22: fig04_22.cpp // Initializing multidimensional arrays. #include using std::cout; using std::endl;

Outline Chú ý dạng thức của nguyên mẫu.

void printArray( int [][ 3 ] ); int main() { int array1[ 2 ][ 3 ] = { { 1, 2, 3 }, { 4, int array2[ 2 ][ 3 ] = { 1, 2, 3, 4, 5 }; int array3[ 2 ][ 3 ] = { { 1, 2 }, { 4 } };

fig04_22.cpp (1 of 2)

Lưu ý nhiều kiểu khởi tạo khác nhau. Các phần tử trong array2 được gán cho hàng đầu tiên sau đó tới hàng 2d then the second. 5, 6 } };

cout << "Values in array1 by row are:" << endl; printArray( array1 ); cout << "Values in array2 by row are:" << endl; printArray( array2 ); cout << "Values in array3 by row are:" << endl; printArray( array3 ); return 0;

// indicates successful termination

} // end main

 2003 Prentice Hall, Inc. All rights reserved.

76

28 29 30 31 32 33 34 35 36 37 38 39 40 41

Vòng lặp for thường được

// function to output array with two rows and three columns dùng để nhắc lại xuyên suốt void printArray( int a[][ 3 ] ) mảng. Các vòng lặp hữu ích { choeach các mảng for ( int i = 0; i < 2; i++ ) { // for row nhiều biến. for ( int j = 0; j < 3; j++ ) cout << a[ i ][ j ] << ' '; cout << endl;

// output column values

Outline fig04_22.cpp (2 of 2) fig04_22.cpp output (1 of 1)

// start new line of output

} // end outer for structure } // end function printArray

Values in array1 by row are: 1 2 3 4 5 6 Values in array2 by row are: 1 2 3 4 5 0 Values in array3 by row are: 1 2 0 4 0 0

 2003 Prentice Hall, Inc. All rights reserved.

77

78

4.9 Mảng nhiều biến • Tiếp theo: chương trình hiển thị giá trị khởi tạo – – – –

Sau đó, chương trình tiếp tục tìm điểm sinh viên Mảng nhiều biến (bảng biểu) Hàng là sinh viên Cột là điểm Quiz1 Quiz2

 2003 Prentice Hall, Inc. All rights reserved.

Student0 95

85

Student1

80

89

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// Fig. 4.23: fig04_23.cpp // Double-subscripted array example. #include using using using using

Outline fig04_23.cpp (1 of 6)

std::cout; std::endl; std::fixed; std::left;

#include using std::setw; using std::setprecision; const int students = 3; const int exams = 4;

// number of students // number of exams

// function prototypes int minimum( int [][ exams ], int, int ); int maximum( int [][ exams ], int, int ); double average( int [], int ); void printArray( int [][ exams ], int, int );

 2003 Prentice Hall, Inc. All rights reserved.

79

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

int main() { // initialize student grades for three students (rows) int studentGrades[ students ][ exams ] = { { 77, 68, 86, 73 }, { 96, 87, 89, 78 }, { 70, 90, 86, 81 } };

Outline fig04_23.cpp (2 of 6)

// output array studentGrades cout << "The array is:\n"; printArray( studentGrades, students, exams ); // determine smallest and largest grade values cout << "\n\nLowest grade: " << minimum( studentGrades, students, exams ) << "\nHighest grade: " << maximum( studentGrades, students, exams ) << '\n'; cout << fixed << setprecision( 2 );

 2003 Prentice Hall, Inc. All rights reserved.

80

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

// calculate average grade for each student for ( int person = 0; person < students; person++ ) cout << "The average grade for student " << person << " is " << average( studentGrades[ person ], exams ) << endl; return 0;

Outline fig04_23.cpp (3 of 6)

Xác định điểm trung bình cho viên. Chúng ta thông qua mảng/ hàng chứa điểm sinh viên the average for one student. Lưu ý rằng bản thân studentGrades[0] là pupils, int tests ) một mảng.

// indicates successful termination mỗi sinh

} // end main

// find minimum grade int minimum( int grades[][ exams ], int { int lowGrade = 100; // initialize to highest possible grade for ( int i = 0; i < pupils; i++ ) for ( int j = 0; j < tests; j++ ) if ( grades[ i ][ j ] < lowGrade ) lowGrade = grades[ i ][ j ]; return lowGrade; } // end function minimum

 2003 Prentice Hall, Inc. All rights reserved.

81

70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

// find maximum grade int maximum( int grades[][ exams ], int pupils, int tests ) { int highGrade = 0; // initialize to lowest possible grade

Outline fig04_23.cpp (4 of 6)

for ( int i = 0; i < pupils; i++ ) for ( int j = 0; j < tests; j++ ) if ( grades[ i ][ j ] > highGrade ) highGrade = grades[ i ][ j ]; return highGrade; } // end function maximum

 2003 Prentice Hall, Inc. All rights reserved.

82

87 88 89 90 91 92 93 94 95 96 97 98

// determine average grade for particular student double average( int setOfGrades[], int tests ) { int total = 0;

Outline fig04_23.cpp (5 of 6)

// total all grades for one student for ( int i = 0; i < tests; i++ ) total += setOfGrades[ i ]; return static_cast< double >( total ) / tests;

// average

} // end function maximum

 2003 Prentice Hall, Inc. All rights reserved.

83

99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118

// Print the array void printArray( int grades[][ exams ], int pupils, int tests ) { // set left justification and output column heads cout << left << " [0] [1] [2] [3]";

Outline fig04_23.cpp (6 of 6)

// output grades in tabular format for ( int i = 0; i < pupils; i++ ) { // output label for row cout << "\nstudentGrades[" << i << "] "; // output one grades for one student for ( int j = 0; j < tests; j++ ) cout << setw( 5 ) << grades[ i ][ j ]; } // end outer for } // end function printArray

 2003 Prentice Hall, Inc. All rights reserved.

84

The array is: [0] studentGrades[0] 77 studentGrades[1] 96 studentGrades[2] 70

[1] 68 87 90

[2] 86 89 86

[3] 73 78 81

Outline fig04_23.cpp output (1 of 1)

Lowest grade: 68 Highest grade: 96 The average grade for student 0 is 76.00 The average grade for student 1 is 87.50 The average grade for student 2 is 81.75

 2003 Prentice Hall, Inc. All rights reserved.

85