Bài giảng Cấu trúc dữ liệu và Giải thuật - Danh sách liên kết - Phạm Ngọc Nam

Danh sách liên kết 1 Giới thiệu Các loại danh sách liên kết Các thao tác trên danh sách So sánh các thực thi của danh sách So sánh danh sách liên kết và mảng 2 Tập có thứ tự.  Số lượng phần tử cố định (tĩnh).  Cấp phát vùng nhớ liên tục.  Truy xuất phần tử thông qua chỉ số. Giới thiệu Mảng: Cấu trúc dữ liệu quen thuộc 3 Truy xuất phần tử ?  Cập nhật ?  Chèn phần tử ?  Xóa phần tử ? Giới thiệu Đánh giá thao tác trên mảng: 4 không xác định chính xác số lượng phần tử  Danh sách bệnh nhân tăng/giảm.  Danh sách sinh viên tăng/giảm  Vùng nhớ thay đổi trong quá trình sử dụng. Không đủ vùng nhớ cấp phát liên tục. Cấu trúc dữ liệu động đáp ứng nhu cầu trên. Giới thiệu Thực tế: ? 5 Danh sách liên kết là một tập dữ liệu tuần tự mà mỗi phần tử(element) chứa vị trí của phần tử tiếp theo.  element = data + link  Ví dụ: Khái Niệm danh sách liên kết 6 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. Các loại danh sách liên kết 7Mỗi phần tử có một liên kết đến phần tử phía sau nó. Danh sách liên kết đơn 8Mỗi phần tử có hai liên kế đến phần tử đứng trước và sau nó. Danh sách liên kết kép 9 Là danh sách liên kết đơn và có mối liên kết giữa phần tử cuối và phần tử đầu. Danh sách liên kết vòng 10  Phần tử = dữ liệu + liên kết  Phần tử trên danh sách liên kết 11 Phần tử trên danh sách liên kết 12 Cài đặt  Phần tử có dữ liệu gồm 1 thành phần struct NODE{ dataType number;// dataType là kdl của number NODE * pNext; }; 13 Cài đặt  Phần tử có dữ liệu gồm 3 thành phần struct NODE { data type name; datatype id; dataType number; NODE * pNext; }; 14 Cài đặt  Phần tử có dữ liệu gồm 3 thành phần Ví dụ name kiểu char, id kiểu int, number kiểu float, ta có cấu trúc như sau: struct NODE { char name[50]; int id; float number; NODE * pNext; }; 15 Cài đặt  Phần tử có dữ liệu gồm một cấu trúc struct DATA struct NODE { { char name[50]; DATA data; int id; NODE *pNext; float number; }; }; 16 Tổ chức danh sách liên kết Mỗi danh sách liên kết bao gồm:  Con trỏ đến phần tử đầu (hoặc/và cuối ) danh sách o Con trỏ đến phần tử đầu: pHead o Con trỏ đến phần tử cuối: pTail  (Các) phần tử trên danh sách: o Dữ liệu o Các mối liên kết  Lưu ý: pHead, pTail không phải là một nút, nó chỉ là con trỏ chỉ đến nút. 17 Tổ chức danh sách liên kết  Ví dụ: quản lý bằng con trỏ đầu:  Ví dụ quản lý bằng con trỏ đầu và cuối: 18 Cấu tạo của danh sách liên kết  Quản lý danh sách bằng con trỏ đầu struct LIST{ NODE *pHead; int Count; };  Quản lý danh sách bằng con trỏ đầu và cuối struct LIST{ NODE *pHead; NODE *pTail; int Count; // số nút trong danh sách có thể ko cần nếu ko dùng }; 11/1/2016 19 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Cấu tạo của danh sách liên kết List // Linked Implementation of List (for Singly Linked List) head count // number of elements (optional). End List Singly Linked List head head data link 20 head count An empty Singly Linked List having only head. An empty Singly Linked List having head and count. 0 Signly linked list  Tạo lập danh sách rỗng  Kiểm tra danh sách rỗng  Kiểm tra số phần tử trong danh sách  Thêm một nút vào danh sách  Xóa một nút khỏi danh sách  Duyệt danh sách  Tìm một phần tử 11/1/2016 21 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên DSLK Đơn Before After List having head List having head and count head ? head head = NULL head count = ? ? head count = 0 head = NULL count = 0 22 Create an empty linked list 23 Create an empty linked list 11/1/2016 24 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Create an empty linked list Tạo lập danh sách rỗng 11/1/2016 25 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng ? Count pHead ?list Trước khi tạo lập 0 Count pHead list Sau khi tạo lập void InitList(LIST &L) { L.Count = 0; L.pHead = NULL; } Lưu ý: Luôn luôn khởi tạo danh sách rỗng trước khi sử dụng Create an empty linked list Kiểm tra danh sách rỗng Kiểm tra số phần tử trong danh sách 11/1/2016 26 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng int IsEmptyList(LIST L) { if(L.pHead == NULL) return 1; return 0; } int CountNode(LIST L) { return L.Count; } Check linked list 1. Allocate memory for the new node and set up data. 2. Locate the pointer p in the list, which will point to the new node:  If the new node becomes the first element in the List: p is head.  Otherwise: p is pPre->link, where pPre points to the predecessor of the new node. 27 head pNew x pPre pNew head x Insert Node to a Linked List 3. Update pointers:  Point the new node to its successor.  Point the pointer p to the new node. 28 head X pNew X pNew->link = pPre->link (1) pPre->link = pNew (2) pPre (1)(2) pNew->link = head (1) head= pNew (2) X head pNew X (1) (2) Insert Node to a Linked List Insert Node to a Linked List (cont.) Insertion is successful when allocation memory for the new node is successful. 29 Insert Node to a Linked List (cont.) There is no difference between  insertion in the middle (a) and insertion at the end of the list (b) (a) (b) 30 head X pNew X pNew->link = pPre->link (1) pPre->link = pNew (2) pPre (1)(2) pPre pNew head x Insert Node to a Linked List (cont.) There is no difference between  insertion at the beginning of the list (a) and insertion to an empty list (b). (a) (b) 31 pNew head pNew pNew->link = head (1) head= pNew (2) X head pNew X (1) (2) head Insert Algorithm Insert (val DataIn ) // For ordered list. Inserts a new node in a singly linked list. Pre DataIn contains data to be inserted Post If list is not full, DataIn has been inserted; otherwise, list remains unchanged. Return success or overflow. 32 InsertNode Algorithm (cont.) Insert (val DataIn ) 1. Allocate pNew 2. if (memory overflow) 1. return overflow 3. else 1. pNew->data = DataIn 2. Locate pPre // pPre remains NULL if Insertion at the beginning or to an empty list 3. if (pPre = NULL) // Adding at the beginning or to an empty list 1. pNew->link = head 2. head = pNew 4. else // Adding in the middle or at the end of the list 1. pNew->link = pPre->link 2. pPre->link = pNew 5. return success end Insert 33  Trước khi thêm  Sau khi thêm 11/1/2016 34 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng 1 15 Count pHead 99 pNew (1) (2) pNew Count pHead 152 99 Thêm một node vào đầu danh sách  Thêm một nút vào đầu DS (quản lý bằng con trỏ đầu)  Nếu danh sách rỗng thì L.pHead = pNew  Ngược lại:  pNew  pNext = L.pHead  L.pHead = pNew void AddFirst( LIST &L , NODE * pNew){ if(L.pHead == NULL) L.pHead = pNew; else { pNew  pNext = L.pHead; L.pHead = pNew; } } 11/1/2016 35 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn Cách 1 Cách 1.1  Thêm một nút vào đầu DS (quản lý bằng con trỏ đầu) void AddFirst( LIST &L , datatype x) { NODE * pNew = new NODE; pNew data = x; pNew pNext = NULL; if(L.pHead == NULL) L.pHead = pNew; else { pNew  pNext = L.pHead; L.pHead = pNew; } }11/1/2016 36 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn Cách 1.2  Thêm một nút vào đầu DS (quản lý bằng con trỏ đầu và cuối)  Nếu danh sách rỗng thì L.pHead = L.pTail = pNew  Ngược lại:  pNew  pNext = L.pHead  L.pHead = pNew void AddFirst( LIST &L , NODE * pNew) { if(L.pHead == NULL) L.pHead = L.pTail = pNew; else { pNew  pNext = L.pHead; L.pHead = pNew; } } 11/1/2016 37 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn Cách 2  Thêm một nút vào giữa DS. Sau nút pRev (ql bằng con trỏ đầu)  Trước khi thêm  Sau khi thêm 11/1/2016 38 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn 992 15 50 pNew (1) pPrev (2) 503 15 99 pPrev pNew Count pHead Count pHead  Thêm một nút vào giữa DS. Sau nút pRev(quản lý bằng con trỏ đầu ) void AddMid( LIST &L, NODE *pRev , NODE * pNew) { pNew  pNext = pRev pNext; pRev pNext = pNew; } void AddMid( LIST &L , NODE *pRev , DataType x) { NODE *pNew = new NODE; pNew  data = x; pNew  pNext = NULL; pNew  pNext = pRev pNext; pRev pNext = pNew; } 11/1/2016 39 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn Cách 1 Cách 2  Thêm 1 nút vào giữa DS. Sau nút pRev(ql bằng con trỏ đầu và cuối ) void AddMid( LIST &L, NODE *pRev , NODE * pNew) { pNew  pNext = pRev pNext; pRev pNext = pNew; if(pRev == L.pTail) L.pTail = pNew; } void AddMid( LIST &L, NODE *pRev , Datatype x) { NODE *pNew = new NODE; pNew  data =x; pNew  pNext = NULL; pNew  pNext = pRev pNext; pRev pNext = pNew; if(pRev == L.pTail) L.pTail = pNew; }11/1/2016 40 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn Cách 1 Cách 2  Thêm 1 nút cuối DSLK  Nếu DS rỗng thì L.pHead = L.pTail = pNew  Ngược lại:  L.pTail  pNext = Pnew  L.pTail = pNew 11/1/2016 41 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn 992 15 pTail Count pHead 50 pNew (1) (2) 992 15 pPrev Count pHead 50 L.pTail  pNext = pNew L.pTail = pNew Remove Node from a Linked List 1. Locate the pointer p in the list which points to the node to be deleted (pDel will hold the node to be deleted).  If that node is the first element in the List: p is head.  Otherwise: p is pPre->link, where pPre points to the predecessor of the node to be deleted. 42 pPre pDel pDel head head Remove Node from a Linked List (cont.) 2. Update pointers: p points to the successor of the node to be deleted. 3. Recycle the memory of the deleted node. head pDel X head pDel X pPre head = pDel->link Recycle pDel pPre->link = pDel->link Recycle pDel 43 Remove Node from a Linked List (cont.) Removal is successful when the node to be deleted is found. 44 Remove Node from a Linked List (cont.) There is no difference between Removal a node from the middle (a) and removal a node from the end (b) of the list. (a) (b) 45 head pDel X pPre head pDelpPre pPre->link = pDel->link Recycle pDel pDel X pPre head Remove Node from a Linked List (cont.) There is no difference between  removal the node from the beginning (a) of the list and removal the only-remained node in the list (b). (a) (b) 46 head pDel head pDel head pDel X head = pDel->link Recycle pDel RemoveNode Algorithm Remove (ref DataOut ) Removes a node from a singly linked list. Pre DataOut contains the key need to be removed. Post If the key is found, DataOut will contain the data corresponding to it, and that node has been removed from the list; otherwise, list remains unchanged. Return success or failed. 47 RemoveNode Algorithm (cont.) Remove (ref DataOut ) 1. Allocate pPre, pDel // pPre remains NULL if the node to be deleted is at the beginning of the list or is the only node. 2. if (pDel is not found) 1. return failed 3. else 1. DataOut = pDel->data 2. if (pPre = NULL) // Remove the first node or the only node 1. head = pDel->link 3. else // Remove the node in the middle or at the end of the list 1. pPre->link = pDel->link 4. recycle pDel 5. return success end Remove 48  Xóa một nút ở đầu DS  Trước khi xóa  Sau khi xóa 11/1/2016 49 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn (1) 992 15 pCurr Count pHead 1 99 Count pHead (2) L.pHead = pCurr pNext; delete pCurr;  Xóa một nút ở đầu DS (ql bằng con trỏ đầu)  Nếu pHead != NULL thì  Lấy nút ở đầu DS (pCurr) ra để xóa  Tách pCurr ra khỏi danh sách  Delete pCurr Void DeleteFirst(LIST &L) { NODE *pCurr; if(L.pHead != NULL) { pCurr = L.pHead; L.pHead = L.pHead pNext;// L.pHead=pCurr->pNext delete pCurr; } } 11/1/2016 50 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn  Xóa một nút ở đầu DS (ql bằng con trỏ đầu và cuối)  Nếu pHead != NULL thì  Lấy nút ở đầu DS (pCurr) ra để xóa  Tách nút ở đầu DS (pCurr) ra khỏi danh sách  Delete pCurr  Nếu pHead = NULL thì pTail = NULL: Xâu rỗng Void DeleteFirst(LIST &L) { NODE *pCurr; if(L.pHead != NULL) { pCurr = L.pHead; L.pHead = L.pHead pNext; delete pCurr; } if(L.pHead == NULL) L.pTail = NULL; } 11/1/2016 51 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn  Xóa 1 nút ở giữa DS. Sau nút pRev (ql bằng con trỏ đầu)  Trước khi xóa  Sau khi xóa 11/1/2016 52 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn 503 15 99 pCurrpPrev 2 15 99 pPrev Count pHead Count pHead pPrev  pNext = pCurr  pNext Delete pCurr  Xóa 1 nút ở giữa DS. Sau nút pRev (ql bằng con trỏ đầu) Void DeleteAfter_pPrev(LIST & L, NODE * pPrev) { NODE * pCurr; pCurr = pPrev  pNext;// lấy nút sau pPrev ra để xóa pPrev  pNext =pCurr  pNext; delete pCurr; } 11/1/2016 53 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn  Xóa 1 nút ở giữa DS. Sau nút pRev (ql bằng con trỏ đầu và cuối) Int DeleteAfter_pPrev(LIST & L, NODE * pPrev) { NODE * pCurr; if(pPrev == L.pTail) return 0; pCurr = pPrev  pNext; pPrev  pNext =pCurr  pNext; delete pCurr; if(pPrev pNext == NULL) L.pTail = pPrev; } 11/1/2016 54 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn  Xóa 1 nút trong DS ( tổng quát)  void DeleteNode(LIST & L, NODE * pPrev, NODE * PCurr) { if(pPrev == NULL) // xóa nút đầu L.pHead =pCurr  pNext; else // Xóa nút giữa pPrev pNext =pCurrpNext; delete pCurr; L.count --; } 11/1/2016 55 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn  Duyệt DSLK Đơn: là đi từ đầu DSLK cho đến cuối DSLK  Để đi từ đầu DSLK đến cuối DSLK ta sử dụng một biến con trỏ NODE để lần lượt giữ địa chỉ các NODE trong DSLK. void PrintList( LIST L) { NODE * pCurr = L.pHead; while( pCurr != NULL) { cout << pCurr  data; pCurr = pCurr  pNext; } }11/1/2016 56 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn  Duyệt DSLK Đơn: sử dụng vòng lặp for void PrintList( LIST L) { for(NODE * pCurr = L.pHead; pCur; pCurr  pNext) { cout << pCurr  data; pCurr = pCurr  pNext; } } 11/1/2016 57 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn pCurr !=NULL  Tìm một phần tử  Duyệt tuần tự từ đầu danh sách  Nếu gặp nút chứa khóa cần tìm  Stop và thông báo tìm thấy  Nếu đi đến cuối danh sách  Stop và thông báo không tìm thấy  Chi phí O(n) 11/1/2016 58 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn o Tìm một phần tử NODE * FindNode(LIST L, DataType key ) { NODE * pCurr = L.pHead;// bđ từ đầu DS while(pCurr != NULL) { if(pCurr  data == key) return pCurr; // tìm Thấy pCurr = pCurr  pNext;// chuyển đến nút kế } return NULL;// không tìm thấy } 11/1/2016 59 Bộ môn KHMT - Khoa CNTT - Trường ĐH Tôn Đức Thắng Các thao tác trên danh sách liên kết đơn