学步园

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <fstream>
#include<conio.h>
#include<time.h> 
#define N 10
using namespace std;
#define  HASHSIZE 1201
#define  SIZE 1000  

typedef struct MapNode{
	MapNode    *next;
	//unsigned int nHashValue; 
	char   *name;    //key
	//char   *value;  //value
}MapNode;

static MapNode *hashtab[HASHSIZE];

unsigned int Hash(char *str)	
{
	//8
	//unsigned int hashval = 1;
	//unsigned int g = 4;
	unsigned int hashval = 0;
	unsigned int g;
	long n=0x100; 
	int r ;

	for(hashval = 0; *str != '\0';str++)
	{
		//1
		//hashval = *str + 31 * hashval;
		//2
		//hashval = *str + 32 * hashval+hashval;
		//3		
		//hashval=(hashval<<5)+hashval+*str;
		//4
		//hashval = hashval*31 + *str++;
		//5
		//hashval=(hashval<<5)+hashval+*str++;
		//6
		/*hashval = (hashval << 4) + *str++; 
		if ((g = (hashval & 0xF0000000))) { 
			hashval = hashval ^ (g >> 24); 
			hashval = hashval ^ g; 
		}*/
		//7
		/*
		g=n|(*str); 
		n+=0x100; 
		r= (int)((g>>2)^g)&0x0f; 
		hashval=(hashval * (32-r)); 
		hashval&=0xFFFFFFFFL; 
		hashval^=g*g; 
		*/
		//8
// 		hashval^= (((hashval & 63)+g)*(*str++))+ (hashval << 8); 
// 		g+=3; 
		 //9
		hashval *= 16777619; 
		hashval ^= (unsigned int) *(unsigned char*) str; 

	}
	return hashval % HASHSIZE;
}

MapNode *lookup(char *str)
{
	MapNode *np;

	for(np = hashtab[Hash(str)]; np != NULL; np = np->next)
	{
		if(strcmp(str,np->name) == 0)
		return np;
	}
	return NULL;
}

MapNode  *insert(char *name)
{
	MapNode *mp;
	unsigned int hashval;
	
	if((mp = lookup(name)) == NULL){
		mp = (MapNode *)malloc(sizeof(MapNode));
		if(mp == NULL || (mp->name = strdup(name)) == NULL)
			return NULL;
		hashval = Hash(name);
		mp->next= hashtab[hashval];
		hashtab[hashval] = mp;
 	}
//		else
// 		free((void *)np->value);
// 	if((np->value = strdup(defn)) == NULL)
// 		return NULL;
	return mp;
}


void makeStr(void){
	int flag; 
	int j,k=0; 

	char str[11] ={};
	for(j=0;j<N;j++)  
	{  
		flag=rand()%2;    
		if(flag) 
			str[k++]='A'+rand()%26;  
		else str[k++]='a'+rand()%26; 
	} 
	str[k]='\0';  
	insert(str);
} 
int main()
{	
	ofstream os("results.txt",ios::binary);
//  	for (int i =0;i<SIZE;i++) //number 0-999
//  	{
//  		char temp[5]={};
//  		sprintf(temp,"%d",i);
//  		insert(temp);
//  	}
	srand((unsigned)time(NULL));  
	for (int i =0;i<SIZE;i++)
	{
		makeStr();	          //string 
	}
	
	int countTime1 = 0;
	int countTime2 = 0;
	int countTime3 = 0;
	int countTime4 = 0;
	
	for (int i =0;i<HASHSIZE;i++)
	{
		if (hashtab[i]!=NULL)
		{
			countTime1++;
			int Time2  = 2;
			int	Time3  = 3;
			int Time4  = 4;
			//printf("%d  ",i);
			os<<i<<" ";
			for(MapNode *np = hashtab[i]; np != NULL; np = np->next)
			{
				if(--Time2==0)
				{
					countTime2++;
				}
				if(--Time3==0)
				{
					countTime3++;
				}
				if(--Time4==0)
				{
					countTime4++;
				}
				
			//	printf("%s  ",np->name);
				os<<np->name<<" ";
			}

			//printf("\n");
			os<<endl;
		}
		
	}
	os<<countTime1<<endl;
	os<<countTime2<<endl;
	os<<countTime3<<endl;
	os<<countTime4<<endl;
	


//	MapNode *mp = lookup("555");
//	printf("%s\n",mp->name);
	printf("ok\n");
	getchar();
}