Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Ngô Công Thắng

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết" cung cấp cho người học các kiến thức: Giới thiệu về danh sách liên kết, danh sách liên kết đơn, danh sách liên kết vòng, danh sách liên kết kép, cài đặt ngăn xếp và hàng đợi bằng danh sách liên kết đơn.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Ngô Công Thắng1. Giới thiệu về danh sách liên kếtSử dụng con trỏ để tổ chức lưu trữ danhsách tuyến tính sẽ tạo ra cấu trúc dữ liệudanh sách liên kết.l Mỗi phần tử của danh sách được lưu trữtrong một phần tử nhớ mà ta gọi là nút(node). Mỗi nút bao gồm một số ô nhớ liềnkề nhau và có thể nằm ở bất kỳ chỗ nàotrong bộ nhớ. Trong mỗi nút ngoài thôngtin ứng với phần tử, còn có địa chỉ của nútliền kề nó.lCHƯƠNG 3DANH SÁCH LIÊN KẾTGV. Ngô Công ThắngBộ môn Công nghệ phần mềmKhoa Công nghệ thông tinWebsite: dse.vnua.edu.vn/ncthangEmail: ncthang@vnua.edu.vnNgô Công ThắngDanh sách liên kết được chia thành danhsách liên kết đơn, danh sách liên kết vòngvà danh sách liên kết kép.l Danh sách liên kết đơn có thể dùng làmcấu trúc lưu trữ cho cấu trúc ngăn xếp vàhàng đợi.1. Giới thiệu về danh sách liên kết2. Danh sách liên kết đơn3. Danh sách liên kết vòng4. Danh sách liên kết kép5. Cài đặt ngăn xếp và hàng đợi bằng danhsách liên kết đơnBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.31. Giới thiệu về danh sách liên kết(tiếp)CHƯƠNG 3DANH SÁCH LIÊN KẾTNgô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 03l3.2Ngô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.42.1. Quy tắc tổ chức danh sáchliên kết đơn (tiếp)2. Danh sách liên kết đơn2.1. Quy tắc tổ chức danh sách liên kết đơnl Mỗi nút trong danh sách có hai trường,trường INFOR chứa thông tin của phần tửvà trường LINK chứa địa chỉ của nút đứngsau (đây chính là địa chỉ liên kết).INFORlllllLINKĐể tổ chức lưu trữ một danh sách liên kết thì phảicó:Ta ký hiệu:llNgô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.5Phải có phương tiện chia bộ nhớ ra thành các nút và ởmỗi nút có thể truy nhập vào từng trường.Phải có cơ chế để xác định một nút đang được sửdụng hoặc chưa được sử dụng (nút trống).Phải có cơ chế cung cấp các nút trống khi có yêu cầusử dụng và thu hồi lại các nút khi không cần dùng nữa.P ⇐ AVAIL là phép lấy ra một nút trống có địa chỉ là P(cấp phát một nút)P ⇒ AVAIL là phép thu hồi một nút có địa chỉ là PNgô Công Thắng2.1. Quy tắc tổ chức danh sáchliên kết đơn (tiếp)Nút cuối cùng trong danh sách không cónút đứng sau nên trường địa chỉ là rỗng,không chứa địa chỉ, ta ký hiệu là ∅.l Để truy nhập vào tất cả nút trong danhsách thì phải có địa chỉ nút đầu tiên, do đócần phải có con trỏ F trỏ tới nút đầu tiên.l Nếu danh sách rỗng thì qui ước F = ∅A1Ngô Công ThắngA2A3Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.72.2. Một số phép toán trêndanh sách liên kết đơnlFBài giảng Cấu trúc dữ liệu và giải thuật - Chương 03A4 ∅3.6Ký hiệu: Một nút có địa chỉ là p (được trỏbởi p) thì INFOR(p) và LINK(p) tương ứngchỉ trường INFOR và LINK của nút đó.a) Bổ sung một nút mới vào danh sáchCho danh sách liên kết đơn F, M là con trỏtrỏ tới một nút trong danh sách. Viết thủtục bổ sung phần tử dữ liệu X vào sau nútM.lNgô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.82.2. Một số phép toán trêndanh sách liên kết đơn (tiếp)a) Bổ sung một nút mới vào danh sách:- Vào: F, M, X- Ra: Không có{Thủ tục này bổ sung phần tử X vào sau núttrỏ bởi M trong danh sách liên kết đơn F}Procedure INSERT(F,M,X)1. {Tạo nút mới}new ⇐ AVAILINFOR(new):=X; LINK(new):= ∅;Ngô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.92. {Thực hiện bổ sung: Nếu danh sách rỗng thì bổsung nút mới vào thành nút đầu tiên. Nếu danhsách không rỗng thì bổ sung nút mới vào saunút M}If F=∅ then F:=newElse beginLINK(new):=LINK(M);LINK(M):=new;end;ReturnBài giảng Cấu trúc dữ liệu và giải thuật - Chương 03b) Loại bỏ một nút khỏi danh sách- Vào: F, M- Ra: Không{Cho danh sách liên kết đơn F, loại bỏ nút trỏ bởiM khỏi danh sách.}Procedure DELETE(F,M)1. { Trường hợp danh sách rỗng}If F=∅ then beginWrite(‘danh sách rỗng’)ReturnendNgô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.112.2. Một số phép toán trêndanh sách liên kết đơn (tiếp)2.2. Một số phép toán trêndanh sách liên kết đơn (tiếp)Ngô Công Thắng2.2. Một số phép toán trêndanh sách liên kết đơn (tiếp)3.10b) Loại bỏ một nút khỏi danh sách2. {Nút trỏ bởi M là nút đầu tiên của danhsách }If M=F then beginF:=LINK(F)M ⇒ AVAILReturnendNgô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033.122.2. Một số phép toán trêndanh sách liên kết đơn (tiếp)2.2. Một số phép toán trêndanh sách liên kết đơn (tiếp)c) Ghép hai danh sách liên kết đơn3. {Tìm đến nút đứng trước nút M }P:=F;While LINK(P) # M do P:=LINK(P)4. {Loại bỏ nút trỏ bởi M}LINK(P):=LINK(M)5. {Hủy nút M}M ⇒ AVAILReturnNgô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 033. {Tìm đến nút cuối danh sách p}p1:= pWhile link(p1) # ∅ do p1:=link(p1);4. {Ghép}Link(p1):=q;Return3.132. ...