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

Phép băm được đề xuất và hiện thực trên máy tính từ những năm 50 của thế kỷ 20. Nó dựa trên ý tưởng: biến đổi giá trị khóa thành một số (xử lý băm) và sử dụng số này để đánh chỉ cho bảng dữ liệu. Các phép toán trên các cấu trúc dữ liệu như danh sách, cây nhị phân, phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gia...

16 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2711 | Lượt tải: 2

Ý tưởng: Có dãy số: a1, a2, ., an Giải thuật QuickSort làm việc như sau: Chọn x là một phần tử làm biên: thường chọn là phần tử ở giữa dãy số. Phân hoạc dãy thành 3 dãy con 1. ak <= x , với k = 1.i 2. ak = x , với k = i.j 3. ak > =x , với k = j.N

15 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2612 | Lượt tải: 2

Các khai báo cần thiết là typedef . ElementType; //kiểu phần tử trong danh sách typedef struct Node { ElementType Element;//Chứa nội dung của phần tử Node* Next; /*con trỏ chỉđến phần tử kế tiếp trong danh sách*/ }; typedef Node* Position; // Kiểu vị trí typedef Position List;

29 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 3291 | Lượt tải: 1

Cây Đỏ -Đen (Red-Black) • Một thuật toán phức tạp • Cho O(log n) với Thêm(addition), Xóa(deletion) và Tìm(search) • Các kỹ thuật phần mềm • Biết về thuật toán • Biết khi nào có thể dùng chúng • Biết về hiệu suất • Biết nơi có thể áp dụng • Đủthông minh để dùng cho các máy phát minh. • Họ sử dụng lại bộ mã • Vì thế họ cần nhiều thời gian h...

28 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 3759 | Lượt tải: 2

Cây nhị phân O(log n) nếu nó là cây cân bằng • Cây nhịphân đơn giản tốt cho các mảng tĩnh • Tần xuất thấp (preferably zero) cho insertions/deletions Nhưng bộ dữ liệu của tôi có thể thay đổi! • Bộ dữ liệu động • Cần thiết phải tạo ra cây cân bằng • Đầu tiên, kiểm tra một vài hoạt động của cây cơ bản. • Hữu ích trong một vài cách!

37 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2290 | Lượt tải: 1

• Tìm kiếm tuần tự • Thời gian tồi nhất là n • Chúng tôi có Độ phức tạp O(n) • Ứng dụng cho mảng (không sắp xếp) và danh sách liên kết • Tìm kiếm nhị phân • Ứng dụng cho dãy đã sắp xếp • Thời gian thực hiện thuật toán log2n • Độ phức tạp tính toán O(log n)

16 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2472 | Lượt tải: 1

Stacks là một dạng danh sách (mảng)đặc biệt vớingữ cảnh LIFO • Hai phép toán • int push( Stack s, void *item ); - Bổ xung một phần tử vào đỉnh của stack • void *pop( Stack s ); - Loại bỏ một phần tử từđỉnh của stack • Tương tựnhư một máy xếp đĩa • Các phép toán khác int IsEmpty( Stack s ); /* Return TRUE if empty */ void *Top( Stack s ); ...

11 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2527 | Lượt tải: 1

Mảng (Arrays) • Đơn giản, • Nhanhnhưng • Phải chỉ định một kích thước cụ thể tại thời điểm xây dựng mảng • Tuân thủ Luật Đầy (Murphy) • Xây dựng một mảng với không gian cho nbiến • n = Ước lượng chính chắn của bạn về số lượng biến sẽ sử dụng lớn nhất • Ngày mai, bạn có thể cần n+1 biến • Liệu có thể có một hệ thống mềm dẻo hơn?

18 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2530 | Lượt tải: 1

Quicksort • Sử dụng tốt cho hầu hết các hệ thống, ( kể cảtrườnghợp hệ thống có thời gian thực hiện không bị ràng buộc) • Heap Sort • Chậm hơn quick sort, nhưng bảo đảm O(n log n) • Dùng cho các hệ thống thời gian thực (những hệ thống bị phê phán về thời gian thực hiện)

28 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2253 | Lượt tải: 1

Tìm kiếm tuần tự (tìm kiếm tuyến tính) – Thời gian tồi nhất để thực hiện giải thuật:n x constant – Tỷ suất tăng của giải thuật là n – Độ phức tạp thuật toán O(n)

81 trang | Chia sẻ: haohao89 | Ngày: 29/07/2013 | Lượt xem: 2375 | Lượt tải: 1