C语言写一个散列表

目录

一、快速理解散列表

散列表，就是下标可以为字母的数组。

假设现有一个数组int a[100]，想查找其中第40个元素，则直接输入a[40]就可以了，时间复杂度为o ( 1 ) o(1)o(1)。

问题在于，当下标不是数字，而是一个字符串的时候，可能需要一个超大的空间才能将所有下标妥善地存放在特定的位置。例如，若以大小写字母作为下标索引，那么一位就需要预留52个空间，10位就需要52的10次方这么大的空间，根本没有设备可以满足。

好在，52的10次方这么庞大的数字也超出了正常人的使用范围，无论多长的索引，我们能用上的值也绝对是有限的。

例如，现有下面三个字符串作为下标

key1 = "microcold";key2 = "tinycold";key3 = "microcool";

其实只需要选取头、尾两个字母，就能很好地区分这三个字符串，即

def hash(key):  return key[0]+key[-1]

但这种算法对索引字符的要求非常高，至少头尾不能重复。所以，现在需要能把超长字符串映射成特定短字符串而且尽量避免重复的算法。

二、散列函数

最简单的散列函数就是求余，将输入字符串按位转为整数之后求余。由于在字符串可能会转成非常大的整数，故需了解余数放暑假的性质

(a+b)%c=(a%c+b %c)% c

相应地有：

(a*b)%c=((a%c)*(b %c))% c

用c语言实现如符融下：

#include <stdio.h>#define maxhash 100//快速取幂法，a*b^n%cint powermod (int a, int b, int n, int c){   int ans = 1;  b = b % c;  while (n > 0) {     if(n % 2 == 1)      ans = (ans * b) % c;    n = n / 2;    //b >>= 1;    b = (b * b) % c;  }  return (a*ans)%c;}int hash(char* key, int n){  int addr = 0;  for(int i = 0; i < n; i++){    addr += powermod(key[i], 128, i, maxhash);  }  return addr%maxhash;}int main(){  char* str;  int i;  while(1){    gets(str);    i = 0;    while(str[i++]!='
#include <stdio.h>#define maxhash 100//快速取幂法，a*b^n%cint powermod (int a, int b, int n, int c){   int ans = 1;  b = b % c;  while (n > 0) {     if(n % 2 == 1)      ans = (ans * b) % c;    n = n / 2;    //b >>= 1;    b = (b * b) % c;  }  return (a*ans)%c;}int hash(char* key, int n){  int addr = 0;  for(int i = 0; i < n; i++){    addr += powermod(key[i], 128, i, maxhash);  }  return addr%maxhash;}int main(){  char* str;  int i;  while(1){    gets(str);    i = 0;    while(str[i++]!='\0'){}    printf("%d\n",hash(str,i));  }  return 0;}
'){}    printf("%d\n",hash(str,i));  }  return 0;}

测试如下：

>gcc hash.c>a.exeasdf21microcold81tinycold12microcool5minicool81minicold73

三、防撞

尽管minicool和microcold撞车了，但通过100以内的位数，去表示52的9次方的样本，也算是不错的表现了。

为了不发生撞车，则需更改数组中的元素类型——至少得是个结构体。而防止撞车的方法很简单，如果发生撞车，那我就不散列了，直接发配到一个指定的数组中。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define maxhash 100typedef struct hashnode{  char *key;  int next;} *hashnode;struct hashnode* hashtable[maxhash];struct hashnode* crashtable[maxhash];   //存储撞击之后的值int numcrash=0;          //已有的撞击值void inittable(){  for(int i=0; i < maxhash; i++){    hashtable[i] = (hashnode)malloc(sizeof(struct hashnode));    hashtable[i]->key = null;    hashtable[i]->next = -1;    crashtable[i] = (hashnode)malloc(sizeof(struct hashnode));    crashtable[i]->key = null;    hashtable[i]->next = -1;  }}void inrtcrash(char* str, int index, int n){  if(index == numcrash){    c贷款还款rashtable[numcrash]->key = (char*)malloc(sizeof(char)*n);    strcpy(crashtable[numcrash++]->key, str); //此时新增一个节点  }  el {    if(crashtable[index]->next==-1)      crashtable[index]->next = numcrash;    inrtcrash(str, hashtable[index]->next, n);  }}//n为字符串长度void inrthash(char* str, int index,int n){  if(hashtable[index]->key==null){    hashtable[index]->key = (char*)malloc(sizeof(char)*n);    strcpy(hashtable[index]->key, str);  }el{    if(hashtable[index]->next==-1)      hashtable[index]->next = numcrash;    inrtcrash(str, hashtable[index]->next, n);  }}void printhash(){  for(int i = 0; i < maxhash; i++){    if(hashtable[i]->key!=null)      printf("hashtable[%d]:%s\n",i,hashtable[i]->key);    if(crashtable[i]->key!=null)      printf("crashtable[%d]:%s\n",i,crashtable[i]->key);  }}int powermod (int a, int b, int n, int c){   int ans = 1;  b = b % c;  while (n > 0) {     if(n % 2 == 1)      ans = (ans * b) % c;    n = n / 2;    //b >>= 1;    b = (b * b) % c;  }  return (a*ans)%c;}int hash(char* key, int n){  int addr = 0;  for(int i = 0; i < n; i++){    addr += powermod(key[i], 128, i, maxhash);  }  return addr%maxhash;}int main(){  inittable();  char* str;  int i;  while(1){    gets(str);    if(strcmp(str,"exit")==0) break;    i = 0;    while(str[i++]!='
#include <stdio.h>#include <stdlib.h>#include <string.h>#define maxhash 100typedef struct hashnode{  char *key;  int next;} *hashnode;struct hashnode* hashtable[maxhash];struct hashnode* crashtable[maxhash];   //存储撞击之后的值int numcrash=0;          //已有的撞击值void inittable(){  for(int i=0; i < maxhash; i++){    hashtable[i] = (hashnode)malloc(sizeof(struct hashnode));    hashtable[i]->key = null;    hashtable[i]->next = -1;    crashtable[i] = (hashnode)malloc(sizeof(struct hashnode));    crashtable[i]->key = null;    hashtable[i]->next = -1;  }}void inrtcrash(char* str, int index, int n){  if(index == numcrash){    crashtable[numcrash]->key = (char*)malloc(sizeof(char)*n);    strcpy(crashtable[numcrash++]->key, str); //此时新增一个节点  }  el {    if(crashtable[index]->next==-1)      crashtable[index]->next = numcrash;    inrtcrash(str, hashtable[index]->next, n);  }}//n为字符串长度void inrthash(char* str, int index,int n){  if(hashtable[index]->key==null){    hashtable[index]->key = (char*)malloc(sizeof(char)*n);    strcp制药工程y(hashtable[index]->key, str);  }el{    if(hashtable[index]->next==-1)      hashtable[index]->next = numcrash;    inrtcrash(str, hashtable[index]->next, n);  }}void printhash(){  for(int i = 0; i < maxhash; i++){    if(hashtable[i]->key!=null)      printf("hashtable[%d]:%s\n",i努力正能量的句子,hashtable[i]->key);    if(crashtable[i]->key!=null)      printf("crashtable[%d]:%s\n",i,crashtable[i]->key);  }}int powermod (int a, int b, int n, int c){   int ans = 1;  b = b % c;  while (n > 0) {     if(n % 2 == 1)      ans = (ans * b) % c;    n = n / 2;    //b >>= 1;    b = (b * b) % c;  }  return (a*ans)%c;}int hash(char* key, int n){  int addr = 0;  for(int i = 0; i < n; i++){    addr += powermod(key[i], 128, i, maxhash);  }  return addr%maxhash;}int main(){  inittable();  char* str;  int i;  while(1){    gets(str);    if(strcmp(str,"exit")==0) break;    i = 0;    while(str[i++]!='\0'){}    inrthash(str,hash(str,i),i);    printf("%d\n",hash(str,i));  }  printhash();  return 0;}
'){}    inrthash(str,hash(str,i),i);    printf("%d\n",hash(str,i));  }  printhash();  return 0;}

最后得到：

>gcc hash.c>a.exeasdf21hellworld84microcold81minicool81tinycool20tinycold12weixiaoleng11exitcrashtable[0]:minicoolhashtable[11]:weixiaolenghashtable[12]:tinycoldhashtable[20]:tinycoolhashtable[21]:asdfhashtable[81]:microcoldhashtable[84]:hellworld

可见一方面的确散列了，另一方面也的确防撞了。

到此这篇关于c语言写一个散列表的文章就介绍到这了,更多相关c语言写散列表内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！