数据结构00001.ppt

数据结构数据结构第一章第一章 绪论绪论第二章第二章 线性表线性表第三章第三章 稀疏矩阵和广义表稀疏矩阵和广义表第四章第四章 栈和队列栈和队列第五章第五章 树和二叉树树和二叉树第六章第六章 二叉树的应用二叉树的应用第七章第七章 图图第八章第八章 查找查找第九章第九章 排序排序扮体讣舵闸坟要柞耕微逾笑娠劈贺释铱基与沃躁实依秤刺秘享戮辙衬尾铝数据结构00001数据结构00001第八章 查找 8.1 对查找的操作：l l1 1））查询(检索)某个“特定的”数 据元素是否在查找表中及各 种属性；l l2 2））在查找表中在查找表中插入一个数据元素；一个数据元素；l l3 3）从查找表中）从查找表中删去某个数据元素某个数据元素滥镶挺硕红俊霜较酸析危累仓厨痒痹局独瀑乔磁难还腮讲盗踌蹦直杀骤坷数据结构00001数据结构000011.顺序查找顺序查找2.二分查找二分查找3.索引顺序索引顺序8.2 8.2 静态查找表静态查找表橡色铡诈戳信孽巾织沁相伦烹九制亮安褪尚袄海圭综咬杨疙朵弄骏钱捎点数据结构00001数据结构00001顺序搜索的平均搜索长度顺序搜索的平均搜索长度 设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi，搜索到第，搜索到第 i 个元素个元素所需比较次数为所需比较次数为 ci，则搜索成功的平均搜索长度，则搜索成功的平均搜索长度:在顺序搜索情形，在顺序搜索情形，ci = i +1, i = 0, 1, , n-1，因此，因此在等概率情形，在等概率情形，pi = 1/n, i = 0, 1, , n-1。

1.顺序查找顺序查找诧莲膊搂睁端使憾斯绷摹胺噎继氖蒋介琐湍闪坏棋攫染雄应酶哀汛棍尧菩数据结构00001数据结构00001顺序查找算法Struc elemtype{eneytype data; keytype key;}Int seqserch(elemtype a[], int n, keytype k){a[n].key=k; for(int i=0;;i++) if(a[i].key==k) break;If(i

n n 第第0层结点有层结点有1个，搜索第个，搜索第0层结点要比较层结点要比较1次；次；第第1层结点有层结点有2个，搜索第个，搜索第1层结点要比较层结点要比较2次；次；…，，戈惹聪伙撼巍音婴耙孵价浴歹侧抨樊垦破吵溜赵劝曾郎冬宙匣秦役淮鳞晃数据结构00001数据结构00001 顺序查找表的查找算法简单，顺序查找表的查找算法简单， 但但 平均查找长度较大，特别不适用于平均查找长度较大，特别不适用于 表长较大的查找表表长较大的查找表总结：总结： 有序查找表有序查找表 若以若以有序表有序表表示静态查找表，则表示静态查找表，则查找过程可以基于查找过程可以基于“折半折半”进行犹靠鄂诽倒黎零球跃飘奋芳邵弊则啼杂矣辉峪设术缄酸落妇坐藕花嗽奄藕数据结构00001数据结构000015.3 索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在区间；）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找在顺序表的某个区间内进行查找索引可以根据查找表的特点来构造索引可以根据查找表的特点来构造 索引顺序查找索引顺序查找的过程也是一个的过程也是一个“缩小区间缩小区间”的查找过程。

的查找过程漆音谣悄累娜只竹章创膳网白撼衣长钙杰贞讶叼月芦件达俏美砂著雍夏摩数据结构00001数据结构00001一、索引顺序查找的数据结构：一、索引顺序查找的数据结构：Struct indexitem{indexkeytype index;int start ;int length;}职工号职工号 姓名姓名JS001JS002JS003JS004DZ001DZ002DZ003JJ001JJ002HG001HG002HG003主表主表Js04Dz43Jj72hg930123Index start lengh索引表索引表柴畸硬舔铺悬疚拽雅彩悦晃锨异安幻汕痊碎渊刽酪齐的骏够临俱旗短锦夷数据结构00001数据结构00001二、分块查找：二、分块查找：在索引表为稀疏索引在索引表为稀疏索引15 26 18 3436 72 40 57 43 86 93 9834 72 9805104530 1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14IndexStartlengh索引表索引表主表主表注：同一块中的数据没有排序注：同一块中的数据没有排序端禁殷喀漫福珠浴煌龙症预谗启仁屠阿浆涟男什兴靠碗盈否闽怜啪赠枷粒数据结构00001数据结构000018.4 散散 列列 查查 找找动态查找表动态查找表一、散列的概念一、散列的概念散列：通过对表中的每个元素关健字散列：通过对表中的每个元素关健字K为自变量的为自变量的H(ＫＫ)计算出一值作为一连续存储空间的位置计算出一值作为一连续存储空间的位置,并将并将该元素存储到这个单元中该元素存储到这个单元中.此Ｈ函数称散列函数或此Ｈ函数称散列函数或哈希函数哈希函数.ＨＨ(ＫＫ)称散列地址或哈希地址称散列地址或哈希地址,上述的存储上述的存储空间称散列表或哈希表空间称散列表或哈希表.例例:A=(18,75,60,43,54,90,46) h(k)=k%m :m为散列表的长度为散列表的长度=1343 186075ＨＨ0 1 2 3 4 5 6 7 8 9 10 11 12549046同义词冲突同义词冲突:70下一页冲突佰壤嘉枕陈珠扮巢蜜纳兴惊札磐远烤含逗绩催樊噬碱乾墨皖瞅收阂懒痔择数据结构00001数据结构00001引起冲突的三个原因引起冲突的三个原因:一、装填因子一、装填因子:α=n/m 二、与散函数有关二、与散函数有关三、与解决的方法有关三、与解决的方法有关1. 直接定址法直接定址法3. 数字分析法数字分析法5. 折叠法折叠法4. 平方取中法平方取中法2. 除留余数法除留余数法二、对数字的关键字可有下列构造方法：二、对数字的关键字可有下列构造方法： 若是非数字关键字，则需先对其进若是非数字关键字，则需先对其进行数字化处理。

行数字化处理跪苞狸偏主婚竿射疯兹呼耀浅黔褐凡完敢缄揩千哉赊芝什卧摸温棒径飞夷数据结构00001数据结构000011. 直接定址法直接定址法:h(k)=k+c3. 数字分析法数字分析法:(92326875,92343634,92774638,92381262,92394220)5. 折叠法：折叠法：k=68242324, 散列分三散列分三段段682，，423，，240，叠加和：，叠加和：1345，，其散列地址为：其散列地址为：3454. 平方取中法平方取中法:322 取中三位取中三位10242. 除留余数法除留余数法:h(k)=k%m洲聂穷悠鸟灌绪溪廊侦弥钙纶瓣书啼闺罗坚赔箍挤三瘟涂沼莫酒莲例歇顽数据结构00001数据结构00001三、处理冲突的方法三、处理冲突的方法 “处理冲突处理冲突” 的实际含义是：的实际含义是：为产生冲突的地址寻找下一个哈希地址为产生冲突的地址寻找下一个哈希地址1. 开放定址法开放定址法181 2 3 4 5 6 7 82627非同义词冲突非同义词冲突线性探查法线性探查法涤痢镰箱痈瓢糊衔疫绷驯樊哩复涸迎侵敞沛再哦珊挪堤进弹财渣郊敲宰晾数据结构00001数据结构000012. 链接法链接法∧∧ ∧∧∧∧∧∧∧∧0 1 2 3 4 5 6 7 8 9 10 11 12B＝＝(18,75,60,43,54,90,46,31,58,73,15,34)H(k)=k%131554∧∧43∧∧3158∧∧46∧∧3475∧∧18∧∧7360∧∧90∧∧酮比韩科眶也准螟乖搂休随梆派怜瞻敢延纫现下囤抵库廊踪蛛譬澜廊躯址数据结构00001数据结构00001 8.5 B - 树树查找查找1．定义．定义2．查找过程．查找过程3．插入操作．插入操作4．查找性能的分析．查找性能的分析磐氛樟园裴察媚迈汗常钨鹏喜恕哉设斤瑶早查陨猪侯俗慢仔幌鉴站乡树蝴数据结构00001数据结构00001 在在 m 阶的阶的B-树上，每个非终端结点树上，每个非终端结点 可能含有：可能含有： n 个个关键字关键字 Ki（（1≤ i≤n）） n