CẤU TRÚC DỮ LIỆU - Chương 6: DANH SÁCH (LIST)

Định nghĩa Là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng. Tùy cách liên kết giữa các phần tử, danh sách liên kết chia thành các loại khác nhau: Danh sách liên kết đơn Danh sách liên kết đôi/kép Danh sách đa liên kết Danh sách liên kết vòng (vòng đơn, vòng đôi) Mỗi loại danh sách có cách biểu diễn theo các cấu trúc dữ liệu và thao tác trên dữ liệu khác nhau...
Nội dung trích xuất từ tài liệu:
CẤU TRÚC DỮ LIỆU - Chương 6: DANH SÁCH (LIST) Môn: CẤU TRÚC DỮ LIỆU Chương 6: DANH SÁCH (LIST) 4. Danh sách liên kết (Linked List) 4.  4.1. Định nghĩa 4.2. Danh sách liên kết đơn (Simply Linked List) 4.3. Danh sách liên kết kép (Doubly Linked List) 4.4. Danh sách liên kết vòng 4.5. Ưu nhược điểm của danh sách liên kết 4. Danh sách liên kết (tt) 4.  4.1. Định nghĩa  Là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng.  Tùy cách liên kết giữa các phần tử, danh sách liên kết chia thành các loại khác nhau: ◦ Danh sách liên kết đơn ◦ Danh sách liên kết đôi/kép ◦ Danh sách đa liên kết ◦ Danh sách liên kết vòng (vòng đơn, vòng đôi)  Mỗi loại danh sách có cách biểu diễn theo các cấu trúc dữ liệu và thao tác trên dữ liệu khác 4.2. Danh sách liên kết đơn (SLL) 4.2. Danh s 4.2. Danh sách liên kết đơn (SLL) 4.2. Danh s 4.2.1. Cấu trúc dữ liệu  Nội dung mỗi phần tử (nút) trong danh sách liên kết gồm 2 vùng Vùng dữ liệu và Vùng liên kết struct node { int data; node *link; // liên kết đến vùng của phần tử kế tiếp }; data link 4.2. Danh sách liên kết đơn (SLL) 4.2. Danh s 4.2.1. Cấu trúc dữ liệu 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.1. Cấu trúc dữ liệu (tt)  Để quản lý danh sách liên kết có thể dùng nhiều phương pháp khác nhau, mỗi phương pháp sẽ có cấu trúc dữ liệu cụ thể. ◦ Quản lý địa chỉ phần đầu và cuối danh sách struct List { Node *pHead; Node *pTail; }; pHead info pNext pTail 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.1. Cấu trúc dữ liệu (tt) 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2. Các thao tác trên danh sách liên kết đơn a. Khởi tạo danh sách SLL b. Tạo mới 1 phần tử (nút) trong danh sách SLL c. Thêm 1 phần tử vào danh sách SLL  Thêm vào đầu | cuối | giữa danh sách liên kết đơn d. Duyệt qua các nút trong danh sách e. Tìm kiếm phần tử trong danh sách f. Hủy bỏ 1 phần tử trong danh sách g. Hủy danh sách h. Tạo mới danh sách/Nhập danh sách i. Tách 1 danh sách thành nhiều danh sách j. Nhập nhiều danh sách thành 1 danh sách k. Sắp xếp thứ tự các phần tử trong danh sách 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2. Các thao tác trên danh sách liên kết đơn: Giả sử ta có các định nghĩa sau: struct node{  int data; node *link; }; struct List{  node *pHead; node *pTail; }; node *p;  List l;  4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2.a. Khởi tạo danh sách SLL  Thao tác khởi tạo danh sách liên kết đơn là cho giá trị con trỏ quản lý địa chỉ đầu của danh sách về con trỏ NULL.  Hàm khởi tạo danh sách liên kết đơn: void Init(node *pHead) { pHead = NULL; return; } 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2. b. Tạo mới 1 phần tử (nút) trong danh sách SLL Giả sử tạo mới 1 phần tử có thành phần dữ liệu =x Thuật toán B1: p = new node //cấp phát bộ nhớ cho con trỏ p B2: IF(p == NULL) // cấp phát không thành công Thực hiện BKT B3: p->data=x; B4: p->link=NULL BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s (Hàm tạo node) node* get_node(int n){ Node *p; p=new node; //p=(struct node *)malloc(sizeof(struct node)); if (p==NULL) { cout4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm đầu DS) 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm đầu DS) Thuật toán Gỉa sử ta muốn thêm phần tử p vào đầu DS: Nếu DS rỗng thì: pHead=p; pTail=pHead; // pTail=new_element Ngược lại: p->link=pHead; pHead=p; 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s Cài đặt void insert_head(list &l, node *p){ if (l.pHead==NULL){ l.pHead=p; l.pTail=p; } else{ p->link=l.pHead; l.pHead=p; } } 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s Như vậy một danh sách bằng cách chèn đầu ta có thể viết hàm như sau: void create_list_head(list &l, int n) { node *p; for (int i=1;i4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (tt) (Thêm giữa DS) 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (tt) (Thêm giữa DS) 4.2. Danh sách liên kết đơn (tt) 4.2. Danh s 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (tt) (Thêm giữa DS)  Thêm phần tử mới vào ngay sau phần tử q Thuật toán Nếu q!=NULL; B1: p->link=q->link; B2: q->link=p Ngược lại: thêm vào đầu DS