›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Danh sách liên kết - Đào Nam Anh

pdf 33 trang ngocly 3880
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Danh sách liên kết - Đào Nam Anh", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_bai_1_danh_sach_lie.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Danh sách liên kết - Đào Nam Anh

  1. DATA STRUCTURE AND ALGORITHM Linked List CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Danh sách liên kết Dr. Dao Nam Anh Data Structure and Algorithm 1
  2. Resource - Reference Slides of James Joshi, modified by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 2
  3. Sample function definition –Ví dụ định nghĩa hàm #include int lg(int); main() { int i, N; for (i = 1, N = 10; i 0; i++, N/= 2); return i; } Data Structure and Algorithm 3
  4. Data Structure – Cấu trúc dữ liệu • Sử dụng cấu trúc dữ liệu để quản lý tập các dữ liệu:  Các thao tác với dữ liệu nào là cần thiết  Triển khai các thao tác đó như thế nào • Trong C ta dùng mảng, struct • Ví dụ mảng trong C: int A1[N]; int A2[N][M]; char str[50]; » A1[4]? A1[i] = *(A1+i)? Data Structure and Algorithm 4
  5. Linked List – Danh sách liên kết • Mỗi phần tử của danh sách gọi là node (nút) • Mỗi node có 2 thành phần: phần dữ liệu và phần liên kết chứa địa chỉ của node kế tiếp hay node trước nó • Các thao tác cơ bản  Thêm một phần tử mới  Xóa một phần tử  Tìm kiếm h a e g m NULL Data Structure and Algorithm 5
  6. Linked List – Danh sách liên kết • Có nhiều kiểu tổ chức liên kết giữa các phần tử trong danh sách:  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 typedef struct node *link; struct node {char ch; link next;} h a e g m NULL Data Structure and Algorithm 6
  7. Linked List – Danh sách liên kết (đơn) • Insert - Chèn h a e g m NULL Data Structure and Algorithm 7
  8. Linked List – Danh sách liên kết (đơn) • Insert - Chèn t (t after x) f x h a e g m NULL Data Structure and Algorithm 8
  9. Linked List – Danh sách liên kết (đơn) • Insert - Chèn t (t after x) f x h a e g m NULL Data Structure and Algorithm 9
  10. Linked List – Danh sách liên kết (đơn) • Insert - Chèn t (t after x) f x h a e g m NULL Data Structure and Algorithm 10
  11. Linked List – Danh sách liên kết (đơn) • Insert - Chèn f h a e g m NULL Data Structure and Algorithm 11
  12. Linked List – Danh sách liên kết (đơn) • Delete - Xóa x h a e g m NULL Data Structure and Algorithm 12
  13. Linked List – Danh sách liên kết (đơn) • Delete - Xóa x (delete after x) h a e g m NULL Data Structure and Algorithm 13
  14. Linked List – Danh sách liên kết (đơn) • Delete - Xóa x (delete after x) h a e g m NULL Data Structure and Algorithm 14
  15. Linked List – Danh sách liên kết (đơn) • Delete - Xóa x (delete after x) h a e g m NULL Data Structure and Algorithm 15
  16. Linked List – Danh sách liên kết (đơn) • Delete - Xóa h a e m NULL Data Structure and Algorithm 16
  17. Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ (exchange nodes after t1 and t2) t1 t2 h a e g h m n Data Structure and Algorithm 17
  18. Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ (exchange nodes after t1 and t2) t1 t2 h a e g h m n Data Structure and Algorithm 18
  19. Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ (exchange nodes after t1 and t2) t1 t2 h a e g h m n Data Structure and Algorithm 19
  20. Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ (exchange nodes after t1 and t2) t1 t2 h a e g h m n Data Structure and Algorithm 20
  21. Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ (exchange nodes after t1 and t2) t1 t2 h a e g h m n Data Structure and Algorithm 21
  22. Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ (exchange nodes after t1 and t2) h a e g h m n Data Structure and Algorithm 22
  23. Linked List – Danh sách liên kết (đơn) t (t after x) Insert - Chèn • f x h a e g m NULL • Delete - Xóa x (delete after x) h a e g m NULL • Exchange – Đổi chỗ (exchange nodes after t1 and t2) h a e g h m t1 t2 Data Structure and Algorithm 23
  24. Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} h a b c g m NULL Data Structure and Algorithm 24
  25. Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} h a b c g m NULL (delete after h) Data Structure and Algorithm 25
  26. Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} t (insert t after x) fe h x a b c g m NULL Data Structure and Algorithm 26
  27. Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} t (insert t after x) fe h x a b c g m NULL Data Structure and Algorithm 27
  28. Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} t (insert t after x) fe h x a b c g m NULL Data Structure and Algorithm 28
  29. Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} fe h a b c g m NULL Data Structure and Algorithm 29
  30. Circular Linked List - Danh sách liên kết vòng h a b c g m h a b c g m Data Structure and Algorithm 30
  31. Circular Linked List - Danh sách liên kết vòng h a b c g m h a b c g m Data Structure and Algorithm 31
  32. Circular Linked List - Danh sách liên kết vòng h a b c g m h a b c g m Data Structure and Algorithm 32
  33. Discussion – Câu hỏi • structure-algorithm Data Structure and Algorithm 33