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

- Các cấu trúc dữ liệu.
- Cấu trúc dữ liệu &.
- Các cấu trúc dữ liệu cơ bản.
- Danh sách liên kết đơn (Singly Linked List).
- Danh sách liên kết đôi (Doubly Linked List).
- Nếu muốn thêm (Insert) 1 phần tử vào mảng, phải làm sao.
- Phải di chuyển các phần tử về phía sau 1 vị trí.
- …rồi chèn phần tử mới vào.
- 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.
- 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.
- Thao tác thêm phần tử chỉ cần thay đổi các mối liên kết tại chỗ.
- Thao tác Thêm/Xóa không cần phải dịch chuyển phần tử.
- Kích thước cố định Số phần tử thay đổi tùy ý Các phần tử lưu trữ tuần tự.
- Các phần tử lưu trữ rời rạc, liên kết với nhau bằng con trỏ.
- Phải tịnh tiến các phần tử khi muốn Thêm/Xóa 1 phần tử - chi phí O(n).
- Chỉ cần thay đổi con trỏ liên kết khi muốn Thêm/Xóa 1 phần tử - chi phí O(1).
- Danh sách liên kết đơn (1).
- Danh sách liên kết đơn (2).
- Đếm số phần tử trong danh sách.
- Danh sách liên kết đơn (3).
- Danh sách liên kết đơn (4).
- Danh sách liên kết đôi (1).
- Danh sách liên kết đôi (2).
- Danh sách liên kết đôi (3).
- Danh sách liên kết đôi (4).
- Danh sách liên kết đôi (5).
- Dùng để lưu trữ nhiều phần tử dữ liệu.
- Thêm một phần tử vào đỉnh Stack (Push).
- Xóa một phần tử ở đỉnh Stack (Pop).
- Lấy phần tử ở đỉnh Stack mà không loại bỏ nó.
- Push: thêm 1 phần tử vào đỉnh Stack.
- Pop: lấy ra 1 phần tử ở đỉnh Stack.
- Khai báo biến stack S, và khởi tạo S có N phần tử.
- Lần lượt lấy các phần tử trong S ra và in lên màn hình.
- Cho mảng a chứa dãy số nguyên từ 1->N, hãy đảo ngược các phần tử của mảng a.
- Thêm 1 phần tử vào cuối Queue (EnQueue).
- Lấy ra 1 phần tử ở đầu Queue (DeQueue).
- Lấy phần tử ở đầu Queue mà không loại bỏ nó.
- EnQueue: thêm 1 phần tử vào cuối Queue.
- DeQueue: lấy ra 1 phần tử ở đầu Queue.
- Minh họa hình ảnh các phần tử đang chứa trong Queue.
- Cây nhị phân.
- Cài đặt cấu trúc dữ liệu.
- Chèn/xóa phần tử: O(1).
- Tìm kiếm: O(n).
- Cây nhị phân tìm kiếm.
- Thêm/xóa phần tử: O(log 2 n).
- Tìm kiếm: O(log 2 n).
- Node: là 1 phần tử trong cây.
- p i  <T>}.
- Cây nhị phân (binary tree).
- Cây nhị phân tìm kiếm (BST).
- Cài đặt cấu trúc dữ liệu BST.
- Tìm 1 phần tử trong cây nhị phân.
- Cài đặt cấu trúc dữ liệu BST (1).
- Cài đặt cấu trúc dữ liệu BST (2).
- Thay vì xóa trực tiếp node p, ta (i) tìm 1 phần tử thay thế cho p (gọi là phần tử p tt.
- Phần tử thay thế p tt.
- Cách 1: là phần tử lớn nhất trong cây con bên trái p.
- Cách 2: là phần tử nhỏ nhất trong cây con bên phải p.
- phần tử p tt sẽ có tối đa 1 cây con.
- Hai cách chọn phần tử thay thế cho p.
- Danh sách liên kết.
- Chi phí xóa phần tử O(log 2 n) O(n) O(1).
- Bộ nhớ sử dụng cho 1 phần tử.
- Một tập hợp nhiều phần tử.
- Mỗi phần tử có một “key”, là độ ưu tiên của phần tử đó.
- Thêm 1 phần tử vào queue và hiệu chỉnh vị trí (insert).
- Lấy phần tử nhỏ nhất (hay lớn nhất) và xóa nó (deleteMin).
- Lấy phần tử nhỏ nhất (hay lớn nhất) nhưng không xóa nó.
- Cài đặt cấu trúc dữ liệu (1).
- Cài đặt cấu trúc dữ liệu (2).
- Cài đặt cấu trúc dữ liệu (3).
- deleteMin: xóa phần tử ở đầu heap và Heapify.
- Bước 1: lấy phần tử ở đầu heap Bước 2: thay phần tử đầu heap bằng phần tử cuối heap.
- Bước 3: heapify phần tử đầu.
- Cài đặt cấu trúc dữ liệu (4).
- Cây nhị phân tìm kiếm cân bằng (1).
- Cây nhị phân tìm kiếm cân bằng (2).
- Cây nhị phân tìm kiếm cân bằng (3).
- Cây nhị phân tìm kiếm cân bằng (4).
- [Insert – Thêm 1 phần tử vào cây]: có thể làm cây mất cân bằng..
- Thêm phần tử 54 làm cây mất cân bằng tại node P.
- [Delete – Xóa 1 phần tử]: có thể làm cây mất cân bằng..
- Xóa phần tử 32 làm cây mất cân bằng tại node P.
- Chi phí thêm phần tử O(log 2 N).
- Tìm kiếm: O(log 2 N).
- Chi phí xóa phần tử O(log 2 N).
- Cấu trúc dữ liệu.
- phần tử).
- Cây 1001 nhánh, chỉ 3 mức  chứa hơn 1 tỉ phần tử.
- Mảng, Danh sách liên kết, BST,… tìm kiếm bằng cách so sánh lần lượt các phần tử  thời gian tìm kiếm.
- Nhiệm vụ của hàm băm là biến đổi khóa k của phần tử thành địa chỉ trong bảng băm..
- bảng T lưu phần tử đầu tiên + con trỏ của linked-list.
- Các cấu trúc dữ liệu khác:.
- Các phần tử chỉ lưu trong bảng T, không dùng thêm bộ nhớ mở rộng như phương pháp nối kết.
- Tên gọi “ open addressing ” mang ý nghĩa là địa chỉ (address) của phần tử không phải chỉ được xác.
- định bằng “ duy nhất ” hash value của phần tử đó, mà còn có sự can thiệp của phép “ dò tìm.
- Cho một dãy phần tử theo thứ tự như sau:.
- Hãy trình bày kết quả khi thêm các phần tử trên vào bảng băm, với lần lượt từng phương pháp xử lý đụng độ:

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt