데이터 구조 - 해시 표/산 목록

#include "stdio.h"
#include "stdlib.h"

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define OK 1
#define ERROR -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
#define BT(a,b) ((a)> (b))
#define NULLKEY -111

int hashsize[]={11,19,29,37}; //         ，
                              //         

int m=0; //      ，    
typedef int KeyType;
typedef int info;
typedef struct
{
    KeyType key;
    //info otherinfo;
}ElemType;

typedef struct
{
    ElemType *elem;
    int count;
    int sizeindex;
}HashTable;

int InitHashTable(HashTable &H)
{ //     :          
   int i;
   H.count=0; //        0
   H.sizeindex=0; //        hashsize[H.sizeindex]
   m=hashsize[0];
   H.elem=(ElemType*)malloc(m*sizeof(ElemType));
   if(!H.elem)
     exit(0); //       
   for(i=0;i<m;i++)
     H.elem[i].key=NULLKEY; //        
   return OK;
}

void DestroyHashTable(HashTable &H)
{ //     :    H  。    :      H
   free(H.elem);
   H.elem=NULL;
   H.count=0;
   H.sizeindex=0;
}//DestroyHashTable

int Hash(KeyType K)
{ //          (m   ，    )
   //     
   return K%m;
}//Hash

void collision(int &p,int d) //        
{ //          
   p=(p+d)%m;
}//collision


int SearchHash(HashTable H,KeyType K,int &p,int &c)
{   
    p=Hash(K); //      
    while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))    //         ，        
    {
        collision(p,++c); //       p
        if(c>=m)
            break;
    }
    if(EQ(K,H.elem[p].key))        //    ，p          
        return SUCCESS;
    else                        //     (H.elem[p].key==NULLKEY)
        return UNSUCCESS;        //p        
}//SearchHash

int InsertHash(HashTable &H,ElemType e);

void RecreateHashTable(HashTable &H) //      
{
   int i,count=H.count;
   ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
   p=elem;
   printf("     
");
   for(i=0;i<m;i++)            //          elem 
        if((H.elem+i)->key!=NULLKEY) //       
            *p++=*(H.elem+i);
   H.count=0;      // H.coun   0
   H.sizeindex++; //       
   m=hashsize[H.sizeindex];       
   p=(ElemType*)realloc(H.elem,m*sizeof(ElemType));
   if(!p)
        exit(-1); //       
   H.elem=p;
   for(i=0;i<m;i++)
        H.elem[i].key=NULLKEY; //        (   )
   for(p=elem;p<elem+count;p++) //                            
        InsertHash(H,*p);
}//RecreateHashTable

int InsertHash(HashTable &H,ElemType e)
{ //             e        H ，   OK；
   //        ，      
   int c,p;
   c=0;
   if(SearchHash(H,e.key,p,c)) //      e     
        return DUPLICATE;    //SUCCESS=1
   else if(c<hashsize[H.sizeindex]/2) //     c     ,(c     )
   { //   e
        H.elem[p]=e;
        ++H.count;
        return OK;
   }
   else
     RecreateHashTable(H); //     c    ，         ，            e
   return ERROR;
}

int InsertHashD(HashTable &H)
{
    ElemType e;
    printf("input the data until -1
");
    scanf("%d",&e.key);
    while(e.key!=-1)
      {
          InsertHash(H,e);
          scanf("%d",&e.key);
      }//while
    return 1;
}//InsertHashD

int SearchHashD(HashTable &H)
{
    KeyType key;
    int p=0,c=0;
    printf("input the data you want to search:
");
    scanf("%d",&key);
    if(SearchHash(H,key,p,c))
           printf("the location is %d,%d
",p,H.elem[p].key);
    else printf("Search Failed!
");
    return 1;
}//SearchHashD

void print(int p,ElemType r)
{
   printf("address=%d (%d)
",p,r.key);
}//print

void TraverseHash(HashTable H,void(*Vi)(int,ElemType))
{ //              
   printf("    0～%d
",m-1);
   for(int i=0;i<m;i++)
     if(H.elem[i].key!=NULLKEY) //    
       Vi(i,H.elem[i]);
}//TraverseHash

void TraverseHashD(HashTable &H)
{
    TraverseHash(H,print);
}//TraverseHashD

int main()
{
    HashTable H;
    InitHashTable(H);        //   
    InsertHashD(H);            //     
    //SearchHashD(H);            //  
    TraverseHashD(H);        //  
    DestroyHashTable(H);    //  
    return 1;
}