www.pudn.com > iprout-hash.rar > iprout.cpp

#include 
#include 
#include 
//#include 
//#include 
#include  
#define RoutLen 10   //路由前缀个数 
	   
    //随机初始化10个路由前缀 
char routpre[RoutLen][13]={"01010","010110","0100110","0111011","00101101","010011010","001011010", 
"01100101001","010010100110","01001011010"}; 
 
typedef struct chain{ 
	int key; 
	char *routpre; 
	struct chain *next; 
}ChainType; 
 
typedef struct hash{ 
	struct chain *chainaddr; 
}HashType; 
 
char *SearchPre(char *pre_in,int maxlength,HashType* HashT_in[],ChainType *ChainT_in[]); 
	 
/*在链地址表示的散列表中某条链中查找关键字K，找到返回该记录地址； 
否则返回空值，由形参end返回未查找到关键字时，链表的尾部结点的地址 
ChainType *HashSearch(ChainType* T,int K,ChainType **end) 
{ 
	ChainType *pre,*cur; 
	pre=NULL; 
	cur=T; 
	while(cur!=NULL&&cur->key!=K){ 
		pre=cur; 
		cur=cur->next; 
	} 
	*end=pre; 
	if(cur==NULL) 
		return NULL;    //查找不到时，返回空值 
	else 
		return cur;    //查找到时，返回该记录地址 
} 
 
int HashInsert(ChainType *T[],int K) 
//在链地址的散列表T中，若找不到关键字为K的记录，则插入该记录 
{ 
	 
	ChainType *pre,*cur; 
	 
	cur=HashSearch(T[K],K,&pre); 
	if(cur==NULL){ 
		cur=(ChainType *)malloc(sizeof(ChainType)); 
		cur->key=K; 
		cur->next=NULL; 
		if(pre==NULL) 
			T[K]=cur; 
		else 
			pre->next=cur; 
 
		return 1; 
	} 
	return 0; 
} 
 
//根据A[0....n-1]中结点建立散列表T[0....m-1] 
void CreateHashTable(ChainType *T[],ChainType A[],int n) 
{ 
	int j; 
	for(j=0;jnext=NULL; 
	 
		ChainTable[i]->routpre=routpre[i]; 
 
		if(HashTable[k]==NULL) 
		{ 
		 
			HashTable[k]=(HashType*)malloc(sizeof(HashType)); 
			HashTable[k]->chainaddr=NULL; 
		} 
		if(HashTable[k]->chainaddr==NULL) 
		{	 
 
			HashTable[k]->chainaddr=ChainTable[i]; 
			 
		} 
		else 
		{ 
 
			p=HashTable[k]->chainaddr; 
			while(p->next!=NULL) 
			{ 
				p=p->next; 
			} 
			p->next=ChainTable[i]; 
		} 
 
	} 
	printf("Rout Information:\n"); 
	for(i=0;i<15;i++) 
	{ 
		if(HashTable[i]!=NULL) 
		{ 
			p=HashTable[i]->chainaddr; 
			printf("length  %d",i); 
			while(p!=NULL) 
			{ 
				printf("  %s ",p->routpre); 
				p=p->next; 
			} 
			printf("\n"); 
			maxlen=i; 
		} 
	} 
	printf("the maxlen pre is %d:\n",maxlen); 
	i=0; 
	printf("请输入需要匹配的前缀（只限0/1形式）:");	 
	do{ 
		ch=getchar(); 
		if(ch=='\n') break; 
		if((ch=='0')||(ch=='1')) 
		{ 
			inputpre[i]=ch; 
			i++; 
		} 
		else continue; 
	}while(i<32); 
	printf("您输入的有效前缀是:%s\n",inputpre); 
	long timebegin=GetTickCount(); 
	for(rat=0;rat<100000;rat++)  
	{ 
		strcpy(matchpre,SearchPre(inputpre,maxlen,HashTable,ChainTable)); 
	//	printf(".....\n"); 
	} 
	printf("匹配的前缀是: %s\n",matchpre); 
 
	for(i=RoutLen-1;i>=0;i--) free(ChainTable[i]); 
	for(i=14;i>=0;i--) free(HashTable[i]); 
	timeend=GetTickCount(); 
	printf("timebegin is %u \n",timebegin); 
	printf("timeend is %u\n",timeend); 
	printf("Total time is %u ms",(timeend-timebegin)); 
 
} 
 
char *SearchPre(char *pre_in,int maxlength,HashType* HashT_in[],ChainType *ChainT_in[]) 
{ 
	int j,i; 
	ChainType * p1; 
	 
 
	j=maxlength; 
 
	while(j>0) 
	{ 
		if(HashT_in[j]==NULL)  
		{ 
			j--; 
			continue; 
		} 
		p1=HashT_in[j]->chainaddr; 
		while(p1!=NULL) 
		{ 
			for(i=0;iroutpre[i]) 
				{ 
					break; 
				} 
			} 
			if(i==j) return p1->routpre; 
			p1=p1->next; 
		} 
		j--; 
	} 
	return "no match key"; 
}