Tài liệu tham khảo hỗ trợ môn học Cấu trúc dữ liệu 2

urn(false); 
 } 
//--------------------------- 
int EoR(FILE *f) 
 {float x,y; 
 if(ftell(f)==0) return(false); 
 if(fread(&y,sz,1,f)<=0) return(true); 
 fseek(f,-2.0*sz,1); 
 fread(&x,sz,1,f); 
 if(x<=y) return(false); 
 else 
 return(true); 
 } 
//--------------------------- 
int FileNodes(char *TenTep) 
 {int k;float x; 
 FILE *f = fopen(TenTep,"rb"); 
 fseek(f,0,2);//Ve cuoi tep 
 k = ftell(f)/sz; 
 fclose(f); 
 return(k); 
 }; 
//--------------------------- 
//Tao file co n phan tu 
void CreateFile(char *TenTep) 
 {int i,m;float x; 
 FILE* f; 
 f = fopen(TenTep,"wb"); 
 rewind(f); 
 char ch; 
 do 
 {clrscr(); 
 printf("\nNhap du lieu vao tep:"); 
 printf("\n1. Nhap truc tiep"); 
 printf("\n2. Tao ngau nhien"); 
 printf("\n\n Hay chon 1 hoac 2: "); 
 ch=getche(); 
 } 
 while(ch!='1'&& ch!='2'); 
 printf("\nCho biet so phan tu can dua vao tep: "); 
 scanf("%d",&m); 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 110
 if(ch=='1') 
 {printf("\nHay nhap %d so: ",m); 
 for(i=0;i<m;i++) 
 {scanf("%f",&x); 
 fwrite(&x,sz,1,f); 
 } 
 } 
 else 
 {randomize(); 
 for(i=0;i<m;i++) 
 {x=float(random(5*m)); 
 fwrite(&x,sz,1,f); 
 } 
 } 
 fclose(f); 
 }; 
//--------------------------- 
//Hien thi noi dung file len man hinh 
void ViewFile(char *TenTep) 
 {float x; 
 FILE* f; 
 f = fopen(TenTep,"rb"); 
 rewind(f); 
 printf("\nCac phan tu tren tep %s: ",TenTep); 
 printf("\n\n"); 
 while(fread(&x,sz,1,f)>0) printf("%5.0f",x); 
 fclose(f); 
 }; 
//--------------------------- 
//Chia xoay vong tung run tren file a cho cac file nguon cho den khi het a 
void SplitFile(char *TenTep,char *TepNguon[], int &nWay) 
 { 
 FILE *f[10], *a;float x;int i,j,k; 
 for(i=0;i<nWay;i++) f[i] = fopen(TepNguon[i],"wb"); 
 a = fopen(TenTep,"rb"); 
 rewind(a); 
 for(i=0;i<nWay;i++) rewind(f[i]); 
 while(!EoF(a)) 
 {//Chia xoay vong lan luot cac run tren a cho f[0],f[1],...,f[nWay-1] 
 //hoac chi den f[k] nao do neu het phan tu tren a 
 for(i=0;i<nWay;i++) 
 {if(EoF(a)) break; 
 fread(&x,sz,1,a); 
 fwrite(&x,sz,1,f[i]); 
 while(!EoR(a)) 
 {fread(&x,sz,1,a); 
 fwrite(&x,sz,1,f[i]); 
 } 
 } 
 } 
 fclose(a); 
 for(i=0;i<nWay;i++) fclose(f[i]); 
 for(i=0;i0;i++); 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 111
 nWay=i; 
 }; 
//--------------------------- 
//Tron cac bo run tren cac tep nguon va dua vao cac tep dich 
//cho den khi chi con mot tep dich 
void MergeFile(char *TepNguon[10],char *TepDich[10], int &nWay) 
 {FILE *f[10], *g[10];float x[10],t,t1; 
 int i,j,k,con_x[10],nNguon,CurrDich; 
 /*Neu run tren f[i] chua het thi con_x[i] =true 
 Neu het roi thi con_x[i] = false 
 nNguon la so file nguon co phan tu 
 nDich la so File dich da duoc cap phan tu 
 CurrDich la file dich hien thoi duoc ghi run 
 */ 
 for(i=0;i<nWay;i++) 
 {f[i] = fopen(TepNguon[i],"rb"); 
 rewind(f[i]); 
 g[i] = fopen(TepDich[i],"wb"); 
 } 
 CurrDich=0; 
 while(true) //Se ket thuc khi het cac phan tu tren file nguon 
 {//Vi cac run duoc phan phoi duoc phan bo tu i = 0 do do co the co 
 //mot so tep o phan cuoi co it hon 1 run 
 j=0; 
 for(i=0;i<nWay;i++) 
 if(fread(&t,sz,1,f[i])>0) 
 {x[i]=t;con_x[i]=true;j++;} 
 else 
 con_x[i]=false; 
 nNguon=j; 
 if(nNguon==0) break;//Da het cac phan tu tren cac file nguon 
 while(true) //Bat dau tron cac run va dua vao g[CurrDich] 
 {//Tim phan tu be nhat o dau run trong bo run 
 i=0;//Tim vi tri dau tien con phan tu trong run 
 while(!con_x[i] && i<nWay)i++;//Tim run dang con phan tu 
 if(i==nWay) //Het phan tu trong bo run, chuyen sang bo run khac 
 {CurrDich++;CurrDich = CurrDich%nWay;break;} 
 t = x[i];k=i; 
 for(j=i+1;j<nWay;j++) 
 if(con_x[j] && x[j]<t) {t=x[j];k=j;} 
 //x[k] chinh la gia tri nho nhat trong bo run hien thoi 
 fwrite(&t,sz,1,g[CurrDich]); 
 if(EoR(f[k])) 
 con_x[k]=false; 
 else 
 {fread(&t1,sz,1,f[k]); 
 x[k]=t1; 
 } 
 } 
 } 
 for(i=0;i<nWay;i++) {fclose(f[i]);fclose(g[i]);} 
 for(i=0;i0;i++); nWay=i; 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 112
 }; 
//--------------------------- 
//Kiem tra neu tep da sap xep thi tra ve true 
int SortedFile(char *TenTep) 
 {FILE *f;float x,y; 
 f = fopen(TenTep,"rb"); 
 rewind(f); 
 fread(&x,sz,1,f); 
 while(fread(&y,sz,1,f)>0) 
 {if(x>y) {fclose(f);return(false);} 
 x = y; 
 } 
 fclose(f); 
 return(true); 
 } 
//--------------------------- 
void CopyFile(char *Tep1, char *Tep2) 
 {FILE *f1, *f2;float x; 
 f1 = fopen(Tep1,"rb"); 
 f2 = fopen(Tep2,"wb"); 
 rewind(f1); 
 while(fread(&x,sz,1,f1)>0) fwrite(&x,sz,1,f2); 
 fclose(f1);fclose(f2); 
 } 
//--------------------------- 
//Sap xep tep co ten la TenTep bang phuong phap tron 
void SortFile(char *TenTep) 
 {int i,n,nWay; 
 char *TepNguon[10],*TepDich[10]; 
 char *s; 
 s= new char[12]; 
 n=0; 
 do 
 {printf("\nSo duong can tron n (1<n<=10) = "); 
 scanf("%d",&n); 
 } 
 while(n10); 
 for(i=0;i<n;i++) 
 {TepNguon[i] = new char[12]; 
 TepDich[i] = new char[12]; 
 } 
 for(i=0;i<n;i++) 
 {s = itoa(i,s,10); 
 strcpy(TepNguon[i],"ZZN"); 
 strcat(TepNguon[i],s); 
 strcat(TepNguon[i],".DAT"); 
 strcpy(TepDich[i],"ZZD"); 
 strcat(TepDich[i],s); 
 strcat(TepDich[i],".DAT"); 
 } 
 nWay=n; 
 SplitFile(TenTep,TepNguon,nWay); 
 while(true) 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 113
 {MergeFile(TepNguon,TepDich,nWay); 
 if(nWay==1)break; 
 for(i=0;i<nWay;i++) 
 {strcpy(s,TepNguon[i]); 
 strcpy(TepNguon[i],TepDich[i]); 
 strcpy(TepDich[i],s); 
 } 
 } 
 CopyFile(TepDich[0],TenTep); 
 for(i=0;i<n;i++) {remove(TepNguon[i]);remove(TepDich[i]);} 
 } 
4. Ch−ơng trình 23HASHTR.CPP: Cài đặt bảng băm dùng liên kết trong 
//23HASHTR.CPP 
//Bang bam dung lien ket trong noi bo bang ma thoi 
#include 
#include 
#include 
#include 
#include 
#include 
#define true 1 
#define false 0 
//--------------------------- 
struct node 
 {int* pkey; 
 int next; 
 }; 
//--------------------------- 
class Hash 
 {public: 
 node* H; 
 int max; 
 int count; 
 int current; 
 Hash(int); 
 ~Hash(); 
 int empty(); 
 int full(); 
 int size(); 
 void display(); 
 void traverse(); 
 int search(int); 
 void insert(int); 
 }; 
//--------------------------- 
template 
void swap(T& x,T& y) 
 {T tmp=x;x=y;y=tmp; 
 } 
//--------------------------- 
Hash::Hash(int size=10) 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 114
 {max=size; 
 H = new node[max]; 
 for(int i=0;i<max;i++) 
 {H[i].pkey=NULL;H[i].next=-1; 
 } 
 count=0; 
 }; 
//--------------------------- 
Hash::~Hash() 
 {for(int i=0;i<max;i++) delete H[i].pkey; 
 }; 
//--------------------------- 
int Hash::empty() 
 {return count==0; 
 } 
//--------------------------- 
int Hash::full() 
 {return count==max; 
 } 
//--------------------------- 
int Hash::size() 
 {return count; 
 } 
//--------------------------- 
void Hash::display() 
 {if( H[current].pkey!=NULL) cout<<endl<<* H[current].pkey; 
 }; 
//--------------------------- 
//Hien toan bo danh sach len man hinh. 
void Hash::traverse() 
 {cout<<endl<<" Key Next" ; 
 for(int i=0;i<max;i++) 
 {cout<<endl<<i<<" : "; 
 if(H[i].pkey!=NULL) cout<<*H[i].pkey<<" "<<H[i].next; 
 } 
 } 
//--------------------------- 
//Them nut co noi dung x vao bang bam. 
void Hash::insert(int x) 
 {if(full()) {cout<<endl<<"Bang bam day, khong chen duoc";return;} 
 if(search(x)) {cout<<endl<<"Nut da co, khong chen duoc";return;} 
 int k,i,j; 
 k=x%max; 
 if( H[k].pkey==NULL) 
 { H[k].pkey=new int;* H[k].pkey=x;count++; return;} 
 if(* H[k].pkey%max==k) //Cung lop co phan du la d 
 {i=k; 
 while( H[i].next!=-1) i= H[i].next; 
 for(j=max-1; H[j].pkey!=NULL;j--); 
 H[i].next=j; 
 H[j].pkey=new int; 
 * H[j].pkey=x; 
 H[j].next=-1; 
 count++; 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 115
 return; 
 } 
 //Truong hop x khong cung so du voi i, ta tim mot vi tri trong de chen 
 for(j=max-1;j>0 && H[j].pkey!=NULL;j--); 
 H[j].pkey=new int; 
 * H[j].pkey=x; 
 H[j].next=-1; 
 count++; 
 return; 
 } 
//--------------------------- 
//Tim con tro co noi dung x trong danh sach 
int Hash::search(int x) 
 {int k,i,j; 
 k=x%max; 
 if(* H[k].pkey%max==k) //Cung lop co phan du la d 
 {i=k; 
 while( H[i].pkey!=NULL) 
 {if(* H[i].pkey==x) {current=i;return true;} 
 if( H[i].next==-1) break; else i= H[i].next; 
 } 
 return false; 
 } 
 for(j=max-1; H[j].pkey!=NULL;j--) 
 if(* H[j].pkey==x) {current=j;return true;} 
 return false; 
 }; 
//--------------------------- 
void main() 
 {Hash H(10);int i,x; 
 while(true) 
 {clrscr(); 
 //Tao menu 
 cout<<endl<<" 1. Bang bam co bi rong khong"; 
 cout<<endl<<" 2. Them phan tu x vao bang bam"; 
 cout<<endl<<" 3. Tim phan tu x trong bang bam"; 
 cout<<endl<<" 4. Duyet bang bam "; 
 cout<<endl<<" z. Ket thuc"; 
 cout z de chon: "; 
 char chon=toupper(getch()); 
 if(chon=='Z') break; 
 switch(chon) 
 {case '1':if(H.empty()) cout<<endl<<"Bang bam rong"; 
 else cout<<endl<<"Bang bam khong rong";break; 
 case '2':cout>x; 
 H.insert(x);break; 
 case '3':cout>x; 
 if(H.search(x)) {cout<<endl<<"Phan tu tim thay la "; 
 H.display();} 
 else cout<<endl<<"Khong tim thay";break; 
 case '4':H.traverse();break; 
 } 
 cout<<endl<<endl<<"Nhan phim bat ky de tiep tuc"; 
 getch(); 
Cấu trúc dữ liệu 2 - Câu hỏi lý thuyết và các bài thực hành chuẩn bị cho thi hết môn 
 116
 } 
 }