Cấu trúc dữ liệu và giải thuật II - 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ương pháp đặc biệt. Chương này sẽ giới thiệu một số phương pháp như sau: ...
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật II - Chương 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ương pháp đặc biệt. Chương này sẽ giới thiệu một số phương pháp như sau: Phương pháp trộn RUN Phương pháp trộn tự nhiên Phương pháp trộn đa lối cân bằng(balanced multiway merging) Phương 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ó 5 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à 1 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ừ 2 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ự. 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: f0 là tập tin cần sắp thứ tự. Output: f0 là tập tin đã được sắp thứ tự. Gọi f1, f2 là 2 tập tin trộn. Các tập tin f0, f1, 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 ) Bước 1: - Giả sử các phần tử trên f0 là: 24 12 67 33 58 42 11 34 29 31 - f1 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ừ f0 vào f1 và f2: f1: 24 67 58 11 29 f0: 24 12 67 33 58 42 11 34 29 31 f2: 12 33 42 34 31 - Trộn f1, f2 thành f0: 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ừ f0 vào f1 và f2: f1: 12 24 42 58 29 31 f0: 12 24 33 67 42 58 11 34 29 31 f2: 33 67 11 34 - Trộn f1, f2 thành f0: f1: 12 24 42 58 29 31 f0: 12 24 33 67 11 34 42 58 29 31 f2: 33 67 11 34 Bước 3: - Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và f2, kết quả thu được như sau: f1: 12 24 33 67 29 31 f2: 11 34 42 58 - Trộn f1, f2 thành f0: f0: 11 12 24 33 34 42 58 67 29 31 Bước 4: - Phân bố m=8 phần tử lần lượt từ f0 vào f1 và f2: f1: 11 12 24 33 34 42 58 67 f2: 29 31 - Trộn f1, f2 thành f0: f0: 11 12 24 29 31 33 34 42 58 67 29 Bước 5: Lặp lại tương tự các bước trên, cho đến khi chiều dài m của run cần phân bổ lớn hơn chiều dài n của f0 thì dừng. Lúc này f0 đã được sắp thứ tự xong. Cài đặt: /* Sap xep file bang phuong phap tron truc tiep Cai dat bang Borland C 3.1 for DOS. */ #include #include void tao_file(void); void xuat_file(void); void chia(FILE *a,FILE *b,FILE *c,int p); void tron(FILE *b,FILE *c,FILE *a,int p); int p,n; /**/ void main (void) { FILE *a,*b,*c; clrscr(); tao_file(); xuat_file(); p = 1; while (p < n) { chia(a,b,c,p); tron(b,c,a,p); p=2*p; } printf(\n); xuat_file(); getch(); } void tao_file(void) /* Tao file co n phan tu */ { int i,x; FILE *fp; fp=fopen(d:\\ctdl\\sorfile\bang.int,wb); printf(Cho biet so phan tu : ); scanf(%d,&n); for (i=0;i } fclose(fp); } void chia(FILE *a,FILE *b,FILE *c,int p) /* Chia xoay vong file a cho file b va file c moi lan p phan tu cho den khi het file a. */ { int dem,x; a=fopen(d:\ctdl\sortfile\bang.int,rb); b=fopen(d:\ctdl\sortfile\bang1.int,wb); c=fopen(d:\ctdl\sortfile\bang2,wb); while (!feof(a)) { /*Chia p phan tu cho b*/ dem=0; while ((dem { fscanf(a,%3d,&x); fprintf(c,%3d,x); dem++; } } fclose(a); fclose(b); fclose(c); } void tron(FILE *b,FILE *c,FILE *a,int p) /* Tron p phan tu tren b voi p phan tu tren c thanh 2*p phan tu tren a cho den khi file b hoac c het. */ { int stop,x,y,l,r; a=fopen(d:\ctdl\sortfile\bang.int,wb); b=fopen(d:\ctdl\sortfile\bang1.int,rb); c=fopen(d:\ctdl\sortfile\bang2.int,rb); while ((!feof(b)) && (!feof(c))) { l=0;/*so phan tu cua b da ghi len a*/ r=0;/*so phan tu cua c da ghi len a*/ fscanf(b,%3d,&x); fscanf(c,%3d,&y); stop=0; while ((l!=p) && (r!=p) && (!stop)) { if (x fprintf(a,%3d,x); l++; if (feof(c)) stop=1; } } } } /* Chep phan con lai cua p phan tu tren b len a */ while ((!feof(b)) && (l } } if (!feof(b)) { /*chep phan con lai cua b len a*/ while (!feof(b)) { fscanf(b,%3d,&x); fprintf(a,%3d,x); } } if (!feof(c)) { /*chep phan con lai cua c l ...