Ngôn ngữ lập trình Pascal - Phần 2

dụng mảng thì bao giờ cũng cho số phần tử cực đại có thể dùng tới để khai báo 
mảng và nếu ta dùng không hết thì gây ra lãng phí ô nhớ có thể đang thiếu cho việc khác. Nếu ta 
dùng biến động thì cần đến đâu sẽ tạo ra đến đó. Hoặc nhiều khi ô nhớ bị hạn chế, nên ta không 
104
thể đồng thời sử dụng nhiều biến tĩnh cùng một lúc. Do đó, một trong các biện pháp khắc phục là 
dùng biến con trỏ để xây dựng một danh sách các phần tử móc nối với nhau gọi là danh 
sách liên kết. 
10.3.1. Định nghĩa 
Danh sách liên kết là một danh sách mà các phần tử đ−ợc nối kết lại với nhau thông qua vùng 
liên kết của chúng. Một phần tử của danh sách liên kết bao gồm hai vùng chính: Một vùng chứa 
thông tin gọi là vùng Info, một vùng chứa địa chỉ gọi là vùng liên kết Link. Hình ảnh của một từ 
máy (hay còn gọi là nut) nh− sau: 
Info Link 
Ngoài các phần tử thuộc danh sách liên kết, ta còn dùng một biến chỉ điểm đầu First (kiểu 
Pointer) chứa địa chỉ của phần tử đầu tiên của danh sách liên kết. Tổ chức của danh sách liên kết 
nh− sau 
FIRST → | 
 ↓ 
 | 
 ↓ 
 | 
 ↓ 
 NIL
Ví dụ 5. Danh sách học viên có sắp xếp theo thứ tự tăng dần đ−ợc chứa trong một danh sách 
liên kết nh− sau: 
Vị trí Họ lót Tên Liên kết
0000 
0032 
0064 
0096 
0110 
Mai Thị Ph−ơng 
Nguyễn Châu 
Lê Thị 
Võ Thành 
Hà Hải 
Thảo 
Ph−ơng 
Lan 
Lộc 
Quân 
NIL 
0110 
0096 
0032 
0000 
1050064 
FIRST 
a. Loại bỏ một phần tử trong danh sách 
Để loại bỏ một phần tử trong danh sách ta chỉ cần thay đổi vùng liên kết của phần tử đứng 
ngay tr−ớc nó. 
Ví dụ 6. Muốn loại bỏ tên học viên Võ Thành Lộc, ta chỉ cần sửa vùng liên kết của Lê Thị 
Lan từ 0096 thành 0032 và các vùng liên kết của các phần tử còn lại vẫn giữ nguyên. Kết quả 
ta có danh sách liên kết mới nh− sau : 
Vị trí Họ lót Tên Liên kết
0000 
0032 
0064 
0110 
Mai Thị Ph−ơng 
Nguyễn Châu 
Lê Thị 
Hà Hải 
Thảo 
Ph−ơng 
Lan 
Quân 
NIL 
0110 
0032 
0000 
FIRST 
0064 
b. Thêm một phần tử mới vào danh sách 
Để thêm một phần tử mới vào danh sách, ta có thể chứa phần tử này ở một vùng bất kì trong 
bộ nhớ và cho vùng liên kết của phần tử đứng ngay sau nó. 
Ví dụ 7. Muốn thêm tên học viên Trần Phúc Quyền vào danh sách, ta sửa vùng liên kết của 
Hà Hải Quân từ 0000 thành 0200 và gán giá trị vùng liên kết của Trần Phúc Quyền là 0000. 
Ta có danh sách liên kết nh− sau : 
106
 Vị trí Họ lót Tên Liên kết 
0000 
0032 
0064 
0096 
0110 
0200 
Mai Thị Ph−ơng 
Nguyên Châu 
Lê Thị 
Võ Thành 
Hà Hải 
Trần Phúc 
Thảo 
Ph−ơng 
Lan 
Lộc 
Quân 
Quyền 
NIL 
0110 
0096 
0032 
0200 
0000 
FIRST 
0064 
Danh sách liên kết có −u điểm: Tốc độ thực hiện các phép toán thêm vào, loại bỏ phần tử 
nhanh chóng, không phụ thuộc vào số phần tử của danh sách. Nó phù hợp với loại danh sách có 
nhiều biến động. Nh−ợc điểm : Thêm vào một vùng biến liên kết (tốn thêm bộ nhớ). 
10.3.2. Các phép toán trên danh sách liên kết 
a. Khởi tạo danh sách liên kết 
Khi khởi tạo danh sách thì danh sách là rỗng, ta cho First là NIL. 
Giải thuật : 
First:=NIL; 
b. Thêm một phần tử vào danh sách liên kết 
Phần tử mới có địa chỉ là P với nội dung là Newinfor và danh sách sau của phần tử là q. 
Giải thuật : 
New(P) 
p^.info:=NewInfo; 
p^.Link:=q^.Link; {Tao 1} 
q^.Link:=p {Tao 2} 
c. Loại bỏ phần tử trong danh sách liên kết 
Loại bỏ phần tử có địa chỉ p ngay sau phần tử có địa chỉ q. 
Giải thuật : 
p:=q^.Link; 
If pNIL Then 
107
Begin 
q^.Link:=p^Link; 
Dispose(p) 
End. 
d. Tìm kiếm một phần tử trong danh sách 
Giả sử danh sách đ−ợc sắp xếp thứ tự tăng dần theo vùng Info. 
Ta tìm kiếm một phần tử có Info là X. 
Giải thuật : 
p:=First; 
While p NIL Do 
Begin 
If p^.Info = X Then {...} ; 
If p^.Info < X Then p=p^.Link ; 
If p^.Info > X Then {...} ; 
End; 
10.3.3. Ví dụ về các danh sách liên kết 
Ch−ơng trình sau đây thực hiện tổ chức danh sách sinh viên và thực hiện một số thao tác trên 
danh sách. Độc giả có thể tìm thấy các phép xử lí trên danh sách thông qua các thủ tục trong 
ch−ơng trình. 
User Crt; 
Type 
svPointer=^sinhvien; 
sinhvien = Record 
Maso :String[6]; 
Hoten : String[30]; 
dtb : real; 
Next : svPointer; 
End; 
108
Var 
First, Last, p, q: svPointer; 
Masv : String[6]; 
Chon1 : Byte ; 
Traloi : Char; 
Procedure Menu(Var cho : Byte); 
Begin 
Window(50,14,80,25): 
Writeln (‘ ’); 
Writeln (‘ Cac thao tac ’); 
Writeln (‘ 1. Tao danh sach sinh vien ’); 
Writeln (‘ 2. Duyet danh sach sinh vien ’); 
Writeln (‘ 3. Bo sung vao cuoi danh sach ’); 
Writeln (‘ 4. Loai bo ’); 
Writeln (‘ 5. Cham dut ’); 
Writeln (‘ **Chon so: ’); 
GotoXY(21,8); Readln(Chon); 
Clrscr; 
End; { Menu } 
(*------------------------------------------------------------------*) 
Procedure Taosd; 
Var 
Ptr : svPointer; 
i:Integer ; 
Begin 
First:=NIL; 
i:=1 ; 
Repeat 
Write(i:3,‘>Mã số SV(Enter : Kết thúc):’); 
109
Readln(masv); 
If masv ‘ ’ Then 
Begin 
new(ptr); 
Ptr^.maso:=masv; 
Write(‘Ho va ten:’ ); 
Readln(Ptr^.Hoten); 
Write(‘Diem trung binh:’); 
Readln(Ptr^.dtb); 
Ptr^.Next:=NIL; 
If First =NIL Then First:=Ptr 
Else Last^.Next:=Ptr; 
Last:=Ptr; 
i:=i+1; 
End; 
Until masv=‘ ’; 
End; { Taods } 
(*-----------------------------------------------------------*) 
Procedure DuyetDS; 
Var 
Ptr :svPointer; 
i: Integer; 
Begin 
Writeln(‘ DANH SACH SINH VIEN ’); 
Writeln(‘ ==============================’); 
Writeln(‘ STT Ma so Ho va ten DTB’); 
Writeln(‘ ==============================’); 
i:=1; 
Ptr :=First; 
While PtrNIL Do 
110
Begin 
Writeln(i:3,’ ‘,Ptr^.maso:5,’ ‘,Ptr^.hoten:25,’ ‘,Ptr^.dtb:5:2); 
Ptr:=Ptr^.Next; 
i:=i+1; 
End; 
End; { DuyetDS } 
(*---------------------------------------------------------------*) 
Procedure Themsv; 
Var 
Ptr:Pointer; 
Begin 
New(Ptr); 
Writeln(‘Nhap thong tin mot sinh vien moi’); 
Write(‘Mã số:’); Readln(Ptr^.maso); 
Write(‘Họ tên:’); Readln(Ptr^.hoten); 
Write(‘Điểm TB:’); Readln(Ptr^.dtb); 
Ptr^.Next:=NIL; Last^.Next:=Ptr; Last :=Ptr; 
End; { ThemSV } 
(*--------------------------------------------------------------*) 
Procedure XoaSV; 
Var 
Timco: Boolean; 
Begin 
Write(‘Ma so sinh vien can loai khoi danh sach:’); 
Readln(masv); 
p:=First; 
If p NIL Then 
Begin 
Timco:=False; 
While(pNIL) And Not Timco Do 
111
If p^.maso=masv Then Timco:=True 
Else 
Begin 
q:=p; 
p:=p^.Next; 
End; 
If Timco Then 
Begin 
If p=First Then First:=p^.Next 
Else q^.Next=p^.Next; 
If p^.Next=NIL Then Last :=q; 
Dispose(p); 
End; 
End; 
End; { Xoa SV } 
(*-----------------------------------------------------------*) 
Begin 
Clrscr; 
Writeln(‘ VI DU DANH SACH LIEN KET ‘); 
Writeln(‘ ==========================’); 
Repeat 
Menu(chon1); 
Case chon1 Of 
1: TaoDS; 
2: DuyetDS 
3: Begin 
Repeat 
Themsv ; 
Write(‘Co tiep tuc khong (C/K) ?:’); Readln(Traloi); 
Until Upcase(Traloi)=’K’; 
112
End; 
4: Begin 
Repeat 
XoaSV; 
Write(‘Co tiep tuc nua khong (C/K)? :’); Readln(Traloi); 
Until Upcase (Traloi)=‘K’; 
End; 
End; { Of Case } 
Until chon1 = 5; 
End. 
Câu hỏi – Bài tập Ch−ơng 10 
1. Sử dụng hàm Radomize (Hàm khởi tạo bộ nhớ ngẫu nhiên) và hàm Random (Hàm tạo một số 
ngẫu nhiên trên đoạn [0,1]) để tạo một mảng ngẫu nhiên gồm 10000 phần tử. 
2. Lập ch−ơng trình nhân hai ma trận A(m,n) và B(n,p) để đ−ợc ma trận tích C(m,p). Các mảng 
A,B,C đều khai báo d−ới dạng biến con trỏ. 
3. Viết ch−ơng trình tạo một danh sách liên kết chứa các số nguyên nhập vào từ bàn phím. Từ đó 
viết thuật toán : 
a) Đếm xem danh sách có bao nhiêu nút. 
b) Tính giá trị trung bình của các phần tử trong danh sách. 
c) Xác định nút cuối cùng của danh sách đó. 
d) Xác định nút có giá trị lớn nhất của danh sách đó. 
e) Xác định nút có giá trị âm đầu tiên của danh sách đó (nếu có). 
f) Chèn một số nguyên X vào sau nút thứ n trong danh sách. 
g) Xoá 1 phần tử n trong danh sách, n là số nguyên cho tr−ớc. 
4. Viết ch−ơng trình nhập vào một dãy số thực có số phần tử tuỳ ý và sắp xếp dãy số đó theo thứ 
tự tăng dần. 
5. Viết ch−ơng trình nhập vào một dãy số thực đã đ−ợc sắp xếp theo thứ tự tăng dần (số phần tử 
tuỳ ý) và một số thực X. Viết ch−ơng trình chèn số X vào danh sách sao cho dãy số mới cũng 
có thứ tự tăng dần. 
113
6. Viết ch−ơng trình nhập vào một danh sách các sinh viên (số sinh viên tuỳ ý), mỗi sinh viên có 2 
tr−ờng : họ tên, tuổi. In ra danh sách đó theo thứ tự ng−ợc lại. 
7. Hãy lập ch−ơng trình đọc vào hai dãy số và tổ chức chúng thành hai danh sách liên kết. Thực 
hiện các phép xử lí sau đây trên hai danh sách : 
a) Phần giao của 2 danh sách. 
b) Phần hợp của 2 danh sách. 
c) Hiệu của danh sách thứ nhất và danh sách thứ hai. 
Ghi chú : không cần phải tạo danh sách mới trong mỗi thuật toán. 
8. Viết ch−ơng trình cho phép nhập vào 2 dãy số tăng dần và l−u vào 2 danh sách liên kết, trộn 2 
danh sách trên bằng cách tạo ra một danh sách mới sao cho dãy số hợp thành cũng tăng dần. 
9. Viết ch−ơng trình tạo ra 2 danh sách liên kết (tuỳ ý) và nối 2 danh sách đó lại thành 1 danh 
sách. 
10. Viết ch−ơng trình nhập vào một dãy số và l−u trữ trong một danh sách liên kết sau đó xác 
định xem các phần tử danh sách có giá trị tăng dần hay không. 
11. Viết ch−ơng trình để biểu diễn một số nguyên lớn (Ví dụ : 1234567891234567) thành một 
danh sách tuyến tính động. 
12. Viết ch−ơng trình tính tổng của 2 số nguyên có độ lớn tuỳ ý. 
13. Dùng cấu trúc dữ liệu để thực hiện tính n! mà không dùng đệ quy. 
14. Một đa thức đã cho có thể đ−ợc biểu diễn d−ới dạng một danh sách tuyến tính động, trong đó 
mỗi nút của danh sách gồm 2 tr−ờng : 
* Tr−ờng chứa hệ số ai. 
* Tr−ờng chứa số mũ i (ai 0, ∀i). 
Hãy viết ch−ơng trình : 
a) Nhập vào 2 đa thức. 
b) Cộng 2 đa thức đó. 
c) Tính f(x) với x là 1 số cho tr−ớc. 
114
 Chịu trách nhiệm nội dung: 
Ts. Nguyễn văn hòa 
Biên tập: 
Tổ công nghệ thông tin 
Phòng khảo thí - đảm bảo chất l−ợng giáo dục 
Đơn vị phát hành: 
trung tâm đào tạo từ xa - đại học huế 
115