Cấu trúc dữ liệu và giải thuật assignment 01 - Tree set

Chia sẻ: Minh Trí | Ngày: | Loại File: PDF | Số trang:4

0
2
lượt xem
0
download

Cấu trúc dữ liệu và giải thuật assignment 01 - Tree set

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài tập lớn này sinh viên sẽ hiện thực cấu trúc dữ liệu tập hợp TreeSet1 . Cụ thể, cấu trúc dữ liệu tập hợp này sẽ được hiện thực dựa trên cây AVL đã được học trên lớp. Việc hiện thực này phải đảm bảo thời gian thực thi trong trường hợp xấu nhất (worst case) là log(n) cho các phép toán cơ bản như thêm phần từ (add), xóa phần tử (remove), và các phép toán tìm kiếm. Ở bài tập lớn này, dữ liệu kiểm tra sẽ có kích thước rất lớn, do đó, sinh viên cần lưu ý tối ưu hóa mã nguồn để đảm bảo thời gian thực thi.

Chủ đề:
Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật assignment 01 - Tree set

Vietnam National University – HCMC<br /> Hochiminh University of Technology<br /> Faculty of Computer Science and Engineering<br /> <br /> Đại Học Quốc Gia TP.HCM<br /> Trường Đại học Bách Khoa<br /> Khoa KH&KT Máy Tính<br /> <br /> CẤU TRÚC DỮ LIỆU & GIẢI THUẬT<br /> ASSIGNMENT 02 - Tree set<br /> 1<br /> <br /> Giới thiệu<br /> <br /> Trong bài tập lớn này sinh viên sẽ hiện thực cấu trúc dữ liệu tập hợp TreeSet1 . Cụ thể, cấu trúc dữ liệu tập<br /> hợp này sẽ được hiện thực dựa trên cây AVL đã được học trên lớp. Việc hiện thực này phải đảm bảo thời gian<br /> thực thi trong trường hợp xấu nhất (worst case) là log(n) cho các phép toán cơ bản như thêm phần từ (add),<br /> xóa phần tử (remove), và các phép toán tìm kiếm. Ở bài tập lớn này, dữ liệu kiểm tra sẽ có kích thước rất lớn,<br /> do đó, sinh viên cần lưu ý tối ưu hóa mã nguồn để đảm bảo thời gian thực thi.<br /> <br /> 2<br /> <br /> Hiện thực<br /> <br /> Phần hiện thực trong bài tập lớn này được tổ chức trong file main.cpp và 2 lớp: AVLNode and TreeSet và<br /> được chia thành bốn file riêng biệt: AVLNode.h, TreeSet.h, TreeSet.cpp và main.cpp. Cụ thể như sau:<br /> <br /> 2.1<br /> <br /> AVLNode.h<br /> <br /> File này chứa phần khai báo và định nghĩa cấu trúc dữ liệu AVLNode để hiện thực cấu trúc dữ liệu cây AVL.<br /> 1 class AVLNode {<br /> 2 public :<br /> 3<br /> int key ;<br /> // data<br /> 4<br /> AVLNode∗ l e f t ;<br /> // left child<br /> 5<br /> AVLNode∗ r i g h t ;<br /> // right child<br /> 6<br /> int b a l a n c e ;<br /> // balance factor<br /> 7<br /> 8<br /> AVLNode( int key ) {<br /> 9<br /> this−>key = key ;<br /> 10<br /> l e f t = r i g h t = NULL;<br /> 11<br /> balance = 0;<br /> 12<br /> }<br /> 13<br /> AVLNode( int key , int b a l a n c e ) {<br /> 14<br /> this−>key = key ;<br /> 15<br /> this−>b a l a n c e = b a l a n c e ;<br /> 16<br /> l e f t = r i g h t = NULL;<br /> 17<br /> }<br /> 18 } ;<br /> <br /> 2.2<br /> <br /> TreeSet.h<br /> <br /> File này chứa phần khai báo các hàm (method) cho lớp TreeSet. Phần prototype của lớp này là dựa trên hiện<br /> thực Java của cấu trúc dữ liệu TreeSet.<br /> 1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> 8<br /> 9<br /> <br /> class T r e e S e t<br /> {<br /> private :<br /> AVLNode ∗ r o o t ;<br /> int count ;<br /> protected :<br /> void c l e a r R e c (AVLNode∗ r o o t ) ;<br /> 1 https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html<br /> <br /> 1<br /> <br /> 10<br /> 11 public :<br /> 12<br /> TreeSet ( ) ;<br /> 13<br /> ~TreeSet ( ) ;<br /> 14<br /> void c l e a r ( ) ;<br /> 15<br /> // print out the set in ascending order<br /> 16<br /> friend os tr ea m& operator
Đồng bộ tài khoản