Khai báo và sử dụng danh sách liên kết trong Pascal

Chia sẻ: Abcdef_45 Abcdef_45 | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

1.030
lượt xem 95
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khai báo và sử dụng danh sách liên kết trong Pascal

Khai báo và sử dụng danh sách liên kết trong Pascal 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 (pNIL) 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 pNIL THEN BEGIN found:= FALSE; WHILE (pNIL) 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 firstNIL 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ỏ next chứ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ỏ firstchứ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 firstNIL THEN BEGIN p:= first; found:= FALSE; WHILE (pNIL) 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 firstNIL THEN BEGIN p:= first; found:= FALSE; WHILE (pNIL) 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 qNIL THEN q^.next:= p^.next; IF ptNIL 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 topNIL THEN BEGIN p:=top; WHILE pNIL 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 n0 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ết 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 frontNIL THEN BEGIN p:=front; WHILE pNIL 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 n0 THEN writeln('Phan tu lay ra = ',n) ELSE
writeln('Queue rong'); END; 3: Duyet; END; UNTIL chon=4; END.