Kỹ thuật lập trình - Danh sách liên kết

Nội dung text: Kỹ thuật lập trình - Danh sách liên kết

1. Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường Đại học Khoa học Tự nhiên KỸ THUẬT LẬP TRÌNH ThS. Đặng Bình Phương dbphuong@fit.hcmus.edu.vn DANH SÁCH LIÊN KẾT 1
2. & VC BB Nội dung 1 Các hình thức tổ chức danh sách 2 Các loại danh sách liên kết 3 Thao tác trên DSLK đơn 4 Các ứng dụng của DSLK đơn 2 Danh sách liên kết
3. & VC BB Các hình thức tổ chức danh sách vMối liên hệ giữa các phần tử được ngầm hiểu § Mỗi phần tử có một chỉ số và ngầm hiểu rằng xi+1 nằm sau xi. Do đó các phần tử phải nằm cạnh nhau trong bộ nhớ. § Số lượng phần tử cố định. Không có thao tác thêm và hủy mà chỉ có thao tác dời chỗ. § Truy xuất ngẫu nhiên đến từng phần tử nhanh chóng. § Phí bộ nhớ do không biết trước kích thước. § Ví dụ: mảng một chiều. 3 Danh sách liên kết
4. & VC BB Các hình thức tổ chức danh sách vMối liên hệ giữa các phần tử rõ ràng § Mỗi phần tử ngoài thông tin bản thân còn có thêm liên kết (địa chỉ) đến phần tử kế tiếp. § Các phần tử không cần phải sắp xếp cạnh nhau trong bộ nhớ. § Việc truy xuất đến một phần tử này đòi hỏi phải thông qua một phần tử khác. § Tùy nhu cầu, các phần tử sẽ liên kết theo nhiều cách khác nhau tạo thành danh sách liên kết đơn, kép, vòng. 4 Danh sách liên kết
5. & VC BB Danh sách liên kết vNhậ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. 5 Danh sách liên kết
6. & VC BB Các loại danh sách liên kết vDanh sách liên kết đơn pTail A B C D E pHead typedef struct tagNode { Data Info; struct tagNode *pNext; } NODE; typedef struct tagList { NODE *pHead; NODE *pTail; } LIST; 6 Danh sách liên kết
7. & VC BB Các loại danh sách liên kết vDanh sách liên kết kép (Doubly Linked List) A B C D typedef struct tagDNode pHead { pTail Data Info; struct tagDNode *pNext, *pPrev; } DNODE; typedef struct tagDList { NODE *pHead; NODE *pTail; } DLIST; 7 Danh sách liên kết
8. & VC BB Các loại danh sách liên kết vDanh sách liên kết đơn vòng (Circular Linked List) A B C D E typedef struct tagCNode pHead { pTail Data Info; struct tagCNode *pNext; } CNODE; typedef struct tagCList { NODE *pHead; NODE *pTail; } CLIST; 8 Danh sách liên kết
9. & VC BB Các loại danh sách liên kết vDanh sách liên kết kép vòng (Circular Linked List) A B C D typedef struct tagCNode pHead { pTail Data Info; struct tagCNode *pNext, *pPrev; } CNODE; typedef struct tagCList { NODE *pHead; NODE *pTail; } CLIST; 9 Danh sách liên kết
10. & VC BB Danh sách liên kết đơn vKhởi tạo danh sách pHead ? pTail ? vKiểm tra danh sách có rỗng hay không pHead NULL? pTail 10 Danh sách liên kết
11. & VC BB Danh sách liên kết đơn vTạo một nút mới X ? ? vXác định con trỏ của nút thứ i trong danh sách § p = pHead § p = p->pNext i lần trong khi p != NULL rồi return lại con trỏ p hiện tại vXác định vị trí của nút p trong danh sách § Tương tự như trên nhưng trả lại vị trí 11 Danh sách liên kết
12. & VC BB Danh sách liên kết đơn vChèn một nút vào đầu danh sách § Danh sách rỗng pTail pHead X § Danh sách không rỗng X pTail A B C D E pHead 12 Danh sách liên kết
13. & VC BB Danh sách liên kết đơn vThêm một nút vào cuối danh sách § Danh sách rỗng pTail pHead X § Danh sách không rỗng pTail X A B C D E pHead 13 Danh sách liên kết
14. & VC BB Danh sách liên kết đơn vThêm một nút vào sau nút q § q == NULL chèn vào đầu danh sách § q != NULL q X pTail A B C D E pHead 14 Danh sách liên kết
15. & VC BB Danh sách liên kết đơn vThêm một nút vào trước nút q § q == NULL chèn vào đầu danh sách § q != NULL Tìm nút p trước q rồi thêm vào sau nút p này. q X pTail A B C D E pHead 15 p Danh sách liên kết
16. & VC BB Danh sách liên kết đơn vHủy một nút đầu danh sách § 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) pTail A B C D E pHead 16 p = pHead Danh sách liên kết
17. & VC BB Danh sách liên kết đơn vHủy một nút sau nút q § q == NULL hủy nút đầu danh sách § q != NULL q pTail A B C D E pHead 17 p = q->pNext Danh sách liên kết
18. & VC BB Danh sách liên kết đơn vHủy một nút cuối danh sách § Nút cuối p (p = pTail) § Tìm nút q trước nút p (nếu có) § Hủy nút sau nút q vHủy một nút có khóa k (Info = k) § Tìm nút p có khóa k và hủy nút q trước đó. § Hủy nút sau nút q (nếu có) vHủy toàn bộ danh sách vDuyệt danh sách để in/tìm/đếm các nút 18 Danh sách liên kết
19. & VC BB Ứng dụng của DSLK đơn vStack (Ngăn xếp) § Làm việc theo cơ chế LIFO (Last In First Out) (Top) pHead C B A pTail (Bottom) 19 Danh sách liên kết
20. & VC BB Ứng dụng của DSLK đơn vQueue (Hàng đợi) § Làm việc theo cơ chế FIFO (First In First Out) pHead (Front) A B C D pTail (Rear) 20 Danh sách liên kết