数据结构-C语言描述(第三版)第12章文件和外排序.ppt

12.2.3 C语言文件 1. C语言文件概述 C语言将文件称为流(stream)。术语“流”一词指字节序列的源和目标。C语言没有其他高级语言所提供的格式记录文件。如何按记录(相当于结构)形式进行输入/输出是程序员的责任。 2. 标准设备的输入/输出 C语言将键盘和显示器作为标准设备文件处理。键盘的标准设备文件指针是stdin，显示器是stdout和stderr。标准设备文件stdin和stdout可以由操作系统的换向功能换向到其他设备输入/输出，而stderr作为出错信息的输出流不能换向。标准设备文件由系统管理，不需要用户进行打开和关闭操作。 使用标准设备文件可以进行字符串的输入和输出，还可以进行格式化输入和输出。 3. 数据文件的输入/输出 与标准设备文件不同，数据文件必须遵循“打开—读写—关闭”的操作过程。在数据文件的输入/输出中，系统提供字符、字符串输入/输出和格式化输入/输出函数，以及数据块和整数(字)输入/输出函数。在使用这些函数时，都要求包含头文件stdio.h。 程序12－1是C语言格式化读写的例子。它从键盘读入10个整数，存入磁盘数据文件test.dat中，然后再从该磁盘文件中读出，在显示器上显示这10个整数。 【程序12－1】 C文件读写。 #include stdio.h #include stdlib.h void main( ) { int i, k; FILE *f; printf(Create a file.\n); if (f=fopen(C:\\test.dat, wb+)) for ( i=0; i10; i++){ scanf(%d, k); fprintf(f, %d , k); } fclose(f); printf(\nDisplay the file just created.\n); if (f=fopen(C:\\test.dat, rb+) ) for ( i=0; i10; i++){ fscanf(f, %d, k); printf(%d , k); } printf(\n\n); fclose(f); } 12.3 文件的索引结构 12.3.1 静态索引结构 在12.2.2节中，我们介绍了索引文件结构。这是一种静态的索引结构。由于索引表总是有序的，因此每当数据文件更新时，通常需要移动索引表中各索引项的位置，这是一项负担很重的处理。当数据文件很大时，索引表本身也很大，在内存中放不下，可以建立多级索引：2级索引，3级索引，……。这种多级索引形成一种静态的m叉有哪些信誉好的足球投注网站树结构。所谓静态m叉有哪些信誉好的足球投注网站树，是指树的叉数m是固定不变的。同样，静态的多叉树索引结构也不利于记录的频繁插入和删除。 图12－6 ISAM文件结构示意图 12.3.2 动态索引结构 前面我们已经讨论了B－树，认为B－树可用于组织磁盘文件，适合外有哪些信誉好的足球投注网站。但实际上几乎从来没有实现过。最普遍实现的是B－树的一个变体，称为B+树。B+树用于建立多级索引。图12－7是B+树的示意图。 图12－7 B+树索引的文件结构示意图 B+树与B－树的最显著的区别是B+树只在叶结点中存储记录。非叶结点存储索引项。每个索引项为：(关键字值，指向子树的指针)。叶结点存储实际记录。叶结点中可能存储多于或少于m个记录，只是简单地要求叶结点的磁盘块存储足够的记录，以保持该块至少半满。B+树的叶结点组成数据文件。 一棵m阶B+树或者是空树，或者是满足下列特性的树： (1) 每个非叶结点最多有m个孩子； (2) 除根结点以外的非叶结点至少有(m/2(个孩子； (3) 有n个孩子的非叶结点必须有n个关键字值； (4) 根结点至少有两个孩子； (5) 所有叶结点均在同一层上。 因此，每个B+树结点的结构如下： n，(P0, K0)，(P1，K1)，...，(Pn－1，Kn－1) 其中，Pi是指向子树的指针，Ki是子树Pi上的最大关键字值，0≤i＜n＜m，Ki＜Ki+1, 0≤i＜n。 B+树的有哪些信誉好的足球投注网站、插入和删除操作的算法基本上与普通B－树的相应操作一致。 在B+树上插入一个记录首先有哪些信誉好的足球投注网站应当包含该记录的叶结点。如果该叶结点未满，则直接将该记录插入后操作结束。如果叶结点已满，则叶结点应进