Cấu trúc dữ liệu 2 - Trương Hải Bằng

- Trương Hải Bằng-Cấu trỳc dữ liệu 2 Tài liệu tham khảo hỗ trợ môn học Cấu trúc dữ liệu 2 Trương Hải Bằng-Cấu trỳc dữ liệu 2 http://www.ebook.edu.vn mục lục Ch−ơng 1.
- Sắp xếp ngoại.
- Cài đặt ch−ơng trình .
- Ph−ơng pháp trộn đa pha (Polyphase merge Ch−ơng 2.
- Cài đặt bảng băm .
- Vài nhận xét về bảng băm Ch−ơng 3.
- Cài đặt cây AVL trên bộ nhớ ngoài Ch−ơng 4.
- 89 Ch−ơng 1.
- Sắp xếp ngoại Ch−ơng 2.
- Bảng băm Ch−ơng 3.
- Cây đỏ đen Ch−ơng 4.
- Phần thực hành http://www.ebook.edu.vn Trương Hải Bằng-Cấu trỳc dữ liệu 2 Ch−ơng 1 Sắp xếp ngoại Trong nhiều ứng dụng của tin học, ta phải sắp xếp các tập tin rất lớn.
- Trong ch−ơng này chúng ta sẽ tìm hiểu một số ph−ơng pháp sắp xếp ngoại th−ờng dùng là: trộn các run có độ dài cố định, trộn tự nhiên, trộn đa lối cân bằng và trộn đa pha.
- Thao tác trên tệp bằng ngôn ngữ lập trình C++ Trong ch−ơng này chúng ta sẽ nghiên cứu và cài đặt các thuật toán sắp xếp trên tệp bằng ngôn ngữ C.
- Tuy nhiên nếu ta dùng các ch−ơng trình soạn thảo văn bản nh− NCEDIT hoặc C hay Pascal thì chỉ nhập đ−ợc các ký tự có trên bàn phím do đó nội dung tệp trông nh− một văn bản có thể đọc đ−ợc.
- Nếu ta dùng ch−ơng trình soạn thảo văn bản để xem một tệp bất kỳ, ví dụ tệp có đuôi .EXE thì sẽ thấy có nhiều ký tự lạ, vì khi đó ch−ơng trình soạn thảo văn bản đã cho hiện lên cả những ký tự không có trên bàn phím.
- http://www.ebook.edu.vn Trương Hải Bằng-Cấu trỳc dữ liệu 2 1.1.2.
- Để hiểu rõ hơn những điều trên đây bạn hãy chạy thử ch−ơng trình sau: void ThuTep() {FILE * f = fopen("a.dat","w+t.
- Còn nếu ta mở tệp theo kiểu văn bản thì khi gặp ký tự 26 ch−ơng trình cho là đã hết tệp và gán c = -1.
- http://www.ebook.edu.vn 5 Trương Hải Bằng-Cấu trỳc dữ liệu 2 1.1.3.
- Ví dụ đoạn ch−ơng trình sau sẽ tạo một tệp có tên là A.DAT và ghi vào 3 ký tự A,B,C rồi đóng tệp: FILE *f.
- http://www.ebook.edu.vn 8 Trương Hải Bằng-Cấu trỳc dữ liệu 2 B3.
- Truong hop x lon hon tat ca cac khoa trong nut thi tra ve vi tri p->keynum, tuc la vi tri sau khoa cuoi cung Input: Khoa x va con tro toi nut p Output: Vi tri i, sao cho son[i] se la nhanh cay tiep theo de tim x*/ http://www.ebook.edu.vn 80 Cấu trúc dữ liệu2 – Ch−ơng 4.
- http://www.ebook.edu.vn 81 Cấu trúc dữ liệu2 – Ch−ơng 4.
- http://www.ebook.edu.vn 83 Cấu trúc dữ liệu2 – Ch−ơng 4.
- http://www.ebook.edu.vn 84 Cấu trúc dữ liệu2 – Ch−ơng 4.
- http://www.ebook.edu.vn 85 Cấu trúc dữ liệu2 – Ch−ơng 4.
- http://www.ebook.edu.vn 86 Cấu trúc dữ liệu2 – Ch−ơng 4.
- Có thể sửa đổi ch−ơng trình 41BCAY.CPP cho tr−ờng hợp này bằng cách khai báo thêm hàm Node GetNode(int n) để truy xuất đến một nút ở vị trí n trên tệp.
- Trong bộ nhớ ta tạo ra một cấu trúc dữ liệu B-cây.
- Mỗi lần nhập mới một nút ta nhập vào cuối tệp, đồng thời cập nhật thông tin vào cấu trúc dữ liệu trong http://www.ebook.edu.vn 87 Cấu trúc dữ liệu2 – Ch−ơng 4.
- Ch−ơng trình sẽ có một chức năng dọn dẹp: khi chạy chức năng này ta đọc và ghi sang tệp mới các bản ghi trên tệp mà có nút t−ơng ứng trên cấu trúc dữ liệu, sau đó xóa tên tệp cũ và đổi lại tên tệp mới thành tên tệp cũ.
- http://www.ebook.edu.vn 88 Câu hỏi và bài tập Ch−ơng 1.
- Sắp xếp ngoại 1.1.
- b) Hãy mô tả quá trình sắp xếp trộn run tự nhiên.
- d) So sánh các ph−ơng pháp sắp xếp trên.
- Cài đặt và chạy các ch−ơng trình thực hiện các ph−ơng pháp sắp xếp trộn: trực tiếp, tự nhiên và đa lối cân bằng.
- Copy ch−ơng trình mẫu vào máy (hoặc ch−ơng trình bạn tự viết).
- 1.7.* Thử cài đặt ch−ơng trình bằng cách khác với tài liệu, ví dụ không dùng hàm EoR() và khi đọc các phần tử trên tệp chỉ tiến lên chứ không lùi lại.
- 1.8.* Hãy sử dụng ch−ơng trình cài đặt cho tr−ờng hợp các phần tử trên tệp là các cấu trúc, ví dụ struct node {Char HoTen[20], int Tuoi.
- Ch−ơng 2.
- Bảng băm 2.1.
- Trình bày cấu trúc dữ liệu bảng băm.
- Chạy thử ch−ơng trình cài đặt bảng băm dùng liên kết ngoài trong tài liệu để hiểu rõ các tác vụ.
- Hãy xóa các tác vụ search() và insert() trong ch−ơng trình mẫu hoặc ch−ơng trình tự viết rồi viết lại mà không dùng tài liệu.
- http://www.ebook.edu.vn Cấu trúc dữ liệu2 – Câu hỏi và bài tập 2.9.
- Ch−ơng 3.
- Chạy thử ch−ơng trình mẫu cài đặt cây nhị phân AVL.
- Giải thích các chức năng quay nút, tìm kiếm, thêm nút, xóa nút trong ch−ơng trình cài đặt cây nhị phân AVL.
- Ch−ơng 4.
- Chạy thử ch−ơng trình mẫu cài đặt B-cây cấp M.
- Giải thích các chức năng tìm kiếm, thêm nút, xóa nút trong ch−ơng trình cài đặt B-cây cấp M.
- Phần này không bắt buộc, nh−ng nếu sinh viên nào làm đ−ợc chúng tôi sẽ có hệ số điểm −u tiên, ví dụ điểm thi đ−ợc cọng thêm điểm chẳng hạn (nếu quy chế cho phép) http://www.ebook.edu.vn 90 Cấu trúc dữ liệu2 – Câu hỏi và bài tập Mục đích của các bài tập là rèn luyện kỹ năng áp dụng bài học vào thực tế bằng cách vận dụng các cấu trúc dữ liệu đã học để viết ch−ơng trình thực hiện các thao tác trên các cấu trúc dữ liệu nh− bảng băm, cây AVL, B - cây.
- Viết ch−ơng trình tudien.cpp, ch−ơng trình có cài đặt bảng băm T = (a0, a1.
- Ch−ơng trình có các chức năng sau.
- int luong;int phucap, int thunhap;} Hãy sử dụng các cấu trúc dữ liệu đã học nh− bảng băm, cây AVL, B-cây để viết ch−ơng trình quản lý nhân sự với các chức năng sau: 1.
- http://www.ebook.edu.vn 91 Cấu trúc dữ liệu2 – Phụ lục.
- Các ch−ơng trình C++ cài đặt các thuật toán CTDL 2 Tài liệu tham khảo 1.
- Phần lý thuyết Ch−ơng 1.
- Ví dụ với m = 3 và các số chèn vào là ta có sơ đồ sau: http://www.ebook.edu.vn Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn Hình 2.1.
- http://www.ebook.edu.vn 94 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 2.6.
- Tuy nhiên đối với tệp ch−ơng trình ví dụ 11SXF.CPP chúng tôi không dùng quy −ớc này vì không có sự nhập nhằng.
- Do đó chúng tôi quy −ớc khi viết http://www.ebook.edu.vn 95 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn tên hàm mà không có gì phía sau, ví dụ SplitFile thì có nghĩa ta chỉ nói đến tên hàm, còn phần tham số thì phải tham khảo ch−ơng trình mới biết đ−ợc.
- Nếu bạn đ−ợc yêu cầu viết lại một đoạn ch−ơng trình nào đó thì bạn phải hiểu rõ ch−ơng trình mình viết.
- Nếu việc viết lại ch−ơng trình là quá khó đối với bạn thì bạn cần phải hiểu đ−ợc những phần ch−ơng trình mà bài ra yêu cầu.
- Ch−ơng 1.
- Ch−ơng trình 11SXF.CPP cài đặt thuật toán trộn trực tiếp để sắp xếp tệp nhị phân chứa các số thực.
- Ch−ơng trình này có một số hàm, trong đó 3 hàm quan trọng nhất là SplitFile, MergeFile và SortFile.
- Đọc toàn bộ ch−ơng trình để hiểu đ−ợc chức năng, input và output của các hàm, ý nghĩa các lệnh.
- để l−u tệp 11SXF.CPP thành tệp BAI11.CPP và thử sửa đổi ch−ơng trình này theo gợi ý sau: b.
- Bạn hãy xóa hàm SplitFile rồi viết lại mà không sử dụng tài liệu hoặc ch−ơng trình mẫu, sao cho ch−ơng trình này chạy đ−ợc và cho kết quả đúng.
- Bạn hãy xóa hàm MergeFile rồi viết lại mà không sử dụng tài liệu hoặc ch−ơng trình mẫu, sao cho ch−ơng trình này chạy đ−ợc và cho kết quả đúng.
- Hàm void SortFile(char *TenTep) http://www.ebook.edu.vn 96 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn có đầu vào là tệp TenTep th−ờng ch−a đ−ợc sắp xếp.
- Bạn hãy xóa hàm SortFile rồi viết lại mà không sử dụng tài liệu hoặc ch−ơng trình mẫu, sao cho ch−ơng trình này chạy đ−ợc và cho kết quả đúng.
- Ch−ơng trình 12SXF.CPP cài đặt thuật toán trộn run tự nhiên để sắp xếp tệp nhị phân chứa các số thực.
- để l−u tệp 12SXF.CPP thành tệp BAI12.CPP và thử sửa đổi ch−ơng trình này theo gợi ý sau: b.
- http://www.ebook.edu.vn 97 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 1.3.
- Ch−ơng trình 13SXF.CPP cài đặt thuật toán trộn đa lối cân bằng để sắp xếp tệp nhị phân chứa các số thực.
- để l−u tệp 13SXF.CPP thành tệp BAI13.CPP và thử sửa đổi ch−ơng trình này theo gợi ý sau: b.
- Ch−ơng trình sẽ tính toán lại số đ−ờng trộn nWay dựa trên số tệp nguồn thực tế.
- Trong thân hàm, ch−ơng trình yêu cầu ng−ời sử dụng nhập số đ−ờng trộn, sau đó tạo ra các tệp nguồn và các tệp đích nh− đã nói ở trên.
- Ch−ơng trình copy dữ liệu đã sắp xếp vào tệp TenTep, xóa các tệp trung gian và kết thúc.
- Ch−ơng trình 21HASHLK.CPP cài đặt bảng băm dùng danh sách liên kết ngoài bằng ngôn ngữ lập trình C.
- Để có thể hiểu đ−ợc ch−ơng trình 21HASHLK.CPP, bạn cần tìm hiểu tệp LIST_H.CPP mà các chức năng của nó có thể hiểu đ−ợc khi đọc ch−ơng trình.
- Sau khi hiểu tệp này, bạn chạy thử ch−ơng trình DS-LK.CPP.
- Ch−ơng trình này chèn (include) tệp LIST_H.CPP vào, sau đó chạy các chức năng nh− nhập dữ liệu vào danh sách, tìm kiếm trên danh sách.
- Ch−ơng trình 21HASHLK.CPP cài đặt bảng băm với một số chức năng (theo ngôn ngữ C++ thì đó là các ph−ơng thức), trong đó quan trọng nhất là các chức năng insert, search và traverse.
- Bạn hãy tìm hiểu ch−ơng trình, sau đó dùng chức năng "Save as.
- Hàm void HashTab::insert(int x) thực hiện việc chèn một khóa x vào bảng băm Bạn hãy xóa phần thân hàm và viết lại sao cho ch−ơng trình vẫn chạy đúng.
- Bạn hãy xóa phần thân hàm và viết lại sao cho ch−ơng trình vẫn chạy đúng.
- Hàm void HashTab::traverse() thực hiện việc liệt kê tất cả các khóa trong bảng băm Bạn hãy xóa phần thân hàm và viết lại sao cho ch−ơng trình vẫn chạy đúng.
- Ch−ơng trình 23HASHTR.CPP cài đặt bảng băm với một số chức năng (theo ngôn ngữ C++ thì đó là các ph−ơng thức), trong đó quan trọng nhất là các chức năng insert, search và traverse.
- Hàm http://www.ebook.edu.vn 99 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn int HashTab::search(int x) thực hiện việc tìm khóa x trên bảng băm.
- Cây đỏ đen Ch−ơng trình 31CAYAVL.CPP cài đặt cây nhị phân tìm kiếm cân bằng chiều cao.
- Ch−ơng trình này rất khó, nên chúng tôi chỉ yêu cầu bạn đọc và hiểu các chức năng của ch−ơng trình.
- B - cây Ch−ơng trình 41BTREE.CPP cài đặt B - cây.
- Các bài thực hành trong hai ch−ơng 3 và 4 sẽ là giải thích ch−ơng trình.
- http://www.ebook.edu.vn 100 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn Một số ch−ơng trình mẫu Sau đây là một số ch−ơng trình mẫu cơ sở t−ơng đối đơn giản các bạn có thể tìm hiểu để hiểu và viết lại: 1.
- Ch−ơng trình 11SXF.CPP: Sắp xếp tệp nghị phân bằng ph−ơng pháp trộn trực tiếp //11SXF.CPP Sap xep file bang phuong phap tron truc tiep tren tep nhi phan //Programmer: Phan Dang Cau, Khoa CNTT, Hoc vien CNBCVT #include #include #include #define true 1 #define false 0 #define sz (sizeof(float.
- http://www.ebook.edu.vn 101 Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn return(k