《【数据结构算法】文件》由会员分享，可在线阅读，更多相关《【数据结构算法】文件（39页珍藏版）》请在金锄头文库上搜索。
1、数据结构算法 Visual C+ 6.0程序集 侯 识 忠 等编著 中国水利水电出版社 第九章 文件 9、0 散列文件的插入、删除和查找操作 /散列文件的插入、删除和查找操作 /HashFM.cpp #include #include #include #include /m为散列表的长度,确定取值为16 const int m=16; /km为散列主文件中每个结点所含的元素个数， /取值大于等于1,暂取为3 const int km=3; /定义关键字类型为整型 typedef int KeyType; /索引主文件中的记录元素类型 struct ElemType int key; /关键字
2、域 char rest10;/其他域,暂用字符数组表示 ; /索引主文件中的结点类型 struct FLNode ElemType datakm;/值域 int next; /指向下一个结点的指针域 ; /b1为索引表文件中的记录长度 const int b1=sizeof(int); /b2为索引主文件中的记录长度 const int b2=sizeof(FLNode); /NullTag作为空关键字的标记,假定用-10表示 const int NullTag=-10; /散列文件的类定义 template class HFile public: /构造函数,初始化散列表文件和主文件 HFi
3、le(char* fn1,char* fn2); /把元素x插入到按桶散列的文件中 void THFInsertA(char* fn1,char* fn2,T x); /把数组x中n个元素插入到按桶散列的文件中 void THFInsertB(char* fn1,char* fn2,T x,int n); /从按桶散列的文件中删除关键字为x.key的元素, /并由x带回该元素,若删除成功则返回1,否则返回0 bool THFDelete(char* fn1, char* fn2, T /从按桶散列的文件中查找关键字为x.key的元素, /并由x带回该元素,若查找成功则返回1,否则返回0 boo
4、l THFSearch(char* fn1,char* fn2,T /按单链表顺序打印出按桶散列主文件中每个结点的所有元素值 void THFPrint(char* fn1,char* fn2); /散列文件的类实现 /初始化散列表文件和主文件 template HFile:HFile(char* fn1,char* fn2) /以输出方式打开并建立空的散列表文件 ofstream f1(fn1, ios:out|ios:binary); if(!f1) cerrfn1 不能打开!endl;exit(1); /以输出方式打开并建立空的散列主文件 ofstream f2(fn2, ios:out
5、|ios:binary); if(!f2) cerrfn2 不能打开!endl;exit(1); /动态分配具有m+1个整型存储空间的数组A int* A=new intm+1; if(!A)cerr申请堆内存失败!endl;exit(1); /给数组A中的每个元素赋初值-1，表示空指针 for(int i=0; im+1; i+) Ai=-1; /初始化散列表文件 f1.write(char*)A, (m+1)*b1); /删除数组A并关闭文件 delete A; f1.close(); f2.close(); /把元素x插入到按桶散列的文件中 template void HFile:THF
6、InsertA(char* fn1, char* fn2, T x) /以输入输出和不新建方式打开散列表文件 fstream f1(fn1,ios:in|ios:out|ios:binary); if(!f1) cerrfn1 不能打开!endl;exit(1); /以输入输出和不新建方式打开散列主文件 fstream f2(fn2, ios:in|ios:out|ios:binary); if(!f2)cerrfn2 不能打开!endl;exit(1); /给数组A中的每个元素赋初值-1，表示空指针 int* A=new intm+1; if(!A) cerr申请堆内存失败!endl; ex
7、it(1); /将散列表文件中的内容全部读入到数组A中 f1.read(char*)A, (m+1)*b1); /以关键字x.key计算x的散列地址 int d=x.key%m; /将x插入到d单链表的表头结点中 int j; FLNode temp; if(Ad!=-1) f2.seekg(Ad*b2); f2.read(char*) for(j=0; jkm; j+) if(temp.dataj.key=NullTag) break; if(jkm) temp.dataj=x; f2.seekg(-b2, ios:cur); f2.write(char*) goto END; /插入表头结
8、点后，转去做结束处理 /当d单链表为空或头结点中没有空闲位置时向下执行 /建立待插入d单链表表头的内存结点temp temp.data0=x; for(j=1; jkm; j+) temp.dataj.key=NullTag; temp.next=Ad; /将temp结点的值写入到f2文件尾并被链接到d单链表的表头 if(Am=-1) /将f2中的文件指针移至文件尾 f2.seekg(0,ios:end); /计算出文件尾的结点位置序号 int len=f2.tellg()/b2; /将temp结点的值写入文件尾 f2.write(char*) /使Ad指向新插入的结点 Ad=len; /将t
9、emp结点的值写入到f2文件的一个空闲结点中 /并被链接到d单链表的表头 else /p指向空闲单链表的表头结点 int p=Am; /使空闲单链表的表头指针指向其下一个结点 f2.seekg(p*b2); FLNode pn; f2.read(char*) Am=pn.next; /使temp的值写入到p位置的结点上 f2.seekg(-b2, ios:cur); f2.write(char*) /使Ad指向新插入的p结点 Ad=p; /将数组A中的全部内容写回到散列表文件f1中 f1.seekg(0); f1.write(char*)A, (m+1)*b1); /删除动态数组A和关闭所有文
10、件 END: delete A; f1.close(); f2.close(); /把数组x中n个元素插入到按桶散列的文件中 template void HFile:THFInsertB(char* fn1,char* fn2,T x,int n) fstream f1(fn1, ios:in|ios:out|ios:binary); if(!f1) cerrfn1 不能打开!endl; exit(1); fstream f2(fn2, ios:in|ios:out|ios:binary); if(!f2) cerrfn2 不能打开!endl; exit(1); int* A=new intm
11、+1; if(!A) cerr申请堆内存失败!endl; exit(1); f1.read(char*)A, (m+1)*b1); for(int i=0; in; i+) int d=xi.key%m; int j; FLNode temp; if(Ad!=-1) f2.seekg(Ad*b2); f2.read(char*) for(j=0; jkm; j+) if(temp.dataj.key=NullTag) break; if(jkm) temp.dataj=xi; f2.seekg(-b2, ios:cur); f2.write(char*) continue; temp.data
12、0=xi; for(j=1;jkm;j+) temp.dataj.key=NullTag; temp.next=Ad; if(Am=-1) f2.seekg(0,ios:end); int len=f2.tellg()/b2; f2.write(char*) Ad=len; else int p=Am; f2.seekg(p*b2); FLNode pn; f2.read(char*) Am=pn.next; f2.seekg(-b2, ios:cur); f2.write(char*) Ad=p; f1.seekg(0); f1.write(char*)A, (m+1)*b1); delet
13、e A; f1.close();f2.close(); /从按桶散列的文件中删除关键字为x.key的元素,并由x带回该 /元素,若删除成功则返回1,否则返回0 template bool HFile:THFDelete(char* fn1,char* fn2,T int k; if(!f1) cerrfn1 不能打开!endl; exit(1); fstream f2(fn2,ios:in|ios:out|ios:binary); if(!f2) cerrfn2 不能打开!endl; exit(1); int* A=new intm+1; if(!A) cerr申请堆内存失败!endl; ex
14、it(1); f1.read(char*)A, (m+1)*b1); int DeleteTag=0; /用DeleteTag作为删除是否成功的标记 int d=x.key%m; int p=Ad,i=0; /用p保存d单链表的表头结点的位置序号， /用i保存该结点中被删除元素的下标或第一个空元素的下标 FLNode temp; /从d单链表的表头结点中删除关键字为x.key的元素 if(p!=-1) f2.seekg(p*b2); f2.read(char*) while(ikm else i+; if(ikm /由x带回被删除的元素值 for(k=i+1; kkm; k+) if(temp.datak.key!=NullTag) temp.datak-1=temp.datak; else break; temp.datak-1.key=NullTag; if(k-1=0) /删除d单链表中表头空结点 Ad=temp.next; temp.next=Am; Am=p; f2.seekg(-b2, ios:cur); f2
