电子小字典（查找）

[问题描述]

利用键树结构，建立一个微型电子字典。

[基本要求]

实现生词的加入，单词的查找、删除，修改等操作。

解题思路：

首先对键树结构进行解释。这里，我们每个节点中并不是一个或几个关键字，而是只含有组成关键字的符号。在这题中，每个节点只包含组成单词的字母。我们用结构体数组（vector类型）来存储键树，原键树的节点在这里对应数组的一格。先在“字典”中初始化26个英文字母（小写），作为插入、查询等的起始位置。

插入：对要插入单词的字母进行逐个遍历，先匹配字典中已有的部分，例如原来已有“be”，再插入“bean”时，就会先匹配be的部分，之后an的部分会在vector后面按顺序添加，最后将末尾字母的end置为1，代表一个单词插入完成。查询时，按照next进行追踪即可。删除：先查询，若查询成功，则获得末尾字母的编号，把末尾字母的end重新置为0，则删除成功；若查询失败，则插入失败。修改：考虑到修改的方式多种多样，可能是减短、增长或改变几个字母等，为了简便，这里就直接把原单词删除，再把修改后的单词插入到字典中。

程序代码：

# include <iostream>
# include <stdlib.h>
# include <string>
# include <vector>using namespace std;typedef struct Alphabet {char a;     //字母int end;    //是否为单词结尾(0:否 1:是)vector<int>next;
}Alphabet;//操作菜单
void Menu();
//添加单词
void InsertWord(string str);
//查询单词
int SearchWord(string str);
//删除单词
void DeleteWord(string str);
//修改单词
void ChangeWord(string str1, string str);
int num = 0;          //保存当前的数组长度
vector<Alphabet>word; //字典//主函数
int main()
{//初始化字典Alphabet al;for (int i = 0; i < 26; i++) {al.a = 97 + i;al.end = 0;word.push_back(al);num++;}int select;while (1) {int t;string str, str1;Menu();cout << "请选择：";cin >> select;if (select == 1) {//添加单词cout << "请输入要添加的单词：";cin >> str;InsertWord(str);}else if (select == 2) {//查询单词cout << "请输入要查询的单词：";cin >> str;t = SearchWord(str);if (t >= 0) {cout << "查询成功" << endl;}else {cout << "查询失败" << endl;}}else if (select == 3) {//删除单词cout << "请输入要删除的单词：";cin >> str;DeleteWord(str);}else if (select == 4) {//修改单词cout << "请输入要修改的单词：";cin >> str1;cout << "请输入修改后的单词：";cin >> str;ChangeWord(str1, str);}else {break;}}return 0;
}//操作菜单
void Menu()
{cout << "\n*******************************\n";cout << "**（1）、添加单词 *************\n";cout << "**（2）、查询单词 *************\n";cout << "**（3）、删除单词 *************\n";cout << "**（4）、修改单词 *************\n";cout << "**（5）、退出 *****************\n";cout << "*******************************\n";
}//添加单词
void InsertWord(string str)
{Alphabet al;int j = str[0] - 97;  //字母int t, i;for (i = 1; i < str.size(); i++) {t = 0;for (int k = 0; k < word[j].next.size(); k++) {int m = word[j].next[k];if (word[m].a == str[i]) {j = m;t = 1;break;}}if (!t) {//到此能遍历的单词部分break;}}while (i < str.size()) {//单词没有遍历完al.a = str[i];al.end = 0;word[j].next.push_back(num);word.push_back(al);j = num;num++;i++;}word[j].end = 1;
}//查询单词
int SearchWord(string str)
{int j = str[0] - 97;  //字母int t, i;for (i = 1; i < str.size(); i++) {t = 0;for (int k = 0; k < word[j].next.size(); k++) {int m = word[j].next[k];if (word[m].a == str[i]) {j = m;t = 1;break;}}if (!t) {//到此能遍历的单词部分break;}}if (i == str.size() && word[j].end) {return j;}else {return -1;}
}//删除单词
void DeleteWord(string str)
{int t = SearchWord(str);if (t >= 0) {word[t].end = 0;cout << "删除成功" << endl;}else {cout << "删除失败" << endl;}
}//修改单词
void ChangeWord(string str1, string str)
{int t = SearchWord(str1);if (t >= 0) {word[t].end = 0;InsertWord(str);cout << "修改成功" << endl;}else {cout << "修改失败" << endl;}
}

总结：

这种写法比较简单，但也有一定的缺点。对于单词的删除，我只是做了形式上的“删除”，保证其无法再被查询到，但其占据的空间还在，这样会导致空间的浪费。大家可以尝试自己改进。

以上是我对这道题的看法，很高兴与大家分享。