Bài giảng "Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu" cung cấp cho người học các kiến thức: Các cấu trúc dữ liệu cơ bản, cây nhị phân – Binary Trees, các cấu trúc dữ liệu nâng cao. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu - Nguyễn Tri Tuấn Cấu trúc dữ liệu & Giải thuật (Data Structures and Algorithms) Các cấu trúc dữ liệu Nguyễn Tri Tuấn Khoa CNTT – Email: nttuan@ LOGO Nội dung 1 Các cấu trúc dữ liệu cơ bản 2 Cây nhị phân – Binary Trees 3 Các cấu trúc dữ liệu nâng cao Winter 2017 2 (C) Nguyen Tri Tuan - Truong DHQG-HCM Các cấu trúc dữ liệu cơ bản (Fundamental Data Structures) Các danh sách liên kết – Linked Lists Ngăn xếp – Stack Hàng đợi - Queue Winter 2017 3 (C) Nguyen Tri Tuan - Truong DHQG-HCM Danh sách liên kết – Linked Lists Đặt vấn đề Danh sách liên kết là gì ? So sánh Mảng và Danh sách liên kết Danh sách liên kết đơn (Singly Linked List) Danh sách liên kết đôi (Doubly Linked List) Winter 2017 4 (C) Nguyen Tri Tuan - Truong DHQG-HCM Đặt vấn đề (1) Nếu muốn thêm (Insert) 1 phần tử vào mảng, phải làm sao ? 10 5 13 11 6 12 9 ? 18 Winter 2017 5 (C) Nguyen Tri Tuan - Truong DHQG-HCM Đặt vấn đề (2) Phải di chuyển các phần tử về phía sau 1 vị trí . 18 10 5 13 11 6 12 9 rồi chèn phần tử mới vào 10 5 18 13 11 6 12 9 Vậy chi phí là O(n) Winter 2017 6 (C) Nguyen Tri Tuan - Truong DHQG-HCM Đặt vấn đề (3) Tương tự, chi phí xóa 1 phần tử trong mảng cũng là O(n) Làm sao có thể thêm (hay xoá) 1 phần tử mà không phải di chuyển các phần tử khác ? Winter 2017 7 (C) Nguyen Tri Tuan - Truong DHQG-HCM Đặt .
