Cơ sở dữ liệu - Danh sách liên kết

G V : L Ê T H Ị N GỌC HẠN H DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 1 NỘI DUNG  Cấp phát động và cấp phát tĩnh  Con trỏ và cấp phát động  Danh sách liên kết 9/10/2015 Data structure & Algorithms 2 BIẾN TĨNH  Được khai báo tường minh  Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này.  Được cấp phát vùng nhớ trong vùng dữ liệu (data segment) hoặc là Stack. Kích thước không thay đổi trong suốt quá trình sống. 9/10/2015 Data structure & Algorithms 3 BIẾN ĐỘNG  Không được khai báo tường minh  Có thể được cấp phát hoặc giải phóng bộ nhớ khi người sử dụng yêu cầu.  Các biến này không theo quy tắc phạm vi (tĩnh)  Vùng nhớ của biến được cấp phát trong Heap.  Kích thước có thể thay đổi trong quá trình sống 9/10/2015 Data structure & Algorithms 4 CON TRỎ VÀ CẤP PHÁT ĐỘNG 9/10/2015 Data structure & Algorithms 5 CON TRỎ VÀ CẤP PHÁT ĐỘNG 9/10/2015 Data structure & Algorithms 6 CON TRỎ VÀ CẤP PHÁT ĐỘNG 9/10/2015 Data structure & Algorithms 7 DANH SÁCH LIÊN KẾT (LINKED LIST)  Mảng là một hình thức liên kết ngầm  Các phần tử trong mảng được cấp phát vùng nhớ một cách liên tiếp nhau  Với T là kiểu dữ liệu cho trước, xét mảng các phần tử kiểu T. Ta có: Address(i)=Address(0)+(i-1)*sizeof(T) 9/10/2015 Data structure & Algorithms 8 DANH SÁCH LIÊN KẾT  Một số loại danh sách liên kết (DSLK): • Danh sách liên kết đơn • Danh sách liên kết kép • Danh sách liên kết vòng • .. 9/10/2015 Data structure & Algorithms 9 DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 10 DANH SÁCH LIÊN KẾT  Mỗi phần tử của danh sách đơn là một cấu trúc chứa 2 thành phần chính: - data: lưu trữ các thông tin về bản thân phần tử. - link: lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối danh sách.  Con trỏ Head: dùng để lưu trữ địa chỉ phần tử đầu ds, nên ta gọi Head là đầu xâu(ds).  Con trỏ Tail: giữ địa chỉ phần tử cuối xâu. 9/10/2015 Data structure & Algorithms 11 DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 12 DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 13 KHAI BÁO DSLK typedef struct NODE { int data; NODE* next; }NODE; typedef struct LIST { NODE* pHead; NODE* pTail; }LIST; 9/10/2015 Data structure & Algorithms 14 CÁC THAO TÁC TRÊN DSLK  Khai báo danh sách  Tạo một phần tử cho danh sách  Chèn một phần tử vào danh sách  Tìm một phần tử trong danh sách đơn  Huỷ một phần tử khỏi danh sách  Duyệt danh sách  Sắp xếp danh sách 9/10/2015 Data structure & Algorithms 15 TẠO PHẦN TỬ TRONG DSLK void Initial(LinkList &l) { l.head = l.tail = NULL; } 9/10/2015 Data structure & Algorithms 16 THÊM 1 NÚT VÀO ĐẦU DSLK 9/10/2015 Data structure & Algorithms 17 THÊM 1 NÚT VÀO CUỐI DSLK 9/10/2015 Data structure & Algorithms 18 THÊM 1 NÚT VÀO SAU 1 NÚT 9/10/2015 Data structure & Algorithms 19 THÊM 1 NÚT VÀO TRƯỚC 1 NÚT 9/10/2015 Data structure & Algorithms 20 HỦY 1 NÚT ĐẦU DSLK Danh sách rỗng: không làm gì cả Danh sách không rỗng (nếu sau khi hủy mà pHead = NULL thì pTail = NULL) 9/10/2015 Data structure & Algorithms 21 HỦY 1 NÚT SAU 1 NÚT q == NULL: hủy nút đầu danh sách q != NULL 9/10/2015 Data structure & Algorithms 22