《数据结构--文件》由会员分享，可在线阅读，更多相关《数据结构--文件（65页珍藏版）》请在金锄头文库上搜索。
1、 10.1 文件的基本概念 10.2 顺序文件10.4 Hash文件10.3 索引文件10.5 多关键字文件10.1 文件的基本概念10.1.1 什么是文件10.1.2 文件的逻辑结构及操作10.1.3 文件的存储结构10.1.1什么是文件数据库文件的每个记录由若干数据项构成。记 录是文件存取的基本单位，数据项是文件使用的最 小单位。数据项又称关键字项，关键字项的值称为 关键字(Key)。能惟一标识一个记录的关键字称为主 关键字，而其他的关键字称为次关键字。文件（File）是性质相同、逻辑上相关的 记录的集合。按文件记录的类型不同可以将文件分为两类： 操作系统文件和数据库文件。操作系统文件是一
2、维 的字符序列，无结构，无解释。数据库文件是带有 结构的记录集合。 图10-1所示是一个简单的学生文件，每个学生的情况是一个记录。每个记录由学号、姓 名、性别和年龄4个数据项组成。其中“学号”是主关键字，“姓名”、“性别”等是次关 键字。 学号姓名性别年龄200801001张小平男18200801002李立新女20200801003王鹏飞男19200801004王新刚男18200801005张惠女19图10-1 学生文件文件又可分为定长文件和不定长文件。和其它数据结构一样，文件结构也包括逻辑结构、存储结构以及文件上的各种操作这3个方面。文件的操作是定义在逻辑结构上的，但操作的具体实现要在存储结
3、构上进行若文件中记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称为定长文件；若文件中记录含有的信息长度不等，则称为不定长文件。10.1.2文件的逻辑结构及操作文件的逻辑结构是指文件的外部组织形式，是用户对数据的表示和存取方式。 文件中各记录之间存在着逻辑关系，当一个 文件的各记录按照某种次序排列起来时，各记录 之间自然地形成了一种线性关系。文件中的各个 记录最多只有一个前驱记录和一个后继记录，而 文件的第一个记录只有后继记录没有前驱记录， 文件的最后一个记录只有前驱记录没有后继记录 。所以可以把文件看成是线性结构。 文件上的操作主要有两类：检索和维护。文件检索就是在文
4、件中查找满足条件的记录，可以按记录的逻辑号查找，也可以按关键字查找。文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。10.1.3文件的存储结构文件的存储结构是指文件在物理存储介质（磁盘或磁带）上的组织形式，它决定了文件信息在存储设备上的存储位置。文件的存取方式与文件的物理结构有关。采用不同的组织形式就得到不同的存储结构。基本的组织有顺序组织、索引组织和Hash组织。 顺序文件是指记录按其在文件中的逻辑顺序依次存入存储介质而建立的，即顺 序文件中物理记录的顺序和逻辑记录的顺 序是一致的。若顺序文件中的记录按关键 字有序，则称此顺序文件为有序顺序文件 ，否则称为无序顺序文件。10.2
5、顺序文件顺序文件有如下特点：(1)存取第i个记录，必须先存取前面的第i-1个记录。(2)插入的新记录只能加在文件的末尾。(3)若要更新文件中的某个记录，必须将整个文件进行复制。顺序文件在存储介质中可以有两种不同的实现结构：连续结构和链结构。连续结构是指逻辑上相邻的记录其存储位置是相邻的，链结构是指物理记录之间的次序由指针链来表示。这两种结构对应的顺序文件分别称为连续顺序文件和链接顺序文件。图10-2为一个具有4个逻辑块的连续结 构文件，其逻辑块号0、1、2、3依次存放在 物理块15、16、17、18中。 连续结构的优点是：(2)顺序访问速度快，对于等长记录的连续文件可以进行顺序存取，也可以进行
6、类似折半查找的随机存取，但是对于不等长记录的连续文件只能进行顺序存取；(3)因为数据集中存放在连续的盘块中， 访问时所需的寻道次数和寻道时间少。 (1)结构简单；连续结构存储的缺点：(1)由于插入和删除记录会引起其它记录的移动，在外存中执行此操作会引起磁头的频繁来回移动，因此连续结构只能在文件的末尾插入记录，删除记录时，只作标记进行逻辑删除，只有用户指定物理删除时才真正删除相应记录，进行记录的移动；(2)顺序文件需要连续的盘块存放数据，因此，在插入记录时如果原来分配的盘块已没有空闲空间，而与其邻接的盘块也不空闲时，需要重新在外存中查找新的较大的空闲空间，并将原有数据移动到新空间中，然后才能插入
7、新的数据，因此，连续结构不易动态增长，而且外存容易存在碎片。图10-3为一个4个逻辑块的链结构文件的物理存储。使用链结构时，只要指明该文件的第一个块号就可以按链指针检索整个文件。链结构的另一个特点是文件长度可以动态地增长，只要调整链指针就可插入或删除一个信息块。链结构文件适用于顺序存取，不便于进行直接存取，存取第i个记录，必须搜索在它之前的i-1个记录。(1)提高了磁盘空间利用率，解决了磁盘碎片问题；(2)便于文件的插入和删除操作；链结构主要优点是：(3)便于文件的动态增长。从本质上讲，顺序文件就是线性表，因而对顺序文件的各种操作与线性表类似，但是，外存的访问速度比主存要慢的多，在考虑算法时要
8、立足于尽量减少外存的访问次数，寻道次数和寻道时间。 10.3 索引文件 10.3.1 ISAM文件10.3.2 VSAM文件10.3.1 ISAM文件 1. ISAM文件组成ISAM为Indexed Sequential Access Method(索引顺序存取方法)的缩写，它是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。 由于磁盘是以盘组、柱面和磁道三级地址存取的设备，所以可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。磁道索引中的每一个索引项，都由两个子索引项组成：基本索引和溢出索引项,每一子索引项又由关键字和指针两项组成。基本索引项关键字记录该磁道中最大（最末一个记录）的
9、关键字，指针记录该磁道中第一记录的位置；溢出索引项记录该磁道中溢出的记录的最大关键字，指针记录溢出区中的第一个记录。柱面索引每一索引项由关键字和指针两项组成，关键字记录该柱面中最大（最末一个记录） 的关键字，指针记录该柱面中磁道索引的位置。 柱面索引存放在某个柱面上，如果柱面索引过大 ，占多个磁道时，则建立柱面索引的索引主索 引。因此，ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。文件存放记录时遵循下面原则：记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上；对同一柱面，则应按盘面的次序顺序存放。 各种索引项结构如图10-5所示。 图10-6为一ISAM文
10、件结构示意图，从图中可看出，主索 引是柱面索引的索引，这里只有一级主索引。 当文件占用的柱面索引很大，使得一级主索引也很大时，可采用多级主索引。当然，若柱面索引较小时，则主索引可省 略。通常主索引和柱面索引放在同一个柱面上(图10-6是放在0号 柱面上)，主索引放在该柱面最前面的一个磁道上（图10-6中放 在0柱面0磁道上），其后的磁道中存放柱面索引。每个存放主文件的柱面都建立有一个磁道索引，放在该柱面的最前面的磁 道T0上，其后的若干个磁道是存放主文件记录的基本区，该柱面最后的若干个磁道是溢出区。基本区中的记录是按主关键字 大小顺序存储的，溢出区 被整个柱面上的基本区中各磁道共享 ，当基本区
11、中某磁道溢出时，就将该磁道的溢出记录，按主关 键字大小链成一个链表(溢出链表)放入溢出区。 2. ISAM文件的检索在ISAM文件上检索记录时，从主索引出发，找到相应的柱面索引；从柱面索引找到记录所在柱面的磁道索引；从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。若找遍该磁道均不存在此记录，则表明该文件中无此记录；若被查找的记录在溢出区，则可从磁道索引项的溢出索引项中得到溢出链表的头指针，然后对该表进行顺序查找。例如，要在图10-6中查找记录R136，先查主索引，即读入C0T0；因为1360)/比较性别returnelse return 0; int com
12、pareAge(STREC r1,STREC r2)if (r1.age r2.age)/比较年龄return 1;else return 0; 有了记录属性的比较函数，下面可以设计通用记录排序函数，排序函数中根据排序的次关键字不同调用不同的比较函数。 int studentSort(STREC rs,int len,int (*comp)(STREC r1, STREC r2 ) ) /排序函数，最后一个参数为函数指针 int i,j;STREC temp;for(i=0;ilen -1;i+)for(j=i+1;jlen;j+)if(*comp)(rsi,rsj)/*用函数指针调用传入的比
13、较函数*/ temp=rsj;rsj=rsi;rsi=temp; return 0; void invertSex(STREC *rs, int len)/*实现性别倒排表，将倒排表写到stSex.txt中，函数中rs为记录数组，len为记录个数*/FILE *outFile;int i;char temsex3=“;studentSort(rs,len,compSex);/*调用排序函数，在调用时把函数名compareSex作为参数传给函数指针*/outFile=fopen(“stSex.txt“,“w“);/性别倒排表文 for(i=0;ilen;i+) if(strcmp(rsi.sex
14、,temsex) /*当前次关键字值与前面处理的次关键值不同，形成新行*/ strcpy(temsex,rsi.sex );fprintf(outFile,“n“);fprintf(outFile,“%s %d“,rsi.sex, rsi.rec);/ rsi.rec代表当前记录号else fprintf(outFile,“ %d“, rsi.rec);fclose(outFile); void invertAge(STREC *rs, int len) /*实现年龄倒排表，将倒排表写到stAge.txt中，函数中rs为记录数组， len为记录个数 */FILE *outFile;int i;
15、nt temage;studentSort(rs,len,compareAge);/调用排序函数，在调用时把函数名compareAge作为参数传给函数指针 for(i=0;ilen; i+)if(rsi.age!=temage)/*当前次关键字值与前面处理的次关键值不同，形成新行*/outFile=fopen(“stAge.txt“,“w“);/年龄倒排表文件temage=-1 temage=rsi.age;fprintf(outFile,“n“);fprintf (outFile,“%d %d“,rsi.age, rsi.rec); else fprintf(outFile,“ %d“, rsi.rec); fclose(outFile);
