Chinaunix首页 | 论坛 | 博客

遇见0425的ChinaUnix博客

首页　| 　博文目录　| 　关于我

遇见0425

  • 博客访问： 153194
  • 博文数量： 36
  • 博客积分： 802
  • 博客等级： 准尉
  • 技术积分： 717
  • 用 户 组： 普通用户
  • 注册时间： 2012-06-02 22:47
文章分类

全部博文（36）

文章存档

2012年（36）

我的朋友
最近访客
推荐博文
相关博文
关于散列函数的两种实现

分类： C/C++

2012-09-10 10:41:17

散列表：理想的散列表数据结构不过是一个包含有关键字的具有固定大小的数组，我们把表的大小记做TableSize，并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量。
散列函数：每个关键字被映射到0～Tablesize这个范围中的某个数，并且被放在适当的单元中，这个映射就叫做散列函数。

------我们必须选择一个函数，决定当两个关键字散列到同一个值的时候，应该如何处理。

处理这种冲突最简单的两种方法：分离链接法和开放定址法

一：分离链接法
做法是将散列到同一个值的所有元素保存到一个表中。
首先我们得定义：

  

点击(此处)折叠或打

  1. typedef struct LinkNode
  2.   {
  3.    int elem;
  4.    struct LinkNode *next
  5.   }*List;// 这个结构体记录了取这个值的所有数所在的链表

  7. typedef struct HashTbl
  8.  {
  9.    int Tablesize;
  10.    List *TheList;//指针的指针，指向每一个值的链表
  11.  }*HashTable;
然后我们实现这个表的初始化函数

点击(此处)折叠或打开

  1. HashTable Init(int Size)
  2.   {
  3.   HashTable H;
  4.   int i;
  5.   if(Tablesize<MinSize)
  6.   {
  7.    perror("Out of space!\n");
  8.    return NULL;
  9.    }
  10.   H=(HashTable)malloc(sizeof(struct HashTbl));
  11.   if(H==NULL)
  12.   perror("Out of space!\n");
  13.   H->Tablesize=Size;
  14.   H->TheList=(List)malloc(sizeof(struct LinkNode)*Size);
  15.   if(H->TheList==NULL)
  16.      perror("Out of space!\n");
  17.   for(i=0;i<H->Tablesize;i++)
  18.   {
  19.      H->TheList[i]=(List)malloc(sizeof(LinkNOde));
  20.      if(H->TheList=[i]==NULL)
  21.           perror("Out of space!\n");
  22.      else
  23.           H->TheList[i]->next=NULL;
  24.   }
  25.   return H;
  26.   }
这个是寻找key这个元素位置的一个函数，返回值是行

点击(此处)折叠或打开

  1. struct ListNode Find(int key,HashTable H)
  2.     {
  3.     struct Node *p;
  4.     List L;
  5.     L=H->TheList(Hash(key,H->Tablesize));
  6.     p=L->next;
  7.     while(p!=NULL&&p->elem!=key)
  8.     p=p->next;
  9.     return p;
  10. }
接着是我门的插入函数

点击(此处)折叠或打开

  1. void Insert(int key,HashTable H)
  2.    {
  3.     List Pos,NewCell;
  4.    List L;
  5.    Pos=Find(key,H);
  6.    if(Pos==NULL)
  7.   {
  8.    NewCell=malloc(sizeof(struct ListNode));
  9.    if(NewCell==NULL)
  10.   perror("Out of space!\n");
  11.   else
  12.   {
  13.    NewCell->elem=key;
  14.   L=H->TheList(Hash(key,H->Tablesize));
  15.    NewCell->next=L->next;
  16.    L->next=NewCell;
  17.    }
  18.   }
  19.   }
我们给出分离链接法的全部代码


点击(此处)折叠或打开

  1. 1. #include<stdio.h>
  2.    2. #include<stdlib.h>
  3.    3.

  5.    4. #define MinTablesize 10
  6.    5. #define Size 15
  7.    6.

  9.    7. typedef struct ListNode
  10.    8. {
  11.    9. int elem;
  12.   10. struct ListNode *next;
  13.   11. }*List;
  14.   12.

  16.   13. typedef struct HashTbl
  17.   14. {
  18.   15. int Tablesize;
  19.   16. List *TheList;
  20.   17. }*HashTable;
  21.   18. HashTable InitializeTable(int Tablesize)
  22.   19. {
  23.   20. HashTable H;
  24.   21. int i;
  25.   22. if(Tablesize<MinTablesize)
  26.   23. {
  27.   24. perror("ERROR!\n");
  28.   25. return NULL;
  29.   26. }
  30.   27.

  32.   28. H=(HashTable)malloc(sizeof(struct HashTbl));
  33.   29. if(H==NULL)
  34.   30. perror("Out of space!\n");
  35.   31. H->Tablesize=Size;
  36.   32.

  38.   33. H->TheList=malloc(H->Tablesize*sizeof(struct ListNode));
  39.   34. if(H->TheList==NULL)
  40.   35. perror("Out of space!\n");
  41.   36.

  43.   37. for(i=0;i<H->Tablesize;i++)
  44.   38. {
  45.   39. H->TheList[i]=malloc(sizeof(struct ListNode));
  46.   40. if(H->TheList[i]==NULL)
  47.   41. perror("Out of space!\n");
  48.   42. else
  49.   43. H->TheList[i]->next=NULL;
  50.   44. }
  51.   45. return H;
  52.   46. }
  53.   47.

  55.   48. int Hash(int key,int x)
  56.   49. {
  57.   50. int i;
  58.   51. i=key%x;
  59.   52. return i;
  60.   53. }
  61.   54. struct ListNode *Find(int key,HashTable H)
  62.   55. {
  63.   56. struct ListNode *P;
  64.   57. List L;
  65.   58.

  67.   59. L=H->TheList[Hash(key,H->Tablesize)];
  68.   60. P=L->next;
  69.   61. while(P!=NULL&&P->elem!=key)
  70.   62. P=P->next;
  71.   63. return P;
  72.   64. }
  73.   65. void Insert(int key,HashTable H)
  74.   66. {
  75.   67. struct ListNode *Pos,*NewCell;
  76.   68. List L;
  77.   69. Pos=Find(key,H);
  78.   70. if(Pos==NULL)
  79.   71. {
  80.   72. NewCell=(List)malloc(sizeof(struct ListNode));
  81.   73. if(NewCell==NULL)
  82.   74. perror("Out of space!!!\n");
  83.   75. else
  84.   76. {
  85.   77. NewCell->elem=key;
  86.   78. L=H->TheList[Hash(key,H->Tablesize)];
  87.   79. NewCell->next=L->next;
  88.   80. L->next=NewCell;
  89.   81. }
  90.   82. }
  91.   83.

  93.   84. }
  94.   85.

  96.   86. void Print(HashTable H)
  97.   87. {
  98.   88. int i;
  99.   89. struct ListNode *p;
  100.   90. for(i=0;i<15;i++)
  101.   91. { printf("第%d组的成员有：\n",i);
  102.   92. p=H->TheList[i]->next;
  103.   93. while(p)
  104.   94. {
  105.   95. printf("%d ",p->elem);
  106.   96. p=p->next;
  107.   97. }
  108.   98. printf("\n");
  109.   99. }
  110.  100.

  112.  101. }
  113.  102. int main()
  114.  103. {
  115.  104. HashTable H;
  116.  105. int i;
  117.  106. int key;
  118.  107. int a[15];
  119.  108. List t,p;
  120.  109. H=InitializeTable(Size);
  121.  110. printf("please input number into Hash:");
  122.  111. for(i=0;i<15;i++)
  123.  112. scanf("%d",&a[i]);
  124.  113. for(i=0;i<Size;i++)
  125.  114. Insert(a[i],H);
  126.  115. Print(H);
  127.  116. key=2;
  128.  117. printf("please find %d\n",key);
  129.  118. t=Find(key,H);
  130.  119. if(t->elem==key)
  131.  120. printf("I can find %d\n",t->elem);
  132.  121. else
  133.  122. printf("I can not find the key!!!\n");
  134.  123.
  135.  124.

  137.  125. }
二：开放定址法
1：线性探测法
这个方法就是如果要插入的位置被占用，则往后退一个位置，直到找到位置可插入为止
2：平方探测法
这个方法就是分别取1平方，2平方，依次往下
下面给出这个方法的全部代码

 

点击(此处)折叠或打开

  1. 1. #include<stdio.h>
  2.    2. #include<stdlib.h>
  3.    3.

  5.    4. #define Size 50
  6.    5. #define MinSize 9
  7.    6.

  9.    7. enum KindofEntry
  10.    8. {
  11.    9. Legitimate,Empty,Deleted
  12.   10. };
  13.   11. struct HashEntry
  14.   12. {
  15.   13. int elem;
  16.   14. enum KindofEntry Info;
  17.   15. };
  18.   16.

  20.   17. typedef struct HashEntry Cell;
  21.   18.

  23.   19. struct HashTbl
  24.   20. {
  25.   21. int Tablesize;
  26.   22. Cell *Thecells;
  27.   23. };
  28.   24.

  30.   25. typedef struct HashTbl *HashTable;
  31.   26.

  33.   27. HashTable InitializeTable(int Tablesize)
  34.   28. {
  35.   29. HashTable H;
  36.   30. int i;
  37.   31. if(Size<MinSize)
  38.   32. {
  39.   33. perror("Table size too small!\n");
  40.   34. return NULL;
  41.   35. }
  42.   36. H=(HashTable)malloc(sizeof(struct HashTbl));
  43.   37. if(H==NULL)
  44.   38. printf("Out of space!\n");
  45.   39. H->Tablesize=Size;
  46.   40. H->Thecells=(Cell *)malloc(sizeof(Cell)*H->Tablesize);
  47.   41. if(H->Thecells==NULL)
  48.   42. perror("Out of space!\n");
  49.   43. for(i=0;i<Size;i++)
  50.   44. {
  51.   45. H->Thecells[i].Info=Empty;
  52.   46. H->Thecells[i].elem=0;
  53.   47. }
  54.   48. return H;
  55.   49. }
  56.   50. int Hash(int key,int x)
  57.   51. {
  58.   52. int i;
  59.   53. i=key%x;
  60.   54. return i;
  61.   55. }
  62.   56.

  64.   57. unsigned int Find(int key,HashTable H)
  65.   58. {
  66.   59. unsigned int Pos;
  67.   60. int Num;
  68.   61. Num=0;
  69.   62. Pos=Hash(key,H->Tablesize);
  70.   63. while((H->Thecells[Pos].Info!=Empty)&&(H->Thecells[Pos].elem!=key))
  71.   64. {
  72.   65. Pos+=2*++Num-1;
  73.   66. if(Pos>H->Tablesize)
  74.   67. Pos-=Size;
  75.   68. }
  76.   69. return Pos;
  77.   70. }
  78.   71.

  80.   72. void Insert(int key,HashTable H)
  81.   73. {
  82.   74. unsigned Pos;
  83.   75. Pos=Find(key,H);
  84.   76. if(H->Thecells[Pos].Info!=Legitimate)
  85.   77. {
  86.   78. H->Thecells[Pos].Info=Legitimate;
  87.   79. H->Thecells[Pos].elem=key;
  88.   80. }
  89.   81. }
  90.   82.

  92.   83. void Print(HashTable H,int data[])
  93.   84. {
  94.   85. int b=0;
  95.   86. unsigned int m;
  96.   87. for(b=0;b<15;b++)
  97.   88. {
  98.   89. m=Find(data[b],H);
  99.   90. printf("%d在第%d行\n",data[b],m);
  100.   91. }
  101.   92. }
  102.   93.

  104.   94. int main()
  105.   95. {
  106.   96. int i;
  107.   97. int data[15];
  108.   98. HashTable H;
  109.   99. H=InitializeTable(Size);
  110.  100. printf("请输入要插入哈西表的元素:\n");
  111.  101. for(i=0;i<15;i++)
  112.  102. scanf("%d",&data[i]);
  113.  103. printf("插入之后的哈西表为：\n");
  114.  104. for(i=0;i<15;i++)
  115.  105. Insert(data[i],H);
  116.  106. Print(H,data);
  117.  107.

  119.  108. }
三：再散列法
这个方法是当表填写过于满的时候，我们重新建立一个表。
eg：将13，15，24，6插入一个大小为7的开放定址散列表中，如果再插入23，则这个表就会有超过%70的空间被填满，所以我们再创建一个新表，新表的大小为17（因为2*7是14，而17是大于7的二倍之后第一个素数），然后再进行插入操作
这个再散列方法比较简单：
再散列可以永平方探测以多种方式实现：
1）只要表填满一半就开是再散列
2）只有当插入失败再散列
3）当表达到一定的装填因子的时候再散列

点击(此处)折叠或打开

  1. HashTable Rehash(HashTable H)
  2.    {
  3.    int i,oldsize;
  4.    Cell *OldCells;

  6.    oldsize=H->Tablesize;
  7.    OldCells=H->TheCells;

  9.    H=InitializeTable(2*oldsize)；

  11.    for(i=0;i<oldsize;i++)
  12.   if(OldCell[i].Info==Legitimate)
  13.   Insert(OldCells[i].elem,H);
  14.   free(OldCells);
  15.    return H;
  16.   }

阅读(1677) | 评论(0) | 转发(1) |
0

上一篇：平衡二叉树

下一篇：内部排序之---插入类排序

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6