Chinaunix首页 | 论坛 | 博客
  • 博客访问: 388328
  • 博文数量: 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 17:23:13

  1. #include "stdio.h"
  2. #define NIL -1
  3. #define M 997
  4. typedef int KeyType;
  5. typedef struct chain
  6. {
  7.     KeyType key;
  8.     struct chain *next;
  9. }ChainType;

  10. int h(KeyType K)
  11. {
  12.     return K%M;
  13. }

  14. ChainType* HashSearch(ChainType *Ti,KeyType K,ChainType **end)
  15. {
  16.     ChainType *pre,*cur;
  17.     pre = NULL;
  18.     cur = Ti;
  19.     while(cur!=NULL && cur->key!=K)
  20.     {
  21.         pre =cur;
  22.         cur=cur->next;
  23.     }
  24.     
  25.     *end=pre; //end返回未查到关键字时,链表的尾部结点的地址,因为要用于插入
  26.     if(cur == NULL) //查找不到时,返回空值
  27.     {
  28.         return NULL;
  29.     }
  30.     else
  31.     {
  32.         return cur; //查找到时,返回该记录地址
  33.     }
  34. }

  35. int HashInsert(ChainType *T[],KeyType K)
  36. {
  37.     ChainType *pre,*cur;
  38.     int i;
  39.     i=h(K);
  40.     cur=HashSearch(T[i],K,&pre);
  41.     if(cur==NULL) //未找到时,在链表尾部插入该记录
  42.     {
  43.         cur = (ChainType*)malloc(sizeof(ChainType));
  44.         cur->key = K;
  45.         cur->next=NULL;
  46.         if(pre == NULL) //在该链表插入第一条记录
  47.         {
  48.             T[i]=cur;
  49.         }
  50.         else
  51.         {
  52.             pre->next=cur; //插入后续记录
  53.         }
  54.         return 1;
  55.     }
  56.     return 0; //记录存在时,返回0
  57. }

  58. void CreateHashTable(ChainType *T[],ChainType A[],int n)
  59. {
  60.     //根据A[0...n-1]中结点建立散列表T[0..m-1]
  61.     int i;
  62.     for(i=0;i<n;i++)
  63.     {
  64.         HashInsert(T,A[i]);
  65.     }

  66. }
用链地址解决冲突的方法是:将所有关键字为同义词的记录存储在一个线性表中,并将这些链表的表头指针放在数组中,这类似于图中的邻接表和树中孩子链表的结构。
阅读(482) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册