哈希表
给定一组元素的关键字hash[] = {78,90,66,70,155,82,123,231}，利用除留余数法和线性再探测散列法将元素存储再哈希表中，并查找给定的关键字，求平均查找长度。
分析：主要考察哈希表的构造和冲突解决办法
代码：
#include "pch.h" #include <iostream> #include<stdio.h> #include<stdlib.h> typedef int KeyType;// 关键字类型 typedef struct//元素类型定义 {KeyType key;//关键字int hi;//冲突次数 }DataType; typedef struct //哈希表类型定义 {DataType *data;int tablesize;//哈希表的长度int curSize;//表中关键字的个数 }HashTable; /*-----------函数申明-----------*/ void CreateHashTable(HashTable *H, int m, int p, int hash[], int n); int SearchHash(HashTable H, KeyType k); void DisplayHash(HashTable H, int m); void HashASL(HashTable H, int m); /*-----------主函数------------*/ int main() {int hash[] = { 78,90,66,70,155,82,123,231 };int m = 11;int p = 11, n = 8, pos;KeyType k;HashTable H;CreateHashTable(&H, m, p, hash, n);DisplayHash(H, m);k = 155;pos = SearchHash(H, k);printf("关键字%d在哈希表中的位置为：%dn", k, pos);HashASL(H, m);return 0; } /*----------函数定义------------*/ void CreateHashTable(HashTable *H, int m, int p, int hash[], int n) //创建一个空的Hash表，并处理冲突 {int i, sum, addr, di, k = 1;(*H).data = (DataType*)malloc(m * sizeof(DataType));if (!(*H).data)exit(-1);for (i = 0; i < m; i++)//初始化哈希表{(*H).data[i].key = -1;//关键字设置为-1(*H).data[i].hi= 0;// 冲突次数为0}for (i = 0; i < n; i++)//求哈希函数地址，并处理冲突{sum = 0;//冲突次数addr = hash[i] % p;//用除留余数法求哈希函数地址di = addr;if ((*H).data[addr].key==-1)//如果不冲突，直接存进去{(*H).data[addr].key = hash[i];(*H).data[addr].hi = 1;}else//使用线性探测在散列,一个一个找{do{di = (di + k) % m;sum += 1;} while ((*H).data[di].key!=-1);(*H).data[di].key = hash[i];(*H).data[di].hi = sum + 1;}}(*H).curSize = n;//关键字个数(*H).tablesize = m;//哈希表的长度 } int SearchHash(HashTable H, KeyType k) //在哈希表中查找关键字为k的元素 {int d, d1, m;m = H.tablesize;d = d1 = k % m;while (H.data[d].key!=-1)//遇到了空位，那肯定找不到{if (H.data[d].key == k)//找到了return d;else//由于可能存在冲突可能这个关键字没有存在这个地方{d = (d + 1) % m;//继续往后查找}if (d == d1)//找完了一圈所有的位置return 0;}return 0; } void HashASL(HashTable H, int m) //求平均查找长度 {float average = 0;int i;for (i = 0; i < m; i++){average = average + H.data[i].hi;}average /= H.curSize;printf("平均查找长度ASL=%2f", average); } void DisplayHash(HashTable H, int m) {int i;printf("哈希表地址：");for (i = 0; i < m; i++)printf("%-5d", i);printf("n");printf("关键字key: ");for (i = 0; i < m; i++){printf("%-5d", H.data[i].key);}printf("n");printf("冲突次数： ");for (i = 0; i < m; i++){printf("%-5d", H.data[i].hi);}printf("n"); }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139程序运行结果：
相关知识
哈希表
Java学习（86）Java集合——案例：宠物猫信息管理（HashSet增删改查）
嵌入式开发
区块链100讲：从宠物商店案例看DAPP架构和WEB3.JS交互接口
交互表
宠物档案表
大航海探险物语宠物配方表，怪物反向查询表
梦到表坏了是什么意思 梦见表坏了有什么预兆
食品营养成分表计算公式
宠物喂养记录表
网址: 哈希表 https://m.mcbbbk.com/newsview349173.html
| 上一篇: 跨境电商：亚马逊Prime Da |
下一篇: 为什么狗狗老是要人抱抱 |
