索引文件由索引表和主文件两部分构成。
索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项称作索引项。索引项是按键(或逻辑记录号)顺序排列。若文件本身也是按关键字顺序排列,则称为索引顺序文件。否则,称为索引非顺序文件。
(1)索引顺序文件
(Indexed Sequential File)
主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中,可对一组记录建立一个索引项。这种索引表称为稀疏索引。
(2)索引非顺序文件
(Indexed NonSequentail File)
主文件按主关键字无序得文件称索引非顺序文件。在索引非顺序文件中,必须为每个记录建立一个索引项,这样建立的索引表称为稠密索引。
注意:
① 通常将索引非顺序文件简称为索引文件。
② 索引非顺序文件主文件无序,顺序存取将会频繁地引起磁头移动,适合于随机存取,不适合于顺序存取。
③ 索引顺序文件的主文件是有序的,适合于随机存取、顺序存取。
④ 索引顺序文件的索引是稀疏索引。索引占用空间较少,是最常用的一种文件组织。
⑤ 最常用的索引顺序文件:ISAM文件和VSAM文件。
我们创建一个工程
实现索引类如下
// 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,
如果觉得《VC++编程演练数据结构《20》索引文件》对你有帮助,请点赞、收藏,并留下你的观点哦!