TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

Mở đầu • Khi xây dựng cây nhị phân tìm kiếm, ta muốn có kiểu cây nào hơn? • Ví dụ: dựng cây từ dãy {3, 5, 8, 20, 18, 13, 22} Mở đầu (tiếp) • Ta muốn một cây nhị phân tìm kiếm cân đối: − có độ sâu của cây = log n, và do đó − cho phép chèn và xóa với thời gian chạy O(log n) trong mọi trường hợp. • Cây AVL là một kiểu cây như vậy! Cây AVL (A...

27 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 984 | Lượt tải: 1

Mở đầu • Khi xây dựng cây nhị phân tìm kiếm, ta muốn có kiểu cây nào hơn? • Ví dụ: dựng cây từ dãy {3, 5, 8, 20, 18, 13, 22} Mở đầu (tiếp) • Ta muốn một cây nhị phân tìm kiếm cân đối: − có độ sâu của cây = log N, và do đó − cho phép chèn và xóa với thời gian chạy O(log N) trong mọi trường hợp • Cây AVL là một kiểu cây như vậy!

26 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 761 | Lượt tải: 1

Định nghĩa • Xét trường hợp các phần tử có giá trị khác nhau • Cây nhị phân tìm kiếm là cây nhị phân, trong đó với mọi nút X: − Tất cả các giá trị trên cây con trái của X nhỏ hơn X − Tất cả các giá trị trên cây con phải của X lớn hơn X Các thao tác chính • Tìm phần tử nhỏ nhất • Tìm phần tử lớn nhất • Tìm phần tử x • Chèn phần tử x • X...

25 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 584 | Lượt tải: 1

Định Nghĩa Cây Cây là một tập hợp T các phần tử (gọi là nút của cây), trong đó có một nút đặc biệt gọi là nút gốc, các nút còn lại được chia thành những tập rời nhau T1, T2, ,Tn theo quan hệ phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta gọi là quan hệ cha – con.C Một Số Khái Niệ...

14 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 526 | Lượt tải: 1

Các Thao Tác Trên List Kép • Khởi tạo danh sách liên kết kép rỗng • Tạo 1 nút có thành phần dữ liệu = x • Chèn 1 phần tử vào danh sách – Chèn vào đầu – Chèn sau phần tử Q – Chèn vào trước phần tử Q – Chèn vào cuối danh sách • Huỷ 1 phần tử trong danh sách – Hủy phần tử đầu danh sách – Hủy phần tử cuối danh sách – Hủy 1 phần tử có khoá bằ...

20 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 537 | Lượt tải: 1

Duyệt cây biểu thức theo thứ tự trước • Xuất phát từ nút gốc. • Trình tự: thăm nút đang xét  duyệt con trái theo thứ tự trước  duyệt con phải theo thứ tự trước. • Đầu ra: biểu thức tiền tố. 29Xây dựng cây biểu thức • Xét trường hợp biểu thức hậu tố. (Ví dụ: a b + c d e + * *) • Cách xây dựng (dùng ngăn xếp): − Đọc từng toán hạng/toán tử ...

40 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 805 | Lượt tải: 1

Định nghĩa cây Cây là một tập nút: • Nếu tập nút rỗng, đó là cây rỗng • Nếu tập nút không rỗng: − Có một nút root được gọi là nút gốc − Có k cây con T1, T2, , Tk (k  0) sao cho nút gốc của mỗi cây con đó được nối với nút gốc root bằng một cạnh trực tiếp − root được gọi là nút cha, còn gốc của các cây con T1, T2, , T k được gọi là các nút c...

36 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 558 | Lượt tải: 1

1. Ngăn xếp Ngăn xếp • Một danh sách theo kiểu vào sau ra trước LIFO (Last In First Out) • Ba thao tác cơ bản (xảy ra ở đỉnh ngăn xếp): − push: Thêm phần tử − pop: Xóa phần tử − top: Truy nhập phần tử • Các thao tác khác: − Lấy kích thước − Kiểm tra rỗng Cài đặt ngăn xếp – cách 1 • Cài đặt bằng danh sách liên kết đơn: • Các thao tác: ...

34 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 570 | Lượt tải: 1

Tổ Chức Của DSLK Đơn Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách  Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần  Thành phần dữ liệu: Lưu trữ thông tin về bản thân phần tử  Thành phần liên kết: Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách Mỗi ph...

83 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 751 | Lượt tải: 1

1. Danh sách liên kếtDanh sách liên kết • Là một tập nút liên kết với nhau theo trật tự tuyến tính • Mỗi nút chứa: − một phần tử − một hoặc nhiều liên kết tới các nút lân cận • Các nút nằm rải rác trong bộ nhớ máy tính (trong khi các phần tử của mảng và vector nằm liên tục) 2. Danh sách liên kết đơnDanh sách liên kết đơn • Có một liên kết ...

33 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 634 | Lượt tải: 1