查找数据结构.pptxVIP

查找梁音地球信息科学与技术系地球物理与空间信息学院

查找基本概念静态查找表顺序表的查找有序表的查找动态查找表二叉排序数平衡二叉数（AVL数）

查找的基本概念查找是针对查找表这种数据类型进行的操作；查找表：是由同一类型的数据元素(或记录)构成的集合；该集合中的元素的关系完全松散；查找表是一种非常灵活的数据结构。

查找的基本概念对查找表经常进行的操作有：(1)查询某个特定的数据元素是否在查找表中；(2)检索某个特定的数据元素的各种属性。这两种操作统称为“查找”的操作，若只对查找表进行查找的操作，则此类查找表称为静态查找表(StaticSearchTable)。

查找的基本概念对查找表经常进行的操作有：(3)在查找表中插入一个数据元素；(4)在查找表中删去某个数据元素。若对查找表不仅作查找操作，同时还向查找表中插入或者删除数据元素。则此类查找表称为动态查找表(DynamicSearchTable)。

查找的基本概念在日常生活中，我们几乎每天都需要进行“查找”；查阅某人的电话号码；查阅图书馆的资料；在字典中查找某个词的读音和含义。查找：在一个含有众多的数据元素的查找表中找出某个特定数据元素。

查找的基本概念特定的数据元素是与关键字相联系的；关键字：是数据元素(或记录)中某个数据项的值；用它可以标识一条记录；若关键字与记录是一一对应的，该关键字为主关键字；若该关键字可以同时标识若干条记录，则该关键字为次关键字。

查找的基本概念学号姓名高数英语数据结构总分063051陈平987080248063052张红768090246063054陆华858585255063057陈平667075211

查找的基本概念对于上述查找表而言，学号、姓名、甚至各科的成绩都可以作为关键字；但是，显然学号是主关键字；姓名应该是次关键字，因为可能出现同名同姓的记录；各科的成绩应该也是次关键字，而且相同成绩的记录应该来说比同姓名更多。

查找的基本概念所以查找的实质：根据给定的某个值，在查找表中确定一个或若干个其关键字等于该给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功；否则，查找不成功。

静态查找表该表只是查找某一条记录是否存在；或者是查找某一条特定记录中的其他属性；定义一条记录：typedefstruct{KeyTypeKey;//关键字……//其他属性或数据域}ElemType

静态查找表用前面的记录的结构体来定义一个静态的顺序查找表：typedefstruct{ElemType*record;//记录存储空间基址intlength;//查找表的长度}SSTable注意：表中的数据元素的顺序是任意的。

静态查找表这种顺序静态查找表的查找与一个线性表的查找毫无差别；只是线性表中的数据元素可能过于简单；而查找表中的每一个数据元素都是一条记录；记录本身在C语言中就是一个结构体的实例化。

静态查找表intSearchSTable(SSTableST,KeyTypeKey){//查找一个顺序表，并返回查找到的记录在表中的位置for(i=0;iST.length;i++)if(ST.elem[i].Key==Key)returni;}//endofSearchSTable

静态查找表时间复杂度分析：查找的基本操作是：将记录的关键字与给定的值进行比较；所以，这里的时间复杂度用“其关键字和给定值进行过比较的记录个数的平均值”来衡量。平均查找长度(AverageSearchLength)

静态查找表顺序表查找成功时的平均查找长度：假设每个记录的查找概率时相等的；

静态查找表但是，在实际的过程中，每个记录被访问到的概率是不一样的；可以在每个记录中加入频度域；在每次查找结束之后，按照记录的访问频度将记录排序，将经常访问的记录放在表的最前面，以加快查找的速度；但是，排序实际上也是要消耗时间的。

静态查找表上述的分析是在查找成功的情况下进行的；实际过程中，查找成功与查找不成功都是存在的；查找不成功时，记录的关键字和给定值必定要进行n次比较。

静态查找表假设查找成功和查找不成功的概率都是1/2，则：当n值很大的时候，查找不成功的概率应该会非常的小，相应的平均查找长度可按上式类推。

静态查找表不管在什么情况下，顺序表的查找的时间复杂度都是O(n)；该算法的优点：简单、适应面广；该算法的缺点：当n很大时，查找效率很低。

静态查找表有序表的查找：这里的有序是指按记录的关键字有序排列；所以在有序表表示的静态查找表中，所有的记录都是按关键字有序排列的；折半查找。

静态查找表折半查找：逐步缩小待查记录所在的范围；直到找到该记录；或者找不到该记录为止。缩小范围得以