Bài giảng Lập trình cơ bản: Bài 6

SỬ DỤNG MẢNG

LÊ ĐỨC LONG-NGÔ QUỐC VIỆT 2011

NỘI DUNG

1. Khai báo và sử dụng mảng một hay hai chiều

 Khai báo mảng một chiều  Thao tác trên dữ liệu mảng một chiều  Khai báo mảng hai chiều  Thao tác trên dữ liệu mảng hai chiều  Dùng mảng làm tham số cho hàm

2. Khai báo và sử dụng chuỗi.

 Khai báo chuỗi ký tự  Nhập xuất chuỗi trên bàn phím và màn hình  Một số hàm dùng với chuỗi

3. Bài tập

Ngô Quốc Việt-Lập trình cơ bản 2

MẢNG

 100 quả trứng, mỗi quả trứng có vai trò, tính chất “gần

như nhau” lưu trữ 100 biến ?

 1000 số nguyên trong dãy số nguyên  lưu 1000 biến

nguyên?

 Tính trung bình cộng của một dãy n số (không phải tăng từ 1 đến n)  cần lưu n giá trị  dùng n biến?

 Ví dụ: tính trung bình 10 giá trị

 Nhập 10 giá trị từ bàn phím, lưu vô n1, n2, n3, n4, n5, n6, n7,

n8, n9, n10.

 Tính ntb = (n1, n2, n3, n4, n5, n6, n7, n8, n9, n10) /10.0;

 Khi n lớn thì sao?  Không thể làm như vậy.

Ngô Quốc Việt-Lập trình cơ bản 3

MẢNG

 Mảng được dùng để lưu trữ nhiều giá trị cùng

kiểu và tham gia vào một vấn đề cụ thể.

 Mảng là một biến được cấp phát bộ nhớ liên tục

và bao gồm nhiều biến thành phần.

 Các thành phần của mảng là tập hợp các biến có

cùng kiểu dữ liệu và cùng tên.

 Để truy xuất thành phần, dùng chỉ số mảng.

Ngô Quốc Việt-Lập trình cơ bản 4

Khai báo mảng một chiều

< Kiểu > < Tên mảng > [ < Số phần tử tối đa> ] ;

 Ví dụ khai báo mảng integer 50 phần tử

int iArr[5];

//kiểu integer, tên iArr, số phần tử: 5

Các phần tử của mảng iArr là

iArr[0]

iArr[1]

iArr[2]

iArr[3]

iArr[4]

Chỉ số phần tử mảng iArr[0], iArr[1], ..iArr[4]: là các tên biến sử dụng được.

 Ví dụ khai báo mảng float 50 phần tử

float fArr[20]; //kiểu float, tên fArr, số lượng: 20

Ngô Quốc Việt-Lập trình cơ bản 5

Sử dụng mảng một chiều  Chương trình khai báo, nhập và in ra mảng 10 phần tử

integer

#include int main() {

int iMyArr[10]; cout << “Hay nhap 10 phan tu ” << endl; for (int i = 0; i < 10; i ++)

{ cout << “Nhap phan tu thu: “ << i; cin >> iMyArr[i]; cout << endl;

} cout << “Cac phan tu moi nhap tinh tu cuoi la:” << endl; { for (int i = 9; i >= 0; i --)

cout << iMyArr[i] << “’ ”;

}

Ngô Quốc Việt-Lập trình cơ bản 6

Sử dụng mảng một chiều  Truy xuất các phần tử mảng thông qua chỉ số

mảng.

int iArr[5];

iArr[0]

iArr[1]

iArr[2]

 Chỉ số mảng bắt đầu từ zero.  Phần tử cuối cùng có chỉ số n-1, với n là kích

thước mảng

Ngô Quốc Việt-Lập trình cơ bản 7

Sử dụng mảng một chiều

Ngô Quốc Việt-Lập trình cơ bản 8

Sử dụng mảng một chiều

 Khai báo tường minh và gán giá trị

 Khai báo không tường minh

Ngô Quốc Việt-Lập trình cơ bản 9

Trường hợp với chuỗi - string

Ngô Quốc Việt-Lập trình cơ bản 10

Processing an array – NNLT C

Lowercase to Uppercase Text Conversion

/* read in a line of lowercase text to uppercase */ #include #include #define SIZE 80 void main ( )

{

char letter[SIZE]; int count ; /* read in the line */ for (count = 0; count < SIZE; ++count)

letter[count] = getchar();

/* display the line in uppercase */ for (count = 0; count < SIZE; ++count)

putchar(toupper(letter[count]));

}

Ngô Quốc Việt-Lập trình cơ bản 11

Sử dụng mảng một chiều

Ngô Quốc Việt-Lập trình cơ bản 12

Khởi tạo mảng lúc khai báo

 Mục đích: gán giá trị cho phần tử mảng lúc khai

báo.

 Khởi tạo khi biết rõ mảng cần giá trị nào.  Ví dụ, khai báo mảng chứa các loại tiền có mệnh

giá 500, 1000, 2000, 5000, 10000. int iMoneyArr[5] = {500, 1000, 2000, 5000, 10000}’;  Ví dụ, khai báo mảng chứa các giá vé, không cần kích thước. Kích thước mảng xác định bởi số phần tử khởi tạo int iMoneyArr[] = {40000, 50000, 60000, 240000}’;

Ngô Quốc Việt-Lập trình cơ bản 13

Ví dụ về mảng

 Trả về giá trị lớn nhất trong mảng các số thực

#include int main() {

const int MAXPHANTU = 20; float fMyArr[MAXPHANTU]; cout << “Hay nhap “ << MAXPHANTU << “ phan tu ” << endl; for (int i = 0; i < MAXPHANTU; i ++)

{

cout << “Nhap phan tu thu: “ << i; cin >> fMyArr[i]; cout << endl;

} float fMax = iMyArr[0]; for (int i = 1; i < MAXPHANTU; i ++)

{

if(fMax < fMyArr [i])

fMax = fMyArr [i];

} cout << “Gia tri lon nhat la: “ << fMax << endl;

}

Ngô Quốc Việt-Lập trình cơ bản 14

“Xoá” một phần tử ra khỏi mảng

 “Xoá”: thật ra là “dồn” các phần tử phía sau phần

tử cần xóa lên trên một vị trí.

 “Xoá” một phần tử mảng không làm thay đổi

kích thước mảng

 Duyệt mảng từ trái sang phải . Xuất phát từ vị trí cần xoá tiến hành dời các phần tử về phía trước cho đến khi kết thúc mảng

Ngô Quốc Việt-Lập trình cơ bản 15

“Xoá” một phần tử ra khỏi mảng

 Ví dụ “xoá” một phần tử tại vị trí cho trước trong

mảng

void XoaPhanTuMatTai(int iArr[], int &n, int vitri) {

if(vitri >= n || vitri < 0) return;

for(int i = vitri; i < n-1; i ++)

iArr[i] = iArr[i+1];

n = n-1;

}

Ngô Quốc Việt-Lập trình cơ bản 16

“Thêm” một phần tử vào mảng

 “Thêm” một giá trị vào mảng: dời các phần tử về bên phải mảng, chừa ra một chỗ trống để đặt giá trị mới vào

 “Thêm” một phần tử mảng không làm thay

đổi kích thước mảng

void ChenX (int a[], int &n, int X, int vitri) {

for (int i = n; i >vitri ; i--) a[i] = a[i-1] ;

a[vitri] = X; n++;

}

Ngô Quốc Việt-Lập trình cơ bản 17

Bài tập luyện tập

1. Viết chương trình nhập vào N ( <= 50)số nguyên,

tính trung bình cộng N số nguyên đó

2. Nhập vào nhập vào N ( <= 50) số nguyên chứa trong mảng. Nhập vào phần tử x. Tìm vị trí xuất hiện của x trong mảng đã nhập. Nếu x không tồn tại trong mảng, xuất ra -1.

3. Sửa lại bài 2 với yêu cầu, viết hàm tìm vị trí phần tử có giá trị x xuất hiện cuối cùng trong mảng. 4. Viết hàm in vị trí các phần tử nguyên tố trong

mảng các số nguyên.

Ngô Quốc Việt-Lập trình cơ bản 18

Bài tập luyện tập

5. Viết hàm tính tổng các phần tử nằm ở vị trí lẻ

trong mảng các số nguyên.

6. Viết hàm tính tổng các phần tử nằm ở vị trí

nguyên tố trong mảng

7. Viết chương trình nhập M giá trị nguyên vào mảng. Thực hiện xoá ra khỏi mảng các giá trị âm. 8. Viết chương trình xóa phần tử nhỏ nhất ra khỏi

mảng.

9. Viết hàm chèn phần tử có giá trị X vào phía sau

phần tử có giá trị lớn nhất trong mảng

Ngô Quốc Việt-Lập trình cơ bản 19

Sử dụng tham số mảng một chiều

 Cho phép chuyển mảng một chiều giữa các hàm  Ví dụ về hàm có tham số dạng mảng

//Trả về giá rị max trong mảng //n: số phần tử trong mảng //iArr: mảng input int KiemtraMax(int iArr[], int n) {

int iMax = iArr[0]; for(int i = 1; i < n; i ++) if(iMax < iArr[i])

iMax = iArr[i];

return iMax;

}

Ngô Quốc Việt-Lập trình cơ bản 20

Sử dụng tham số mảng một chiều

int main() {

int iArr[10]; cout << “Nhap 10 gia tri cho mang” << endl for(int i = 0; i < 10; i ++) {

cout < “Nhap gia tri cho phan tu thu: “ << i; cin >> iArr[i]; //nhap gia tri cho phan tu mang thu i coutn << endl;

} int iMax = KiemtraMax(iArr, 10); cout << “Gia tri lon nhat la: “ << iMax; return 0;

}

Ngô Quốc Việt-Lập trình cơ bản 21

Sử dụng tham số mảng một chiều

An entire array can be passed to a function as an argument. To pass an array to a function, the array name must appear by itself, without brackets or subscripts, as an actual argument within the function call.

 Lời gọi hàm – sử dụng tên của mảng

Ngô Quốc Việt-Lập trình cơ bản 22

Sử dụng tham số mảng một chiều

Kết luận: Mảng được truyền vào trong hàm theo dạng tham biến

Ngô Quốc Việt-Lập trình cơ bản 23

Sử dụng tham số mảng một chiều

Lưu ý: cách sử dụng biến toàn cục và biến địa phương

Ngô Quốc Việt-Lập trình cơ bản 24

Bài toán tìm phần tử

YÊU CẦU: Tìm phần tử đầu tiên trong (A,n) thoả mãn một điều kiện nào đó

DẠNG BÀI TOÁN:

flag = -1; i = 0; // flag được gọi là phần tử lính canh Lặp trong khi (i < n) và (flag = -1) làm

Nếu (A[i] thoả điều kiện) thì

flag = i; Cuối nếu i ++; Cuối lặp

// kết thúc vòng lặp nếu j = -1 thì tìm không có – ngược lại thì a[j] chính là phần tử cần tìm ở vị trí j

Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số nguyên A gồm n phần tử. Tìm và in ra phần tử âm đầu tiên trong mảng tận cùng bằng 6

Gợi ý:

int Am_6(int A[ ], int n);

Ngô Quốc Việt-Lập trình cơ bản 25

Bài toán tìm phần tử

YÊU CẦU: Tìm tất cả các phần tử trong (A,n) thoả mãn một điều kiện nào đó

DẠNG BÀI TOÁN:

//Sử dụng một mảng phụ (B,m) để lưu phần tử tìm được //Duyệt mảng (B,m) để xuất tất cả các phần tử tìm được m = 0; Lặp tuần tự i = 0, 1, 2, … n-1 làm Nếu (A[i] thoả điều kiện) thì

B[m] = A[i]; m = m + 1;

Cuối nếu

Cuối lặp

Hoặc, trường hợp xuất thẳng ra màn hình:

Lặp tuần tự i = 0, 1, 2, … n-1 làm Nếu (A[i] thoả điều kiện) thì

In A[i] ra màn hình

Cuối nếu

Cuối lặp

Ngô Quốc Việt-Lập trình cơ bản 26

Bài toán tìm phần tử lớn/nhỏ nhất

YÊU CẦU: Tìm phần tử lớn nhất (max) hoặc nhỏ nhất (min) trong (A,n) Điều kiện cần: S là tập hợp có thứ tự toàn phần – nghĩa là, mọi cặp phần tử của S đều có thể so sánh được với nhau

DẠNG BÀI TOÁN:

// Tìm phần tử nhỏ nhất + Chọn phần tử x0  S, gán min = x0 + Lặp cho đến khi chọn hết các phần tử của S Với mỗi phần tử kế tiếp x  S, nếu

// Tìm phần tử lớn nhất + Chọn phần tử x0  S, gán max = x0 + Lặp cho đến khi chọn hết các phần tử của S Với mỗi phần tử kế tiếp x  S, nếu max < x thì gán max = x

min > x thì gán min = x

Cuối lặp.

Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số thực A gồm n phần tử. Tìm phần tử nhỏ nhất trong mảng.

Gợi ý:

float Tim_min(float A[ ], int n);

Ngô Quốc Việt-Lập trình cơ bản 27

Bài toán sắp xếp

YÊU CẦU: Sắp xếp các phần tử trong (A,n) thoả mãn một điều kiện nào đó

DẠNG BÀI TOÁN:

// Sắp xếp phần tử tăng dần Lặp tuần tự i = 0, 1, 2, … n-2 làm

Lặp tuần tự j = 1, 2, 3, … n-1 làm

Nếu A[i] > A[j] thì

Tmp = A[i]; // hoán vị 2 phần tử thứ i và j A[i] = A[j]; A[j] = Tmp;

Cuối nếu

Cuối lặp j

Cuối lặp i

// Có nhiều thuật toán sắp xếp như: Selection, Insertion, Buble, Quick, Merge, ...

Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số nguyên A gồm n phần tử. Sắp xếp các phần tử trong mảng A theo thứ tự tăng dần

Gợi ý:

void Sapxep(int A[ ], int n);

Ngô Quốc Việt-Lập trình cơ bản 28

Bài toán sắp xếp

YÊU CẦU: Sắp xếp các phần tử trong (A,n) thoả mãn một điều kiện nào đó

DẠNG BÀI TOÁN:

// Sắp xếp các phần tử thoả điều kiện. // Giữ nguyên vị trí các phần tử khác Lặp tuần tự i = 0, 1, 2, … n-2 làm

Lặp tuần tự j = i+1, i+2, i+3, … n-1 làm Nếu (A[i], A[j] thoả điều kiện) thì

Nếu A[i] > A[j] thì

Hoán vị A[i], A[j];

Cuối nếu

Cuối lặp j

Cuối lặp i

Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số nguyên A gồm n phần tử. Sắp xếp các phần tử không âm trong mảng A theo thứ tự tăng dần

Ngô Quốc Việt-Lập trình cơ bản 29

Bài toán tìm cặp quan hệ

YÊU CẦU: Tìm cặp phần tử trong (A,n) có quan hệ với nhau theo đkiện nào đó

DẠNG BÀI TOÁN:

//Chương trình chính Lặp tuần tự i = 0, 1, 2, … n-2 làm

Lặp tuần tự j = i+1, i+2, i+3, … n-1 làm

Nếu (Quan_he(A[i], A[j])) thì

//Chương trình con-xét quan hệ qh = FALSE; // qh được gọi là cờ hiệu Nếu (A[i], A[j] có quan hệ nhau) thì

In cặp (A[i], A[j]);

qh = TRUE;

Cuối nếu

Cuối lặp j

Cuối nếu return qh;

Cuối lặp i

// nếu qh = FALSE thì không có cặp quan hệ nào, ngược lại thì in ra

Ví dụ: a) Nhập vào 10 số nguyên, xác định xem có cặp số nào trong các số đó có quan

hệ chia hết hay không? In ra nếu có.

b) Nhập vào 10 số nguyên, xác định xem có cặp số nào trong các số đó có hiệu

của chúng bằng 5 hay không? In ra nếu có.

Ngô Quốc Việt-Lập trình cơ bản 30

Mảng hai chiều

 Phát triển tự nhiên từ mảng một chiều.  Là mảng một chiều: trong đó mỗi phần tử lại

là mảng một chiều.

 Ma trận MxN (M hàng N cột): sử dụng mảng hai

chiều để quản lý.

 Các phần tử trong mảng hai chiều được truy xuất

bằng hai chỉ số

Ngô Quốc Việt-Lập trình cơ bản 31

Ví dụ về mảng 2 chiều

Ví dụ:

x là mảng 2 chiều, có m dòng và n cột

float x[20][50]; char page[24][80]; int A[20][20];

Ngô Quốc Việt-Lập trình cơ bản 32

Ví dụ về mảng 2 chiều

Ngô Quốc Việt-Lập trình cơ bản 33

Khai báo mảng hai chiều

< Kiểu dữ liệu > < Tên mảng > [ < Số dòng > ][ < Số cột > ];  Ví dụ khai báo mảng:

//ma trận 5 hàng 6 cột. int iArr[5][6]; float fArr[10][7]//ma trận thực 10 hàng, mỗi hàng 7 cột

 Khai báo mảng 2 chiều và khởi tạo giá trị

int iArr[3][4] = { {1,3,5,4} , {5,1,3,2} , {2,3,4,5} }; float fArr[2][3] = {{3, 4, 7}, {4, 1, 8}};

Ngô Quốc Việt-Lập trình cơ bản 34

Sử dụng mảng hai chiều

 Sử dụng hai chỉ số để truy xuất một phần tử mảng

void Nhap (int a[][], int &d, int &c ) {

printf (“\nNhap so dong: ”); scanf (“ %d”, &d ); printf (“\nNhap so cot: ”); scanf (“%d”, &c ); for ( int i = 0; i < d; i ++ ) for (int j = 0; j < c; j ++) {

printf (“ a[%d][%d] = ”, i, j ); scanf (“%d”, &a[i][j]);

}

Ngô Quốc Việt-Lập trình cơ bản 35