- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
数据结构国家教学资源库建设项目
数据结构教学目标【知识目标】?了解查找的基本概念?掌握顺序查找的基本思想、算法实现和查找效率分析?掌握二分查找的基本思想、算法实现和查找效率分析?掌握分块查找的基本思想、算法实现和查找效率分析?掌握二叉查找树的插入、删除、建树和查找算法及时间性能?掌握哈希查找方法、哈希函数的构造和解决冲突的方法【能力目标】?具有选择恰当的查询算法解决实际问题的能力单元7查找
数据结构引例描述——高校最低录取分数线查询该系统用于学生、学生家长和其他人员查询各高校的最低录取分数线,为他们的了解高校录取情况、做出正确的选择和决策提供有必要的信息。该系统有以下六项功能:(1)按考生分数查询高校信息;(2)按给定分数查询一定范围内的高校信息,包括:查询录取分数线比给定分数高(包括相等)的高校信息和录取分数线比给定分数低(包括相等)的高校信息;(3)按给定的分数范围查询高校信息;(4)能够添加高校信息;(5)为用户提供系统帮助,以便更好的使用系统;(6)安全退出本系统。演示执行单元7查找
数据结构知识储备7.1查找的基本概念一、基本概念1.查找定义给定一个值K,在含有n个结点的表中找出关键字等于给定值K的结点。若找到,则查找成功,返回该结点的信息或该结点在表中的位置;否则查找失败,返回相关的指示信息。2.动态查找表和静态查找表若在查找的同时对表做修改操作(如插入和删除),则相应的表称之为动态查找表。否则称之为静态查找表。3.内查找和外查找若整个查找过程都在内存进行,则称之为内查找;反之,若查找过程中需要访问外存,则称之为外查找。单元7查找
数据结构4.平均查找长度(AverageSearchLength)ASL查找运算的主要操作是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度ASL定义:即ASL等于每个结点的查找概率pi与比较次数ci的乘积的和。其中:(1)n是结点的个数;(2)p是查找第i个结点的概率。若不特别声明,认为每个i结点的查找概率相等,即p=p=…=p=1/n;l2n(3)c是找到第i个结点所需进行的比较次数。i单元7查找
数据结构7.2静态查找一、顺序查找(sequentialsearch)#defineN20typedefintKeyType;//关键字字段类型定义顺序查找又称线性查找,是最基本的查找方法之一。顺typedefcharOtherdataType;//非关键字字段类型定义序查找既适用于顺序表,也适用于链表。typedefstruct1.基本思想{KeyTypekey;从表的一端开始,顺序扫描线性表,依次按给定值kx与OtherdataTypedata;关键字(Key)进行比较,若相等,则查找成功,并给出数}NodeType;据元素在表中的位置;若整个表查找完毕,仍未找到与kx相typedefNodeTypeSeqList[N+1];//0号单元用作监视哨同的关键字,则查找失败,给出失败信息。2.基于顺序结构的顺序查找算法的类型描述单元7查找
数据结构3.具体算法4.算法分析(1)算法中监视哨R[0]的作用intSeqSearch(SeqlistR,KeyTypeK)为了在for循环中省去判定防止下标越界的条件i≥1,从而{//在顺序表R[1...n]中查找关键字为K的结点节省比较的int时i;间。(2)成功时的顺序查找的平均查找长度R[0].key=K;//设置哨兵在等概率情况下,pi=1/n(1≤i≤n),故成功的平均查找长for(i=n;R[i].key!=K;i--);//从表后往前找度为(n+…+2+1)/n=(n+1)/2,即查找成功时的平均比较次数约returni;//若i为0,表示查找失败,否则R[i]是要找为表长的一半,若K值不在表中,则须进行n+1次比较之后才的结点能确}定查找失败。(3)顺序查找的优缺点优点是算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。缺点是查找效率低,因此,当n较大时不宜采用顺序查找。单元7查找
数据结构二、二分查找(binarysearch)1.二分查找:二分查找又称折半查找,它是一种效率较高的查找方法。二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2.二分查找的基本思想设R[low...high]是当前的查找区间。(1)首先确定该区间的中点位置:mid=[(low+high)/2];(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,
您可能关注的文档
- 新北师大版二年级下册《算得对吗》课件.ppt
- 文化常识之称谓z课件.ppt
- 数控程序编制分解课件.ppt
- 数控机床插补计算课件.ppt
- 数据完整性和计算机管理GMP要求课件.ppt
- 数据信号的传输课件.ppt
- 2024-2025学年小学英语六年级上册冀教版(三起)(2024)教学设计合集.docx
- 2024-2025学年小学科学五年级下册冀人版(2024)教学设计合集.docx
- 2024-2025学年小学劳动五年级上册湘人版《劳动实践指导手册》教学设计合集.docx
- 2024-2025学年高中语文必修三北师大版教学设计合集.docx
- 第十一章 电流和电路专题特训二 实物图与电路图的互画 教学设计 2024-2025学年鲁科版物理九年级上册.docx
- 人教版七年级上册信息技术6.3加工音频素材 教学设计.docx
- 5.1自然地理环境的整体性 说课教案 (1).docx
- 4.1 夯实法治基础 教学设计-2023-2024学年统编版九年级道德与法治上册.docx
- 3.1 光的色彩 颜色 电子教案 2023-2024学年苏科版为了八年级上学期.docx
- 小学体育与健康 四年级下册健康教育 教案.docx
- 2024-2025学年初中数学九年级下册北京课改版(2024)教学设计合集.docx
- 2024-2025学年初中科学七年级下册浙教版(2024)教学设计合集.docx
- 2024-2025学年小学信息技术(信息科技)六年级下册浙摄影版(2013)教学设计合集.docx
- 2024-2025学年小学美术二年级下册人美版(常锐伦、欧京海)教学设计合集.docx
文档评论(0)