Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: KDLTT danh sách cài đặt bằng danh sách liên kết

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: KDLTT danh sách cài đặt bằng danh sách liên kết

1. Bài 6: KDLTT danh sách cài đặt bằng danh sách liên kết Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Nội dung chính  Thư viện khuôn mẫu chuẩn STL  KDLTT danh sách  Khái niệm DSLK  Các phép toán trên DSLK 2 diepht@vnu
3. Thư viện khuôn mẫu chuẩn STL                   3 diepht@vnu
4. Ví dụ thư viện :: push_front() // list::push_front #include #include #include using namespace std; int main(){ list mylist(2,100); // 2 bien nguyen gia tri 100 mylist.push_front(200); mylist.push_front(300); cout ::iterator it; for (it=mylist.begin(); it!=mylist.end(); ++it) cout << ' ' << *it; cout << '\n'; getch(); return 0; } 4 diepht@vnu
5. Ví dụ thư viện :: pop_front() // list::pop_front #include #include #include using namespace std; int main(){ list mylist; mylist.push_back(100); mylist.push_back(200); mylist.push_back(300); cout << "Thuc hien pop_front cac phan tu trong mylist:"; while(!mylist.empty()){ cout << ' ' << mylist.front(); mylist.pop_front(); } cout << "\nKich thuoc cuoi cung cua mylist: " << mylist.size() << '\n'; getch(); return 0; } 5 diepht@vnu
6. Tra cứu tương tự  Trên  Các phép toán  push_back  pop_back  insert  erase 6 diepht@vnu
7. 3 cách để liên kết dữ liệu  Mảng: tập hợp các phần tử cùng kiểu  struct/class: tập hợp các thành phần có kiểu (có thể) khác nhau  Con trỏ 7 diepht@vnu
8. Các KDLTT đã học  KDLTT danh sách  KDLTT tập động  Phép toán  Phép toán  insert  insert  erase  erase  append  search  at  max  length  min  empty  length  Cài đặt  empty  mảng tĩnh  Cài đặt  mảng động  mảng động không được sắp  mảng động được sắp 8 diepht@vnu
9. KDLTT danh sách  Cài bằng mảng  Cài bằng danh sách liên  truy cập & cập nhật, at: kết O(1)  insert và erase hiệu  xen, insert: O(N) quả hơn  xóa, erase: O(N) 9 diepht@vnu
10. So sánh Mảng Danh sách liên kết Giống Các phần tử có cùng kiểu và có thứ tự Khác Bố cục logic giống với bố cục vật Bố cục logic không cần phải giống lý trong bộ nhớ máy tính với bố cục vật lý 10 diepht@vnu
11. Khái niệm  DSLK được tạo thành từ các nút [dữ liệu] [con trỏ]  mỗi nút gồm 2 phần  phần dữ liệu: chứa phần tử dữ liệu  phần con trỏ: chứa 1 địa chỉ  các nút liên kết với nhau thông qua con trỏ dữ liệu con trỏ dữ liệu con trỏ dữ liệu con trỏ Nội Bài Đà Nẵng Tân Sơn Nhất  11 diepht@vnu
12. DSLK bằng C++  Mỗi nút là một biến Node struct Node{  Nút cuối cùng có giá trị next Item data; bằng NULL Node * next;  Xác định DSLK bằng địa chỉ }; của nút đầu tiên trong danh sách  gọi biến lưu địa chỉ này là con trỏ đầu head Node * head = NULL;  khởi tạo danh sách rỗng: head Nội Bài Đà Nẵng Tân Sơn Nhất  12 diepht@vnu
13. DSLK bằng C++ struct Node{ Item data;  Có thể sử dụng thêm Node * next; }; con trỏ đuôi tail để các Node * head; thao tác trên DSLK Node * tail; được thuận lợi  danh sách rỗng head = tail = NULL; head tail Nội Bài Đà Nẵng Tân Sơn Nhất  13 diepht@vnu
14. typedef int Item; struct Node{ Item data; Node * next; }; struct SList{ Node * head; Node * tail; long size; SList(); ~SList(); Node* findPrevious(Node* p); Node* addFirst(const Item& v); Node* addLast(const Item& v); Node* insertAfter(Node* p, const Item& v); Node* insertBefore(Node* p, const Item& v); void removeFirst(); void remove(Node*& p); void print(); }; 14 diepht@vnu
15. Các phép toán trên DSLK  Thêm dữ liệu vào danh sách  Thêm vào đầu danh sách: addFirst(v)  Thêm vào sau nút p: insertAfter(p, v)  Thêm vào trước nút p: insertBefore(p, v)  Thêm vào cuối danh sách: addLast(v)  Xóa dữ liệu khỏi danh sách  Xóa nút đầu danh sách: removeFirst()  Xóa nút cuối danh sách: removeLast() ?  Xóa nút không phải đầu danh sách: remove(p)  Duyệt danh sách: traverse() 15 diepht@vnu
16. Thêm vào đầu danh sách head tail Nội Bài Đà Nẵng Tân Sơn Nhất  head tail x Đi ệnBiênPh ủ Nội Bài Đà Nẵng Tân Sơn Nhất  16 diepht@vnu
17. addFirst(v) Algorithm addFirst(v) Input dữ liệu v cần thêm vào đầu danh sách Output q new Node() {tạo nút mới} (*q).data  v {nút mới chứa dữ liệu v} (*q).next  head {nút mới chứa con trỏ đến nút head cũ} head  q {trỏ head đến nút mới} size  size + 1 {tăng biến đếm nút} cập nhật tail head tail x Đi ệnBiênPh ủ Nội Bài Đà Nẵng Tân Sơn Nhất  17 diepht@vnu
18. Thêm vào sau nút p head p tail Nội Bài Đà Nẵng Tân Sơn Nhất  p tail head Cam Ranh x Nội Bài Đà Nẵng Tân Sơn Nhất  18 diepht@vnu
19. insertAfter(p, v) Algorithm insertAfter(p, v) Input dữ liệu v cần thêm vào sau nút p trong danh sách Output q new Node() {tạo nút mới} (*q).data  v {nút mới chứa dữ liệu v} (*q).next  (*p).next {nút mới chứa con trỏ đến nút sau p} (*p).next  q {nút p chứa con trỏ đến nút mới} size  size + 1 {tăng biến đếm nút} cập nhật tail p tail head Cam Ranh x Nội Bài Đà Nẵng Tân Sơn Nhất  19 diepht@vnu
20. Thêm vào trước nút p head p tail Nội Bài Đà Nẵng Tân Sơn Nhất  head Phú Bài p tail x Nội Bài Đà Nẵng Tân Sơn Nhất  20 diepht@vnu
21. insertBefore(p, v) Algorithm insertBefore(p, v) Input dữ liệu v cần thêm vào trước nút p trong danh sách Output if p = head then addFirst(v) else tìm nút pre liền trước p insertAfter(pre, v) head Phú Bài p tail x Nội Bài Đà Nẵng Tân Sơn Nhất  21 diepht@vnu
22. Thêm vào cuối danh sách head tail Nội Bài Đà Nẵng Tân Sơn Nhất  head tail Phú Quốc  x Nội Bài Đà Nẵng Tân Sơn Nhất 22 diepht@vnu
23. addLast(v) Algorithm addLast(v) Input dữ liệu v cần thêm vào cuối trong danh sách Output q new Node() {tạo nút mới} (*q).data  v {nút mới chứa dữ liệu v} (*q).next  NULL {nút mới chứa con trỏ NULL} (*tail).next  q {nút tail cũ chứa con trỏ đến nút mới} tail  q {tail trỏ đến nút mới} size  size + 1 {tăng biến đếm nút} head tail Phú Quốc  Nội Bài Đà Nẵng Tân Sơn Nhất 23 diepht@vnu
24. Xóa nút đầu danh sách head tail Nội Bài Đà Nẵng Tân Sơn Nhất  head tail x Nội Bài Đà Nẵng Tân Sơn Nhất  24 diepht@vnu
25. removeFirst() Algorithm removeFirst() Input Output if head = null then báo lỗi: danh sách rỗng t  head head  (*head).next {trỏ head đến nút sau nó} delete t {giải phóng vùng nhớ trỏ bởi head cũ} size  size - 1 {giảm biến đếm nút} cập nhật tail head tail x Nội Bài Đà Nẵng Tân Sơn Nhất  25 diepht@vnu
26. Xóa nút không phải đầu danh sách head p tail Nội Bài Đà Nẵng Tân Sơn Nhất  head p tail x x Nội Bài Đà Nẵng Tân Sơn Nhất  26 diepht@vnu
27. remove(p) Algorithm remove(p) Input nút p cần xóa khỏi danh sách Output if p=head then removeFirst() else tìm nút pre liền trước p (*pre).next (*p).next {pre chứa con trỏ đến nút sau p} delete p {giải phóng vùng nhớ trỏ bởi p} size  size - 1 {giảm biến đếm nút} cập nhật tail head p tail x x Nội Bài Đà Nẵng Tân Sơn Nhất  27 diepht@vnu
28. Các dạng DSLK  DSLK đơn  singly linked list, uni-directional list, one-way list  DSLK kép  doubly linked list, bi-directional list  DSLK vòng tròn  ring list 28 diepht@vnu
29. head tail  Nội Bài Đà Nẵng Tân Sơn Nhất  head tail Nội Bài Đà Nẵng Tân Sơn Nhất 29 diepht@vnu
30. Cài đặt danh sách bởi DSLK  Sinh viên tự nghiên cứu chương 5.4, 5.5. 30 diepht@vnu
31. Câu hỏi  Hãy mô tả cấu trúc của DSLK được định nghĩa bởi đoạn mã sau. typedef struct Node ListNode; typedef struct Node ListNode; struct Node{ struct Node{ int data; int data; ListNode *next; ListNode* next; } } typedef struct FirstNode *LinkedList; typedef struct FirstNode* LinkedList; struct FirstNode{ struct FirstNode{ ListNode *first; ListNode* first; } } 31 diepht@vnu
32. Chuẩn bị tuần tới  Thực hành: Cài đặt các phép toán trên DSLK  Lý thuyết: Đọc chương 6, 7 giáo trình. 32 diepht@vnu