Chương 11. Con trỏ vμ cấu trúc dữ liệu động
11.4. Danh sách liên kết
11.4.1. Khái niệm danh sách liên kết
Danh sách liên kết là một danh sách mà mỗi phần tử của nó đ−ợc lưu trữ một nơi trong bộ nhớ nhưng vẫn liên kết theo một thứ tự trước sau trong danh sách. Để tạo danh sách liên kết cần cấp phát động cho mỗi phần tử của nó. Ngoài các tr−ờng chứa dữ liệu thông th−ờng, mỗi phần tử của danh sách liên kết cần có thêm một trường chứa địa chỉ của phần tử liên kết. Các phần tử có dạng sau:
Mô hình khai báo các phần tử (còn đ−ợc gọi là nút hay node) của danh sách nh− sau:
Type
DataType = ... {kiểu dữ liệu}
PNode = ^Node;
Node = record
Data: DataType; lưu trữ dữ liệu}
Next: PNote; {trỏ đến nút kế tiếp}
Để quản lý danh sách, cần có một biến bên ngoài thuộc kiểu PNode, trỏ tới nút đầu tiên của danh sách:
Var
First: Pnode;
Dữ liệu Liên kết
Chương 11: Con trỏ vμ cấu trúc dữ liệu động 147
Để báo hết danh sách, tr−ờng Next của nút cuối cần trỏ vào NIL.
Từ First ta có thể truy cập danh sách bắt đầu từ phần tử đầu tiên, theo đúng thứ tự đã liên kết trong danh sách. Quy −ớc rằng nếu First = NIL thì có nghĩa là danh sách rỗng.
11.4.2. Tạo danh sách
Để tạo danh sách, đầu tiên khởi tạo danh sách rỗng, sau đó là quá
trình kết nạp lần l−ợt các nút vào danh sách. Thứ tự các nút trong danh sách phụ thuộc vào cách chọn vị trí kết nạp. Thông th−ờng có 2 cách chọn vị trí này: hoặc luôn thêm nút mới vào danh sách hoặc luôn thêm nút mới vào cuối danh sách.
Với cách thứ nhất, ta đ−ợc một danh sách mà thứ tự các nút ng−ợc với thứ tự kết nạp, danh sách này đ−ợc gọi là LIFO (Last In First Out- vμo sau ra tr−íc).
Với cách thứ hai, ta đ−ợc một danh sách mà thứ tự các nút trùng với thứ tự kết nạp, danh sách này đ−ợc gọi là FIFO (First In First Out- vμo tr−íc ra tr−íc).
Tạo danh sách LIFO
Cần chuẩn bị một biến con trỏ p có kiểu Pnode để cấp phát cho các nút. Mô hình LIFO nh− sau:
First: =NIL; {khởi tạo danh sách rỗng}
while {ch−a kÕt thóc} do begin
New(p); {xin cấp phát nút mới}
{ghi nhận dữ liệu cho tr−ờng p^.data}
...
F
Data Next
Data Next
Data Next
Nil
p^.next: = First {nối nút mới vào tr−ớc First}
First:= p; {ghi nhận lại First}
end;
Ví dụ: Nhập vào 1 danh sách nhân sự, sau đó đ−a kết quả ra màn hình.
Program vidu1;
uses crt;
Type
PointerN= ^Nhansu;
Nhansu = Record ten: string[30];
tuoi: integer;
next: PointerN; {De tro vao phan tu ben canh}
End;
Var
first,ptr, P, Q, tam: PointerN;
HeapTop: ^integer; {Con tro danh dau cua Mark}
m_ten: string[30];
n, i, j: integer;
Begin clrscr;
first:=nil; mark(heaptop);
repeat
write('Cho ten, an 0 thoat:'); readln(m_ten);
if m_ten<>'0' then begin
new(ptr);
ptr^.ten:= m_ten;
write('Tuoi:'); readln(ptr^.tuoi);
ptr^.next:= first; {noi nut moi vao truoc first}
first:= ptr; {Ghi nhan lai first}
end
Chương 11: Con trỏ vμ cấu trúc dữ liệu động 149
until m_ten ='0';
Ptr:=first; {ptr tro vao nguoicuoi}
while ptr<>nil do begin
write(ptr^.ten,' ');
write(ptr^.tuoi);
writeln;
ptr:=ptr^.next {*ptr tro vao nguoi ben canh*}
end;
Release(heaptop);
readln;
end.
11.4.3. Ví dụ sử dụng danh sách liên kết
Ví dụ: Nhập vào danh sách cán bộ (gồm 2 tr−ờng Họ tên và tuổi) theo kiểu LIFO, sắp xếp theo tuổi giảm dần hoặc tăng dần, đ−a kết quả
ra màn hình.
Program vidu;
Uses crt;
Type
PointerN= ^Nhansu;
Nhansu = Record ten: string[30];
tuoi:integer;
next:
PointerN; {De tro vao phan tu ben canh}
End;
Var
first,ptr,min,P,Q,tam: PointerN;
HeapTop: ^integer; {Con tro danh dau cua Mark}
m_ten: string[30];
n, i, j: integer;
Begin clrscr;
first:=nil; mark(heaptop);
repeat
write('Cho ten= ,(an 0 thoat)'); readln(m_ten);
if m_ten<>'0' then begin
new(ptr);
ptr^.ten:= m_ten;
write('Tuoi:'); readln(ptr^.tuoi);
ptr^.next:= first; {noi nut moi vao truoc first}
first:= ptr; {Ghi nhan lai first}
end
until m_ten ='0';
writeln('Danh sach sau khi nhap la');
Ptr:=first; {ptr tro vao nguoicuoi}
while ptr<>nil do begin
write(ptr^.ten,' ');
write(ptr^.tuoi);
writeln;
ptr:=ptr^.next {*ptr tro vao nguoi ben canh*}
end;
{sap xep danh sach}
ptr:=first; {Khoi dong nut dau tien}
while ptr<> nil do begin
q:=ptr^.next;
min:=ptr;
while (q<>nil) do begin
if(q^.tuoi>min^.tuoi) then
Chương 11: Con trỏ vμ cấu trúc dữ liệu động 151
min:= q;
q:=q^.next;
end;{vong while trong}
tam^.tuoi:= min^.tuoi;
min^.tuoi:=ptr^.tuoi;
ptr^.tuoi:=tam^.tuoi;
ptr:=ptr^.next;
end;
writeln('Danh sach sau khi sap xep');
Ptr:=first; {ptr tro vao nguoicuoi}
while ptr<>nil do begin
write(ptr^.ten,' ');
write(ptr^.tuoi);
writeln;
ptr:=ptr^.next {*ptr tro vao nguoi ben canh*}
end;
Release(heaptop);
readln;
end.
Bài tập chương 11
Bμi 1: Viết chương trình trong đó khai báo kiểu Mat, lưu các ma trận vuông, có các phần tử là các số thực, cấp không quá 100:
Type
Mat = aray[1..100, 1..100] of real;
Sau đó dùng 3 biến A, B, C để thực hiện phép nhân ma trận C = A*B. Chương trình nhập cấp của ma trận từ bàn phím sau đó sinh ngẫu nhiên các ma trận A, B. Sau khi thực hiện phép nhân, các ma trận A, B và C đều đ−ợc đ−a ra màn hình.
Bμi 2: Viết ch−ơng trình nhập vào một giá trị nguyên d−ơng n từ bàn phím, sau đó nạp các số nguyên bắt đầu từ 1, 2,... cho đến n vào hai danh sách (mỗi nút của danh sách chứa một số nguyên): danh sách LIFO và danh sách FIFO. Duyệt các danh sách đã tạo và in các số trong danh sách ra màn hình để thấy rằng thứ tự các số đ−ợc in trong danh sách LIFO ng−ợc với thứ tự đã nạp chúng, còn các thứ tự các số
đ−ợc in trong danh sách FIFO trùng với thứ tự đã nạp chúng.
Bμi 3: Một danh mục các số điện thoại đ−ợc cất trong file văn bản, mỗi dòng ghi thông tin của một số điện thoại bao gồm 25 cột đầu ghi họ tên, 35 cột tiếp theo ghi địa chỉ và 7 cột sau cùng ghi số điện thoại t−ơng ứng.
Viết chương trình đọc file đã cho và lưu danh mục điện thoại vào một danh sách FIFO có mỗi nút chứa thông tin của một số điện thoại, sau đó chương trình thực hiện qua giao diện menu các chức năng sau:
1. Hiển thị danh mục điện thoại lên màn hình
Chương 11: Con trỏ vμ cấu trúc dữ liệu động 153
2. Vào từ bàn phím một số điện thoại, hiển thị lên màn hình họ tên, địa chỉ tương ứng nếu tìm thấy.
3. Thêm một số điện thoại vào cuối danh mục. Thông tin của số
điện thoại đ−ợc thêm nhập từ bàn phím.
4. Xóa một số điện thoại ra khỏi danh mục. Số điện thoại cần xóa nhập từ bàn phím.
5. Kết thúc ch−ơng trình
Chương 12
TIN HỌC ỨNG DỤNG TRONG TÍNH TOÁN