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

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...
Nội dung trích xuất từ tài liệu:
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 Pascal1. Danh sách liên kết đơnDanh 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áchcá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áchnà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àomả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êntụ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 địachỉ 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 contrỏ 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ốicùng giá trị của con trỏ next bằng NIL. Để thuận tiện khi thêm phần tử mới vàocuố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ốicùng. Khởi tạo một danh sách rỗng first = NIL Chương trìnhDslk.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ệucủ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épDanh 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ằngNIL, con trỏ prev của phần tử đầu tiên cũng bằng NIL. Danh sách liên kết képhoàn toàn xác định bởi hai con trỏ: con trỏ firstchứa địa chỉ phần tử đầu tiên, contrỏ 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àngxác định phần tử đứng trước một phần tử đã biết, do đó nó thuận tiện hơn d ...