Giáo trình về Kỹ thuật lập trình

qua Cú pháp: remove (tê n file) Hà m remove trả về 0 : xóa thà nh công trả về -1 : có lỗi khi xóa file, và lúc nà y biế n errno có 1 trong 2 giá trị sau: ENOENT : không tì m thấ y file muốn xóa EACCES : không cho phép xóa file mà bạ n chỉ định Lưu ý : File nê n đóng trước khi xóa. Ví dụ: Xóa file do ta chỉ định. #include void main() { char filename[80]; /* prompt for file name to delete */ printf("File muon xoa: "); gets(filename); /* delete the file */ if (remove(filename) == 0) printf("Removed %s.\n",filename); else perror("remove"); // in thông bá o lỗi mà hà m remove gâ y ra } V.2. File nhị phân (file có cấu trúc) File nhị phâ n là file dùng để lưu trữ cá c cấ u trúc dưới dạ ng struct hoặ c union V.2.1. Khai báo: FILE * fptr; V.2.2. Mở file: fptr = fopen (tê nfile, “kiể u”); . rb ( b: binary): mở chỉ để đọc . wb : để ghi. Nế u file đ∙ có thì xóa trước khi mở. . ab : nối thê m; mở để ghi thê m và o cuối file, nế u file chưa có thì tạ o mới . rb+ : mở file đ∙ có để cậ p nhậ t (đọc/ghi) . wb+ : tạ o file mới cho phép đọc/ghi . ab+ : mở để nối thê m về cuối file, cho phép đọc/ghi Kỹ thuật lập trì nh 63 V.2.3. Đóng file: fclose (fptr) V.2.4. Đọc/ghi file: Hà m fread : đọc số mẫ u tin(cấ u trúc) trong file fptr và o . fread (& biế n cấu trúc, sizeof (biế n cấu trúc) , số cấu trúc, fptr); Hà m fread trả về số cấ u trúc đọc được Hà m fwrite ghi dữ liệ u trong và o file fptr. fwrite (&biế n cấu trúc, sizeof (biế n cấu trúc) , số cấu trúc, fptr); Hà m fwrite trả về số cấ u trúc ghi được lê n file Chú ý : - Để kiể m tra việ c đọc file ta kiể m tra số cấ u trúc được đọc. Nế u số cấ u trúc trả về bằ ng 0 mà ta cầ n đọc là 1 cấ u trúc thì điề u đó chứng tỏ đ∙ hế t file. * Ghi một mảng cấu trúc lê n file fwrite(tê nmả ng, sizeof (tê nmả ng), 1, fptr); ⇔ for (i= 0; i< n; i++) fwrite (&tê nmả ng[i], sizeof (tê nmả ng[i] , 1, fptr); Ví dụ 1: Chương trì nh ghi lê n file nhị phâ n #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; FILE *fptr; char tenfile[67]; char tuoi[3]; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"wb")) == NULL) // mở file nhị phâ n để ghi { printf ("Khong the tao file\n"); exit(0); } do { printf("Nhap ho ten hoc vien :"); Kỹ thuật lập trì nh 64 gets(hv.hoten); if (strlen(hv.hoten) !=0) { printf("Nhap tuoi :"); gets(tuoi); hv.tuoi = atoi(tuoi); // macro doi chuoi qua so nguyen fwrite(&hv, sizeof(hv), 1, fptr) ; // ghi noi dung 1 mau tin trong bien hv // vao file fptr } } while (strlen(hv.hoten)!=0); fclose (fptr); } Ví dụ 2: Ghi dữ liệ u mả ng và o file nhị phâ n #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; struct hocvien table[3]; FILE *fptr; char tenfile[67]; char tuoi[3]; int i=0; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"wb")) == NULL) { printf ("Khong the tao file\n"); exit(0); } do { printf("Nhap ho ten hoc vien :"); gets(hv.hoten); printf("Nhap tuoi :"); gets(tuoi); hv.tuoi = atoi(tuoi); // macro doi chuoi qua so nguyen table[i++]=hv; Kỹ thuật lập trì nh 65 } while (i<3); fwrite(table, sizeof(table), 1, fptr) ; // ghi noi dung toan bo hoc vien trong // table vao file fptr // hoặ c for (i=0; i<3; i++) // fwrite(&table[i], sizeof(table[i]), 1, fptr) fclose (fptr); } Ví dụ 3: Chương trì nh đọc file nhị phâ n, và in danh sá ch học viê n ra mà n hì nh. // In danh sá ch học viê n ra mà n hì nh #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; FILE *fptr; char tenfile[67]; char tuoi[3]; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"rb")) == NULL) // Mở file để đọc { printf ("Khong the mo file\n"); exit(0); } clrscr(); printf(" Ho va ten Tuoi"); while (fread(&hv,sizeof(hv),1,fptr) ==1) { printf("\n%-20s",hv.hoten); printf("%3d",hv.tuoi); } fclose (fptr); } V.2.5. Truy xuất tập tin ngẫu nhiê n: (điề u khiể n con trỏ tậ p tin trê n file nhị phâ n) Kỹ thuật lập trì nh 66 * Con trỏ file: Mỗi tậ p tin đề u có con trỏ file sau khi được mở. Con trỏ file là con trỏ chỉ đế n từng byte trê n file. Khi đọc hay ghi dữ liệ u trê n tậ p tin, ta đ∙ là m dịch chuyể n con trỏ file một số byte, đâ y chí nh là số byte mà kiể u dữ liệ u đ∙ chiế m. Khi đóng rồi mở tậ p tin, con trỏ file luôn ở đầ u tậ p tin ; ngoạ i trừ trường hợp ta mở bằ ng tùy chọn 'a' thì con trỏ file sẽ ở cuối tậ p tin để ghi thê m dữ liệ u và o cuối tậ p tin. Hà m fseek cho phép ta di chuyể n con trỏ file đế n vị trí mong muốn. Cú pháp: int fseek (FILE * fptr, long nbytes, kiể u) + nbytes : số bytes tí nh từ vị trí kiể u cho đế n vị trí cầ n tới + kiể u là số nguyê n : kiể u = 0 (tí nh từ đầ u tậ p tin) kiể u = 1 (tí nh từ vị trí hiệ n tạ i) kiể u = 2 (tí nh từ cuối tậ p tin) Nế u fseek trả về 0 nghĩ a là nó đ∙ di chuyể n tới vị trí đó. Lưu ý: số thứ tự trê n tậ p tin tí nh từ 0. Ví dụ: Viế t chương trì nh truy xuấ t ngẫ u nhiê n một mẫ u tin theo số thứ tự của nó trong file nhị phâ n #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; FILE *fptr; char tenfile[67]; int stt, sobytes; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"rb")) == NULL) { printf ("Khong the mo file\n"); exit(0); } clrscr(); Kỹ thuật lập trì nh 67 printf("Cho biet so thu tu mau tin can di chuyen den :"); scanf("%d",&stt); sobytes = stt * sizeof(hv); if (fseek(fptr,sobytes,0)!=0) { printf ("Khong the di chuyen con tro file toi vi tri ban chi dinh duoc"); exit(0); } fread(&hv,sizeof(hv),1,fptr) ; printf("\n%-20s",hv.hoten); printf("%3d",hv.tuoi); fclose (fptr); getch(); } V.3. Phát hiệ n lỗi khi truy xuất tập tin Phầ n lớn những hà m xuấ t, nhậ p tậ p tin chuẩ n không thông bá o rõ nội dung của lỗi. Chẳ ng hạ n như : - putc () sẽ trả về EOF khi có lỗi hoặ c cuối tậ p tin - fgets () sẽ trả về là NULL khi đọc hế t file hoặ c khi có lỗi Do đó, để phá t hiệ n lỗi khi truy xuấ t tậ p tin, ta dùng macro ferror (FILE *fptr) int ferror (file * ptr) Macro ferror trả về một trị khá c 0 nế u phá t hiệ n ra lỗi trê n file fptr. * Để xuấ t câ u thông bá o lỗi ta dùng hà m perror () void perror (const char * str) với str : chuỗi ký tự chứa câ u thông bá o * Hai hà m nà y thường được sử dụng ngay sau khi sử dụng cá c hà m đọc / ghi file Ví dụ: fwrite (&table, sizeof (table), 1, fptr); if (ferror (fptr) != 0) { perror (“Loi ghi du lieu”); exit (0); } Ví dụ : #include void main() { FILE *fp; Kỹ thuật lập trì nh 68 fp = fopen("perror.dat", "r"); if (!fp) perror("Không thể mở file để đọc"); } Khi chạ y chương trì nh nà y, nế u trê n dĩ a chưa có tậ p tin perror.dat thì sẽ hiệ n thông bá o lỗi: Không thể mở file để đọc: No such file or directory. Bài tập 1. Tạ o tậ p tin diệ n tí ch.h #define Pi 3.14 #define dthv (x) x*x #define dtht (x) (Pi*x*x) 2. Viế t chương trì nh tí nh diệ n tí ch dựa và o file dientich.h ở trê n 3. Viế t hà m đệ qui tí nh tí ch P(n) = 1 * 2 * 3* ....* n , n>0 4. Viế t hà m đệ qui tí nh hà m mũ xn, với n nguyê n. 5. Viế t hà m đệ qui tí nh phầ n tử thứ n của hà m Fibonacci. 6. Viế t hà m đệ qui giả i quyế t bà i toá n Thá p Hà nội. Có 3 cột A, B, C. Cột A hiệ n đang có n dĩ a kí ch thước khá c nhau, dĩ a nhỏ ở trê n dĩ a lớn ở dưới. H∙ y dời n dĩ a từ cột A sang cột C (xem cột B là cột trung gian) với điề u kiệ n mỗi lầ n chỉ được dời 1 dĩ a và dĩ a đặ t trê n bao giờ cũng nhỏ hơn dĩ a đặ t dưới. 7. Viế t chương trì nh m∙ hóa và giả i m∙ một file vă n bả n sao cho nế u ta đ∙ m∙ hóa rồi thì chương trì nh không m∙ hóa nữa, và nế u file đó chưa m∙ hóa thì không được giả i m∙ . 8. Cho biế t trong một file vă n bả n do ta nhậ p và o có bao nhiê u ký tự, bao nhiê u từ, và bao nhiê u dòng; biế t rằ ng cá c từ cá ch nhau khoả ng trắ ng, dấ u tab, dấ u chấ m. 9. Viế t chương trì nh tạ o một menu thực hiệ n cá c chức nă ng sau trê n file vă n bả n: - Tạ o file mới - Đọc file - Xóa file - Ghi nối đuôi file - Copy file - Di chuyể n file từ thư mục nà y sang thư mục khá c - Tì m một từ xuấ t hiệ n bao nhiê u lầ n trong file (không phâ n biệ t chữ in, chữ Kỹ thuật lập trì nh 69 thường) - Thay thế từ nà y bằ ng từ khá c 10. Tạ o menu thực hiệ n cá c công việ c sau: - Nhậ p danh sá ch có kiể u học viê n và o một file tê n 'HOSO.TXT', mỗi học viê n có cá c thông tin sau: maso (int), hoten (chuỗi tối đa 30 ký tự), phá i (NAM/NU), tuổi (int). - Liệ t kê danh sá ch học viê n ra mà n hì nh theo dạ ng sau: M∙ số Họ và tê n Phá i Tuổi - Truy xuấ t ngẫ u nhiê n theo thứ tự mẫ u tin - Tì m kiế m một người trong file theo m∙ số - Cậ p nhậ t sửa đổi cá c mẫ u tin theo m∙ số (Nhậ p m∙ số, sau đó hiệ u chỉ nh lạ i hoten, phai, và tuổi). - Xóa một người trong file theo m∙ số. Kỹ thuật lập trì nh 70 CHươNG 3 CáC THUậT TOáN TRÊN CấU TRúC Dữ LIệU MảNG I. Mảng không sắp xếp và thuật toán tìm kiếm trên mảng chưa có thứ tự I.1. Một số khái niệ m về mảng: I.1.1. Định nghĩ a: Mả ng là 1 d∙ y cá c phầ n tử có cùng kiể u dữ liệ u được sắ p xế p liê n tiế p nhau trong bộ nhớ 0100 0102 1 int 0104 2 Mả ng n phầ n tử n-1 Bộ nhớ !Khai báo: Cú pháp: Khai bá o mả ng 1 chiề u Kiể u_DL Tê nmả ng [kí ch thước]; ♦ Kiể u_DL : là 1 trong cá c kiể u dữ liệ u cơ bả n, đó là kiể u của phầ n tử của mả ng ♦ Tê nmả ng: là tê n của mả ng được đặ t 1 cá ch hợp lệ ♦ Kí ch thước: là 1 hằ ng nguyê n cho biế t số phầ n tử tối đa của mả ng Ví dụ 1: Khai bá o 1 mả ng số nguyê n • int n ; int M[n] ; SAI • int M[10] ; đúng vì kí ch thước mả ng phả i là hằ ng không phả i là biế n • #define max 100 int M[max] ; Ví dụ 2: Khai bá o 1 danh sá ch họ tê n học viê n của 1 lớp học char dshv[50][30]; // dshv có thể chứa tối đa họ tê n 50 học viê n, // chiề u dà i họ tê n mỗi học viê n tối đa là 30 ký tự Cú pháp: Khai bá o mả ng 2 chiề u Kỹ thuật lập trì nh 71 Kiể u_DL Tê nmả ng [kí ch thước 1][kí ch thước 2] Chú ý : Một mả ng trong C, cá c phầ n tử được đá nh số từ 0 tới n-1 Ví dụ: Với M[10] thì thà nh phầ n thứ 1 là M[0] thà nh phầ n cuối cùng M[9] * C không bắ t bẻ , không kiể m tra xem biế n đế m có vượt ra khỏi giới hạ n cho phép của mả ng chưa. Do đó, chúng ta phả i kiể m tra biế n đế m trong chương trì nh (phả i nhỏ hơn n) I.1.2. Khởi động trị cho mảng: Ta khởi động được trị cho mả ng trong 2 trường hợp sau: • Mả ng được khai bá o là biế n ngoà i (main) nghĩ a là biế n toà n cục • Mả ng được khai bá o cục bộ Ví dụ 1 : int M[3] = {10,11,12} main() { } Ví dụ 2: main() { static int M[ ]={10,22,30}; ............ } • Ta có thể gá n 1 hằ ng cho cả mả ng như sau: memset (M,0,sizeof(int) *3) ; // gá n 0 cho mả ng M với M có 3 phầ n tử • Từ khóa static dùng để khai bá o 1 biế n cục bộ thường trực cho phép duy trì giá trị riê ng của nó ở những lầ n gọi hà m sau nà y. • Khởi tạ o mả ng 2 chiề u: int M[2][3]= {{1,2,3}, {0,1,0}}; I.1.3.Truy xuất thành phần của mảng: M[chỉ số] • Truy xuấ t thà nh phầ n thứ 2 của mả ng 1 chiề u: M[1] • Truy xuấ t thà nh phầ n thứ i của mả ng 1 chiề u: M[i-1] • Truy xuấ t thà nh phầ n dòng 2, cột 3 của mả ng 2 chiề u M[1][2] I.1.4. Đọc (nhập) dữ liệ u cho mảng: - Để nhậ p dữ liệ u cho mả ng ta phả i nhậ p dữ liệ u cho từng thà nh phầ n của mả ng. Ví dụ 1: Kỹ thuật lập trì nh 72 int n,i; float M[10]; printf("\nCho biet so phan tu cua mang:") scanf (“%d”,&n); for ( i=0; i< n; i++) { printf(“a[%d]= “,i+1); scanf (“%f”,&M[i]); } Ví dụ 2: Nhậ p và o mả ng 2 chiề u. int m, n, i, j; float M[10] [10]; printf("So dong ="); scanf("%d",&n); printf("So cot ="); scanf("%d",&m); for(i= 0; i< n; i++) for(j= 0; j<m; j++) { printf(“M[%d] [%d] = “,i,j); scanf(“%f”, &M[i][j]); } I.1.5. Xuất dữ liệ u kiể u mảng: Để xuấ t dữ liệ u mả ng ta cũng phả i xuấ t dữ liệ u của từng thà nh phầ n mả ng Ví dụ: int i, n; float M[10]; for(i = 0; i< n; i++) printf(“a[%d] = %f”,i+1, M[i]); I.2. Thuật toán tì m kiế m trê n mảng chưa có thứ tự: Do mả ng chưa có thứ tự nê n ta á p dụng phương phá p tì m kiế m tuyế n tí nh tì m từ đầ u mả ng cho đế n cuối mả ng. Trong chương trì nh sau đâ y, hà m Timkiế m sẽ trả về trị -1 nế u không có m∙ sinh viê n trong danh sá ch ds, ngược lạ i hà m sẽ trả về vị trí của m∙ số đó trong danh sá ch ds. #include #include #include #include #define MAX_SOSV 100 // số sinh viê n tối đa trong danh sá ch typedef struct sinhvien // định nghĩ a kiể u sinhvien Kỹ thuật lập trì nh 73 { char maso[6]; char hoten[30]; }; typedef struct danhsach_sv // định nghĩ a kiể u danhsach_sv { int tssv; sinhvien sv[MAX_SOSV]; } ; void Nhap_ds (struct danhsach_sv *psv) { char sosv[4]; printf("So sinh vien muon nhap :"); gets(sosv); psv->tssv=atoi(sosv); for (int i=0; itssv; i++) { printf("Ma so :"); gets(psv->sv[i].maso); printf("Ho ten :"); gets(psv->sv[i].hoten); } } void Lietke_ds (struct danhsach_sv *psv) { int i=0; clrscr(); printf (" Ma so Ho & ten \n"); while (i tssv) { printf ("%8s %-s\n", psv->sv[i].maso,psv->sv[i].hoten); i++; } getch(); } /* Hàm Timkiem tì m maso trong danhsach *psv */ int Timkiem(danhsach_sv *psv, char maso[]) { int i=0; while ((itssv) && (strcmp(psv->sv[i].maso, maso)!=0)) i++; return (i==psv->tssv ? -1 : i) ; Kỹ thuật lập trì nh 74 } void main() { struct danhsach_sv ds; char maso[6]; int vitri; Nhap_ds(&ds); // Gọi hà m Nhap_ds với tham số là ds Lietke_ds(&ds); printf("Ma so sinh vien ban can tim :"); gets(maso); vitri = Timkiem(&ds, maso); if (vitri !=-1) printf("Ho ten cua sinh vien la %s",ds.sv[vitri].hoten); else printf(" Khong co sinh vien voi ma ban nhap vao"); getch(); } II. Các thuật toán sắp xếp: Trong thực tế cuộc sống cũng như trong lĩ nh vực lậ p trì nh, việ c quả n lỹ dữ liệ u thường đòi hỏi sự tì m kiế m cá c dữ liệ u cầ n thiế t; Để thuậ n tiệ n cho việ c tì m kiế m, dữ liệ u thường được sẵ p xế p theo một thứ tự nà o đó. Có rấ t nhiề u phương phá p sắ p thứ tự, trong bà i giả ng nà y ta chỉ khả o sá t hai phương phá p sắ p xế p là Bubble_Sort và Quick_Sort. Để thuậ n tiệ n ta giả sử mả ng là d∙y số có tối đa 100 số, và cá c thuậ t toá n dưới đâ y dùng để sắ p xế p d∙ y số theo thứ tự tă ng dầ n. II.1. Sắp xế p theo phương pháp Bubble_Sort (phương pháp nổi bọt) - Nội dung : Ta cho i duyệ t d∙ y a[0], .. ,a[n-1]; nế u a[i-1] lớn hơn a[i] thì ta hoá n đổi (a[i-1],a[i]). Lặ p lạ i quá trì nh duyệ t d∙y nà y cho đế n khi không có xả y ra việ c đổi chỗ của hai phầ n tử. Ví dụ: Ta sắ p thứ tự d∙ y số sau : 26 33 35 29 19 12 32 Bước 0 1 2 3 4 5 6 26 12 12 12 12 12 12 33 26 19 19 19 19 19 35 33 26 26 26 26 26 29 35 33 29 29 29 29 19 29 35 33 32 32 32 Kỹ thuật lập trì nh 75 12 19 29 35 33 33 33 32 32 32 32 35 35 35 - Chương trì nh: #include #include int mang[100]; // biế n toà n cục int size ; void Bubble_Sort(int A[100], int n) { int i,j,temp; for (i=1; i<n; i++) for (j=n-1;j>=i; j--) if (A[j-1] > A[j]) { temp = A[j-1]; A[j-1] = A[j]; A[j] = temp; } } int Nhap_day_so (int A[]) { int i,n; printf("\nSo phan tu cua mang :"); scanf("%d",&n); for (i=0; i<n; i++) { printf ("A[%d] = ",i+1); scanf("%d",&A[i]); } return n; } void Liet_ke (int A[], int n) { int i; printf("\n Gia tri mang da duoc sap : \n"); for (i=0; i<n; i++) printf ("%5d",A[i]); getch(); } void main() { size= Nhap_day_so(mang); Kỹ thuật lập trì nh 76 Bubble_Sort(mang,size); Liet_ke(mang,size); } Ta nhậ n thấ y phương phá p nà y có thể được cả i tiế n dễ dà ng. Nế u ở lầ n duyệ t d∙y nà o đó mà không có có sự đổi chỗ giữa hai phầ n tử thì d∙y đ∙ có thứ tự và giả i thuậ t kế t thúc. Trong trường hợp nà y, ta dùng một cờ hiệ u flag để ghi nhậ n điề u nà y, và giả i thuậ t Bubble Sort được cả i tiế n như sau: #define FALSE 0 #define TRUE 1 void Bubble_Sort_Ad(int A[], int n) { int i,temp; unsigned char flag=TRUE; while (flag) { flag = FALSE ; for (i=0; i<n-1; i++) if (A[i] > A[i+1]) { temp = A[i]; A[i] = A[i+1]; A[i+1] = temp; flag=TRUE; } } } II.2. Sắp xế p theo phương pháp Quick_Sort II.2.1. Nội dung: Chọn một phầ n tử bấ t kỳ trong danh sá ch là m điể m chốt x, so sá nh và đổi chỗ những phầ n tử trong danh sá ch nà y để tạ o ra 3 phầ n: phầ n có giá trị nhỏ hơn x, phầ n có giá trị bằ ng x, và phầ n có giá trị lớn hơn x. Lạ i tiế p tục chia 2 phầ n có giá trị nhỏ hơn và lớn hơn x theo nguyê n tẵ c như trê n; quá trì nh chia phầ n sẽ kế t thúc khi mỗi phầ n chỉ còn lạ i một phầ n tử, lúc nà y ta đ∙ có một danh sá ch có thứ tự. Ví dụ: Xét d∙ y 26 33 35 29 19 12 32 ' Lầ n chia phầ n thứ nhấ t : Chọn phầ n tử chốt có khóa là 29, đặ t là x 26 33 35 29 19 12 32 i % $ j Dùng hai biế n chỉ số i và j để duyệ t từ hai đầ u danh sá ch đế n x. Nế u i gặ p Kỹ thuật lập trì nh 77 phầ n tử lớn hơn hay bằ ng x sẽ dừng lạ i, j gặ p phầ n tử nhỏ hơn hay bằ ng x sẽ dừng lạ i, rồi đổi chỗ hai phầ n tử nà y; sau đó tiế p tục duyệ t cho đế n khi i>j thì ngừng lạ i. Lúc nà y d∙ y sẽ có 3 phầ n khá c nhau như hì nh vẽ sau : 26 33 35 29 19 12 32 i j 26 12 35 29 19 33 32 i j 26 12 19 29 35 33 32 ij 26 12 19 29 35 33 32 j i ' Lầ n chia phầ n thứ hai cho d∙ y con 26 12 19, chọn chốt x=12 26 12 19 % 12 26 19 i j j i Kế t thúc ta sẽ có hai phầ n : 12 ; 26 19 ' Lầ n chia phầ n thứ 3 cho d∙ y con 26 19, chọn chốt x=26 26 19 % 19 26 Kế t thúc quá trì nh chia nhỏ d∙ y con 26 12 19 i j j i - Lầ n chia phầ n thứ 4 cho d∙ y con 35 33 32, chọn chốt x= 33 35 33 32 % 32 33 35 % 32 33 35 i j ij j i Kế t thúc ta sẽ có ba phầ n : 32 ; 33 ; 35 Đế n đâ y quá trì nh chia phầ n kế t thúc vì tấ t cả các phầ n chỉ có một phầ n tử, lúc nà y ta sẽ có một danh sá ch có thứ tự là : 12 19 26 29 32 33 35 II.2.2. Giải thuật: a. Giải thuật không đệ quy: - Ta tạ o một Stack , mỗi phầ n tử của Stack có 2 thà nh phầ n là q, r chứa chỉ số đầ u và chỉ số cuối của d∙y cầ n sắ p. Ban đầ u, Stack[0].q = 0 và Stack[0].r =n-1 - Tiế n hà nh phâ n hoạ ch d∙y số gồm cá c số bắ t đầ u từ chỉ số q đế n chỉ số r - Sau mỗi lầ n chia phầ n, ta kiể m tra xem phầ n có giá trị nhỏ hơn chốt và phầ n có giá trị lớn hơn chốt nế u có từ 2 phầ n tử trở lê n thì đưa và o Stack. Sau mỗi lầ n phâ n hoạ ch, ta lạ i lấ y d∙ y số mới từ Stack ra phâ n hoạ ch tiế p. Kỹ thuật lập trì nh 78 - Quá trì nh cứ như thế cho tới khi Stack rỗng thì kế t thúc. * Chương trì nh: #include #include #include #include int mang[100]; int size ; void Quick_Sort(int A[100], int n) { struct Element_Stack // kiể u phầ n tử trong Stack { int q, r; } ; Element_Stack Stack[50]; // Stack có tối đa 50 phầ n tử int sp=0; // con trỏ Stack, khởi tạ o sp=0 int i,j,x,q,r,temp; Stack[0].q =0 ; // chỉ số đầ u của mả ng cầ n sắ p Stack[0].r =n-1; // chỉ số cuối của mả ng cầ n sắ p do { // Lấ y một phâ n hoạ ch ra từ Stack q = Stack[sp].q ; r =Stack[sp].r ; sp--; // Xóa 1 phầ n tử khỏi Stack do { // Phâ n đoạ n d∙ y con a[q] ,..., a[r] i = q; j =r; x = A[(q+r) / 2] ; // Lấ y phầ n tử giữa của d∙ y cầ n sắ p thứ tự là m chốt do { while (A[i] < x) i++; //Tì m phầ n tử đầ u tiê n có trị lớn hơn hay bằ ng x while (A[j] > x) j--; //Tì m phầ n tử đầ u tiê n có trị nhỏ hơn hay bằ ng x if (i<=j) // Đổi chỗ A[i] với A[j] { temp = A[i]; A[i] =A[j]; A[j] = temp; i++ ; j--; } } while (i<=j); Kỹ thuật lập trì nh 79 if (i<r) // phầ n thứ ba có từ 2 phầ n tử trở lê n { // Đưa và o Stack chỉ số đầ u và chỉ số cuối của phầ n thứ ba sp++; Stack[sp].q=i; Stack[sp].r=r; } r = j ; // Chuẩ n bị vị trí để phâ n hoạ ch phầ n có giá trị nhỏ hơn chốt } while (q< r); } while (sp!=-1); // Ket thuc khi Stack rong } int Nhap_day_so (int A[]) /* Tạ o d∙ y n số ngẫ u nhiê n từ 0 đế n 9999 đưa và o mả ng A */ { int i,n; printf("\nSo phan tu cua mang :"); scanf("%d",&n); randomize(); // dùng và for (i=0; i<n; i++) A[i]= rand() % 10000; // Phá t sinh cá c số ngẫ u nhiê n từ 0 đế n 9999 return n; } void Liet_ke (char str[],int A[], int n) { int i; printf("\n%s\n",str); for (i=0; i<n; i++) printf ("%5d",A[i]); getch(); } void main() { size= Nhap_day_so(mang); Liet_ke("Day so ngau nhien :",mang,size); Quick_Sort(mang,size); Liet_ke("Gia tri mang da duoc sap :",mang,size); } b. Giải thuật Quick Sort đệ qui: về cơ chế thực hiệ n thì cũng giống như Kỹ thuật lập trì nh 80 giả i thuậ t không đệ qui, nhưng ta không kiể m soá t Stack mà để cho quá trì nh gọi đệ qui tự tạ o ra Stack. * Chương trì nh: void Sort(int A[], int q,int r) { int temp; int i=q; int j=r; int x = A[(q+r) / 2] ; // Lấ y phầ n tử giữa của d∙ y cầ n sắ p thứ tự là m chốt do { // Phâ n đoạ n d∙ y con a[q] ,..., a[r] while (A[i] < x) i++; //Tì m phầ n tử đầ u tiê n có trị lớn hơn hay bằ ng x while (A[j] > x) j--; //Tì m phầ n tử đầ u tiê n có trị nhỏ hơn hay bằ ng x if (i<=j) // Doi cho A[i] voi A[j] { temp = A[i]; A[i] =A[j]; A[j] = temp; i++ ; j--; } } while (i<=j); if (q<j) // phầ n thứ nhấ t có từ 2 phầ n tử trở lê n Sort(A,q,j); if (i<r) // phầ n thứ ba có từ 2 phầ n tử trở lê n Sort (A,i,r); } void Quick_Sort(int A[], int n) { Sort( A,0,n-1); // Gọi hà m Sort với phầ n tử đầ u có chỉ số 0 đế n // phầ n tử cuối cùng có chỉ số n-1 } III. Tìm kiếm trên mảng đã có thứ tự: Giả sử d∙y số của ta là d∙y số đ∙ có thứ tự tă ng dầ n, và x là giá trị cầ n tì m. Cá c hà m tì m kiế m sẽ trả về trị -1 nế u không có x trong d∙y, ngược lạ i cá c hà m tì m kiế m sẽ trả về chỉ số của x trong d∙ y. III.1. Tì m kiế m nhanh bằng phương pháp lặp: - Nội dung: Do d∙ y số đ∙ có thứ tự tă ng dầ n, nê n nế u ta tì m được phầ n tử đầ u tiê n có trị vừa lớn hơn x thì ta có thể kế t luậ n d∙ y số không chứa trị x. Vì vậ y, ta sẽ rút ngắ n thời gian tì m kiế m. Kỹ thuật lập trì nh 81 - Giả i thuậ t: int Search(int A[], int n, int x) { int i=0; while (i<n && A[i] < x) i++; return (i<n && A[i]==x ? i : -1) ; } void main() { int so,vitri; size= Nhap_day_so(mang); Quick_Sort(mang,size); Liet_ke("Gia tri mang da duoc sap :",mang,size); printf("\nGia tri muon tim :"); scanf("%d",&so); vitri = Search(mang,size, so); if (vitri !=-1) printf("Vi tri cua so %d trong day = %d",so,vitri); else printf(" Khong co so %d trong day",so); getch(); } III.2. Phép tì m kiế m nhị phân: - Nội dung: ! Bước 1: Phạ m vi tì m kiế m ban đầ u là toà n bộ danh sá ch. ! Bước 2: Lấ y phầ n tử chí nh giữa của phạ m vi tì m kiế m (gọi là y) so sá nh với x. Nế u x=y thì ta đ∙ tì m thấ y, trả về chỉ số. Giả i thuậ t kế t thúc Nế u x < y thì phạ m vi tì m kiế m mới là cá c phầ n tử nằ m phí a trước của y. Nế u x > y thì phạ m vi tì m kiế m mới là cá c phầ n tử nằ m phí a sau của y. ! Bước 3: Nế u còn tồn tạ i phạ m vi tì m kiế m thì lặ p lạ i bước 2, ngược lạ i giả i thuậ t kế t thúc với kế t quả là không có x trong d∙ y số. - Giả i thuậ t: int Binary_Search(int A[], int n, int x) { unsigned char found=FALSE; // Giả sử ban đầ u ta chưa tì m thấ y x trong d∙ y // Phạ m vi ban đầ u tì m kiế m là từ k=0 % m = n-1 Kỹ thuật lập trì nh 82 int k=0; int m=n-1; int j; while (k<=m && !found) { j=(k+m) /2; //chỉ số phầ n tử giữa if (A[j]==x) found=TRUE; else if (x>A[j]) k=j+1; // Phạ m vi tì m mới là (j+1, m) else m=j-1; // Phạ m vi tì m mới là (k, j-1) } return (found ? j : -1) ; } III.3. Phép tì m kiế m nhị phân đệ qui: - Nội dung: tương tự như trê n ! Bước 1: Phạ m vi tì m kiế m ban đầ u là toà n bộ danh sá ch (k=0%m=n-1). ! Bước 2: Lấ y phầ n tử chí nh giữa của phạ m vi tì m kiế m (gọi là y) so sá nh với x. Nế u x=y thì ta đ∙ tì m thấ y, trả về chỉ số. Giả i thuậ t kế t thúc Nế u x < y thì phạ m vi tì m kiế m mới là cá c phầ n tử nằ m phí a trước của y, nê n ta gọi đệ qui với phạ m vi mới là (k,j-1) Nế u x > y thì phạ m vi tì m kiế m mới là cá c phầ n tử nằ m phí a sau của y, nê n ta gọi đệ qui với phạ m vi mới l