Bài giảng Hệ thống máy tính và ngôn ngữ C - Chương 11: Mảng

ỦA MẢNG 
Khi khai báo mảng là biến toàn cục hoặc tĩnh thì mảng có 
thể được khởi động trị bằng các giá trị hằng. 
Ví dụ : 
 int a[5] = {1, 3, 5, 7, 9}; 
 int b[10] = {1, 2, 3, 4, 5}; 
Nếu số trị ít hơn số phần tử mảng thì các phần tử còn lại 
không được khởi động trị, có nghĩa các phần tử này có trị 
là 0. 
CHƯƠNG 11 
MẢNG 
11.3 KHỞI ĐỘNG TRỊ CỦA MẢNG 
Ví dụ: 
double a[] = {1.23, –5.67, 9.87, 1.34}; 
char s[30] = “I go to shool \n”; 
char ch[] = “Hello, World!”; 
CHƯƠNG 11 
MẢNG 
11.3 KHỞI ĐỘNG TRỊ CỦA MẢNG 
Ví dụ: 
Cho khai báo mảng và khởi động trị như sau: 
 int a[][3] = { 
 { 11, 12, 13}, 
 { 21, 22, 23}, 
 { 31, 32, 33} 
 }; 
 Với khai báo này, mảng a sẽ cĩ 9 phần tử trong 3 hàng 
CHƯƠNG 11 
MẢNG 
11.3 KHỞI ĐỘNG TRỊ CỦA MẢNG 
Ví dụ : 
Chuỗi char s[] = “Hello”; 
char ch[] = {'H', 'e', 'l', 'l', 'o'}; 
H 
 e 
 l 
 l 
 o 
 \0 
H 
 e 
 l 
 l 
 o 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
Khi khai báo đối số của hàm là mảng, kích thước của chiều 
đầu tiên của mảng không cần xác định cụ thể. Tuy nhiên 
từ chiều thứ hai trở đi, kích thước mảng phải xác định. 
Tên mảng chính là địa chỉ của mảng, nên việc truyền tên 
mảng cho hàm chính là truyền địa chỉ thực của mảng nên 
mọi thay đổi trên mảng trong hàm cũng chính là thay đổi 
trên mảng thật (truyền theo kiểu tham số biến). 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
Ví dụ 12.14 (SGT) 
void select_sort (int a[ ], int n) 
{ 
.... 
} 
Ví dụ 12.15, 12.16 (SGT) 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
Ví dụ 12.17: Xét chương trình tính trung bình của các số như 
sau: 
#include 
#define MAX 10 
int Average (int values[]); 
main() 
{ int index; 
 int mean; 
 int a[MAX]; 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
printf (“Mời nhập %d số nguyên: ”, MAX); 
 // Nhập trị cho mảng 
 for (index = 0; index < MAX; index++) 
 scanf (“%d”, &a[index]); 
 mean = Average (a); 
 printf (“Trung bình của các số này là %d.\n”, mean); 
} 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
int Average (int values[]) 
{ 
 int index; 
 int sum = 0; 
 for (index = 0; index < MAX; index++) 
 sum += values[index]; 
 return (sum/MAX); 
} 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ 
ĐỐI SỐ CỦA 
HÀM MẢNG LÀ 
BIẾN TOÀN CỤC 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
#include 
#define MAX 10 
int Average (int values[], int number); 
main() 
{ int index; 
 int mean; 
 int n; 
 int a[MAX]; 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
// Nhập số số nguyên cần làm việc 
 do 
 { printf (“Bạn muốn làm việc với bao nhiêu số nguyên? (0 
< n <= 10): ”); 
 scanf (“%d”, &n); 
 if (n 10) 
 printf (“Sai trị. Nhập lại.\n”); 
 } while (n 10); 
 printf (“Mời nhập %d số nguyên: ”, n); 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
// Nhập trị cho mảng 
 for (index = 0; index < n; index++) 
 scanf (“%d”, &a[index]); 
 mean = Average (a, n); 
 printf (“Trung bình của các số này là %d.\n”, mean); 
} 
CHƯƠNG 11 
MẢNG 
11.4 MẢNG LÀ ĐỐI SỐ CỦA HÀM MẢNG LÀ BIẾN 
TOÀN CỤC 
int Average (int values[], int number) 
{ 
 int index; 
 int sum = 0; 
 for (index = 0; index < number; index++) 
 sum + = values[index]; 
 return (sum/number); 
} 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.1 Sắp xếp mảng 
Trong phần trên, để sắp xếp một mảng, giải thuật được 
nêu ra là giải thuật select sort, trong mục này ta sẽ xét 
thêm hai giải thuật nữa là giải thuật bubble sort và 
quick sort. 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.1 Sắp xếp mảng 
1- Bubble sort (ví dụ 5.17) 
Giải thuật sort này dựa vào nguyên tắc: phần tử nhỏ hơn 
sẽ "nhẹ hơn" và vì vậy sẽ "nổi" lên trên. Như vậy, đây là 
phương pháp so sánh trực tiếp hai phần tử trong mảng với 
nhau, nếu phần tử nào nhỏ sẽ được đổi chỗ sang chỗ có chỉ 
số (cước số) thấp hơn (nếu việc sắp xếp theo thứ tự từ nhỏ 
tới lớn). 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
 11.5.1 Sắp xếp mảng 
1- Bubble sort (ví dụ 5.17) 
Chuong trinh thu ma tran 
Moi ban nhap kich thuoc day: 5 
Moi nhap cac phan tu cua ma tran: 
9 -5 7 0 1 
Lan lap thu 0 
9 -5 0 7 1 
-5 9 0 7 1 
Lan lap thu 1 
-5 9 0 1 7 
-5 0 9 1 7 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.1 Sắp xếp mảng 
1- Bubble sort (ví dụ 5.17) 
Lan lap thu 2 
-5 0 1 9 7 
Lan lap thu 3 
-5 0 1 7 9 
Ma tran duoc sap xep la: 
-5 0 1 7 9 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.1 Sắp xếp mảng 
2- Quick sort 
Đây là giải thuật sort được đánh giá là nhanh nhất trong 
các giải thuật sắp xếp. Nguyên tắc của giải thuật này như 
sau: 
Giải thuật quick sort bắt đầu bằng việc tìm một giá trị 
giữa tầm cho mảng. 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.1 Sắp xếp mảng 
2- Quick sort 
Giá trị giữa tầm có thể được tính bằng trung bình cộng 
của hai phần tử đầu tiên và sau cùng trong phần mảng 
đang được sắp xếp. Giải thuật sẽ chuyển tất cả các phần 
tử có giá trị nhỏ hơn giá trị giữa tầm sang phần có chỉ số 
thấp của mảng, và chuyển tất cả các phần tử có giá trị lớn 
hơn giá trị giữa tầm sang phần có chỉ số cao của mảng. 
CHƯƠNG 11 
MẢNG 
86 3 10 23 12 67 59 47 31 24 
Trị giữa tầm Vị trí trong mảng 
0 1 2 3 4 5 6 7 8 9 
Bước 1: 55 86 3 10 23 12 67 59 47 31 24 
Bước 2: 35 24 3 10 23 12 31 47 59 67 86 
Bước 3: 27 24 3 10 23 12 31 47 59 67 86 
Bước 4: 18 24 3 10 23 12 31 47 59 67 86 
Bước 5: 11 12 3 10 23 24 31 47 59 67 86 
Bước 6: 6 10 3 12 23 24 31 47 59 67 86 
Bước 7: 23 3 10 12 23 24 31 47 59 67 86 
Bước 8: 72 3 10 12 23 24 31 47 59 67 86 
Bước 9: 63 3 10 12 23 24 31 47 59 67 86 
Bước 10: 63 3 10 12 23 24 31 47 59 67 86 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.1 Sắp xếp mảng 
3- Select sort 
Giải thuật sẽ tìm giá trị lớn nhất đưa về vị trí có cước số 
thất nhất, sau đó tìm giá trị lớn thứ nhì đưa về vị trí có 
cước số thất nhì, quá trình diễn ra tương tự cho đến hết 
Ví dụ 8.14(SGT) 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.2 Stack 
Stack (tạm dịch là ngăn xếp) là một kiểu cấu trúc dữ liệu 
do lập trình viên tự lập ra, khi cần, lập trình viên có thể 
thêm một phần tử vào stack, hoặc xóa một phần tử ra 
khỏi stack. 
Đặc điểm của cấu trúc dữ liệu này là dữ liệu được ghi vào 
hoặc lấy ra khỏi stack theo trật tự vào trước ra sau 
(last-in first-out). 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.2 Stack 
Các thao tác cần có để làm việc trên stack: 
- Khởi động stack, tương ứng với hàm init_stack() cần 
thiết kế. 
- Các hàm để xem stack rỗng, đầy, hay xem trị trên đỉnh 
stack. 
- Đẩy một phần tử vào stack, tương ứng hàm push() cần 
thiết kế. 
- Lấy một phần tử từ đỉnh stack ra, tương ứng với hàm 
pop() cần thiết kế. 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.2 Stack 
Ví dụ: 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.2 Stack 
Chương trình ứng dụng stack (SGT) 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.3 Queue 
Queue là một cấu trúc dữ liệu, trong đó việc thêm dữ liệu 
vào được thực hiện ở một đầu, còn việc lấy một phần tử ra 
khỏi queue được thực hiện ở đầu kia. Dữ liệu vào ra queue 
theo trật tự vào đầu tiên ra đầu tiên (first-in first-out). 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.3 Queue 
Cũng tương tự như đối với stack, các thao tác cần có để 
làm việc trên queue: 
- Khởi động queue, tương ứng với hàm init_queue() cần 
thiết kế. 
- Các hàm để xem queue rỗng, đầy. 
- Thêm một phần tử vào queue, tương ứng hàm addqueue() 
cần thiết kế. 
- Lấy một phần tử ra khỏi queue, tương ứng với hàm 
deletequeue() cần thiết kế. 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.3 Queue 
Ví dụ: 
CHƯƠNG 11 
MẢNG 
11.5 CÁC ỨNG DỤNG 
11.5.3 Queue 
Ví du (SGT) 
CHƯƠNG 11 
MẢNG 
BÀI TẬP CUỐI CHƯƠNG 
1. Nhập một ma trận n x n bất kỳ, sắp xếp lại ma trận 
sao cho các trị lớn nhất trên từng hàng, nằm trên đường 
chéo của ma trận. 
2. Viết chương trình tạo và in ra màn hình ma trận có 
dạng sau: 
 a b c d 
 b c d a 
 c d a b n : tham số nhập 
 d a b c 
 n 
CHƯƠNG 11 
MẢNG 
BÀI TẬP CUỐI CHƯƠNG 
3. Nhập một chuỗi bất kỳ từ bàn phím, xóa tất cả các ký 
tự khoảng trắng thừa của chuỗi và in ra màn hình chuỗi 
mới. 
4. Nhập một dãy số từ bàn phím. Viết hai hàm để in ra 
màn hình biểu đồ ngang và biểu đồ dọc của các dấu * 
tương ứng với các số nhập trong dãy số. 
Ví dụ: Nhập 2 4 3; * * * 
 * * * * * 
 * * * * * * 
 * * * * 
CHƯƠNG 11 
MẢNG 
BÀI TẬP CUỐI CHƯƠNG 
5. Viết chương trình tạo và in ra màn hình tam giác 
PASCAL cấp n, với n nhập từ bàn phím. 
6. Viết chương trình tạo ma trận nghịch đảo n x n. 
7. Viết chương trình giải hệ phương trình tuyến tính bằng 
phương pháp Gauss. 
CHƯƠNG 11 
MẢNG 
BÀI TẬP CUỐI CHƯƠNG 
8. Nhập một ma trận vuông bất kỳ, tính tổng các hàng, 
các cột, các đường chéo. 
9. Nhập một ma trận bất kỳ. In ra màn hình các trị và vị 
trí của các số nguyên tố có trong mảng đó. 
10. Viết các hàm đổi từ số sang chuỗi, và từ chuỗi sang số. 
CHƯƠNG 11 
MẢNG 
 KẾT THÚC CHƯƠNG 11 
CHƯƠNG 11 
MẢNG