TIOJ 1302 撿鞋問題─強化死筆之路！ [Hash]

nolonger    1302    Accepted    5988K    217MS    G++    1.92K    2009-12-19 01:21:51                        .





int tohash(char *s){
    return s[0];
}

咦等一下這樣的hash就過了= =


反正就基本Hash操作啊


小乃：開map啦


唔如果考出類似題我一定開map

//*****************************

#include<stdio.h>
#include<string.h>
#define HV 33331
#define LEN 30
struct hash{
	char s[LEN];
	int dir;
	hash *next,*topair;
}H[HV];
char com[10],s1[LEN],s2[LEN];
//dir 0 NULL 'n' name 'w' death
int tohash(char *s){
	
	int val=0;
	for(int i=0;s[i];i++)
		val=(val*31+s[i])%HV;
	return val;
	
	return s[0];
}
void push(char *name,char *death){
	int nh=tohash(name),dh=tohash(death);
	hash *p=&H[nh],*q,*r;
	if(p->dir){
		r=p->next;
		p->next=new hash;
		p=p->next;
		p->next=r;
	}
	strcpy(p->s,name);
	p->dir='n';
	
	q=&H[dh];
	if(q->dir){
		r=q->next;
		q->next=new hash;
		q=q->next;
		q->next=r;
	}
	strcpy(q->s,death);
	q->dir='w';
	
	q->topair=p;
	p->topair=q;
}
hash* find(char *s,int d){
	int v=tohash(s);
	hash *p=&H[v];
	while(p&&(strcmp(s,p->s)||p->dir!=d)){
		p=p->next;
	}
	if(p==NULL || p->dir!=d)return NULL;
	return p;
}
bool del(char *s,int d){
	int v=tohash(s);
	hash *p=&H[v],*pre=NULL;
	while(p&&(strcmp(s,p->s)||p->dir!=d)){
		pre=p;
		p=p->next;
	}
	if(p==NULL || p->dir!=d)return 0;
	if(pre==NULL){
		if(p->dir==d){
			p->dir=0;
			del(p->topair->s,d=='n'?'w':'n');
		}
		return 0;
	}
	pre->next=p->next;
	del(p->topair->s,d=='n'?'w':'n');
	delete p;
	return 1;
}
main(){
	while(~scanf("%s%s",com,s1)){
		if(!strcmp(com,"add")){
			scanf("%s",s2);
			push(s1,s2);
		}
		else if(!strcmp(com,"chk")){
			hash *p=find(s1+1,s1[0]);
			if(p==NULL || p->dir!=s1[0])puts("Not found.");
			else{
				if(p->dir=='w')
					p=p->topair;
				printf("%s %s\n",p->s,p->topair->s);
			}
		}
		else{
			del(s1+1,s1[0]);
		}
	}
}