›
›

Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết - Võ Quang Hoàng Khang

pdf 68 trang huongle 2410
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết - Võ Quang Hoàng Khang", để 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:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat_chuong_3_danh_sach.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết - Võ Quang Hoàng Khang

  1. CHƯƠNG 3. DANH SÁCH LIÊN KẾT Võ Quang Hoàng Khang Email: vqhkhang@gmail.com
  2. Mục tiêu . Nắm vững khái niệm về kiểu dữ liệu tĩnh và động . Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn . Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ 2
  3. Vấn đề kiểu dữ liệu tĩnh 6 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 ? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng 3
  4. Vấn đề kiểu dữ liệu tĩnh 6 Giả sử cần thêm tiếp 1 phần tử ? 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 9 Bổ sung thêm 4
  5. Bài tập Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên a, kích thước n, theo mẫu hàm như sau: void ChenX(int a[], int &n, int x, int vt); 5
  6. Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 ? Làm sao để xóa phần tử 9 6
  7. Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 7
  8. Bài tập .Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau: void XoaX (int a[], int &n, int x); 8
  9. Vấn đề kiểu dữ liệu tĩnh Độ phức tạp của chèn/ xóa i trên mảng 1 chiều là O(n) 9
  10. Vấn đề kiểu dữ liệu tĩnh . Giải quyết vấn đề phức tạp khi chèn/ xóa? . Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa? . Giải quyết vấn đề vùng nhớ không liên tục? . Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến? DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG 10
  11. Biến tĩnh và biến động trong C++ . Biến tĩnh tên biến; . Vd: int a; float y; char s[20];  Tồn tại trong phạm vi khai báo  Được cấp phát vùng nhớ trong vùng dữ liệu  Kích thước cố định 11
  12. Biến tĩnh và biến động trong C++ . Biến động *tên biến; . Vd: int *a; float *y;  Chứa địa chỉ của một đối tượng dữ liệu  Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào người lập trình  Kích thước có thể thay đổi 12
  13. Biến tĩnh và biến động trong C++ . Biến động  Cấp phát bộ nhớ: new int [kích thước]  Giải phóng bộ nhớ: delete vùng nhớ . Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng 13
  14. Danh sách liên kết (DSLK) 1 Các phần tử kết dính với nhau bằng “sợi dây liên kết” 7 2 6 3 10 8 5 9 4 14
  15. 1 7 2 6 3 10 8 Để đơn giản 5 hơn trong việc 9 minh họa 4 15
  16. Đặc điểm DSLK .Một dãy tuần tự các nút (Node) .Giữa hai nút có con trỏ liên kết .Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ .Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) 16
  17. Đặc điểm DSLK .Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết .Quản lý phần tử đầu tiên bằng con trỏ pHead .Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết 17
  18. Cấu tạo của DSLK Node List pHead pTail 18
  19. Cấu tạo của DSLK .Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHead .pHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi .Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail) .pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi 19
  20. Cấu tạo của nút .Tạo lập bằng cách cấp phát bộ nhớ động .Mỗi nút có 2 thông tin: .Dữ liệu (data) .Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link) .Nếu không trỏ đến phần tử nào thì con trỏ Next = NULL 20
  21. Thao tác chèn thêm node vào DSLK .“Kết nối” lại sợi dây liên kết theo trình tự List pHead pTail 21
  22. Thao tác xóa node khỏi DSLK Cần xóa List pHead pTail 22
  23. Các loại DSLK DSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới” A B X Z Y 23
  24. Các loại hình DSLK DSLK đôi: Các phần tử kết nối với nhau theo hướng “chiều đi tới và và đi lui” A B C D 24
  25. Các loại hình DSLK Danh sách liên kết vòng: Các phần tử kết nối với nhau theo hướng “chiều đi tới” và phần tử cuối cùng có “đường đi vòng trở lại tới” phần tử đầu danh sách A B X Z Y A B C D 25
  26. So sánh Mảng và DSLK Mảng Danh sách liên kết Số phần tử thay đổi tùy Kích thước cố định ý Các phần tử lưu trữ tuần Các phần tử liên kết với tự (địa chỉ tăng dần) nhau bằng con trỏ trong bộ nhớ Phải dịch chuyển các Chỉ cần thay đổi con trỏ phần tử khi Thêm/Xóa liên kết khi Thêm/Xóa Truy xuất ngẫu nhiên Truy xuất tuần tự 26
  27. DSLK đơn pNext Data Cấu trúc 1 node List pHead pTail Data : Dữ liệu của node pNext : Con trỏ đến node kế tiếp pHead: Con trỏ đến node đầu pTail: Con trỏ đến node cuối 27
  28. Khai báo cấu trúc node pNext Data struct tNODE { Data; struct tNODE *pNext; }; typedef struct tNODE NODE; 28
  29. Khai báo cấu trúc node lưu số nguyên pNext 20 struct tNODE { int Data; struct tNODE *pNext; }; typedef struct tNODE NODE; 29
  30. Khai báo cấu trúc node lưu thông tin SV pNext ID, hoten, dtb struct tSinhVien { char ID[10], hoten[30]; float dtb; }; typedef struct tSinhVien SINHVIEN; struct tNODE { SINHVIEN Data; struct tNODE *pNext; }; typedef struct tNODE NODE; 30
  31. Khai báo cấu trúc DSLK đơn List pHead pTail struct tList { NODE *pHead, *pTail; }; typedef struct tList LIST; 31
  32. Khai báo cấu trúc DSLK đơn list pHead pTail struct tNODE struct tList { { int Data; NODE *pHead, *pTail; struct tNODE *pNext; }; }; typedef struct tList LIST; typedef struct tNODE NODE; 32
  33. Các thao tác trên DSLK đơn . Thêm 1 nút vào danh sách: đầu, cuối, sau ptử q . Duyệt danh sách . Xóa 1 nút: đầu, cuối, nút có giá trị x . Tìm 1 phần tử . Sắp xếp danh sách 33
  34. 1 Khai báo thư viện hàm 2 Khai báo cấu trúc danh sách liên kết 3 Khai báo các nguyên mẫu hàm 4 void main() { Tạo lập danh sách rỗng Nhập dữ liệu vào danh sách Các thao tác xử lý trên danh sách Hủy danh sách } 5 Cài đặt các hàm con 34 Cấu trúc tổng quát chương trình chương quát tổng trúc Cấu
  35. Tạo lập danh sách rỗng pHead và pTail pHead và pTail trỏ chưa xác định vào NULL (rỗng) List ? ? List pHead pTail pHead pTail Trước khi tạo lập Sau khi tạo lập void CreateEmptyList(LIST &L) { L.pHead = L.pTail = NULL; } 35
  36. Kiểm tra danh sách rỗng List pHead pTail Danh sách rỗng bool IsEmptyList(LIST L) { return ((L.pHead==NULL) && (L.pTail==NULL)); } 36
  37. Thêm một nút vào danh sách TH danh sách rỗng list.pHead = pNew list 30 pHead pTail list.pTail = pNew pNew if(IsEmptyList(list)) { list.pHead = list.pTail = pNew; } 37
  38. Thêm một nút vào danh sách TH danh sách đã có phần tử list 30 25 pHead pTail pNew Có 2 trường hợp để thêm pNew 1.Thêm pNew vào đầu (AddHead) 2.Thêm pNew vào cuối (AddTail) 38
  39. TH Thêm một nút vào đầu danh sách 2 1 list 30 25 pHead pTail pNew 39
  40. TH Thêm một nút vào đầu danh sách list 30 25 pHead pTail Vẽ lại list 25 30 pHead pTail 40
  41. TH Thêm một nút vào đầu danh sách Hãy vẽ lại “đường kết nối” theo ? thứ tự thích hợp khi thêm pNew vào đầu danh sách list 25 30 42 pHead pTail pNew 41
  42. TH Thêm một nút vào đầu danh sách 1 pNew->pNext = list.pHead 2 list.pHead = pNew 42
  43. TH Thêm một nút vào đầu danh sách Hãy viết hàm thêm phần tử pNew vào đầu danh sách (bằng ngôn ngữ C/C++), ? theo mẫu sau: void AddHead(LIST &L, NODE *pNew) 43
  44. TH Thêm một nút vào cuối danh sách list 30 1 25 pHead pTail pNew 2 1 list.pTail->pNext = pNew 2 list.pTail = pNew 44
  45. TH Thêm một nút vào cuối danh sách Hãy vẽ lại “đường kết nối” theo ? thứ tự thích hợp khi thêm pNew vào cuối danh sách list 30 25 42 pHead pTail pNew 45
  46. TH Thêm một nút vào cuối danh sách Hãy viết hàm thêm phần tử pNew vào cuối danh sách (bằng ngôn ngữ C/C++), ? theo mẫu sau: void AddTail (LIST &list, NODE *pNew) 46
  47. Nhập dữ liệu vào danh sách Nhập dữ liệu cho node Tạo con trỏ node Thêm node vào danh sách 47
  48. Nhập dữ liệu vào danh sách Để tạo node mới từ dữ liệu x có sẵn .Đưa dữ liệu có giá trị x vào phần Data .Con trỏ pNext trỏ đến NULL pNew->Data = x Data x pNew->pNext = NULL pNew 48
  49. Nhập dữ liệu vào danh sách VD hàm tạo và trả về con trỏ node có chứa giá trị nguyên x bằng ngôn ngữ C++ NODE *CreateNode (int x) { NODE *p; p = new NODE; if(p == NULL) { cout Data = x; p->pNext=NULL; return p; } 49
  50. Nhập dữ liệu vào danh sách VD hàm nhập dữ liệu cho danh sách số nguyên và đưa vào đầu danh sách void Input(LIST &list) { int x; NODE *pNew; CreateEmptyList(list); do{ cout >x; if(x==0) break; pNew=CreateNode(x); AddHead(list, pNew); }while(true); } 50
  51. Xuất dslk p List pHead pTail 51
  52. Chèn node vào DSLK đơn .Chèn vào sau node p 25 .Chèn vào trước node p p pNew list pHead pTail 52
  53. Chèn node vào sau node p p pNew list pHead pTail 53
  54. Các thao tác trên DSLK (tt) . . Xóa phần tử trong danh sách (đầu, cuối, giữa) . Sắp xếp danh sách
  55. Chèn node vào trước node p – Cách 1 pPrev p pNew list pHead pTail 55
  56. Chèn node vào trước node p – Cách 1 Hãy viết hàm tìm và trả về con trỏ node đứng trước con trỏ node p (bằng ngôn ? ngữ C/C++), theo mẫu sau: NODE *PrevNode (LIST list, NODE *p) 56
  57. Chèn node vào trước node p – Cách 2 Bước 1. Chèn pNew vào sau q Bước 2. Hoán vị giá trị pNew và q q pNew list pHead pTail 57
  58. Xóa một nút trong danh sách .Xóa nút đầu của danh sách Ảnh hưởng pHead .Xóa nút cuối của danh sách Ảnh hưởng pTail .Xóa nút giữa danh sách 58
  59. Xóa một nút trong danh sách .Xóa nút đầu của danh sách Cần xóa list 30 25 41 78 pHead pTail pDel NODE *pDel = list.pHead list.pHead = list.pHead->pNext delete pDel 59
  60. Xóa một nút trong danh sách Hãy viết hàm xóa nút đầu của danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: ? void DeleteHead (LIST &list) (lưu ý trường hợp danh sách chỉ còn 1 node trước khi xóa) 60
  61. Xóa một nút trong danh sách .Xóa nút cuối của danh sách Cần xóa pPrev pDel list 30 25 41 78 pHead pTail NODE *pDel = list.pTail NODE *pPrev = “Tìm node trước pTail” pPrev->pNext = NULL list.pTail = pPrev delete pDel 61
  62. Xóa một nút trong danh sách Hãy viết hàm xóa nút cuối của danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: ? void DeleteTail (LIST &list) (lưu ý trường hợp danh sách chỉ còn 1 node trước khi xóa) 62
  63. Xóa một nút trong danh sách .Xóa nút giữa của danh sách Cần xóa pPrev pDel list 30 25 41 96 78 pHead pTail NODE *pPrev = “Tìm node trước pDel” pPrev->pNext = pDel->pNext delete pDel 63
  64. Xóa một nút trong danh sách Hãy viết hàm xóa một node bất kỳ trong danh sách (bằng ngôn ngữ C/C++), ? theo mẫu sau: void DeleteNode (LIST &L, NODE *pDel) 64
  65. Xóa một nút trong danh sách Hãy viết hàm hủy toàn bộ danh sách ? (bằng ngôn ngữ C/C++), theo mẫu sau: void DestroyList (LIST &list) 65
  66. Bài tập Cài đặt các hàm sau trên dslk đơn số nguyên: 1. Đếm số lượng node trong dslk int DemSL(LIST list); 2. Tìm node có giá trị lớn nhất NODE* TimMax(LIST list); 3. Tìm node có giá trị x NODE* TimX(LIST list, int x); 4. In những node có giá trị chẵn void InChan(LIST list); 5. Tính giá trị trung bình các node lẻ float TBLe(LIST list); 66
  67. 6. Chèn node có giá trị x vào phía sau node có giá trị lớn nhất void ChenXSauMax(LIST &list, int x); 7. Xóa node có giá trị x bool XoaX(LIST &list, int x); 8. Sắp tăng dslk void SapTang(LIST &list); 67
  68. Sắp xếp void Doichotructiep ( LIST &L ) { Node *p,*q; for (p=L.DAU ; p!=L.CUOI ; p=p->tiep ) for (q=p->tiep; q!=NULL ; q=q->tiep) if ( p->dulieu > q->dulieu) Hoanvi( p->dulieu , q->dulieu ); } 68