CẤU TRÚC DỮ LIỆU TUYẾN TÍNH VÀ CÁCH CÀI ĐẶT BẰNG MẢNG

12/14/2014 8:12:10 AM
1
CHƯƠNG 4: CẤU TRÚC DỮ LIỆU TUYẾN TÍNH VÀ
CÁCH CÀI ĐẶT BẰNG MẢNG
12/14/2014 8:12:10 AM
2
I. Mảng
II. Ngăn xếp (Stack)
III. Hàng đợi (Queue)
Khái niệm
Lưu trữ mảng
Khái niệm
Cài đặt stack bằng mảng
Ứng dụng
Khái niệm
Cài đặt Queue bằng mảng
Ứng dụng
I. Mảng
12/14/2014 8:12:10 AM
3
1. Khái niệm
 
12/14/2014 8:12:10 AM
4
2. Lưu trữ mảng
Mảng được lưu trữ trong máy bởi một vùng nhớ liên tục. Ở đây chúng ta quan tâm đến mảng một chiều và mảng hai chiều.
Mảng một chiều
là dãy hữu hạn các phần tử cùng kiểu
là mảng dùng một chỉ số để xác định các phần tử của mảng
Khai báo : Var TênMảng : array[cậnđầu . .cậncuối] of kiểumảng;
TênMảng: tên gọi tự đặt theo quy tắc đặt tên.
Kiểu mảng: kiểu mà các phần tử của mảng lưu trữ trong từng ô nhớ.
Cậnđầu, cậncuối: xác định giá trị chỉ số đầu và chỉ số cuối của mảng.


12/14/2014 8:12:10 AM
5
12/14/2014 8:12:10 AM
6
Nếu mỗi phần tử có kiểu mảng chiếm s từ máy thì hệ thống sẽ dành ra
(cậncuối-cậnđầu+1)*s từ máy liên tục đủ để lưu trữ mảng .
 
2. Lưu trữ mảng
b) Mảng hai chiều
Mảng hai chiều là bảng các phần tử cùng kiểu.
Gần giống như mảng một chiều , mảng hai chiều dùng hai chỉ số để xác định phần tử của mảng.
Khai báo:
Var TênMảng : array [1..m,1..n] of KiểuPhầnTửCủaMảng ;
(m là số hàng ,n là số cột).


12/14/2014 8:12:10 AM
7
12/14/2014 8:12:10 AM
8
Lưu trữ mảng hai chiều: có hai cách lưu trữ
Lưu trữ theo hàng (hết hàng này đến hàng khác).
Với cách lưu trữ này thì địa trỉ của phần tử ở hàng i cột j được
tính theo công thức:
Loc(A[i,j])= Loc([1,1])+[(i-1)*n+(j-1)]*s
12/14/2014 8:12:10 AM
9
Công thức tổng quát xác định phần tử ở hàng i cột j :
Loc(A[i,j]) = Loc(A[1,1]) + [(j-1)*m+(i-1)]*s
Lưu trữ theo cột
II. Ngăn xếp (Stack)
12/14/2014 8:12:10 AM
10
1. Định nghĩa
Khái niệm
Stack là một danh sách mà trong đó thao tác thêm một phần tử vào trong danh sách và thao tác lấy ra một phần tử trong danh sách được thực hiện ở cùng một đầu.
Stack chứa các đối tượng làm việc theo cơ chế vào sau ra trước (LIFO).

VD: băng đạn súng ngắn: ta chỉ có thể thêm đạn 1 đầu của băng súng và khi lấy đạn ra cũng ở chính đầu đó....
12/14/2014 8:12:10 AM
11
12/14/2014 8:12:10 AM
12
X
Y
Z
TOP
Stack 3 phần tử
Sau khi lấy ra một phần từ
W
Sau khi thực hiện Push(W)
Ví dụ:
Các thao tác trên ngăn xếp
Create(): Tạo stack mới, rỗng
Push(E,S): Thêm đối tượng vào đầu stack
Pop(S): Lấy đối tượng ở đỉnh stack ra khỏi stack và trả về giá trị của nó. Nếu stack rỗng thì lỗi sẽ xảy ra.
Empty(S): Kiểm tra xem stack có rỗng không.
Full(S): Kiểm tra Stack có tràn hay không.
Top(S): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra.
12/14/2014 8:12:10 AM
13
Cài đặt stack bằng mảng
Sử dụng mảng một chiều để cài đặt Stack.
Biến Top để giữ phần từ ở đỉnh Stack.
Nếu chỉ số của Mảng bắt đầu từ 1 thì

Stack rỗng khi Top = 0
Stack đầy khi Top = Max

Nhược điểm của cách cài này là kích thước của mảng cố định
Muốn khắc phục nhược điểm này ta phải sử dụng danh sách liên kết được học ở chương sau.
12/14/2014 8:12:10 AM
14
1
2
3
4
…
…
Max
1
2
3
4
…
…
Max
0
Mảng
TOP
Giải thuật của các thuật toán cơ bản trên ngăn xếp
12/14/2014 8:12:10 AM
15
1. Khai báo
Const Max=10;
Type Stack = Record
A: Array[1..Max] of integer;
TOP: 0..Max;
end;
12/14/2014 8:12:10 AM
16



2.Creat(S): Tạo stack mới và rỗng
Procedure Creat(Var S:Stack);
Begin
S.Top:=0;
end;
12/14/2014 8:12:10 AM
17
Là S>


1
2
3
4
5
Top = i
Top=0
3. Empty(S): Kiểm tra rỗng
Function Empty(S:Stack):Boolean;
begin
If S.Top=0 then Empty:=true else Empty:=false;
end;
12/14/2014 8:12:10 AM
18
< Khai báo Hàm với Tham số là S và kiểu dữ liệu là Boolean>

4. Full(S): Kiểm tra đầy
Function Full(S:Stack):Boolean;
begin
If S.Top=Max then Full:=True else Full:=False;
end;
12/14/2014 8:12:10 AM
19


5. Pop(S): Xóa phần tử ở đỉnh Stack
Procedure Pop(Var S:Stack);
begin
If Empty(S) then writeln(`Stack rong ko co phan tu de xoa`)
else
begin
S.Top:=S.Top-1;
end;
end;
12/14/2014 8:12:10 AM
20
Hiện câu lệnh sau else>
Top đi 1 đơn vị>
1
2
3
4
5
6
Top
6. Push(S,x): Đẩy phần tử x vào đỉnh stack
Procedure Push(Var S:Stack; x:integer);
begin
If Full(S) then writeln(`Stack day khong the them phan tu vao`)
else
begin
S.Top:=S.Top+1;
S.A[S.Top]:=x;
end;
end;
12/14/2014 8:12:10 AM
21



1
2
3
4
5
6
TOP
7
7. Top(S): Trả về giá trị hiện tại ở đỉnh Stack
Function Top(S:Stack);
begin
If Empty(S) then writeln(`Stack rong ko co phan tu de lay ra`)
else
Top:=S.A[S.Top];
end;
12/14/2014 8:12:10 AM
22


Ứng dụng
Stack được sử dụng nhiều trong lĩnh vực máy tính
Nhờ sử dụng Stack các lời gọi thủ tục được thực hiện theo đúng thứ tự.
12/14/2014 8:12:10 AM
23
Đổi số nguyên hệ 10 sang hệ 2
Ý tưởng thuật toán:
Lấy số nguyên đó chia lấy phần dư cho 2 cho đến khi số chia bằng 0
Số dư thu được đưa vào Stack bằng lệnh Push(S,x)
In Stack ra màn hình.
12/14/2014 8:12:10 AM
24
Input
10
2
5
0
2
2
1
2
1
0
2
0
1
Output
Đổi số nguyên hệ 10 sang hệ 2
Thuật toán
While (n/2)<>0 do
Begin
Push(S,n mod 2);
n:=n div 2;
End;
While Empty(S) = False do
Begin
Write(Top(S):4);
Pop(S);
End;
12/14/2014 8:12:10 AM
25
<Đẩy số dư của n chia 2 vào stack>





Chuyển biểu thức trung tố sang hậu tố
Trong biểu thức trung tố các toán tử được đặt giữa các toán hạng, VD:
a * b
f * g – b
d / e * c + 2
Trong biểu thức hậu tố các toán tử được đặt sau các toán hạng, VD:
a b *
f g * b -
d e / c * 2 +
12/14/2014 8:12:10 AM
26
Các thao tác thực hiện giải thuật chuyển biểu thức trung tố sang hậu tố
Quét đầu vào từ trái sang phải, nếu gặp toán hạng thì đưa vào chuỗi đầu ra.
Nếu gặp toán tử thì so sánh thứ tự thực hiện của toán tử này với toán tử đứng đầu stack.
Nếu có thứ tự thực hiện trước thứ tự thực hiện của toán tử ở đỉnh thì lưu vào stack
Nếu có thứ tự thực hiện sau thứ tự thực hiện của toán tử ở đỉnh thì ta đưa toán tử ở đỉnh stack ra chuỗi đầu ra. Lặp lại hành động này cho tới khi toán tử đang xét có thứ tự thực hiện trước thứ tự thực hiện của toán tử ở đỉnh hoặc stack rỗng.
Sau khi duyệt hết chuỗi đầu vào, ở chuỗi đầu ra còn bao nhiêu toán tử ta lấy ra lần lượt.
12/14/2014 8:12:10 AM
27
Input: a+b*c-d Output: Empty Stack: Empty
Input: a+b*c-d Output: a Stack:
Input: a+b*c-d Output: a Stack:+
Input: a+b*c-d Output: ab Stack:+
Input: a+b*c-d Output: ab Stack:+*
Input: a+b*c-d Output: abc Stack:+*
Input: a+b*c-d Output: abc*+ Stack:-
Input: a+b*c-d Output: abc*+d Stack:-
Input: a+b*c-d Output: abc*+d- Stack: Empty
12/14/2014 8:12:10 AM
28
Thuật toán
1. Khai báo:
Const Max=10;
Dau = [`+`,`-`,`*`,`/`];

Var S:string;
i, Count:integer;
trungto:string;
12/14/2014 8:12:10 AM
29
2. Cài đặt Stack (1)
Procedure Creat(Var S:String);
Begin
S:= ``;
Count:=0;
end;
12/14/2014 8:12:10 AM
30

2. Cài đặt Stack (2)
Procedure Push(x:char);
begin
begin
Count:=Count+1;
S[Count]:=x;
end;
end;
12/14/2014 8:12:10 AM
31
<Đẩy kí tự x vào trong stack>
2. Cài đặt Stack (3)
Procedure Pop(Var S:String);
begin
Count:=Count-1;
end;
12/14/2014 8:12:10 AM
32

2. Cài đặt Stack (4)
Function Top:Char;
begin
Top:=S[Count];
end;
12/14/2014 8:12:10 AM
33

3. Chương trình con xét thứ tự ưu tiên của toán tử:
Function UuTien(TT:char): integer;
begin
If (TT=`*`) or (TT=`/`) then Uutien:=2;
If (TT=`+`) or (TT=`-`) then Uutien:=1;
end;
12/14/2014 8:12:10 AM
34
4. Chương trình chính
for i:=1 to length(trungto) do
begin
If not (trungto[i] in Dau) then write(trungto[i]) else
begin
If (UuTien(trungto[i])) > (UuTien(Top)) then Push(trungto[i]) end else
begin
While ((UuTien(trungto[i])) <= (UuTien(Top))) and (Count <> 0) do
begin Write(Top); Pop(S); end;
Push(trungto[i]);
end;
end;
end;
12/14/2014 8:12:10 AM
35
5. Hàng đợi (Queue)
12/14/2014 8:12:10 AM
36
5.1: Định nghĩa hình thức
a. Khái niệm
Queue là cấu trúc dữ liệu vào trước, ra trước tuyến tính (FIFO, First in First out). Trong đó các thao tác xóa được thực hiện ở đầu Queue (Front), các thao tác bổ sung được thực hiện ở cuối Queue (Rear). Ta chỉ có thể truy cập vào phần tử ở trong Queue lâu nhất.
A
B
C
D
Front
Rear
12/14/2014 8:12:10 AM
37
5.1: Định nghĩa hình thức
b. Các thao tác cơ bản

Queue gồm có 7 thao tác cơ bản trong đó có thao tác tạo Queue mới, hai thao tác biến đổi Queue và 4 thao tác kiểm tra queue
12/14/2014 8:12:11 AM
38
Các thao tác trong Queue
Creat(Q): Tạo một Queue mới, rỗng
EnQueue(Q,x): Tạo một Queue mới có thêm một phần từ ở cuối Queue
DeQueue(Q): Xóa một phần tử ở đầu Queue
First(Q): Trả về phần tử ở đầu Queue
Last(Q): Kiểm tra phần tử ở cuối Queue
Empty(Q): Kiểm tra rỗng
Full(Q): Kiểm tra đầy
12/14/2014 8:12:11 AM
39
5.2: Cài đặt Queue bằng mảng
coi mảng như một mảng vòng.
Phần tử đầu tiên A[0] sẽ đứng ngay sau phần tử cuối cùng A[Max].
Con trỏ Front và Rear sẽ cùng trỏ vào một vị trí khi Queue rỗng.
Trong trường hợp queue không rỗng thì Front sẽ trỏ vào phần tử đầu queue.
Rear luôn trỏ vào phần từ cuối Queue.
Như vậy queue sẽ đầy trong hai trường hợp: Rear trỏ vào phần tử cuối cùng của mảng, Front trỏ vào phần tử đầu tiên của mảng hay Rear=Front+1.
12/14/2014 8:12:11 AM
40
Queue rỗng
R
F
A
B
C
D
E
F
G
R
Queue có
3 phần tử
F
Queue đầy
12/14/2014 8:12:11 AM
41
H
Program hangdoi;
uses crt;
Const Max=100;
Type Queue = record
A:array[0..Max] of integer;
Front, Rear, Count: 0..Max;
End;
Var Q:Queue;
Tên chương trình
Gọi crt (dùng để xóa màn hình)
Khai báo hằng số

Mô tả kiểu dữ liệu Queue


Khai báo biến
12/14/2014 8:12:11 AM
42
1. Khai báo
2. Creat: Tạo Queue mới
Procedure Creat(Var Q:Queue);
Begin
Q.Front:=1;
Q.Rear:=0;
Q.Count:=0;
End;
12/14/2014 8:12:11 AM
43


3. Empty(Q): Kiểm tra rỗng
Function Empty(Q:Queue):Boolean;
Begin
If Q.Count=0 then Empty:=True else Empty:=False;
End;
12/14/2014 8:12:11 AM
44
Không có phần tử nào trong Queue>
4. Full(Q): Kiểm tra đầy
Function Full(Q:Queue):Boolean;
Begin
If Q.Count=Max then Full:=true else Full:=False;
End;
12/14/2014 8:12:11 AM
45
Số phần tử trong Queue lúc này là max>
5.EnQueue(Q,x): Thêm phần tử x vào cuối Queue Q
Procedure EnQueue(var Q:Queue; x:integer);
begin
If Full(Q) then writeln(`Hang day khong the chen them`)
else
begin
If Q.Rear = max then Q.Rear:=1 else Q.Rear:=Q.Rear+1;
Q.A[Q.Rear] :=x;
Q.Count:=Q.Count+1;
writeln(`chen thanh cong`);
end;
end;
12/14/2014 8:12:11 AM
46
6. DeQueue(Q): Xóa phần tử ở đầu Queue Q
Procedure DeQueue(Var Q:Queue);
begin
If Empty(Q) then writeln(`Hang rong khong co phan tu de xoa`)
else
begin
if Q.Front = max then Q.Front:=1 else Q.Front:=Q.Front+1;
Q.Count:=Q.Count-1;
end;
end;
12/14/2014 8:12:11 AM
47
7. First(Q): Trả về giá trị ở đầu Queue
Function First(Q:Queue):integer;
begin
If Empty(Q) then writeln(`Queue rong`) else
First:=Q.A[Q.Front];
end;
12/14/2014 8:12:11 AM
48

8. Last(Q): Kiểm tra giá trị ở cuối Queue
Function Last(Q:Queue):integer;
begin
If Empty(Q) then writeln(`Queue rong`) else
Last:=Q.A[Q.Rear];
end;
12/14/2014 8:12:11 AM
49
5.3: Ứng dụng của Queue
là cấu trúc dữ liệu hết sức quan trọng và được sử dụng trong khoa học máy tính.
thường được sử dụng trong trường hợp có các đối tượng nào đó đợi truy cập tài nguyên.
Ví dụ, dòng người xếp hàng đợi xe bus là một cấu trúc queue.
Trong máy tính, cấu trúc queue là một dãy các tiến trình xếp hàng đợi tài nguyên như bộ xử lí hoặc thiết bị vào/ra,…
12/14/2014 8:12:11 AM
50
Chuyển phần thập phân từ hệ 10 sang hệ 2
Cách đổi
Lấy phần thập phân nhân với 2 được một số gồm phần nguyên và phần thập phân
Lấy phần thập phân nhân với 2
Nhân đến khi tích thu được có phần nguyên bằng 1.
12/14/2014 8:12:11 AM
51
Chuyển phần thập phân từ hệ 10 sang hệ 2
Ví dụ:
0.625 x 2 = 1 .250
0.250 x 2 = 0 .500
0.500 x 2 = 1 .000
12/14/2014 8:12:11 AM
52
Output: 101
Chuyển phần thập phân từ hệ 10 sang hệ 2
Ý tưởng thuật toán:
Lấy phần thập phân của số Input bằng hàm Frac(x).
Lấy phần thập phân đó x2.
Lấy phần nguyên của tích nhận được bằng hàm Trunc(x).
Đưa phần nguyên trên vào Queue.
Lặp lại bước 2 cho tới khi phần tích ở bước hai = 1.
Đưa Queue ra màn hình.
12/14/2014 8:12:11 AM
53
Chuyển phần thập phân từ hệ 10 sang hệ 2
Code:
Creat(Q); Write(`so thap phan: `); readln(x);
tphan:=frac(x);
Repeat
tphan:=frac(tphan)*2;
nguyen:=Trunc(tphan);
EnQueue(Q,nguyen);
Until (tphan=1) or (full(Q));
While Q.Count<>0 do
begin
Write(First(Q));
DeQueue(Q);
end;
12/14/2014 8:12:11 AM
54
Bài tập cuối chương
Bài 1: Tìm số lớn nhất và số nhỏ nhất của một mảng một chiều gồm 15 số thực.
12/14/2014 8:12:11 AM
55
Bài tập cuối chương
Bài 2: Viết chương trình con lập ma trận chuyển vị của ma trận A hai chiều.
B là ma trận chuyển vị của ma trận A nếu các phần tử của chúng có quan hệ
B[i,j] = A[j,i]
12/14/2014 8:12:11 AM
56
Bài tập cuối chương
Bài 2:








for i:=1 to hang do
for j:=1 to cot do
begin
B[j,i]:=A[i,j];
end;
12/14/2014 8:12:11 AM
57
Bài tập cuối chương
Bài 3: Dùng các phép toán cơ bản của hàng đợi và ngăn xếp, viết một thuật toán đảo ngược các phần tử của hàng đợi.
INPUT: 1 2 3 4 5
OUNTPUT: 5 4 3 2 1
12/14/2014 8:12:11 AM
58
Bài tập cuối chương
While Q.count<>0 do
begin
Push(S,First(Q));
DeQueue(Q);
end;
While S.top<>0 do
begin
EnQueue(Q,Top(S));
Pop(S);
end;
While Q.count<>0 do
begin
Write(First(Q));
DeQueue(Q);
end;
12/14/2014 8:12:11 AM
59
12/14/2014 8:12:11 AM
60
THE END
Cám ơn thầy cô và tất cả các bạn đã theo dõi!