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

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

（1）索引顺序文件

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

（2）索引非顺序文件

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

注意：

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

实现索引类如下
[cpp]
// 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];//其他域,暂用字符数组表示
};   www.zzzyk.com
//索引文件中的记录类型
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[i],b1);
//关闭逻辑文件ofs
ofs.close();
//把a中n个记录的索引项依次插入到索引文件fn2中
T x;
for(i=0; i<n; i++) {
x.key=a[i].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[i];
    bool k=IFDelete(fn2,x);
    if(!k)
&nb

补充：软件开发 , Vc ,