1. Danh sách liên kết đơn
Danh sách là một dãy hữu hạn các phần tử thuộc cùng một lớp đối
tượng nào đó. Ví dụ : danh sách sinh viên, danh sách vật tư, danh sách các hoá
đơn, danh sách các số thực. Trong các bài trước ta đã dùng
mảng để biểu thị một danh sách. Cách này có các nhược điểm: kích
thước của mảng phải định trước nên tốn bộ nhớ (số phần tử thực tế dùng
nhiều khi rất ít so với khai báo), khi thêm một phần tử vào mảng hoặc xoá một
phần tử ra khỏi mảng ta phải mất nhiều thời gian để dồn mảng.
Danh sách liên kết dùng để cài đặt một danh sách sẽ khắc phục được
các nhược điểm trên của mảng. Danh sách liên kết thuận gồm nhiều phần tử nằm
không liên tục trong Heap. Cấu tạo của danh sách liên kết thuận: có một con trỏ first chứa
địa chỉ của phần tử đầu tiên của danh sách, phần tử đầu có phần dữ liệu
và một con trỏ next để
chứa địa chỉ của phần tử thứ hai, tổng quát phần tử thứ i có phần dữ liệu và
một con trỏ next để chứa địa chỉ của phần tử thứ i+1, đối với phần tử cuối cùng
giá trị của con trỏ next bằng NIL. Để thuận tiện khi thêm phần tử mới vào cuối
danh sách liên kết ta dùng một con trỏ last chứa
địa chỉ của phần tử cuối cùng. Khởi tạo một danh sách rỗng first = NIL
Chương trình Dslk.pas minh hoạ các cách làm việc với danh sách
liên kết thuận. Phần dữ liệu của một phần tử là các thông tin về một sinh viên.
uses crt;
type SVienPtr = ^SVien;
SVien = record maso: string[6];
hoten: string[23];
dtb: real;
next : SVienPtr
end;
var first, last : SVienPtr; chon: byte; traloi: char;
procedure Bosung;
var p: SVienPtr; ans: integer;
begin
while true do
begin new(p);
with p^ do begin
write(‘Ma sinh vien : ‘); readln(maso);
write(‘Ho va ten : ‘); readln(Hoten);
write(‘Diem trung binh: ‘); readln(dtb);
end;
p^.next:=NIL;
if first=NIL then begin first:= p; last:= p end
else begin last^.next:= p; last:= p end;
write(‘Co tiep tuc khong 1/0 ? ‘); readln(ans);
if ans=0 then break;
end;
end;
procedure DuyetXuoi;
var p: SVienPtr;
begin if first = NIL then begin writeln(‘D.sach rong’); exit end;
p := first;
while p <> NIL do
begin with p^ do writeln(maso:5,’ ‘,Hoten:25,’ ‘,dtb:5:2);
p := p^.Next;
end;
end;
procedure ChenSau;
var q,p: SVienPtr; found: boolean; masv: string[6];
begin if first <> NIL then begin
write(‘Ma so SV can tim de chen : ‘); readln(masv);
p:= first; found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true else p:=p^.next;
if found then
begin new(q);
with q^ do begin
write(‘ Ma so : ‘); readln(maso);
write(‘ Ho ten : ‘); readln(Hoten);
write(‘ Diem trung binh : ‘); readln(dtb);
end;
q^.next:= p^.next; p^.next:= q;
end else begin write(‘Khong tim thay…’); readln end;
end;
end;
procedure TimXoa;
var masv: string[6]; found: boolean; p,q: SVienPtr;
begin write(‘Ma so SV can loai khoi danh sach : ‘); readln(masv);
p:= first;
if p<>NIL then begin found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true
else begin q:=p; p:=p^.next end;
if found then
begin if p=first then first :=p^.next else q^.next:=p^.next;
if p^.next=NIL then last:=q; dispose(p)
end else begin write(‘Khong tim thay…’); readln end;
end;
end;
Begin clrscr; First := NIL;
repeat
writeln; writeln(’1. Bo sung mot sinh vien’);
writeln(’2. Duyet danh sach sinh vien’);
writeln(’3. Tim kiem mot phan tu va chen vao sau’);
writeln(’4. Tim kiem mot phan tu va xoa’);
writeln(’5. Ket thuc chuong trinh’);
writeln; write(‘Chon chuc nang: ‘); readln(chon); writeln;
case chon of
1: Bosung;
2: DuyetXuoi;
3: ChenSau;
4: TimXoa;
end;
until chon=5;
while first<>NIL do begin last:= first; first:= first^.next;
dispose(last) end;
End.
uses crt;
type SVienPtr = ^SVien;
SVien = record maso: string[6];
hoten: string[23];
dtb: real;
next : SVienPtr
end;
var first, last : SVienPtr; chon: byte; traloi: char;
procedure Bosung;
var p: SVienPtr; ans: integer;
begin
while true do
begin new(p);
with p^ do begin
write(‘Ma sinh vien : ‘); readln(maso);
write(‘Ho va ten : ‘); readln(Hoten);
write(‘Diem trung binh: ‘); readln(dtb);
end;
p^.next:=NIL;
if first=NIL then begin first:= p; last:= p end
else begin last^.next:= p; last:= p end;
write(‘Co tiep tuc khong 1/0 ? ‘); readln(ans);
if ans=0 then break;
end;
end;
procedure DuyetXuoi;
var p: SVienPtr;
begin if first = NIL then begin writeln(‘D.sach rong’); exit end;
p := first;
while p <> NIL do
begin with p^ do writeln(maso:5,’ ‘,Hoten:25,’ ‘,dtb:5:2);
p := p^.Next;
end;
end;
procedure ChenSau;
var q,p: SVienPtr; found: boolean; masv: string[6];
begin if first <> NIL then begin
write(‘Ma so SV can tim de chen : ‘); readln(masv);
p:= first; found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true else p:=p^.next;
if found then
begin new(q);
with q^ do begin
write(‘ Ma so : ‘); readln(maso);
write(‘ Ho ten : ‘); readln(Hoten);
write(‘ Diem trung binh : ‘); readln(dtb);
end;
q^.next:= p^.next; p^.next:= q;
end else begin write(‘Khong tim thay…’); readln end;
end;
end;
procedure TimXoa;
var masv: string[6]; found: boolean; p,q: SVienPtr;
begin write(‘Ma so SV can loai khoi danh sach : ‘); readln(masv);
p:= first;
if p<>NIL then begin found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true
else begin q:=p; p:=p^.next end;
if found then
begin if p=first then first :=p^.next else q^.next:=p^.next;
if p^.next=NIL then last:=q; dispose(p)
end else begin write(‘Khong tim thay…’); readln end;
end;
end;
Begin clrscr; First := NIL;
repeat
writeln; writeln(’1. Bo sung mot sinh vien’);
writeln(’2. Duyet danh sach sinh vien’);
writeln(’3. Tim kiem mot phan tu va chen vao sau’);
writeln(’4. Tim kiem mot phan tu va xoa’);
writeln(’5. Ket thuc chuong trinh’);
writeln; write(‘Chon chuc nang: ‘); readln(chon); writeln;
case chon of
1: Bosung;
2: DuyetXuoi;
3: ChenSau;
4: TimXoa;
end;
until chon=5;
while first<>NIL do begin last:= first; first:= first^.next;
dispose(last) end;
End.
2. Danh sách liên kết kép
Danh sách liên kết kép là danh sách mà mỗi phần tử của nó gồm ba
thành phần: phần dữ liệu, con trỏ nextchứa
địa chỉ phần tử tiếp sau, con trỏ prev chứa
địa chỉ của phần tử liền trước, con trỏ next của phần tử cuối cùng trong danh
sách bằng NIL, con trỏ prev của phần tử đầu tiên cũng bằng NIL. Danh sách liên
kết kép hoàn toàn xác định bởi hai con trỏ: con trỏ first chứa
địa chỉ phần tử đầu tiên, con trỏ last chứa
địa chỉ phần tử cuối cùng. Danh sách liên kết kép cho phép dễ dàng xác định
phần tử đứng trước một phần tử đã biết, do đó nó thuận tiện hơn danh sách
liên kết thuận trong các thao tác: duyệt ngược danh sách, chèn một phần tử mới
vào trước một phần tử, xoá một phần tử.
Chương trình DslkKep.pas minh hoạ cách làm việc với danh sách liên
kết kép.
uses crt;
type svienPtr = ^svien;
svien = record maso : string[6];
hoten: string[23];
dtb : real;
prev, next : svienPtr;
end;
var first,last: svienPtr; chon: byte;
procedure Bosung;
var p,q: svienPtr; ans: char;
begin
while true do begin
new(p); with p^ do
begin write(‘- Ma so: ‘); readln(maso);
write(‘- Ho va ten: ‘); readln(hoten);
write(‘- Diem trung binh: ‘); readln(dtb); end;
if first=NIL then begin p^.next:= NIL;
p^.prev := NIL; first:= p; last:= p; end
else begin q:= last; q^.next:= p; p^.next:= NIL;
p^.prev:= q; last:= p; end;
write(‘Co tiep tuc khong C/K ?’); readln(ans);
if upcase(ans) = ‘K’ then break;
end;
end;
procedure DuyetXuoi;
var p: svienPtr;
begin
if first <> NIL then
begin p:= first;
while p<> NIL do
begin with p^ do
writeln(maso,’ ‘,hoten,’ ‘,dtb:1:2);
p:= p^.next;
end;
end
else writeln(‘Danh sach rong …’); readln;
end;
procedure DuyetNguoc;
var p: svienPtr;
begin
if first <> NIL then
begin p:= last;
while p<> NIL do
begin with p^ do
writeln(maso,’ ‘,hoten,’ ‘,dtb:1:2);
p:= p^.prev;
end;
end
else writeln(‘Danh sach rong …’); readln;
end;
procedure ChenTruoc;
var p,q,r: svienPtr; found: boolean; masv: string[6];
begin write(‘Ma so SV can tim : ‘); readln(masv);
if first<>NIL then Begin
p:= first; found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true else p:=p^.next;
if found then
begin new(q);
with q^ do
begin write(‘- Ma so: ‘); readln(maso);
write(‘- Ho va ten: ‘); readln(hoten);
write(‘- Diem trung binh: ‘); readln(dtb);
end;
if p=first then
begin q^.next:= p; first^.prev:= q; first:= q end
else begin r:=p^.prev; q^.next:= r^.next; r^.next:= q;
q^.prev:= p^.prev; p^.prev:= q end;
end
else begin write(‘Khong tim thay…’); readln end;
End;
end;
procedure TimXoa;
var p,q,pt: svienPtr; found: boolean; masv: string[6];
begin
write(‘Ma so SV can loai khoi danh sach : ‘); readln(masv);
if first<>NIL then begin
p:= first; found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true else p:=p^.next;
if found then
begin q:= p^.prev; pt:= p^.next; if q<>NIL then q^.next:= p^.next;
if pt<>NIL then pt^.prev:= p^.prev;
if p=first then first:= pt; if p=last then last:= q;
dispose(p);
end
else begin write(‘Khong tim thay …’); readln end;
end;
end;
Begin first:= NIL; clrscr;
repeat writeln(’1. Bo sung phan tu’);
writeln(’2. Duyet danh sach theo chieu xuoi’);
writeln(’3. Duyet danh sach theo chieu nguoc’);
writeln(’4. Chen vao truoc mot phan tu’);
writeln(’5. Tim kiem va xoa mot phan tu’);
writeln(’6. Ket thuc chuong trinh’);
write(‘ Chon chuc nang : ‘); readln(chon);
case chon of
1: Bosung; 2: DuyetXuoi; 3: DuyetNguoc;
4: ChenTruoc; 5: TimXoa;
end;
until chon=6;
while first<> NIL do begin last:=first; first:=first^.next;
dispose(last); end;
End.
uses crt;
type svienPtr = ^svien;
svien = record maso : string[6];
hoten: string[23];
dtb : real;
prev, next : svienPtr;
end;
var first,last: svienPtr; chon: byte;
procedure Bosung;
var p,q: svienPtr; ans: char;
begin
while true do begin
new(p); with p^ do
begin write(‘- Ma so: ‘); readln(maso);
write(‘- Ho va ten: ‘); readln(hoten);
write(‘- Diem trung binh: ‘); readln(dtb); end;
if first=NIL then begin p^.next:= NIL;
p^.prev := NIL; first:= p; last:= p; end
else begin q:= last; q^.next:= p; p^.next:= NIL;
p^.prev:= q; last:= p; end;
write(‘Co tiep tuc khong C/K ?’); readln(ans);
if upcase(ans) = ‘K’ then break;
end;
end;
procedure DuyetXuoi;
var p: svienPtr;
begin
if first <> NIL then
begin p:= first;
while p<> NIL do
begin with p^ do
writeln(maso,’ ‘,hoten,’ ‘,dtb:1:2);
p:= p^.next;
end;
end
else writeln(‘Danh sach rong …’); readln;
end;
procedure DuyetNguoc;
var p: svienPtr;
begin
if first <> NIL then
begin p:= last;
while p<> NIL do
begin with p^ do
writeln(maso,’ ‘,hoten,’ ‘,dtb:1:2);
p:= p^.prev;
end;
end
else writeln(‘Danh sach rong …’); readln;
end;
procedure ChenTruoc;
var p,q,r: svienPtr; found: boolean; masv: string[6];
begin write(‘Ma so SV can tim : ‘); readln(masv);
if first<>NIL then Begin
p:= first; found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true else p:=p^.next;
if found then
begin new(q);
with q^ do
begin write(‘- Ma so: ‘); readln(maso);
write(‘- Ho va ten: ‘); readln(hoten);
write(‘- Diem trung binh: ‘); readln(dtb);
end;
if p=first then
begin q^.next:= p; first^.prev:= q; first:= q end
else begin r:=p^.prev; q^.next:= r^.next; r^.next:= q;
q^.prev:= p^.prev; p^.prev:= q end;
end
else begin write(‘Khong tim thay…’); readln end;
End;
end;
procedure TimXoa;
var p,q,pt: svienPtr; found: boolean; masv: string[6];
begin
write(‘Ma so SV can loai khoi danh sach : ‘); readln(masv);
if first<>NIL then begin
p:= first; found:= false;
while (p<>NIL) and (not found) do
if p^.maso=masv then found := true else p:=p^.next;
if found then
begin q:= p^.prev; pt:= p^.next; if q<>NIL then q^.next:= p^.next;
if pt<>NIL then pt^.prev:= p^.prev;
if p=first then first:= pt; if p=last then last:= q;
dispose(p);
end
else begin write(‘Khong tim thay …’); readln end;
end;
end;
Begin first:= NIL; clrscr;
repeat writeln(’1. Bo sung phan tu’);
writeln(’2. Duyet danh sach theo chieu xuoi’);
writeln(’3. Duyet danh sach theo chieu nguoc’);
writeln(’4. Chen vao truoc mot phan tu’);
writeln(’5. Tim kiem va xoa mot phan tu’);
writeln(’6. Ket thuc chuong trinh’);
write(‘ Chon chuc nang : ‘); readln(chon);
case chon of
1: Bosung; 2: DuyetXuoi; 3: DuyetNguoc;
4: ChenTruoc; 5: TimXoa;
end;
until chon=6;
while first<> NIL do begin last:=first; first:=first^.next;
dispose(last); end;
End.
3. Ngăn xếp dùng danh sách liên kết
Stack là một danh sách theo đó tất cả các công việc chèn và huỷ
đều được thực hiện ở một đầu của danh sách (gọi là đỉnh của ngăn xếp). Stack
giống như một chồng đĩa, đĩa nào đặt cuối cùng lên đỉnh chồng thì đĩa đó sẽ
được lấy ra đầu tiên. Do đó Stack còn có tên gọi là LIFO (last in first out –
vào sau ra trước). Việc thêm một phần tử vào stack có tên gọi là đẩy (Push) vào
stack, còn việc huỷ một phần tử khỏi stack gọi là lấy (Pop) khỏi stack.
Stack dùng danh sách liên kết hoàn toàn giống danh sách liên kết
thuận, nhưng chỉ có điều khác là khi thêm phần tử mới hay huỷ một phần tử ta
luôn luôn làm ở đầu danh sách. Do đó ta phải duy trì một con trỏ Top để trỏ vào
phần tử đầu tiên của danh sách (đỉnh của stack)
Chương trình StDslk.pas minh hoạ cách làm việc với stack dùng danh
sách liên kết, các phần tử của stack là các số nguyên dương.
uses crt;
type StackPtr= ^node;
node = record
data: integer;
next: StackPtr;
end;
var top: StackPtr; chon,n: integer;
procedure Push(n: integer);
var p: StackPtr;
begin new(p); p^.data:= n; p^.next:= top; top:= p;
end;
function Pop: integer;
var p: StackPtr;
begin if top=NIL then pop:=0
else begin pop:= top^.data; p:= top;
top:= top^.next; dispose(p) end;
end;
procedure Duyet;
var p: StackPtr;
begin
if top<>NIL then
begin p:=top;
while p<>NIL do begin writeln(p^.data,’ ‘); p:=p^.next end;
end
else writeln(‘Stack rong’); readln;
end;
Begin clrscr; top:=NIL;
repeat write(’1. Push 2. Pop 3. Duyet 4. Thoat. Chon: ‘);
read(chon);
case chon of
1: begin write(‘Vao n : ‘); readln(n); Push(n) end;
2: begin n:= Pop;
if n<>0 then writeln(‘Phan tu lay ra = ‘,n)
else writeln(‘Stack rong’);
end;
3: Duyet;
end;
until chon=4;
end.
uses crt;
type StackPtr= ^node;
node = record
data: integer;
next: StackPtr;
end;
var top: StackPtr; chon,n: integer;
procedure Push(n: integer);
var p: StackPtr;
begin new(p); p^.data:= n; p^.next:= top; top:= p;
end;
function Pop: integer;
var p: StackPtr;
begin if top=NIL then pop:=0
else begin pop:= top^.data; p:= top;
top:= top^.next; dispose(p) end;
end;
procedure Duyet;
var p: StackPtr;
begin
if top<>NIL then
begin p:=top;
while p<>NIL do begin writeln(p^.data,’ ‘); p:=p^.next end;
end
else writeln(‘Stack rong’); readln;
end;
Begin clrscr; top:=NIL;
repeat write(’1. Push 2. Pop 3. Duyet 4. Thoat. Chon: ‘);
read(chon);
case chon of
1: begin write(‘Vao n : ‘); readln(n); Push(n) end;
2: begin n:= Pop;
if n<>0 then writeln(‘Phan tu lay ra = ‘,n)
else writeln(‘Stack rong’);
end;
3: Duyet;
end;
until chon=4;
end.
4. Hàng đợi dùng danh sách liên kếp
Queue là một danh sách mà việc thêm một phần tử mới được thực hiện
ở đuôi queue, việc huỷ một phần tử được thực hiện ở đầu queue. Queue giống như
một dãy khách hàng xếp hàng trả tiền trong siêu thị, người xếp hàng trước sẽ
được phục vụ trước và ra khỏi hàng, người mới tham gia xếp hàng thì xếp vào
cuối hàng. Do đó queue còn có tên gọi FIFO (first in first out – vào trước thì
ra trước).
Queue dùng danh sách liên kết hoàn toàn giống danh sách liên kết
thuận , nhưng chỉ có điều khác là khi thêm phần tử mới ta luôn luôn nối vào
cuối danh sách, khi huỷ một phần tử ta luôn huỷ phần tử đầu tiên trong
danh sách. Do đó ta phải duy trì hai con trỏ: front trỏ vào phần tử đầu, back
trỏ vào phần tử cuối
Chương trình QueDslk.pas tạo một hàng đợi gồm các số nguyên dương
dùng danh sách liên kết thuận.
uses crt;
type queuePtr= ^node;
node = record data: integer;
next: queuePtr;
end;
var front,back: queuePtr; chon,n: integer;
procedure ThemVao(n: integer);
var p: queuePtr;
begin new(p); p^.data:= n; p^.next:= NIL;
if front=NIl then begin front:=p; back:=p end
else begin back^.next:=p; back:=p end;
end;
function LayRa: integer;
var p: queuePtr;
begin if front=NIL then LayRa:=0
else begin LayRa:= front^.data; p:= front;
front:= front^.next; dispose(p) end;
end;
procedure Duyet;
var p: queuePtr;
begin if front<>NIL then
begin p:=front;
while p<>NIL do begin write(p^.data,’ ‘); p:=p^.next end;
writeln;
end else writeln(‘Queue rong’); readln;
end;
Begin clrscr; front:=NIL; back:=NIL;
repeat write(’1.Push 2.Pop 3.Duyet 4.Thoat. Chon: ‘); read(chon);
case chon of
1: begin write(‘Vao n : ‘); readln(n); ThemVao(n) end;
2: begin n:= LayRa; if n<>0 then writeln(‘Phan tu lay ra = ‘,n)
else writeln(‘Queue rong’);
end;
3: Duyet;
end;
until chon=4;
end.
uses crt;
type queuePtr= ^node;
node = record data: integer;
next: queuePtr;
end;
var front,back: queuePtr; chon,n: integer;
procedure ThemVao(n: integer);
var p: queuePtr;
begin new(p); p^.data:= n; p^.next:= NIL;
if front=NIl then begin front:=p; back:=p end
else begin back^.next:=p; back:=p end;
end;
function LayRa: integer;
var p: queuePtr;
begin if front=NIL then LayRa:=0
else begin LayRa:= front^.data; p:= front;
front:= front^.next; dispose(p) end;
end;
procedure Duyet;
var p: queuePtr;
begin if front<>NIL then
begin p:=front;
while p<>NIL do begin write(p^.data,’ ‘); p:=p^.next end;
writeln;
end else writeln(‘Queue rong’); readln;
end;
Begin clrscr; front:=NIL; back:=NIL;
repeat write(’1.Push 2.Pop 3.Duyet 4.Thoat. Chon: ‘); read(chon);
case chon of
1: begin write(‘Vao n : ‘); readln(n); ThemVao(n) end;
2: begin n:= LayRa; if n<>0 then writeln(‘Phan tu lay ra = ‘,n)
else writeln(‘Queue rong’);
end;
3: Duyet;
end;
until chon=4;
end.
procedure ThemVao(n: integer);
var p: queuePtr;
begin new(p); p^.data:= n; p^.next:= NIL;
if front=NIl then begin front:=p; back:=p end
else begin back^.next:=p; back:=p end;
end;
function LayRa: integer;
var p: queuePtr;
begin if front=NIL then LayRa:=0
else begin LayRa:= front^.data; p:= front;
front:= front^.next; dispose(p) end;
end;
procedure Duyet;
var p: queuePtr;
begin if front<>NIL then
begin p:=front;
while p<>NIL do begin write(p^.data,’ ‘); p:=p^.next end;
writeln;
end else writeln(‘Queue rong’); readln;
end;
Begin clrscr; front:=NIL; back:=NIL;
repeat write(’1.Push 2.Pop 3.Duyet 4.Thoat. Chon: ‘); read(chon);
case chon of
1: begin write(‘Vao n : ‘); readln(n); ThemVao(n) end;
2: begin n:= LayRa; if n<>0 then writeln(‘Phan tu lay ra = ‘,n)
else writeln(‘Queue rong’);
end;
3: Duyet;
end;
until chon=4;
end.
Không có nhận xét nào:
Đăng nhận xét