Giáo trình cấu trúc dữ liệu và giải thuật

- Thêm phần tử vào cây nhị phân tìm kiếm .
- Loại phần tử trong cây nhị phân tìm kiếm .
- Thêm phần tử vào Trie .
- Thêm phần tử vào B-tree .
- Loại phần tử trong B-tree .
- Thêm phần tử .
- Tác vụ thêm phần tử .
- Tác vụ loại phần tử .
- Định ra các lớp với các chức năng mà chúng ta mong đợi.
- Chương 2 – Ngăn xế p Giáo trình Cấu trúc dữ liệu và Giải thuật 18 Vậy chúng ta có định nghĩa của ngăn xếp dưới đây, không khác gì đối với định nghĩa danh sách, ngoại trừ cách thức mà ngăn xế p cho phép thay đổi hoặc truy xuất đến các phần tử của nó..
- Với một đặc tả như vậy chúng ta đã hoàn toàn có thể sử dụng lớp Stack trong các ứng dụng.
- Vấn đề đặt ra là chúng ta nên chọn phần tử đầu hay phần tử cuối của cấu trúc liên kết làm đỉnh của ngăn xếp.
- Hình 2.4 - Cấu trúc liên kết Firstnode Chương 3 – Hàng đợi Giáo trình Câu trúc dữ liệu và Giải thuật 39 và để tránh nhầm lẫn với những từ mà chúng ta sẽ dùng với các cấu trúc dữ liệu khác.
- Chúng ta có lớp Queue như sau: template class Queue { public: Queue.
- Chúng ta có thể bổ sung các tác vụ trên vào lớp hàng đã có ở trên.
- Tuy nhiên, chúng ta có thể tạo lớp mới có thể sử dụng lại các phương thức và cách hiện thực của các lớp đã có.
- Chương 3 – Hàng đợi Giáo trình Câu trúc dữ liệu và Giải thuật 40 Chúng ta có lớp Extended_Queue : template class Extended_Queue : public Queue { public: bool full() const.
- Khi lấy một phần tử ra khỏi hàng chúng ta lấy phần tử tại vị trí front và tăng front lên một.
- Chúng ta có thể hình dung Chương 3 – Hàng đợi Giáo trình Câu trúc dữ liệu và Giải thuật 46 3.4.
- Chúng ta có định nghĩa lớp Queue như sau: const int maxQueue = 10.
- Định nghĩa danh sách Chúng ta bắt đầu bằng việc định nghĩa kiểu cấu trúc dữ liệu trừu tượng gọi là danh sách ( list.
- Tìm số phần tử của danh sách.
- Chúng ta có thể xây dựng rất nhiều dạng khác nhau cho các kiểu cấu trúc dữ liệu trừu tượng tương tự bằng cách sử dụng các gói tác vụ khác nhau.
- post : trả về số phần tử của danh sách.
- Chúng ta xem xét tiếp các tác vụ truy xuất các phần tử của danh sách.
- Chúng ta dùng một số nguyên để chỉ vị trí ( position ) của phần tử trong danh sách.
- Nếu chúng ta thêm một phần tử vào một vị trí nào đó trong danh sách thì vị trí của tất cả các phần tử phía sau sẽ tăng lên 1.
- Nhưng chúng ta cũng vẫn thông qua vị trí để tìm các phần tử trong danh sách liên kết dù rằng danh sách liên kết không có chỉ số.
- Chương 4 – Danh sách Giáo trình Cấ u trúc dữ liệu và Giải thuật 53 Chúng ta sẽ đặc tả chính xác các phương thức liên quan đến chỉ một phần tử của danh sách dưới đây.
- chúng ta bắt đầu với khai báo Node.
- Trong định nghĩa trên chúng ta không liệt kê lại các phương thức của danh sách liên kết vì chúng cũng tương tự như đối với danh sách liên tục .
- Nếu chúng ta thêm từ “ simple ” trước từ “ lists ” chúng ta có danh sách như hình b.
- Tìm đến một vị trí trong danh sách Chúng ta thiết kế một hàm set_position để được gọi trong một vài phương thức.
- Trong trường hợp xấu Chương 4 – Danh sách Giáo trình Cấ u trúc dữ liệu và Giải thuật 63 nhất, nếu cần phải bắt đầu từ đầu danh sách, hàm cũng sẽ làm việc giống như cách chúng ta đã hiện thực trước đây.
- Bằng cách dịch chuyển theo tham chiếu thích hợp chúng ta có thể duyệt danh sách theo hướng mong muốn.
- Trong cách hiện thực này chúng ta chỉ cần giữ một con trỏ tham chiếu đến một phần tử nào đó trong danh sách là chúng ta có thể duyệt danh sách theo hướng này hoặc hướng kia.
- Với hàm này chúng ta viết tác vụ insert sau đây.
- Chúng ta cũng đặc biệt chú ý hai trường hợp hơi đặc biệt, Chương 4 – Danh sách Giáo trình Cấ u trúc dữ liệu và Giải thuật 65 đó là khi thêm phần tử vào một trong hai đầu của danh sách hoặc thêm vào một danh sách rỗng.
- Để tránh điều này chúng ta hãy thử thay đổi dòng lệnh.
- Chúng ta cần hàm để đọc các đối tượng String .
- Chúng ta có thể thực hiện tương tự như đối với C-String , tác vụ 0) cout data.
- Hành vi của giải thuật Chúng ta thấy rằng tree_search dựa trên cơ sở của tìm nhị phân.
- Chúng ta cũng đã biết tìm nhị phân thực hiện O(log n) lần so sánh đối với danh sách có chiều dài n.
- Không phải chúng ta luôn có thể dự đoán trước hình dạng của một cây nhị phân tìm kiếm trước khi cây được tạo ra, và cây ở hình (b) là một cây điển hình thường có nhất so với cây ở hình (a).
- Thêm phần tử vào cây nhị phân tìm kiếm 9.3.3.1.
- Đặt vấn đề Tác vụ quan trọng tiếp theo đối với chúng ta là thêm một phần tử mới vào cây nhị phân tìm kiếm sao cho các khóa trong cây vẫn giữ đúng thứ tự.
- Khi thêm f, chúng ta qua phải của e như hình (d).
- Chúng ta có được cây ở hình (g).
- Chúng ta chỉ cần cho con trỏ root chỉ đến nút này.
- Lưu ý rằng chúng ta vừa mô tả việc thêm vào bằng cách sử dụng đệ quy.
- Chúng ta đã quy ước cây nhị phân tìm kiếm sẽ không có hai phần tử trùng khóa, do đó hàm search_and_insert từ chối mọi phần tử có trùng khóa.
- Sắp thứ tự theo cây Khi duyệt một cây nhị phân tìm kiếm theo inorder chúng ta sẽ có được các khóa theo đúng thứ tự của chúng.
- Chúng ta chỉ cần dùng phương thức insert để xây dựng một cây nhị phân tìm kiếm từ các phần tử cần sắp thứ tự, sau đó dùng phép duyệt inorder chúng ta sẽ có các phần tử có thứ tự.
- Như chúng ta đã biết, quicksort là một phương pháp rất tốt.
- Xét trung bình, trong các phương pháp mà chúng ta đã học, chỉ có mergesort là có số lần so sánh Chương 9 – Cây nhị phân Giáo trình Cấ u trúc Dữ liệu và Giải thuật 207 các khóa ít nhất.
- Từ phần 8.8.4 chúng ta có thể kết luận: Trong trường hợp trung bình, trong một danh sách có thứ tự ngẫu nhiên có n phần tử, treesort thực hiện 2n ln n + O (n.
- Khi chúng ta chọn phần tử đầu của mỗi danh sách con làm pivot, trường hợp xấu nhất là khi các khóa đã có thứ tự.
- Loại phần tử trong cây nhị phân tìm kiếm Khi xem xét về treesort , chúng ta đã nhắc đến khả năng thay đổi trong cây nhị phần tìm kiếm là một ưu điểm.
- Nhưng chúng ta chưa đề cập đến cách loại một phần tử ra khỏi cây.
- Chúng ta bắt đầu bằng một hàm phụ trợ sẽ loại đi một nút nào đó trong cây nhị phân tìm kiếm.
- Xây dựng một cây nhị phân tìm kiếm Giả sử chúng ta có một danh sách các dữ liệu đã có thứ tự, hoặc có thể là một file các bản ghi có các khóa đã có thứ tự.
- Nếu chúng ta muốn sử dụng các dữ liệu Chương 9 – Cây nhị phân Giáo trình Cấ u trúc Dữ liệu và Giải thuật 211 này để tìm kiếm thông tin, hoặc thực hiện một số thay đổi nào đó, chúng ta có thể tạo một cây nhị phân tìm kiếm từ danh sách hoặc file này.
- Chúng ta có thể bắt đầu từ một cây rỗng và đơn giản sử dụng giải thuật thêm vào cây để thêm từng phần tử.
- Chẳng hạn, khi số phần tử n bằng 31, chúng ta muốn cây sẽ có được dạng như hình 9.12.
- Chương 9 – Cây nhị phân Giáo trình Cấu trúc Dữ liệu và Giải thuật 212 Giả sử chúng ta không biết trước số nút sẽ tạo cây.
- Thiết kế giải thuật Khi nhận phần tử thứ nhất có nhãn là 1, chúng ta sẽ tạo một nút lá có các con trỏ left và right đều là NULL .
- Để đơn giản chúng ta sẽ cho rằng các phần tử này được chứa trong một danh sách các Record gọi là supply .
- Chương 9 – Cây nhị phân Giáo trình Cấu trúc Dữ liệu và Giải thuật 214 Sau khi tất cả các phần tử từ supply đã được thêm vào cây nhị phân tìm kiếm mới, chúng ta cần tìm gốc của cây và nối tất cả các cây con phải còn rời rạc.
- Chúng ta cần tìm cách thay thế các danh sách liên tục này bởi các danh sách liên kết.
- Hiện thực liên kết Để nắm các con của một nút trong một danh sách liên kết, chúng ta cần hai loại tham chiếu.
- Bằng cách sử dụng hai tham chiếu này chúng ta có được cấu trúc của một cây nhị phân, nghĩa là, hiện thực liên kết của một cây có thứ tự là một cây nhị phân liên kết.
- Đối với hình 10.2, chúng ta có được cây nhị phân ở hình 10.3.
- Chúng ta sẽ sử dụng quá trình này để đưa ra một định nghĩa đệ quy mới cho các cây có thứ tự và các vườn.
- Chúng ta nhớ rằng một cây nhị phân có thể rỗng.
- Chúng ta có thể biểu diễn cây có thứ tự bằng một cặp có thứ tự T.
- Chúng ta có thể biểu diễn vườn bằng một cặp có thứ tự O.
- Trước hết chúng ta cần một ký hiệu tương tự cho cây nhị phân.
- Nếu chúng ta định nghĩa ánh xạ f từ một vườn đến một cây nhị phân bởi f.
- Chúng ta sẽ sử dụng phương thức char key_letter(int position) trả về ký tự tại vị trí position trong khóa hoặc ký tự rỗng nếu khóa có chiều dài ngắn hơn position , và hàm phụ trợ int alphabetic_order(char symbol) trả về thứ tự của symbol trong bảng chữ cái.
- Chuyển các phần tử từ.
- Phương pháp Đối với việc loại bỏ phần tử, chúng ta mong muốn rằng phần tử được loại bỏ thuộc một nút lá nào đó.
- Hiện thực C++ Chúng ta có thể viết giải thuật loại phần tử với cấu trúc tổng thể tương tự như giải thuật thêm vào.
- Chúng ta sẽ sử dụng đệ quy, với một phương thức riêng để khởi động quá trình đệ quy.
- Loại phần tử trong nút lá.
- Dẫn nhập Trong phần trước, chúng ta đã sử dụng danh sách liên tục để chứa các phần tử của cây B-tree .
- Tuy nhiên, nói một các tổng quát, chúng ta có thể dùng bất kỳ cấu trúc có thứ tự nào để chứa các phần tử trong mỗi nút của B-tree .
- Như vậy chúng ta sẽ sử dụng cả hai cách biểu diễn cho các nút có hai phần tử trong cây B-tree.
- Sau khi chuyển đổi một cây B-tree thành cây đỏ đen, chúng ta có thể sử dụng nó tương tự bất kỳ cây nhị phân tìm kiếm nào.
- chúng ta chỉ đơn giản bỏ qua các màu của các tham chiếu.
- Tương tự, chúng ta sẽ xem tất cả các cây rỗng (tương ứng tham chiếu NULL ) có màu đen .
- Ở đây chúng ta chọn cách khi thêm phần tử mới vào thì nó sẽ được đứng tại vị trí đầu của danh sách liên kết, do đây là cách dễ nhất.
- Chúng ta sẽ dùng từ thử ( probe ) cho việc xem xét một phần tử và so sánh khóa của nó với khóa cần tìm.
- Chúng ta sẽ xem xét riêng từng bảng trên.
- Bây giờ chúng ta hãy giả sử là việc tìm kiếm sẽ thành sông.
- Nhưng chiều dài mong đợi của danh sách này không lớn hơn λ , và chúng ta biết trước là nó chứa ít nhất một phần tử (phần tử cần tìm).
- Chúng ta có thể thấy được một vài kết luận từ bảng này.
- Chúng ta có thể tổng kết những khảo sát về việc truy xuất từ n phần tử như sau.
- Chúng ta sẽ tìm hiểu các phương pháp biểu điễn đồ thị bằng các cấu trúc dữ liệu và xây dựng một số giải thuật tiêu biểu liên quan đến đồ thị.
- Đồ thị có hướng Đối với các đồ thị có hướng, chúng ta có thể có những định nghĩa tương tự.
- Cách thứ nhất là biểu diễn tập các đỉnh như là một danh sách các phần tử của nó, chúng ta sẽ tìm hiểu phương pháp này sau

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