Những nội dung chính được trình bày trong chương 3 gồm 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. Mời các bạn cùng tham khảo. | CHƯƠNG 3 DANH SÁCH LIÊN KẾT 1. Giới thiệu về danh sách liên kết 2. Danh sách liên kết đơn 3. Danh sách liên kết vòng 4. Danh sách liên kết kép 5. Cài đặt ngăn xếp và hàng đợi bằng danh sách liên kết đơn Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03 1. Giới thiệu về danh sách liên kết l Danh sách liên kết là danh sách tuyến tính khi sử dụng cấu trúc lưu trữ phân tán. Các phần tử dữ liệu của danh sách được lưu trữ trong các phần tử nhớ mà ta gọi là nút node . Trong mỗi nút nhớ ngoài phần tử dữ liệu còn có địa chỉ của nút lân cận. Nếu giữa các nút nhớ có 1 liên kết thì ta có DSLK đơn nếu giữa các nút có 2 liên kết thì ta có DSLK kép. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03 2. Danh sách liên kết đơn . Quy tắc tổ chức danh sách liên kết đơn l 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 đứng sau đây chính là địa chỉ liên kết . INFOR LINK Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03 . Quy tắc tổ chức danh sách liên kết đơn tiếp l Nút cuối cùng trong danh sách không có nút đứng sau nên trường địa chỉ LINK là rỗng . l Để truy nhập vào tất cả nút trong danh sách thì phải có con trỏ F trỏ tới nút đầu tiên. l Khi danh sách rỗng thì F F A1 A2 A3 A4 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03 . Quy tắc tổ chức danh sách liên kết đơn tiếp l Để tổ chức lưu trữ một danh sách liên kết thì phải có l Phả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. l 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 . l Phải có cơ chế cung cấp các nút trống khi có yêu cầu sử dụng và thu hồi lại các nút khi không cần dùng nữa. l Ta ký hiệu l 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 l P AVAIL là phép thu hồi một nút có địa chỉ là P Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03 .
