哈希表实验C语言版实现

代码如下:

/*
 数据结构C语言版 哈希表

*/
#include <stdio.h>
#include <malloc.h>
#define NULLKEY 0 // 0为无记录标志
#define N 10  // 数据元素个数
typedef int KeyType;// 设关键字域为整型
typedef struct
{
 KeyType key;
 int ord;
}ElemType; // 数据元素类型
// 开放定址哈希表的存储结构
int hashsize[]={11,19,29,37}; // 哈希表容量递增表,一个合适的素数序列
int m=0; // 哈希表表长,全局变量
typedef struct
{
 ElemType *elem; // 数据元素存储基址,动态分配数组
 int count; // 当前数据元素个数
 int sizeindex; // hashsize[sizeindex]为当前容量
}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
// 构造一个空的哈希表
int InitHashTable(HashTable *H)

 int i;
 (*H).count=0; // 当前元素个数为0
 (*H).sizeindex=0; // 初始存储容量为hashsize[0]
 m=hashsize[0];
 (*H).elem=(ElemType*)malloc(m*sizeof(ElemType));
 if(!(*H).elem)
  exit(0); // 存储分配失败
 for(i=0;i<m;i++)
  (*H).elem[i].key=NULLKEY; // 未填记录的标志

return 1;
}
//  销毁哈希表H
void DestroyHashTable(HashTable *H)
{
 free((*H).elem);
 (*H).elem=NULL;
 (*H).count=0;
 (*H).sizeindex=0;
}
// 一个简单的哈希函数(m为表长,全局变量)
unsigned Hash(KeyType K)
{
 return K%m;
}
// 开放定址法处理冲突
void collision(int *p,int d) // 线性探测再散列

 *p=(*p+d)%m;
}
// 算法9.17
// 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
// 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS
// c用以计冲突次数,其初值置零,供建表插入时参考。
int SearchHash(HashTable H,KeyType K,int *p,int *c)
{
 *p=Hash(K); // 求得哈希地址
 while(H.elem[*p].key!=NULLKEY&&!(K == H.elem[*p].key))
 {
  // 该位置中填有记录.并且关键字不相等
  (*c)++;
  if(*c<m)
   collision(p,*c); // 求得下一探查地址p
  else
   break;
 }
 if (K == H.elem[*p].key)
  return SUCCESS; // 查找成功,p返回待查数据元素位置
 else
  return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY),p返回的是插入位置
}
int InsertHash(HashTable *,ElemType); // 对函数的声明
// 重建哈希表
void RecreateHashTable(HashTable *H) // 重建哈希表
{
 int i,count=(*H).count;
 ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
 p=elem;
 printf("重建哈希表\n");
 for(i=0;i<m;i++) // 保存原有的数据到elem中
  if(((*H).elem+i)->key!=NULLKEY) // 该单元有数据
   *p++=*((*H).elem+i);
 (*H).count=0;
 (*H).sizeindex++; // 增大存储容量
 m=hashsize[(*H).sizeindex];
 p=(ElemType*)realloc((*H).elem,m*sizeof(ElemType));
 if(!p)
  exit(0); // 存储分配失败
 (*H).elem=p;
 for(i=0;i<m;i++)
  (*H).elem[i].key=NULLKEY; // 未填记录的标志(初始化)
 for(p=elem;p<elem+count;p++) // 将原有的数据按照新的表长插入到重建的哈希表中
  InsertHash(H,*p);
}
// 算法9.18
// 查找不成功时插入数据元素e到开放定址哈希表H中,并返回1;
// 若冲突次数过大,则重建哈希表。
int InsertHash(HashTable *H,ElemType e)
{
 int c,p;
 c=0;
 if(SearchHash(*H,e.key,&p,&c)) // 表中已有与e有相同关键字的元素
  return DUPLICATE;
 else if(c<hashsize[(*H).sizeindex]/2) // 冲突次数c未达到上限,(c的阀值可调)
 {
  // 插入e
  (*H).elem[p]=e;
  ++(*H).count;
  return 1;
 }
 else
  RecreateHashTable(H); // 重建哈希表

return 0;
}
// 按哈希地址的顺序遍历哈希表
void TraverseHash(HashTable H,void(*Vi)(int,ElemType))

 int i;
 printf("哈希地址0~%d\n",m-1);
 for(i=0;i<m;i++)
  if(H.elem[i].key!=NULLKEY) // 有数据
   Vi(i,H.elem[i]);
}
// 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
// 元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS
int Find(HashTable H,KeyType K,int *p)
{
 int c=0;
 *p=Hash(K); // 求得哈希地址
 while(H.elem[*p].key!=NULLKEY&&!(K == H.elem[*p].key))
 { // 该位置中填有记录.并且关键字不相等
  c++;
  if(c<m)
   collision(p,c); // 求得下一探查地址p
  else
   return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
 }
 if (K == H.elem[*p].key)
  return SUCCESS; // 查找成功,p返回待查数据元素位置
 else
  return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
void print(int p,ElemType r)
{
 printf("address=%d (%d,%d)\n",p,r.key,r.ord);
}
int main()
{
 ElemType r[N] = {
  {17,1},{60,2},{29,3},{38,4},{1,5},
  {2,6},{3,7},{4,8},{60,9},{13,10}
 };
 HashTable h;
 int i, j, p;
 KeyType k;

InitHashTable(&h);
 for(i=0;i<N-1;i++)
 {
  // 插入前N-1个记录
  j=InsertHash(&h,r[i]);
  if(j==DUPLICATE)
   printf("表中已有关键字为%d的记录,无法再插入记录(%d,%d)\n",
    r[i].key,r[i].key,r[i].ord);
 }
 printf("按哈希地址的顺序遍历哈希表:\n");
 TraverseHash(h,print);
 printf("请输入待查找记录的关键字: ");
 scanf("%d",&k);
 j=Find(h,k,&p);
 if(j==SUCCESS)
  print(p,h.elem[p]);
 else
  printf("没找到\n");
 j=InsertHash(&h,r[i]); // 插入第N个记录
 if(j==0) // 重建哈希表
  j=InsertHash(&h,r[i]); // 重建哈希表后重新插入第N个记录
 printf("按哈希地址的顺序遍历重建后的哈希表:\n");
 TraverseHash(h,print);
 printf("请输入待查找记录的关键字: ");
 scanf("%d",&k);
 j=Find(h,k,&p);
 if(j==SUCCESS)
  print(p,h.elem[p]);
 else
  printf("没找到\n");
 DestroyHashTable(&h);

system("pause");
 return 0;
}
/*
输出效果:
表中已有关键字为60的记录,无法再插入记录(60,9)
按哈希地址的顺序遍历哈希表:
哈希地址0~10
address=1 (1,5)
address=2 (2,6)
address=3 (3,7)
address=4 (4,8)
address=5 (60,2)
address=6 (17,1)
address=7 (29,3)
address=8 (38,4)
请输入待查找记录的关键字: 17
address=6 (17,1)
重建哈希表
按哈希地址的顺序遍历重建后的哈希表:
哈希地址0~18
address=0 (38,4)
address=1 (1,5)
address=2 (2,6)
address=3 (3,7)
address=4 (4,8)
address=6 (60,2)
address=10 (29,3)
address=13 (13,10)
address=17 (17,1)
请输入待查找记录的关键字: 13
address=13 (13,10)
请按任意键继续. . .
*/

(0)

相关推荐

  • C语言单循环链表的表示与实现实例详解

    1.概述: 对于一个循环链表来说,其首节点和末节点被连接在一起.这种方式在单向和双向链表中皆可实现.要转换一个循环链表,可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点.再来看另一种方法,循环链表可以被视为"无头无尾".这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下. 指向整个列表的指针可以被称作访问指针. 用单向链表构建的循环链表 循环链表中第一个节点之前就是最后一个节点,反之亦然.循环链表的无边界使得在这

  • c语言链表基本操作(带有创建链表 删除 打印 插入)

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define LEN sizeof(struct Student)struct Student{    long num;    float score;    struct Student*next;};int n;int main(){    /*-----------------------------程序描述----------

  • C语言单向链表的表示与实现实例详解

    1.概述: C语言中的单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始. 链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域.这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值. 如下图所示: 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 一个单向链表的节点被分成两个部分.第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址.单向链表只可向一个方向遍历. 链表最基本的结构是在每个节点

  • C语言运算符优先级列表(超详细)

    每当想找哪个运算符优先级高时,很多时候总是想找的就没有,真让人气愤!现在,终于有个我个人觉得非常全的,分享给大家,欢迎拍砖! C语言运算符优先级 优先级 运算符 名称或含义 使用形式 结合方向 说明 1 [] 数组下标 数组名[常量表达式] 左到右 -- () 圆括号 (表达式)/函数名(形参表) -- . 成员选择(对象) 对象.成员名 -- -> 成员选择(指针) 对象指针->成员名 -- 2 - 负号运算符 -表达式 右到左 单目运算符 ~ 按位取反运算符 ~表达式 ++ 自增运算符 +

  • C++如何实现广义表详解

    以下给出几种简单的广义表模型: 由上图我们可以看到,广义表的节点类型无非head.value.sub三种,这里设置枚举类型,利用枚举变量来记录每个节点的类型: enum Type { HEAD, //头节点 VALUE, //值节点 SUB, //子表节点 }; 每个节点都有自己的类型以及next指针,除此之外,如果该节点是VALUE类型还要分配空间存储该节点的有效值:但是若该节点是SUB类型,就需定义一个指针指向子表的头. 这里我们可以用联合来解决这个问题. (联合(或共同体)是一种不同数据类

  • C语言双向链表的表示与实现实例详解

    1.概述: C语言中一种更复杂的链表是"双向链表"或"双面链表".其表中的每个节点有两个连接:一个指向前一个节点,(当这个"连接"为第一个"连接"时,指向空值或者空列表):而另一个指向下一个节点,(当这个"连接"为最后一个"连接"时,指向空值或者空列表) 一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接 在一些低级语言中, XOR-linking 提供一种在双向链表中

  • 用C语言实现单链表的各种操作(一)

    最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的<数据结构>(C 语言版),中的例子和后面的习题进行改编的.首先,是单链表的各种实现,其中,包含了一些常考的知识点.例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现.下面这个是单链表的结构体的定义: 复制代码 代码如下: typedef struct LNode{ ElemType data; struct LNode *next;}LinkList; 下面的基本的单链表的操作:其

  • C语言实现带头结点的链表的创建、查找、插入、删除操作

    本文实例讲述了C语言实现带头结点的链表的创建.查找.插入.删除操作.是数据结构中链表部分的基础操作.分享给大家供大家参考.具体方法如下: #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next;// 这个地方注意结构体变量的定义规则 } Node, *PNode; Node* createLinklist(int length) { int i = 0; PNo

  • 哈希表实验C语言版实现

    复制代码 代码如下: /* 数据结构C语言版 哈希表 */#include <stdio.h>#include <malloc.h>#define NULLKEY 0 // 0为无记录标志 #define N 10  // 数据元素个数 typedef int KeyType;// 设关键字域为整型 typedef struct{ KeyType key; int ord;}ElemType; // 数据元素类型 // 开放定址哈希表的存储结构 int hashsize[]={11

  • C语言数据结构哈希表详解

    /* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其

  • C语言哈希表概念超详细讲解

    目录 1. 哈希概念 2. 哈希冲突 3. 哈希实现 3.1 闭散列(哈希表) 3.1.1 闭散列的细节 3.1.2 优化后的闭散列 3.2 扩散列(哈希桶) 3.2.1 扩散列的细节 4. 哈希表和哈希桶的比较 5. 结尾语 1. 哈希概念 哈希其实在学排序时已经用过了,就是计数排序.计数排序也是用的一种映射关系. 比如对此数组进行 计数排序 :1 1 9 9 9 3 3 8 8 我用的是绝对映射 ,所以开辟的数组空间 它的大小 必须 能映射到 最大的元素. 但是 对于哈希来讲,可以用决定映射

  • php内核解析:PHP中的哈希表

    PHP中使用最为频繁的数据类型非字符串和数组莫属,PHP比较容易上手也得益于非常灵活的数组类型. 在开始详细介绍这些数据类型之前有必要介绍一下哈希表(HashTable). 哈希表是PHP实现中尤为关键的数据结构. 哈希表在实践中使用的非常广泛,例如编译器通常会维护的一个符号表来保存标记,很多高级语言中也显式的支持哈希表. 哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,这些操作在最坏的情况下和链表的性能一样为O(n). 不过通常并不会这么坏,合理设计的哈希

  • Perl哈希表用法解析

    本文和大家重点讨论一下Perl哈希表的概念,Perl语言和其他编程语言各有各的特点,这里和大家分享一下Perl哈希表的概念,其实Perl哈希表是一种结构. Perl哈希表Perl哈希表是一种结构.key/value.访问Perl哈希表元素$Perl哈希表{$some_key}当给Perl哈希表选择名字时,最好这样思考:Perl哈希表元素的名字和key之间可以用for来连接.如thefamily_nameforfredisflintstone. 要引用整个Perl哈希表,使用百分号(%)作为前缀.

  • js实现HashTable(哈希表)的实例分析

    一.javascript哈希表简介 javascript里面是没有哈希表的,一直在java,C#中有时候用到了这一种数据结构,javascript里面若没有,感觉非常不顺手.细细看来,其实javascript的object的属性其实与哈希表非常类似. 如: var person = {}; person["name"] = "关羽"; 我们只需要在其基础上再封装一些HashTable的函数,就能够得到一个精简版的哈希表. 加入函数如下: 函数名 说明 返回值 add

  • socket多人聊天程序C语言版(二)

    socket多人聊天程序C语言版(一)地址: http://www.jb51.net/article/94938.htm 1V1实现了,1V多也就容易了.不过相对于1V1的程序,我经过大改,采用链表来动态管理.这样效率真的提升不少,至少CPU使用率稳稳的在20以下,不会飙到100了.用C语言写这个还是挺费时间的,因为什么功能函数都要自己写,不像C++有STL库可以用,MFC写就更简单了,接下来我还会更新MFC版本的多人聊天程序.好了,废话少说,进入主题. 这个程序要解决的问题如下: 1.CPU使

  • PHP内核探索:哈希表碰撞攻击原理

    下面通过图文并茂的方式给大家展示PHP内核探索:哈希表碰撞攻击原理. 最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招.本文结合PHP内核源码,聊一聊这种攻击的原理及实现.  哈希表碰撞攻击的基本原理 哈希表是一种查找效率极高的数据结构,很多语言都在内部实现了哈希表.PHP中的哈希表是一种极为重要的数据结构,不但用于表示Array数据类型,还在Zend虚拟机内部用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结

  • 探索PowerShell (八) 数组、哈希表(附:复制粘贴技巧)

    我们经常在程序设计中用到的数组,同样在脚本中很常用.本节就详细介绍一下数组,以及哈希表在PowerShell中的使用. 数组 在PowerShell中,声明一个变量为数组时,需要使用符号"@",例如: $strUsers=@(""user1","user2","user3) <enter> 这样,我们就声明了一个具有3个成员的数组.查看它的值,使用: $strUsers <enter> 还有一些其他的操

  • C语言版扫雷游戏

    本文实例为大家分享了C语言版扫雷游戏的具体代码,供大家参考,具体内容如下 1.思路 一.创建二维数组,来表示地图 每一个格子要表示的信息: 1.未翻开状态(草地)和已翻开状态(数字) 2.该格子是地雷或者不是地雷(1表示是地雷,0表示不是) 二.使用两个二维数组来分别表示以上的两种状态 第一个二维数组 char showMap[9][9];表示每个格子的翻开和未翻开状态 表示未翻开,字符'0'-'8'表示已翻开的数字 第二个二维数组 char mineMap[9][9];表示每个格子是否是地雷

随机推荐