哈希查找

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #define MaxSize 100        /*哈希表最大长度*/
  5. typedef int KeyType;
  7. typedef struct node
  8. {
  9.     KeyType key;    /*关键字值*/
  10.     int si;            /*探查次数*/    
  11.     struct node *next;
  12. } Node;        /*数据结点类型*/
  14. typedef struct
  15. {
  16.     Node *link;
  17. } HNode;    /*头结点类型*/
  19. void CreateHT(HNode *ht[],KeyType a[],int n,int p)    /*构造哈希表*/
  20. {
  21.     int i,d,cnt;
  22.     Node *s,*q;
  23.     for (i=0;i<p;i++)    /*所有头结点的link域置空*/
  24.     {
  25.         ht[i]=(HNode *)malloc(sizeof(HNode));
  26.         ht[i]->link=NULL;
  27.     }
  28.     for (i=0;i<n;i++)
  29.     {
  30.         cnt=1;
  31.         s=(Node *)malloc(sizeof(Node));    /*构造一个数据结点*/
  32.         s->key=a[i];s->next=NULL;
  33.         d=a[i]%p;                        /*求其哈希地址*/
  34.         if (ht[d]->link==NULL)            
  35.         {
  36.             ht[d]->link=s;
  37.             s->si=cnt;
  38.         }
  39.         else
  40.         {
  41.             q=ht[d]->link;
  42.             while (q->next!=NULL)
  43.             {
  44.                 q=q->next;cnt++;
  45.             }
  46.             cnt++;
  47.             s->si=cnt;q->next=s;
  48.         }
  49.     }
  50. }
  52. void DispHT(HNode *ht[],int n,int p)    /*输出哈希表*/
  53. {
  54.     int i,sum=0;
  55.     Node *q;
  56.     printf("哈希表:\n");
  57.     for (i=0;i<p;i++)
  58.     {
  59.         q=ht[i]->link;
  60.         printf("%d:link->",i);
  61.         while (q!=NULL)
  62.         {
  63.             sum+=q->si;
  64.             printf("[%d,%d]->",q->key,q->si);
  65.             q=q->next;
  66.         }
  67.         printf("∧\n");
  68.     }
  69.     printf("\n平均查找长度:ASL=%g\n",1.0*sum/n);
  70. }
  72. void main()
  73. {
  74.     HNode *ht[MaxSize];
  75.     KeyType a[]={87,25,310,8,27,132,68,95,187,123,70,63,47};
  76.     int n=13,p=13;
  77.     CreateHT(ht,a,n,p);
  78.     DispHT(ht,n,p);
  79. }