tailieunhanh - Giáo trình Cấu trúc dữ liệu 2: Phần 1 - Trương Hải Bằng (biên soạn)

Giáo trình Cấu trúc dữ liệu 2 do tác giả Trương Hải Bằng biên soạn gồm 4 chương, được chia thành hai phần. Phần 1 giới thiệu đến bạn đọc nội dung chương 1 và chương 2. Chương 1 giới thiệu đến bạn đọc nội dung về sắp thứ tự ngoại. Chương 2 cung cấp cho bạn đọc nội dung về bảng băm (hash table). | ĐẠI HỌC QUỐC GIA TP. Hổ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN Gino TRINH A f A CAU TRÚC DỬ LIEU 2 f NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA TP HÓ CHÍ MINH H 1 CHƯƠNG 1 - SẮP THỨ Tự NGOẠI sắp thứ tự ngoại là sắp thứ tự trên tập tin. Khác với sắp xếp dãy trên bộ nhớ có số lượng phần tử nhỏ và truy xuất nhanh tập tin có thể có số lượng phần tử rất lớn và thời gian truy xuất chậm. Do vậy việc sắp xếp trên các cấu trúc dữ liệu loại tập tin đòi hỏi phải áp dụng các phưong pháp đặc biệt. Chuông này sẽ giới thiệu một số phưong pháp như sau Phuong pháp trộn Run Phuong pháp trộn tự nhiên Phuong pháp trộn đa lối cân bằng balanced multiway merging Phuong pháp trộn đa pha Polyphase Merge 1. PHƯƠNG PHÁP TRỘN RUN Khái niệm cơ bản Run là một dãy liên tiếp các phần tử được sắp thứ tự. Vỉ dụ 1 2 3 4 5 là một run gồm có năm phần tử Chiều dài run chính là số phần tử trong run. Chẳng hạn run trong ví dụ trên có chiều dài là 5. Như vậy mỗi phần tử của dãy có thể xem như là một run có chiều dài là 1. Hay nói khác đi mỗi phần tử của dãy chính là một run có chiều dài bằng 1. Việc tạo ra một run mới từ hai run ban đầu gọi là trộn run merge . Hiển nhiên run được tạo từ hai run ban đầu là một dãy các phần tử đã được sắp thứ tự. 5 Giải thuật Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau Input . fí là tập tin cần sắp thứ tự. Output . fí là tập tin đã được sắp thứ tự. Gọi fl f2 là hai tập tin trộn. Các tập tin fo fl f2 có thể là các tập tin tuần tự text file hay có thể là các tập tin truy xuất ngẫu nhiên File of kiểu Bước 1 - Giả sử các phần tử trên fí là 24 12 67 33 58 42 11 34 29 31 - fl ban đầu rỗng và f2 ban đầu cũng rỗng. - Thực hiện phân bố m 1 phần tử lần lượt từ fo vào fl và f2 fl 2 4 67 58 11 29 f0 24 12 67 33 58 42 11 34 29 31 f2 1233 42 34 31 - Trộn fl f2 thành fí f0 12 24 33 67 42 58 11 34 29 31 Bước 2 -Phân bố m 2 phần tử lần lượt từ fí vào fl và f2 fl 1 24 42 58 29 31 f0 12 24 33 67 42 58 11 34 29 31 f2 33 6 71 34 6 - Trộn fl Í2 thành fi fl 12 24 42 58 29