大二上学期的数据结构课设的一道题让我们实现单词接龙，如今已经大三上了，之前学的东西拿出来整理一下，顺便分享给有需要的人， 由于代码比较长，打包放在github仓库：https://github.com/JiannBai/words-solitaire。
结合数据结构课程的学习内容，设计并完成一个单词接龙游戏。游戏开始 前，根据预先设定的词典，建立合理的搜索结构。游戏开始后，根据用户输入 单词的终止字符，从搜索结构中选择以该字符作为起始字符的单词并提供给用 户。游戏结束后，统计用户参与的接龙次数和得分。
游戏开始前：能够从文本文件中读取单词信息，并设计合理的结构保存单词数据。在文本读取过程中，能够对重复的单词进行有效甄别，确保系统中单词的唯一性。
游戏过程中：支持用户输入单词，自动判别单词的结尾字符，并从现有单 词中快速查找所有以该字符开始的单词，显示在屏幕上供用户选择。给出的参 考单词不能与已有的单词重复，用户也可以输入提示单词范围之外的其他单词。
设计合理的结构，记录用户每次选择接龙的单词。如果系统找不到满足条件的单词，游戏自动结束。用户也可以手动终止游戏。
游戏结束后：统计用户参与接龙的单词总数，并根据游戏顺序，在屏幕上依次显示所有参与接龙的单词。
2、设计思想 2.1总体思路2.1.1字典树作为底层的存储单词的结构，具有以下功能：
插入单词
查找单词
查找所有公共前缀的单词
删除单词
返回前缀尾字母结点
2.1.2设计一个words类利用字典树的存储功能对接龙功能进行封装，如
得到两个单词的重复部分
利用该重复部分作为前缀查找所有符合接龙规则的单词
对接龙单词的得分根据不同规则排序
记录已经接龙的单词并确保其不会重复出现
改变单词库、接龙规则、得分规则等
2.1.3.设计控制ui页面的类（这里不作为关注对象）用来控制交互操作。
动态记录得分
动态显示接龙单词
更换单词库
错误提示
特点：
根结点不包含任何字母；
其余结点仅包含一个字母；
优点：
利用串的公共前缀，方便寻找接龙单词；
搜索的时间复杂度低（O（n)）,仅与单词长度有关。
存储结构不因单词量的增加而发生明显变化，其所消耗内存上限只与单词长度有关。
缺点：
消耗存储空间较大，当单词数较少时，存在较多冗余空间的消耗
在本程序中每个节点对应一个结构体，该字典树的UML类图表示为：
整个程序操作流程如下：
解决方案：先设计结点结构体，然后进行字典树功能接口的设计（参数、返回类型），进而对各个功能进行详细实现。
4.2 搜索所有前缀单词等功能的实现解决方案：利用递归将所有单词找到存储在一个字符串中，单词与单词之间用'#'隔离。
4.3 接龙功能的抽象解决方案：在word类中，实现得到所有前缀单词的函数、得到单词重复部分的函数、计算得分的函数、排序函数，然后对其进行组装进而实现单词接龙的基本函数接口。
5、算法分析 5.1、存储结构字典树能够存储所有单词的前缀，易于实现单词的前缀查找搜索，且当前缀长度不固定时，搜索的时间复杂度具有很大的优势。
字典树对单个单词的搜索、删除、插入的时间复杂度为O(n),n为单词长度，时间复杂度较低。
字典树存在一定的冗余存储空间消耗，其空间复杂度最差情况为O（26^n），算是一种空间换时间的存储结构。
由于存在较大的词库（10万单词）并且不需要单词的顺序固定，在考虑到游戏的流畅性，使用快速排序这种不稳定但是平均时间复杂度较低的算法（为O(nlog(n))）
6、代码由于代码比较长，打包放在github仓库：https://github.com/JiannBai/words-solitaire，下面给出部分核心代码。
6.1 字典树.h
#ifndef TRIETREE_H
#define TRIETREE_H
#include#include#includestruct TrieNode
{
QChar ch;//该节点存储的字符
TrieNode *children[27];//
bool is_word;//是否为一个单词
qint8 childrenNums;
TrieNode():ch('#'),is_word(false),childrenNums(0){
for(int i=0;i<27;++i)
{
children[i]=nullptr;
}
}
};
class TrieTree : public QObject
{
Q_OBJECT
public:
explicit TrieTree(QObject *parent = nullptr);
explicit TrieTree(const QString &fileName,QObject *parent = nullptr);
bool insert(QChar *word);
bool find_string(const QString &s,bool isEliminate=true);
//找到相同前缀的单词
std::shared_ptrfindWordsWithSuffix(const QString &prefix,int nums);
bool delet(const QString &s);
bool insert(const QString &s);
QString getPrefixWords(const QString &prefix);
//随机得到一个单词
QString get_a_random_word(int d_time=0);
private:
TrieNode *root;//根节点
int nums;//叶节点数量
QString words_list;//以'#'为分隔符，存储公共前缀单词
TrieNode* startWith(TrieNode *tempNode,const QString prefix);
void DFS(const TrieNode* tempRoot,QString prefix);
signals:
};
#endif // TRIETREE_H .cpp
#include "trietree.h"
#include#include#include#include#includeTrieTree::TrieTree(QObject *parent) : QObject(parent)
{
root=new TrieNode();
}
TrieTree::TrieTree(const QString &fileName,QObject *parent) : QObject(parent),root(new TrieNode),nums(0),words_list("")
{
QString wordsPath=fileName;
//读取单词文件,相对路径
QFile wordsFile(wordsPath);
//打开文件(只读模式）
wordsFile.open(QFileDevice::ReadOnly);
//读取文件内容，一行一行读
QString wordsArray;
int charToInt;
TrieNode *tempNode=nullptr;
if(wordsFile.isOpen())
{
while(!wordsFile.atEnd())//读取文件中的每一行
{
wordsArray=QString(wordsFile.readLine());
//this->insert(wordsArray);
tempNode=root;
for(QChar c:wordsArray)//遍历每一个单词构建字典树
{
charToInt=c.toLatin1();//应该不会改变c的类型
if(charToInt>96 && charToInt<123)//小写字母
{
//qchar无法直接转为int 或者qint
if(tempNode->children[charToInt-97]==nullptr)
{
TrieNode *newTrieNode=new TrieNode;
newTrieNode->ch=c;
tempNode->children[charToInt-97]=newTrieNode;//将新节点连接在当前节点对应的指针上
++(tempNode->childrenNums);//该节点的孩子数+1
tempNode=newTrieNode;//孩子结点变为当前节点
newTrieNode=nullptr;
}
else
{
tempNode=tempNode->children[charToInt-97];
}
}
else if(charToInt>64 && charToInt<91)
{
if(tempNode->children[charToInt-65]==nullptr)
{
TrieNode *newTrieNode=new TrieNode;
newTrieNode->ch=c;
tempNode->children[charToInt-65]=newTrieNode;//将新节点连接在当前节点对应的指针上
++(tempNode->childrenNums);//该节点的孩子数+1
tempNode=newTrieNode;//孩子结点变为当前节点
newTrieNode=nullptr;
}
else
{
tempNode=tempNode->children[charToInt-65];
}
}
else if(charToInt==45)//连接符'-'
{
if(tempNode->children[26]==nullptr)
{
TrieNode *newTrieNode=new TrieNode;
newTrieNode->ch=c;
tempNode->children[26]=newTrieNode;//将新节点连接在当前节点对应的指针上
++(tempNode->childrenNums);//该节点的孩子数+1
tempNode=newTrieNode;//孩子结点变为当前节点
newTrieNode=nullptr;
}
else
{
tempNode=tempNode->children[26];
}
}
}
tempNode->is_word=true;
++this->nums;
}
}
else
{
qDebug()<<"open fail!"<<'\n';
}
wordsFile.close();
}
//查找某个单词是否在字典树中,isEliminate表示是否提出该单词，默认为真
bool TrieTree::find_string(const QString &s,bool isEliminate)
{
TrieNode *tempNode=root;
char ch;
for(QChar c:s)
{
ch=c.toLatin1();
//若当前节点为空，则该单词一定没有
if(tempNode==nullptr) return false;
//若不为空
else if(ch>='a' && ch<='z')
{
//若当前节点的下一节点不为空，但此节点该字符为'#'
if(tempNode->children[ch-'a']!=nullptr && tempNode->children[ch-'a']->ch=='#')
{
return false;
}
//将当前节点下移
tempNode=tempNode->children[ch-'a'];
}
else if(ch>='A' && ch<='Z')
{
if(tempNode->children[ch-'A']!=nullptr && tempNode->children[ch-'A']->ch=='#')
{
return false;
}
tempNode=tempNode->children[ch-'A'];
}
else if(ch=='-')
{
if(tempNode->children[26]!=nullptr && tempNode->children[26]->ch=='#')
{
return false;
}
tempNode=tempNode->children[26];
}
}
//判断结尾节点是否为一个单词的末尾
if(tempNode!=nullptr && tempNode->is_word==true)
{
if(isEliminate) tempNode->is_word=false;
return true;
}
return false;
}
//若找到，返回最后一个字母的节点
TrieNode* TrieTree::startWith(TrieNode *tempNode,const QString prefix)
{
//将指针移到前缀的最后一个字符上
char ch;
for(QChar c:prefix)
{
ch=c.toLatin1();
if(tempNode!=nullptr && ch>='a' && ch<='z')
{
tempNode=tempNode->children[ch-'a'];
}
else if(tempNode!=nullptr && ch>='A' && ch<='Z' )
{
tempNode=tempNode->children[ch-'A'];
}
else if(tempNode!=nullptr && ch=='-' )
{
tempNode=tempNode->children[26];
}
else
{
qDebug()<<"无该前缀，查询失败！"<<'\n';
tempNode=nullptr;
return tempNode;
}
}
return tempNode;
}
//传入一个节点，以该节点为根节点做深度遍历,找到所有公共前缀的单词，存入words_list
//贼难写这里
void TrieTree::DFS(const TrieNode* tempRoot,QString prefix)
{
if(tempRoot==nullptr) return;
//每个单词以‘#‘为分隔符
if(tempRoot->is_word)
{
this->words_list.push_back(prefix+'#');
}
//若为叶节点，则返回
if(tempRoot->childrenNums==0) return;
//从根节点往下深度优先遍历
for(int i=0;i<27;++i)
{
if(tempRoot->children[i]!=nullptr)
{
//深度优先遍历
DFS(tempRoot->children[i],prefix+tempRoot->children[i]->ch);
}
}
}
//返回该前缀的所有单词，以字符串的形式，各单词以'#'分隔
QString TrieTree::getPrefixWords(const QString &prefix)
{
//每次开始清空字符串单词
this->words_list=NULL;
TrieNode *tempNode=root;
tempNode=startWith(tempNode,prefix);
if(tempNode==nullptr)
{
return words_list;
}
;//没有该前缀开头的单词，返回空
DFS(tempNode,prefix);
return this->words_list;
}
//插入单词
bool TrieTree::insert(const QString &s)
{
TrieNode *tempNode = root;
if(find_string(s,false))
{
qDebug()<<"该字符串已经存在！"<<'\n';
return 0;
}
else
{
int charToInt;
for(QChar c:s)//遍历每一个单词构建字典树
{
charToInt=c.toLatin1();//应该不会改变c的类型
if(charToInt>96 && charToInt<123)//小写字母
{
//qchar无法直接转为int 或者qint
if(tempNode->children[charToInt-97]==nullptr)
{
TrieNode *newTrieNode=new TrieNode;
newTrieNode->ch=c;
tempNode->children[charToInt-97]=newTrieNode;//将新节点连接在当前节点对应的指针上
++(tempNode->childrenNums);//该节点的孩子数+1
tempNode=newTrieNode;//孩子结点变为当前节点
newTrieNode=nullptr;
}
else
{
tempNode=tempNode->children[charToInt-97];
}
}
else if(charToInt>64 && charToInt<91)
{
if(tempNode->children[charToInt-65]==nullptr)
{
TrieNode *newTrieNode=new TrieNode;
newTrieNode->ch=c;
tempNode->children[charToInt-65]=newTrieNode;//将新节点连接在当前节点对应的指针上
++(tempNode->childrenNums);//该节点的孩子数+1
tempNode=newTrieNode;//孩子结点变为当前节点
newTrieNode=nullptr;
}
else
{
tempNode=tempNode->children[charToInt-65];
}
}
else if(charToInt==45)//连接符'-'
{
if(tempNode->children[26]==nullptr)
{
TrieNode *newTrieNode=new TrieNode;
newTrieNode->ch=c;
tempNode->children[26]=newTrieNode;//将新节点连接在当前节点对应的指针上
++(tempNode->childrenNums);//该节点的孩子数+1
tempNode=newTrieNode;//孩子结点变为当前节点
newTrieNode=nullptr;
}
else
{
tempNode=tempNode->children[26];
}
}
}
tempNode->is_word=true;
++this->nums;
return 1;
}
}
//大小写问题，存进去有的本该大写，但是与小写的为公共前缀
bool TrieTree::delet(const QString &s)
{
TrieNode *tempNode = root;
char ch;
for(QChar c:s)
{
ch=c.toLatin1();
if(tempNode!=nullptr && ch>='a' && ch<='z')
{
tempNode=tempNode->children[ch-'a'];
}
else if(tempNode!=nullptr && ch>='A' && ch<='Z' )
{
tempNode=tempNode->children[ch-'A'];
}
else if(tempNode!=nullptr && ch=='-' )
{
tempNode=tempNode->children[26];
}
else
{
qDebug()<<"无该单词，删除失败！"<<'\n';
return false;
}
}
//最后的结点若是单词，则删除
if(tempNode->is_word==true) tempNode->is_word=false;
else return false;
return true;
}
QString TrieTree::get_a_random_word(int d_time)
{
//随机种子
srand(time(NULL)+d_time);
TrieNode *tempNode=root;
QString word;
while(!tempNode->is_word)
{
int random_number=rand()%26;;
if(tempNode->children[random_number] && tempNode->children[random_number]->ch!='#')
{
word.push_back(tempNode->children[random_number]->ch);
tempNode=tempNode->children[random_number];
}
}
return word;
} .h
#ifndef WORD_H
#define WORD_H
#include#include#include#include"trietree.h"
struct wordsWithGoal
{
QString words="";
int goal=-1;
int next_words_num=999999;
bool is_depend_less_word=false;
bool operator>(const wordsWithGoal &other)
{
if(!is_depend_less_word)return this->goal>other.goal;
else return this->next_words_num>other.next_words_num;
}
bool operator<(const wordsWithGoal &other)
{
if(!is_depend_less_word)return this->goalnext_words_num=(const wordsWithGoal &other)
{
if(!is_depend_less_word)return this->goal>=other.goal;
else return this->next_words_num>=other.next_words_num;
}
bool operator<=(const wordsWithGoal &other)
{
if(!is_depend_less_word)return this->goal<=other.goal;
else return this->next_words_num<=other.next_words_num;
}
void operator=(const wordsWithGoal &other)
{
this->goal=other.goal;
this->words=other.words;
this->is_depend_less_word=other.is_depend_less_word;
this->next_words_num=other.next_words_num;
}
};
class word : public QObject
{
Q_OBJECT
public:
explicit word(QObject *parent = nullptr);
//设置单词文本
void setWordsTxt(const QString &fileName);
//初始化游戏页面,随机初始化一个单词,未实现
QString initial_word(int d_time=0);
//查找某一单词是否存在于词库中，若存在则返回该单词，否则返回空字符串；
QString find(const QString &word,bool is_useless_words=true);
//字符串后几位的匹配,按接龙匹配程度返回匹配到的前m个合法单词
std::shared_ptrwords_matching(QString prefix,int num=20);
//返回该单词和接龙单词的单词重叠部分
QString get_prefix(const QString &pred_word,const QString & connect_word);
//设置规则
void setRule(const bool &is_overlap_goal);
//计算得分
int get_goals(QString prifix,QString word);
//得到该单词的后续单词数
int get_next_words_num(QString word);
void setOrderRule(const bool &is_depend_less_words);
//存储单词的数据结构
TrieTree *wordsTree=nullptr;
//接过龙的单词
TrieTree *UselesswordsTree;
private:
//是否使用重叠得分规则
bool is_overlap_goal=false;
//排序会泽
bool is_depend_less_words=false;
//快速排序
void quick_sort(wordsWithGoal *&connectWords,int begin,int all_words_number);
signals:
//查找某个单词用于接龙的信号
void find_input_word();
//游戏开始信号
void start_game();
};
#endif // WORD_H .cpp
#include "word.h"
#include"trietree.h"
#include#includeword::word(QObject *parent) : QObject(parent),UselesswordsTree(new TrieTree),is_overlap_goal(false)
{
}
//用于为存储结构放入单词
void word::setWordsTxt(const QString &fileName)
{
//若该树为空
if(this->wordsTree==nullptr) this->wordsTree=new TrieTree(fileName);
//若该树不为空
else
{
delete this->wordsTree;
wordsTree=new TrieTree(fileName);
}
}
//初始化游戏页面,随机初始化一个单词
QString word::initial_word(int d_time)
{
return this->wordsTree->get_a_random_word(d_time);
}
//设置规则
void word::setRule(const bool &is_overlap_goal)
{
if(is_overlap_goal) this->is_overlap_goal=true;
else this->is_overlap_goal=false;
}
//词库中是否有该单词，有则返回，没有返回空字符串
QString word::find(const QString &word,bool is_useless_words)
{
//查询剔除后的单词树
if(is_useless_words)
{
if(this->UselesswordsTree->find_string(word,false))
{
return word;
}
else return "";
}
else
{
if(this->wordsTree->find_string(word))
{
return word;
}
else return "";
}
}
//得到两个接龙单词大重叠字符串(暴力搜索，可改用KMP)
QString word::get_prefix(const QString &pre_word,const QString & connect_word)
{
int pre_length=pre_word.length();
int con_lenght=connect_word.length();
int min_length=pre_lengthmax_str_num) max_str_num=temp_str_num;
}
return connect_word.mid(0,max_str_num);
}
//返回前num个接龙单词和对应的分数
std::shared_ptrword::words_matching(QString prefix_words,int num)
{
QVectorallPrifixWords;
//所有符合规则的单词
QString allConnectWords;
if(!is_overlap_goal)allConnectWords=this->wordsTree->getPrefixWords(prefix_words[prefix_words.length()-1]);
else
{
int pre_word_length=prefix_words.length();
for(int i=1;iwordsTree->getPrefixWords(prefix_words.mid(i,pre_word_length-1));
}
}
//得到所有符合条件的单词
QString temp_string;
for(QChar ch:allConnectWords)
{
if(ch=='#')
{
allPrifixWords.push_back(temp_string);
temp_string="";
continue;
}
else temp_string.push_back(ch);
}
//将所有公共前缀单词结构体存入自己的数组中
int all_words_number=allPrifixWords.length();//全部符合规则的单词
wordsWithGoal *connectWords= new wordsWithGoal[all_words_number];
for(int i=0;iget_goals(prefix_words,allPrifixWords[i]);
connectWords[i].next_words_num=this->get_next_words_num(allPrifixWords[i]);
connectWords[i].is_depend_less_word=this->is_depend_less_words;
}
//排序
quick_sort(connectWords,0,all_words_number-1);
//存入要返回的数组中（智能指针）
std::shared_ptrresule_words(new wordsWithGoal[num]);
if(!is_depend_less_words)//按得分由高到低
{
num=numall_words_number-num;--i)
{
resule_words[all_words_number-i]=connectWords[i-1];
}
}
else
{
for(int i=all_words_number;i>0;--i)
{
resule_words[all_words_number-i]=connectWords[i-1];
}
}
}
delete [] connectWords;
connectWords=nullptr;
return resule_words;
}
//计算一个接龙单词的得分
int word::get_goals(QString prefix_word,QString word)
{
//若是规则一
if(!this->is_overlap_goal)
{
if(prefix_word[prefix_word.length()-1]==word[0])return word.length();
else return 0;
}
else
{
return this->get_prefix(prefix_word,word).length()*word.length();
}
}
//快速排序 不稳定
void word::quick_sort(wordsWithGoal *&a,int l,int r)
{
if (l >= r) return;
int t1 = l, t2 = r;
wordsWithGoal key = a[(l + r) / 2];
do {
while (a[t1] >key) t1++;
while (a[t2]< key) t2--;
if (t1<= t2)
{
wordsWithGoal temp=a[t1];
a[t1]=a[t2];
a[t2]=temp;
t1++,t2--;
}
} while (t1<= t2);
quick_sort(a,l, t2);
quick_sort(a,t1, r);
}
int word::get_next_words_num(QString word)
{
int num=0;
if(!this->is_overlap_goal)
{
QString s=this->wordsTree->getPrefixWords(word[word.length()-1]);
for(QChar c:s)
{
if(c=='#')++num;
}
}
else
{
int pre_word_length=word.length();
QString s;
for(int i=1;iwordsTree->getPrefixWords(word.mid(i,pre_word_length-i));
}
for(QChar c:s)
{
if(c=='#')++num;
}
}
return num;
}
void word::setOrderRule(const bool &is_depend_less_words)
{
this->is_depend_less_words=is_depend_less_words;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
