快速排序+二分查找与哈希表

快速序排+二分查找

#include
const int MAX= 100001;
typedef struct
{
char e[11];
char f[11];
}Entry;
Entry entry[MAX];
int i = 0;//词典总条数

int cmp(const void *a, const void *b)
{
return strcmp((*(Entry *)a).f, (*(Entry *)b).f);
}

int BinSearch(char c[])
{
int low = 0, high = i - 1;
int mid, t;
while(low <= high)
{
mid = (low + high) / 2;
t = strcmp(entry[mid].f, c);
if(t == 0)
return mid;
else if(t == -1)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

int main()
{
char str[25];
int index = -1;
while(gets(str))
{
if(str[0] == )
break;
sscanf(str,"%s%s",entry[i].e,entry[i].f);
i++;
}
qsort(entry,i,sizeof(Entry),cmp);
while(gets(str))
{
index = BinSearch(str);
if(index == -1)
printf("ehn");
else
printf("%sn",entry[index].e);
}
return 0;
}

字符串哈希表，在《算法艺术与信息学竞赛》推荐使用ELFHash函数，哈希冲突的处理采用链表法

#include

const int M = 149993;

typedef struct
{
char e[11];
char f[11];
int next;
}Entry;
Entry entry[M];
int i = 1;//词典总条数
int hashIndex[M];

int ELFHash(char *key)
{
unsigned long h=0;
while(*key)
{
h=(h<4)+(*key++);
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%M;
}

void find(char f[])
{
int hash = ELFHash(f);
for(int k = hashIndex[hash]; k; k = entry[k].next)
{
if(strcmp(f, entry[k].f) == 0)
{
printf("%sn",entry[k].e);
return;
}
}
printf("ehn");
}

int main()
{
char str[22];
while(gets(str))
{
if(str[0] == )
break;
sscanf(str,"%s %s",entry[i].e,entry[i].f);
int hash = ELFHash(entry[i].f);
entry[i].next = hashIndex[hash];
hashIndex[hash] = i;
i++;
}
while(gets(str))
find(str);
return 0;
}