Bài giảng Cấu trúc dữ liệu và giải thuật chương 4: Cấu trúc danh sách liên kết

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 4: Cấu trúc danh sách liên kết Đặt vấn đề: Những hạn chế biến kiểu mảng (kiểu dữ liệu tĩnh) sử dụng ở chương trước? Khai báo nhiều nhưng khi sử dụng ít  Thừa, kém hiệu quả trong sử dụng vùng nhớ (1) int a[100]; // Khai báo 100 phần tử nhưng nhiều lúc chỉ sử dụng 10 hoặc 20 phần tử. Ngược lại muốn sử dụng >100 phần tử thì làm sao?  Thiếu, mở code sửa lại chương trình!!! (2) int a[100]; // Khai báo 100 phần tử nhưng lúc chỉ sử dụng 120 phần tử. Đặt vấn đề: Những hạn chế biến kiểu mảng (kiểu dữ liệu tĩnh) sử dụng ở chương trước? Giả sử xóa phần tử trên mảng, hoặc thêm một phần tử thì làm thế nào? Thao tác xóa: Xóa xong phải dời lại Tốn kém quá!!! Thao tác chèn: Nới ra xong chèn vào  Cũng mất công sức quá!!! 44 55 12 42 94 18 06 67 44 55 12 42 94 18 06 67 X Đặt vấn đề: Những hạn chế biến kiểu mảng (kiểu dữ liệu tĩnh) sử dụng ở chương trước? Trong quá trình sử dụng nếu đến thời điểm nào đó đến khi kết thúc chương trình ta không sử dụng mảng đó nữa  không thể bỏ được.  Lãng phí bộ nhớ Giải quyết vấn đề Để sao vừa đủ sử dụng (không thừa cũng chẳng thiếu!) ta sử dụng cấp phát động …. int *a; //Khai báo mảng kiểu con trỏ int n; //Khai báo số phần tử thực tế sử dụng cout>n; a = new int[n]; //Cấp phát động cho mảng đúng n phần tử …. Giải quyết vấn đề Khi đến thời điểm không sử dụng nữa, ta xóa đi để sử dụng vùng nhớ cho việc khác …. delete a; //Xóa mảng a vừa cấp phát ở trên … Vậy thao tác thêm, xóa thì như thế nào?  Vẫn như cũ! Giải quyết như thế nào đây?? Giải quyết vấn đề Để khắc phục hạn chế trên người ta tổ chức dữ liệu theo kiểu móc nối (hay liên kết và gọi là danh sách liên kết) Vậy danh sách liên kết là gì? Danh sách liên kết Mỗi phần tử ngoài thành phần thông tin về dữ liệu còn chứa thêm liên kết đến phần tử tiếp theo trong danh sách Các phần tử của danh sách được cấp phát động nên không cần liên tục trong vùng nhớ như khai báo mảng. Hạn chế của danh sách liên kết!? Kiểu dữ liệu liên quan đến Danh sách liên kết: Kiểu con trỏ Kiểu con trỏ ứng với kiểu dữ liệu T là một kiểu dữ liệu của các đối tượng dùng để chứa địa chỉ vùng nhớ cho các đối tượng có kiểu T. Kiểu dữ liệu liên quan đến Danh sách liên kết: Kiểu con trỏ Khai báo biến: Item * item_ptr1, * item_ptr2; Tạo mới đối tượng: item_ptr1 = new Item; Sử dụng: *item_ptr1 = 1378; Hủy bỏ đối tượng: delete item_ptr1; Con trỏ NULL: item_ptr2 = NULL; Kiểu dữ liệu liên quan đến Danh sách liên kết: Kiểu con trỏ Gán con trỏ trong C++ Gán nội dung: bình thường Gán con trỏ: nguy hiểm Danh sách liên kết đơn Có nhiều loại danh sách liên kết (DSLK), như DSLK đơn, DSLK đối xứng, DSLK vòng, DS đa liên kết. Nhưng chúng ta chủ yếu nghiên cứu loại DSLK đơn như hình sau: Danh sách liên kết đơn Thiết kế node liên kết Định nghĩa kiểu dữ liệu typedef … DataType; struct Node {DataType Data; Node *Next; }; typedef Node *NodePtr; //Định nghĩa kiểu dữ liệu NodePtr là kiểu con trỏ của Node Các thao tác cơ bản trên kiểu DSLK đơn Khai báo một DSLK NodePtr List; Khởi tạo một DSLK rỗng void CreateEmptyList(NodePtr &List) { List=NULL; } Các thao tác cơ bản trên kiểu DSLK đơn Cấp vùng nhớ chứa dữ liệu x cho một nút DSLK. NodePtr CreateNodeList(DataType x) { NodePtr temp; temp= new Node; if (temp==NULL) coutData , x); temp->Next=NULL;} return temp; } Các thao tác trên danh sách liên kết Thêm Xóa Tìm kiếm Cập nhật ….