tailieunhanh - Bài giảng Cấu trúc dữ liệu 1: Chương 3C - Huỳnh Cao Thế Cường

Chương này trang bị cho người học những hiểu biết về danh sách liên kết (link list). Nội dung được trình bày trong chương này gồm có: Các loại danh sách liên kết, danh sách liên kết, danh sách liên kết đơn. . | CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@ TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNG Chương 3. CẤU TRÚC DỮ LIỆU ĐỘNG Đặt vấn đề Kiểu dữ liệu Con trỏ Danh sách liên kết (link list) Danh sách đơn (xâu đơn) Tổ chức danh sách đơn theo cách cấp phát liên kết Một số cấu trúc dữ liệu dạng danh sách liên kết khác Danh sách liên kết kép Hàng đợi hai đầu (double-ended queue) Danh sách liên kết có thứ tự (odered list) Danh sách liên kết vòng Danh sách có nhiều mối liên kết Danh sách tổng quát DANH SÁCH LIÊN KẾT Danh sách liên kết? Bao gồm các thành phần có cấu trúc giống nhau. Mỗi cấu trúc gồm: thành phần dữ liệu và con trỏ chỉ tới phần tử kế tiếp trong danh sách – Gọi là con trỏ next Các loại danh sách liên kết Danh sách liên kết đơn Header A B C D E Header Các loại danh sách liên kết Danh sách liên kết kép (Doubly Linked List) B A C D Các loại danh sách liên kết Danh sách liên kết đơn vòng (Circular Linked List) A B C D E Các loại danh sách liên kết Danh sách liên kết kép vòng (Circular Linked List) B A C D Danh sách liên kết Nhận xét Số nút không cố định, thay đổi tùy nhu cầu nên đây là cấu trúc động. Thích hợp thực hiện các thao tác chèn và hủy vì không cần phải dời nút mà chỉ cần sửa các liên kết cho phù hợp. Thời gian thực hiện không phụ thuộc vào số nút danh sách. Tốn bộ nhớ chứa con trỏ liên kết pNext. Truy xuất tuần tự nên mất thời gian. Danh sách liên kết đơn Header A B C D E Header DANH SÁCH LIÊN KẾT ĐƠN (tt) a1 a2 an * NULL Header DANH SÁCH LIÊN KẾT ĐƠN Khai báo typedef . ElementType; //kiểu của phần tử trong danh sách typedef struct Node { ElementType Element; //Chứa nội dung của phần tử Node *Next; / /con trỏ chỉ đến phần tử kế tiếp }; typedef Node *PtrToNode; typedef PtrToNode Position; //kiểu vị trí typedef PtrToNode List; //Danh sách DANH SÁCH LIÊN KẾT ĐƠN (tt) Để quản lý danh sách ta chỉ cần một biến giữ địa chỉ ô chứa phần tử đầu tiên của danh sách. Biến | CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@ TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNG Chương 3. CẤU TRÚC DỮ LIỆU ĐỘNG Đặt vấn đề Kiểu dữ liệu Con trỏ Danh sách liên kết (link list) Danh sách đơn (xâu đơn) Tổ chức danh sách đơn theo cách cấp phát liên kết Một số cấu trúc dữ liệu dạng danh sách liên kết khác Danh sách liên kết kép Hàng đợi hai đầu (double-ended queue) Danh sách liên kết có thứ tự (odered list) Danh sách liên kết vòng Danh sách có nhiều mối liên kết Danh sách tổng quát DANH SÁCH LIÊN KẾT Danh sách liên kết? Bao gồm các thành phần có cấu trúc giống nhau. Mỗi cấu trúc gồm: thành phần dữ liệu và con trỏ chỉ tới phần tử kế tiếp trong danh sách – Gọi là con trỏ next Các loại danh sách liên kết Danh sách liên kết đơn Header A B C D E Header Các loại danh sách liên kết Danh sách liên kết kép (Doubly Linked List) B A C D Các loại danh sách liên kết Danh sách liên kết đơn vòng (Circular .