索引文件由索引表和主文件两部分构成。
索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项称作索引项。索引项是按键（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。
（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
#include
#include
#include
//定义一次读写文件的逻辑块的大小
const int m=5;
//设主文件记录的逻辑删除标记
const int DMark=-10;
//设关键字的类型为整型
typedef int KeyType;
//主文件中的记录类型
struct ElemType {
KeyType key; //关键字域
char rest[10];//其他域,暂用字符数组表示
}; www.2cto.com
//索引文件中的记录类型
struct IndexItem {
KeyType key; //关键字域
int next; //保存对应记录的存储位置域
};
//索引文件的类定义
template
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
void InFile::PrintMainFile(char* fn1)
{ifstream fin(fn1,ios::in|ios::binary);
if(!fin)
{cerr< 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 fin.read((char*) &x, b1); //从文件中读出一条记录
if(i%4==0) cout< cout< cout< fin.close();}
//顺序打印出索引有序文件fn2中的每个索引项
template
void InFile::PrintIndexFile(char* fn2)
{ifstream fin(fn2,ios::in|ios::binary);
if(!fin)
{cerr< 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 fin.read((char*) &x, b2); //从文件中读出一个索引项
if(i%8==0) cout< cout< cout< fin.close();}
//向物理文件名为fn1指针所指主文件中追加n个记录
template
void InFile::MFAppend(char* fn1,char* fn2,T1 a[],int n)
{//定义一个输出文件流对象ofs,与主文件相联系
ofstream ofs(fn1,ios::out|ios::binary);
if(!ofs)
{cerr< int i;
//求出T1记录类型的长度
int b1=sizeof(T1);
//把文件指针移到文件尾
ofs.seekp(0, ios::end);
//求出当前主文件长度
int flen=ofs.tellp()/b1;
//把a数组中的n个记录写入到主文件中
for(i=0; i ofs.write((char*) &a[i],b1);
//关闭逻辑文件ofs
ofs.close();
//把a中n个记录的索引项依次插入到索引文件fn2中
T x;
for(i=0; i x.key=a[i].key;
x.next=flen+i;
IFInse