内蒙古大学《算法与数据结构》课件第5章集合与查找
142页1、1第第5章章 集合与查找集合与查找5.1 基本概念基本概念5.2 具有具有Merge、Find的的ADT集合集合5.3 静态查找表静态查找表5.4 Hash表表5.5 二叉查找树二叉查找树(动态查找表动态查找表)5.6 平衡二叉查找树(平衡二叉查找树(AVL树)树)5.7 B-树树2若表中存在特定元素,称查找成功,应输出该元素。若表中存在特定元素,称查找成功,应输出该元素。否则,称查找不成功(也应输出失败标志或失败位置)否则,称查找不成功(也应输出失败标志或失败位置)查找表查找表查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素所构成的集合。由同一类型的数据元素所构成的集合。查询查询(Searching)特定数据元素特定数据元素是否在表中。是否在表中。只查找,不改变查找表中的数据元素。只查找,不改变查找表中的数据元素。既查找,又改变(增减)查找表中的数据元素。既查找,又改变(增减)查找表中的数据元素。元素中某个数据项的值,可用来识别一个元素。元素中某个数据项的值,可用来识别一个元素。 可以可以唯
2、一唯一标识一个元素的关键字。标识一个元素的关键字。 例如例如“学号学号”例如例如“性别性别”识别若干元素的关键字。识别若干元素的关键字。5.1 基本概念基本概念3v 对查找表常用的操作有对查找表常用的操作有哪些?哪些? v查询查询某个某个“特定的特定的”数据元素是否在表中;数据元素是否在表中;v在查找表中在查找表中插入插入一元素;一元素;v从查找表中从查找表中删除删除一元素。一元素。 v查找的过程是怎样的?查找的过程是怎样的? 5.1 5.1 基本概念基本概念4v如何评估查找算法的优劣?如何评估查找算法的优劣? 查找的过程就是将给定的查找的过程就是将给定的K值与值与查找表查找表中各元素的中各元素的关键字进行比较的过程。所以用比较次数的平均值来关键字进行比较的过程。所以用比较次数的平均值来评估算法的优劣,称为评估算法的优劣,称为平均查找长度平均查找长度(ASL:average search length)。)。显然,显然,ASL值越小,时间效率越高。值越小,时间效率越高。 5.1 基本概念基本概念 niiniiisuccpcpASL11) 1 ( .5一、顺序查找(线性查找)一、顺序查找
3、(线性查找)二、折半查找(二分或对分查找)二、折半查找(二分或对分查找)三、分块查找(索引顺序查找)三、分块查找(索引顺序查找)5.3 静态查找表静态查找表6所谓顺序查找,又称线性查找,主要用于在所谓顺序查找,又称线性查找,主要用于在线性结构线性结构中中进行查找。进行查找。设若表中有设若表中有 n 个元素,则顺序查找从表的前端开始,顺个元素,则顺序查找从表的前端开始,顺序用各元素的关键字与给定值序用各元素的关键字与给定值x进行比较,直到找到与其进行比较,直到找到与其值相等的元素,则查找成功,给出该元素在表中的位置。值相等的元素,则查找成功,给出该元素在表中的位置。n若整个表都已检测完仍未找到关键字与若整个表都已检测完仍未找到关键字与x相等的元素,相等的元素,则查找失败,给出失败信息。则查找失败,给出失败信息。n以以顺序表或单链表顺序表或单链表表示静态查找表表示静态查找表一、顺序查找(一、顺序查找(Linear search,又称线性查找)又称线性查找)7一、顺序查找一、顺序查找1).1).顺序表的存储结构:顺序表的存储结构:int MaxListSize=100;class DataT
4、ype KeyType Key; other;class SeqList DataType dataMaxListSize; /表基址,表基址,0号单元留空。号单元留空。 int size; /表长,即表中数据元素个数表长,即表中数据元素个数 ;8 int Locate (DataType e) int i = 0; while ( i =size ) return -1; /没有找到没有找到 else return i; /找到此元素,返回其下标找到此元素,返回其下标/ Locate 第二章讲的查找算法:第二章讲的查找算法:92).算法的实现:算法的实现:编程技巧:编程技巧: 把待查关键字把待查关键字keykey存入表头或表尾(俗称存入表头或表尾(俗称“哨兵哨兵”),),这样可以加快执行速度(避免每一次查找都检测整个表这样可以加快执行速度(避免每一次查找都检测整个表是否查找完毕)。是否查找完毕)。一、顺序查找一、顺序查找10int Search( KeyType key ) /在顺序表中,查找关键字与在顺序表中,查找关键字与keykey相同的元素;若成功相同的元素;若成功 / /返回
5、其位置信息,否则返回返回其位置信息,否则返回0 0data0.key =key; for( i=size; data i .key!=key; - - i );return i; / Search同学们自己考虑对同学们自己考虑对单链表单链表如何线性查找?如何线性查找?2).算法的实现:算法的实现:一、顺序查找一、顺序查找11为确定元素在查找表中的位置,需给定值进行比较的关键字个数为确定元素在查找表中的位置,需给定值进行比较的关键字个数的期望值的期望值其中其中: n 为表长,为表长,Pi 为查找表中第为查找表中第i个记录的概率,假设每次查找个记录的概率,假设每次查找都是成功的都是成功的,则有则有 Pi=1Ci为找到该记录时,比为找到该记录时,比较过的关键字的个数,较过的关键字的个数,Ci = n-i+1,ASL = nP1 +(n-1)P2 +2Pn-1+Pn,如果要查找的元素如果要查找的元素在表中的任何位置的概率是相等的,在表中的任何位置的概率是相等的,P=1/n,ASL=(n+1)/23) 顺序查找算法的平均查找长度顺序查找算法的平均查找长度(ASL)一、顺序查找一、顺序查找 nii
《内蒙古大学《算法与数据结构》课件第5章集合与查找》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第5章集合与查找》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页