散列表:理想的散列表数据结构不过是一个包含有关键字的具有固定大小的数组,我们把表的大小记做TableSize,并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量。
散列函数:每个关键字被映射到0~Tablesize这个范围中的某个数,并且被放在适当的单元中,这个映射就叫做散列函数。
------我们必须选择一个函数,决定当两个关键字散列到同一个值的时候,应该如何处理。
处理这种冲突最简单的两种方法:分离链接法和开放定址法
一:分离链接法
做法是将散列到同一个值的所有元素保存到一个表中。
首先我们得定义:
- typedef struct LinkNode
- {
- int elem;
- struct LinkNode *next
- }*List;// 这个结构体记录了取这个值的所有数所在的链表
- typedef struct HashTbl
- {
- int Tablesize;
- List *TheList;//指针的指针,指向每一个值的链表
- }*HashTable;
然后我们实现这个表的初始化函数
- HashTable Init(int Size)
- {
- HashTable H;
- int i;
- if(Tablesize<MinSize)
- {
- perror("Out of space!\n");
- return NULL;
- }
- H=(HashTable)malloc(sizeof(struct HashTbl));
- if(H==NULL)
- perror("Out of space!\n");
- H->Tablesize=Size;
- H->TheList=(List)malloc(sizeof(struct LinkNode)*Size);
- if(H->TheList==NULL)
- perror("Out of space!\n");
- for(i=0;i<H->Tablesize;i++)
- {
- H->TheList[i]=(List)malloc(sizeof(LinkNOde));
- if(H->TheList=[i]==NULL)
- perror("Out of space!\n");
- else
- H->TheList[i]->next=NULL;
- }
- return H;
- }
这个是寻找key这个元素位置的一个函数,返回值是行
- struct ListNode Find(int key,HashTable H)
- {
- struct Node *p;
- List L;
- L=H->TheList(Hash(key,H->Tablesize));
- p=L->next;
- while(p!=NULL&&p->elem!=key)
- p=p->next;
- return p;
- }
接着是我门的插入函数
- void Insert(int key,HashTable H)
- {
- List Pos,NewCell;
- List L;
- Pos=Find(key,H);
- if(Pos==NULL)
- {
- NewCell=malloc(sizeof(struct ListNode));
- if(NewCell==NULL)
- perror("Out of space!\n");
- else
- {
- NewCell->elem=key;
- L=H->TheList(Hash(key,H->Tablesize));
- NewCell->next=L->next;
- L->next=NewCell;
- }
- }
- }
我们给出分离链接法的全部代码
- 1. #include<stdio.h>
- 2. #include<stdlib.h>
- 3.
- 4. #define MinTablesize 10
- 5. #define Size 15
- 6.
- 7. typedef struct ListNode
- 8. {
- 9. int elem;
- 10. struct ListNode *next;
- 11. }*List;
- 12.
- 13. typedef struct HashTbl
- 14. {
- 15. int Tablesize;
- 16. List *TheList;
- 17. }*HashTable;
- 18. HashTable InitializeTable(int Tablesize)
- 19. {
- 20. HashTable H;
- 21. int i;
- 22. if(Tablesize<MinTablesize)
- 23. {
- 24. perror("ERROR!\n");
- 25. return NULL;
- 26. }
- 27.
- 28. H=(HashTable)malloc(sizeof(struct HashTbl));
- 29. if(H==NULL)
- 30. perror("Out of space!\n");
- 31. H->Tablesize=Size;
- 32.
- 33. H->TheList=malloc(H->Tablesize*sizeof(struct ListNode));
- 34. if(H->TheList==NULL)
- 35. perror("Out of space!\n");
- 36.
- 37. for(i=0;i<H->Tablesize;i++)
- 38. {
- 39. H->TheList[i]=malloc(sizeof(struct ListNode));
- 40. if(H->TheList[i]==NULL)
- 41. perror("Out of space!\n");
- 42. else
- 43. H->TheList[i]->next=NULL;
- 44. }
- 45. return H;
- 46. }
- 47.
- 48. int Hash(int key,int x)
- 49. {
- 50. int i;
- 51. i=key%x;
- 52. return i;
- 53. }
- 54. struct ListNode *Find(int key,HashTable H)
- 55. {
- 56. struct ListNode *P;
- 57. List L;
- 58.
- 59. L=H->TheList[Hash(key,H->Tablesize)];
- 60. P=L->next;
- 61. while(P!=NULL&&P->elem!=key)
- 62. P=P->next;
- 63. return P;
- 64. }
- 65. void Insert(int key,HashTable H)
- 66. {
- 67. struct ListNode *Pos,*NewCell;
- 68. List L;
- 69. Pos=Find(key,H);
- 70. if(Pos==NULL)
- 71. {
- 72. NewCell=(List)malloc(sizeof(struct ListNode));
- 73. if(NewCell==NULL)
- 74. perror("Out of space!!!\n");
- 75. else
- 76. {
- 77. NewCell->elem=key;
- 78. L=H->TheList[Hash(key,H->Tablesize)];
- 79. NewCell->next=L->next;
- 80. L->next=NewCell;
- 81. }
- 82. }
- 83.
- 84. }
- 85.
- 86. void Print(HashTable H)
- 87. {
- 88. int i;
- 89. struct ListNode *p;
- 90. for(i=0;i<15;i++)
- 91. { printf("第%d组的成员有:\n",i);
- 92. p=H->TheList[i]->next;
- 93. while(p)
- 94. {
- 95. printf("%d ",p->elem);
- 96. p=p->next;
- 97. }
- 98. printf("\n");
- 99. }
- 100.
- 101. }
- 102. int main()
- 103. {
- 104. HashTable H;
- 105. int i;
- 106. int key;
- 107. int a[15];
- 108. List t,p;
- 109. H=InitializeTable(Size);
- 110. printf("please input number into Hash:");
- 111. for(i=0;i<15;i++)
- 112. scanf("%d",&a[i]);
- 113. for(i=0;i<Size;i++)
- 114. Insert(a[i],H);
- 115. Print(H);
- 116. key=2;
- 117. printf("please find %d\n",key);
- 118. t=Find(key,H);
- 119. if(t->elem==key)
- 120. printf("I can find %d\n",t->elem);
- 121. else
- 122. printf("I can not find the key!!!\n");
- 123.
- 124.
- 125. }
二:开放定址法
1:线性探测法
这个方法就是如果要插入的位置被占用,则往后退一个位置,直到找到位置可插入为止
2:平方探测法
这个方法就是分别取1平方,2平方,依次往下
下面给出这个方法的全部代码
- 1. #include<stdio.h>
- 2. #include<stdlib.h>
- 3.
- 4. #define Size 50
- 5. #define MinSize 9
- 6.
- 7. enum KindofEntry
- 8. {
- 9. Legitimate,Empty,Deleted
- 10. };
- 11. struct HashEntry
- 12. {
- 13. int elem;
- 14. enum KindofEntry Info;
- 15. };
- 16.
- 17. typedef struct HashEntry Cell;
- 18.
- 19. struct HashTbl
- 20. {
- 21. int Tablesize;
- 22. Cell *Thecells;
- 23. };
- 24.
- 25. typedef struct HashTbl *HashTable;
- 26.
- 27. HashTable InitializeTable(int Tablesize)
- 28. {
- 29. HashTable H;
- 30. int i;
- 31. if(Size<MinSize)
- 32. {
- 33. perror("Table size too small!\n");
- 34. return NULL;
- 35. }
- 36. H=(HashTable)malloc(sizeof(struct HashTbl));
- 37. if(H==NULL)
- 38. printf("Out of space!\n");
- 39. H->Tablesize=Size;
- 40. H->Thecells=(Cell *)malloc(sizeof(Cell)*H->Tablesize);
- 41. if(H->Thecells==NULL)
- 42. perror("Out of space!\n");
- 43. for(i=0;i<Size;i++)
- 44. {
- 45. H->Thecells[i].Info=Empty;
- 46. H->Thecells[i].elem=0;
- 47. }
- 48. return H;
- 49. }
- 50. int Hash(int key,int x)
- 51. {
- 52. int i;
- 53. i=key%x;
- 54. return i;
- 55. }
- 56.
- 57. unsigned int Find(int key,HashTable H)
- 58. {
- 59. unsigned int Pos;
- 60. int Num;
- 61. Num=0;
- 62. Pos=Hash(key,H->Tablesize);
- 63. while((H->Thecells[Pos].Info!=Empty)&&(H->Thecells[Pos].elem!=key))
- 64. {
- 65. Pos+=2*++Num-1;
- 66. if(Pos>H->Tablesize)
- 67. Pos-=Size;
- 68. }
- 69. return Pos;
- 70. }
- 71.
- 72. void Insert(int key,HashTable H)
- 73. {
- 74. unsigned Pos;
- 75. Pos=Find(key,H);
- 76. if(H->Thecells[Pos].Info!=Legitimate)
- 77. {
- 78. H->Thecells[Pos].Info=Legitimate;
- 79. H->Thecells[Pos].elem=key;
- 80. }
- 81. }
- 82.
- 83. void Print(HashTable H,int data[])
- 84. {
- 85. int b=0;
- 86. unsigned int m;
- 87. for(b=0;b<15;b++)
- 88. {
- 89. m=Find(data[b],H);
- 90. printf("%d在第%d行\n",data[b],m);
- 91. }
- 92. }
- 93.
- 94. int main()
- 95. {
- 96. int i;
- 97. int data[15];
- 98. HashTable H;
- 99. H=InitializeTable(Size);
- 100. printf("请输入要插入哈西表的元素:\n");
- 101. for(i=0;i<15;i++)
- 102. scanf("%d",&data[i]);
- 103. printf("插入之后的哈西表为:\n");
- 104. for(i=0;i<15;i++)
- 105. Insert(data[i],H);
- 106. Print(H,data);
- 107.
- 108. }
三:再散列法
这个方法是当表填写过于满的时候,我们重新建立一个表。
eg:将13,15,24,6插入一个大小为7的开放定址散列表中,如果再插入23,则这个表就会有超过%70的空间被填满,所以我们再创建一个新表,新表的大小为17(因为2*7是14,而17是大于7的二倍之后第一个素数),然后再进行插入操作
这个再散列方法比较简单:
再散列可以永平方探测以多种方式实现:
1)只要表填满一半就开是再散列
2)只有当插入失败再散列
3)当表达到一定的装填因子的时候再散列
- HashTable Rehash(HashTable H)
- {
- int i,oldsize;
- Cell *OldCells;
- oldsize=H->Tablesize;
- OldCells=H->TheCells;
- H=InitializeTable(2*oldsize);
- for(i=0;i<oldsize;i++)
- if(OldCell[i].Info==Legitimate)
- Insert(OldCells[i].elem,H);
- free(OldCells);
- return H;
- }
阅读(1731) | 评论(0) | 转发(1) |