《数据结构00001.ppt》由会员分享，可在线阅读，更多相关《数据结构00001.ppt（24页珍藏版）》请在三一文库上搜索。
1、数据结构 第一章 绪论 第二章 线性表 第三章 稀疏矩阵和广义表 第四章 栈和队列 第五章 树和二叉树 第六章 二叉树的应用 第七章 图 第八章 查找 第九章 排序 扮 体 讣 舵 闸 坟 要 柞 耕 微 逾 笑 娠 劈 贺 释 铱 基 与 沃 躁 实 依 秤 刺 秘 享 戮 辙 衬 尾 铝 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 第八章第八章 查找查找 8.1 8.1 对查找的操作：对查找的操作： l l 1 1）查询查询( (检索检索) )某个某个“特定的特定的” 数数 据元素是否在查找表中及各据元素是否在查找表中及各 种属性；种属性； l l 2 2）在查
2、找表中在查找表中插入插入一个数据元素；一个数据元素； l l 3 3）从查找表中）从查找表中删去删去某个数据元素。某个数据元素。 滥 镶 挺 硕 红 俊 霜 较 酸 析 危 累 仓 厨 痒 痹 局 独 瀑 乔 磁 难 还 腮 讲 盗 踌 蹦 直 杀 骤 坷 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 1. 1.顺序查找顺序查找 2. 2.二分查找二分查找 3. 3.索引顺序索引顺序 8.2 8.2 静态查找表静态查找表 橡 色 铡 诈 戳 信 孽 巾 织 沁 相 伦 烹 九 制 亮 安 褪 尚 袄 海 圭 综 咬 杨 疙 朵 弄 骏 钱 捎 点 数 据 结 构 0
3、0 0 0 1 数 据 结 构 0 0 0 0 1 顺序搜索的平均搜索长度顺序搜索的平均搜索长度 设搜索第设搜索第 i i 个元素的概率为个元素的概率为 p p i i ，搜索到第，搜索到第 i i 个元素个元素 所需比较次数为所需比较次数为 c c i i ，则搜索成功的平均搜索长度，则搜索成功的平均搜索长度: : 在顺序搜索情形，在顺序搜索情形，c c i i = = i i +1, +1, i i = 0, 1, = 0, 1, , , n n-1-1，因此，因此 在等概率情形，在等概率情形，p p i i = 1/ = 1/n n, , i i = 0, 1, = 0, 1, , ,
4、n n-1-1。 1. 1.顺序查找顺序查找 诧 莲 膊 搂 睁 端 使 憾 斯 绷 摹 胺 噎 继 氖 蒋 介 琐 湍 闪 坏 棋 攫 染 雄 应 酶 哀 汛 棍 尧 菩 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 顺序查找算法 Struc elemtypeeneytype data; keytype key; Int seqserch(elemtype a, int n, keytype k) an.key=k; for(int i=0;i+) if(ai.key=k) break; If(in) return I Else return -1; 臼 轻 逾 斋
5、 问 匈 砒 确 甄 依 厘 巢 色 透 队 他 辖 冤 人 栖 注 抠 蔷 燎 死 帘 太 攒 九 标 轴 斩 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 2.二分查找 条件：表已排序 思想：第一步把表一分为二； 判定查找的元素落在哪部分； 依据上述步骤重复直到最后找 到（或对半结束查找不成 功） 算法下一页 物 训 耙 晌 贩 角 酵 强 世 骑 葱 哼 炕 痰 篱 私 舶 谚 枚 刊 塌 资 涡 霍 箱 篡 传 岛 前 焰 腥 橙 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 Int binserch(elemtype a, int
6、low, int hiht ,keytype k) if(low=high) int mid =(low+high)/2; if(k=amid.key) return mid; else if(kamid.key) return binserch(a,low,mid-1,k); else return binserch(a,mid,high-1,k) return -1; 下一页图示 匹 桨 娠 咽 杖 弹 烹 泽 钻 泪 师 符 敝 房 窟 交 艺 凿 冬 胡 余 蒜 贮 碗 胡 忘 酌 涡 颐 揣 恃 焙 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 搜索成功的例
7、子 搜索失败的例子 下一页判定树 掐 傣 橇 木 肉 布 禄 尧 毗 属 萍 栓 乌 骋 点 煤 圣 赌 题 吞 凑 陵 蜂 仍 蕉 框 具 蘸 讥 尔 狐 拂 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 搜索成功的情形 搜索不成功的情形 从有序表构造出的二叉搜索树从有序表构造出的二叉搜索树( (判定树判定树) ) n n 若设若设 n n = 2= 2 h h -1-1，2 2 h h = = n n+1, +1, h h = log = log 2 2 ( (n n+1)+1)。 n n 第第0 0层结点有层结点有1 1个，搜索第个，搜索第0 0层结点要比较层结
8、点要比较1 1次；次； 第第1 1层结点有层结点有2 2个，搜索第个，搜索第1 1层结点要比较层结点要比较2 2次；次； ， 戈 惹 聪 伙 撼 巍 音 婴 耙 孵 价 浴 歹 侧 抨 樊 垦 破 吵 溜 赵 劝 曾 郎 冬 宙 匣 秦 役 淮 鳞 晃 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 顺序查找表的查找算法简单，顺序查找表的查找算法简单， 但但 平均查找长度较大，特别不适用于平均查找长度较大，特别不适用于 表长较大的查找表。表长较大的查找表。 总结：总结： 有序查找表有序查找表 若以若以有序表有序表表示静态查找表，则表示静态查找表，则 查找过程可以基于查找
9、过程可以基于“ “折半折半” ”进行。进行。 犹 靠 鄂 诽 倒 黎 零 球 跃 飘 奋 芳 邵 弊 则 啼 杂 矣 辉 峪 设 术 缄 酸 落 妇 坐 藕 花 嗽 奄 藕 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 5.3 5.3 索引顺序表的查找过程：索引顺序表的查找过程： 1 1）由索引确定记录所在区间；）由索引确定记录所在区间； 2 2）在顺序表的某个区间内进行查找。）在顺序表的某个区间内进行查找。 索引可以根据查找表的特点来构造。索引可以根据查找表的特点来构造。 索引顺序查找索引顺序查找的过程也是一个的过程也是一个 “ “缩小区间缩小区间” ”的查找过程。
10、的查找过程。 漆 音 谣 悄 累 娜 只 竹 章 创 膳 网 白 撼 衣 长 钙 杰 贞 讶 叼 月 芦 件 达 俏 美 砂 著 雍 夏 摩 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 一、索引顺序查找的数据结构： Struct indexitem indexkeytype index;int start ;int length; 职工 号 姓 名 JS001 JS002 JS003 JS004 DZ001 DZ002 DZ003 JJ001 JJ002 HG001 HG002 HG003 主表 Js04 Dz43 Jj72 hg93 0 1 2 3 Index s
11、tart lengh 索引表 柴 畸 硬 舔 铺 悬 疚 拽 雅 彩 悦 晃 锨 异 安 幻 汕 痊 碎 渊 刽 酪 齐 的 骏 够 临 俱 旗 短 锦 夷 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 二、分块查找：在索引表为稀疏索引 15 26 18 3436 72 40 57 43 86 93 98 34 72 98 0510 453 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Index Start lengh 索引表 主表 注：同一块中的数据没有排序 端 禁 殷 喀 漫 福 珠 浴 煌 龙 症 预 谗 启 仁 屠 阿 浆
12、 涟 男 什 兴 靠 碗 盈 否 闽 怜 啪 赠 枷 粒 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 8.4 8.4 散散 列列 查查 找找 动态查找表 一、散列的概念 散列：通过对表中的每个元素关健字K为自变量的 H()计算出一值作为一连续存储空间的位置,并将 该元素存储到这个单元中.此函数称散列函数或 哈希函数.()称散列地址或哈希地址,上述的存储 空间称散列表或哈希表. 例:A=(18,75,60,43,54,90,46) h(k)=k%m :m为散列表的长度=13 43186075 0 1 2 3 4 5 6 7 8 9 10 11 12 54 9046 同
13、义词冲突:70 下一页冲突 佰 壤 嘉 枕 陈 珠 扮 巢 蜜 纳 兴 惊 札 磐 远 烤 含 逗 绩 催 樊 噬 碱 乾 墨 皖 瞅 收 阂 懒 痔 择 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 引起冲突的三个原因: 一、装填因子:=n/m 二、与散函数有关 三、与解决的方法有关 1. 1. 直接定址法直接定址法 3. 3. 数字分析法数字分析法 5. 5. 折叠法折叠法 4. 4. 平方取中法平方取中法 2. 2. 除留余数法除留余数法 二、对数字的关键字可有下列构造方法：二、对数字的关键字可有下列构造方法： 若是非数字关键字，则需先对其进若是非数字关键字，则
14、需先对其进 行数字化处理。行数字化处理。 跪 苞 狸 偏 主 婚 竿 射 疯 兹 呼 耀 浅 黔 褐 凡 完 敢 缄 揩 千 哉 赊 芝 什 卧 摸 温 棒 径 飞 夷 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 1. 1. 直接定址法直接定址法:h(k)=k+c:h(k)=k+c 3. 3. 数字分析法数字分析法:(923:(9232687526875,923,9234363443634, , 9279277463874638,923,9238126281262,923,9239422094220) ) 5. 5. 折叠法：折叠法：k=68242324, k=68
15、242324, 散列分三散列分三 段段682682，423423，24240 0，叠加和：，叠加和：1 1345345， 其散列地址为：其散列地址为：345345 4. 4. 平方取中法平方取中法:32:32 2 2 取中三位取中三位1 102024 4 2. 2. 除留余数法除留余数法:h(k)=k%m:h(k)=k%m 洲 聂 穷 悠 鸟 灌 绪 溪 廊 侦 弥 钙 纶 瓣 书 啼 闺 罗 坚 赔 箍 挤 三 瘟 涂 沼 莫 酒 莲 例 歇 顽 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 三、处理冲突的方法三、处理冲突的方法 “ “处理冲突处理冲突” ” 的实际
16、含义是：的实际含义是： 为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。 1. 1. 开放定址法开放定址法 18 1 2 3 4 5 6 7 8 2627 非同义词冲突 线性探查法 涤 痢 镰 箱 痈 瓢 糊 衔 疫 绷 驯 樊 哩 复 涸 迎 侵 敞 沛 再 哦 珊 挪 堤 进 弹 财 渣 郊 敲 宰 晾 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 2. 2. 链接法链接法 0 1 2 3 4 5 6 7 8 9 10 11 12 B(18,75,60,43,54,90,46,31,58,73,15,34) H(k)=k%13 15 54
17、43 3158 46 3475 18 73 60 90 酮 比 韩 科 眶 也 准 螟 乖 搂 休 随 梆 派 怜 瞻 敢 延 纫 现 下 囤 抵 库 廊 踪 蛛 譬 澜 廊 躯 址 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 8.5 B - 8.5 B - 树树查找查找 1 1定义定义 2 2查找过程查找过程 3 3插入操作插入操作 4 4查找性能的分析查找性能的分析 磐 氛 樟 园 裴 察 媚 迈 汗 常 钨 鹏 喜 恕 哉 设 斤 瑶 早 查 陨 猪 侯 俗 慢 仔 幌 鉴 站 乡 树 蝴 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1
18、 在在 m m 阶的阶的B-B-树上，每个非终端结点树上，每个非终端结点 可能含有：可能含有： n n 个个关键字关键字 K K i i （1 1 i i n n） nmnm 或或 n n 个个指向记录的指针指向记录的指针 D D i i （1in1in） n+1n+1 个个指向子树的指针指向子树的指针 A A i i （0in0in） 多叉树的特性多叉树的特性 步 螺 盘 紫 缚 纯 涉 鳃 莫 坯 譬 蔑 鹏 操 纸 逮 二 忘 荆 雹 姿 禁 魁 怀 填 赫 苛 利 熊 崔 颗 捧 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 162a mt 21538 162
19、 1 8 2 21 26 1 45 bc defg h 轴 兹 铭 间 熙 核 猫 鞘 骂 啊 都 啡 宙 悼 绰 钻 亏 商 区 柑 春 舀 墨 壤 帖 昼 整 策 谜 面 玄 乔 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 非叶结点中的非叶结点中的多个关键字多个关键字均均自小至大有序自小至大有序排排 列，即：列，即：K K 1 1 K K 2 2 K Kn n ； ； A Ai-1 i-1 所指子树上所有关键字均 所指子树上所有关键字均小于小于K K i i ； A A i i 所指子树上所有关键字均所指子树上所有关键字均大于大于K K i i ； 查找树的特性
20、查找树的特性 脯 遁 踪 韧 惭 渊 窝 略 求 赢 灿 阮 顷 朵 阅 融 丈 凸 艳 抚 戈 抿 量 附 吨 残 闷 亦 目 贝 皿 柒 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 平衡树的特性平衡树的特性 l l 树中所有树中所有叶子结点叶子结点均不带信息，且在树中均不带信息，且在树中 的的同一层次同一层次上；上； l l 根结点或为叶子结点，或根结点或为叶子结点，或至少至少含有两棵子含有两棵子 树；树； l l 其余所有非叶结点均其余所有非叶结点均至少至少含有含有 m/2m/2 棵棵子子 树，树，至多至多含有含有 mm 棵子树；棵子树； 咏 道 洗 铁 曙 院 叉 亢 邱 爬 极 涤 铅 托 取 橇 鸽 脂 夫 柠 耀 艳 伦 申 臻 邵 降 筷 顿 武 麓 洁 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1 B-B-树的定义树的定义 B-B-树是一种树是一种 平衡平衡 的的 多路多路 查找查找 树：树： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 棺 补 魏 炽 阶 么 煌 猖 聋 祁 钧 剥 莱 肿 挫 妮 伟 吏 拿 斑 索 荤 捅 免 盆 幌 裳 缓 痞 抑 家 且 数 据 结 构 0 0 0 0 1 数 据 结 构 0 0 0 0 1