map和字典树各实现一次，总结之，字典上效率很高，尤其对于某些情况。

 MAP实现

字典树实现

//2133296 2010-03-30 20:54:39 Wrong Answer  1109 C++ 140 14968 Xredman 
//错误原因：打错字了 
//2133299 2010-03-30 20:57:05 Accepted  1109 C++ 120 14968 Xredman 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <malloc.h>
using namespace std;

const int N = 26;

typedef struct dicTNode
{
	struct dicTNode *child[N];
	int cnt;
	char res[12];
	dicTNode()
	{//对根节点初始化，根节点不存储任何数据
		*res = '\0';
		cnt = 0;
		for(int i = 0;i < N; i++)
			child[i] = NULL;
	} 
	void setRes(char *e)
	{
		strcpy(res, e);
	}
}dicTNode, *dictree;


void insert(char *str, dictree &root, char *e)
{
	dictree curNode, newNode;
	int len = strlen(str);
	int i, j;
	
	if(len == 0)
		return;//无须插入的情况
	curNode = root;
	for(i = 0; i < len; i++)
	if(curNode->child[str[i] - 'a'])
	{//子树存在
		curNode = curNode->child[str[i] - 'a'];
		curNode->cnt++; 
	} else
	{//子树不存在的情况 
		newNode = new dicTNode;
		newNode->cnt = 1;
		
		curNode->child[str[i] - 'a'] = newNode;
		curNode = curNode->child[str[i] - 'a']; 
	}
	curNode->setRes(e);
}

char* find(char *str, dictree root)
{
	int i, len;
	dictree curNode;
	len = strlen(str);
	
	if(len == 0)
		return 0;
	curNode = root;
	for(i = 0; i < len; i++)
	{//一直遍历到串底
		if(curNode->child[str[i] - 'a'])
			curNode = curNode->child[str[i] - 'a'];
		else
			return 0; 
	}
	return curNode->res;
}

void dfs(dictree &tc)
{
	if(tc)
	{
		for(int i = 0;i < N; i++)
			dfs(tc->child[i]);
	}
	free(tc);
	tc = NULL;
}
int main()
{
	int i, j, len;
	char str[30];
	char a[12], b[12];
	char *p;
	dictree root = new dicTNode();
	while(gets(str))
	{
		len = strlen(str);
		if(len == 0)
			break;
		for(i = j = 0; i < len && str[i] != ' '; i++, j++)
			a[j] = str[i];
		a[j] = '\0';
		for(i++, j = 0; i < len; i++, j++)
			b[j] = str[i];
		b[j] = '\0';
		insert(b, root, a);
	}
	while(scanf("%s", str) != EOF)
	{
		p = find(str, root);
		if(p)
			printf("%s\n", p);
		else
			printf("eh\n");
	}
	return 0;
}

//2133149 2010-03-30 19:53:27 Runtime Error  1109 C++ 520 11008 Xredman 
//原因：数组开小了 
//2133159 2010-03-30 19:57:40 Accepted  1109 C++ 2360 11008 Xredman 
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <cstring>
using namespace std;

const int MAX_SIZE = 30;//the input is a sequence of at most 10 lowercase letters.

int main()
{
	map<string, string> M;
	string a, b;
	int len, i;
//	gets(a);
	char str[MAX_SIZE];
	while(gets(str))
	{
		a = b = "";
		len = strlen(str);
		if(len == 0)
			break;
		for(i = 0; i < len && str[i] != ' '; i++)
			a += str[i];
		for(i++; i < len; i++)
			b += str[i];
		M[b] = a;
	}
	while(cin>>a)
	{
		if(M.find(a) != M.end())
			cout<<M[a]<<endl;
		else
			cout<<"eh"<<endl;
	}
	return 0;
}

• 相关文章
• 全局相关文章