哈希表

  1 //哈希做查找
  2 //建立一个哈希表，然后查找元素
  3 #include <iostream>
  4 const int tablelength = 15;
  5 int maxtimes = 4;
  6 int keynum = 13; //小于容量15的最大素数
  7 int invalidedata = -1;//hash表中没有内容时每个单元初始化为-1
  8 int fullflag  = -2; //hash表满
  9 int notfind = -3;
 10 typedef struct node
 11 {
 12     int data;
 13     ///////如果还有其他数据的话
 14 };
 15 void init(node mydata[],int length)
 16 {
 17     for(int i = 0;i<length;i++)
 18         mydata[i].data = invalidedata;
 19     return ;
 20 }
 21 int hashalgo(int i)
 22 {
 23     return i%keynum;
 24 }
 25 int increment()//如果遇到冲突，每次探查位置加1
 26 {
 27     return 1; 
 28 }
 29 int insert(node table[],int i)
 30 {
 31     int temp;
 32     int times = 0;
 33     
 34     temp = hashalgo(i);
 35     //一次就找到
 36     if(table[temp].data==invalidedata ||table[temp].data == i)
 37     {
 38         table[temp].data = i;
 39         return 1; //正常找到
 40     }
 41     else //已经有内容
 42     {
 43         while(1)
 44         {
 45             temp += increment();
 46             if(temp>=tablelength)
 47                 return fullflag;
 48             if(table[temp].data==invalidedata ||table[temp].data == i)
 49             {
 50                 table[temp].data = i;
 51                 return 1;
 52             }
 53         }
 54     }
 55 }
 56 
 57 void inserthashtable(node table[],int data[])
 58 {
 59     int ret;
 60     for(int i = 0;i<12;i++)
 61     {
 62         ret = insert(table,data[i]);
 63         if(ret == fullflag)
 64         {
 65             printf("hash表已满\n");
 66             exit(1);
 67         }
 68     }
 69     return ;
 70 
 71 }
 72 int search(node mydata[],int i)
 73 {
 74     int temp;
 75     int times = 0;
 76     
 77     temp = hashalgo(i);
 78     //一次就找到
 79     if(mydata[temp].data == i)
 80         return temp;
 81     else 
 82     {
 83         while(times<maxtimes)
 84         {
 85             temp += increment();
 86             if(temp>=tablelength)
 87                 return notfind;
 88             if(mydata[temp].data == i)
 89                 return temp;
 90             times++;
 91         }
 92         return notfind;
 93     }
 94 }
 95 int main()
 96 {
 97     node mydata[tablelength];
 98     init(mydata,tablelength);
 99     int anotherdata[12] = {1,2,4,5,21,15,99,8,0,13,26,27};
100     inserthashtable(mydata,anotherdata);
101     for(int i = 0;i<tablelength;i++)
102         printf("%d ",mydata[i].data);
103     int ret = search(mydata,5);
104     printf("5的查找结果为：%d\n",ret);
105     ret = search(mydata,100);
106     printf("100的查找结果为：%d\n",ret);
107     ret = search(mydata,27);
108     printf("27的查找结果为：%d\n",ret);
109  
110     return 0;
111 }