Giáo trình Cấu trúc dữ liệu và giải thuật (Phần 1)

Thủ tục sau xác 
định C là tích Đề-các của A và B. 
Procedure Tich_De_cac( A, B, C) 
 1. C := null; 
 2. Q := A; 
 While Q ≠ null do 
 Begin 
 P:= B; 
 While P ≠ null do 
Begin 
Bo_sung(C, info(Q), info(P)); 
P := link(P); 
 End; 
 Q := link(Q); 
End; 
 3. Return; 
5.5. NGĂN XẾP VÀ HÀNG ĐỢI MÓC NỐI 
 Như ta đã biết, đối với stack việc truy nhập đều thực hiện ở một đầu (đỉnh ). 
Vì vậy việc cài đặt stack bằng cách dùng danh sách móc nối là khá tự nhiên. 
Chẳng hạn, với danh sách nối đơn trỏ bởi L thì có thể coi L như con trỏ trỏ tới 
đỉnh stack chính là bổ sung một nút vào thành nút đầu tiên của danh sách; loại bỏ 
một nút ra khỏi stack chính là loại bỏ nút đầu tiên của danh sách đang trỏ bởi L . 
Trong thủ tục bổ sung với danh sách móc nối ta không phải kiểm tra hiện tượng 
TRÀN như đối với stack kế tiếp, vì stack không hề bị giới hạn về kích thước, nó 
chỉ phụ thuộc vào giới hạn của bộ nhớ toàn phần (chỉ khi danh sách chỗ trống đã 
cạn hết ) 
 Đối với queue thì loại bỏ ở một đầu bổ sung lại ở đầu khác. Nếu coi danh sách 
nối đơn như một queue và coi L trỏ tới lối trước thì việc loại bỏ một nút sẽ không 
khác gì với stack, nhưng bổ sung một nút thì phải thực hiện vào "đuôi " nghĩa là 
phải lần tìm đến nút cuối cùng. Nếu tổ chức queue móc nối có dạng như danh 
sách nối kép có 2 con trỏ L và R như đã nói ở trên, thì sẽ không phải tìm đuôi 
nữa. Lúc đó coi lối trước được trỏ bởi L, còn lối sau được trỏ bởi R (hoặc ngược 
lại cũng được ) 
a. Giải thuật Push, Pop đối với Stack 
Procedure Push(S, x) 
{Giải thuật bổ sung phần tử x vào Stack S được cài đặt bằng danh sách nối đơn, 
nút đầu trỏ bởi S} 
1. {Tạo nút mới} 
p <= AVAIL; 
 info(p) := x; 
2. {Bổ sung vào đỉnh Stack} 
 if S = null then link(p) := null; 
 else link(p) := S; 
 S := p; 
3. Return; 
Procedure Pop(S) 
{Giải thuật loại bỏ phần tử ở đỉnh Stack S được cài đặt bằng danh sách nối đơn, 
nút đầu trỏ bởi S} 
1. {Stack rỗng} 
 if S = null then begin 
 write(„ Stack rong‟); 
 return; 
 end; 
 else begin 
 x := info(S); 
 p:= S; 
 S := link(S); 
 p =>Avail; 
Return x; 
end; 
b. Giải thuật Push, Pop đối với Queue 
Procedure Push(L, R, x) 
{Giải thuật bổ sung phần tử x vào queue được cài đặt bằng danh sách nối kép, 
nút cực trái và nút cực phải lần lượt được trỏ bởi L và R} 
1. {Tạo nút mới} 
p <= AVAIL; 
 info(p) := x; 
2. {Bổ sung} 
 if L = R = null then begin 
 L := R := p; 
 LPTR(L) := RPTR(R) := null; 
 end 
 else begin 
 LPTR(p) := R; 
 RPTR(R) := p; 
 R := p; 
 RPTR(R) := null; 
 end; 
3. Return; 
Procedure Pop(S) 
{Giải thuật loại bỏ phần tử ở đỉnh queue được cài đặt bằng danh sách nối kép, 
nút cực trái và nút cực phải lần lượt được trỏ bởi L và R} 
1. {Stack rỗng} 
 if L = R = null then begin 
 write(„ Queue rong‟); 
 return; 
 end; 
 else begin 
 p := L; 
 L := RPTR(L); 
 LPTR(L) := null; 
 x := info(p); 
 p => AVAIL; 
Return x; 
end; 
 5.6. CẤU TRÖC ĐA DANH SÁCH 
Một cách tổng quát thì đa danh sách là một cấu trúc bao gồm nhiều nút mà 
mỗi nút có nhiều mối nối và có thể là phần tử đồng thời của nhiều danh sách. Tất 
nhiên đối với nút như vậy thì vấn đề khá quan trọng là phải phân biệt được các 
mối nối để lần vào từng danh sách cần thiết mà không nhầm vào danh sách khác. 
ở đây ta chỉ xét ứng dụng của đa danh sách trong phạm vi hẹp đó là dùng để biểu 
diễn ma trận thưa. 
5.6.1. Biểu diễn ma trận thƣa 
 Như chúng ta đã biết, với ma trận thưa nếu ta lưu trữ kế tiếp như ma trận 
thông thường thì rất lãng phí bộ nhớ, để tiết kiệm bộ nhớ ta có thể tổ chức lưu trữ 
theo cấu trúc đa danh sách. Theo cấu trúc này, mỗi nút trong danh sách, ứng với 
một phần tử khác không của ma trận và có qui cách. 
Trường LEFT: chứa con trỏ, trỏ tới nút tiếp theo (nút có chỉ số cột nhỏ hơn) 
trong danh sách nối vòng ứng với hàng (mà ta gọi là danh sách hàng). 
Trường UP: chứa con trỏ, trỏ tới nút tiếp theo (nút có chỉ số hàng nhỏ hơn) 
trong danh sách nối vòng ứng với cột (mà ta gọi là danh sách cột). 
Trường V: ghi giá trị khác không của phần tử 
 R: ghi chỉ số hàng của phần tử 
 C: ghi chỉ số cột của phần tử. 
Ví dụ, với ma trận: 
80007
65000
00032
46000
thì đa danh sách biểu diễn nó có dạng: 
LEFT
UP 
V C R 
5.6.2. Một số giải thuật 
3) TẠO LẬP MỘT ĐA DANH SÁCH BIỂU DIỄN MA TRẬN 
THƢA 
Procedure Create(A) 
{Thủ tục tạo đa danh sách biểu diễn ma trận thưa A gồm m hàng, n cột, với k 
phần tử khác không đã biết} 
1. {Khởi tạo danh sách hàng, danh sách cột} 
for i :=1 to m do begin 
 AROW[i] <= AVAIL; 
 C(AROW[i]) := 0; 
LEFT(AROW[i]) := AROW[i]; 
 end; 
for i :=1 to n do begin 
 ACOL[i] <= AVAIL; 
 R(ACOL[i]) := 0; 
UP(ACOL[i]) := ACOL[i]; 
 end; 
2. {Tạo các danh sách} 
for i := 1 to k do begin 
3. {Nhập các phần tử khác không} 
read(VALUE, ROW, COL); 
4. {Khởi tạo nút mới} 
0 0 0 0 0 
0 
0 
0 
0 
4 1 6 5 1 4 
1 2 2 2 2 3 
4 3 5 
1 4 7 5 4 8 
5 3 6 
P <= AVAIL; 
V(P) := VALUE; 
R(P) := ROW; 
C(P) := COL; 
5. {Định vị trong danh sách hàng cho nút mới} 
Q := AROW[R(P)]; 
while C(P) < C(LEFT(Q)) do Q := LEFT(Q); 
LEFT(P) := LEFT(Q); 
LEFT(Q) := P; 
6. {Định vị trong danh sách cột cho nút mới} 
Q := ACOL[C(P)]; 
while R(P) < R(UP(Q)) do Q := UP(Q); 
UP(P) := UP(Q); 
UP(Q) := P; 
 end; 
7. return; 
4) BỔ SUNG NÖT MỚI VÀO ĐA DANH SÁCH 
Procedure Insert(A, VALUE, ROW, COL) 
{Thủ tục bổ sung vào hàng ROW, cột COL của ma trận thưa A phần tử có giá 
trị VALUE} 
1. {Khởi tạo nút mới} 
P <= AVAIL; 
V(P) := VALUE; 
R(P) := ROW; 
C(P) := COL; 
2. {Định vị trong danh sách hàng cho nút mới} 
Q := AROW[R(P)]; 
while C(P) < C(LEFT(Q)) do Q := LEFT(Q); 
LEFT(P) := LEFT(Q); 
LEFT(Q) := P; 
3. {Định vị trong danh sách cột cho nút mới} 
Q := ACOL[C(P)]; 
while R(P) < R(UP(Q)) do Q := UP(Q); 
UP(P) := UP(Q); 
UP(Q) := P; 
 end; 
4. return; 
5) CỘNG HAI MA TRẬN 
Procedure Add(A, B, C) 
{Thủ tục tạo đa danh sách biểu diễn ma trận thưa C gồm m hàng, n cột là tích 
của hai ma trận thưa A, B kích thước mxn} 
1. {Khởi tạo danh sách hàng, danh sách cột của C} 
for i :=1 to m do begin 
 CROW[i] <= AVAIL; 
 C(CROW[i]) := 0; 
LEFT(CROW[i]) := CROW[i]; 
 end; 
for i :=1 to n do begin 
 CCOL[i] <= AVAIL; 
 R(CCOL[i]) := 0; 
UP(CCOL[i]) := CCOL[i]; 
 end; 
2. {Thực hiện với m hàng của ma hai ma trận A và B} 
for i := 1 to m do begin 
 A := LEFT(AROW[i]); 
 B := LEFT(BROW[i]); 
while C(B) ≠ 0 and C(A) ≠ 0 do 
if C(A) > C(B) then begin 
Call Insert(C, V(A), i, C(A)); 
A := LEFT(A); 
end; 
else if C(A) < R(B) then begin 
Call Insert(C, V(B), i, C(B)); 
B :=LEFT(B); 
 end; 
 else Begin 
if V(A)+V(B) ≠ 0 then Call Insert(C, V(A)+V(B), i, C(A)); 
 A := LEFT(A); 
 B := LEFT(B); 
 end; 
if C(B) = 0 then 
while C(A) ≠ 0 do begin 
 Call Insert(C, V(A), i, C(A); 
 A := LEFT(A); 
 end; 
else 
while C(B) ≠ 0 do begin 
 Call Insert(C, V(B), i, C(B); 
 B := LEFT(B); 
 end; 
 end; 
3. return; 
6) NHÂN HAI MA TRẬN 
Procedure Multi(A, B, C); 
{Thủ tục tạo đa danh sách biểu diễn ma trận thưa C gồm m hàng, t cột là tích 
của hai ma trận thưa A kích thước mxn, ma trận B kích thước nxt} 
1. hởi tạo danh sách hàng, danh sách cột của C} 
for i :=1 to m do begin 
 CROW[i] <= AVAIL; 
 C(CROW[i]) := 0; 
LEFT(CROW[i]) := CROW[i]; 
 end; 
for i :=1 to t do begin 
 CCOL[i] <= AVAIL; 
 R(CCOL[i]) := 0; 
UP(CCOL[i]) := CCOL[i]; 
 end; 
2. {Thực hiện với m hàng của ma trận A} 
for i := 1 to m do 
3. {Thực hiện với t cột của ma trận B} 
for j := 1 to t do begin 
 A := LEFT(AROW[i]); 
 B := UP(BCOL[j]); 
 RESULT := 0; 
4. {Xác định các phần tử tương ứng và thực hiện phép nhân} 
while R(B) ≠ 0 and C(A) ≠ 0 do 
if C(A) > R(B) then A := LEFT(A) 
else if C(A) < R(B) then B :=UP(B); 
 else Begin 
 RESULT := RESULT + V(A)*V(B); 
 A := LEFT(A); 
 B := UP(B); 
 end; 
 end; 
5. return; 
5.7. DANH SÁCH TỔNG QUÁT 
5.7.1. Định nghĩa 
 Danh sách tổng quát A là một dãy hữu hạn của N ≥ 0 phần tử a1, a2, .., an trong 
đó ai hoặc là một nút (mà ta gọi là nguyên tử(atom)) hoặc là một danh sách (mà 
ta gọi là danh sách con(sublist)). 
 Danh sách tổng quát A được ký hiệu bởi A = (a1, a2, .., an ), n được coi là độ 
dài của danh sách. Nếu n ≥ 1 thì a1 gọi là đầu của A, (a2, a3, .., an ) gọi là đuôi của 
A. 
Ví dụ: A = (a, (b, c), d, (e, f, g, h)) là một danh sách tổng quát gồm 4 phần tử 
trong đó: a và d là nguyên tử và (b, c), (e, f, g, h) là các danh sách con. 
 B = (y, (z, w), (x, (z, w), t)) 
 C = (a, C) 
5.7.2. Biểu diễn danh sách tổng quát 
 Có nhiều cách biểu diễn danh sách tổng quát, chẳng hạn: Mỗi nút có thể tổ 
chức gồm 3 trường: 
 Trường ATOM: trường dùng để phân biệt nút là nguyên tử hay nút ứng với 
danh sách con. Nếu ATOM = 1 thì nút ứng với nút nguyên tử, lúc đó DPTR là 
con trỏ trỏ tới nơi lưu trữ thông tin của nguyên tử đó; ATOM = 0 nút ứng với 
danh sách con, lúc đó DPTR là con trỏ trỏ tới phần tử đầu tiên của danh sách con 
này. RPTR là con trỏ trỏ tới phần tử tiếp theo của danh sách tổng quát.Ví dụ: 
A = (a, (b, c), d, (e, f, g, h)) thì danh sách tổng quát tương ứng 
1 a 0 1 d 0 
1 b 1 c 
1 e 1 f 1 g 1 h 
ATOM DPTR RPTR 
B = (y, (z, w), (x, (z, w), t)) th× danh s¸ch tæng qu¸t t-¬ng øng 
Nếu ta đưa vào nút đầu danh sách với qui cách tương tự như các nút khác, 
nhưng ATOM thì bằng 0 và DPTR của nó thì bằng null. Nếu danh sách rỗng thì 
DPTR và RPTR đều bằng null. Khi đó danh sách B có dạng 
5.7.3. Một số giải thuật xử lý danh sách tổng quát 
1) Tạo danh sách 
Cho Input là một xâu ký tự ứng với dạng biểu diễn bằng dấu ngoặc của danh 
sách. Tạo danh sách tổng quát tương ứng với xâu Input đã cho, trả về con trỏ 
trỏ tới nút đầu danh sách đó. Xâu Input không chứa dấu cách, không có phần 
tử( danh sách) dùng chung và không xuất hiện chu trình. 
Function Create(Input) 
{Hàm tạo danh sách tổng quát, với xâu đầu vào Input, trong hàm có sử dụng: 
hàm Sub(Input, m, n ) là hàm trả về xâu con gồm n kí tự trong xâu Input bắt 
đầu từ kí tự thứ m; Stack với các giải thuật Push, Pop} 
1. {Tạo nút đầu danh sách} 
if Sub(Input,1,1) = „(„ then 
 Begin 
1 y 0 0 
1 z 1 w 
1 x 0 1 t 
1 y 0 0 
1 z 1 w 
1 x 0 1 t 
0 
0 
0 
 P <= AVAIL; 
 RPTR(P) := DPTR(P) := null; 
Atom(P) := 0; 
call Push(S, Top, P); 
 end; 
 else begin 
 write(„Không đúng qui cách‟); 
 return(null); 
 end; 
2. {Lặp cho tới khi toàn bộ xâu Input đã được xử lý} 
m :=1; 
while m < length(Input) do 
 begin 
 m := m+1; 
 case 
Sub(Input,m,1) = „(„ : Q <= AVAIL; 
 RPTR(Q) := null; 
Atom(Q) := 0; 
RPTR(P) := Q; 
call Push(S,Top,Q); 
P <= AVAIL; 
Atom(P) := 0; 
RPTR(P) := null; 
DPTR(Q) := P; 
 Sub(Input, m, 1) = „,‟: {Không làm gì} 
Sub(Input, m, 1) = „)‟ : P := Pop(S, Top); 
Sub(Input, m, 1) = „A‟ to „Z‟: 
Q <= AVAIL; 
RPTR(Q) := null; 
Atom(Q) := 1; 
DPTR(Q) := Sub(Input, m , 1); 
RPTR(P) := Q; 
P := Q; 
else begin 
write(„ Ký tự không hợp lệ‟); 
return null; 
end; 
end case; 
end; 
3. P := Pop(S, Top); 
4. return P; 
2) Dựng một danh sách tổng quát từ hai danh sách tổng quát 
Procedure Combine(A, B, C) 
{A, B là hai danh sách tổng quát, giải thuật thực hiện việc ghép A trở thành 
đầu, B trở thành đuôi của danh sách C} 
1. {Kiểm tra tính hợp lệ của hai danh sách A và B} 
if A = null or B = null then begin 
 write(„Qui cach danh sach khong hop le‟); 
 C := null; return; 
 end; 
2. if DPTR(B) ≠ null then 
begin 
 write(„Khong dung qui cach‟) 
 C := null; return; 
end; 
3. {Ghép} 
if Atom(A) = 1 then 
 begin 
 P := RPTR(B); 
RPTR(B) := A; 
RPTR(A) := P; 
C := B; 
 end 
 else 
 begin 
Q <= AVAIL; 
Atom(Q) := 0; 
P := RPTR(B); 
RPTR(B) := Q; 
RPTR(Q) := P; 
DPTR(Q) := A; 
C := B; 
end; 
4. return; 
3) Đếm số lƣợng nguyên tử trong danh sách 
a. Giải thuật đệ quy 
 Procedure Count(A, count) 
 { Giải thuật đệ quy đếm số lượng nguyên tử trong danh sách tổng quát có nút 
đầu trỏ bởi A, kết quả đếm lưu tại biến count} 
 1. while A ≠ null do 
 begin 
 if Atom(A) =1 then count := count +1; 
 else if DPTR(A) ≠ null then call Cout(DPTR(A), count); 
 A := RPTR(A); 
 end; 
2. return; 
b. Giải thuật không đệ quy 
 Procedure Count(A, count) 
 { Giải thuật không đệ quy đếm số lượng nguyên tử trong danh sách tổng quát 
có nút đầu trỏ bởi A, kết quả đếm lưu tại biến count} 
1. call Push(A, Top, A); 
2. while Top > 0 do 
 begin 
 P := RPTR(Pop(S, Top)); 
 while P ≠ null do 
 begin 
 case 
 Atom(P) = 1: count := count +1; 
 DPTR(P) = null: P := RPTR(P); 
 DPTR(P) ≠ null: begin 
call Push(S, Top, P); 
P := DPTR(P); 
 end; 
 end case; 
 end; 
 end; 
3. return; 
5.8. BÀI TẬP 
1. Cho danh sách nối đơn nút đầu danh sách được trỏ bởi L biểu diễn đa thức 
một biến, cho biết nguyên tắc tổ chức danh sách trên và viết các giải thuật thực 
hiện các công việc sau: 
a) Nhập một đa thức từ bàn phím 
b) Hiển thị đa thức ra màn hình 
c) Tính giá trị đa thức 
d) Bổ sung một số hạng vào đa thức 
e) Tình đạo hàm bậc nhất của đa thức 
f) Tìm nguyên hàm của đa thức 
g) Tính tổng hai đa thức 
h) Tính hiệu hai đa thức 
i) Tính tích của đa thức với một số 
j) Tính tích hai đa thức 
2. Cho danh sách nối đơn, nút đầu danh sách được trỏ bởi L biểu diễn một tập 
hợp hữu hạn. Viết các giải thuật thực hiện các phép toán sau: 
a) Kiểm tra phần tử x có thuộc danh sách không 
b) Tìm hợp của hai tập hợp 
c) Tìm hiệu hai tập hợp 
d) Tìm giao của hai tập hợp 
3. Lập các giải thuật thực hiện các phép sau đối với danh sách nối đơn có nút đầu 
được trỏ bởi L. 
a) Tính số lượng các nút của danh sách 
b) Tìm tới nút thứ k trong danh sách, nếu có nút thứ k thì cho ra địa chỉ của nút 
đó, nếu không có thì cho ra địa chỉ null 
c) Bổ sung một nút vào trước nút thứ k 
d) Xoá bỏ nút đứng sau nút thứ k 
e) Cho M là một con trỏ trỏ vào một nút có trong danh sách, chèn vào sau nút M 
một danh sách nối đơn có nút đầu trỏ bởi P 
f) Cho Q là một con trỏ trỏ vào một nút có trong danh sách, tách danh sách thành 
hai danh sách mà danh sách thứ hai có nút đầu trỏ bởi Q. 
4. Cho L, R lần lượt là các con trỏ trỏ vào nút cực trái và nút cực phải của một 
danh sách nối kép mà mỗi nút biểu diễn một số nguyên trong một dãy các số 
nguyên khác nhau. Viết các giải thuật thực hiện các phép sau: 
a) Đếm số phần tử của dãy số 
b) Sắp xếp dãy số theo thứ tự tăng dần 
c) Bổ sung vào dãy số nguyên x( nếu x chưa có trong dãy), sao cho dãy vẫn đảm 
bảo tính sắp xếp. 
d) Loại bỏ số nguyên y (nếu có) 
5. Cho một đa danh sách biểu diễn ma trận thưa A, viết giải thuật tìm ma trận 
chuyển vị của A. 
6. Cho danh sách nối vòng, mỗi nút trong danh sách lưu trữ một số thực. Viết 
chương trình thanh lọc danh sách để tránh trường hợp các nút trong danh sách bị 
trùng nội dung. 
7. Cho n Hoàng tử xếp trên một vòng tròn và đánh số theo chiều kim đồng hồ, 
chọn ngẫu nhiên một bước đếm, xuất phát từ một Hoàng tử bất kỳ để bắt đầu 
đếm và loại đi hoàng tử 
5.9. Kiểm tra