数据结构第十二文件

《数据结构第十二文件》由会员分享，可在线阅读，更多相关《数据结构第十二文件（36页珍藏版）》请在装配图网上搜索。

1、 数据结构课程本章内容本章内容中国科大数据结构12-3 中国科大数据结构12-4 中国科大数据结构12-5 记录的逻辑结构与物理结构的差别示例记录的逻辑结构与物理结构的差别示例 中国科大数据结构12-6 n文件的修改：文件的修改包括：文件的修改：文件的修改包括：l插入一条记录；插入一条记录；l删除一条记录删除一条记录l更新一条记录。更新一条记录。中国科大数据结构12-7 事务文件有序的排序事务文件终端主文件新主文件批处理示意图批处理示意图中国科大数据结构12-8 中国科大数据结构12-9 12.2 顺序文件n连续文件连续文件：次序相继的两个物理记录在存储介质上的存储位置：次序相继的两个物理记录

2、在存储介质上的存储位置是相邻的顺序文件。是相邻的顺序文件。n串联文件串联文件：物理记录之间的次序由指针相链表示的顺序文件。：物理记录之间的次序由指针相链表示的顺序文件。p特点：顺序文件是根据记录的序号或记录的相对位置来进行存取的特点：顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：文件组织方式。它的特点是：n存取第存取第i个记录，必须先搜索在它之前的个记录，必须先搜索在它之前的i1个记录。个记录。n插入新的记录时只能加在文件的末尾。插入新的记录时只能加在文件的末尾。n若要更新文件中的某个记录，则必须将整个文件进行复制。若要更新文件中的某个记录，则必须将整个文件进行

3、复制。中国科大数据结构12-10 12.2 顺序文件中国科大数据结构12-11 12.2 顺序文件p批处理算法实现批处理算法实现批处理的示意算法如教材批处理的示意算法如教材p310的算法的算法12.1所示。算法中用到所示。算法中用到的各符号的含义说明如下：的各符号的含义说明如下：nF：主文件；：主文件；nG：事务文件；：事务文件；nH：新主文件。：新主文件。它们都按关键字递增排序。事务文件的每个记录中，增设一个它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：代码以示修改要求，其中：nI：表示插入；：表示插入；nD：表示删除；：表示删除；nU：表示更改。：表示更改。

4、中国科大数据结构12-12 12.2 顺序文件void MergeFile (FILE *f, FILE *g, FILE *h) /由按关键字递增有序的非空顺序文件由按关键字递增有序的非空顺序文件f和和g归并得到新文件归并得到新文件h， /三个文件均已打开，其中，三个文件均已打开，其中，f和和g为只读文件，文件中各附加为只读文件，文件中各附加 /一个最大关键字记录，且一个最大关键字记录，且g文件中对该记录的操作为插入。文件中对该记录的操作为插入。 / h为只写文件。为只写文件。 fread (*fr, sizeof(RcdType), 1, f); fread (*gr, sizeof(Rc

5、dType), 1, g); while (!feof (f) | | !feof (g) switch case fr.key gr.key: /插入插入,函数函数P把把gr加工为加工为h的结构的结构 fwrite (P(gr), sizeof(RcdType), 1, h); if (!feof (g) fread (*gr, sizeof(RcdType), 1, g); break; case gr.code = = U & fr.key = = gr.key: /更改更改”旧旧”主文件中记录主文件中记录 fwrite (Q(fr, gr), sizeof(RcdType),

6、1, h); /函数函数Q将将fr和和gr归并成一个归并成一个h结构的记录结构的记录 if (!feof (f) fread (*fr, sizeof(RcdType), 1, f); if (!feof (g) fread (*gr, sizeof(RcdType), 1, g); break; default ERROR(); /其他均为出错情况其他均为出错情况 / switch / while / MergeFile中国科大数据结构12-13 12.2 顺序文件p分析批处理算法的时间分析批处理算法的时间假设主文件包含假设主文件包含n个记录，事务文件包含个记录，事务文件包含m个记录。一般情

7、况下，事个记录。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为务文件较小，可以进行内部排序，则时间复杂度为O(m*logm)。内部归并。内部归并的时间复杂度为的时间复杂度为O(nm)，则总的内部处理时间为，则总的内部处理时间为O(m*logmn)。假设所有的输入假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为输出都是通过缓冲区进行的，并假设缓冲区大小为s（个记录），则整个批处理过程中读（个记录），则整个批处理过程中读/写外存的次数为写外存的次数为 ：2m/s + (m+n)/s ）中国科大数据结构12-14 12.3 索引文件中国科大数据结构12-15 12.3 索引文

8、件p例如，下图为两个索引表的例子。例如，下图为两个索引表的例子。逻辑记录号逻辑记录号存在标识存在标识物理记录号物理记录号01111720null3110关键字关键字ki物理记录号物理记录号1011190119117812311601251142物理地址物理地址职工号职工号姓名姓名性别性别工资工资1142125张三张三男男35001160123李四李四女女40001178119王五王五男男45001190101黄六黄六男男2800中国科大数据结构12-16 12.3 索引文件中国科大数据结构12-17 12.3 索引文件中国科大数据结构12-18 12.3 索引文件通常最高可有四级索引：通常最高

9、可有四级索引： 多级索引是静态索引，各级索引均为顺序表结构。其结构简单，但修改很多级索引是静态索引，各级索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较多时，应采用动态索引。如二叉排序树（或二叉平衡树）、多时，应采用动态索引。如二叉排序树（或二叉平衡树）、B-B-树以及键树。树以及键树。中国科大数据结构12-19 12.4 ISAM和VSAM文件12.4.1 ISAM文件文件pISAM文件定义：索引顺序存取方法文件定义：索引顺序存取方法ISAM(Indexed Seq

10、uential Access Method)是一种专为磁盘存取设计的文件组织方式。磁盘是一种专为磁盘存取设计的文件组织方式。磁盘是以盘组、柱面和磁道三级地址存取的设备，可对磁盘上的数据文是以盘组、柱面和磁道三级地址存取的设备，可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。件建立盘组、柱面和磁道三级索引。n磁道索引项：磁道索引项：l基本索引项：基本索引项：u关键字：表示该磁道中最末一个记录的关键字（在此为关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）。最大关键字）。u指针：指示该磁道中第一个记录的位置。指针：指示该磁道中第一个记录的位置。l溢出索引项：溢出索引项：u关键字：表示

11、该磁道溢出的记录的最大关键字。关键字：表示该磁道溢出的记录的最大关键字。u指针：指示在溢出区中的第一个记录。指针：指示在溢出区中的第一个记录。中国科大数据结构12-20 12.4 ISAM和VSAM文件n柱面索引项：柱面索引项：l关键字：表示该柱面中最末一个记录的关键字（最大关键关键字：表示该柱面中最末一个记录的关键字（最大关键字）。字）。l指针：指示该柱面上的磁道索引位置。指针：指示该柱面上的磁道索引位置。中国科大数据结构12-22 12.4 ISAM和VSAM文件中国科大数据结构12-23 12.4 ISAM和VSAM文件12.4.2 VSAM文件文件中国科大数据结构12-24 12.4

12、ISAM和VSAM文件中国科大数据结构12-25 12.4 ISAM和VSAM文件VSAM文件的结构示意图文件的结构示意图 控制区间控制区间控制区域控制区域索引集索引集顺序集顺序集数据集数据集B+树树中国科大数据结构12-26 12.4 ISAM和VSAM文件中国科大数据结构12-27 12.4 ISAM和VSAM文件pVASM文件的特点文件的特点n优点：动态地分配和释放存储空间，不需要对文件进行重组，优点：动态地分配和释放存储空间，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同

13、的。间与查找一个原有记录的时间是相同的。n缺点：占有较多的存储空间，一般只能保持约缺点：占有较多的存储空间，一般只能保持约75的存储空间的存储空间利用率。利用率。中国科大数据结构12-28 12.5 直接存取文件(散列文件)p定义：定义：直接存取文件直接存取文件指的是利用杂凑（指的是利用杂凑（Hash）法进行组织的文件。它类似）法进行组织的文件。它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数和处理冲突的方于哈希表，既根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称法将记录散列到存储设备上，故又称散列文件散列文件。与哈希表不同的是，对于。与哈希表不同

14、的是，对于文件来说，磁盘上的文件记录通常是成组存放的。文件来说，磁盘上的文件记录通常是成组存放的。p溢出处理：若干个记录组成一个存储单位，在散列文件中，这个存储单位溢出处理：若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做叫做桶桶（Bucket）。）。假若一个桶能存放假若一个桶能存放m个记录，这就是说，个记录，这就是说，m个同义词的记录可以存放个同义词的记录可以存放在同一地址的桶中，而当第在同一地址的桶中，而当第m1个同义词出现时才发生个同义词出现时才发生“溢出溢出”。对散列。对散列文件主要采用链地址法处理溢出。文件主要采用链地址法处理溢出。发生发生“溢出溢出”时，需要将第时，需要将

15、第m1个同义词存放到另一个桶中，称此个同义词存放到另一个桶中，称此桶为桶为“溢出桶溢出桶”；相对地，称前；相对地，称前m个同义词存放的桶为个同义词存放的桶为“基桶基桶”。溢出桶。溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待查记录时，和基桶大小相同，相互之间用指针相链接。当在基桶中没有待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。中国科大数据结构12-29 12.5 直接存取文件(

16、散列文件)p例如，某一文件有例如，某一文件有18个记录，其关键字分别为个记录，其关键字分别为278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量为。桶的容量为m3，桶数，桶数b7。用除留余数。用除留余数法作哈希函数法作哈希函数H(key)key MOD 7。由此得到的直接存取文件如下。由此得到的直接存取文件如下图所示。图所示。桶编号桶编号 基桶基桶 溢出桶溢出桶0 063 1841 589 505 008 33023 269 1644 109 6205 278 215 810 110 3556

17、930 083 384直接存取文件示例直接存取文件示例中国科大数据结构12-30 12.5 直接存取文件(散列文件)p查找操作查找操作查找过程查找过程：首先根据给定值求得哈希地址（即基桶号），将基桶的：首先根据给定值求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的记录，则记录读入内存进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，若基桶内没有填满记录或其指针域为空，则文件检索成功；否则，若基桶内没有填满记录或其指针域为空，则文件内不含有待查记录；否则根据指针域的值的指示将溢出桶的记录读内不含有待查记录；否则根据指针域的值的指示将溢出桶的记录读入

18、内存继续进行顺序查找，直至检索成功或不成功。因此，总的查入内存继续进行顺序查找，直至检索成功或不成功。因此，总的查找时间为：找时间为：T = a (te + ti)其中：其中：a为存取桶数的期望值（相当于哈希表中的平均查找长度），为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址处理溢出来说，对链地址处理溢出来说，a = 1 + /2；te为存取一个桶所需的时间；为存取一个桶所需的时间；ti为在内存中顺序查找一个记录所需的时间。为在内存中顺序查找一个记录所需的时间。为装载因子，在散列文件中：为装载因子，在散列文件中：= n/(bm)n为文件的记录数，为文件的记录数，b为桶数，为桶数，

19、m为桶的容量。为桶的容量。中国科大数据结构12-31 12.5 直接存取文件(散列文件)p删除操作删除操作在直接存取文件中删除记录时，仅需对被删记录作一标记即可。在直接存取文件中删除记录时，仅需对被删记录作一标记即可。p直接存取文件的特点直接存取文件的特点n优点：文件随机存放，记录不需进行排序；插入、删除方便，优点：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。存取速度快，不需要索引区，节省存储空间。n缺点：不能进行顺序存取，只能按关键字随机存取，且询问方缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的式限于简单询

20、问，并且在经过多次的 插入、删除之后，也可能插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。录。此时亦需重组文件。中国科大数据结构12-32 12.6 多关键字文件在对文件进行检索操作是，不仅对主关键字进行简单询问，还在对文件进行检索操作是，不仅对主关键字进行简单询问，还经常需要对关键字进行其他类型的询问检索。经常需要对关键字进行其他类型的询问检索。12.6.1 多重表文件多重表文件p特点：多重表文件（特点：多重表文件（Multilist File）的特点是：）的特点是：1.记录按主关键字的

21、顺序构成一个串联文件，并建立主关键字的记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（称为主索引）；索引（称为主索引）；2.对每一个次关键字项建立次关键字索引（称为次索引），所有对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记具有同一次关键字的记 录构成一个链表。录构成一个链表。主索引为非稠密索引，次索引为稠密索引。每个索引项包括次主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头指针和链表长度。关键字、头指针和链表长度。中国科大数据结构12-33 12.6 多关键字文件p例子：例子：中国科大数据结构12-34 12.6 多关键字文件12.6

22、.2 倒排文件倒排文件倒排文件和多重表文件的区别在于次关键字索引的结构不同。倒排文件和多重表文件的区别在于次关键字索引的结构不同。通常称倒排文件中的次关键字索引为倒排表，具有相同次关键字的通常称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这些记录的物理记录号。些记录的物理记录号。中国科大数据结构12-35 12.6 多关键字文件在倒排文件中可以较快地检索记录，特别是在检索多个次关键在倒排文件中可以较快地检索记录，特别是在检索多个次关键字的情况时。在处理各种次关键字的查询时，

23、只要在次关键字索引字的情况时。在处理各种次关键字的查询时，只要在次关键字索引中检索出有关的指针集合，再对这些指针集合进行交、并、差等逻中检索出有关的指针集合，再对这些指针集合进行交、并、差等逻辑运算，就可求出符合查询条件的记录指针，然后按指针到外存去辑运算，就可求出符合查询条件的记录指针，然后按指针到外存去存取记录。存取记录。在插入和删除记录时，倒排表也要进行相应修改；需要移动索在插入和删除记录时，倒排表也要进行相应修改；需要移动索引项中记录号以保持其有序排列。若数据文件是索引顺序文件（如引项中记录号以保持其有序排列。若数据文件是索引顺序文件（如ISAM文件），倒排表中应存放记录的主关键字而不是物理记录号。文件），倒排表中应存放记录的主关键字而不是物理记录号。倒排文件的缺点是维护困难。同一倒排表中各项长度不同，不倒排文件的缺点是维护困难。同一倒排表中各项长度不同，不同倒排表的长度也不同，这些都给倒排文件的维护带来一定的困难，同倒排表的长度也不同，这些都给倒排文件的维护带来一定的困难，而且倒排表需要额外存储空间。而且倒排表需要额外存储空间。中国科大数据结构12-36 习题