电子小字典（南航2022数据结构课程设计第十八题）

[问题描述]

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

[基本要求]

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

[基本思路]

这道题的关键就是键树的操作，键树大概就是下图的样子，每个节点存一个字母，多个节点相连构成一个单词，单词的最后一个字母的节点再存储汉译，并用一个bool记这是个单词的结尾。

[代码实现]

头文件即节点声明

#include<iostream>
#include<fstream>
using namespace std;
typedef struct node
{bool is_word;//记录是否是单词的尾字母char data;//当前节点数据string translation;//汉译node* next[26];//子节点指针,a~z的顺序int num;//子结点个数node()//构造函数{memset(next, NULL, sizeof(next));num = 0;is_word = false;}
}node;
node* root = new node;//根节点声明

单词添加

void add(string tran, string s, node* t, int d)
{if (t->next[int(s[d] - 'a')] == NULL)//该节点子节点字符没有与所添加单词下一字母相同的{t->next[int(s[d] - 'a')] = new node;//新建节点t->next[int(s[d] - 'a')]->data = s[d];if (d == s.length() - 1)//单词存储完成{t->next[int(s[d] - 'a')]->is_word = true;t->next[int(s[d] - 'a')]->translation = tran;cout << tran << endl;t->num++;return;}t->num++;add(tran, s, t->next[int(s[d] - 'a')], d + 1);}else//有相同的{if (d == s.length() - 1)//单词存储完成{t->next[int(s[d] - 'a')]->is_word = true;t->next[int(s[d] - 'a')]->translation = tran;cout << tran << endl;return;}add(tran, s, t->next[int(s[d] - 'a')], d + 1);}
}

单词删除

bool delete_(string s, node* t, int d) 
{if (d == s.length()){t->is_word = false;if (t->num == 0)//该节点无子节点{return true;}return false;}else{if (delete_(s, t->next[int(s[d] - 'a')], d + 1))//若末节点删除，则删除其在上一节点对应的信息{free(t->next[int(s[d] - 'a')]);t->next[int(s[d] - 'a')] = NULL;if (t->is_word)//若当前节点return false;t->num--;if (t->num == 0)//若当前节点仍有其他子节点，保留return true;elsereturn false;}else//否则上节点无变化{return false;}}
}

单词查找

bool search(string s,node *t,int d,bool flag)
{static char out[100] = { '\0' };if (d == s.length()){if (t->is_word == true){if (flag){for (int i = 0; i <= d; i++)cout << out[i];cout << ' ' << t->translation;cout << endl;}return true;}elsereturn false;}if (t->next[int(s[d] - 'a')] == NULL){return false;}else{return search(s, t->next[int(s[d] - 'a')], d + 1, flag);}
}

单词展示

void show(node *t,int d)
{static char s[32] = { 0 };if (d != -1)s[d] = t->data;if (t->is_word){for (int i = 0; i <= d; i++)cout << s[i];cout << ' ' << t->translation << endl;}for (int i = 0; i < 26; i++){if (t->next[i] != NULL)show(t->next[i], d + 1);}return;
}

单词存储（单词添加可以直接在文件尾追加，没必要用这个函数，主要是删除）

void sort(node* t, int d)
{fstream file("word.txt", ios::app);static char s[100] = { '\0' };if (d != -1)s[d] = t->data;else{fill(s, s + 100, '\0');}if (t->is_word){for (int i = 0; i <= d; i++)file << s[i];file << ' ';file << t->translation;file << '\n';file.flush();}for (int i = 0; i < 26; i++){if (t->next[i] != NULL)sort(t->next[i], d + 1);}file.flush();
}

源代码

#include<iostream>
#include<fstream>
using namespace std;
typedef struct node
{bool is_word;//记录是否是单词的尾字母char data;//当前节点数据string translation;//汉译node* next[26];//子节点指针int num;//子结点个数node()//构造函数{memset(next, NULL, sizeof(next));num = 0;is_word = false;}
}node;
node* root = new node;//根节点声明
bool is_lawful(string s)
{int i = 0;while (s[i] != '\0'){if (s[i] > 'z' || s[i] < 'a')return false;i++;}return true;
}
void add(string tran, string s, node* t, int d)
{if (t->next[int(s[d] - 'a')] == NULL)//该节点子节点字符没有与所添加单词下一字母相同的{t->next[int(s[d] - 'a')] = new node;//新建节点t->next[int(s[d] - 'a')]->data = s[d];if (d == s.length() - 1)//单词存储完成{t->next[int(s[d] - 'a')]->is_word = true;t->next[int(s[d] - 'a')]->translation = tran;//cout << tran << endl;t->num++;return;}t->num++;add(tran, s, t->next[int(s[d] - 'a')], d + 1);}else//有相同的{if (d == s.length() - 1)//单词存储完成{t->next[int(s[d] - 'a')]->is_word = true;t->next[int(s[d] - 'a')]->translation = tran;//cout << tran << endl;return;}add(tran, s, t->next[int(s[d] - 'a')], d + 1);}
}
bool delete_(string s, node* t, int d) 
{if (d == s.length()){t->is_word = false;if (t->num == 0)//该节点无子节点{return true;}return false;}else{if (delete_(s, t->next[int(s[d] - 'a')], d + 1))//若末节点删除，则删除其在上一节点对应的信息{free(t->next[int(s[d] - 'a')]);t->next[int(s[d] - 'a')] = NULL;if (t->is_word)return false;t->num--;if (t->num == 0)return true;elsereturn false;}else//否则上节点无变化{return false;}}
}
void initialize()
{fstream file("word.txt", ios::in);if (file.fail()){cout << "word.txt打开失败！！！" << endl;exit(0);}while (!file.eof()){string s;string tran;file >> s;file >> tran;//cout << s << endl;if (s != "")add(tran, s, root, 0);}
}
bool search(string s,node *t,int d,bool flag)
{static char out[100] = { '\0' };if (d == s.length()){if (t->is_word == true){if (flag){for (int i = 0; i <= d; i++)cout << out[i];cout << ' ' << t->translation;cout << endl;}return true;}elsereturn false;}if (t->next[int(s[d] - 'a')] == NULL){return false;}else{return search(s, t->next[int(s[d] - 'a')], d + 1, flag);}
}
void show(node *t,int d)
{static char s[32] = { 0 };if (d != -1)s[d] = t->data;if (t->is_word){for (int i = 0; i <= d; i++)cout << s[i];cout << ' ' << t->translation << endl;}for (int i = 0; i < 26; i++){if (t->next[i] != NULL)show(t->next[i], d + 1);}return;
}
void sort(node* t, int d)
{fstream file("word.txt", ios::app);static char s[100] = { '\0' };if (d != -1)s[d] = t->data;else{fill(s, s + 100, '\0');}if (t->is_word){for (int i = 0; i <= d; i++)file << s[i];file << ' ';file << t->translation;file << '\n';file.flush();}for (int i = 0; i < 26; i++){if (t->next[i] != NULL)sort(t->next[i], d + 1);}file.flush();
}
void run()
{while (1){cout << "1.添加单词" << endl << "2.查找单词" << endl << "3.删除单词" << endl << "4.修改单词" << endl;cout << "5.单词展示" << endl << "6.退出程序" << endl;int choice;cin >> choice;switch (choice){case 1: {string s;string tran;cout << "请输入单词：";cin >> s;cout << "请输入汉译：";cin >> tran;if (!is_lawful(s)){cout << "输入不合法！！！" << endl;system("pause");system("cls");break;}if (search(s, root, 0, false)){cout << "单词已存在！！！" << endl;system("pause");system("cls");break;}fstream file("word.txt", ios::app);if (file.fail()){cout << "word.txt打开失败！！！" << endl;exit(0);}file << s << ' ' << tran << '\n';file.close();add(tran, s, root, 0);cout << "添加成功！！！" << endl;system("pause");system("cls");break;}case 2: {cout << "请输入要查找的单词：";string s;cin >> s;if (!is_lawful(s)){cout << "输入不合法！！！" << endl;system("pause");system("cls");break;}if (search(s, root, 0, true)){cout << "单词存在。" << endl;}else{cout << "未找到！！！" << endl;}system("pause");system("cls");break;}case 3: {string s;cout << "请输入要删除的单词：";cin >> s;if (!is_lawful(s)){cout << "输入不合法！！！" << endl;system("pause");system("cls");break;}if (!search(s, root, 0, false)){cout << "单词不存在！！！" << endl;system("pause");system("cls");break;}delete_(s,root,0);fstream file("word.txt", ios::trunc | ios::out);sort(root, -1);file.close();cout << "删除成功！！！" << endl;system("pause");system("cls");break;}case 4: {string s1, s2;while (1){cout << "请输入要修改的单词：";cin >> s1;if (!is_lawful(s1)){cout << "输入不合法！！！" << endl;system("pause");system("cls");continue;}if (!search(s1, root, 0, false)){cout << "单词不存在！！！" << endl;system("pause");system("cls");continue;}break;}string tran;while (1){cout << "请输入写改成什么单词：";cin >> s2;cout << "汉译：";cin >> tran;if (!is_lawful(s2)){cout << "输入不合法！！！" << endl;system("pause");system("cls");continue;}break;}delete_(s1, root, 0);add(tran, s2, root, 0);fstream file("word.txt", ios::trunc | ios::out);sort(root, -1);file.close();cout << "修改成功！！！" << endl;system("pause");system("cls");break;}case 5: {show(root, -1);system("pause");system("cls");break;}case 6: {return;}}}
}
int main()
{initialize();run();return 0;
}

[运行结果]