百度面试题--给定一个单词，从字典查找该单词的所有兄弟单词
一 问题描述：
一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。
二 解题思路：
本题有两个关键点：第一，如何设计英语字典的数据结构？第二，如何查找兄弟单词？
1. 设计英语字典的数据结构
如图，可以采用哈希链表的形式组织字典，而每个结点有三个域组成，分别是单词，频度和后继指针，频度表示这个单词被访问的次数，当我们访问某个单词时，它的频度会加1，然后应用程序根据频度重新调整该单词在链表中的位置，使得频度高的里链表头近，这样可以提高查找的效率。
2. 设计查找兄弟单词的算法
比如army 和amry是兄弟单词，我们只要对两个单词按同一次序，比如升序进行排序，排序后两个单词相等，那么这两个单词是兄弟单词。
3. 代码
/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:百度面试题--给定一个单词，从字典查找该单词的所有兄弟单词
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*E-mail: 2363702560@qq.com
*Date: 2012/12/30
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
/*
*单词结构体
*/
typedef struct Word {
string word;
int freq;
// 单词被访问的频度
struct Word *next;
}Word;
const int N=26;
// 26个字母
/*
*字典类
*/
class Dictionary {
private:
vectord;
/*
*哈希函数,将ch映射为索引号
*/
int Hash(char ch) {
ch=tolower(ch);
return ch-'a';
}
/*
*比较单词one和other是否相等
*/
bool cmp(string &one, string &other) {
return one == other;
}
/*
*根据索引号index来将p所指向的结点插入该链表的合适位置
*pre指向p的直接前驱
*/
void Adjust(int index, Word *pre,Word *p) {
if(!pre) return;
//p指向链表的第一个结点
Word *cur=d[index];
//指向当前结点
Word *q=NULL;
//指向cur的直接前驱
while(cur && cur->freq>p->freq) {
q=cur;
cur=cur->next;
}
pre->next=p->next;
//将p指向的结点删除
if(!q) {
p->next=d[index];
d[index]=q;
}
else {
p->next=cur;
q->next=p;
}
}
public:
Dictionary() {
int i;
for(i=0;
i=N) {
cout<<"参数有误,程序退出!"<word,word)) {//找到要查找的单词
p->freq++;
Adjust(index,pre,p);
break;
}
pre=p;
p=p->next;
}
if(!p) {//没有找到单词
Word *q;
q=new Word;
q->freq=1;
q->word=word;
q->next=0;
if(pre) pre->next=q;
//pre指向链表最后一个结点
else d[index]=q;
//该链表为空
}
}
/*
*查找兄弟单词
**/
void SearchSibling(string word) {
int i;
int index;
Word *p,*pre;
for(i=0;
word[i];
i++) {
index=Hash(word[i]);
if(index<0 || index>=N) {
cout<<"参数有误,程序退出!"<word;
string other=word;
sort(one.begin(),one.end());
sort(other.begin(),other.end());
if(cmp(one,other)) {//找到要查找的单词
p->freq++;
Adjust(index,pre,p);
coutnext;
}
}
}
void show() const {
int i;
Word *p;
for(i=0;
inext;
}
cout<>word;
while(word!="exit") {
dictionary.Search(word);
cin>>word;
}
dictionary.show();
cout<<"输入要查找的单词:";
cin>>word;
cout<
四： 测试
【百度面试题--给定一个单词，从字典查找该单词的所有兄弟单词】
推荐阅读
- PMSJ寻平面设计师之现代(Hyundai）
- 杜月笙的口才
- Linux下面如何查看tomcat已经使用多少线程
- 皮夹克
- 解读《摩根集团》（1）
- 绘本与写作
- 蓝桥杯试题
- 麦田社群
- 面对苦难——如何化解
- 葱爷说股20190107