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).
Nội dung trích xuất từ tài liệu:
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ải thuật 1 CHƯƠNG 1 - SẮP THỨ TỰ NGOẠI 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: f0 là tập tin cần sắp thứ tự. Output: f0 là tập tin đã được sắp thứ tự.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 Gọi f1, f2 là hai tập tin trộn.bộ nhớ có số lượng phần tử nhỏ và truy xuất nhanh, tập tin có thể Các tập tin f0, f1, f2 có thể là các tập tin tuần tự (text file) hay có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 thể là các tập tin truy xuất ngẫu nhiên (File of )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ácphương pháp đặc biệt. Bước 1Chương này sẽ giới thiệu một số phương pháp như sau: - Giả sử các phần tử trên f0 là: Phương pháp trộn Run 24 12 67 33 58 42 11 34 29 31 Phương pháp trộn tự nhiên - f1 ban đầu rỗng, và f2 ban đầu cũng rỗng. Phương pháp trộn đa lối cân bằng (balanced multiway merging) - Thực hiện phân bố m = 1 phần tử lần lượt từ f0 vào f1 và f2: Phương pháp trộn đa pha (Polyphase Merge) f1: 24 67 58 11 291. PHƯƠNG PHÁP TRỘN RUN f0: 24 12 67 33 58 42 11 34 29 31Khái niệm cơ bản f2: 12 33 42 34 31 Run là một dãy liên tiếp các phần tử được sắp thứ tự. - Trộn f1, f2 thành f0: Ví dụ 1 2 3 4 5 là một run gồm có năm phần tử f0: 12 24 33 67 42 58 11 34 29 31 Chiều dài run chính là số phần tử trong run. Chẳng hạn, run Bước 2 trong ví dụ trên có chiều dài là 5. -Phân bố m = 2 phần tử lần lượt từ f0 vào f1 và f2: 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à f1: 12 24 42 58 29 31 một run có chiều dài bằng 1. f0: 12 24 33 67 42 58 11 34 29 31 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 f2: 33 67 11 34 các phần tử đã được sắp thứ tự. 5 6 - Trộn f1, f2 thành f0: #include f1: 12 24 42 58 29 31 #include f0: 12 24 33 67 11 34 42 58 29 31 void tao_file(void); f2: 33 67 11 34 void xuat_file(void); Bước 3 void chia(FILE *a,FILE *b,FILE *c,int p); - Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và void tron(FILE *b,FILE *c,FILE *a,int p); f2, kết quả thu được như sau: int p,n; f1: 12 24 33 67 29 31 /*------------------------------------------------------------------------------------ */ f2: 11 34 42 58 void main (void) - Trộn f1, f2 thành f0: { f0: 11 12 24 33 34 42 58 67 29 31 FILE *a,*b,*c; Bước 4 ...