CẤU TRÚC TUYẾN TÍNH
Danh sách móc nối
Các nội dung chính– Con trỏ và cấp phát bộ nhớ cho đối tượng động– Mô tả cấu trúc lưu trữ móc nối [danh sách móc nối]– Các loại danh sách móc nối• Danh sách nối đơn– Danh sách nối đơn thẳng– Danh sách nối đơn vòng• Danh sách nối kép– Danh sách nối kép thẳng– Danh sách nối kép vòng– Cài đặt LIFO, FIFO bằng cấu trúc lưu trữ móc nối• LIFO
• FIFO
Con trỏ và cấp phát bộ nhớ cho đối tượng động
― Con trỏ [pointer]: là một kiểu dữ liệu [datatype] mà giá trị của nó chỉ dùng để chỉ đến một giá trị khác chứa trong bộ nhớ.
• Giải phóng đối tượng DL động: delete P;
Mô tả cấu trúc lưu trữ móc nối [danh sách móc nối]• Là tập hợp các phần tử dữ liệu không liên tục được kết nối với nhau thông qua một liên kết [thường là con trỏ]• Cho phép ta quản lý bộ nhớ linh động• Các phần tử được chèn vào danh sách và xóa khỏi danh sách một cách dễ dàng
• Tại mỗi nút có hai thành phần:
• Dữ liệu trong nút
• Con trỏ trỏ đến phần tử kế tiếp
Phân loại danh sách móc nối
• Phân loại theo hướng con trỏ [hay số con trỏ trong 1 nút]– Danh sách nối đơn [single linked list]:
• con trỏ luôn chỉ theo một hướng trong danh sách
• 2 con trỏ chỉ theo hai hướng trong danh sách
• Phân loại theo cách móc nối vòng hoặc thẳng
– Danh sách nối thẳng: truy cập vào danh sách thông qua điểm truy nhập H
• Các nút sắp xếp tuần tự trong danh sách
Các thao tác cơ bản
• Khởi tạo danh sách: tạo ra một danh sách rỗng
• Kiểm tra trạng thái hiện tại của DS:
• Rỗng [Empty]: khi con trỏ H = NULL
• Phép xen một phần tử mới vào danh sách
• Xen phần tử mới vào trước phần tử hiện tại Q: InsertAfter
• Xen phần tử mới vào sau phần tử hiện tại Q: InsertBefore
• Phép xoá phần tử khỏi danh sách: Delete• Phép tìm kiếm phần tử có dữ liệu = x: Search
• Phép duyệt danh sách: Traverse
• Khởi tạo danh sách: gán con trỏ H=Null
void InitList [ LinkedList & H ] { H = NULL; }
• Kiểm tra danh sách rỗng: kiểm tra con trỏ H có bằng Null không
bool IsEmpty [ LinkedList H ] { return [H == NULL]; }• Thao tác bổ sung một phần tử mới K vào đầu danh sách H
• Thao tác bổ sung một phần tử mới K vào sau phần tử hiện tại được trỏ bởi P trong d/s H. Thao tác này sau đó trả về con trỏ trỏ vào nút vừa bổ sung . Nếu không cần trả về phần tử vừa bổ sung thì sửa thế nào?
• Thao tác bổ sung một phần tử mới vào trước phần tử hiện tại P trong d/s H.
Thao tác này sau đó trả về con trỏ trỏ vào nút vừa bổ sung [bổ sung một cách khác bằng việc dùng node trung gian,]
• Phép xóa phần ở đầu danh sách H
• Phép xóa phần tử hiện tại mà con trỏ P trỏ tới trong danh sách H
• Phép tìm kiếm một phần tử trong danh sách H có dữ liệu bằng K cho trước. Hàm trả về địa chỉ của phần tử đó
• Thao tác duyệt danh sách, ứng dụng vào tính số phần tử của danh sách
Danh sách nối kép– Với danh sách đơn sử dụng một con trỏ, ta chỉ có thể duyệt danh sách theo một chiều– Danh sách nối kép [double linked list]:• Con trỏ trái [nextL]: trỏ tới thành phần bên trái [phía trước]• Con trỏ phải [nextR]: trỏ tới thành phần bên phải [phía sau]– Đặc điểm• Sử dụng 2 con trỏ, giúp ta luôn xem xét được cả 2 chiều của danh sách
• Tốn bộ nhớ nhiều hơn
struct DNode { Type info; DNode * nextL, * nextR; }; typedef DNode * PDNode; typedef struct { PDNode H; //con trỏ đầu PDNode T; //con trỏ cuối } DoubleLinkedList;
• Khởi tạo danh sách: NewDList• Phép xen một phần tử mới vào danh sách• Xen phần tử mới vào trước phần tử hiện tại Q: InsertAfter• Xen phần tử mới vào sau phần tử hiện tại Q: InsertBefore• Phép xoá phần tử khỏi danh sách: Delete• Phép tìm kiếm phần tử có dữ liệu = x: Search
• Phép duyệt danh sách: Traverse
Cài đặt LIFO [Stack] bằng CTLT móc nối
– Cách tổ chức:• Chỉ cần một con trỏ S vừa là đỉnh, vừa là điểm truy nhập
– Khai báo cấu trúc
struct Node { Type info; Node * next; }; typedef Node * PNode; typedef PNode Stack;
– Các phép toán:
void Initialize [Stack & S ] {
S = NULL;
}
– Kiểm tra trạng thái của ngăn xếp
– Các phép toán: bổ sung 1 phần tử vào đỉnh
• Phép toán lấy một phần tử khỏi ngăn xếp
int StackLength[Stack S] { Pnode P; P = S; count = 0; while [P != NULL] { count++; P = P -> next; } return count; }
Cài đặt FIFO [Queue] bằng CTLT móc nối
– Cấu trúc
struct Node { Type info; Node * next; }; typedef Node * PNode; typedef struct { PNode F, R; } Queue;– Các phép toán:
– Phép toán thêm phần tử vào hàng đợi void InsertQ[Type x, Queue & Q] { Pnode P; P = new PNode; P -> info = x; P -> next = NULL; if [isEmpty[Q]] { Q.F = Q.R = P; } else { Q.R -> next = P; Q.R = P; } }
Bài tập• Bài 1: Cài đặt một danh sách số nguyên bằng cấu trúc lưu trữ móc nối kép. Việc cài đặt bao gồm:– Nêu cách tổ chức danh sách– Định nghĩa cấu trúc– Cài đặt các hàm thực hiện các thao tác cơ bản: khởi tạo, bố sung một phần tử vào trước 1 phần tử hiện tại, bổ sung một phần tử vào sau một phần tử hiện tại, loại bỏ một phần tử hiện tại.• Bài 2: Cài đặt Queue bằng cấu trúc móc nối kép:– Định nghĩa cấu trúc
– Cài đặt các thao tác cơ bản: Khởi tạo, bổ sung, loại bỏ
• Bài 3: cài đặt một danh sách các môn học, mỗi môn học gồm các thông tin: mã môn, tên môn, số tín chỉ. Danh sách luôn được sắp xếp theo thứ tự tăng dần của số tín chỉ. Yêu cầu:– Sử dụng cấu trúc lưu trữ móc nối đơn để cài đặt danh sách
– Cài đặt các thao tác: khởi tạo, bổ sung 1 môn, loại bỏ một môn có mã môn cho trước, in ra nội dung của DS.