Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 3: Danh Sách Liên Kết - Nguyễn Hà Giang

Danh Sách Liên Kết - Linked List ThS. Nguyễn Hà Giang Khoa CNTT - Hutech Nguyen Ha Giang - 20082 Nội dung  Danh sách liên kết đơn  Giới thiệu  Cài đặt  Thao tác  Ứng dụng  Danh sách vòng  Danh sách liên kết kép Nguyen Ha Giang - 20083 Singly Linked List - Giới thiệu  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) 0 1 2 3 4 n-2 n-1 chèn Nguyen Ha Giang - 20084 Singly Linked List - Giới thiệu  Danh sách liên kết  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 xoá đơn giản Insert, Delete Nguyen Ha Giang - 20085 Singly Linked List - định nghĩa  DSLK đơn là chuỗi các node, được tổ chức theo thứ tự tuyến tính  Mỗi node gồm 2 phần:  Phần Data, information  Phần link hay con trỏ trỏ đến node kế tiếp Data Link Node Nguyen Ha Giang - 20086 Singly Linked List – Ôn pointer  Nhắc lại pointer int i, *pi; i 1FF0 ? pi 1FF4 ? pi = &i; pi 1FF4 1FF0 i 1FF0 ?*pi i = 10 hoặc *pi = 10 pi 1FF4 1FF0 i 1FF0 10*pi Nguyen Ha Giang - 20087 Singly Linked List – Minh hoạ  Mô tả DSLK A1 A2 A3 An Header Node Node Tail Node null Data Link Nguyen Ha Giang - 20088 Singly Linked List – Minh họa  VD: ‘D’ 500 ‘S’ 600 ‘L’ 300 ‘D’ null 700 700 500 600 300 Địa chỉ pHead Nguyen Ha Giang - 20089 Singly Linked List – Khai báo phần data  Khai báo DSLK - DataType  Kiểu dữ liệu định nghĩa trước  Chứa dữ liệu, thông tin của từng node typedef int DataType; typedef char DataType; typedef struct{ char Ten[30]; char MaSo[10]; DateTime NgaySinh; char Khoa[10]; }SinhVien; typedef SinhVien DataType; Nguyen Ha Giang - 200810 Singly Linked List – Khai báo phần Data typedef struct node { DataType info; struct node * next; }NODE; typedef struct node { int info; struct node * next; }NODE; typedef struct node { SinhVien info; struct node * next; }NODE; Cấu trúc node Nguyen Ha Giang - 200811 Singly Linked List – Khai báo DSLK  Khai báo và khởi tạo typedef struct node { DataType info; struct node * next; }NODE; typedef NODE * NodePtr; NodePtr pHead; pHead = NULL; pHead quản lý ds Khởi tạo dslk Nguyen Ha Giang - 200812 Singly Linked List – Thao tác cơ bản  Các thao tác cơ bản  Init  IsEmpty  FreeNode  NewNode  ShowList  InsertFirst  InsertAfter  DeleteFirst  DeleteAfter  Search  Sort Phần minh hoạ sẽ dùng DataType là int Nguyen Ha Giang - 200813 Singly Linked List – thao tác khởi tạo  Init: khởi động danh sách, ban đầu chưa có phần tử  NewNode: cấp phát một node cho ds, trả về địa chỉ node vừa cấp phát void Init(NodePtr *pHead) { *pHead = NULL; } NodePtr NewNode() { NodePtr newnode; newnode = (NodePtr) malloc(sizeof(NODE)); return newnode; } Nguyen Ha Giang - 200814 Singly Linked List- giải phóng node  FreeNode: giải phóng vùng nhớ cấp phát cho node  IsEmpty: kiểm tra danh sách rỗng void FreeNode(NodePtr p) { free(p); } int IsEmpty(NodePtr pHead) { return (pHead==NULL)? TRUE:FALSE; } Nguyen Ha Giang - 200815 Singly Linked List – In danh sách  ShowList: in toàn bộ danh sách void ShowList(NodePtr pHead) { NodePtr p; p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } } Nguyen Ha Giang - 200816 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000pHead p Nguyen Ha Giang - 200817 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 3000 pHead p Nguyen Ha Giang - 200818 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 3000 pHead p Nguyen Ha Giang - 200819 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 3000 pHead p Nguyen Ha Giang - 200820 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 5000 pHead p Nguyen Ha Giang - 200821 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 5000 pHead p Nguyen Ha Giang - 200822 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 5000 pHead p Nguyen Ha Giang - 200823 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 4000 pHead p Nguyen Ha Giang - 200824 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 4000 pHead p Nguyen Ha Giang - 200825 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 4000 pHead p Nguyen Ha Giang - 200826 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 NULL pHead p Nguyen Ha Giang - 200827 Singly Linked List – Minh họa in danh sách p = pHead; while (p!=NULL) { ShowNode(p); p = p->next; } 3000 “Tran” 5000 “Ngoc” 4000 “Thao” NULL 3000 5000 4000 NULL pHead p Kết thúc Nguyen Ha Giang - 200828 Singly Linked List – thêm vào đầu  Thêm vào đầu danh sách pHead pHead newnode new pHead newnode pHead newnode Nguyen Ha Giang - 200829 Singly Linked List – thêm vào đầu  InsertFirst: thêm nút có nội dung x vào đầu ds void InsertFirst(NodePtr &pHead, int x) { NodePtr node; node = NewNode(); node->info = x; node->next = pHead; pHead = node; } Nguyen Ha Giang - 200830 Singly Linked List – thêm vào sau 1 phần tử  Thêm vào sau node p trong danh sách p p newnode new p newnode p newnode Nguyen Ha Giang - 200831 Singly Linked List – thêm vào sau 1 phần tử  InsertAfter: thêm node có nội dung x sau node p void InsertAfter(NodePtr &p, int x) { NodePtr node; if (p == NULL) printf(“Cannot insert new node!”); else { node = NewNode(); node->info = x; node->next = p->next; p->next = node; } } Nguyen Ha Giang - 200832 Singly Linked List – Xoá phần tử đầu  Xoá phần tử đầu danh sách pHead pHead pHead pHead Nguyen Ha Giang - 200833 Singly Linked List – Xoá phần tử đầu  DeleteFirst: xóa node đầu tiên của danh sách void DeleteFirst(NodePtr &pHead) { NodePtr p; if (IsEmpty(pHead)) printf(“List is empty!”); else { p = pHead; pHead = pHead->next; FreeNode(p); } } Nguyen Ha Giang - 200834 Singly Linked List – Xoá phần tử sau 1 node  Xoá phần tử sau node p trong danh sách p q qp p Nguyen Ha Giang - 200835 Singly Linked List – Xoá phần tử sau 1 node  DeleteAfter: xoá node sau node p trong danh sách void DeleteAfter(NodePtr &p) { NodePtr q; if (p->next ==NULL) printf(“Cannot delete node!”); else { q = p->next; p->next = q->next; FreeNode(q); } } Nguyen Ha Giang - 200836 Singly Linked List – Xoá toàn bộ danh sách  Xoá toàn bộ danh sách pHead p pHead p Nguyen Ha Giang - 200837 Singly Linked List – Xoá toàn bộ danh sách pHead p pHead p Nguyen Ha Giang - 200838 Singly Linked List – Xoá toàn bộ danh sách pHead p pHead p Nguyen Ha Giang - 200839 Singly Linked List – Xoá toàn bộ danh sách pHead p pHead p pHead p pHead p Nguyen Ha Giang - 200840 Singly Linked List – Xoá toàn bộ danh sách  DeleteAll: xoá toàn bộ danh sách void DeleteAll(NodePtr &pHead) { NodePtr p; while (pHead!=NULL) { p = pHead; pHead = p->next; FreeNode(p); } } Nguyen Ha Giang - 200841 Singly Linked List – Tìm kiếm  Search: Tìm kiếm phần tử x trong danh sách NodePtr Search(NodePtr pHead, int x) { NodePtr p; p = pHead; while ( p != NULL && p->info != x) p = p->next; return p; } Nguyen Ha Giang - 200842 Singly Linked List - Sắp xếp  Sắp xếp ds theo thứ tự tăng dần, dùng Selection Sort void Sort(NodePtr &pHead) { NodePtr q, min, p = pHead; while (p!=NULL) { min = p; q = p; while (q!=NULL) { if (q->info info) min = q; q = q->next; } Swap(p->info, min->info); p = p->next; } } Nguyen Ha Giang - 200843 Singly Linked List – Bài tập bổ sung  Các thao tác bổ sung (SV cài đặt) 1. Thêm vào cuối danh sách 2. Sắp xếp danh sách theo phương pháp Interchange Sort 3. Xoá 1 phần tử có khoá là x 4. Thêm phần tử x vào ds đã có thứ tự (tăng) sao cho sau khi thêm vẫn có thứ tự (tăng). 5. Xoá các phần tử trùng nhau trong danh sách, chỉ giữ lại duy nhất một phần tử (*) 6. Trộn hai danh sách có thứ tự tăng thành một danh sách cũng có thứ tự tăng. (*) 7. Xác định vị trí của node x trong danh sách 8. Xác định kích thước của danh sách (số phần tử) 9. Chèn một phần tử có khoá x vào vị trí pos trong ds Nguyen Ha Giang - 200844 Nguyen Ha Giang - 200845 Circular Linked List  Tương tự như danh sách liên kết đơn.  Trường next của nút cuối chỉ đến đầu danh sách A1 A2 A3 An Trường Next của nút cuối ko còn trỏ đến NULL, mà trỏ đến nút đầu Nguyen Ha Giang - 200846 Circular Linked List  Mô tả CLL  Sử dụng pList trỏ đến phần tử cuối của danh sách A1 A2 A3 An Node Tail Node pList Nguyen Ha Giang - 200847 Circular Linked List  Khai báo & khởi tạo typedef struct node { DataType info; struct node * next; }NODE; typedef NODE * NodePtr; NodePtr pList; pList = NULL; pList trỏ nút cuối ds Khởi tạo dslk Nguyen Ha Giang - 200848 Circular Linked List  Các thao tác  InsertFirst  InsertLast  DeleteFirst  DeleteLast  ShowList  Search Nguyen Ha Giang - 200849 Circular Linked List  Chèn vào đầu – pList = NULL pList newnode new pList newnode pList newnode pList Nguyen Ha Giang - 200850 Circular Linked List  Chèn vào đầu – pList ≠ NULL pList pList newnode new pList newnode pList newnode Nguyen Ha Giang - 200851 Circular Linked List void InsertFirst(NodePtr &pList, int x) { NodePtr newNode; newNode = NewNode(); newNode->Info = x; if (pList == NULL){ pList = newNode; pList->next = pList } else { newNode->next = pList->next; pList->next = newNode; } } Nguyen Ha Giang - 200852 Circular Linked List  InsertLast: pList = NULL pList newnode new pList newnode pList newnode pList Nguyen Ha Giang - 200853 Circular Linked List  InsertLast: pList ≠ NULL pList pList newnode new pList newnode pList newnode Nguyen Ha Giang - 200854 Circular Linked List void InsertLast(NodePtr &pList, int x) { NodePtr newNode; newNode = NewNode(); newNode->Info = x; if (pList == NULL){ pList = newNode; pList->next = pList; } else { newNode->next = pList->next; pList->next = newNode; pList = newNode; } } Nguyen Ha Giang - 200855 Circular Linked List  DeleteFirst: pList->next = pList pList pList Nguyen Ha Giang - 200856 Circular Linked List  DeleteFirst: pList->next ≠ pList pList pList p pList p pList p Nguyen Ha Giang - 200857 Circular Linked List void DeleteFirst(NodePtr &pList) { NodePtr p; if (pList == NULL) return; else if (pList == pList->next) { FreeNode(pList); pList = NULL; } else { p = pList->next; pList->next = p->next; FreeNode(p); } } Nguyen Ha Giang - 200858 Circular Linked List  DeleteLast: pList->next = pList pList pList Nguyen Ha Giang - 200859 Circular Linked List  DeleteLast: pList->next ≠ pList pList pListq p pListq p pListq p Nguyen Ha Giang - 200860 Circular Linked List void DeleteLast(NodePtr &pList) { } Nguyen Ha Giang - 200861 Circular Linked List  ShowList:  Duyệt từ đầu danh sách  Đến khi nào quay lại phần tử đầu thì dừng void ShowList(NodePtr pList) { NodePtr p; if (pList == NULL ) return; p = pList->next; do { ShowNode(p); p = p->next; } while (p!=pList->next); } Nguyen Ha Giang - 200862 Circular Linked List 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 pList p p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); Nguyen Ha Giang - 200863 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 8000 pList p Nguyen Ha Giang - 200864 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 8000 pList p Nguyen Ha Giang - 200865 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 8000 pList p “Tran” Nguyen Ha Giang - 200866 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 5000 pList p “Tran” Nguyen Ha Giang - 200867 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 5000 pList p “Tran” true Nguyen Ha Giang - 200868 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 5000 pList p Tran Ngoc Nguyen Ha Giang - 200869 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 1000 pList p Tran Ngoc Nguyen Ha Giang - 200870 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 1000 pList p Tran Ngoc true Nguyen Ha Giang - 200871 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 1000 pList p Tran Ngoc Thao Nguyen Ha Giang - 200872 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 8000 pList p Tran Ngoc Thao Nguyen Ha Giang - 200873 Circular Linked List p = pList->next; do { ShowNode(p); p = p->next; } while (p != pList->next); 1000 “Tran” 5000 “Ngoc” 1000 “Thao” 8000 8000 5000 1000 8000 pList p Tran Ngoc Thao false Nguyen Ha Giang - 200874 Circular Linked List  Search:  Xuất phát từ đầu danh sách  Nếu tìm thấy trả về địa chỉ nút đó  Ngược lại qua phần tử tiếp theo  Điều kiện dừng khi quay lại phần tử đầu tiên  Không tìm thấy trả về NULL Nguyen Ha Giang - 200875 Circular Linked List NodePtr Search(NodePtr pList, int x) { NodePtr p; if (pList ==NULL) return NULL; p = pList->next; while (p->info != x && p != pList->next) p = p->next; if ( p->info == x) return p; return NULL; } Nguyen Ha Giang - 200876 Circular Linked List  Nối danh sách vòng pList2 vào pList 1 pList1 pList2 Nguyen Ha Giang - 200877 Circular Linked List  Nối danh sách vòng pList2 vào pList 1 pList1 pList2 pHead Nguyen Ha Giang - 200878 Circular Linked List  Nối danh sách vòng pList2 vào pList 1 pList1 pList2 pHead Nguyen Ha Giang - 200879 Circular Linked List  Nối danh sách vòng pList2 vào pList 1 pList1pList2 pHead Nguyen Ha Giang - 200880 Circular Linked List void AddList(NodePtr &pList1, NodePtr &pList2) { } Nguyen Ha Giang - 200881 Nguyen Ha Giang - 200882 Doubly Linked List  Cho phép di chuyển 2 chiều đến nút trước và sau.  Liên kết nút trước là: prev  Liên kết nút sau là: next  Nút đầu có prev là NULL  Nút cuối có next là NULL A1 A2 An Nguyen Ha Giang - 200883 Doubly Linked List  Khai báo typedef struct node { DataType info; struct node * prev; struct node * next; }NODE; typedef NODE * NodePtr; NodePtr pHead; pHead = NULL; pHead quản lý ds kép Khởi tạo dslk trỏ đến nút trước trỏ đến nút sau Nguyen Ha Giang - 200884 Doubly Linked List  Các thao tác cơ bản  NewNode, FreeNode, Init, IsEmpty  InsertFirst: chèn vào đầu  InsertPrev: chèn trước nút p  InsertNext: chèn sau nút p  DeleteFirst: xoá nút đầu  DeleteNode: xóa nút p  ShowList: duyệt ds  ShowReverse: duyệt từ cuối danh sách  ClearList: xoá toàn bộ ds Nguyen Ha Giang - 200885 Doubly Linked List  InsertPrev: chèn vào trước nút p p p newnewnode Nguyen Ha Giang - 200886 Doubly Linked List p newnode p Nguyen Ha Giang - 200887 Doubly Linked List void InsertPrev(NodePtr &pHead, NodePtr &p, int x){ NodePtr newnode, left; if (p == NULL) return; if (p ==pHead) InsertFirst(pHead,x); else { newnode = NewNode(); newnode->info = x; left = p->prev; newnode->prev = left; left->next = newnode; newnode->next = p; p->prev = newnode; } Nguyen Ha Giang - 200888 Doubly Linked List  DeleteNode: xoá nút p p p Nguyen Ha Giang - 200889 Doubly Linked List void DeleteNode(NodePtr &pHead, NodePtr &p) { NodePtr left, right; if (p == NULL) return; if (p==pHead) DeleteFirst(pHead); else { left = p ->prev; right = p->next; left->next = right; if (right != NULL) right->prev = left; FreeNode(p); } } Nguyen Ha Giang - 200890 Doubly Linked List  Các thao tác còn lại SV tự làm! Nguyen Ha Giang - 200891 Bài tập  Xây dựng cấu trúc danh sách liên kết đôi vòng  Mỗi nút trên danh sách có hai trường liên kết  Prev: trỏ đến nút trước  Next: trỏ đến nút sau  Nút cuối cùng trong danh sách có trường next là nút đầu tiên  Nút đầu tiên có trường prev là nút cuối cùng.  Các thao tác trên danh sách:  Init, IsEmpty, NewNode, FreeNode  InsertFrist, InsertLast, InsertPrev, InsertNext, InsertPos  DeleteFirst, DeleteLast, DeleteNext, DeletePrev, DeletePos  ShowList, ShowInvert  Search, Sort.  ClearList