Giáo trình Bài tập Pascal - Chương 9: Dữ liệu kiểu con trỏ

il do
begin 
with p do 
if tuoi <= n then 
writeln(mabn, #32,hoten, #32, tuoi); 
p:= p^.tiep; 
end; 
End; 
e. Procedure XoaBN(Var First: TroBN; Bma: St5) xoá bệnh nhân có mã Bma khỏi 
danh sách. 
Procedure XoaBN(Var First: TroBN; Bma: St5); 
Var 
p,q: TroBN; 
Beginp:= first;while (p nil) and (p^.MaBN Bma) do
beginq:= p;p:= p^.tiep;
end; 
if p nil then 
begin 
if p = first then 
first:= first^.tiep 
else 
q^.tiep:= p^.tiep; 
dispose(p); 
End; 
106 
Giáo trình bài tập Pascal 
Bài tập 9.8: Người ta lưu thông tin của mỗi đại lý trong công ty bởi một nút trong danh 
sách liên kết đơn và được khai báo như sau: 
Type St6 = String[6]; TroDL = ^ DaiLy; DaiLy = Record 
SoDT: St6; 
DoanhThu: LongInt; 
Next: TroDL; 
End; 
Viết các thủ tục và hàm: 
a. Procedure BoSung(Var First: TroDL; Tel: St6; m: LongInt) để bổ sung một đại 
lý có số điện thoại Tel và doanh thu là m vào đầu danh sách có nút đầu trỏ bởi 
First. 
Procedure BoSung(Var First: TroDL; Tel: St6; m: LongInt); 
Var 
p: TroDL; 
Beginnew(p);p^.SoDt:= Tel;p^.Doanhthu:= m;p^.next:= first;first:= p;
End; 
b. Function DThu(First: TroDL; Tel: St6): LongInt trả về doanh thu của đại lý có 
số điện thoại là Tel, nếu không có đại lý đó thì hàm trả về giá trị 0. 
Function DThu(First: TroDL; Tel: St6): LongInt; 
Var 
p: TroDL; 
Beginp:= first;while (p nil) and (p^.SoDT Tel) do
p:= p^.next; 
if p nil then 
Dthu:= p^.doanhthu 
else 
Dthu:= 0; 
End; 
c. Function TongDThu(First: TroDL): Real trả về tổng doanh thu của tất cả các đại 
lý trong công ty. 
Function TongDThu(First: TroDL): Real; 
Var 
107 
Giáo trình bài tập Pascal 
p: TroDl; 
T: real; 
Begin 
T:= 0; 
p:= first; 
while p nil do 
beginT:= T+ p^.Doanhthu;p:= p^.next;
end; 
TongDthu:= T; 
End; 
d. Function DemDL(First: TroDL; m: LongInt): Word trả về số đại lý của công ty 
có doanh thu lớn hơn m. 
Function DemDL(First: TroDL; m: LongInt): Word; 
Var 
p: TroDL; 
dem: word; 
Begin 
dem:= 0; 
p:= first; 
while p nil do 
begin 
if p^.Doanhthu > m then 
inc(dem); 
p:= p^.next; 
end; 
DemDL:= dem; 
End; 
e. Procedure XoaDL(Var First: TroDL; Tel: St6) xóa đại lý có số điện thoại Tel ra 
khỏi danh sách. 
Procedure XoaDL(Var First: TroDL; Tel: St6); 
Var 
p,q: TroDL; 
Beginp:= first;while (p nil) and (p^.SoDT Tel) do
beginq:= p;p:= p^.next;
end; 
if p nil then 
108 
Giáo trình bài tập Pascal 
begin 
if p = first then 
first:= first^.next 
else 
q^.next:= p^.next; 
dispose(p); 
end; 
End; 
BÀI TẬP TỰ GIẢI 
Bài tập 9.9: Viết một hàm để xác định xem một danh sách liên kết đã cho có thứ tự 
tăng dần hay không theo 2 cách: Không đệ qui và đệ qui. 
Bài tập 9.10: Cho 2 danh sách liên kết đơn đại diện cho 2 tập hợp được trỏ bởi L1 và 
L2. Viết chương trình để hiển thị:1. Phần giao của 2 danh sách trên.2. Phần hợp của 2 danh sách trên.3. Phần hiệu của 2 danh sách trên.
Bài tập 9.11: Cho 2 danh sách liên kết L1 và L2.1. Sắp xếp lại 2 danh sách đó theo thứ tự tăng dần.2. Trộn 2 danh sách đó lại thành danh sách L3 sao cho L3 vẫn có thứ tự tăng dần.
Bài tập 9.12: Dùng danh sách móc nối để biểu diễn một đa thức Pn(x) = anxn + an-1xn-1 +...+ a0. Trong đó, mỗi số hạng của đa thức được xác định bởi 2 thành phần: hệ số ai và số mũ i. 
Như vậy, ta có thể xây dựng cấu trúc dữ liệu cho đa thức như sau: 
TYPE DATHUC = ^SOHANG; 
SOHANG = RecordHeSo: Real;SoMu: Integer;Next: DATHUC;
End; 
Viết chương trình thực hiện các công việc sau:1. Viết thủ tục nhập vào một đa thức.2. Viết thủ tục để sắp xếp lại các số hạng của đa thức theo thứ tự số mũ giảm dần.3. Viết thủ tục/hàm để cộng 2 đa thức.4. Viết hàm để tính giá trị của đa thức theo giá trị X.
Bài tập 9.13: Cho một file văn bản trong đó có chứa các từ. Các dấu phân cách từ là: ký tự trắng, dấu chấm, dấu phẩy, dấu chấm phẩy, dấu hai chấm, dấu than, dấu hỏi. Mọi từ đều bắt đầu bằng một ký tự trong tập ['A'..'Z']. 
1. Viết thủ tục cho phép đọc các từ trong file văn bản đã cho và lưu các từ đó vào 
mảng các danh sách móc nối: 
TuDien : ARRAY['A'..'Z'] OF DanhSach; 
109 
Giáo trình bài tập Pascal 
Trong đó kiểu DanhSach được cho như sau: 
TYPE DanhSach = RECORDTu : String[10];Next : DanhSach;
END; 
Mỗi danh sách móc nối trong từ điển đều phải được sắp thứ tự (tăng dần), và các từ 
được lưu trong từ điển phải khác nhau. 
2. Viết một thủ tục hiển thị tất cả các từ trong từ điển ra màn hình theo thứ tự tăng dần. 3. Viết một thủ tục bổ sung một từ mới vào từ điển bằng cách đọc từ đó từ bàn phím, tìm nó trong từ điển. 
- Nếu tìm thấy, hiển thị thông báo:"Từ đã có trong từ điển". 
- Nếu không tìm thấy, chèn từ đó vào trong từ điển ở vị trí thích hợp. 
Bài tập 9.14: Cho dãy số nguyên sắp theo thứ tự tăng dần và lưu trong một danh sách 
liên kết đơn có địa chỉ nút đầu danh sách là First. 
a.Viết chương trình xoá tất cả các nút trong danh sách có giá trị 0. 
b.Viết chương trình in ra các giá trị phân biệt của danh sách. 
Bài tập 9.15: Cho hai dãy số thực lưu trong hai danh sách liên kết đơn, có địa chỉ của các nút đầu danh sách lần lượt là First1 và First2. Giả sử trong mỗi danh sách giá trị các nút đã được sắp tăng dần. Hãy viết chương trình tạo một danh sách liên kết đơn có nút đầu trỏ bởi List, chứa tất cả các phần tử của hai danh sách trên, danh sách mới này cũng được sắp thứ tự. 
Bài tập 9.16: Một công ty du lịch quản lý tất cả các xe ô tô của họ bằng một danh sách 
liên kết, mỗi nút của danh sách được khai báo như sau: 
Type 
TroXe = ^Xe; 
St6 = String[6]; 
St20 = String[20]; 
Xe = RecordTaiXe: St20; { họ tên tài xế }BienSo: St6; { biển số xe }Socho: Byte; { số chỗ ngồi }
Tiep: TroXe; 
end; 
VarFirst: TroXe; 
a.Viết thủ tục Procedure Print(First: TroXe; n:byte); in họ tên tài xế, biển số 
xe của tất cả các xe có n chỗ ngồi được lưu trong danh sách. 
b.Viết hàm Function SoChoNgoi(First: TroXe; Bso: St6); trả về số chỗ của xe 
có biển số Bso. 
Bài tập 9.17: Người ta quản lý các sách trong thư viện bằng một danh sách liên kết, sắp theo thứ tự của mã sách. Mỗi đầu sách tương ứng với một nút trong danh sách có khai báo như sau: 
110 
Giáo trình bài tập Pascal 
Type 
TroSach = ^Sach;St4 = String[4];St20 = String[20];Sach = Record
Ma: St4; 
Ten, Tacgia: St20; 
NamXb: word; Soluong: Byte; Next: TroSach; 
end; 
VarFirst: TroSach; 
Chú ý: Các đầu sách được săp theo thứ tự mã sách. 
a.Viết thủ tục Procedure CapNhat(Var First: TroSach; Bma:St4; Bten, BTgia: 
St20; Bnam: word; n: byte); bổ sung vào thư viện đầu sách có mã là Bma, tên sách Bten, tác giả BTgia và số lượng bổ sung là n theo yêu cầu: Nếu đầu sách có mã là Bma đã có trong thư viện thì chỉ tăng số lượng lên n, ngược lại thêm một đầu sách mới vào thư viện với số lượng n và bảo toàn thứ tự của mã sách. 
b.Viết thủ tục Procedure LietKeNam(First: TroSach; Nam: word) in danh sách 
các đầu sách xuất bản vào năm Nam. 
c.Viết hàm Function So_Dau_Sach(First: TroSach; BTgia: St20) trả về số đầu 
sách của tác giả BTgia. 
d.Viết thủ tục Procedure LietKeten(First: TroSach; Bten: St20) in danh sách 
tất cả các đầu sách có tên sách là Bten. 
Bài tập 9.18: Một cửa hàng kinh doanh vật liệu xây dựng quản lý lượng hàng tồn kho bằng một danh sách liên kết. Mỗi loại vật liệu tương ứng với một nút trong danh sách và có khai báo như sau: 
Type 
St3 = String[3]; 
St10 = String[10]; 
TroVT = ^Vattu; 
Vattu = RecordMa: St3;Ten: St10;DVTinh: St10; { đơn vị tính}Soluong: word;
Tiep: TroVattu; 
End; 
VarFirst: TroVattu; 
111 
Giáo trình bài tập Pascal 
a.Viết thủ tục Procedure XuatKho(Var First: TroVattu; Bma: St3; Bdonvi: 
St10; n: word); lấy ra khỏi kho n bdonvi loại vật tư có mã là Bma theo yêu 
cầu sau: 
•Nếu vật tư có mã Bma không có trong kho thì thông báo kho không có 
loại vât tư này và kết thúc thực hiện. 
•Ngược lại, kiểm tra Bdonvi có trùng với DVTinh của loại vật tư này 
không, nếu không trùng thì yêu cầu đổi theo đơn vị tính lưu trong danh 
sách trước khi thực hiện xuất kho. 
•Nếu số lượng trong kho của vật tư có mã Bma nhỏ hơn n thì đưa ra 
thông báo và hỏi lại có muốn xuất không, nếu muốn thì xuất với số 
lượng bao nhiêu? 
•Sau khi xuất n đơn vị loại vật tư theo yêu cầu, giảm số lượng vật tư trong 
kho cho phù hợp và nếu số lượng của vật tư này bằng 0 thì xoá nó ra 
khỏi danh sách. 
b.Viết thủ tục Procedure NhapKho(Var First: TroVattu; Bma: St3; Bten, Bdv: 
St10; n: word); nhập vào kho n Bdv laọi vật tư có mã Bma theo yêu cầu: 
•Nếu loại vật tư có mã Bma đã có trong kho thì chỉ tăng số lượng vật tư 
này trong kho, nhớ kiểm tra đơn vị tính như câu a. 
•Ngược lại, bổ sung một loại vật tư mới vào kho với mã là Bma, tên vật 
tư là Bten, đơn vị tính là Bdv và số lương tương ứng là n. 
c.Viết hàm Function SoVattu(First: TroVattu; Bma:St3); trả về số lượng vật tư 
có mã là Bma còn tồn trong kho, nếu không có vật tư này, hàm trả về giá trị 
0. 
d.Viết thủ tục Procedure ThongKe(First: TroVattu); in ra thông tin của tất cả 
các loại vật tư hiện có trong kho. 
Bài tập 9.19: Cho danh sách các số nguyên được tổ chức như sau: 
Type TRO = ^PT; 
PT = RecordX: Integer;Link: TRO;
End; 
1. Viết thủ tục NHAP(Var Dau:TRO); để nhập vào một danh sách các số nguyên có 
nút đầu tiên được trỏ bởi con trỏ Dau. 
2. Viết thủ tụcLIETKE(Da u:TRO); để in ra màn hình giá trị của tất cả các nút trong 
danh sách được trỏ bởi con trỏ Dau. 
3. Giả sử Dau là con trỏ trỏ đến đầu của một danh sách chưa được sắp xếp, còn L được gán bằng NIL. Hãy viết thủ tục SAPCHON(Var Dau,L:TRO); cho phép chọn các phần tử trong danh sách Dau từ giá trị lớn đến bé, đưa vào danh sách L để cuối cùng Dau=Nil, còn L sẽ trở thành một danh sách đã được sắp xếp theo thứ tự tăng dần. 
4. Viết hàmTANG(Dau :TRO):Boolean; để xác định xem danh sách được trỏ bởi 
Dau đã có thứ tự tăng dần hay không theo 2 cách: Không đệ qui và đệ qui. 
5. Viết thủ tục DAO(Var Dau:TRO); để đảo ngược các con trỏ của danh sách Dau. 
Bài tập 9.20: Cho danh sách các số nguyên được tổ chức như sau: 
112