首页 > 代码库 > Quicksearch2503

Quicksearch2503

2024-07-26 01:41:59   215人阅读

poj2503题目意思很简单：就像查找一本字典，根据输入的条目和要查询的单词，给出查询结果（每个单词长度不超过10）。这题有很多实现方式，最容易想到的就是map，但这是acm训练且stl里面的map速度不够快，那就要另谋出路。

 

关于字符串：

‘ ’ 是空格 ‘\n’是换行 

S[i]=0 等价于s[i]=’\0’  即字符串的结束标志。

//如果输入了一个回车,以getchar获得的回车仍然保持原样，即’\n’，如果是gets(ch),则ch[0]=’0’或者说ch[0]=0

Scanf(“%s”)遇到空格即为终止，gets()遇到空格不终止，遇到回车才终止

还是多用gets()方便多了

 

本题的数据输入格式为：

dog ogday

cat atcay

pig igpay

froot ootfray

loops oopslay

 

atcay

ittenkay

oopslay

给出对应的序列以后，给一个回车，然后是需要翻译的词组。

 

快排+二分，复杂度是O(nlog2n)：

 

 

#include <iostream>const int MAX = 100001;typedef struct{	char e[11];	char f[11];}Entry;Entry entry[MAX];int i = 0;		//词典总条数int cmp(const void *a, const void *b){	return strcmp((*(Entry *)a).f, (*(Entry *)b).f);}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////int comp ( const void *a, const void *b ){    return * ( int * ) a - * ( int * ) b;}上面是由小到大排序，而return *(int *)b-*(int *)a则为由大到小排序。////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////int BinSearch(char c[]){	int low = 0, high = i - 1;	int mid, t;	while(low <= high)	{		mid = (low + high) / 2;		t = strcmp(entry[mid].f, c);		if(t == 0)			return mid;		else if(t == -1)//说明c更大，所以从后半段开始找			low = mid + 1;		else			high = mid - 1;	}	return -1;}int main(){	char str[25];	int index = -1;	while(gets(str))	{		if(str[0] == ‘\0‘)			break;		sscanf(str,"%s%s",entry[i].e,entry[i].f);//sscanf函数和scanf的区别在于前者从str里面取数据，后者从input取数据。感觉还不如逐渐遍历整个数组，遇到空格即为下一个字符。此函数不难记		i++;	}	qsort(entry,i,sizeof(Entry),cmp);  	while(gets(str))	{        index = BinSearch(str);		if(index == -1)			printf("eh\n");		else			printf("%s\n",entry[index].e);	}	return 0;}

 

　　

直接用MAP容器更加简单：

 

 

//Memory  Time//17344K 1563MS #include<iostream>#include<string>#include<map>using namespace std;int main(void){	char english[11],foreign[11];	map<string,bool>appear;  //记录foreign与engliash的配对映射是否出现	map<string,string>translate; //记录foreign到engliash的映射	/*Input the dictionary*/	while(true)	{		char t;  //temporary		if((t=getchar())==‘\n‘)  //如果输入了一个回车,以getchar获得的回车仍然保持原样，即’\n’，如果是gets(ch),则ch[0]=’0’或者说ch[0]=0			break;		else     //输入english		{			english[0]=t;			int i=1;			while(true)			{				t=getchar();//同上，以getchar获得的字符仍然保持原样				if(t==‘ ‘)				{					english[i]=‘\0‘;					break;				}				else					english[i++]=t;			}		}				cin>>foreign;//这里的cin>>foreign可以换成scanf(“%s”,foreign)。		getchar();  //吃掉 输入foreign后的 回车符		appear[foreign]=true;		translate[foreign]=english;	}	/*Translate*/	char word[11];	while(cin>>word)	{		if(appear[word])			cout<<translate[word]<<endl;		else			cout<<"eh"<<endl;	}		return 0;}

 

　　

 

 

Quicksearch2503


联系
我们