c语言数据结构查找算法大全.ppt

查找 9 1基本概念 查找是指从一组记录集合中找出满足给定条件的记录 查找表在讨论查找时 通常假设被查找的对象是由一组同一类型的记录构成的集合 称这个集合为查找表 关键字是指记录的某个数据项 用它可以标识一个记录 若此关键字可以唯一地标识一个记录 则称此关键字为主关键字 反之 把可以识别若干记录的关键字称为次关键字 查找是指根据某个给定的值 在查找表中查找一个其关键字值等于给定值的记录 若表中存在这样的一个记录 则称查找成功 若表中不存在关键字值等于给定值的记录 则称查找失败 查找技术分为 1静态查找表技术顺序查找 折半查找 索引顺序查找2动态查找表技术二叉查找树3哈希表技术哈希表技术 在查找一个记录时所做的主要操作是关键字的比较 所以通常把查找过程中对关键字的平均比较次数作为衡量一个查找算法效率优劣的标准 并称平均比较次数为平均查找长度 AverageSearchLength 平均查找长度的定义为 ASL 其中 n为元素的个数 ci是查找第i个记录需进行的比较次数 pi是查找第i个记录的概率 一般可认为查找每个记录的概率是相等的 即p1 p2 pn 1 n 查找算法的衡量指标 当ASL不易计算时 使用最大查找长度MSL来衡量算法 9 2静态查找表 基于线性表的查找 此类查找主要有顺序查找 折半查找和索引顺序查找三种方法 为简便起见 假设查找表中的记录为整型 记录的关键字即为该整数 记录的个数为N 存放在数组R中 查找表的C语言定义如下 defineN100intR N 1 使用的地址空间 1 N 9 2 1顺序查找基本思想 从查找表的一端开始 逐个将记录的关键字值和给定值进行比较 如果某个记录的关键字值和给定值相等 则称查找成功 否则 说明查找表中不存在关键字值为给定值的记录 则称查找失败 顺序查找算法如下 intseqsearch intR intk 元素存放在R的1 N处 在查找表R中查找关键字为k的记录 查找成功 返回记录在R中的下标值 否则返回0 inti R 0 k 将k放入R 0 中 i N 从最后一个元素开始查找 while R i k R 0 用来控制循环退出 起 监视哨 的作用 i return i 若i为0 表示查找失败 否则R i 为要找的记录 顺序查找算法性能分析 在顺序查找中 比较次数ci取决于所查记录在表中的位置 如查找记录R n 时 仅需比较一次 而查找记录R 1 时 则需比较n次 一般来说 查找第i个记录的比较次数为ci n i 1 因此 查找成功的平均查找长度为 在等概率情况下 即pi 1 n时 查找成功的平均查找长度为 n 1 2 若关键字不在表中 则必须经过n 1次比较后才能确定查找失败 所以查找失败的平均查找长度为n 1 这个结果表明 顺序查找的查找长度是与记录的个数n成正比的 结论 顺序查找的优点是算法简单 且对表的结构没有任何要求 它的缺点是查找效率低 因此 当表中元素个数比较多时 不宜采用顺序查找 ASL成功 pi ci pi n i 1 已知含有10个整数的查找表如下 9 13 15 7 45 32 56 89 60 36 从键盘上输入一个整数 用顺序查找的方法在查找表中查找该整数 若存在 输出该元素的下标值 否则 给出相应的信息 程序如下 例9 1 include defineN10main intx p inta N 1 0 9 13 15 7 45 32 56 89 60 36 scanf d 9 2 2折半查找 二分查找 使用折半查找必须具备两个前提条件 1 要求查找表中的记录按关键字有序 设 从小到大有序 2 只能适用于顺序存储结构基本思想 先取查找表的中间位置的关键字值与给定关键字值作比较 若它们的值相等 则查找成功 如果给定值比该记录的关键字值大 说明要查找的记录一定在查找表的后半部分 则在查找表的后半部分继续使用折半查找 若给定值比该记录的关键字值小 说明要查找的记录一定在查找表的前半部分 则在查找表的前半部分继续使用折半查找 直到查找成功 或者直到确定查找表中没有待查找的记录为止 即查找失败 设有一个11个记录的有序表的关键字值如下 812263745566472818995假设指针low和high分别指示待查元素所在区间的下界和上界 指针mid指示区间的中间位置 查找关键字值为26的过程 812263745566472818995low 1 mid 6 high 11 取mid位置的关键字值56与26作比较 显然26 56 故要查找的26应该在前半部分 所以下次的查找区间应变为 1 5 即low值不变仍为1 high的值变为mid 1 5 求得mid 3 812263745566472818995lowmidhigh 5 取mid指示位置的关键字值26与给定值26作比较 显然是相等的 说明查找成功 所查元素在查找表中的位置即为mid所指示的值 例 mid low high 2 查找关键字值为75的记录的过程 812263745566472818995lowmidhigh取mid位置的关键字值56与75作比较 显然75 56 说明要查找的记录在后半部分 待查区间变为 7 11 low mid 1 6 1 7 求得mid 9 812263745566472818995lowmidhigh再取mid位置的关键字值81与75作比较 显然7564 low mid 1 8 待查区间变为 8 8 求得mid 8 812263745566472818995low mid high显然75 72 待查区间变为low mid 1 9 high 8 此时high low 说明查找表中没有关键字值为75的记录 查找失败 折半查找算法 intbinsearch intR intk intlow high mid find 0 low 1 high n 置区间初值 while lowR mid low mid 1 在后半区查找 修改low elsehigh mid 1 在前半区查找 修改high if find return mid 查找成功 返回找到的元素位置 elsereturn 1 查找失败 返回 1 折半查找算法性能分析 在折半查找的过程中 每经过一次比较 查找范围都要缩小一半 所以折半查找的最大查找长度为MSL log2n 1当n足够大时 可近似的表示为log2 n 可见在查找速度上 折半查找比顺序查找速度要快的多 这是它的主要优点 结论 折半查找要求查找表按关键字有序 而排序是一种很费时的运算 另外 折半查找要求表是顺序存储的 为保持表的有序性 在进行插入和删除操作时 都必须移动大量记录 因此 折半查找的高查找效率是以牺牲排序为代价的 它特别适合于一经建立就很少移动 而又经常需要查找的线性表 9 2 3索引顺序查找 分块查找 分块查找又称索引顺序查找 是顺序查找的一种改进方法 分块查找要求把线性表分成若干块 在每一块中记录的关键字不一定有序 但是 块与块之间必须有序 假设这种排序是按关键字值递增排序的 抽取各块中的最大关键字及该块的起始位置构成一个索引表 按块的顺序存放在一个数组中 显然这个数组是有序的 一般按升序排列 折半查找或顺序查找 顺序查找 块1 块2 块3 分块查找过程分两步进行 首先查找索引表 确定待查记录所在块 子表 可用折半查找法或顺序查找法 在相应块 子表 中用顺序查找法查找记录 分块查找算法 structidtable intkey intaddr structidtableID b b为块数 索引表的类型定义如下 在下面的分块查找算法中 对索引表的查找采用折半查找法 查找成功时 函数值为关键字等于k的记录在R中的序号 查找失败时 函数值为 1 intblksearch intR struckidtableID intk inti low1 low2 high1 high2 mid low1 high1为索引表的区间下 上界 low1 0 high1 b 1 b为块数 while low1 b 则k大于查找表R中的所有关键字 return 0 结论 分块查找的效率介于顺序查找和折半查找之间 对于数据量巨大的线性表 它是一种较好的方法 在表中插入或删除一个记录时 只要找到该记录所属的块 就可以在该块内进行插入和删除运算 插入和删除无需移动大量记录 分块查找的主要代价是 需要增加一个辅助数组的存储空间和将初始表分块排序的运算 9 3哈希表的查找 用记录的关键字作为自变量 通过一个确定的函数H 计算出相应的函数值H k 然后以H k 作为该记录的存储地址 用这种方式建立起来的查找表称为哈希表 哈希表又称Hash表 散列表 换句话说 哈希表是通过对记录的关键字进行某种计算来确定该记录的存储位置的一种查找表 哈希表 9 3 1哈希表 把记录的关键字映射为记录的存储地址的函数称为哈希函数 哈希 Hash 表查找 对被查记录的关键字作某种运算后直接确定所查记录在表中的位置 记录的存储位置 Hash函数 记录的关键字 简单记为 d H k 哈希函数 假设要建立一个某单位30个人的基本信息表 每个人为一个记录 记录的基本信息有 编号 姓名 性别 学历等 其中这30个人的姓名分别简写为 Liu Feng Li Wu Chen Han Ye Dai 可以用一个长度为30的一维数组来存放这些人的信息 4 3 12 6 25 23 12 8 哈希表构造示例1 如果以姓名为关键字 设哈希函数为取姓名第一个字母在字母表中的序号 则各记录在表中的存储位置如下所示 根据该哈希函数构建的哈希表如下所示 冲突 不同的关键字 根据哈希函数被映射到同一个存储地址 这种现象被称为冲突 具有相同函数值的关键字称为该哈希函数的同义词 实际上 冲突是不可避免的 因为关键字的取值集合远远大于表空间的地址集合 我们只能尽量减少冲突的发生 在构造哈希函数时 主要面临两个问题 一是构造较好的哈希函数 把关键字集合中元素尽可能均匀地分布到地址空间中去 减少冲突的发生 另一个就是找到解决冲突的方法 当关键字是整型数时 取关键字本身或者关键字的某个线性函数为哈希函数 即 H key key或者H key a key b其中a b为常数 key为记录的关键字 直接定址法 9 3 2哈希函数的构造方法 例如 设有一个某年每月出生人口的统计表如下所示 从表可以看到 每个记录的存放是以月份为关键字 哈希函数取关键字自身 即H key key 如果要查找5月份出生的人数时 则根据H 5 5求出存储地址 查找地址为5的存储空间即可 先取关键字的平方 然后根据可使用空间的大小 选取平方数的中间几位为哈希地址 平方取中法 例 设有一组关键字为AB BC CD DE EF 其相应的机内码分别为0102 0203 0304 0405 0506 假设可利用的地址空间为两位的十进制整数 则利用平方取中法得到的哈希地址如下表所示 把关键字分成位数相等的几个部分 最后一部分的位数可以不同 对各部分进行叠加求和 将和去掉进位后作为哈希地址 折叠法 例如 设有一关键字key 7895613492 可利用的地址空间为三位十进制整数 下面分别用移位叠加和间界叠加法得到其哈希地址 7895613492 1701 7891653492 1305 此方法适用于关键字位数较多 而且关键字的每位上的数字分布大致均匀的情况 选择某个不大于哈希表长度m的最大质数p 用p去除关键字 用所得到的余数作为记录的哈希地址 即 H key key p p m 除留余数法 例如 设哈希表长度为100 则可取p为97 下表所示是利用p去除关键字 用所得余数作为哈希地址 对各记录关键字的各个位进行分析 选择其中分布均匀的若干位作为其哈希地址 数字分析法 例如 设有100条记录 记录的关键字为7位十进制数 如下表所示 通过分析表中的关键字 发现前2位均为03 第4 5位多为7 8 9三个数 因此这四位不可取 可以考虑取第3 6 7位中的任两位作为哈希地址 选择一个随机函数 取关键字的随机函数值作为它的哈希地址 即 H key random key 其中 random为随机函数 随机数法 通常 当关键字长度不等时 采用此方法构造哈希函数比较恰当 intrand void 函数 会返回一随机数值 范围在0至RAND MAX间 include C语言中怎样用rand函数产生一组数据值在m到n之间的数 m int 1 0 n m rand RAND MAX 处理冲突 在发生冲突时 为冲突元素找到一个哈希地址存放该元素 9 3 3处理冲突的方法 开放地址法链地址法再哈希法公共溢出区法 处理冲突的常用方法有 在冲突发生时 按照某种方法在哈希表中产生一个探测序列 按照这个序列 探测在哈希表中的其他存储空间 直到探测到不发生冲突的存储空间为止 探测公式 Hi key H key di m i 1 2 3 m 其中 Hi key 为经过i次探测找到的关键字为key的记录的哈希地址 H key 为哈希函数 m为表的长度 di为每次再探测时的地址增量 处理冲突 开放地址法 线性探测再散列di 1 2 m 1平方探测再散列di 12 12 22 22 32 32 k2 k2 k m 2 随机探测再散列di 随机函数 地址增量的取值有以下三种 把长度m的哈希表看成一个环形表 若发生冲突的地址为d 则依次探测d 1 d 2 d 3 m 1 0 1 d 1 直到找到一个空单元或找到关键字为key的记录为止 线性探测再散列 例 设在表长为14的哈希表中已放有关键字分别为17 57 19的记录 哈希函数H key key 13 现有第4个记录 其关键字为43 请将该记录填入哈希表 012345678910111213 关键字为43的记录填入前 实现的过程如下 H 43 43 13 4 由哈希函数得到该记录的哈希地址为4 产生冲突 用线性探测再散列处理冲突H 43 43 1 13 5 仍然冲突 继续探测 H 43 43 2 13 6 仍然冲突 继续探测 H 43 43 3 13 7 该地址为空 冲突处理结束 将记录填入地址为7的空间 012345678910111213 关键字为43的记录填入后 设有一组关键字 19 1 23 14 55 20 84 29 69 11 10 77 采用哈希函数 H key key 13 用开放地址法的线性探测再散列方法处理冲突 在地址区间为 0 18 的空间中对该关键字序列构造哈希表 例9 4 解 依题意 m 19 线性探测再散列的下一地址的计算公式为 d0 H key di di 1 1 m i 1 2 每个元素的哈希地址计算如下 H 29 29 13 3 冲突 H 29 3 1 19 4H 69 69 13 4 冲突 H 69 4 1 19 5H 11 11 13 11H 10 10 13 10 冲突 H 10 10 1 19 11 仍冲突 H 10 11 1 19 12H 77 77 13 12 冲突 H 77 12 1 19 0 地址 元素 H 19 19 13 6H 1 1 13 1H 23 23 13 10H 14 14 13 1 冲突 H 14 1 1 19 2H 55 55 13 3H 20 20 13 7H 84 84 13 6 冲突 H 84 6 1 19 7 仍冲突 H 84 7 1 19 8 因此 各关键字的记录对应的地址分配如下图所示 例设哈希函数为Hash key key 7 哈希表地址空间为 0 6 对关键字序列 32 13 49 55 22 38 21 利用线性探测再散列法解决冲突 1 构造哈希表 2 计算平均查找长度 解 由题意 首先计算出各关键字的初始哈希地址为Hash 32 4 Hash 13 6 Hash 49 0 Hash 55 6 Hash 22 1 Hash 38 3 Hash 21 0 哈希表及各关键字比较的次数 ASL 1 3 2 1 1 6 1 2 14 为每一个哈希地址建立一个链表 当冲突发生时 将具有相同哈希地址的记录链接到同一链表中 处理冲突 链地址法 例 已知一组关键字为 16 5 69 34 21 56 38 14 52 80 请按哈希函数H key key 11和链地址法处理冲突构造哈希表 解 依题意得每个记录的哈希地址为 H 16 16 11 5H 5 5 11 5H 69 69 11 3H 34 34 11 1H 21 21 11 10 H 56 56 11 1H 38 38 11 5H 14 14 11 3H 52 52 11 8H 80 80 11 3 构造的哈希表如下所示 H 16 16 11 5H 5 5 11 5H 69 69 11 3H 34 34 11 1H 21 21 11 10H 56 56 11 1H 38 38 11 5H 14 14 11 3H 52 52 11 8H 80 80 11 3 每个记录的哈希地址为 在查找等概率的前提下 成功查找每一个元素的平均查找长度为 ASL 1 5 2 3 3 2 10 17 10 当冲突发生时 采用另一个哈希函数计算关键字的哈希地址 即构造一系列的哈希函数H1 key H2 key Hn key 当冲突发生时 依次检查所构造的一系列哈希函数得到的哈希地址是否为空 处理冲突 再哈希法 当冲突发生时 将发生冲突的记录存储在另设立的一个公共溢出区 处理冲突 公共溢出区法 假设ht 0 m 1 是利用哈希函数H key 和某种解决冲突的方法构造的一个哈希表 则该哈希表的查找过程如下 9 3 3哈希表的查找过程 对给定值K 通过哈希函数H key 计算其哈希地址d H key 若哈希表中地址为d的位置没有记录 则查找失败 退出 如果ht d K 则查找成功 否则 按照解决冲突的方法重复计算处理冲突后的下一个地址di 直到哈希表的ht di 为空或ht di K 若ht di K 则查找成功 否则查找失败 9 4各种查找方法的比较 1