Trong chương này người học có thể nắm bắt được những kiến thức sau: Khái niệm danh sách, các phép toán trên danh sách, các hình thức tổ chức danh sách, cài đặt danh sách bằng mảng (DS đặc). . | 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 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 Khái niệm danh sách Khái niệm danh sách Mô hình toán học của danh sách là một tập hợp hữu hạn các phần tử có cùng một kiểu, tổng quát gọi là kiểu phần tử (ElementType). Ta biểu diễn danh sách như là một chuỗi các phần tử của nó: a1, a2, . . ., an với n ≥ 0. Nếu n=0 ta nói danh sách rỗng (empty list). Số phần tử của DS gọi là độ dài của danh sách. Một tính chất quan trọng của danh sách là các phần tử của danh sách có thứ tự tuyến tính theo vị trí (position) xuất hiện của các phần tử. Các phép toán trên danh sách INSERT_LIST(x,p,L): xen phần tử x (kiểu ElementType) vào vị trí p (kiểu position) trong danh sách L. LOCATE(x,L): thực hiện việc định vị phần tử có nội dung x đầu tiên trong danh sách L. Nếu x không có trong danh sách thì vị trí sau phần tử cuối cùng của danh sách được trả về, tức là ENDLIST(L). RETRIEVE(p,L): lấy giá trị của phần tử ở vị trí p (kiểu position) của danh sách L. Các phép toán trên danh sách DELETE_LIST(p,L): thực hiện việc xoá phần tử ở vị trí p (kiểu position) của danh sách. NEXT(p,L): cho kết quả là vị trí của phần tử sau phần tử p; nếu p là phần tử cuối cùng trong danh sách L thì NEXT(p,L) cho kết quả là ENDLIST(L). PREVIOUS(p, L): cho kết quả là vị trí của phần tử đứng trước phần tử p trong danh sách. Các phép toán trên danh sách FIRST(L): cho kết quả là vị trí của phần tử đầu tiên trong danh sách. EMPTY_LIST(L): cho kết quả TRUE nếu danh sách rỗng, ngược lại nó cho giá . | 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 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 Khái niệm danh sách Khái niệm danh sách Mô hình toán học của danh sách là một tập hợp hữu hạn các phần tử có cùng một kiểu, tổng quát gọi là kiểu phần tử (ElementType). Ta biểu diễn danh sách như là một chuỗi các phần tử của nó: a1, a2, . . ., an với n ≥ 0. Nếu n=0 ta nói danh sách rỗng (empty list). Số phần tử của DS gọi là độ dài của danh sách. Một tính chất quan trọng của danh sách là các phần tử của danh sách có thứ tự tuyến
