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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Danh sách liên kết" trình bày các kiến thức: Cấu trúc dữ liệu, danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết vòng. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
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 AnhDATA STRUCTURE AND ALGORITHMLinked ListCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTDanh sách liên kếtDr. Dao Nam AnhData Structure and Algorithm1Resource - ReferenceSlides 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 byRobert 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ọcSư Phạm, 2002Data Structure and Algorithm2Sample 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 Algorithm3Data 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, structVí dụ mảng trong C:int A1[N]; int A2[N][M]; char str[50];» A1[4]?A1[i] = *(A1+i)?Data Structure and Algorithm4Linked List – Danh sách liên kết••Mỗi phần tử của danh sách gọi là node (nút)•Các thao tác cơ bảnMỗi node có 2 thành phần: phần dữ liệu và phầnliên kết chứa địa chỉ của node kế tiếp hay nodetrước nó Thêm một phần tử mới Xóa một phần tử Tìm kiếmhaegmNULLData Structure and Algorithm5