Chinaunix首页 | 论坛 | 博客
  • 博客访问: 387197
  • 博文数量: 109
  • 博客积分: 1463
  • 博客等级: 上尉
  • 技术积分: 859
  • 用 户 组: 普通用户
  • 注册时间: 2011-07-22 13:21
个人简介

希望和广大热爱技术的童鞋一起交流,成长。

文章分类

全部博文(109)

文章存档

2017年(1)

2016年(2)

2015年(18)

2014年(1)

2013年(9)

2012年(15)

2011年(63)

分类: C/C++

2011-09-08 16:28:27

    建表时首先要将表中各结点的关键字清空,使其地址为开放的。然后调用调入算法将给定的关键字序列依次插入表中。
    插入算法首先调用查找算法。若在表中找到待插入的关键字或表已满,则插入失败。若在表中找到一个开放地址,则将待插入的结点插入其中,即插入成功。
代码:
 
  1. #include "stdio.h"
  2. #define NIL -1 //空结点标记
  3. #define M 997  //表长度,一般表长度为素数
  4. typedef int KeyType;
  5. typedef struct node  //散列表结点类型
  6. {
  7.     KeyType key;
  8. }HashType;

  9. //用除余法求K的散列地址的函数h
  10. int h(KeyType K)
  11. {
  12.     return K%M}
  13. //求增量序列的函数,它依赖于解决冲突的方法
  14. int Increment(int i)  //用线性探查法求第i个增量di
  15. {
  16.     return i;  //若用二次探查法,则返回i*i
  17. }
  18. //求在散列表T[0...M-1]中第i次探查的散列地址hi,0<=i<=M-1
  19. int Hash(KeyType k,int i)
  20. {
  21.     return (h(k)+Increment(i))%M;
  22. }

  23. int HashSearch(HashType T[],KeyType K,int *pos)
  24. {
  25.     int i=0; //记录探查次数
  26.     do
  27.     {
  28.         *pos=Hash(K,i);
  29.         if(T[*pos].key == K) return 1;  //查找成功返回1
  30.         if(T[*pos].key == NIL) return 0;  //找到一个空地址即开放地址返回0
  31.     }while(++i<M); //最多做M次探查
  32.     return -1; //表满未找到返回-1
  33. }
  34. //将新结点newnode插入散列表中
  35. void HashInsert(HashType T[],HashType newnode)
  36. {
  37.     int pos,sign;
  38.     sign=HashSearch(T,newnode.key,&pos);
  39.     if(!sign)
  40.         T[pos]=newnode;   //找到一个开放地址即插入
  41.     else
  42.     {
  43.         if(sign>0)
  44.             printf("重复的关键字!");
  45.         else
  46.         {
  47.             printf("表满错误,终止程序执行!");
  48.             exit(0);
  49.         }
  50.             
  51.     }
  52. }

  53. void CreateHashTable(HashType T[],HashType A[],int n)
  54. {
  55.     int i;
  56.     if(n>M)   //用开放地址法处理冲突时,装填因子a须不大于1,一般为0.6-0.9
  57.     {
  58.         printf("装填因子a须不大于1");
  59.         exit(0);
  60.     }
  61.     for(i=0;i<M;i++)
  62.     {
  63.         T[i].key=NIL;   //将各关键字清空,使地址i为开放地址
  64.         for(i=0;i<n;i++)
  65.         {
  66.             HashInsert(T,A[i]);
  67.         }
  68.     }
  69. }
阅读(1215) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册