Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Trần Minh Thái (Trường Đại học Hồng Bàng )

Chia sẻ: Bình Yên | Ngày: | Loại File: PPTX | Số trang:70

Thêm vào BST

Báo xấu

62
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách liên kết" cung cấp cho người học các kiến thức về: Đặt vấn đề, kiểu dữ liệu con trỏ, biến không động, kiểu con trỏ, biến động, danh sách liên kết. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Trần Minh Thái (Trường Đại học Hồng Bàng )

Chương 4. Danh sách liên kết Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: ngày 10 tháng 04 năm 2016
Mục tiêu • Nắm vững khái niệm về kiểu dữ liệu tĩnh và động • Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn • Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ 2
Vấn đề kiểu dữ liệu tĩnh 6 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 ? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng 3
Vấn đề kiểu dữ liệu tĩnh 6 ? Giả sử cần thêm tiếp 1 phần tử 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 9 Bổ sung 4 thêm
Bài tập Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên a, kích thước n, theo mẫu hàm như sau: void ChenX(int a[], int &n, int x, int vt); 5
Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 ? Làm sao để xóa phần tử 9 6
Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 7
Bài tập • Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau: void XoaX (int a[], int &n, int x); 8
Vấn đề kiểu dữ liệu tĩnh i Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n) 9
Vấn đề kiểu dữ liệu tĩnh • Giải quyết vấn đề phức tạp khi chèn/ xóa? • Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa? • Giải quyết vấn đề vùng nhớ không liên tục? • Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến? DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG 10
Biến tĩnh và biến động trong C++ • Biến tĩnh tên biến; • Vd: int a; float y; char s[20]; ü Tồn tại trong phạm vi khai báo ü Được cấp phát vùng nhớ trong vùng dữ liệu ü Kích thước cố định 11
Biến tĩnh và biến động trong C++ • Biến động *tên biến; • Vd: int *a; float *y; ü Chứa địa chỉ của một đối tượng dữ liệu ü Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào người lập trình ü Kích thước có thể thay đổi 12
Biến tĩnh và biến động trong C++ • Biến động ü Cấp phát bộ nhớ: new int [kích thước] ü Giải phóng bộ nhớ: delete vùng nhớ • Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng 13
Danh sách liên kết (DSLK) Các phần tử kết 1 dính với nhau bằng “sợi dây 7 liên kết” 2 6 3 10 8 5 9 14 4
1 7 2 6 3 10 8 Để đơn giản 5 hơn trong 9 việc minh họa 4 15
Đặc điểm DSLK • Một dãy tuần tự các nút (Node) • Giữa hai nút có con trỏ liên kết • Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ • Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) 16
Đặc điểm DSLK • Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết • Quản lý phần tử đầu tiên bằng con trỏ pHead • Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết 17
Cấu tạo của DSLK Node List pHead pTail 18
Cấu tạo của DSLK • Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHead • pHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi • Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail) • pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi 19
Cấu tạo của nút • Tạo lập bằng cách cấp phát bộ nhớ động • Mỗi nút có 2 thông tin: • Dữ liệu (data) • Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link) • Nếu không trỏ đến phần tử nào thì con trỏ Next = NULL 20