›
›

Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 3: Danh sách - Phạm Thanh An

ppt 72 trang ngocly 4040
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 3: Danh sách - Phạm Thanh An", để 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:

  • pptbai_giang_cau_truc_va_du_lieu_giai_thuat_chuong_3_danh_sach.ppt

Nội dung text: Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 3: Danh sách - Phạm Thanh An

  1. Chương 3 DANH SÁCH Ths. Phạm Thanh An Bộ môn Khoa học máy tính - Khoa CNTT Trường Đại học Ngân hàng TP.HCM LOGO
  2. Nội dung trình bày ❖ Danh sách và các phép toán trên danh sách ❖ Danh sách đặc ▪ Định nghĩa, Cách biểu diễn và các phép toán ▪ Ưu và nhược điểm của danh sách đặc ▪ Tổ chức Stack và Queue theo kiểu danh sách đặc ❖ Danh sách liên kết ▪ Khái niệm , Biểu diễn, Các phép toán ▪ Ưu và nhược điểm ▪ Tổ chức Stack và Queue theo kiểu danh sách liên kết ❖ Danh sách liên kết kép
  3. Danh sách ❖ Định nghĩa danh sách ▪ Danh sách là dãy hữu hạn có thứ tự bao gồm một số biến động các phần tử thuộc cùng một lớp đối tượng nào đó. ▪ Mô tả danh sách : L = (a1, a2, . . . ,an) ▪ Danh sách tuyến tính: là danh sách mà quan hệ lân cận giữa các phần tử được hiển thị
  4. Lưu trữ danh sách ❖Tổ chức lưu trữ danh sách trong bộ nhớ ▪ Sử dụng mảng - Danh sách đặc ▪ Đối tượng lớp - danh sách liên kết • Mỗi node là một đối tượng lớp
  5. Các phép toán trên danh sách ❖Thêm ❖Loại bỏ ❖Sắp xếp: ❖Tìm kiếm ❖Tách ❖Ghép ❖Duyệt:
  6. Danh sách đặc (condensed list) ❖ Định nghĩa ▪ Là danh sách có các phần tử được xếp kế tiếp nhau trong bộ nhớ a1 a2 a3 . an-1 an ❖ Đặc điểm ▪ d: chiều dài mỗi phần tử trong danh sách ▪ l0: địa chỉ của phần tử đầu tiên  địa chỉ của phần tử thứ i là: li=l0+(i-1)d
  7. Danh sách đặc (condensed list) ❖ Ưu điểm ❖ Nhược điểm
  8. Mảng danh sách đặc phổ biến ❖Mảng một chiều a[ ] Hình ảnh một biến Hình ảnh mảng ❖Khai báo: ▪ Cách 1: [] tên_mảng; ▪ Tên_mảng = new [size]; ▪ Ví dụ: • int[] myIntArray; myIntArray = new int[5]; • int[] numbers; numbers = new int[] {0,1,2,3,4};
  9. Mảng 2 chiều ❖ Mảng hai chiều a[,] ▪ Khai báo mảng 2 chiều: int[,] grades = new int[2,3]; // 2 hàng, 3 cột 0 1 4 1 2 5 ▪ Truy cập phần tử của mảng [dòng, cột]
  10. Khởi tạo mảng 2 chiều int[,] grades = new int[,] {{1, 82, 74, 89, 100}, {2, 93, 96, 85, 86}, {3, 83, 72, 95, 89}, {4, 91, 98, 79, 88}}
  11. Ví dụ cài đặt danh sách class CArray { private int [] arr; private int upper; private int numElements; public CArray(int size) { arr = new int[size]; upper = size-1; numElements = 0; }
  12. Mảng danh sách đặc phổ biến public void Insert(int item) { arr[numElements] = item; numElements++; } public void DisplayElements() { for(inti=0;i<= upper; i++) Console.Write(arr[i]+""); }
  13. Mảng danh sách đặc phổ biến static void Main() { CArray nums = new CArray(); for(inti=0;i<=49; i++) nums.Insert(i); nums.DisplayElements(); }
  14. Mảng danh sách đặc phổ biến static void Main() { CArray nums = new CArray(); Random rnd = new Random(100); for(inti=0;i<10; i++) nums.Insert((int)(rnd.NextDouble() * 100)); nums.DisplayElements(); }
  15. Cài đặt danh sách bằng mảng ❖ Thêm một phần tử vào mảng 10 5 13 11 5 8 13 ? 18 10 5 13 11 5 8 13 10 5 18 13 11 5 8 13
  16. Cài đặt danh sách bằng mảng ❖ Xóa phần tử ra khỏi mảng 10 5 18 13 11 5 8 ? 10 5 13 11 5 8 ? 10 5 13 11 5 8 ? ?
  17. Cài đặt danh sách bằng mảng ❖ Tìm kiếm phần tử trong mảng 13 10 5 13 11 5 8 ? ? 13 10 5 13 11 5 8 ? ? 13 10 5 13 11 5 8 ? ?
  18. Bài tập ▪ Nhập một dãy số nguyên từ bàn phím, và sắp xếp chúng theo thứ tự tăng dần Input: 5 2 4 18 9 1 Output: 1 2 4 5 9 18 ▪ Nhập một dãy số nguyên từ bàn phím, và cho biết số lần xuất hiện của từng số trong dãy số Input: 1 3 2 9 4 3 2 9 8 1 1 3 2 9 1 Ouput: (1,4) (2,3) (3,3) (4,1) (8,1) (9,3)
  19. Tổ chức Stack theo kiểu danh sách đặc Pop Push Top
  20. Tổ chức Stack theo kiểu danh sách đặc ❖Cấu trúc của STACK ▪ Dùng 1 mảng (StkArray) để chứa các phần tử ▪ Dùng 1 số nguyên (StkMax) để lưu số phần tử tối đa trong Stack ▪ Dùng 1 số nguyên (StkTop) để lưu chỉ số đỉnh của STACK
  21. Tổ chức Stack theo kiểu danh sách đặc
  22. Tổ chức Stack theo kiểu danh sách đặc ❖Các thao tác cơ bản trên Stack: ▪ Stack: khởi tạo Stack rỗng ▪ IsEmpty: kiểm tra Stack rỗng ? ▪ IsFull: kiểm tra Stack đầy ? ▪ Push: thêm 1 phần tử vào đỉnh Stack, có thể làm Stack đầy ▪ Pop: lấy ra 1 phần tử từ đỉnh Stack, có thể làm Stack rỗng
  23. Tổ chức Stack theo kiểu danh sách đặc
  24. Khao báo lớp Stack ❖ Thao tác “Khởi tạo Stack rỗng” class Cstack{ private int [] StkArr; private int StkTop; private int StkMax; public Cstack(int size) { StkArr = new int[size]; StkMax = size; StkTop = -1; // Stack rỗng }
  25. Kiểm tra Stack rỗng boolean IsEmpty() { if (StkTop == -1) return true; // Stack rỗng return false; // Stack không rỗng }
  26. Kiểm tra Stack đầy boolean IsFull() { if (StkTop == StkMax-1) return true; // Stack đầy return false; // Stack chưa đầy }
  27. Thêm một phần tử vào Stack boolean Push(int newitem) { if (IsFull()) return false; // Stack đầy, không thêm vào được StkTop++; StkArr[StkTop] = newitem; return true; // Thêm thành công }
  28. Lấy một phần tử ra khỏi Stack ❖ Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack boolean Pop(int outitem) { if (IsEmpty()) Return false; // Stack rỗng, không lấy ra được outitem = StkArr[StkTop]; StkTop ; return true; // Lấy ra thành công }
  29. Tổ chức Queue theo kiểu danh sách đặc ❖Queue là 1 cấu trúc dữ liệu: ▪ Gồm nhiều phần tử có thứ tự ▪ Hoạt động theo cơ chế “Vào trước – Ra trước” (FIFO – First In, First Out)
  30. Tổ chức Queue theo kiểu danh sách đặc Front Append Take
  31. Tổ chức Queue theo kiểu danh sách đặc ❖Cấu trúc của Queue ▪ Dùng 1 mảng (QArray) để chứa các phần tử ▪ Dùng 1 số nguyên (QMax) để lưu số phần tử tối đa trong hàng đợi ▪ Dùng 2 số nguyên (QFront, QRear) để xác định vị trí Đầu, Cuối hàng đợi ▪ Dùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi
  32. Tổ chức Queue theo kiểu danh sách đặc
  33. Tổ chức Queue theo kiểu danh sách đặc ❖Các thao tác trên Queue ▪ Queue: khởi tạo Queue rỗng ▪ IsEmpty: kiểm tra Queue rỗng ? ▪ IsFull: kiểm tra Queue đầy ? ▪ Append: thêm 1 phần tử vào cuối Queue, có thể làm Queue đầy ▪ Take: lấy ra 1 phần tử ở đầu Queue, có thể làm Queue rỗng
  34. Khai báo lớp Queue // Giả sử Queue chứa các phần tử kiểu nguyên (int) Class Queue { private int [] QArray; private int QMax; private int QNumItems; private int QFront; private int QRear;
  35. Khai báo lớp Queue // Khởi tạo Queue chứa các phần tử kiểu nguyên (int) public Queue(int size) { QArray = new int[size]; QMax = size; QFront = Qrear= -1; // Queue rỗng QNumItems = 0; // chưa có phần tử nào trong Queue }
  36. Kiểm tra Queue rỗng, đầy ❖ Thao tác “Kiểm tra Queue rỗng” boolean IsEmpty() { if (QNumItems==0) return true; // Queue rỗng return false; // Queue không rỗng } ❖ Thao tác “Kiểm tra Queue đầy” boolean IsFull() { if (QNumItems == QMax) return true; // Queue đầy return false; // Queue không đầy }
  37. Thêm 1 phần tử vào Queue ❖ Thao tác: thêm 1 phần tử vào cuối Queue boolean Append(int newitem) { if (IsFull()) return false; //Queue đầy, không thêm vào được QRear++; QArray[q.QRear] = newitem; // thêm phần tử vào cuối Queue QNumItems++; return true; // Thêm thành công }
  38. Lấy một phần tử ra khỏi Queue ❖ Thao tác Take: lấy ra 1 phần tử ở đầu Queue boolean Take(int itemout) { if (IsEmpty()) return false; // Queue rỗng, không lấy ra được itemout = QArray[QFront]; // lấy phần tử đầu ra QFront++; QNumItems ; if (QFront==QMax) // nếu đi hết mảng QFront = QRear = -1 ; // quay trở về đầu mảng return true; // lấy thành công }
  39. Hạn chế của Queue theo kiểu danh sách đặc ❖ Khi thêm nhiều phần tử, sẽ làm “tràn” mảng “Tràn giả” Queue Queue Front Rear [0] [1] [2] [3] [4] [5] [6] [7]
  40. Giải pháp ❖Giải pháp cho tình huống “tràn giả”: xử lý mảng như là 1 mảng vòng tròn Front Rear [0] [1] [2] [3] [4] [6]
  41. Tổ chức Queue theo kiểu danh sách đặc [2] [3] [2] [3] J2 J3 J8 J9 [1] J1 J4 [4][1] J7 [4] J5 J6 J5 [0] [5] [0] [5] front =0 front =4 rear = 5 rear =3
  42. Bài tập ❖Viết lại các giải thuật, bổ sung, lấy phần tử cho QUEUE nối vòng
  43. DANH SÁCH LIÊN KẾT ❖Đặt vấn đề: ▪ Nếu muốn chèn vào 1 phần tử vào mảng ? • Chi phí là O(n) ▪ Muốn xóa một phần tử trong mảng ? • Chi phí O(n)
  44. DANH SÁCH LIÊN KẾT ❖ Ta tách rời các phần tử của mảng, và kết nối chúng lại với nhau bằng một “móc xích” 15  5  7  6  3  15  5  7  6  3  12  15  5  7  6  3  12 
  45. DANH SÁCH LIÊN KẾT ❖ Một dãy tuần tự các nút (Node) ❖ Giữa hai nút có một tham chiếu ❖ 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ớ) ❖ Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử ❖ Quản lý danh sách bới con trỏ đầu pHead ❖ Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết
  46. DANH SÁCH LIÊN KẾT ❖Cấu tạo 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) • Tham chiếu liên kết đến phần tử kế tiếp trong danh sách (Next pointer link) Phần dữ 12  Phần liên liệu kết
  47. DANH SÁCH LIÊN KẾT ❖Cấu tạo nút : Gồm 2 thành phần public class Node { public Object Element; public Node Link; Nút có một public Node() { trường dữ liệu Element = null; Link = null; } public Node(Object theElement) { Element = theElement; Link = null; } }
  48. Cấu tạo của danh sách liên kết ❖Quản lý danh sách qua con trỏ đầu pHead, có thể thêm con tro cuối pTail ❖Có hai cách tổ chức danh sách ▪ pHead, pTail là một nút của danh sách ▪ pHead, pTail không phải là nút mà chỉ là con trỏ trỏ đến nút đầu và nút cuối của danh sách
  49. Cấu tạo của danh sách liên kết 15  5  12  7  6  3  pHead 15  5  12  7  6  3  pHead pTail
  50. ƯU VÀ NHƯỢC CỦA DANH SÁCH LIÊN KẾT ❖Ưu điểm ▪ Tận dụng được không gian nhớ để lưu trữ • Các nút không cần lưu trữ kế tiếp nhau • Có thể mở rộng kích thước tùy ý (phụ thuộc bộ nhớ) ▪ Việc thêm vào hay loại bỏ được tiến hành dễ dàng O(1) ▪ Dễ dàng kết nối hay phân rã danh sách ❖Nhược điểm ▪ Truy xuất tuần tự từng phần tử
  51. Các loại danh sách liên kết ❖ Danh sách liên kết đơn (Single-Linked list) ▪ Mỗi nút chỉ có 1 con trỏ liên kết (pNext) ❖ Danh sách liên kết đôi (Double-Linked list) ▪ Mỗi nút có 2 con trỏ liên kết (pPrev, pNext) ❖ Danh sách đa liên kết (Multi-Linked list) ▪ Mỗi nút có nhiều hơn 2 con trỏ liên kết ❖ Danh sách liên kết vòng (Circular-Linked list) ▪ Liên kết ở nút cuối cùng của danh sách chỉ đến nút đầu tiên trong danh sách
  52. Danh sách liên kết đơn ❖Mỗi nút, bao gồm hai phần, ▪ Phần Data: chứa dữ liệu, có thể nhiều hơn 1 trường ▪ Phần next: chỉ có duy nhất một liên kết đến nút kế tiếp ▪ Phần tử cuối cùng có liên kết NULL
  53. MẢNG & DANH SÁCH LIÊN KẾT ❖ Mảng ❖ Danh sách liên kết ▪ Phải biết trước số phần ▪ Số phân tử tùy biến tử ▪ Sử dụng con trỏ ▪ Lưu trữ tuần tự ▪ Khi chèn/xóa chỉ cần thay ▪ Khi chèn và xóa phải dịch đổi con trỏ liên kết chuyển các phần tử ▪ Truy xuất tuần tự ▪ Truy xuất qua chỉ mục
  54. Các thao tác trên danh sách liên kết đơn ❖Tạo lập danh sách rỗng ❖Kiểm tra danh sách rỗng ❖Đếm số phần tử trong danh sách ❖Thêm 1 nút vào danh sách ❖Xóa 1 nút khỏi danh sách ❖Duyệt danh sách ❖Tìm 1 phần tử trong danh sách
  55. Tạo lập danh sách rỗng public class LinkedList { protected Node header; public LinkedList() { header = new Node("header"); } }
  56. Tạo lập danh sách rỗng ❖Tạo lập danh sách rỗng void Init_List( Node pHead) { pHead = NULL; }
  57. Các thao tác trên danh sách liên kết đơn ❖Kiểm tra danh sách rỗng boolean IsEmptyList( pHead) { return (pHead ==NULL); } ❖Đếm số phần tử trong danh sách int CountNode(Node pHead){ int count = 0; Node p = pHead; while (p != NULL) { cout++ ; p = p.Link; } return cout; }
  58. Các thao tác trên danh sách liên kết đơn ❖Thêm một nút p vào đầu danh sách ▪ Nếu Danh sách rỗng Thì • Gán: pHead = p; ▪ Ngược lại • p.Link = pHead; • pHead = p; pHead A B C D E NULL p X
  59. Chèn nút P vào cuối Danh sách ❖ Chèn nút p vào cuối ▪ Nếu Danh sách rỗng Thì • Gán: pHead = p; ▪ Ngược lại • Gán q = pHead; • Đi về nút cuối của danh sách (while (q.Link != NULL) q = q.Link;) • q.Link = p; pHead A B C D E q X p
  60. Thêm một nút p vào vào sau nút q ▪ Nếu (q != NULL) • P.Link = q.Link; • Q.Link = p ; ▪ Ngược lại: q = p; q pHead A B C D E X p
  61. Các thao tác trên danh sách liên kết đơn ❖Xóa một nút khỏi danh sách ▪ Xóa nút đầu danh sách ▪ Xóa một nút đứng sau nút q ▪ Xóa một nút có khóa k
  62. Các thao tác trên danh sách liên kết đơn ❖Xóa nút đầu danh sách ▪ Nếu (pHead != NULL) thì • p = pHead;// p là nút cần xóa • pHead = pHead.Link; p pHead A B X Z Y
  63. Các thao tác trên danh sách liên kết đơn ❖ Xóa một nút p, đứng sau q ▪ Nếu (q!= NULL) thì • p = q.Next; // p là nút cần xóa • Q.Next = p.Next; // tách p ra khỏi ds • delete p; // Giải phóng p ▪ Ngược lại: • Xóa nút đầu danh sách q p pHead A B C D E
  64. Các thao tác trên danh sách liên kết đơn ❖Xóa một nút có khóa k ▪ Tìm nút p có khóa k và phần tử q đứng trước nó ▪ Nếu (p != NULL) // tìm thấy k • xóa p đứng sau nút q; ▪ Ngược lại – Báo không có k; Xóa nút có khóa là X q pHead A B X Z Y P
  65. Các thao tác trên danh sách liên kết đơn ❖Duyệt danh sách ▪ p = pHead; ▪ Trong khi chưa hết danh sách • Xử lý nút p ; • p= p.pNext; pHead A B C D E P
  66. Duyệt danh sách void TraverseList(Node pHead) { Node p = pHead; while (p !=NULL) { ; p = p.Link; // chuyển sang nút kế } }
  67. Bài tập ❖ Dùng danh sách liên kết quản lý sinh viên trong lớp (mssv, họ, tên, ngày sinh, điểm tổng kết học kỳ). ❖ Thực hiện các thao tác: thêm, bớt, sắp xếp sinh viên (theo điểm tổng kết) trong danh sách
  68. Danh sách liên kết vòng Head A B X Z Y ❖ Các thao tác trên danh sách liên kết vòng ▪ Giải thuật thêm một nút vào đầu danh sách ▪ Giải thuật thêm một nút vào danh sách ▪ Giải thuật loại một nút ra khỏi danh sách
  69. Danh sách liên kết kép ❖ Mỗi nút có 2 con trỏ liên kết: A B C D ❖ Khai báo:
  70. Danh sách liên kết kép ❖ Khi xóa 1 nút, không cần phải duyệt danh sách để tìm phần tử đứng trước ❖ Được sử dụng đối với các dữ liệu mà ta cần truy xuất theo cả 2 chiều: ❖Bài tập: Viết các giải thuật, khởi tạo, bổ sung, tìm kiếm, duyệt, xóa trên danh sách liên kết kép.
  71. Tổ chức STACK và QUEUE bằng danh sách liên kết ❖Sinh viên tự cài đặt. ▪ Tổ chức ngăn xếp (Stack) ▪ Tổ chức hàng đợi (Queue)