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. | Cấu trúc dữ liệu amp 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 https tailieudientucntt 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 https tailieudientucntt 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 https tailieudientucntt 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 https tailieudientucntt Đặ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 https tailieudientucntt Đặ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 https tailieudientucntt Đặ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 https tailieudientucntt Đặt vấn đề 4 Ta tách rời các phần tử của mảng và kết nối chúng lại với nhau bằng một móc xích 10 20 30 Winter 2017 8 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Đặt vấn đề 5 Thao tác thêm phần tử chỉ cần thay đổi các mối liên kết tại chỗ 10 20 30 18 Chi phí O 1 Winter .
