数据结构chapter 8 查找

《数据结构chapter 8 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九章查找所谓的查找就是从众多数据元素中找出一个“特定”的元素。查找通常是在查找表中进行的，查找表是我们这本书中的另一种数据结构，数据元素之间存在最简单的集合关系20-Jul-212查找表：由同一类型的数据元素（或记录）构成的集合。数据元素之间的关系:属于同一个集合，关系非常松散。查找表的主要操作：1)查询某个特定的元素是否在查找表中2）检索表中某个特定元素的各种属性；3）在查找表中插入一个数据元素4）从查找表中删除某个数据元素。静态查找与动态查找如果一个查找表只允许1）2）操作（常称为查找操作），则称为静态查找表；如果在查找过程中还需要插入表中不存在的元素或者删除表中

2、已经存在的某个元素，则称为动态查找表。查找表20-Jul-213查找：也叫检索，根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素的过程关键字:关键字是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个元素或记录。如果一个关键字可以唯一标识一个记录，那么这个关键字称为主关键字，反之用于识别若干记录的关键字成为次关键字。查找成功与不成功：如果表中存在这样的记录，则称查找是成功的，否则查找是不成功的。基本概念20-Jul-214查找方法评价方法查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定

3、记录在表中的位置，需和给定值进行比较的关键字的个数的期望值.20-Jul-215如何进行查找？查找过程依赖于数据元素在查找表中的位置。具体采用什么样的查找方法完全取决于查找表中数据元素是根据何种关系来组织的。20-Jul-216第一节静态查找表静态查找表只能进行查找操作，不能进行插入和删除操作静态查找表的抽象数据类型ADTStaticSearchTable{数据元素：具有相同特性的数据元素的集合。各个数据元素均含有类型相同、可以唯一标识数据元素的关键字。数据关系：数据元素属于同一个集合。主要的操作：Create(&ST,n);//创建静态表Destroy(&ST);//

4、销毁静态表Search(ST,key);//查找关键字为key的元素Tranverse(ST,visit());//遍历静态表}ADTStaticSearchTable静态查找表有两种不同的表示方法：顺序表或线性链表表示。不同的表示方法，其查找操作的实现方法也不同。20-Jul-2171顺序表的查找顺序查找的查找过程从表的最后一个记录开始，逐个比较记录关键字与给定值，如果某个记录的关键字和给定的值相等，则查找成功；如果直到第一个记录其关键字和给定值均不相等，则表明表中没有所查记录，查找不成功。静态表的顺序存储结构表示为：typedefstruct{ElemType*el

5、em;intlength;}SSTable;20-Jul-218i找64监视哨iiii比较次数=5顺序查找示例20-Jul-219顺序查找算法的C语言描述intSearch_Seq(SStableST,KeyTypekey){ST.elem[0]=key;//设置监视哨for(i=ST.length;!EQ(ST.elem[i],key);i--)returni;}intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0]=key;for(i=ST.length;i>0;i--)if(EQ(ST.elem[i],key))break;r

6、eturni;}设置监视哨的目的：查找算法总能找到一个位置上的关键字与给定的值相同。返回值为0表示不成功，否则为成功。20-Jul-2110平均查找长度ASL在查找过程中最重要的操作是比较关键字和给定的值，因此查找算法的时间复杂度常用一个算法的平均比较次数来衡量.平均查找长度：为确定记录在查找表中的位置，需要和给定的值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度ASL(averagesearchlength)对于一个含有n个记录的表，查找成功时的平均查找长度为Pi是查找表中第i个元素的概率，∑pi=1Ci是查找表中第i个记录所需要比较的次数。显然

7、与查找的方法密切相关20-Jul-2111顺序查找过程的平均查找长度顺序查找的比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1因此平均的查找长度为：在顺序查找过程中，如果每个元素查找的概率相同，那么pi=1/n，此时的平均查找长度为：每次查找平均的比较次数为表长度的一半。也就是平均需要比较一半的记录。20-Jul-2112查找概率对平均查找长度的影响在计算ASL时，假定各个元素的查找概率是相同的，而实际上很可能各个元素的查找概率很可能不同例1：同学到校医院去看病，挂号时