TAILIEUCHUNG - 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)

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ương 4. Danh sách liên kết (Phần 1 – 3 tiết) Trần Minh Thái Email: minhthai@ Website: Cập nhật: ngày 10 tháng 10 năm 2016 1 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 3 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 ? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng 6 3 Vấn đề kiểu dữ liệu tĩnh 4 1 2 3 4 5 6 7 8 9 10 5 7 3 9 2 15 1 6 Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử ? 4 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 ? Làm sao để xóa phần tử 9 6 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 6 Vấn đề kiểu dữ liệu tĩnh 7 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 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 9 Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n) i 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? 10 DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG 10 Danh sách liên kết (DSLK) 11 1 7 2 6 3 10 8 5 9 4 Các phần tử kết dính với nhau bằng “sợi dây liên kết” 12 1 7 2 6 3 10 8 5 9 4 Để đơn giản hơn trong việc minh họa 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ÀI LIỆU MỚI ĐĂNG
13    157    1    23-12-2024
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.