cấu trúc dữ liệu và thuật toán

- Khi thiết kế thuật toán để giải quyết một vấn đề, chúng ta cần phải sử dụng các đối tượng dữ liệu và các phép toán trên các đối tượng dữ liệu ở mức độ trừu tượng.
- 1 Chúng ta sẽ cài đặt các KDLTT bởi các lớp C.
- Chúng ta sẽ mô tả các đối tượng dữ liệu bằng cách sử dụng các ký hiệu, các khái niệm toán học và logic.
- 2 Trong phần 2 chúng ta sẽ nghiên cứu các CTDL cao cấp.
- Kiểu dữ liệu trừu tượng 21 1.3.1.
- Cài đặt kiểu dữ liệu trừu tượng 23 1.4.
- Các phép toán trên các dữ liệu đa chiều 367 14.2.
- Mỗi ngôn ngữ lập trình cung cấp cho chúng ta một số kiểu dữ liệu cơ bản (basic data types).
- là các cấu trúc dữ liệu (CTDL).
- Chẳng hạn, sử dụng con trỏ chúng ta có thể tạo nên các danh sách liên kết, hoăc các CTDL để biểu diễn cây.
- Giả sử chúng ta cần xác định CTDL biểu diễn các lớp học.
- Thiết kế thuật toán và cấu trúc dữ liệu.
- Giả sử chúng ta cần viết chương trình lập lịch thi.
- Trong mô tả trên, chúng ta đã sử dụng khái niệm danh sách (khái niệm dãy trong toán học).
- Để dễ dàng đưa ra thuật toán lập lịch, chúng ta sử dụng một mô hình dữ liệu khác: đồ thị.
- Khi thiết kế thuật toán như là một dãy các hành động trên các đối tượng dữ liệu, chúng ta cần sử dụng sự trừu tượng hoá dữ liệu (data abstraction).
- Chúng ta có thể sử dụng các phép toán của các KDLTT trong thiết kế thuật toán khi chúng ta biết rõ các điều kiện để phép toán có thể thực hiện và hiệu quả mà phép toán mang lại.
- Chúng ta sẽ nghiên cứu sự thiết kế và cài đặt một số KDLTT quan trọng nhất được sử dụng thường xuyên trong thiết kế thuật toán .
- Đặc tả đối tượng dữ liệu.
- Để mô tả chúng, chúng ta cần sử dụng sự trừu tượng hoá (chỉ quan tâm tới các đặc tính quan trọng, bỏ qua các chi tiết thứ yếu).
- Chúng ta có thể mô tả các CTDL trong một ngôn ngữ lập trình (chẳng hạn, C/ C.
- Chúng ta có thể biểu diễn một số phức bởi cấu trúc trong C.
- Sau khi đã chọn CTDL biểu diễn đối tượng dữ liệu, bước tiếp theo chúng ta phải thiết kế và cài đặt các hàm thực hiện các phép toán của KDLTT.
- Bước tiếp theo, chúng ta phải thiết kế thuật toán thực hiện công việc của hàm khi mà đối tượng dữ liệu được biểu diễn bởi CTDL đã chọn.
- Chúng ta ký hiệu tập đỉnh đó là.
- Chúng ta cần đến định nghĩa sau.
- Sau đây chúng ta xét xem, nếu tập dữ liệu được cài đặt dưới dạng cây đỏ - đen thì các phép toán tập động sẽ được thực hiện như thế nào.
- Giả sử chúng ta cần xen vào cây đỏ - đen một đỉnh mới v chứa dữ liệu là d.
- Giả sử chúng ta cần loại khỏi cây đỏ - đen đỉnh chứa dữ liệu với khoá là k.
- Giả sử chúng ta có một tập dữ liệu được lưu dưới dạng danh sách.
- Do đó, chúng ta có thể sử dụng các chiến lược heuristic sau đây để tổ chức lại danh sách mỗi khi ta thực hiện một phép toán trên danh sách.
- Chúng ta có thể đánh giá thời gian chạy trong trường hợp xấu nhất của một dãy phép toán bằng phương pháp đơn giản sau.
- Đặc biệt, chúng ta sẽ có điều đó nếu (D0.
- Trong mục này, chúng ta sẽ đưa vào một cấu trúc dữ liệu rất đặc biệt được sử dụng để cài đặt KDLTT tập động, đó là cây tán loe (splay tree).
- Giả sử chúng ta cần tìm dữ liệu có khoá k.
- Chúng ta ký hiệu W(v) là trọng số của đỉnh v, đó là số đỉnh của cây con gốc v.
- R(v)) Chúng ta lần lượt xét từng mẫu biến đổi.
- Bây giờ chúng ta đánh giá thời gian trả góp của một phép làm loe cây.
- Chúng ta sẽ 341 đưa ra các ví dụ ứng dụng hàng ưu tiên với phép toán hợp nhất trong chương nói về các thuật toán đồ thị.
- Bây giờ chúng ta xét xem các phép toán hợp nhất và giảm khoá được thực hiện như thế nào trên cây thứ tự bộ phận.
- Cách tốt nhất chúng ta có thể làm là xen từng đỉnh của cây P2 vào cây P1.
- Chúng ta cần sử dụng n2 phép toán Insert, mỗi phép toán này cần thời gian logarit theo số đỉnh trong cây P 1.
- Chúng ta cũng có thể thực hiện phương pháp hợp nhất trên bằng thuật toán đệ quy sau.
- Chúng ta có các nhận xét sau về phương pháp hợp nhất trên.
- Sau đây chúng ta sẽ cài đặt phép toán hợp nhất bởi hàm đệ quy.
- Chúng ta giả sử rằng, các đỉnh của cây nghiêng có cấu trúc sau: struct Node { keyType key.
- Các trường dữ liệu khác.
- Chúng ta đánh giá sự thay đổi tiềm năng khi thực hiện phép hợp nhất.
- Chúng ta thực hiện dãy phép toán xuất phát từ một họ các hàng ưu tiên chỉ có một phần tử.
- Chúng ta có một họ các tập con không cắt nhau của một tập đã cho.
- Chúng ta sẽ nghiên cứu cách cài đặt họ các tập con rời nhau sao cho hai phép toán hợp và tìm được thực hiện hiệu quả.
- 13.1 KIỂU DỮ LIỆU TRỪU TƯỢNG HỌ CÁC TẬP KHÔNG CẮT NHAU Giả sử chúng ta có một tập hữu hạn S gồm n đối tượng.
- Bây giờ chúng ta xét xem phép hợp được thực hiện như thế nào.
- Trong mục sau đây, chúng ta sẽ đưa ra cách cài đặt khác, trong cách cài đặt này phép hợp được thực hiện trong thời gian hằng.
- (b) Mảng cài đặt rừng cây trong hình (a) Nếu chúng ta biểu diễn các tập con bởi các cây hướng lên, thì phép hợp được thực hiện rất đơn giản.
- Giả sử chúng ta xuất phát từ họ n tập con một phần tử {0}, {1.
- Để cài đặt phép hợp theo trọng số, chúng ta cần lưu trọng số của các cây.
- Nếu chúng ta tiến hành một dãy phép toán gồm n phép hợp và m phép tìm, thì thời gian trong trường hợp xấu nhất là O(mlogn).
- Chúng ta sẽ ký hiệu quan hệ tương đương bởi.
- Một mê lộ Sau đây chúng ta sẽ trình bày một thuật toán thiết kế mê lộ.
- Chúng ta đánh số các phòng từ 0 đến p.
- chúng ta cần phải làm việc với các dữ liệu không phải một chiều.
- Trong chương này, chúng ta sẽ nghiên cứu các CTDL để biểu diễn tập dữ liệu điểm k - chiều.
- Ngoài các phép toán từ điển, trên các dữ liệu đa chiều, chúng ta còn cần đến một phép toán đặc biệt: tìm kiếm phạm vi (Range Search).
- Trước hết chúng ta cần đưa ra một cách biểu diễn văn bản.
- Bây giờ chúng ta có thể đưa ra định nghĩa cây 2-chiều.
- Sau đây chúng ta sẽ xét các phép toán từ điển: tìm kiếm, xen, loại và phép toán tìm kiếm phạm vi trên cây 2-chiều.
- Giả sử chúng ta cần xen vào cây 2-chiều T một đỉnh mới chứa điểm (x, y).
- Bây giờ chúng ta xét xem các phép toán tìm kiếm, xen, loại và phép toán tìm kiếm phạm vi được thực hiện như thế nào trên cây tứ phân.
- Để tìm kiếm (hoặc để xen vào) một điểm, chúng ta cần tìm miền chứa điểm đó.
- Bây giờ chúng ta xét phép toán xen.
- Chúng ta có thể loại đỉnh P (không phải là lá) khỏi cây tứ phân theo thuật toán đơn giản sau.
- Chúng ta xét phép toán xen.
- Như vậy chúng ta cần đánh giá thời gian thực hiện thuật toán.
- Biểu diễn thuật toán.
- Sau này chúng ta chỉ quan tâm tới đánh giá thời gian chạy của thuật toán.
- Đánh giá thời gian chạy của thuật toán bằng cách nào? Với cách tiếp cận thực nghiệm chúng ta có thể cài đặt thuật toán và cho chạy chương trình trên một máy tính nào đó với một số dữ liệu vào.
- Để phân tích thuật toán chúng ta cần sử dụng khái niệm cỡ (size) của dữ liệu vào.
- Thời gian chạy của thuật toán phụ thuộc vào cỡ của dữ liệu vào.
- Vì vậy, chúng ta cần đưa vào khái niệm thời gian chạy trong trường hợp xấu nhất và thời gian chạy trung bình.
- Chúng ta sẽ ký hiệu thời gian chạy trong trường hợp xấu nhất là T(n), trong đó n là cỡ của dữ liệu vào.
- Sau này khi nói tới thời gian chạy của thuật toán chúng ta cần hiểu đó là thời gian chạy trong trường hợp xấu nhất.
- Chúng ta xác định thời gian chạy trung bình (average running time) của thuật toán là số trung bình cộng của thời gian chạy của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ n.
- Như vậy chúng ta xác định thời gian chạy T(n) là số phép toán sơ cấp mà thuật toán đòi hỏi, khi thực hiện thuật toán trên dữ liệu vào cỡ n.
- Do đó, chúng ta sẽ chỉ quan tâm tới tốc độ tăng (rate of growth) của hàm T(n), tức là tốc độ tăng của thời gian chạy khi cỡ dữ liệu vào tăng.
- Trong mục tiếp theo chúng ta sẽ định nghĩa ký hiệu ô lớn và sử dụng ký hiệu ô lớn để biểu diễn thời gian chạy của thuật toán.
- Chúng ta sẽ biểu diễn thời gian chạy của thuật toán bởi ký hiệu ô lớn: T(n.
- Trong 395 số các cận trên của thời gian chạy, chúng ta sẽ lấy cận trên chặt (tight bound) để biểu diễn thời gian chạy của thuật toán.
- chúng ta cần hiểu f(n) là cận trên chặt của thời gian chạy.
- Chúng ta không đi sâu vào vấn đề này.
- Thời gian thực hiện lệnh lặp (1) là thời gian xây dựng cây thứ tự bộ phận mà chúng ta đã xét trong mục 10.3.2.
- Đánh giá thời gian chạy của thuật toán.
- Do đó chúng ta cần đưa ra các phương pháp biểu diễn đồ thị bởi các cấu trúc dữ liệu.
- được biểu diễn bởi cấu trúc dữ liệu trong hình 18.2.c.
- Để lưu lại vết của các đỉnh đã được thăm, chúng ta sử dụng một hàng đợi Q.
- Giả sử chúng ta có một đề án bao gồm nhiều nhiệm vụ.
- Chúng ta sẽ giả thiết rằng, G = (V,E) là đồ thị có trọng số, tập đỉnh V.
- Chúng ta xét hai vấn đề sau.
- Trong thuật toán trên đây, chúng ta mới sử dụng mảng D để ghi lại độ dài đường đi ngắn nhất từ nguồn tới các đỉnh khác.
- Chúng ta cần tìm đường đi ngắn nhất từ đỉnh nguồn là đỉnh 0