数据结构 第8章 查找(作业)
数据结构
第8章 查找
第8章 查找8.1 查找的基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表
数据结构
第8章 查找
8.1 查找的基本概念关键字：数据元素的某个数据项的值，用它可以标识列表 中的一个或一组数据元素。如果一个关键字可以唯一标识列表 中的一个数据元素， 则称其为主关键字，否则为次关键字。
当数据元素仅有一个数据项时， 数据元素的值就是关键字。
数据结构
第8章 查找
查找：根据给定的关键字值，在查找表中确定一个其关键 字与给定值相同的数据元素，并返回该数据元素在查找表中的 位置。若找到相应的数据元素，则称查找是成功的，否则称查
找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。
数据结构
第8章 查找
8.2 静态查找表8.2.1 顺序查找法顺序查找法的过程是：从表中最后一个记录开始，逐个进 行记录的关键字和给定值的比较，若某个记录的关键字和给定 值比较相等，则查找成功，否则查找失败。存储结构通常为顺 序结构，也可为链式结构。
数据结构
第8章 查找
//静态查找表的顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建 //表时按实际长度分配，0号单元留空 int length; //表长度 } SSTable;
数据结构
第8章 查找 基于顺序结构的算法如下：
int Search_Seq(SSTable ST, KeyType key)
{ // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。算法9.1 int i; ST.elem[0].key=key; // 哨兵
for(i=ST.length;!EQ(ST.elem[i].key,key);--i); // 从后往前找
return i;}
// 找不到时，i为0
其中ST.elem[0]称为监视哨，可以起到防止越界的作用。
数据结构
第8章 查找
8.2.2 有序表的查找折半查找法又称二分法查找法，这种方法适用于有序表。
其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成 前、后两个子表，如果中间位置记录的关键字大于查找关键字， 则进一步查找前一子表，否则进一步查找后一子表。重复以上 过程，直到找到满足条件的记录，使查找成功，或直到子表不
存在为止，此时查找不成功。
数据结构
第8章 查找
图8.1 折半查找示意图
数据结构
第8章 查找 折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key) { // 在有序表ST中折半查找其关键字等于key的数据元素。若 找到，则函数值为该元素在表中的位置，否则为0。算法9.2 low=1 ; high=ST.length; // 置区间初值 while(low<=high) { mid=(low+high)/2; if EQ(key,ST.elem[mid].key) // 找到待查元素 return mid; else if LT(key,ST.elem[mid].key) high=mid-1; // 继续在前半区间进行查找 else low=mid+1; // 继续在
后半区间进行查找 } return 0; // 顺序表中不存在待查元素 }
数据结构
第8章 查找
8.2.3 索引顺序表的查找(分块查找法)分块查找法要求将列表组织成以下索引顺序结构： 首先将列表分成若干个块(子表)。一般情况下，块的长度 均匀，最后一块可以不满。每块中元素任意排列，即块内无 序，但块与块之间有序。
构造一个索引表。其中每个索引项对应一个块并记录每块 的起始位置，以及每块中的最大关键字(或最小关键字)。 索引表按关键字有序排列。
数据结构
第8章 查找 下图的索引顺序表包括三个块，第一个块起始地址0,块内 最大关键字25;第二个块起始地址为5, 块内最大关键字 58;第三个块起始地址为10,块内最大关键字为88。
索引表 25 58 88
各块内的最大关键字 各块的起始地址
列表 18 14 12 25 0 1 2 3
8 4
28 32 45 36 58 60 88 71 5 6 7 8 9 10 11 12
图8.2 分块查找法示意图
数据结构
第8章 查找 分块查找的基本过程如下：
(1) 首先将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查
找法进行。 (2) 用顺序查找法在相应块内查找关键字为K的元素。 例如，在上述索引顺序表中查找36。首先，将36与索引 表中的关键字进行比较，因为25<36≤58,所以36在第二个块 中， 进一步在第二个块中顺序查找， 最后在8号单元中找到 36。
数据结构
第8章 查找
8.3 动态查找表动态查找表的特点是表结构本身是在查找过程中动态生成 的，即对于给定值key,若表中存在其关键字等于key的记录，
则查找成功返回，否则插入关键字等于key的记录。主要包括二叉排序树、 平衡二叉树等。
数据结构
第8章 查找 8.3.1 二叉排序树 二叉树排序树或者是一棵空树，或者是具有如下性质的二叉
树：(1)若它的左子树非空，则左子树上所有结点的值均 小于根结点的值； (2)若它的右子树非空，则右子树上所有结点的值均 大于根结点的值；
(3)它的左右子树也分别为二叉排序树。
数据结构
第8章 查找
5 2 1 3 4 7 6 8 9CHEN
CAO
ZHA O DING
WA NG
(a) 二叉排序树示例 1
(b) 二叉排序树示例 2(根据字符 ASCⅡ 码的大小 )
图8.3 二叉排序树
数据结构
第8章 查找 在下面讨论的二叉排序树的操作中，使用二叉链表作 为存储结构，其结点结构说明如下：typedef struct node
{ KeyType key ;
//关键字的值
struct node *lchild, *rchild; //左右指针 }BSTNode, *BSTree;
数据结构
第8章 查找 1. 二叉排序树的插入和生成 已知一个关键字值为key的结点s, 若将其插入到二叉排序 树中，只要保证插入后仍符合二叉排序树的定义即可。插入可 以用下面的方法进行： ① 若二叉排序树是空树，则key成为二
叉排序树的根；② 若二叉排序树非空， 则将key与二叉排序树
的根进行比较，如果key的值等于根结点的值，则停止插入；如果key的值小于根结点的值，则将key插入左子树；如果key
的值大于根结点的值，则将key插入右子树。
数据结构
第8章 查找45 45 ( a) 空树 45 24 12 ( e ) 插入 12 53 12 24 28 ( f ) 插入 28 ( b) 插入 45 45 53 12 24 28 ( g ) 插入 90 24 ( c) 插入 24 24 45 53
( d) 插入 53 45 53 90
图8.4 二叉排序树的建立过程
数据结构
第8章 查找
24 12 28 53 90
45图8.5 输入顺序不同所建立的不同二叉排序树
数据结构
第8章 查找 2. 二叉排序树的删除
从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的
二叉树仍然满足二叉排序树的性质不变。也就是说，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。 删除操作首先要查找，已确定被删结点是否在二叉排序 树中。若不在，则不做任何操作；否则，假设要删除的结点 为p,结点p的双亲结点为f,并假设结点p是结点f的左孩子 (右孩子的情况类似)。
相关推荐：
- [专业资料]《蜜蜂之家》教学反思
- [专业资料]过去分词作定语和表语1
- [专业资料]苏州工业园区住房公积金贷款申请表
- [专业资料]保安管理制度及处罚条例细则
- [专业资料]2018年中国工程咨询市场发展现状调研及
- [专业资料]2015年电大本科《学前教育科研方法》期
- [专业资料]数字信号处理实验 matlab版 离散傅里叶
- [专业资料]“十三五”重点项目-虎杖白藜芦醇及功
- [专业资料]2015-2020年中国竹木工艺市场需求及投
- [专业资料]国际贸易理论与实务作业五：理论案例分
- [专业资料]财政部修订发布事业单位会计制度
- [专业资料]BCA蛋白浓度测定试剂盒(增强型)
- [专业资料]工程进度总计划横道图模板(通用版)
- [专业资料]七年级地理同步练习(天气与气候)
- [专业资料]X光安检机介绍火灾自动报警系统的组成
- [专业资料]衢州市人民政府办公室关于印发衢州市区
- [专业资料]经济全球化及其影响[1]
- [专业资料]质粒DNA限制性酶切图谱分析
- [专业资料]国家安全人民防线工作“六项”制度
- [专业资料]劳动力投入计划及保证措施
- 电子账册联网监管培训手册
- 人教版语文七年级上第1课《在山的那边
- 对我区担保行业发展现状的思考与建议
- 平面四边形网格自动生成方法研究
- 2016年党课学习心得体会范文
- 如何设置电脑定时关机
- 全球最美人妖排行榜新鲜出炉
- 社会实践调查报告及问卷
- Visual Basic习题集
- 《鱼我所欲也》课件2
- 浙江省会计从业资格考试试卷
- 全遥控数字音量控制的D 类功率放大器资
- 鞍钢宪法与后福特主义
- 电表的改装与校准实验报告(1)
- 2014年高考理科数学真题解析分类汇编：
- Windows 7 AIK 的使用
- 风电场全场停电事故应急处置方案
- 化工原理选填题题库(下)
- 关于产学研合作教育模式的学习与思考
- 西安先锋公馆项目前期定位报告
