hashsearch.cpp

常用算法与数据结构原代码

#include <string.h>
#include <stdio.h>
#define N 47
#define P1 47
#define P2 43
#define LEN 10

char tb[N][LEN];
int H1(char *key)
{
	long k=0,d;
	int c;
	while (*key)
	{
		for (d=c=0;*key!='\0' && c<3;c++)
			d=(d<<8)+*key++;
		k+=d;
	}
	return k % P1;
}

int H2(char *key)
{
	long k=0,d;
	int c;
	while (*key)
	{
		for (d=c=0;*key!='\0' && c<2;c++)
			d=(d<<8)+*key++;
		k+=d;
	}
	return k % P2+1;
}

char *k_word[]={"auto","break","case","char","const","continue",
                "default","do","double","else","enum","extern",
				"float","for","goto","if","int","long","register",
				"return","short","signed","sizeof","static","struct",
				"switch","typedef","union","unsigned","void","volatile",
				"while"};
void main()
{
	int count[N],i,pos,c;
	for (i=0;i<N;i++)
	{
		count[i]=0;
		tb[i][0]='\0';
	}
	for (i=0;i<sizeof k_word/sizeof k_word[0];i++)
	{
		pos=H1(k_word[i]);
		c=H2(k_word[i]);
		while (tb[pos][0]!='\0' && strcmp(tb[pos],k_word[i]))
		{
			count[pos]++;
			pos=(pos+c) % N;
		}
		strcpy(tb[pos],k_word[i]);
	}
	for (i=c=0;i<N;i++)
		if (tb[i][0]!='\0')
			printf("%10s%c",tb[i],++c % 5==0?'\n':' ');
	printf("\n\n");
	for (i=c=0;i<N;i++)
		printf("%4d%c",count[i],++c%5==0?'\n':'\t');
	printf("\n\n");
}