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

Data Structure and Algorithm 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 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 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 <= 6; i++, N *= 10) printf(“%7d %2d %9d\n, N, lg(i), N*lg(N)) } Int lg(int N){ int i; for (i = 0;N > 0; i++, N/= 2); return i; } Data Structure and Algorithm 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 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 NULL h a e g m Data Structure and Algorithm 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 NULL h a e g m typedef struct node *link; struct node {char ch; link next;} Data Structure and Algorithm 7 Linked List – Danh sách liên kết (đơn) • Insert - Chèn NULL a e g m h Data Structure and Algorithm 8 Linked List – Danh sách liên kết (đơn) • Insert - Chèn NULL a e g m f h t x (t after x) Data Structure and Algorithm 9 Linked List – Danh sách liên kết (đơn) • Insert - Chèn NULL a e g m f h t x (t after x) Data Structure and Algorithm 10 Linked List – Danh sách liên kết (đơn) • Insert - Chèn NULL a e g m f h t x (t after x) Data Structure and Algorithm 11 Linked List – Danh sách liên kết (đơn) • Insert - Chèn NULL a e g m f h Data Structure and Algorithm 12 Linked List – Danh sách liên kết (đơn) • Delete - Xóa NULL a e g m h x Data Structure and Algorithm 13 Linked List – Danh sách liên kết (đơn) • Delete - Xóa NULL a e g m h x (delete after x) Data Structure and Algorithm 14 Linked List – Danh sách liên kết (đơn) • Delete - Xóa NULL a e g m h x (delete after x) Data Structure and Algorithm 15 Linked List – Danh sách liên kết (đơn) • Delete - Xóa NULL a e g m h x (delete after x) Data Structure and Algorithm 16 Linked List – Danh sách liên kết (đơn) • Delete - Xóa NULL a e m h Data Structure and Algorithm 17 Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ a e g m t1 t2 h (exchange nodes after t1 and t2) h n Data Structure and Algorithm 18 Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ a e g m t1 t2 h (exchange nodes after t1 and t2) h n Data Structure and Algorithm 19 Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ a e g m t1 t2 h (exchange nodes after t1 and t2) h n Data Structure and Algorithm 20 Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ a e g m t1 t2 h (exchange nodes after t1 and t2) h n Data Structure and Algorithm 21 Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ a e g m t1 t2 h (exchange nodes after t1 and t2) h n Data Structure and Algorithm 22 Linked List – Danh sách liên kết (đơn) • Exchange – Đổi chỗ a e g mh (exchange nodes after t1 and t2) h n Data Structure and Algorithm 23 Linked List – Danh sách liên kết (đơn) • Insert - Chèn • Delete - Xóa • Exchange – Đổi chỗ NULL a e g m f h t NULL a e g m h x a e g m t1 t2 h x (delete after x) (t after x) (exchange nodes after t1 and t2) h Data Structure and Algorithm 24 Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} mgcba h NULL Data Structure and Algorithm 25 typedef struct node *link; struct node {char ch; link prev; link next;} Doubly Linked List - Danh sách liên kết đôi mgcb (delete after h) a h NULL Data Structure and Algorithm 26 Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} f t (insert t after x) mgcb e x a h NULL Data Structure and Algorithm 27 Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} f t (insert t after x) mgcb e x a h NULL Data Structure and Algorithm 28 Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} f t (insert t after x) mgcb e x a h NULL Data Structure and Algorithm 29 Doubly Linked List - Danh sách liên kết đôi typedef struct node *link; struct node {char ch; link prev; link next;} f mgcb e a h NULL Data Structure and Algorithm 30 Circular Linked List - Danh sách liên kết vòng mgcba h mgcba h Data Structure and Algorithm 31 Circular Linked List - Danh sách liên kết vòng mgcba h mgcba h Data Structure and Algorithm 32 Circular Linked List - Danh sách liên kết vòng mgcba h mgcba h Data Structure and Algorithm 33 Discussion – Câu hỏi • https://sites.google.com/site/daonamanhedu/data- structure-algorithm