郴州市网站建设科技,杭州做代发的网站有哪些,网站建设j介绍ppt模板,大连seo皮皮代码下载链接#xff1a;https://gitee.com/flying-wolf-loves-learning/data-structure.git
目录
一、查找的原理
1.1 查找概念
1.2 查找方法
1.3平均查找长度
1.4顺序表的查找
1.5 顺序表的查找算法及分析
1.6 折半查找算法及分析
1.7 分块查找算法及分析
1.8 总结…代码下载链接https://gitee.com/flying-wolf-loves-learning/data-structure.git
目录
一、查找的原理
1.1 查找概念
1.2 查找方法
1.3平均查找长度
1.4顺序表的查找
1.5 顺序表的查找算法及分析
1.6 折半查找算法及分析
1.7 分块查找算法及分析
1.8 总结
二、hash表原理
2.1 Hash表的查找
2.2 保留除数法
2.3 处理冲突的方法
2.3 开放地址法
2.4 链地址法
hash表的实现
创建
插入和查找 一、查找的原理 1.1 查找概念 设记录表L(R1 R2……Rn)其中Ri(l≤i≤n)为记录对给定的某个值k在表L中确定keyk的记录的过程称为查找。若表L中存在一个记录Ri的keyk记为Ri.keyk则查找成功返回该记录在表L中的序号i(或Ri 的地址)否则(查找失败)返回0(或空地址Null)。 1.2 查找方法 查找方法有顺序查找、折半查找、分块查找、Hash表查找等等。查找算法的优劣将影响到计算机的使用效率应根据应用场合选择相应的查找算法。 1.3平均查找长度 对查找算法主要分析其T(n)。查找过程是key的比较过程时间主要耗费在各记录的key与给定k值的比较上。比较次数越多算法效率越差即T(n)量级越高故用“比较次数”刻画算法的T(n)。 一般以“平均查找长度”来衡量T(n)。 平均查找长度ASLAverage Search Length对给定k查找表L中记录比较次数的期望值(或平均值)即 1-1 为查找的概率。等概率情况下为查找时key的比较次数(或查找次数)。 1.4顺序表的查找 顺序表是将表中记录……按其序号存储于一维数组空间 记录的类型描述如下 typedef struct { keytype key; //记录key …… //记录其他项 } Retype; 顺序表类型描述如下: #define maxn 1024 //表最大长度 typedef struct { Retype data[maxn]; //顺序表空间 int len; //当前表长表空时len0 } sqlist; 若说明sqlist r则r.data[1]……r.data[r.len]为记录表(R1……Rn) Ri.key为r.data[i].key, r.data[0]称为监视哨为算法设计方便所设。 1.5 顺序表的查找算法及分析 算法思路 设给定值为k在表(R1 R2……Rn)中从Rn开始查找keyk的记录。 int sqsearch(sqlist r, keytype k) { int i; r.data[0].key k; //k存入监视哨 i r.len; //取表长 while(r.data[i].key ! k) i--; return (i); } 设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数) 若r.data[n].key k Cn1 若r.data[n-1].key k Cn-12 …… 若r.data[i].key k Cin-i1 …… 若r.data[1].key k C1n 故ASL O(n)。而查找失败时查找次数等于nl同样为O(n)。对查找算法若ASLO(n)则效率是很低的意味着查找某记录几乎要扫描整个表当表长n很大时会令人无法忍受。 1.6 折半查找算法及分析 算法思路 对给定值k逐步确定待查记录所在区间每次将搜索空间减少一半(折半)直到查找成功或失败为止。 设两个游标low、high分别指向当前待查找表的上界(表头)和下界(表尾)。mid指向中间元素。 图片来源于makeru.com 图片来源于makeru.com 具体代码如下: int Binsearch(sqlist r, keytype k) //对有序表r折半查找的算法
{ int low, high, mid; low 1;high r.len; while (low high) { mid (lowhigh) / 2; if (k r.data[mid].key) return (mid); if (k r.data[mid].key) high mid-1; else low mid1;} return(0);} 不失一般性设表长n2h-lhlog2(n1)。记录数n恰为一棵h层的满二叉树的结点数。得出表的判定树及各记录的查找次数如图所示。 图片来源于makeru.com 1.7 分块查找算法及分析 分块 设记录表长为n将表的n个记录分成 个块每块s个记录最后一块记录数可以少于s个即 图片来源于makeru.com 且表分块有序即第i1≤i≤b-1块所有记录的key小于第i1块中记录的key但块内记录可以无序。 建立索引每块对应一索引项其中kmax为该块内记录的最大keylink为该块第一记录的序号或指针。 图片来源于makeru.com 1.8 总结 顺序、折半、分块查找和树表的查找中其ASL的量级在O(n)O(log2n)之间。不论ASL在哪个量级都与记录长度n有关。随着n的扩大算法的效率会越来越低。ASL与n有关是因为记录在存储器中的存放是随机的或者说记录的key与记录的存放地址无关因而查找只能建立在key的“比较”基础上。 二、Hash表原理 2.1 Hash表的查找 理想的查找方法是对给定的k不经任何比较便能获取所需的记录其查找的时间复杂度为常数级O(C)。 这就要求在建立记录表的时候确定记录的key与其存储地址之间的关系f即使key与记录的存放地址H相对应 当要查找keyk的记录时通过关系f就可得到相应记录的地址而获取记录从而免去了key的比较过程。 这个关系f就是所谓的Hash函数或称散列函数、杂凑函数记为H(key)。 它实际上是一个地址映象函数其自变量为记录的key函数值为记录的存储地址或称Hash地址。 不同的key可能得到同一个Hash地址即当keyl≠key2时可能有H(key1)H(key2)此时称key1和key2为同义词。这种现象称为“冲突”或“碰撞”因为一个数据单位只可存放一条记录。一般选取Hash函数只能做到使冲突尽可能少却不能完全避免。这就要求在出现冲突之后寻求适当的方法来解决冲突记录的存放问题。 根据选取的Hash函数H(key)和处理冲突的方法将一组记录(R1 R2……Rn)映象到记录的存储空间所得到的记录表称为Hash表如图 图片来源于makeru.com 选取或构造Hash函数的方法很多原则是尽可能将记录均匀分布以减少冲突现象的发生。以下介绍几种常用的构造方法。 直接地址法平方取中法叠加法保留除数法随机函数法 2.2 保留除数法 又称质数除余法设Hash表空间长度为m选取一个不大于m的最大质数p令 H(key)key%p。 设记录的key集合k{28356377105……}若选取p213*7包括质数因子7有 key28 35 63 77 105 …… H(key)key%21 7 14 0 14 0 …… 使得包含质数因子7的key都可能被映象到相同的单元冲突现象严重。 若取pl9质数同样对上面给定的key集合k有 key28 35 63 77 105 H(key)key%19 9 16 6 1 10 H(key)的随机度就好多了。 2.3 处理冲突的方法 选取随机度好的Hash函数可使冲突减少一般来讲不能完全避免冲突。设Hash表地址空间为0m-l表长为m 图片来源于makeru.com 冲突是指表中某地址j∈[0m-1]中己存放有记录而另一个记录的H(key)值也为j。 处理冲突的方法一般为在地址j的前面或后面找一个空闲单元存放冲突的记录或将相冲突的诸记录拉成链表。在处理冲突的过程中可能发生一连串的冲突现象即可能得到一个地址序列H1、H2……HnHi∈[0m-l]。H1是冲突时选取的下一地址而H1中可能己有记录又设法得到下一地址H2……直到某个Hn不发生冲突为止。这种现象称为“聚积”它严重影响了Hash表的查找效率。冲突现象的发生有时并不完全是由于Hash函数的随机性不好引起的聚积的发生也会加重冲突。还有一个因素是表的装填因子ααn/m其中m为表长n为表中记录个数。一般α在0.70.8之间使表保持一定的空闲余量以减少冲突和聚积现象。 2.3 开放地址法 当发生冲突时在H(key)的前后找一个空闲单元来存放冲突的记录即在H(key)的基础上获取下一地址 Hi(H(key)di)%m 其中m为表长%运算是保证Hi落在[0m-l]区间 di为地址增量。di的取法有多种 1di123……(m-1)——称为线性探查法 2di12-1222-22……——称为二次探查法。 设记录的key集合k{2334143846166815073126}记录数n11。 令装填因子α0.75取表长m én/αù 15。 用“保留余数法”选取Hash函数p13 H(key)key%13 图片来源于makeru.com 2.4 链地址法 发生冲突时将各冲突记录链在一起即同义词的记录存于同一链表。 设H(key)取值范围值域为[0m-l] 建立头指针向量HP[m] HP[i]0≤i≤m-l初值为空。 设H(key)key%13 k{ 2334143846 166815073126 } 图片来源于makeru.com 链地址法解决冲突的优点无聚积现象删除表中记录容易实现。 三、Hash表的实现 3.1 创建
// 定义一个名为hash_create的函数它返回一个指向hash结构体的指针
hash *hash_create(){ // 声明一个名为HT的指针用于指向新创建的hash结构体 hash * HT; // 使用malloc函数为hash结构体分配内存并将返回的地址赋值给HT // 这里的(hash *)是强制类型转换确保malloc返回的void*被正确转换为hash* if((HT (hash *)malloc(sizeof(hash))) NULL){ // 如果内存分配失败即malloc返回NULL则打印错误信息 printf(malloc failed!\n); // 并返回NULL表示创建失败 return NULL; } // 使用memset函数将HT指向的内存区域初始化为0 // 这通常是为了确保hash结构体中的所有成员都被正确地初始化为默认值对于整数和指针通常是0 memset(HT, 0, sizeof(hash)); // 返回新创建的并已经初始化的hash结构体的地址 return HT;
}
3.2 插入和查找
插入
// 假设datatype是键的数据类型hash是哈希表结构体的指针linklist是链表节点的指针类型
// listnode是链表节点的结构体类型HT-data是哈希表存储的链表数组N是哈希表的大小 int hash_insert(hash *HT, datatype key){ // 检查哈希表是否为空 if(HT NULL){ printf(HT is NULL\n); return -1; // 返回-1表示哈希表为空插入失败 } // 声明两个链表节点的指针p用于新节点q用于遍历链表 linklist p, q; // 为新节点分配内存 if((p (linklist)malloc(sizeof(listnode))) NULL){ printf(malloc failed!\n); return -1; // 返回-1表示内存分配失败 } // 初始化新节点的key和value这里value被简单设置为key对N取模的值可能是哈希值或链表索引 p-key key; p-value key % N; // 注意这里的value可能不是真正的值而是用于链表排序或索引的 p-next NULL; // 初始化新节点的next指针为NULL // 计算哈希值确定在哈希表的哪个位置插入新节点 // 假设HT-data是一个链表数组其索引由key % N确定 q HT-data[key % N]; // q指向对应链表的头部 // 遍历链表找到新节点应该插入的位置保持链表有序或按某种规则插入 // 这里假设链表是按键值key升序排列的 while(q-next q-next-key p-key){ q q-next; // q向后移动直到找到空位置或遇到比p-key大的节点 } // 将新节点p插入到链表中的正确位置 p-next q-next; // 新节点的next指向q原本指向的下一个节点 q-next p; // q的next指向新节点p // 插入成功返回0 return 0;
}
查找
linklist hash_search(hash *HT, datatype key){ // 检查哈希表是否为空 if(HT NULL){ printf(HT is NULL\n); return NULL; // 如果哈希表为空则返回NULL } // 声明链表节点的指针p用于遍历链表 linklist p; // 计算哈希值确定在哈希表的哪个位置查找 p HT-data[key % N]; // p指向对应链表的头部 // 遍历链表查找具有给定key的节点 while(p-next p-next-key ! key){ p p-next; // 如果当前节点的下一个节点存在且key不匹配则移动到下一个节点 } // 检查是否找到了匹配的节点 if(p-next NULL){ // 如果没有找到即p-next为NULL则返回NULL return NULL; } else{ // 如果找到了打印一条消息 printf(found!\n); } // 返回找到的节点的指针注意是p-next因为p指向的是链表头部的指针 return p-next;
}
