Bài giảng Tin học II - Chương VIII: Mảng - Trần Anh Dũng

2/3/2009
CBGD: ThS.Trần Anh Dũng 1
Chương VIII
C
B
G
D
: ThS
.Trần A
nh D
ũng
MẢNG
1
KHÁI NIỆM
C
B
G
D
: ThS
.Trần A
nh D
ũng
2
2/3/2009
CBGD: ThS.Trần Anh Dũng 2
KHAI BÁO MẢNG
1. Mảng một chiều
C
B
G
D
: ThS
.Trần A
nh D
ũng
3
KHAI BÁO MẢNG
1. Mảng một chiều
C
B
G
D
: ThS
.Trần A
nh D
ũng
4
2/3/2009
CBGD: ThS.Trần Anh Dũng 3
KHAI BÁO MẢNG
C
B
1. Mảng một chiều
G
D
: ThS
.Trần A
nh D
ũng
5
KHAI BÁO MẢNG
1. Mảng nhiều chiều
C
B
G
D
: ThS
.Trần A
nh D
ũng
6
2/3/2009
CBGD: ThS.Trần Anh Dũng 4
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
7
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
8
2/3/2009
CBGD: ThS.Trần Anh Dũng 5
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
9
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
10
2/3/2009
CBGD: ThS.Trần Anh Dũng 6
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
Khi lập trình, lập trình viên cần thêm kí tự NUL vào cuối chuỗi
(nếu không sẽ là mảng kí tự)
11
Cả hai hàm đều có prototype nằm trong file stdio.h
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
12
2/3/2009
CBGD: ThS.Trần Anh Dũng 7
KHAI BÁO MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
13
KHỞI ĐỘNG TRỊ CỦA MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
14
2/3/2009
CBGD: ThS.Trần Anh Dũng 8
KHỞI ĐỘNG TRỊ CỦA MẢNG
C
B
G
D
: ThS
.Trần A
nh D
ũng
15
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
16
2/3/2009
CBGD: ThS.Trần Anh Dũng 9
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
17
Vòng lặp for thứ nhất (biến chạy i):
-Lần 1: Tìm số lớn nhất, ghi đầu tiên bên trái
-Lần 2: Tìm số lớn nhì, ghi thứ nhì bên trái
- 
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
18
2/3/2009
CBGD: ThS.Trần Anh Dũng 10
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
19
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
20
2/3/2009
CBGD: ThS.Trần Anh Dũng 11
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
21
MẢNG LÀ ĐỐI SỐ CỦA HÀM –
MẢNG LÀ BIẾN TOÀN CỤC
C
B
G
D
: ThS
.Trần A
nh D
ũng
22
2/3/2009
CBGD: ThS.Trần Anh Dũng 12
CÁC ỨNG DỤNG 
1. Sắp xếp mảng
C
B
G
D
: ThS
.Trần A
nh D
ũng
23
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
24
2/3/2009
CBGD: ThS.Trần Anh Dũng 13
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
25
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
ấ
26
D u -
2/3/2009
CBGD: ThS.Trần Anh Dũng 14
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
27
Sai với giải thuật
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
28
2/3/2009
CBGD: ThS.Trần Anh Dũng 15
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
29
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
30
2/3/2009
CBGD: ThS.Trần Anh Dũng 16
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
31
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
32
2/3/2009
CBGD: ThS.Trần Anh Dũng 17
CÁC ỨNG DỤNG 
C
B
G
D
: ThS
.Trần A
nh D
ũng
33
STACK 
C
B
G
D
: ThS
.Trần A
nh D
ũng
34
2/3/2009
CBGD: ThS.Trần Anh Dũng 18
STACK
C
B
G
D
: ThS
.Trần A
nh D
ũng
35
STACK
Để truy xuất stack, ta dùng một biến để quản lý đỉnh stack, biến
đó là t Khi biế à ó t ị CB
G
D
: ThS
.Trần A
nh D
ũng
op. n n y c r :
¾MAXTACK -1 (là một trị đã được khai báo sẵn, cho biết
kích thước tối đa của stack) Î stack đang đầy, không thể
đẩy thêm một phần nào vào stack nữa được.
¾ 0 thì stack đang rỗngÎ không thể lấy trị từ stack ra được
36
2/3/2009
CBGD: ThS.Trần Anh Dũng 19
STACK
C
B
G
D
: ThS
.Trần A
nh D
ũng
37
STACK
C
B
G
D
: ThS
.Trần A
nh D
ũng
38
2/3/2009
CBGD: ThS.Trần Anh Dũng 20
STACK
C
B
G
D
: ThS
.Trần A
nh D
ũng
39
QUEUE
Queue:
9 Là một cấu trúc dữ liệu.
9 Việc thêm dữ liệu vào được thực hiện ở một đầu, còn việc lấy
ột hầ tử khỏi đượ thự hiệ ở đầ ki th t ật CB
G
D
: ThS
.Trần A
nh D
ũng
m p n ra queue c c n u a eo r
tự vào đầu tiên ra đầu tiên (first-in first-out).
9 Phần tử đầu tiên ra khỏi queue gọi là front, phần tử sau cùng
ra khỏi queue gọi là rear.
9 Queue có nhiều loại, tuy nhiên loại queue được sử dụng trong
lập trình nhiều vẫn là queue vòng. Biến đếm count để biết
được số phần tử đang có trong queue
40
.
2/3/2009
CBGD: ThS.Trần Anh Dũng 21
QUEUE
Tương tự như đối với stack, các thao tác cần có để làm việc trên
queue:
C
B
G
D
: ThS
.Trần A
nh D
ũng
41
QUEUE
C
B
G
D
: ThS
.Trần A
nh D
ũng
42
2/3/2009
CBGD: ThS.Trần Anh Dũng 22
QUEUE
VD:
C
B
G
D
: ThS
.Trần A
nh D
ũng
43
QUEUE
C
B
G
D
: ThS
.Trần A
nh D
ũng
44
2/3/2009
CBGD: ThS.Trần Anh Dũng 23
QUEUE
C
B
G
D
: ThS
.Trần A
nh D
ũng
45
QUEUE
C
B
G
D
: ThS
.Trần A
nh D
ũng
46
2/3/2009
CBGD: ThS.Trần Anh Dũng 24
BÀI TẬP
C
B
G
D
: ThS
.Trần A
nh D
ũng
47
QUEUE
C
B
G
D
: ThS
.Trần A
nh D
ũng
48