VC++2012编程演练数据结构《20》索引文件

大灰狼

索引文件由索引表和主文件两部分构成。
　　索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项称作索引项。索引项是按键（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。


（1）索引顺序文件


　　(Indexed Sequential File)
　　主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。


（2）索引非顺序文件


　　(Indexed NonSequentail File)
　　主文件按主关键字无序得文件称索引非顺序文件。在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。


注意：


　　① 通常将索引非顺序文件简称为索引文件。
　　② 索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。
　　③ 索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。
　　④ 索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。

　　⑤ 最常用的索引顺序文件：ISAM文件和VSAM文件。

我们创建一个工程

实现索引类如下

[cpp] view plaincopy

• // Index.h: interface for the Index class.  
• //  
• //////////////////////////////////////////////////////////////////////  
•   
• #if !defined(AFX_INDEX_H__68B93657_9E7D_4BE5_9259_4780B68E38BD__INCLUDED_)  
• #define AFX_INDEX_H__68B93657_9E7D_4BE5_9259_4780B68E38BD__INCLUDED_  
•   
• #if _MSC_VER > 1000  
• #pragma once  
• #endif // _MSC_VER > 1000  
•   
• #include<iomanip>  
• #include<stdio.h>  
• #include<stdlib.h>  
• #include<fstream>  
• //定义一次读写文件的逻辑块的大小  
• const int m=5;  
• //设主文件记录的逻辑删除标记  
• const int DMark=-10;  
• //设关键字的类型为整型  
• typedef int KeyType;  
• //主文件中的记录类型  
• struct ElemType {  
•     KeyType key;  //关键字域  
•     char rest[10];//其他域,暂用字符数组表示  
• };  
• //索引文件中的记录类型  
• struct IndexItem {  
•     KeyType key;  //关键字域  
•     int next;  //保存对应记录的存储位置域  
• };  
• //索引文件的类定义  
• template<class T,class T1>  
• class InFile  
• {public:  
• //顺序打印出主文件fn1中的每个记录  
• void PrintMainFile(char* fn1);  
• //顺序打印出索引有序文件fn2中的每个索引项  
• void PrintIndexFile(char* fn2);  
• //向物理文件名为fn1指针所指主文件中追加n个记录  
• void MFAppend(char* fn1,char* fn2,T1 a[],int n);  
• //从物理文件名为fn1指针所指主文件中删除n个记录  
• void MFDelete(char* fn1,char* fn2,KeyType a[],int n);  
• //从物理文件名为fn1指针所指主文件中查找n个记录  
• void MFSearch(char* fn1,char* fn2,KeyType a[],int n);  
• //把一个记录的索引项插入到有序数组A中  
• void SeqInsert(T A[], int mm, T x);  
• //向由fn2指针所表示的索引有序文件中插入x索引项  
• void IFInsert(char *fn2, T x);  
• //从有序数组A中删除一个关键字为x.key的索引项  
• bool SeqDelete(T A[],int mm,T& x);  
• //从由fn2指针所表示的索引有序文件中删除  
• //关键字为x.key的索引项,并由x带回被删除的索引项  
• bool IFDelete(char *fn2, T& x);  
• //从由fn2指针所表示的索引有序文件中  
• //查找关键字为x.key的索引项并由x带回  
• bool IFSearch(char* fn2, T& x);  
• };  
•   
• //索引文件的类实现  
• //顺序打印出主文件fn1中的每个记录  
• template<class T,class T1>  
• void InFile<T,T1>::PrintMainFile(char* fn1)  
• {ifstream fin(fn1,ios::in|ios::binary);  
• if(!fin)  
•   {cerr<<fn1<<' '<<"not find!"<<endl;exit(1);}  
• T1 x;  
• fin.seekg(0,ios::end);       //将文件指针移至文件未  
• int b1=sizeof(T1);  
• int n=fin.tellg()/b1;        //用n表示文件所含的记录数  
• fin.seekg(0);                //将文件指针移至文件首  
• for(int i=0;i<n;i++) {  
•     fin.read((char*) &x, b1); //从文件中读出一条记录  
•     if(i%4==0)  cout<<endl;   //每行显示4个数据  
•     cout<<setw(5)<<x.key<<setw(10)<<x.rest;}  
•     cout<<endl;  
•     fin.close();}  
• //顺序打印出索引有序文件fn2中的每个索引项  
• template<class T,class T1>  
• void InFile<T,T1>::PrintIndexFile(char* fn2)  
• {ifstream fin(fn2,ios::in|ios::binary);  
• if(!fin)  
•   {cerr<<fn2<<' '<<"not find!"<<endl;exit(1);}  
• T x;  
• fin.seekg(0,ios::end);     //将文件指针移至文件未  
• int b2=sizeof(T);  
• int n=fin.tellg()/b2;      //用n表示文件所含的记录数  
• fin.seekg(0);              //将文件指针移至文件首  
• for(int i=0;i<n;i++) {  
• fin.read((char*) &x, b2);  //从文件中读出一个索引项  
• if(i%8==0)  cout<<endl;    //每行显示8个数据  
• cout<<setw(4)<<x.key<<setw(3)<<x.next;}  
•   cout<<endl;  
• fin.close();}  
• //向物理文件名为fn1指针所指主文件中追加n个记录  
• template<class T,class T1>  
• void InFile<T,T1>::MFAppend(char* fn1,char* fn2,T1 a[],int n)  
• {//定义一个输出文件流对象ofs,与主文件相联系  
• ofstream ofs(fn1,ios::out|ios::binary);  
• if(!ofs)  
•   {cerr<<fn1<<' '<<"not open!"<<endl;exit(1);}  
• int i;  
• //求出T1记录类型的长度  
• int b1=sizeof(T1);  
• //把文件指针移到文件尾  
• ofs.seekp(0, ios::end);  
• //求出当前主文件长度  
• int flen=ofs.tellp()/b1;  
• //把a数组中的n个记录写入到主文件中  
• for(i=0; i<n; i++)  
•    ofs.write((char*) &a,b1);  
• //关闭逻辑文件ofs  
• ofs.close();  
• //把a中n个记录的索引项依次插入到索引文件fn2中  
• T x;  
• for(i=0; i<n; i++) {  
•   x.key=a.key;  
•   x.next=flen+i;  
•   IFInsert(fn2,x);}  
• }  
• //从物理文件名为fn1指针所指主文件中删除n个记录  
• template<class T,class T1>  
• void InFile<T,T1>::MFDelete(char* fn1,char* fn2,KeyType a[],int n)  
• {//定义一个输入输出文件流对象fio,与主文件相联系  
• fstream fio(fn1,ios::in|ios::out|ios::binary);  
• if(!fio)  
•   {cerr<<fn1<<' '<<"not open!"<<endl;exit(1);}  
• int b1=sizeof(T1);  
• T x;  
• T1 y;  
• int i;  
• //依次删除每条记录  
•   for(i=0; i<n; i++) {  
•     x.key=a;  
•     bool k=IFDelete(fn2,x);  
•     if(!k)  
•      {cout<<"关键字为"<<x.key<<"的记录不存在"<<endl;continue;}  
•     fio.seekg(x.next*b1);  
•     fio.read((char*) &y, b1);  
•     y.key=DMark;  
•     fio.seekg(-b1, ios::cur);  
•     fio.write((char*) &y, b1);  
•     cout<<"关键字为"<<x.key<<"的记录被删除"<<endl;}  
•     fio.close();  
• }  
• //从物理文件名为fn1指针所指主文件中查找n个记录  
• template<class T,class T1>  
• void InFile<T,T1>::MFSearch(char* fn1,char* fn2,KeyType a[],int n)  
• {//定义一个输入输出文件流对象ifs,与主文件相联系  
• ifstream ifs(fn1,ios::in|ios::binary);  
• if(!ifs)  
•   {cerr<<fn1<<' '<<"not open!"<<endl;exit(1);}  
• int b1=sizeof(T1);  
• T x;  
• T1 y;  
• int i;  
• //依次查找每条记录  
• for(i=0; i<n; i++) {  
•    x.key=a;  
•    bool k=IFSearch(fn2,x);  
•    if(!k)  
•     {cout<<"查找关键字为"<<x.key<<"的记录失败!"<<endl;continue;}  
•    ifs.seekg(x.next*b1);  
•    ifs.read((char*) &y, b1);  
•    cout<<"查找关键字为"<<x.key<<"的记录成功!"<<endl;  
•    cout<<"该记录内容为:"<<y.key<<' '<<y.rest<<endl;}  
• ifs.close();  
• }  
• //把一个记录的索引项插入到有序数组A中  
• template<class T,class T1>  
• void InFile<T,T1>::SeqInsert(T A[],int mm,T x)  
• {int i;  
• for(i=mm-1;i>=0;i--)  
•   {//从尾部向前为寻找插入位置进行顺序比较和移动  
•    if(A.key>x.key) A[i+1]=A;  
•    else {A[i+1]=x; break;}}  
• if(i<0) A[0]=x;  
• }  
• //向由fn2指针所表示的索引有序文件中插入x索引项  
• template<class T,class T1>  
• void InFile<T,T1>::IFInsert(char *fn2, T x)  
• {//以输入方式打开由fn2指针所表示的索引有序文件  
• fstream ifs(fn2,ios::in|ios::binary);  
• if(!ifs)  
•   {cerr<<fn2<<' '<<"not open!"<<endl;exit(1);}  
• //以输出方式打开temp文件  
• ofstream ofs(".\\temp",ios::out|ios::binary);  
• if(!ofs)  
•   {cerr<<"temp"<<' '<<"not open!"<<endl;exit(1);}  
• //动态定义一个具有m+1个元素的数组A  
• T* A=new T[m+1];  
• //将原文件指针指向文件开始位置，此语句可省略  
• ifs.seekg(0);  
• //通过while循环完成插入操作  
• int b2=sizeof(T);  
• while(1)  
•   {ifs.read((char*)A, m*b2);  
•    int s=ifs.gcount()/b2;  
•    //读入数组A的实际索引项数被存入s中  
•    if(s==m)  
•     {if(A[m-1].key<x.key) {  
•       ofs.write((char*)A,m*b2);}  
•      else {  
•       SeqInsert(A, m, x);//将x索引项插入到有序数组A中  
•       ofs.write((char*)A,(m+1)*b2);  
•       while(!ifs.eof())  
•       { //把原文件中剩余的所有记录写入到结果文件中  
•        ifs.read((char*)A, m*b2);  
•        s=ifs.gcount()/b2;  
•        ofs.write((char*)A, s*b2);}  
•      break;  //退出while(1)循环  
•    }}  
•    else  
•      {SeqInsert(A, s, x);  
•       ofs.write((char*)A, (s+1)*b2);  
•       break;//处理完最后一个数据块时退出while(1)循环  
•    }}  
•    delete [] A;  
•    ifs.close();  
•    ofs.close();  
•    remove(fn2);  
•    rename("temp",fn2);  
• }  
• //从有序数组A中删除一个关键字为x.key的索引项  
• template<class T,class T1>  
• bool InFile<T,T1>::SeqDelete(T A[], int mm, T& x)  
• {//从数组A的首元素开始顺序查找关键字为x.key的索引项  
• int i=0;  
• while(i<mm && A.key<x.key) i++;  
• //若不存在待删除的索引项则返回假  
• if(i==mm || A.key!=x.key) return false;  
• //被删除的索引项赋给x带回  
• x=A;  
• //使i+1至mm-1的所有元素前移一个位置  
• for(int j=i+1; j<mm; j++) A[j-1]=A[j];  
• //返回真表示删除成功  
• return true;  
• }  
• //从由fn2指针所表示的索引有序文件中删除  
• //关键字为x.key的索引项,并由x带回被删除的索引项  
• template<class T,class T1>  
• bool InFile<T,T1>::IFDelete(char *fn2, T& x)  
• {//以输入方式打开由fn2指针所表示的索引有序文件  
• ifstream ifs(fn2, ios::in|ios::binary);  
• if(!ifs) {  
•    cerr<<fn2<<' '<<"not found!"<<endl;exit(1);}  
• //以输出方式打开temp文件  
• ofstream ofs("temp",ios::out|ios::binary);  
• if(!ofs) {  
•    cerr<<"temp"<<' '<<"not open!"<<endl;exit(1);}  
• int b2=sizeof(T);  
• //动态定义一个具有m个元素的数组A  
• T* A=new T[m];  
• //用d等于true或false表示删除是否成功  
• bool d;  
• //通过while完成删除操作  
• while(1)  
•   {ifs.read((char*)A, m*b2);  
•    int s=ifs.gcount()/b2;  
•    //读入数组A的实际索引项数被存入s中  
•    if(s==m)  
•    {if(A[m-1].key<x.key) {  
•      ofs.write((char*)A, m*b2);}  
•     else {d=SeqDelete(A, m, x);  
•      if(d) ofs.write((char*)A,(m-1)*b2);  
•      else ofs.write((char*)A,m*b2);  
•   while(!ifs.eof())  
•    { //把原文件中剩余的所有记录写入到结果文件中  
•     ifs.read((char*)A, m*b2);  
•     s=ifs.gcount()/b2;  
•     ofs.write((char*)A, s*b2);}  
•     break;  //退出while(1)循环  
•    }}  
•    else  
•    {d=SeqDelete(A, s, x);  
•     if(d)  
•      ofs.write((char*)A, (s-1)*b2);  
•     else  
•      ofs.write((char*)A,s*b2);  
•     break;//处理完最后一个数据块时退出while(1)循环  
• }}  
• delete [] A;  
• ifs.close();  
• ofs.close();  
• remove(fn2);  
• rename("temp", fn2);  
• if(d) return true; else return false;  
• }  
• //从由fn2指针所表示的索引有序文件中  
• //查找关键字为x.key的索引项并由x带回  
• template<class T,class T1>  
• bool InFile<T,T1>::IFSearch(char* fn2, T& x)  
• {ifstream ifs(fn2,ios::in|ios::binary);  
• //以输入方式打开由fn2指针所表示的索引有序文件  
• if(!ifs)  
•   {cerr<<fn2<<' '<<"not found!"<<endl;exit(1);}  
• ifs.seekg(0,ios::end);  
• int b2=sizeof(T);  
• int n=ifs.tellg()/b2;  
• ifs.seekg(0);  
• int low=0, high=n-1;  
• while(low<=high)  
•    { //计算区间中点元素的下标  
•     int mid=(low+high)/2;  
•     //从文件中读入区间中点元素并赋给tm  
•     T tm;  
•     ifs.seekg(mid*b2);  
•     ifs.read((char*)&tm,b2);  
•     //查找成功后由x带回查找到的索引项并返回真  
•     if(x.key==tm.key) {x=tm;  
•      ifs.close();  
•      return true;}  
•     //在左子表中继续查找  
•     else if(x.key<tm.key)  
•       high=mid-1;  
•     //在右子表中继续查找  
•     else  low=mid+1;}  
•     ifs.close();  
•     return false;}//查找失败返回假  
•   
•   
• #endif // !defined(AFX_INDEX_H__68B93657_9E7D_4BE5_9259_4780B68E38BD__INCLUDED_)  
  

调用如下

[cpp] view plaincopy

• #include "stdafx.h"  
•   
• #include<iostream>  
• #include<stdlib.h>  
• #include<fstream>  
• #include<iomanip>  
• #include "Index.h"  
• //索引文件的类实现的测试  
• void main()  
• {cout<<"运行结果:\n";  
• //定义保存记录的数组a并初始化  
• ElemType a[15]={{13,"li"},{18,"liu"},{17,"wphp"},{37,"menrm"},  
• {8,"ytong"},{22,"zhua"},{24,"push"},{48,"qian"},{34,"tang"},  
• {57,"shdm"},{55,"kang"},{30,"liuli"},{25,"qiaoh"},  
• {31,"dukun"},{17,"haiang"}};  
• //定义保存记录关键字的数组b并初始化  
• KeyType b[16]={12,18,15,32,6,23,21,48,36,57,45,29,25,38,14,9};  
• //定义主文件和索引文件的名字，并由字符指针p1和p2所指向  
• char *p1=".\\HFile1.dat",*p2=".\\HFile1.idx";  
• int m;//记录个数  
• InFile<IndexItem,ElemType> myfile;  
• //利用键盘输入操作主文件、索引文件的插入、删除和查找  
• while(1) {  
•     cout<<endl<<"功能号表:"<<endl;  
•     cout<<"1---向主文件插入若干记录"<<endl;  
•     cout<<"2---从主文件中删除若干记录"<<endl;  
•     cout<<"3---从主文件中查找若干记录"<<endl;  
•     cout<<"4---输出主文件fn1"<<endl;  
•     cout<<"5---输出索引文件fn2"<<endl;  
•     cout<<"6---结束运行"<<endl;  
•     char ch;  
•     cout<<"请输入你的选择(1-6): ";cin>>ch;  
•     switch (ch)  
•     {case '1':cout<<"输入待插入记录个数m:";  
•        cin>>m;myfile.MFAppend(p1,p2,a,m);break;  
•     case '2':cout<<"输入待删除记录个数m:";  
•         cin>>m;myfile.MFDelete(p1,p2,b,m);break;  
•     case '3':cout<<"输入待查找记录个数m:";  
•         cin>>m;myfile.MFSearch(p1,p2,b,m);break;  
•     case '4':myfile.PrintMainFile(p1);break;  
•     case '5':myfile.PrintIndexFile(p2);break;  
•     case '6':return;  
•     default:cout<<"输入选择错误,请重输!"<<endl;  
• }}}  
  

效果如下