asdcv.cpp

利用哈希函数对学生姓名进行最优化查找 可选择从键盘输入和文件输入,需输入名字最大长度

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream.h>


typedef struct{
	char name[20];
}student;

typedef struct{
	student classmate[30];
	int count;
	int hashsize;
}HashTable;

int Hash(char *key,int c){
	int p;
	p=(int)(key[0]+key[2]-'a'-'a')%c;
	return p;
}
int EQ(char *a,char *b){
	if(strcmp(a,b)==0)return 1;
	else return 0;
}

void collision(int &p,int c){
	p=(p+1)%c;
}

int SearchHash(HashTable H,char *key,int &p,int &c){	
	c=0;
	p=Hash(key,H.hashsize);
	while((H.classmate[p].name[0]!=-52)&&(!EQ(key,H.classmate[p].name))){
		collision(p,H.hashsize);
		c++;
		if(c>H.hashsize)return 0;
	}
	if(EQ(key,H.classmate[p].name)){
		return 1;
	}
	else return 0;
}

int InsertHash(HashTable &H,student s){
	int p=0,count=0,c=0;
	if(SearchHash(H,s.name,p,c))
		return -1;
	else if(1){//c<2){
		strcpy(H.classmate[p].name,s.name);
		printf("%d\n",p);
		++H.count;
		return 1;
	}
	else {//recreateHashTable(H);
		return 0;}
}



void CreatHash(HashTable &H,int size){
//	for(int i=0;i<size;i++)
	//	H.classmate[i].name[0]=0;	
	//	H.classmate[i].name[1]=0;
			//strcpy(H.classmate[i].name,"\0");
	H.count=0;
	H.hashsize=size;
}

void input(HashTable &H){
	int i;
	student s;
	FILE *fp;
	int size;
	printf("选择--键盘输入<K>___文件输入<F>:");
	switch(getchar()){
		case 'K' :
		case 'k' :
			if((fp=fopen("Hash.txt","wb+"))==NULL){
				printf("cannot open file\n");
				exit(0);
			}
			printf("请输入数据长度:");
			scanf("%d",&size);
			CreatHash(H,size);
			fwrite(&size,sizeof(int),1,fp);
			printf("请输入学生姓名\n");
			for(i=0;i<H.hashsize;i++){
				scanf("%s",s.name);
				fwrite(&s,sizeof(student),1,fp);
				InsertHash(H,s);
			}				
			break;
		case 'f' :
		case 'F' :
				if((fp=fopen("Hash.txt","rb+"))==NULL){
				printf("cannot open file\n");
				exit(0);
			}
			fread(&size,sizeof(int),1,fp);
			printf("数据长度为:%d\n",size);
			CreatHash(H,size);
			for(i=0;i<H.hashsize;i++){
				fread(&s,sizeof(student),1,fp);
				printf("学生姓名:%s\n",s.name);
				InsertHash(H,s);
			}	
			break;
	}
	fclose(fp);
}

void main(){
	HashTable H;	
	char name[20],ch;
	int i,p=0,c=0;
	input(H);
	printf("name\t\t\t\t\t address\n");
	for(i=0;i<H.hashsize;i++){
		if(H.classmate[i].name[1]!=-52){
			printf("%s",H.classmate[i].name);
			SearchHash(H,H.classmate[i].name,p,c);
			printf("\t\t\t\t %d\n",p);
		}
	}

	do{
		printf("输入查找姓名:");
		scanf("%s",name);
		getchar();
		switch(SearchHash(H,name,p,c)){
			case 0:
				printf("Can't Find!\n");
				break;
			case 1:
				printf("Find!   p=%d\n",p);
				break;
			default:
				printf("Can't Find!\n");
				break;
		}
		printf("继续查找吗?Y/N:");
		ch=getchar();
		getchar();
	}while(ch=='Y'||ch=='y');
		
}

/*
选择--键盘输入<K>___文件输入<F>:f
数据长度为:10
学生姓名:wangyuxia
5
学生姓名:chenquanzhi
6
学生姓名:zhengxin
9
学生姓名:lijiajia
0
学生姓名:liyang
7
学生姓名:chenzhaoguo
8
学生姓名:zhanghongwei
1
学生姓名:pengjiaming
2
学生姓名:zhujian
3
学生姓名:lianghan
4
name                                     address
lijiajia                                 0
zhanghongwei                             1
pengjiaming                              2
zhujian                          3
lianghan                                 4
wangyuxia                                5
chenquanzhi                              6
liyang                           7
chenzhaoguo                              8
zhengxin                                 9
输入查找姓名:zhujian
Find!   p=3
继续查找吗?Y/N:y
输入查找姓名:lianghan
Find!   p=4
继续查找吗?Y/N:y
输入查找姓名:lian
Can't Find!
继续查找吗?Y/N:y
输入查找姓名:chen
Can't Find!
继续查找吗?Y/N:n
*/