资源描述：
《北航数据结构课件 (9)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九第九章章文件及查找文件及查找本章内容本章内容99..11文件的基文件的基本本概念概念99..22顺序文件顺序文件查查99..33索引文件索引文件找找99..44B-B-树和树和B+B+树树99..55散列散列(H(Haassh)h)文件文件重点99.1.1文件文件的的基基本本概念概念例例11花名册学号姓名性别年龄其他99001张三女20¼¼99002李四男18¼¼99003王五男17¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼99030刘末女19¼¼例例22商品清单编号名称库存数量入库时间其他010020电视机3002005.7¼010021洗衣机1002006.1¼010023空调机50
2、2006.5¼010025电冰箱302006.9¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼¼一一..名名词术语词术语学号姓名性别年龄其他99001张三女20……99002李四男17……99003王五男18…………………………99030刘末女19……字段、数据项属性：描述一个客体某一方面特征的数据信息。记录：反映一个客体数据信息的集合。属性的集合文件：具有相同属性定义的记录的集合。关键字：区分不同记录的属性或属性组。（主关键字、次关键字）二.文件的逻辑结构记录呈现在用户眼前的排列的先后次序关系。(线性结构)三.文件的物理结构文件在存储介质上的组织方式。1.连续组织方式(顺序组织方式)2.链接组织方式3.
3、索引组织方式4.随机组织方式(散列组织方式)文件索引文文件件文文件件顺顺序序文件索引散散列列四.文件的基本操作查找在文件中确定某个特定记录存在与否的过程。结论:查找成功,给出被查到记录的位置；查找失败,给出相应的信息。(1)查找文件的第i个记录；(2)查找当前位置的下一个记录；(3)按关键字值查找记录。插入删除以查找操作为基础修改排序使记录按关键字值有序排列的过程。99.2.2顺序顺序文件文件一.顺序文件的基本概念在物理结构中记录排列的先后次序与在逻辑结构中记录排列的先后次序一致的文件称为顺序文件。记录的排列按关键字值有序的顺序文件称为排序顺序文件，否则，称为一般顺序文件。逻辑上划分在存储
4、介质上采用连续组织方式的顺序文件称为连续顺序文件；采用链接组织方式的顺序文件称为链接顺序文件。物理上划分若排序顺序文件在存储介质上采用连续组织方式，称之为排序连续顺序文件。关键字排序顺排序顺序文件序文件排排学号姓名性别年龄其他序序06001张三女20…连连06002李四男17…续续06003王五男19…顺顺……………序序……………文文……………件件06050刘末女16…一般顺一般顺序文件序文件关键字二.连续顺序文件的查找1.顺序查找法查找思想：从文件的第一个记录开始,将用户给出的关键字值与当前被查找记录的关键字值进行比较，若匹配，则查找成功，给出被查到的记录在文件中的位置，查找结束。若所有
5、n个记录的关键字值都已比较，不存在与用户要查的关键字值匹配的记录，则查找失败，给出信息0。(key,key,key,…,key)123nk关键字集合被查找记录的关键字值算算法法intSEQSEARCH1(keytypekey[],intn,keytypek){inti;for(i=1;i<=n;i++)if(key[i]==k)returni;return0;}例例key[1..10]38751957100485076211若查找k=48经过6次比较,查找成功,返回i=6若查找k=35查找失败,返回信息0算算法法递递归归intSEQSEARCH2(keytypekey[],intn,key
6、typek,inti){每一个回合的查询每一个回合的查询从第if(i>ni)个位置执行：return0;若不存在(即i>n)，则返回信息0；if(key[i]==k)若存retur在ni;(即key[i]=k)，则返回位置i;retu否rn则，从第SEQSEARCi+1个H2位(k置ey,开始执行上n,k,i+1);述过程。}调用方式ppooss==SSEEQQSSEEAARCRCHH22((kkeeyy,,nn,,k,k,11););返回位置查找效率如何平均查找长度ASL(AverageSearchLength)确定一个记录在文件中的位置所需要进行的关键字值的比较次数的期望值(平均值)。
7、对于具有n个记录的文件，有nASL=åpciii=1其中，pi为查找第i个记录的概率，ci为查找第i个记录所进行过的关键字的比较次数。结论对于具有n个记录的顺序文件，若查找概率相等，则有nn1n+1ASL=åpc=åi=iin2i=1i=1算法的时间复杂度为O(n)优优点：点：查找原理和过程简单，易于理解。对于被查找对象的排列次序没有限制。缺缺点：点：查找的时间效率低。2.排序连续顺序文件的折半查找法(二分查找法、对半查
