数据结构课件-第9章.pdf

  1. 1、本文档共72页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构课件-第9章

数据结构与算法 Data Structure and Algorithm 第9章 查找 目 录 9.1 查找的基本概念 9 .2 静态查找表 9 .3 动态查找表 9 .4哈希表 9.1 查找的基本概念 (1)关键字 主关键字 关键字是数据元素中某个数据项的值,可以标志一个数据元素。 主关键字是可唯一标志一个数据元素的某个数据项的值 出生日期 性 学号 姓名 来 源 总分 录取专业 别 年 月 日 ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ 赵剑平 男 1982 11 05 石家庄一中 593 计算机 蒋伟峰 男 1982 09 12 保定三中 601 计算机 郭 娜 女 1983 01 25 易县中学 598 计算机 ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ 郭 娜 女 1982 05 2 昌平一中 578 计算机 (2 )查找 也称为检索,就是根据给定的值,在一个表中查找出其关键字 等于给定值的数据元素,若表中有这样的元素,则称查找是成功的 ,此时查找的信息为给定整个数据元素的输出或指出该元素在表中 的位置;若表中不存在这样的记录,则称查找是不成功的,或称查 找失败,并可给出相应的提示。 (3)内部查找 外部查找 若整个查找过程全部在内存进行,则称这样的查找为内查找 ;反之,若在查找过程中还需要访问外存,则称之为外查找。我 们仅介绍内部查找。 (4 )查找表 由同一类型的数据元素构成的集合。可分为静态查找表和动态 查找表。 (5 )静态查找 动态查找 查找过程中表中数据不会再增加、删除、修改,如查找数据元 素是否在表中,或检查某个数据的属性这些一般查找都属于静态查 找。 查找过程中数据元素会增加、删除和修改操作的属于动态查找 。 9.2 静态表的查找 9.2.1 顺序表的查找 9.2.2 有序表的查找 9.2.3 索引顺序表的查找 9.2.1 顺序表的查找 1.顺序查找的基本思想(Sequential Search) 顺序查找是一种最简单的查找方法,它的基本思 想是:从表的一端开始,顺序扫描线性表,依次将扫 描到的结点关键字和待找的值K相比较,若相等,则 查找成功,若整个表扫描完毕,仍末找到关键字等于 K的元素,则查找失败。 顺序查找既适用于顺序表,也适用于链表。若用 顺序表,查找可从前往后扫描,也可从后往前扫描, 但若采用单链表,则只能从前往后扫描。另外,顺序 查找的表中元素可以是无序的。 此处以顺序表为例,从后往前扫描。 2 .顺序查找算法实现 typedef struct{ ElemType *elem; int length; }SStable; int Search_Seq(SSTable ST, KeyType key){ //在顺序表ST中顺序查找其关键字等于Key 的数据元素。若找到,则函数值 //为该元素在表中的位置,否则为0 。 ST.elem[0].key = key; //“哨兵”,提高查找效率 for(i=ST.length; !EQ(ST.elem[i].key,key); --i); return i; }//Search_

文档评论(0)

dajuhyy + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档