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

DATA STRUCTURE AND ALGORITHM<br /> Linked List<br /> CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br /> Danh sách liên kết<br /> Dr. Dao Nam Anh<br /> <br /> Data Structure and Algorithm<br /> <br /> 1<br /> <br /> Resource - Reference<br /> Slides of James Joshi, modified by Dao Nam Anh.<br /> Major Reference:<br /> <br /> •<br /> <br /> Robert Sedgewick, and Kevin Wayne, “Algorithms”<br /> Princeton University, 2011, Addison Wesley<br /> <br /> •<br /> <br /> Algorithm in C (Parts 1-5 Bundle)- Third Edition by<br /> Robert Sedgewick, Addison-Wesley<br /> <br /> •<br /> <br /> Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.<br /> <br /> •<br /> <br /> Giải thuật và lập trình, Lê Minh Hoàng, Đại Học<br /> Sư Phạm, 2002<br /> Data Structure and Algorithm<br /> <br /> 2<br /> <br /> Sample function definition –Ví dụ định nghĩa hàm<br /> #include <br /> int lg(int);<br /> main() {<br /> int i, N;<br /> for (i = 1, N = 10; i 0; i++, N/= 2);<br /> return i;<br /> }<br /> Data Structure and Algorithm<br /> <br /> 3<br /> <br /> Data Structure – Cấu trúc dữ liệu<br /> <br /> •<br /> <br /> Sử dụng cấu trúc dữ liệu để quản lý tập các dữ<br /> liệu:<br />  Các thao tác với dữ liệu nào là cần thiết<br />  Triển khai các thao tác đó như thế nào<br /> <br /> •<br /> •<br /> <br /> Trong C ta dùng mảng, struct<br /> Ví dụ mảng trong C:<br /> <br /> int A1[N]; int A2[N][M]; char str[50];<br /> » A1[4]?<br /> <br /> A1[i] = *(A1+i)?<br /> <br /> Data Structure and Algorithm<br /> <br /> 4<br /> <br /> Linked List – Danh sách liên kết<br /> <br /> •<br /> •<br /> <br /> Mỗi phần tử của danh sách gọi là node (nút)<br /> <br /> •<br /> <br /> Các thao tác cơ bản<br /> <br /> Mỗi node có 2 thành phần: phần dữ liệu và phần<br /> liên kết chứa địa chỉ của node kế tiếp hay node<br /> trước nó<br />  Thêm một phần tử mới<br />  Xóa một phần tử<br />  Tìm kiếm<br /> <br /> h<br /> a<br /> <br /> e<br /> <br /> g<br /> <br /> m<br /> NULL<br /> <br /> Data Structure and Algorithm<br /> <br /> 5<br /> <br />