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

1. Sắp xếp chọn (selection sort)Sắp xếp chọn • Dãy A gồm n phần tử a0, a1, , an-1. • Mỗi bước xét một danh sách con chưa sắp xếp (unsorted sublist - USL). • Có n-1 bước: − Bước 0: USL 0 = {a0, a1, , an-1} − Bước 1: USL 1 = {a1, , an-1} − Bước n-2: USL n-1 = {an-2, an-1}Sắp xếp chọn (tiếp) • Mỗi bước: − Tìm phần tử nhỏ nhất amin trong US...

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

2. Sắp xếp nổi bọt (bubble sort)Sắp xếp nổi bọt • Mỗi bước duyệt qua các phần tử a0, a1, , ak • Tại mỗi phần tử ai (i < k): − So sánh a i với ai+1 − Đổi chỗ nếu chúng chưa đúng thứ tự • Sau mỗi bước, phần tử lớn nhất sẽ được đặt (“nổi bọt”) xuống cuối dãy (ak là max)Ví dụ sắp xếp nổi bọt • Ban đầu: 64, 25, 12, 22, 11 (k = n-1-0) • Sau bước...

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

Giới thiệu  Phép Băm (Hashing): Là quá trình ánh xạ một giá trị khóa vào một vị trí trong bảng.  Một hàm băm ánh xạ các giá trị khóa đến các vị trí ký hiệu: h  Bảng băm (Hash Table) là mảng lưu trữ các record, ký hiệu: HT  HT có M vị trí được đánh chỉ mục từ 0 đến M- 1, M là kích thước của bảng băm.  Bảng băm thích hợp cho các ứng dụn...

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

Hàng đợi ưu tiên • Chèn (insert) − Thời gian O(log N) • Xóa phần tử nhỏ nhất (deleteMin) − Thời gian O(log N)Cài đặt hàng đợi ưu tiên • Dùng danh sách liên kết: − insert mất thời gian O(1) − deleteMin mất thời gian O(N) • Dùng cây nhị phân tìm kiếm: − insert và deleteMin mất thời gian O(log N) − Tuy nhiên, cây nhị phân tìm kiếm quá phức t...

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

Cài đặt hàng đợi ưu tiên • Dùng danh sách liên kết: − insert (dùng pushFront) mất thời gian O(1). − deleteMin (quét tìm rồi xóa min) mất thời gian O(N). • Dùng cây nhị phân tìm kiếm: − insert và deleteMin mất thời gian O(log N). − Tuy nhiên, cây nhị phân tìm kiếm quá phức tạp cho yêu cầu đơn giản hơn của hàng đợi ưu tiên. • Đống nhị phân (b...

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

Các thao tác trên cây cân bằng  Khi thêm hay xoá 1 nút trên cây, cĩ thể làm cho cây mất tính cân bằng, khi ấy ta phải tiến hành cân bằng lại.  Cây có khả năng mất cân bằng khi thay đổi chiều cao:  Lệch nhánh trái, thêm bên trái  Lệch nhánh phải, thêm bên phải  Lệch nhánh trái, hủy bên phải  Lệch nhánh phải, hủy bên trái  Cân bằng l...

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

So sánh các cấu trúc dữ liệu • So sánh thời gian tìm kiếm: − Vector và danh sách liên kết: O(n) − Cây AVL: O(log n) − Bảng băm: O(1)Hàm băm (hash function) • Ánh xạ khóa sang số nguyên (vị trí trong bảng băm). • Nếu nhiều khóa ánh xạ sang cùng một số nguyên (cùng vị trí trong bảng băm) thì sẽ dẫn đến đụng độ: − Đụng độ sẽ giảm nếu các khóa ...

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

Bảng băm • Các phần tử dưới dạng cặp khóa-giá trị (key-value) • Mỗi phần tử được lưu trữ vào một ô nào đó trong mảng tùy theo khóa của nó là gì • Thực hiện các phép tìm/chèn/xóa trong thời gian O(1) • Không hiệu quả với các thao tác đòi hỏi thông tin thứ tự: − VD: tìm phần tử lớn nhất và nhỏ nhất Ví dụ bảng băm Mỗi phần tử là một cặp khóa...

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

Định nghĩa B-tree Định nghĩa Một B-tree bậc m là cây nhiều nhánh tìm kiếm thỏa các điều kiện sau: (i) Tất cả các node lá cùng mức. (ii) Tất cả các node trung gian (trừ node gốc) có nhiều nhất m cây con và có ít nhất m/2 cây con (khác rỗng). (iii) Mỗi node hoặc là node lá hoặc có k+1 cây con (k là số khoá của node này). (iv) Node gốc có nhi...

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

Ðịnh nghĩa cây nhị phân tìm kiếm • Cây nhị phân • Bảo đảm nguyên tắc bố trí khoá tại mỗi nút: – Các nút trong cây trái nhỏ hơn nút hiện hành – Các nút trong cây phải lớn hơn nút hiện hành Ưu điểm của cây nhị phân tìm kiếm • Nhờ trật tự bố trí khóa trên cây : – Định hướng được khi tìm kiếm • Cây gồm N phần tử : – Trường hợp tốt nhất h = log...

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