›
›

Cấu trúc dữ liệu và giải thuật - Chapter 6: Danh sách liên kết (linked lists)

pdf 149 trang vanle 3280
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chapter 6: Danh sách liên kết (linked lists)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chapter_6_danh_sach_lien_ket.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chapter 6: Danh sách liên kết (linked lists)

  1. CHAPTER 6: DANH SÁCH LIÊN KẾT (LINKED LISTS)
  2. Nội dung 2  Giới thiệu  Danh sách liên kết đơn (Single Linked List)  Danh sách liên kết đơi (Double Linked List)  Danh sách liên kết vịng (Circular Linked List) Chương 6: Danh sách liên kết
  3. Giới thiệu 3  Kiểu dữ liệu tĩnh  Khái niệm: Một số đối tượng dữ liệu khơng thay thay đổi được kích thước, cấu trúc, trong suốt quá trình sống. Các đối tượng dữ liệu thuộc những kiểu dữ liệu gọi là kiểu dữ liệu tĩnh.  Một số kiểu dữ liệu tĩnh: các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiểu thực, kiểu nguyên, kiểu ký tự hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này thường cứng ngắt, gị bĩ khĩ diễn tả được thực tế vốn sinh động, phong phú. Chương 6: Danh sách liên kết
  4. Giới thiệu 4  Một số hạn chế của CTDL tĩnh  Một số đối tượng dữ liệu trong chu kỳ sống của nĩ cĩ thể thay đổi về cấu trúc, độ lớn, như danh sách các học viên trong một lớp học cĩ thể tăng thêm, giảm đi Nếu dùng những cấu trúc dữ liệu tĩnh đã biết như mảng để biểu diễn Những thao tác phức tạp, kém tự nhiên chương trình khĩ đọc, khĩ bảo trì và nhất là khĩ cĩ thể sử dụng bộ nhớ một cách cĩ hiệu quả  Dữ liệu tĩnh sẽ chiếm vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình sử dụng bộ nhớ kém hiệu quả Chương 6: Danh sách liên kết
  5. Giới thiệu 5  Cấu trúc dữ liệu tĩnh: Ví dụ: Mảng 1 chiều  Kích thước cố định (fixed size)  Chèn 1 phần tử vào mảng rất khĩ  Các phần tử tuần tự theo chỉ số 0 n-1  Truy cập ngẫu nhiên (random access) chèn 0 1 2 3 4 n-2 n-1 Chương 6: Danh sách liên kết
  6. Giới thiệu 6  Cấu trúc dữ liệu động: Ví dụ: Danh sách liên kết, cây  Cấp phát động lúc chạy chương trình  Các phần tử nằm rải rác ở nhiều nơi trong bộ nhớ  Kích thước danh sách chỉ bị giới hạn do RAM  Thao tác thêm xố đơn giản Insert, Delete Chương 6: Danh sách liên kết
  7. Giới thiệu 7  Danh sách liên kết:  Mỗi phần tử của danh sách gọi là node (nút)  Mỗi node cĩ 2 thành phần: phần dữ liệu và phần liên kết chứa địa chỉ của node kế tiếp hay node trước nĩ  Các thao tác cơ bản trên danh sách liên kết:  Thêm một phần tử mới  Xĩa một phần tử  Tìm kiếm  Chương 6: Danh sách liên kết
  8. 8  Cĩ nhiều kiểu tổ chức liên kết giữa các phần tử trong danh sách như:  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 Chương 6: Danh sách liên kết
  9. Giới thiệu 9  Danh sách liên kết đơn: mỗi phần tử liên kết với phần tử đứng sau nĩ trong danh sách: A B X Z Y  Danh sách liên kết đơi: mỗi phần tử liên kết với các phần tử đứng trước và sau nĩ trong danh sách: A B C D Chương 6: Danh sách liên kết
  10. Giới thiệu 10  Danh sách liên kết vịng : phần tử cuối danh sách liên kết với phần tử đầu danh sách: A B X Z Y A B C D Chương 6: Danh sách liên kết
  11. Giới thiệu 11  Hướng giải quyết  Cần xây dựng cấu trúc dữ liệu đáp ứng được các yêu cầu:  Linh động hơn  Cĩ thể thay đổi kích thước, cấu trúc trong suốt thời gian sống Cấu trúc dữ liệu động Chương 6: Danh sách liên kết
  12. Biến khơng động 12 Biến khơng động (biến tĩnh, biến nửa tĩnh) là những biến thỏa:  Đượ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 (đối với biến nửa tĩnh - các biến cục bộ).  Kích thước khơng thay đổi trong suốt quá trình sống.  Do được khai báo tường minh, các biến khơng động cĩ một định danh đã được kết nối với địa chỉ vùng nhớ lưu trữ biến và được truy xuất trực tiếp thơng qua định danh đĩ.  Ví dụ : int a; // a, b là các biến khơng động char b[10]; Chương 6: Danh sách liên kết
  13. Biến động 13  Trong nhiều trường hợp, tại thời điểm biên dịch khơng thể xác định trước kích thước chính xác của một số đối tượng dữ liệu do sự tồn tại và tăng trưởng của chúng phụ thuộc vào ngữ cảnh của việc thực hiện chương trình.  Các đối tượng dữ liệu cĩ đặc điểm kể trên nên được khai báo như biến động. Biến động là những biến thỏa:  Biến 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 qui 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. Chương 6: Danh sách liên kết
  14. Biến động 14  Do khơng được khai báo tường minh nên các biến động khơng cĩ một định danh được kết buộc với địa chỉ vùng nhớ cấp phát cho nĩ, do đĩ gặp khĩ khăn khi truy xuất đến một biến động.  Để giải quyết vấn đề, biến con trỏ (là biến khơng động) được sử dụng để trỏ đến biến động.  Khi tạo ra một biến động, phải dùng một con trỏ để lưu địa chỉ của biến này và sau đĩ, truy xuất đến biến động thơng qua biến con trỏ đã biết định danh. Chương 6: Danh sách liên kết
  15. Biến động 15  Hai thao tác cơ bản trên biến động là tạo và hủy một biến động do biến con trỏ ‘p’ trỏ đến:  Tạo ra một biến động và cho con trỏ ‘p’ chỉ đến nĩ  Hủy một biến động do p chỉ đến Chương 6: Danh sách liên kết
  16. Biến động 16  Tạo ra một biến động và cho con trỏ ‘p’ chỉ đến nĩ void* malloc(size); // trả về con trỏ chỉ đến vùng nhớ // size byte vừa được cấp phát. void* calloc(n,size);// trả về con trỏ chỉ đến vùng nhớ // vừa được cấp phát gồm n phần tử, // mỗi phần tử cĩ kích thước size byte new // tốn tử cấp phát bộ nhớ trong C++  Hàm free(p) huỷ vùng nhớ cấp phát bởi hàm malloc hoặc calloc do p trỏ tới  Tốn tử delete p huỷ vùng nhớ cấp phát bởi tốn tử new do p trỏ tới Chương 6: Danh sách liên kết
  17. Biến động – Ví dụ 17 int *p1, *p2; // cấp phát vùng nhớ cho 1 biến động kiểu int p1 = (int*)malloc(sizeof(int)); *p1 = 5; // đặt giá trị 5 cho biến động đang được p1 quản lý // cấp phát biến động kiểu mảng gồm 10 phần tử kiểu int p2 = (int*)calloc(10, sizeof(int)); *(p2+3) = 0; // đặt giá trị 0 cho phần tử thứ 4 của mảng p2 free(p1); free(p2); Chương 6: Danh sách liên kết
  18. Kiểu dữ liệu Con trỏ 18  Kiểu con trỏ là kiểu cơ sở dùng lưu địa chỉ của một đối tượng dữ liệu khác.  Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nĩ là địa chỉ cuả một vùng nhớ ứng với một biến kiểu T, hoặc là giá trị NULL. Chương 6: Danh sách liên kết
  19. Con trỏ – Khai báo 19  Cú pháp định nghĩa một kiểu con trỏ trong ngơn ngữ C : typedef * ;  Ví dụ : typedef int *intpointer; intpointer p; hoặc int *p; là những khai báo hợp lệ. Chương 6: Danh sách liên kết
  20. Con trỏ – Thao tác căn bản 20  Các thao tác cơ bản trên kiểu con trỏ:(minh họa bằng C)  Khi 1 biến con trỏ p lưu địa chỉ của đối tượng x, ta nĩi ‘p trỏ đến x’.  Gán địa chỉ của một vùng nhớ con trỏ p: p = ; ví dụ : int i,*p; p=&i;  Truy xuất nội dung của đối tượng do p trỏ đến (*p) Chương 6: Danh sách liên kết
  21. Nội dung 21  Giới thiệu  Danh sách liên kết đơn (Single Linked List)  Danh sách liên kết kép (Doule Linked List)  Danh sách liên kết vịng (Circular Linked List) Chương 6: Danh sách liên kết
  22. Danh sách liên kết đơn (DSLK đơn) 22  Khai báo  Các thao tác cơ bản trên DSLK đơn  Sắp xếp trên DSLK đơn Chương 6: Danh sách liên kết
  23. DSLK đơn – Khai báo 23  Là danh sách các node mà mỗi node cĩ 2 thành phần:  Thành phần dữ liệu: lưu trữ các thơng tin về bản thân phần tử  Thành phần mối liên kết: 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 Link Data  Khai báo node struct Node { DataType data; // DataType là kiểu đã định nghĩa trước Node *pNext; // con trỏ chỉ đến cấu trúc Node }; Chương 6: Danh sách liên kết
  24. DSLK đơn – Khai báo 24  Ví dụ 1: Khai báo node lưu số  Ví dụ 2: Định nghĩa một phần nguyên: tử trong danh sách đơn lưu struct Node trữ hồ sơ sinh viên: { struct SinhVien { int data; char Ten[30]; Node *pNext; int MaSV; }; }; struct SVNode { SinhVien data; SVNode *pNext; }; Chương 6: Danh sách liên kết
  25. DSLK đơn – Khai báo 25  Tổ chức, quản lý:  Để quản lý một DSLK đơn chỉ cần biết địa chỉ phần tử đầu danh sách  Con trỏ pHead sẽ được dùng để lưu trữ địa chỉ phần tử đầu danh sách. Ta cĩ khai báo: Node *pHead;  Để tiện lợi, cĩ thể sử dụng thêm một con trỏ pTail giữ địa chỉ phần tử cuối danh sách. Khai báo pTail như sau: Node *pTail; pTail pHead AA B X Z Y Chương 6: Danh sách liên kết
  26. DSLK đơn – Khai báo 26  Ví dụ: Khai báo cấu trúc 1 DSLK đơn chứa số nguyên // kiểu của một phần tử trong danh sách struct Node { int data; Node* pNext; Khai báo biến kiểu danh sách: }; // kiểu danh sách liên kết List tên_biến; struct List { Node* pHead; Node* pTail; }; Chương 6: Danh sách liên kết
  27. DSLK đơn – Khai báo 27  Tạo một node mới  Thủ tục GetNode để tạo ra một nút cho danh sách với thơng tin chứa trong x Node* getNode ( DataType x) { Node *p; p = new Node; // Cấp phát vùng nhớ cho node Gọi if (p==NULL) hàm?? { cout data = x; // Gán dữ liệu cho phần tử p p->pNext = NULL; return p; } Chương 6: Danh sách liên kết
  28. Tạo một phần tử 28 Để tạo một phần tử mới cho danh sách, cần thực hiện câu lệnh: new_ele = GetNode(x); new_ele sẽ quản lý địa chỉ của phần tử mới được tạo. Chương 6: Danh sách liên kết
  29. Danh sách liên kết đơn (DSLK đơn) 29  Khai báo  Các thao tác cơ bản trên DSLK đơn  Sắp xếp trên DSLK đơn Chương 6: Danh sách liên kết
  30. DSLK đơn 30  Các thao tác cơ bản  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Duyệt danh sách  Tìm kiếm một giá trị trên danh sách  Xĩa một phần tử ra khỏi danh sách  Hủy tồn bộ danh sách  Chương 6: Danh sách liên kết
  31. DSLK đơn – Các thao tác cơ sở 31  Tạo danh sách rỗng pTail pHead void Init(List &l) { l.pHead = l.pTail = NULL; } Chương 6: Danh sách liên kết
  32. DSLK đơn 32  Các thao tác cơ bản  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Duyệt danh sách  Tìm kiếm một giá trị trên danh sách  Xĩa một phần tử ra khỏi danh sách  Hủy tồn bộ danh sách  Chương 6: Danh sách liên kết
  33. DSLK đơn – Các thao tác cơ sở 33  Thêm một phần tử vào danh sách: Cĩ 3 vị trí thêm  Gắn vào đầu danh sách  Gắn vào cuối danh sách  Chèn vào sau nút q trong danh sách  Chú ý trường hợp danh sách ban đầu rỗng Chương 6: Danh sách liên kết
  34. DSLK đơn – Các thao tác cơ sở 34  Thêm một phần tử  Nếu danh sách ban đầu rỗng pTail pHead pHead = pTail = new_node; X new_node Chương 6: Danh sách liên kết
  35. DSLK đơn – Các thao tác cơ sở 35  Thêm một phần tử  Nếu danh sách ban đầu khơng rỗng:  Gắn node vào đầu danh sách pHead pTail A B C D E X new_node->pNext = pHead; pHead = new_node; new_node Chương 6: Danh sách liên kết
  36. DSLK đơn – Các thao tác cơ sở 36 Thuật tốn: Gắn nút vào đầu DS // input: danh sách, phần tử mới new_node // output: danh sách với new_node ở đầu DS  Nếu DS rỗng thì  pHead = pTail = new_node;  Ngược lại  new_node->pNext = pHead;  pHead = new_node; Chương 6: Danh sách liên kết
  37. DSLK đơn – Các thao tác cơ sở 37 Cài đặt: Gắn nút vào đầu DS void addHead(List &l, Node* new_node) { if (l.pHead == NULL) // DS rỗng { l.pHead = l.pTail = new_node; } else { new_node->pNext = l.pHead; l.pHead = new_node; } } Chương 6: Danh sách liên kết
  38. DSLK đơn – Các thao tác cơ sở 38 Thuật tốn: Thêm một thành phần dữ liệu vào đầu DS // input: danh sách l // output: danh sách l với phần tử chứa X ở đầu DS  Nhập dữ liệu cho X (???)  Tạo nút mới chứa dữ liệu X (???)  Nếu tạo được:  Gắn nút mới vào đầu danh sách (???) Chương 6: Danh sách liên kết
  39. DSLK đơn – Các thao tác cơ sở 39 Ví dụ: Thêm một số nguyên vào đầu ds: // Nhập dữ liệu cho X int x; cout >x; // Tạo nút mới Node* new_node = getNode(x); // Gắn nút vào đầu ds if (new_node != NULL) addHead(l, new_node); Chương 6: Danh sách liên kết
  40. DSLK đơn – Các thao tác cơ sở 40  Thêm một phần tử vào danh sách: Cĩ 3 vị trí thêm  Gắn vào đầu danh sách  Gắn vào cuối danh sách  Chèn vào sau nút q trong danh sách  Chú ý trường hợp danh sách ban đầu rỗng Chương 6: Danh sách liên kết
  41. DSLK đơn – Các thao tác cơ sở 41  Thêm một phần tử  Nếu danh sách ban đầu rỗng pTail pHead pHead = pTail = new_node; X new_node Chương 6: Danh sách liên kết
  42. DSLK đơn – Các thao tác cơ sở 42  Thêm một phần tử  Nếu danh sách ban đầu khơng rỗng:  Gắn node vào cuối danh sách: pTail pHead A B C D E pTail->pNext = new_node; X pTail = new_node; new_node Chương 6: Danh sách liên kết
  43. DSLK đơn – Các thao tác cơ sở 43 Thuật tốn: Thêm một phần tử vào cuối DS // input: danh sách, phần tử mới new_node // output: danh sách với new_node ở cuối DS  Nếu DS rỗng thì  pHead = pTail = new_node;  Ngược lại  pTail->pNext = new_node ;  pTail = new_node; Chương 6: Danh sách liên kết
  44. DSLK đơn – Các thao tác cơ sở 44 Cài đặt: Gắn nút vào cuối DS void addTail(List &l, Node *new_node) { if (l.pHead == NULL) { l.pHead = l.pTail = new_node; } else { l.pTail->pNext = new_node; l.pTail = new_node ; } } Chương 6: Danh sách liên kết
  45. DSLK đơn – Các thao tác cơ sở 45 Thuật tốn: Thêm một thành phần dữ liệu vào cuối ds // input: danh sách thành phần dữ liệu X // output: danh sách với phần tử chứa X ở cuối DS  Nhập dữ liệu cho X (???)  Tạo nút mới chứa dữ liệu X (???)  Nếu tạo được:  Gắn nút mới vào cuối danh sách (???) Chương 6: Danh sách liên kết
  46. DSLK đơn – Các thao tác cơ sở 46 Ví dụ: Thêm một số nguyên vào cuối ds: // Nhập dữ liệu cho X int x; cout >x; // Tạo nút mới Node* p = getNode(x); // Gắn nút vào cuối DS if (p != NULL) addTail(l, p); Chương 6: Danh sách liên kết
  47. DSLK đơn – Các thao tác cơ sở 47  Thêm một phần tử vào danh sách: Cĩ 3 vị trí thêm  Gắn vào đầu danh sách  Gắn vào cuối danh sách  Chèn vào sau nút q trong danh sách  Chú ý trường hợp danh sách ban đầu rỗng Chương 6: Danh sách liên kết
  48. DSLK đơn – Các thao tác cơ sở 48  Thêm một phần tử  Nếu danh sách ban đầu rỗng pTail pHead pHead = pTail = new_node; X new_node Chương 6: Danh sách liên kết
  49. DSLK đơn – Các thao tác cơ sở 49  Thêm một phần tử  Nếu danh sách ban đầu rỗng  Chèn một phần tử sau q q pTail pHead A B C D E X new_node Chương 6: Danh sách liên kết
  50. DSLK đơn – Các thao tác cơ sở 50 Thuật tốn: Chèn một phần tử sau q // input: danh sách l, q, phần tử mới new_node // output: danh sách với new_node ở sau q  Nếu (q != NULL) thì: new_node -> pNext = q -> pNext; q -> pNext = new_node ; Nếu ( q == l.pTail) thì l.pTail = new_node;  Ngược lại Thêm new_node vào đầu danh sách Chương 6: Danh sách liên kết
  51. DSLK đơn – Các thao tác cơ sở 51 Cài đặt: Chèn một phần tử sau q void addAfter (List &l, Node *q, Node* new_node) { if (q!=NULL) { new_node->pNext = q->pNext; q->pNext = new_node; if(q == l.pTail) l.pTail = new_node; } } Chương 6: Danh sách liên kết
  52. DSLK đơn – Các thao tác cơ sở 52 Thuật tốn: Thêm một thành phần dữ liệu vào sau q // input: danh sách thành phần dữ liệu X // output: danh sách với phần tử chứa X ở cuối DS  Nhập dữ liệu cho nút q (???)  Tìm nút q (???)  Nếu tồn tại q trong ds thì:  Nhập dữ liệu cho X (???)  Tạo nút mới chứa dữ liệu X (???)  Nếu tạo được:  Gắn nút mới vào sau nút q (???)  Ngược lại thì báo lỗi Chương 6: Danh sách liên kết
  53. DSLK đơn 53  Các thao tác cơ bản  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Duyệt danh sách  Tìm kiếm một giá trị trên danh sách  Xĩa một phần tử ra khỏi danh sách  Hủy tồn bộ danh sách  Chương 6: Danh sách liên kết
  54. DSLK đơn – Các thao tác cơ sở 54  Duyệt danh sách  Là thao tác thường được thực hiện khi cĩ nhu cầu xử lý các phần tử của danh sách theo cùng một cách thức hoặc khi cần lấy thơng tin tổng hợp từ các phần tử của danh sách như:  Đếm các phần tử của danh sách  Tìm tất cả các phần tử thoả điều kiện  Hủy tồn bộ danh sách (và giải phĩng bộ nhớ)  Chương 6: Danh sách liên kết
  55. DSLK đơn – Các thao tác cơ sở 55  Duyệt danh sách  Bước 1: p = pHead; //Cho p trỏ đến phần tử đầu danh sách  Bước 2: Trong khi (Danh sách chưa hết) thực hiện:  B2.1 : Xử lý phần tử p  B2.2 : p=p->pNext; // Cho p trỏ tới phần tử kế void processList (List l) { Node *p = l.pHead; while (p!= NULL) { // xử lý cụ thể p tùy ứng dụng p = p->pNext; } } Chương 6: Danh sách liên kết
  56. DSLK đơn – Các thao tác cơ sở 56 Ví dụ: In các phần tử trong danh sách void Output (List l) { Node* p=l.pHead; while (p!=NULL) { cout data pNext; } cout<<endl; } Chương 6: Danh sách liên kết
  57. DSLK – Minh họa in danh sách 57 p first 3000 5000 4000 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL p = first; while (p!=NULL) { printf(“%d\t”,p->data); p = p->link; } Chương 6: Danh sách liên kết
  58. DSLK – Minh họa in danh sách 58 p 3000 first 3000 5000 4000 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL p =first; while (p!=NULL) { printf(“%d\t”,p->data); p = p->link; } Chương 6: Danh sách liên kết
  59. DSLK đơn 59  Các thao tác cơ bản  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Duyệt danh sách  Tìm kiếm một giá trị trên danh sách  Xĩa một phần tử ra khỏi danh sách  Hủy tồn bộ danh sách  Chương 6: Danh sách liên kết
  60. DSLK đơn – Các thao tác cơ sở 60  Tìm kiếm một phần tử cĩ khĩa x Node* Search (List l, int x) { Gọi hàm??? Node* p = l.pHead; while (p!=NULL) { if (p->data==x) return p; p=p->pNext; } return NULL; } Chương 6: Danh sách liên kết
  61. DSLK đơn 61  Các thao tác cơ bản  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Duyệt danh sách  Tìm kiếm một giá trị trên danh sách  Xĩa một phần tử ra khỏi danh sách  Hủy tồn bộ danh sách  Chương 6: Danh sách liên kết
  62. DSLK đơn – Các thao tác cơ sở 62  Xĩa một node của danh sách  Xĩa node đầu của danh sách  Xĩa node sau node q trong danh sách  Xĩa node cĩ khố k Chương 6: Danh sách liên kết
  63. DSLK đơn – Các thao tác cơ sở 63 Xĩa node đầu của danh sách  Gọi p là node đầu của danh sách (pHead)  Cho pHead trỏ vào node sau node p (là p->pNext)  Nếu danh sách trở thành rỗng thì pTail = NULL  Giải phĩng vùng nhớ mà p trỏ tới Chương 6: Danh sách liên kết
  64. DSLK đơn – Các thao tác cơ sở 64  Xĩa một node của danh sách pHead pTail A B C D E p l.pHead = p->pNext; delete p; Chương 6: Danh sách liên kết
  65. DSLK đơn – Các thao tác cơ sở 65 int removeHead (List &l) { if (l.pHead == NULL) return 0; Node* p=l.pHead; l.pHead = p->pNext; if (l.pHead == NULL) l.pTail=NULL; //Nếu danh sách rỗng delete p; return 1; } Chương 6: Danh sách liên kết
  66. DSLK đơn – Các thao tác cơ sở 66  Xĩa một node của danh sách  Xĩa node đầu của danh sách  Xĩa node sau node q trong danh sách  Xĩa node cĩ khố k Chương 6: Danh sách liên kết
  67. DSLK đơn – Các thao tác cơ sở 67 Xĩa node sau node q trong danh sách  Điều kiện để cĩ thể xĩa được node sau q là:  q phải khác NULL (q !=NULL)  Node sau q phải khác NULL (q->pNext !=NULL)  Cĩ các thao tác:  Gọi p là node sau q  Cho vùng pNext của q trỏ vào node đứng sau p  Nếu p là phần tử cuối thì pTail trỏ vào q  Giải phĩng vùng nhớ mà p trỏ tới Chương 6: Danh sách liên kết
  68. DSLK đơn – Các thao tác cơ sở 68 Xĩa node sau node q trong danh sách q p last first A B C D E q->pNext = p->pNext; delete p; Chương 6: Danh sách liên kết
  69. DSLK đơn – Các thao tác cơ sở 69 Xĩa node sau node q trong danh sách int removeAfter (List &l, Node *q ) { if (q !=NULL && q->pNext !=NULL) { Node* p = q->pNext; q->pNext = p->pNext; if (p==l.pTail) l.pTail = q; delete p; return 1; } else return 0; } Chương 6: Danh sách liên kết
  70. DSLK đơn – Các thao tác cơ sở 70  Xĩa một node của danh sách  Xĩa node đầu của danh sách  Xĩa node sau node q trong danh sách  Xĩa node cĩ khố k Chương 6: Danh sách liên kết
  71. DSLK đơn – Các thao tác cơ sở 71  Thuật tốn: Hủy 1 phần tử cĩ khố k  Bước 1:  Tìm phần tử p cĩ khĩa k và phần tử q đứng trước nĩ  Bước 2:  Nếu (p!= NULL) thì // tìm thấy k  Hủy p ra khỏi ds: tương tự hủy phần tử sau q;  Ngược lại  Báo khơng cĩ k Chương 6: Danh sách liên kết
  72. DSLK đơn – Các thao tác cơ sở 72  Cài đặt: int removeNode (List &l, int k) Hủy 1 { Node *p = l.pHead; Tìm phần tử p cĩ khĩa k và phần tử Node *q = NULL; phần tử q đứng trước nĩ cĩ khố while (p != NULL) k { if (p->data == k) break; q = p; p = p->pNext; } if (p == NULL) { cout<<“Khơng tìm thấy k”; return 0;} else if (q == NULL) // thực hiện xĩa phần tử đầu ds là p else // thực hiện xĩa phần tử p sau q } Chương 6: Danh sách liên kết
  73. DSLK đơn 73  Các thao tác cơ bản  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Duyệt danh sách  Tìm kiếm một giá trị trên danh sách  Xĩa một phần tử ra khỏi danh sách  Hủy tồn bộ danh sách  Chương 6: Danh sách liên kết
  74. DSLK đơn – Các thao tác cơ sở 74  Hủy tồn bộ danh sách  Để hủy tồn bộ danh sách, thao tác xử lý bao gồm hành động giải phĩng một phần tử, do vậy phải cập nhật các liên kết liên quan:  Thuật tốn:  Bước 1: Trong khi (Danh sách chưa hết) thực hiện:  B1.1:  p = pHead;  pHead = pHead ->pNext; // Cho p trỏ tới phần tử kế  B1.2:  Hủy p;  Bước 2:  pTail = NULL; //Bảo đảm tính nhất quán khi xâu rỗng Chương 6: Danh sách liên kết
  75. DSLK đơn – Các thao tác cơ sở 75  Hủy tồn bộ danh sách: cài đặt void RemoveList (List &l) { Gọi hàm??? Node *p; while (l.pHead != NULL) { p = l.pHead; l.pHead = p->pNext; delete p; } l.pTail = NULL; } Chương 6: Danh sách liên kết
  76. DSLK đơn – Các thao tác cơ sở 76  Đếm số nút trong danh sách: int CountNodes (List l) { Gọi hàm??? int count = 0; Node *p = l.pHead; while (p!=NULL) { count++; p = p->pNext; } return count; } Chương 6: Danh sách liên kết
  77. DSLK đơn – Các thao tác cơ sở 77  Trích phần tử đầu danh sách Node* PickHead (List &l) { Gọi hàm??? Node *p = NULL; if (l.pHead != NULL){ p = l.pHead; l.pHead = l.pHead->pNext; p->pNext = NULL; if (l.pHead == NULL) l.pTail = NULL; } return p; } Chương 6: Danh sách liên kết
  78. Exercise 78  Write a program for buiding single linked list (Display menu)  Add one node at first  Add one node at last  Add many node at first  Add many node at last  Add one node after select node  Display List  Find one node  Select and display n(th) node  Display node count  Remove one node  Remove List  Get sum of all nodes  Inserting a new node in a sorted list Chương 6: Danh sách liên kết
  79. Danh sách liên kết đơn (DSLK đơn) 79  Khai báo  Các thao tác cơ bản trên DSLK đơn  Sắp xếp trên DSLK đơn Chương 6: Danh sách liên kết
  80. Sắp xếp danh sách 80 Cách tiếp cận:  Phương án 1: Hốn vị nội dung các phần tử trong danh sách (thao tác trên vùng data).  Phương án 2 : Thay đổi các mối liên kết (thao tác trên vùng link) Chương 6: Danh sách liên kết
  81. Sắp xếp danh sách Hốn vị nội dung các phần tử trong danh sách 81  Cài đặt lại trên danh sách liên kết một trong những thuật tốn sắp xếp đã biết trên mảng  Điểm khác biệt duy nhất là cách thức truy xuất đến các phần tử trên danh sách liên kết thơng qua liên kết thay vì chỉ số như trên mảng.  Do thực hiện hốn vị nội dung của các phần tử nên địi hỏi sử dụng thêm vùng nhớ trung gian chỉ thích hợp với các xâu cĩ các phần tử cĩ thành phần data kích thước nhỏ.  Khi kích thước của trường data lớn, việc hốn vị giá trị của hai phân tử sẽ chiếm chi phí đáng kể. Chương 6: Danh sách liên kết
  82. Sắp xếp bằng phương pháp đổi 82 chổ trực tiếp ( Interchange Sort ) void SLL_InterChangeSort ( List &l ) { for ( Node* p=l.first ; p!=l.last ; p=p->link ) for ( Node* q=p->link ; q!=NULL ; q=q->link ) if ( p->data > q->data ) Swap( p->data , q->data ); } Chương 6: Danh sách liên kết
  83. Sắp xếp đổi chổ trực tiếp 83 ( Interchange Sort ) l.last q l.first 12 2 8 1 5 p Chương 6: Danh sách liên kết
  84. Sắp xếp đổi chổ trực tiếp 84 ( Interchange Sort ) l.last q l.first 1 12 8 2 5 p Chương 6: Danh sách liên kết
  85. Sắp xếp đổi chổ trực tiếp 85 ( Interchange Sort ) l.last q l.first 1 2 12 8 5 p Chương 6: Danh sách liên kết
  86. Sắp xếp đổi chổ trực tiếp 86 ( Interchange Sort ) l.last q l.first 1 2 5 12 8 p Chương 6: Danh sách liên kết
  87. Sắp xếp đổi chổ trực tiếp 87 Dừng ( Interchange Sort ) l.last q l.first 1 2 5 8 12 p Chương 6: Danh sách liên kết
  88. Sắp xếp bằng phương pháp chọn trực tiếp 88( Selection sort ) void ListSelectionSort (LIST &l) { for ( Node* p = l.first ; p != l.last ; p = p->link ) { Node* min = p; for ( Node* q = p->link ; q != NULL ; q = q->link ) if ( min->data > q->data ) min = q ; Swap(min->data, p->data); } } Chương 6: Danh sách liên kết
  89. Sắp xếp bằng phương pháp chọn trực tiếp 89( Selection sort ) l.last min l.first 12 2 8 1 5 p Chương 6: Danh sách liên kết
  90. Sắp xếp bằng phương pháp chọn trực tiếp 90( Selection sort ) l.last min l.first 1 2 8 12 5 p Chương 6: Danh sách liên kết
  91. Sắp xếp bằng phương pháp chọn trực tiếp 91( Selection sort ) l.last min l.first 1 2 8 12 5 p Chương 6: Danh sách liên kết
  92. Sắp xếp bằng phương pháp chọn trực tiếp 92 ( Selection sort ) l.last min l.first 1 2 5 12 8 p Chương 6: Danh sách liên kết
  93. Sắp xếp bằng phương pháp chọn trực tiếp (93 Selection sort ) Dừng l.last min l.first 1 2 5 8 12 p Chương 6: Danh sách liên kết
  94. Sắp xếp bằng phương pháp nổi bọt 94 ( Bubble sort ) void SLL_BubleSort ( List l ) { Node* t = l.last ; for ( Node* p = l.first ; p != NULL ; p = p->link) { Node* t1; for ( Node* q=l.first ; p!=t ; q=q->link ) { if( q->data > q->link->data ) Swap( q->data , q->link->data ); t1 = q ; } t = t1; } Chương 6}: Danh sách liên kết
  95. Sắp xếp bằng phương pháp nổi bọt 95 ( Bubble sort ) l.last q->link l.first 12 2 8 1 5 q Chương 6: Danh sách liên kết
  96. Sắp xếp bằng phương pháp nổi bọt 96 ( Bubble sort ) l.last q->link l.first 2 8 1 5 12 q Chương 6: Danh sách liên kết
  97. Sắp xếp bằng phương pháp nổi bọt 97 ( Bubble sort ) l.last q->link l.first 2 1 5 8 12 q Chương 6: Danh sách liên kết
  98. Sắp xếp bằng phương pháp nổi bọt 98 ( Bubble sort ) l.last q->link l.first 1 2 5 8 12 q Chương 6: Danh sách liên kết
  99. Sắp xếp bằng phương pháp nổi bọt 99 ( Bubble sort ) Dừng l.last l.first 1 2 5 8 12 Chương 6: Danh sách liên kết
  100. Sắp xếp Thay đổi các mối liên kết 100  Thay vì hốn đổi giá trị, ta sẽ tìm cách thay đổi trình tự mĩc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn chỉ thao tác trên các mĩc nối (link).  Kích thước của trường link:  Khơng phụ thuộc vào bản chất dữ liệu lưu trong xâu  Bằng kích thước 1 con trỏ (2 hoặc 4 byte trong mơi trường 16 bit, 4 hoặc 8 byte trong mơi trường 32 bit )  Thao tác trên các mĩc nối thường phức tạp hơn thao tác trực tiếp trên dữ liệu. Cần cân nhắc khi chọn cách tiếp cận: Nếu dữ liệu khơng quá lớn thì nên chọn phương án 1 hoặc một thuật tốn hiệu quả nào đĩ. Chương 6: Danh sách liên kết
  101. Phương pháp lấy Node ra khỏi danh 101 sách giữ nguyên địa chỉ của Node q p 12 2 8 5 1 1 . q->link = p->link ; // p->link chứa địa chỉ sau p 2 . q->link = NULL ; // p khơng liên kết phần tử Node Chương 6: Danh sách liên kết
  102. Quick Sort : Thuật tốn 102 //input: xâu (first, last) //output: xâu đã được sắp tăng dần  Bước 1: Nếu xâu cĩ ít hơn 2 phần tử Dừng; //xâu đã cĩ thứ tự  Bước 2: Chọn X là phần tử đầu xâu L làm ngưỡng. Trích X ra khỏi L.  Bước 3: Tách xâu L ra làm 2 xâu L1 (gồm các phần tử nhỏ hơn hay bằng X) và L2 (gồm các phần tử lớn hơn X).  Bước 4: Sắp xếp Quick Sort (L1).  Bước 5: Sắp xếp Quick Sort (L2).  Bước 6: Nối L1, X, và L2 lại theo trình tự ta cĩ xâu L đã được sắp xếp. Chương 6: Danh sách liên kết
  103. Sắp xếp quick sort 103 1 first 8 4 5 2 6 Chương 6: Danh sách liên kết
  104. Quick sort : phân hoạch 104 1 first 8 X 4 5 2 6 Chọn phần tử đầu xâu làm ngưỡng Chương 6: Danh sách liên kết
  105. Quick sort : phân hoạch 105 first1 1 first 8 X 4 5 2 6 first2 Tách xâu hiện hành thành 2 xâu Chương 6: Danh sách liên kết
  106. Quick sort : phân hoạch 106 first1 1 first 8 X 4 5 2 6 first2 Tách xâu hiện hành thành 2 xâu Chương 6: Danh sách liên kết
  107. Quick sort : phân hoạch 107 first1 1 first 8 X 4 5 2 6 first2 Tách xâu hiện hành thành 2 xâu Chương 6: Danh sách liên kết
  108. Quick sort : phân hoạch 108 first1 1 first 8 X 4 5 2 6 first2 Tách xâu hiện hành thành 2 xâu Chương 6: Danh sách liên kết
  109. Quick sort 109 first1 1 first 8 X 4 5 2 6 first2 Sắp xếp các xâu l1, l2 Chương 6: Danh sách liên kết
  110. Quick sort 110 first1 ĐưaNốikết l1quả, X, vàol2 first 1 first 8 X 4 5 2 6 first2 Chương 6: Danh sách liên kết
  111. Nối 2 danh sách 111 void SListAppend(SLIST &l, LIST &l2) { if (l2.first == NULL) return; if (l.first == NULL) l = l2; else { l.first->link = l2.first; l.last = l2.last; } Init(l2); } Chương 6: Danh sách liên kết
  112. void SListQSort(SLIST &l) { NODE *X, *p; 112 SLIST l1, l2; if (list.first == list.last) return; Init(l1); Init(l2); X = l.first; l.first=x->link; while (l.first != NULL) { p = l.first; if (p->data data) AddFirst(l1, p); else AddFirst(l2, p); } SListQSort(l1); SListQSort(l2); SListAppend(l, l1); AddFirst(l, X); SListAppend(l, l2); } Chương 6: Danh sách liên kết
  113. Quick sort : nhận xét 113 Nhận xét:  Quick sort trên xâu đơn đơn giản hơn phiên bản của nĩ trên mảng một chiều  Khi dùng quick sort sắp xếp một xâu đơn, chỉ cĩ một chọn lựa phần tử cầm canh duy nhất hợp lý là phần tử đầu xâu. Chọn bất kỳ phần tử nào khác cũng làm tăng chi phí một cách khơng cần thiết do cấu trúc tự nhiên của xâu. Chương 6: Danh sách liên kết
  114. Nội dung 114  Giới thiệu  Danh sách liên kết đơn (Single Linked List)  Danh sách liên kết đơi (Double Linked List)  Danh sách liên kết vịng (Circular Linked List) Chương 6: Danh sách liên kết
  115. Danh sách liên kết đơi (DSLK đơi) 115  Là danh sách mà mỗi phần tử trong danh sách cĩ kết nối với 1 phần tử đứng trước và 1 phần tử đứng sau nĩ A B C D Chương 6: Danh sách liên kết
  116. DSLK đơi – Khai báo cấu trúc 116  Dùng hai con trỏ:  pPrev liên kết với phần tử đứng trước  pNext liên kết với phần tử đứng sau struct DNode { DataType data; DNode* pPre; // trỏ đến phần tử đứng trước DNode* pNext; // trỏ đến phần tử đứng sau }; struct DList { DNode* pHead; // trỏ đến phần tử đầu ds DNode* pTail; // trỏ đến phần tử cuối ds }; Chương 6: Danh sách liên kết
  117. DSLK đơi – Tạo nút mới 117  Hàm tạo nút: DNode* getNode ( DataType x) Gọi hàm?? { DNode *p; p = new DNode; // Cấp phát vùng nhớ cho phần tử if (p==NULL) { cout data = x; // Gán thơng tin cho phần tử p p->pPrev = p->pNext = NULL; return p; } Chương 6: Danh sách liên kết
  118. DSLK đơi – Thêm 1 nút vào ds 118  Cĩ 4 loại thao tác chèn new_node vào danh sách:  Cách 1: Chèn vào đầu danh sách  Cách 2: Chèn vào cuối danh sách  Cách 3 : Chèn vào danh sách sau một phần tử q  Cách 4 : Chèn vào danh sách trước một phần tử q Chương 6: Danh sách liên kết
  119. DSLK đơi – Thêm vào đầu ds 119 pHead pTail (3) (2) A B C D (1) X new_node new_node->pNext = l.pHead; // (1) l.pHead->pPrev = new_node; // (2) l.pHead = new_node; // (3) Chương 6: Danh sách liên kết
  120. DSLK đơi – Thêm vào đầu ds 120 void addHead (DList &l, DNode* new_node) { if (l.pHead==NULL) Gọi hàm?? l.pHead = l.pTail = new_node; else { new_node->pNext = l.pHead; // (1) l.pHead->pPrev = new_node; // (2) l.pHead = new_node; // (3) pTail } pHead } A B C D (3) (2) X (1) new_node Chương 6: Danh sách liên kết
  121. DSLK đơi – Thêm vào đầu ds 121 NODE* InsertHead(DLIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; AddFirst(l, new_ele) return new_ele; } pTail pHead A B C D (3) (2) X (1) Chương 6: Danh sách liên kết
  122. DSLK đơi – Thêm vào cuối ds 122 pHead pTail (3) A B C D (2) l.pTail->pNext = new_node; // (1) (1) X new_node->pPrev = l.pTail; // (2) l.pTail = new_node; // (3) new_node Chương 6: Danh sách liên kết
  123. DSLK đơi – Thêm vào cuối ds 123 void addTail (DList &l, DNode *new_node) { if (l.pHead==NULL) Gọi hàm?? l.pHead = l.pTail = new_node; else { l.pTail->pNext = new_node; // (1) new_node->pPrev = l.pTail; // (2) l.pTail = new_node; // (3) } } pTail pHead A B C D (1) (3) (2) X new_node Chương 6: Danh sách liên kết
  124. DSLK đơi – Thêm vào cuối ds 124 NODE* InsertTail(DLIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; AddTail(l, new_ele) return new_ele; } pTail pHead A B C D (1) (3) (2) X Chương 6: Danh sách liên kết
  125. DSLK đơi – Chèn vào sau q 125 pHead pTail q p A B C D (4) (2) (1) (3) X new_node Chương 6: Danh sách liên kết
  126. DSLK đơi – Chèn vào sau q 126 void addAfter (DList &l, DNode *q, DNode *new_node) { DNode *p = q->pNext; Gọi hàm?? if (q!=NULL) { new_node->pNext = p; //(1) if (p != NULL) p->pPrev = new_node; //(2) new_node->pPrev = q; //(3) q->pNext = new_node; //(4) if (q == l.pTail) l.pTail = new_node; } else addFirst (l, new_node); // chèn vào đầu ds } Chương 6: Danh sách liên kết
  127. DSLK đơi – Chèn vào sau q 127 void InsertAfter(DLIST &l, DNODE *q, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; AddAfter(l, q, new_ele) } Chương 6: Danh sách liên kết
  128. DSLK đơi – Chèn vào trước q 128 pTail p q pHead A B C D (4) (2) (1) (3) X new_node Chương 6: Danh sách liên kết
  129. DSLK đơi – Chèn vào trước q 129 void addBefore (DList &l, DNode q, DNode* new_node) { DNode* p = q->pPrev; Gọi hàm?? if (q!=NULL) { new_node->pNext = q; //(1) q->pPrev = new_node; //(2) new_node->pPrev = p; //(3) if (p != NULL) p->pNext = new_node; //(4) if (q == l.pHead) l.pHead = new_node; } else addTail (l, new_node); // chèn vào cuối ds } Chương 6: Danh sách liên kết
  130. DSLK đơi – Chèn vào trước q 130 void InsertBefore(DLIST &l, DNODE q, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; DNODE* p = q->pPrev; AddBefore(l, q, new_ele) } Chương 6: Danh sách liên kết
  131. DSLK đơi – Hủy phần tử 131  Cĩ 5 loại thao tác thơng dụng hủy một phần tử ra khỏi danh sách liên kết đơi:  Hủy phần tử đầu ds  Hủy phần tử cuối ds  Hủy một phần tử đứng sau phần tử q  Hủy một phần tử đứng trước phần tử q  Hủy 1 phần tử cĩ khĩa k Chương 6: Danh sách liên kết
  132. DSLK đơi – Hủy đầu ds 132 int removeHead (DList &l) { if ( l.pHead == NULL) return 0; DNode *p = l.pHead; l.pHead = l.pHead->pNext; l.pHead->pPrev = NULL; delete p; if (l.pHead == NULL) l.pTail = NULL; else l.pHead->pPrev = NULL; return 1; } Chương 6: Danh sách liên kết
  133. DSLK đơi – Hủy cuối ds 133 int removeTail (DList &l) { if (l.pTail == NULL) return 0; DNode *p = l.pTail; l.pTail = l.pTail->pPrev; l.pTail->pNext = NULL; delete p; if (l.pHead == NULL) l.pTail = NULL; else l.pHead->pPrev = NULL; return 1; } Chương 6: Danh sách liên kết
  134. DSLK đơi – Hủy phần tử sau q 134 int removeAfter (DList &l, DNode *q) { if (q == NULL) return 0; DNode *p = q ->pNext ; if (p != NULL) { q->pNext = p->pNext; if (p == l.pTail) l.pTail = q; else p->pNext->pPrev = q; delete p; return 1; } else return 0; } Chương 6: Danh sách liên kết
  135. DSLK đơi – Hủy phần tử trước q 135 int removeBefore (DList &l, DNode *q) { if (q == NULL) return 0; DNode *p = q ->pPrev; if (p != NULL) { q->pPrev = p->pPrev; if (p == l.pHead) l.pHead = q; else p->pPrev->pNext = q; delete p; return 1; } else return 0; } Chương 6: Danh sách liên kết
  136. DSLK đơi – Hủy phần tử cĩ khĩa k 136 int removeNode (DList &l, int k) { DNode *p = l.pHead; while (p != NULL) { if (p->data== k) break; p = p->pNext; } Chương 6: Danh sách liên kết
  137. DSLK đơi – Hủy phần tử cĩ khĩa k 137 if (p == NULL) return 0; // Khơng tìm thấy k DNode *q = p->pPrev; if (q != NULL) // Xĩa nút p sau q return removeAfter (l, q); else // Xĩa p là nút đầu ds  return removeHead (l); } Chương 6: Danh sách liên kết
  138. DSLK đơi – Nhận xét 138  DSLK đơi về mặt cơ bản cĩ tính chất giống như DSLK đơn  Tuy nhiên DSLK đơi cĩ mối liên kết hai chiều nên từ một phần tử bất kỳ cĩ thể truy xuất một phần tử bất kỳ khác  Trong khi trên DSLK đơn ta chỉ cĩ thể truy xuất đến các phần tử đứng sau một phần tử cho trước  Điều này dẫn đến việc ta cĩ thể dễ dàng hủy phần tử cuối DSLK đơi, cịn trên DSLK đơn thao tác này tốn chi phí O(n) Chương 6: Danh sách liên kết
  139. DSLK đơi – Nhận xét 139  Bù lại, xâu đơi tốn chi phí gấp đơi so với xâu đơn cho việc lưu trữ các mối liên kết. Điều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp. Như vậy ta cần cân nhắc lựa chọn CTDL hợp lý khi cài đặt cho một ứng dụng cụ thể Chương 6: Danh sách liên kết
  140. Nội dung 140  Giới thiệu  Danh sách liên kết đơn (Single Linked List)  Danh sách liên kết đơi (Double Linked List)  Danh sách liên kết vịng (Circular Linked List) Chương 6: Danh sách liên kết
  141. Danh sách liên kết vịng (DSLK vịng) 141  Là một danh sách liên kết đơn (hoặc đơi) mà phần tử cuối danh sách, thay vì mang giá trị NULL, trỏ tới phần tử đầu danh sách  Đối với danh sách vịng, cĩ thể xuất phát từ một phần tử bất kỳ để duyệt tồn bộ danh sách Chương 6: Danh sách liên kết
  142. DSLK vịng 142  Để biểu diễn, cĩ thể sử dụng các kỹ thuật biểu diễn như danh sách đơn (hoặc đơi) Tail Head A B X Z Y Tail Head A B C D Chương 6: Danh sách liên kết
  143. DSLK vịng – Tìm kiếm 143  Danh sách vịng khơng cĩ phần tử đầu danh sách rõ rệt, nhưng ta cĩ thể đánh dấu một phần tử bất kỳ trên danh sách xem như phân tử đầu xâu để kiểm tra việc duyệt đã qua hết các phần tử của danh sách hay chưa Chương 6: Danh sách liên kết
  144. DSLK vịng – Tìm kiếm 144 Node* Search (List &l, int x) { Node *p = l.pHead; do{ if (p->data== x) return p; p = p->pNext; } while (p != l.pHead); // chưa đi giáp vịng return p; } Chương 6: Danh sách liên kết
  145. DSLK vịng – Thêm vào đầu ds 145 void addHead (List &l, Node *new_node) { if (l.pHead == NULL) { l.pHead = l.pTail = new_node; l.pTail->pNext = l.pHead; } else { new_node->pNext = l.pHead; l.pTail->pNext = new_node; l.pHead = new_node; } } Chương 6: Danh sách liên kết
  146. DSLK vịng – Thêm vào cuối ds 146 void addTail (List &l, Node *new_node) { if (l.pHead == NULL) { l.pHead = l.pTail = new_node; l.pTail->pNext = l.pHead; } else { new_node->pNext = l.pHead; l.pTail->pNext = new_node; l.pTail = new_node; } } Chương 6: Danh sách liên kết
  147. DSLK vịng – Thêm sau nút q 147 void addAfter (List &l, Node *q, Node *new_node) { if (l.pHead == NULL) { l.pHead = l.pTail = new_node; l.pTail->pNext = l.pHead; } else { new_node->pNext = q->pNext; q->pNext = new_node; if (q == l.pTail) l.pTail = new_node; } } Chương 6: Danh sách liên kết
  148. DSLK vịng – Hủy nút đầu ds 148 int removeHead (List &l) { Node *p = l.pHead; if (p == NULL) return 0; if (l.pHead == l.pTail) l.pHead = l.pTail = NULL; else { l.pHead = p->pNext; if (p == l.pTail) l.pTail->pNext = l.pHead; } delete p; return 1; } Chương 6: Danh sách liên kết
  149. DSLK vịng – Hủy phần tử sau q 149 int removeAfter(List &l, Node *q) { if (q == NULL) return 0; Node *p = q ->pNext ; if (p == q) l.pHead = l.pTail = NULL; else{ q->Next = p->pNext; if (p == l.pTail) l.pTail = q; } delete p; return 1; } Chương 6: Danh sách liên kết