[C++知识库]POJ 2503

2503

解决方法一：

用 map容器，一对一的映射过去。

要点二、需要注意输入的问题，这里有一行空行怎么保留，getline(cin, line); 这里读入line之后，就可以发现如果是空行，则line =""

对输入的字符串进行截取。

#include<iostream>
#include <map>
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
int main()
{
    map<string, string> dict;
    string line = "", value = "", key = "";
    int v_pos = 0, k_pos = 0;
    while (1)
    {
        getline(cin, line);
        if (line == "")
            break;
        v_pos = line.find(' ');  //查找第一个空格位置
        value = line.substr(0, v_pos); //取子串
        k_pos = line.rfind(' '); //找最后一个空格位置
        key = line.substr(v_pos + 1, k_pos - v_pos - 1); //取子串
        dict.insert(pair<string, string>(key, value));
    }
    char query[100];
    while (~scanf("%s", query))
    {
        if (dict.find(query) != dict.end())
            cout << dict[query] << endl;
        else
            cout << "eh" << endl;
    }
    return 0;
}

方法二、用二分查找和qsort解决

这里对字符串进行比较。
按字典序排序。
这样可以进行二分查找。

//按字典序排序 
int cmp_chars(const void* e1, const void* e2)
{
	return strcmp(*(char**)e1, *(char**)e2);
}
void test2()
{
	 char* arr1 = "bc";
	 char* arr2 = "ad";
	 char* arr3 = "ac";
	 char* p[3] = { arr1,arr2,arr3 };
	int sz = sizeof(p) / sizeof(p[0]);
	qsort(p, sz, sizeof(p[0]), cmp_chars);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s\n", p[i]);
	}
}

题解：

#include <iostream>
# include <stdio.h>
#include<string.h>
#include<stdlib.h> 
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 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);  //字符匹配 和map的find功能一样。 
		if (t == 0)
			return mid; 
		else if (t == -1)  //小了
			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);
		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;
}