数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第9章_检索
163页1、数据结构,李云清 杨庆红 揭安全,高等学校精品课程,人民邮电出版社,(第2版),数据结构,揭安全,江西省高等学校精品课程,E_mail: ,江西师范大学计算机信息工程学院,第9章 检索,检索的基本概念,线性表的检索,最佳二叉排序树,散列表检索,二叉排序树,B-树,丰满树和平衡树,Huffman树,9.1 检索的基本概念,检索是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。,要进行检索,必须知道待检索对象的特征,也就是要知道待检索数据元素的关键字。,我们将能唯一标识一个数据元素的关键字称为主关键字,而其它关键字称为辅助关键字或从关键字。,静态检索表:检索的前后不会改变查找表的内容。,动态检索表:检索过程中可能会改变数据元素的存储位置。,检索算法的评价标准:平均查找长度ASL(Average Search Length),也就是为确定某一结点在数据集合中的位置,给定值与集合中的结点关键字所需进行的比较次数。,对于具有n个数据元素的集合,查找某元素成功的平均查找长度为:,ASL,9.2 线性表的检索,线性结构是数据元素间最常见的数据结构,基于线性表的检索
2、运算在各类程序中应用非常广泛,本节介绍三种在线性表上进行检索的方法,它们分别是顺序检索、二分法检索与分块检索。为简化问题,本节所介绍的检索方法均视为是基于静态查找表上的操作。,9.2.1顺序检索,从表的一端开始,顺序(逐个)扫描线性表,依次将扫描到的结点关键字和给定值Key相比较,若当前扫描到的结点关键字与Key相等,则检索成功;若扫描结束后,仍未找到关键字等于Key的结点,则检索失败。,存储结构:顺序存储或链式存储,本节介绍基于顺序表的顺序检索算法。,/*/ /* 线性表检索用的头文件 文件名:seqlist.h */ /*/ #include #define maxsize 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct datatype datamaxsize; /*此处假设数据元素只包含一个整型的关键字域*/ int len; /*线性表长度*/ seqlist; /*预定义的顺序表类型*/,算法9.1给出了基于顺序查找表的顺序检索方法。 /* 顺序检索算法 文件名:s_search.
3、c */ /* 函数名: seqsearch1()、seqsearch2() */ #include “seqlist.h“ /*-顺序查找的非递归实现-*/ int seqsearch1(seqlist l,datatype key) int k=l.len-1; while (k=0 ,/*-顺序查找的递归实现-*/ int seqsearch2(seqlist l,int n,datatype key) int k=0; if (n=-1) k=-1; else if (l.datan=key) k=n; else k=seqsearch2(l,n-1,key); return(k); 算法9.1 线性表的顺序检索(顺序存储),顺序检索的缺点是查找时间长。假设顺序表中每个记录的查找概率相同,即Pi=1/n(i=0,1,n-1),查找表中第i个记录所需的进行的比较次数Ci=n-i。因此,顺序查找算法查找成功时的平均查找长度为:,算法分析:,ASLseq=,查找失败时,算法的平均查找长度为:,ASLseq=,9.2.2二分法检索,二分法检索又称为折半查找,采用二分法检索可以大大提高查
4、找效率,它要求线性表结点按其关键字从小到大(或从大到小)按序排列并采用顺序存储结构。,采用二分搜索时,先求位于搜索区间正中的对象的下标mid,用其关键码与给定值x比较: lmid. Key = x,搜索成功; lmid. Key x,把搜索区间缩小到表的前半部分,再继续进行对分搜索; lmid. Key x,把搜索区间缩小到表的后半部分,再继续进行对分搜索。,每比较一次,搜索区间缩小一半。如果搜索区间已缩小到一个对象,仍未找到想要搜索的对象,则搜索失败。,有一组有序的线性表如下: (10,14,20,32,45,50,68,90,100,120),例,下面分析在其中二分检索关键字20的过程。,下面分析二分检索关键字95的过程:,下面给出二分检索法的非递归与递归实现算法,算法中使用seqlist.h中定义的顺序查找表。,/*/ /* 二分查找算法 文件名:b_search.c */ /* 函数名:binsearch1()、binsearch2() */ /*/ /*-二分查找的非递归实现-*/ int binsearch1(seqlist l,datatype key) int low=
《数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第9章_检索》由会员E****分享,可在线阅读,更多相关《数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第9章_检索》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页