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. | 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 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 ASVien 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 pA DO BEGIN write Ma sinh vien readln maso write Ho va ten readln Hoten write Diem trung binh readln dtb END NIL IF first NIL THEN BEGIN first p last p END ELSE BEGIN 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 rong exit END p first WHILE p NIL DO BEGIN WITH pA DO writeln maso 5
