数据结构-第九章

《数据结构-第九章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、查找和排序是数据处理系统中最重要的两个操作；其次是插入、删除操作；1、几个概念文件——查找表，是由同一类型的数据元素(记录)构成的集合记录——构成文件的数据元素，是文件中可存取的数据的基本单位字段——数据项，数据的最小单位关键字——某个可以用来标识记录的数据项主关键字——某个可以用来唯一标识记录的数据项次关键字——可以用来识别若干记录的数据项第九章查找D01曲守宁数据库004S01王永燕数据结构003L01潘玉奇程序设计002S01周劲数据结构001………………………课程号课程名教师课程类别课程安排表文件记录数据项主关键字次关键字查找表上进行的基本操作（1）查询某个“特定

2、的”数据元素是否在查找表中；（2）检索某个“特定的”数据元素的各种属性；（3）在查找表中插入一个数据元素；（4）从查找表中删去某个数据元素。查找表的分类根据查找表上进行的基本操作，可将查找表分为两大类静态查找表只进行上述（1）（2）两种类型的操作；动态查找表能够进行上述四种类型的操作的查找表。第九章查找查找也叫检索，是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。若表中存在这样一个数据元素，则称查找是成功的。若表中不存在关键字等于给定值的数据元素，则称查找不成功。5、查找方法评价平均查找长度ASL(AverageSearchLength)查找的主要

3、操作是关键字的比较。所以，通常也把查找过程中对关键字需要执行的平均比较次数（即平均查找长度）作为衡量一个查找算法效率优劣的标准。9.1静态查找表顺序表的查找以顺序表或线性链表表示静态查找表。本节主要讨论在顺序表中实现的顺序查找。查找过程：从表的一端开始逐个进行数据元素（记录）的关键字和给定值的比较。顺序表的查找i例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1算法中监视哨的作用是为了在循环中省去判

4、定，防止下标越界的条件，从而节省比较的时间。顺序查找算法描述Typedefstruct{intkey;floatinfo;}JD;}intseqsrch(JDr[],intn,intk){inti=n;r[0].key=k;while(r[i].key!=k)i--;return(i);}性能分析：设Pi为查找表中第i个记录的概率(取Pi=1/n)；Ci为找到第i个记录所需的查找次数。则nASL=PiCi=nP1+(n-1)P2+...+2Pn-1+Pni=1=[n+(n-1)+...+2+1]*1/n=(n+1)/2若查找成功与不成功的概率相同，即Pi=1/2n，AS

5、L=nP1+(n-1)P2+...+2Pn-1+Pn+(n+1)/2=(n+1)*3/43顺序查找方法的ASL顺序查找的特点算法简单，但查找效率低。Ci为找到表