Bài giảng Kỹ thuật lập trình - Danh sách liên kết

KỸ THUẬT LẬP TRÌNHDANH SÁCH LIÊN KẾTNội dungDanh sách liên kếtCác hình thức tổ chức danh sách1Các loại danh sách liên kết2Thao tác trên DSLK đơn3Các ứng dụng của DSLK đơn4Các hình thức tổ chức danh sáchMối liên hệ giữa các phần tử được ngầm hiểuMỗ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.Danh sách liên kếtCác hình thức tổ chức danh sáchMối liên hệ giữa các phần tử rõ ràngMỗ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.Danh sách liên kếtDanh sách liên kếtNhận xétSố 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.Danh sách liên kếtDanh sách liên kết đơntypedef struct tagNode{ Data Info; struct tagNode *pNext;} NODE;typedef struct tagList{ NODE *pHead; NODE *pTail;} LIST;Các loại danh sách liên kếtDanh sách liên kếtABCDEpHeadpTailDanh sách liên kết kép (Doubly Linked List)typedef struct tagDNode{ Data Info; struct tagDNode *pNext, *pPrev;} DNODE;typedef struct tagDList{ NODE *pHead; NODE *pTail;} DLIST;Các loại danh sách liên kếtDanh sách liên kếtBpHeadpTailACDDanh sách liên kết đơn vòng (Circular Linked List)typedef struct tagCNode{ Data Info; struct tagCNode *pNext;} CNODE;typedef struct tagCList{ NODE *pHead; NODE *pTail;} CLIST;Các loại danh sách liên kếtDanh sách liên kếtpHeadpTailABCDEDanh sách liên kết kép vòng (Circular Linked List)typedef struct tagCNode{ Data Info; struct tagCNode *pNext, *pPrev;} CNODE;typedef struct tagCList{ NODE *pHead; NODE *pTail;} CLIST;Các loại danh sách liên kếtDanh sách liên kếtBpHeadpTailACD??Danh sách liên kết đơnKhởi tạo danh sáchKiểm tra danh sách có rỗng hay khôngDanh sách liên kếtpHeadpTailNULL?pHeadpTail?Danh sách liên kết đơnTạo một nút mớiXác định con trỏ của nút thứ i trong danh sáchp = pHeadp = p->pNext i lần trong khi p != NULL rồi return lại con trỏ p hiện tạiXác định vị trí của nút p trong danh sáchTương tự như trên nhưng trả lại vị tríDanh sách liên kết?XDanh sách liên kết đơnChèn một nút vào đầu danh sáchDanh sách rỗngDanh sách không rỗngDanh sách liên kếtXABCDEpHeadpTailXpHeadpTailDanh sách liên kết đơnThêm một nút vào cuối danh sáchDanh sách rỗngDanh sách không rỗngDanh sách liên kếtXABCDEpHeadpTailXpHeadpTailDanh sách liên kết đơnThêm một nút vào sau nút qq == NULL  chèn vào đầu danh sáchq != NULLDanh sách liên kếtXABCDEpHeadqpTailDanh sách liên kết đơnThêm một nút vào trước nút qq == NULL  chèn vào đầu danh sáchq != NULL  Tìm nút p trước q rồi thêm vào sau nút p này.Danh sách liên kếtXABCDEpHeadqpTailpDanh sách liên kết đơnHủy một nút đầu danh sáchDanh 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)Danh sách liên kếtABCDEpHeadpTailp = pHeadDanh sách liên kết đơnHủy một nút sau nút qq == NULL  hủy nút đầu danh sáchq != NULLDanh sách liên kếtABCDEpHeadpTailp = q->pNextqDanh sách liên kết đơnHủy một nút cuối danh sáchNú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 qHủ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ó)Hủy toàn bộ danh sáchDuyệt danh sách để in/tìm/đếm các nútDanh sách liên kếtỨng dụng của DSLK đơnStack (Ngăn xếp)Làm việc theo cơ chế LIFO (Last In First Out)Danh sách liên kếtCBA(Top) pHeadpTail (Bottom)Ứng dụng của DSLK đơnQueue (Hàng đợi)Làm việc theo cơ chế FIFO (First In First Out)Danh sách liên kếtABCDpTail (Rear)pHead (Front)