《数据结构-C语言-第九章查找课件》由会员分享，可在线阅读，更多相关《数据结构-C语言-第九章查找课件（68页珍藏版）》请在金锄头文库上搜索。
1、第九章第九章 查找查找4 学时学时数据数据结构构教学目标教学目标l熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法；l熟练掌握二叉排序树的构造和查找算法及其性能分析方法；l掌握二叉排序树的插入算法，了解二叉排序树的删除算法；l熟练掌握哈希函数（除留余数法）的构造l熟练掌握哈希函数解决冲突的方法及其特点数据数据结构构查找查找的的基本概念基本概念l 查找表（查找表（Search Table）：）：由同一类型的数据元素（或记由同一类型的数据元素（或记录）构成的集合，是一种以集合为逻辑结构、以查找为核录）构成的集合，是一种以集合为逻辑结构、以查找为核心运算的数据结构。心运算的数据结构。l
2、静态查找表：静态查找表：只对查找表进行只对查找表进行查询查询某个特定的数据元素或某个特定的数据元素或某个特定数据元素的各种属性的操作。某个特定数据元素的各种属性的操作。如：查询成绩表中如：查询成绩表中是否有某学生或该学生某门课程的成绩。是否有某学生或该学生某门课程的成绩。l 动态查找表：动态查找表：对查找表进行对查找表进行插入或删除插入或删除某个数据元素的操某个数据元素的操作。作。如：插入某个学生某门课程的成绩。如：插入某个学生某门课程的成绩。数据数据结构构查找查找的的基本概念基本概念l关键字：关键字：是数据元素中某个数据项的值，它可以标识一个是数据元素中某个数据项的值，它可以标识一个数据元素
3、数据元素l主关键字：主关键字：可以唯一标识一个记录的关键字可以唯一标识一个记录的关键字l次关键字：次关键字：可以标识若干个记录的关键字可以标识若干个记录的关键字l 查找查找(Search)：也称检索，是根据给定的某个值，在查找也称检索，是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。表中确定一个关键字等于给定值的记录或数据元素。u查找成功：查找成功：即找到满足条件的数据对象，这时作为结果即找到满足条件的数据对象，这时作为结果可报告该对象在结构中的位置可报告该对象在结构中的位置,还可给出该对象中的具还可给出该对象中的具体信息。体信息。u查找不成功：查找不成功：或搜索失败。
4、作为结果应报告一些信息或搜索失败。作为结果应报告一些信息,如失败标志、位置等。如失败标志、位置等。数据数据结构构查找查找的的基本概念基本概念l衡量查找算法的标准：衡量查找算法的标准：u平均查找长度平均查找长度ASL(Average Search Length)：为确定记录在为确定记录在表中的位置，需和给定值进行比较的关键字个数的期望值表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。称为查找算法在查找成功时的平均查找长度。ln：记录的个数记录的个数lpi：查找第查找第i个记录的概率个记录的概率(通常认为通常认为pi=1/n)lci：找到第找到第i个记录所
5、需的比较次数个记录所需的比较次数u算法所需要的存储量和算法的复杂性等算法所需要的存储量和算法的复杂性等数据结构静态查找表静态查找表(基于线性表的查找基于线性表的查找)第一节第一节数据数据结构构l查找方式：查找方式：从表的第一个元素开始，从表的第一个元素开始，将给定的值与表中逐将给定的值与表中逐个元素的关键字进行比较，个元素的关键字进行比较，直到两者符合，查到所要找的直到两者符合，查到所要找的元素为止。否则就是表中没有要找的元素，检索不成功。元素为止。否则就是表中没有要找的元素，检索不成功。l适用范围：适用范围：顺序表或线性链表表示的静态查找表，表内元顺序表或线性链表表示的静态查找表，表内元素之
6、间无序。素之间无序。l顺序表的表示顺序表的表示 typedef struct ElemType *elem;/表基址表基址 int length;/表长表长 SSTable;l顺序查找实现顺序查找实现 int LocateELem(SqList L,ElemType e)for(i=0;i0;-i)或或 for(i=1;i=n;i+)return i;i例例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找找64 64监视哨监视哨 iiii比较次数比较次数=5 比较次数：比较次数：查找第查找第n个元素：个元素：1查找第查找第
7、n-1个元素：个元素：2.查找第查找第1个元素：个元素：n查找第查找第i个元素：个元素：n+1-i查找失败查找失败：n+1数据数据结构构9.1.1 顺序查找顺序查找l顺序查找方法的特点顺序查找方法的特点u 表结构为表结构为有序表、无序表有序表、无序表均可适用；均可适用；u 存储结构为存储结构为顺序存储和链式存储顺序存储和链式存储的表均适用；的表均适用；u 适合于适合于短表短表，方法简单；，方法简单；u 时间复杂度为时间复杂度为O(n)；u 平均查找长度比其他方法大平均查找长度比其他方法大，查找成功时：，查找成功时：数据数据结构构9.1.2 折半查找折半查找l查找方法：查找方法：首先首先选择表中
8、间的一个记录选择表中间的一个记录，比较其关键字与，比较其关键字与要查找关键字的值；若要找的记录的关键字值大，则再取要查找关键字的值；若要找的记录的关键字值大，则再取表的表的后半部的中间记录后半部的中间记录进行比较；否则取进行比较；否则取前半部的中间记前半部的中间记录录进行比较，如此反复，直到找到为止。进行比较，如此反复，直到找到为止。l适用范围：适用范围：采用采用顺序存储顺序存储结构的结构的有序有序表表 数据数据结构构9.1.2 折半查找折半查找l折半查找的实现折半查找的实现l令令low=1,high=n,mid=(low+high)/2 l若若kelemmid.key，则，则low=mid+
9、1lowhighmid例例1 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找21 当当k=elemmid.key,查找成功！查找成功！数据数据结构构9.1.2 折半查找折半查找lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 8
10、0 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighlowhigh 不成功！不成功！数据数据结构构9.1.2 折半查找折半查找l算法描述算法描述u设表长为设表长为n，low、high和和mid分别指向待查元素所在区间的分别指向待查元素所在区间的上界、下界和中点，上界、下界和中点，k为给定值。为给定值。u初始时，令初始时，令low=1,high=n,mid=(low+high)/2 u让让k与与mid指向的记录比较指向的记录比较u若若k=elemmid.key，查找成功，查找成功u若若kel
11、emmid.key，则，则low=mid+1u重复上述操作，直至重复上述操作，直至lowhigh时，查找失败时，查找失败数据数据结构构9.1.2 折半查找折半查找int Search.Bin(SSTable ST,KeyType key)/在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。若找到，的数据元素。若找到，则函数值为则函数值为 该元素在表中的位置，否则为该元素在表中的位置，否则为0。low=1;high=ST.length;/置区间初值置区间初值 while(low50)u时间复杂度时间复杂度 O(log2n)数据数据结构构9.1.3 索引顺序查找（分
12、块查找索引顺序查找（分块查找）l查找方法：查找方法：将将n个元素均匀地分成块，每块有个元素均匀地分成块，每块有s个记录，个记录，块间块间按大小排序，块内元素不排序按大小排序，块内元素不排序。要建立一个块的最大（或最。要建立一个块的最大（或最小）关键字表。查找时，先用小）关键字表。查找时，先用顺序查找或折半查找法顺序查找或折半查找法由最大由最大关键字查出所在的块，再用关键字查出所在的块，再用顺序查找法顺序查找法在块中查找。在块中查找。l适用条件：适用条件：分块有序表分块有序表数据数据结构构9.1.3 索引顺序查找（分块查找索引顺序查找（分块查找）1 2 3 4 5 6 7 8 9 10 11 1
13、2 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表索引表查查38成功成功l算法实现：算法实现：u 用数组存放待查记录，每个数据元素至少含有关键字域用数组存放待查记录，每个数据元素至少含有关键字域u 建立索引表，每个索引表结点含有最大关键字域和指向建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。本块第一个结点的指针。数据数据结构构9.1.3 索引顺序查找（分块查找索引顺序查找（分块查找）l分块查找方法特点：分块查找方法特点：l对存储结构为对存储结构为顺
14、序和线性链表顺序和线性链表的均适用；的均适用；l平均查找长度比顺序查找小；平均查找长度比顺序查找小；l用折半查找确定所在块时：用折半查找确定所在块时：l若用顺序查找确定所在块时：若用顺序查找确定所在块时：数据数据结构构9.1.4 基于线性表的查找方法比较基于线性表的查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找ASL最大最大(N+1)/2最小最小ASL=log2(n+1)-1两者之间两者之间表结构表结构有序表有序表无序表无序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储顺序存储线性链表线性链表顺序存储顺序存储顺序存储顺序存储线性链表线性链表数据数据结构构数据结构动态查
15、找表动态查找表(基于树的查找基于树的查找)第二节第二节数据数据结构构l动态查找表的特点动态查找表的特点u 表结构在表结构在查找过程中动态生成查找过程中动态生成u 对于给定值对于给定值key，若表中存在，若表中存在，则成功返回；则成功返回；否则插入关键字否则插入关键字等于等于key 的记录的记录二叉排序树二叉排序树平衡二叉树平衡二叉树B-B-树树B B+树树键树键树数据数据结构构9.2.1 二叉排序树二叉排序树l二叉排序树的定义：二叉排序树的定义：二叉排序树或是空树，或是满足如下性质的二叉树：二叉排序树或是空树，或是满足如下性质的二叉树：u 若其左子树非空，则若其左子树非空，则左子树左子树上所有
16、结点的值均上所有结点的值均小于小于根结根结点的值；点的值；u 若其右子树非空，则若其右子树非空，则右子树右子树上所有结点的值均上所有结点的值均大于大于等于等于根结点的值；根结点的值；u 其左右子树本身又各是一棵二叉排序树其左右子树本身又各是一棵二叉排序树数据数据结构构9.2.1 二叉排序树二叉排序树下列图形中，哪个不是二叉排序树下列图形中，哪个不是二叉排序树？1624510379831921074658数据数据结构构l中序遍历二叉排序树后的结果有什么规律？中序遍历二叉排序树后的结果有什么规律？9.2.1 二叉排序树二叉排序树353123745100246190783，12，24，37，45，53，61，78，90，100递增递增得到一个关键字的递增有序序列得到一个关键字的递增有序序列数据数据结构构9.2.1 二叉排序树二叉排序树l二叉排序树的操作二叉排序树的操作查找查找u若查找的关键字若查找的关键字等于根结点等于根结点，成功，成功u否则否则若若小于根结点小于根结点，查其左子树，查其左子树若若大于根结点大于根结点，查其右子树，查其右子树u在左右子树上的操作类似在左右子树上的操作类似721
