Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4.1 - Trần Minh Thái (2016)

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

Thêm vào BST

Báo xấu

66
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 các kiến thức giúp sinh viên 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#.

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.1 - Trần Minh Thái (2016)

Chương 4. Danh sách liên kết (Phần 1 – 3 tiế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 10 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# 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 phương thức (bằng ngôn ngữ C#) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên arr, theo mẫu như sau: class CMyIntArray{ int []arr; public void InsertX(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#) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên arr, theo mẫu sau: class CMyIntArray{ int []arr; public void DeleteX(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
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 11 4
1 7 2 6 3 10 8 Để đơn giản 5 hơn trong 9 việc minh họa 4 12
Đặ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ớ) 13
Đặ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 14
Cấu tạo của DSLK Node List pHead pTail 15
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 16
Thao tác chèn thêm node vào DSLK • “Kết nối” lại sợi dây liên kết theo trình tự List pHead pTail 17
Thao tác xóa node khỏi DSLK Cần xóa List pHead pTail 18
Các loại hình DSLK DSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới” 19
Các loại hình DSLK DSLK đôi: Các phần tử kết nối với nhau theo hướng “chiều đi tới và và đi lui” 20