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)

Chia sẻ: Hoa La Hoa | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

162
lượt xem 34
download

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

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).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ác phương pháp đặc biệt. Bước 1 Chươ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 29 1. PHƯƠNG PHÁP TRỘN RUN f0: 24 12 67 33 58 42 11 34 29 31 Khá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 clrscr(); - Phân bố m = 8 phần tử lần lượt từ f0 vào f1 và f2: tao_file(); f1: 11 12 24 33 34 42 58 67 xuat_file(); f2: 29 31 p = 1; - Trộn f1, f2 thành f0: while (p < n) f0: 11 12 24 29 31 33 34 42 58 67 29 { chia(a,b,c,p); Bước 5 tron(b,c,a,p); 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 p=2*p; thứ tự xong. } printf("\n"); Cài đặt xuat_file(); /* ------------------------------------------------------------------------------- Sap xep file bang phuong phap tron truc tiep getch(); Cai dat bang Borland C 3.1 for DOS. } ---------------------------------------------- */ void tao_file(void) 7 8
/* -------------------------------------------------------------------------------------- fscanf(fp,"%d",&x); Tao file co n phan tu printf("%3d",x); ---------------------------------------------------------------------------------------*/ i++; { } int i,x; fclose(fp); FILE *fp; } fp=fopen("d:\\ctdl\\sorfile\bang.int","wb"); void chia(FILE *a,FILE *b,FILE *c,int p) printf("Cho biet so phan tu : "); /*--------------------------------------------------------------------------------------- scanf("%d",&n); Chia xoay vong file a cho file b va file c moi lan p phan tu cho den khi het file a. for (i=0;i
dem=0; while ((l!=p) && (r!=p) && (!stop)) while ((dem
l++; while (!feof(b)) if (feof(c)) { stop=1; fscanf(b,"%3d",&x); } fprintf(a,"%3d",x); } } } } /* -------------------------------------------------------------------------------------- if (!feof(c)) Chep phan con lai cua p phan tu tren b len a ---------------------------------------------------------------------------------------*/ { while ((!feof(b)) && (l
Input: f0 là tập tin cần sắp thứ tự. void Copy(FILE *,FILE *); Output: f0 là tập tin đã được sắp thứ tự. void CopyRun(FILE *,FILE *); void MergeRun(); void Merge(); Lặp Cho đến khi dãy cần sắp chỉ gồm duy nhất một run. Phân bố // - Chép một dây con có thứ tự vào tập tin phụ fi (I >= 1). typedef int DataType; Khi chấm dứt dây con này, biến eor (end of run) có giá trị True. FILE *F0,*F1,*F2; - Chép dãy con có thứ tự kế tiếp vào tập tin phụ kế tiếp fi+1 (xoay vòng). int M,N,Eor; - Việc phân bố kết thúc khi kết thúc tập tin cần sắp f0. /*--------------------------------------------------------------------------------------- Bien eor dung de kiem tra ket thuc Run hoac File Trộn --------------------------------------------------------------------------------------*/ - Trộn 1 run trong f1 và1 run trong f2 vào f0. DataType X1,X2,X,Y; - Việc trộn kết thúc khi duyệt hết f1 và hết f2 (hay nói cách khác, // Ham main việc trộn kết thúc khi đã có đủ n phần tử cần chép vào f0). Cài đặt void main(void) /* ------------------------------------------------------------------------------- { Sap xep file bang phuong phap tron tu nhien clrscr(); --------------------------------------------------------------------------------------*/ randomize(); coutN; #include CreatFile(F0,N); #include ListFile(F0); #include do void CreatFile(FILE *Ft,int); { void ListFile(FILE *); F0=fopen("d:\\ctdl\\sortfile\\bang.int","rb"); void Distribute(); F1=fopen("d:\\ctdl\\sortfile\\bang1.int","wb"); 15 16
F2=fopen("d:\\ctdl\\sortfile\\bang2.int","wb"); DataType X,I=0; Distribute(); Ft = fopen("d:\\ctdl\\sortfile\\bang.int","rb"); F0=fopen("d:\\ctdl\\sortfile\\bang.int","wb"); while ( I < N ) F1=fopen("d:\\ctdl\\sortfile\\bang1.int","rb"); { F2=fopen("d:\\ctdl\\sortfile\\bang2.int","rb"); fscanf(Ft,"%3d",&X); M=0; cout
void Distribute() fscanf(F2,"%3d",&X2); /* Phan bo luan phien cac Run tu nhien tu F0 vao F1 va F2 */ curpos = ftell(F2)-2; { fseek(F2, curpos, SEEK_SET); do if( X1
CopyRun(F1,F0); do M++; { } Hoán đổi vai trò của tập các file nguồn và tập các file đích ; Trộn từng bộ run trên các file nguồn và đưa vào các file đích ; while( !feof(F2) ) { } while ( tổng số run trên các file đích > 1 ) ; CopyRun(F2,F0); Một số qui ước M++; N : tập các file nguồn } S : tập các file nguồn tham gia vào quá trình trộn để fclose(F0); tạo thành một run cho file đích. fclose(F1); Q : tập các file nguồn còn run đang xử lý. fclose(F2); D : tập các file đích } D : tập các file đích đã được phân phối một đường 3. PHƯƠNG PHÁP TRỘN ĐA LỐI CÂN BẰNG chạy trong “tua” hiện hành . Khi tất cả các file đích đã (Balanced MultiWay Merging) được phân phối một run thì hết một tua. Bước 1 Giải thuật N = { f1, f2, ….., fn } Các phương pháp đã trình bày ở trên chủ yếu dựa trên hai thao tác: D = { g1, g2, …., gn } phân phối và trộn các run. Thời gian thực thi các phương pháp này chủ yếu bị chi phối bởi thời gian phân phối các run từ tập tin f0 vào // Phân phối xoay vòng các run của file F ( file cần sắp xếp) các tập tin phụ f1 và f2. cho các file thuộc N Phương pháp trộn đa lối cân bằng sẽ khắc phục được nhược điểm i=1; này. while ( ! feof (F)) Gọi F = { f1, f2, ….., fn } là tập các file nguồn {  Lấy 1 run của F và phân phối cho fi G = { g1, g2, …, gn } là tập các file đích  i = ( i mod n ) + 1 ; Phân phối các run trên file cần sắp xếp cho các file thuộc tập các file nguồn ; } 21 22
S=N; // tất cả các file nguồn đều tham gia vào quá trình { if Q  {} trộn. Goto bước 2.b D = {} ; // chưa có file đích nào được phân phối run. else // Q = {}, bộ run hiện tại đã l=0; // đếm số run trên các tập đích. trộn xong Bước 2 { l++ ; a. Lấy một file đích trong ( D - D ) là tập các file đích D = D + {Dh } chưa được phân phối trong “tua” hiện hành , và gọi nó là file if ( D = D ) đích hiện hành Dh ( tức sẽ được phân phối run ). D = {} // xong một tua Q= S; Goto bước 2.a b. xa = Min { xa / a  Q} // phần tử x trên file a0 0 } c. Copy xa lên Dh } 0 } d. if ( file nguồn a0 hết ) else // file nguồn a0 chưa hết { Q = Q – { a0 } { if ( hết run hiện tại trên a0 ) S = S – { a0 } { Q = Q – { a0 } if ( S = {} ) // xong quá trình trộn từ nguồn đến đích if Q  {} { l++ ; Goto bước 2.b D = D + {Dh else // Q = {}, bộ run Goto bước 3 hiện tại đã trộn xong // hoán đổi vai trò các file : F  G { l++ ; } D = D + {Dh } else if ( D = D ) 23 24
D = {} // xong một tua Du lieu co the la 1 file gom n so tao ngau nhien, hoac la file "Input.Cpp" trong cung thu muc voi CT Goto bước 2.a Co in file (so phan tu it) trong moi buoc sap xep. } /*+++++++++++++++++++++++++++++++++++++++++++++++++++*/ } else // run hiện tại trên a0 chưa hết, tiếp tục #include tìm Min #include Goto bước 2.b #include #include } #include Bước 3 #include if ( l = 1 ) STOP ; else #define FALSE 0 { if ( l < n ) S=D; // không đủ run để phân phối #define TRUE !FALSE cho n file else S=D; #define FILE_INPUT "Input.Cpp" D = {} typedef struct l=0 { int Giatri; int ThuocFile; N  D } Kieu_Xa; Goto bước 2 //Các hàm sử dụng } void TaoFileDuLieu (void); Cài đặt void DocFile_Input__TaoFileDuLieu (void); /*+++++++++++++++++++++++++++++++++++++++++++++++++++*/ void Display_Run_1File (char *filenamePtr); /*CT Sap xep tren file theo phuong phap tron n duong void InCacFile (char *TenCacFile [10]); can bang. void Buoc_1 (void); 25 26
void Buoc_2 (void); int Dhh = 0; /* De biet file dich hien hanh,vd Dhh = 1 thi file g1 la file dich hien hanh. */ void Buoc_2a (void); int SoLanHoanDoi_F_G = 0; void Buoc_2bcd (FILE *file_Dhh); /*--------------------------------------------------*/ void Buoc_3 (void); void main () int HetFile (FILE *f); { int XemCur (FILE *f); int MuonChon; void Copy_run (FILE *f, FILE *fx); char *filenamePtr; int Copy_element (FILE *f, FILE *fx); char filename[13]; int KiemTraRong (int *DC_Mang); clrscr(); void SetRong_Dhoa (void); printf ("\r\n 1. TAO FILE DU LIEU NGAU NHIEN"); void HoanDoi2TapHopTenFile (char *TenCacFile_A[10], char *TenCacFile_B[10]); printf ("\r\n 2. DOC DU LIEU TU FILE"); void CapNhatDbongTruDhoa (void); printf ("\r\n\n Muon chon : "); fflush (stdin); scanf("%d", &MuonChon); /*----------- Cac Bien Toan Cuc -----------*/ switch (MuonChon) int n; { FILE *TapCacFile_F[10], *TapCacFile_G[10]; case 1 : TaoFileDuLieu (); break; int Tap_N[10], Tap_Dbong[10], Tap_S[10], Tap_Q[10], case 2 : DocFile_Input__TaoFileDuLieu (); Tap_Dhoa[10], Tap_DbongTruDhoa[10] ; break; /* Neu Tap_N[i] = 1 la file fi thuoc tap N, neu = 0 la } khong thuoc */ strcpy (filename, "FileDL"); char *TenCacFile_F[10] = { "File_F0", "File_F1", filenamePtr = filename; "File_F2", "File_F3", "File_F4", "File_F5", "File_F6", "File_F7", "File_F8", "File_F9" }, *TenCacFile_G[10] = { "File_G0", "File_G1", "File_G2", printf("\nn la so luong file nguon luc bat dau "File_G3","File_G4","File_G5","File_G6","File_G7","File :\n"); _G8", "File_G9" }; printf ("Xin nhap n < 8 \n"); int l; /* so run tren cac tap dich*/ printf ("n : "); 27 28
scanf ("%d", &n); randomize(); printf ("\nf : "); Display_Run_1File(filenamePtr); dem = 0; printf ("\n\n\n"); getch(); while (dem < n) printf ("\n XIN CHO : DANG SAP XEP \n"); { Buoc_1 (); temp = random (n); //Tao so ngau nhien, 0 < gia tri so < n do fwrite (&temp, sizeof(int), 1, f); { Buoc_2 (); dem++; } while (l > 1); } } } /*+++++++++++++++++++++++++++++++++++++++++++++++++++*/ fclose (f); /* Ham tao file du lieu gom n so nguyen duoc phat sinh ngau nhien. */ printf ("\nDa tao xong file du lieu co %d phan tu.\n", n); /*---------------------------------------------------*/ } void TaoFileDuLieu (void) /*+++++++++++++++++++++++++++++++++++++++++++++++++++*/ { /* Ham doc file input de tao file du lieu. */ FILE *f; /*---------------------------------------------------*/ int n, dem, temp; void DocFile_Input__TaoFileDuLieu () char filename[13]; { FILE *fptr, *f; strcpy (filename, "FileDL"); char filename[13]; if ((f = fopen(filename, "w+b")) == NULL) int n, temp; { printf ("Khong tao duoc file %s \n", filename); getch(); if ((fptr = fopen(FILE_INPUT, "rt")) == NULL) } { else printf ("Khong co file %s \n", FILE_INPUT); {printf("Xin nhap so phan tu cua file du lieu : "); getch(); scanf ("%d", &n); 29 30
} { else int temp, cur, EndOfRun ; { FILE *f; strcpy (filename, "FileDL"); char filename[13]; if ((f = fopen(filename, "w+b")) == NULL) int stt; // De kiem tra lai co bi mat ptu nao trong luc sap xep ? { printf ("Khong tao duoc file %s \n", filename); getch(); strcpy (filename, filenamePtr); } else if ((f = fopen(filename, "rb")) == NULL) { n = 0; { printf ("Khong co file %s \n", filename); while (!feof(fptr)) getch(); exit(1); { } fscanf (fptr, "%d ", &temp); else fwrite (&temp, sizeof(int), 1, f); { stt = 0; n++; while (!HetFile (f)) } { fread (&temp, sizeof(int), 1, f); fclose (fptr); printf ("%d ", temp); fclose (f); stt++; printf ("\nDa tao xong file du lieu co %d if (!HetFile (f)) phan tu.\n", n); { cur = XemCur (f); } EndOfRun = (temp > cur); } if (EndOfRun) } printf (" - "); /*+++++++++++++++++++++++++++++++++++++++++++++++++++*/ } /* Ham hien thi mot file len man hinh, co phan cach else giua cac run. */ break; /*---------------------------------------------------*/ } void Display_Run_1File (char *filenamePtr) 31 32
fclose (f); } for (i= 1; i
fclose (TapCacFile_F[i]); l = 0; Dhh = 0; InCacFile (TenCacFile_F); printf ("\n"); Buoc_2a (); getch(); } } /*---------------------------------------------------*/ /*---------------------------------------------------*/ void Buoc_2a () void Buoc_2 () { { int i; int i; FILE *file_Dhh; printf ("\nTRON LAN %d :", SoLanHoanDoi_F_G +1); Dhh++; // de in cac file luc dang sap, DL it CapNhatDbongTruDhoa(); for (i= 1; i
case 7 : file_Dhh = TapCacFile_G[7]; break; for (i= 1; i
case 9 : file_a0 = TapCacFile_F[9]; break; } } Buoc_2a (); } EOR = Copy_element (file_a0, file_Dhh); } else // file nguon a0 chua het /*-------------------- Buoc_2d --------------------*/ { if (EOR) // Het run hien tai tren file_a0 { Tap_Q[Xa0.ThuocFile] = 0; if (HetFile(file_a0)) // File nguon a0 het if (KiemTraRong (Tap_Q)) // Q = {} , Bo run { Tap_Q[Xa0.ThuocFile] = 0; hien tai da tron xong Tap_S[Xa0.ThuocFile] = 0; { l++; Tap_Dhoa[Dhh] = 1; if (KiemTraRong (Tap_S)) // Xong qua trinh tron CapNhatDbongTruDhoa(); tu Nguon den Dich if (KiemTraRong (Tap_DbongTruDhoa)) { l++; { SetRong_Dhoa(); Tap_Dhoa[Dhh] = 1; Dhh = 0; Buoc_3 ();// Neu chua sap xong se F G } } Buoc_2a (); else } if (KiemTraRong (Tap_Q)) // Q = {} , Bo run } hien tai da tron xong } { } l++; /*---------------------------------------------------*/ Tap_Dhoa[Dhh] = 1; void Buoc_3 () CapNhatDbongTruDhoa(); { if (KiemTraRong (Tap_DbongTruDhoa)) // Dhoa = Dbong int i; { SetRong_Dhoa();// Xong 1 tua for (i= 1; i
for (i= 1; i