新河网站建设顾问页面设计时最好

新河网站建设顾问,页面设计时最好,2021不良正能量免费网站app,免费建设微网站制作【题目描述】在进行文法分析的时候#xff0c;通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度#xff0c;通常都画出与单词列表所对应的单词查找树#xff0c;其特点如下#xff1a;1#xff0e;根结点不包含字母#xff0c;除根结点外每一个结点…【题目描述】在进行文法分析的时候通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度通常都画出与单词列表所对应的单词查找树其特点如下1根结点不包含字母除根结点外每一个结点都仅包含一个大写英文字母2从根结点到某一结点路径上经过的字母依次连起来所构成的字母序列称为该结点对应的单词。单词列表中的每个单词都是该单词查找树某个结点所对应的单词3在满足上述条件下该单词查找树的结点数最少。4例如图3-2左边的单词列表就对应于右边的单词查找树。注意对一个确定的单词列表请统计对应的单词查找树的结点数包含根结点。【输入】为一个单词列表每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成长度不超过63个字母 。文件总长度不超过32K至少有一行数据。【输出】仅包含一个整数该整数为单词列表对应的单词查找树的结点数。【输入样例】A AN ASP AS ASC ASCII BAS BASIC【输出样例】131. 关于那个“文件总长度 32K”题目给的限制很有意思单词长度不超过 63。文件总长度不超过 32K。第一眼看到 63下意识觉得“这题很小”随手开了个 tre[2000]。结果仔细一算不对劲32K 是多少在C里一个char就是 1 字节。32K32*102432768字节。这意味着最坏情况下比如所有单词都长得不一样这棵树得存 3 万多个字符。如果要建树数组至少得开到 40000 才稳。要是按 2000 开读到第 2001 个字符的时候程序直接就炸了越界。教训以后看到 32K、64M 这种单位第一反应必须是换算成字节数。2. 为什么用 vector 存 Trie通常 Trie 树节点是这样写的struct node { char data; node* next[26]; // 或者 int next[26] };这样写查找快但如果节点很多且分叉少空间浪费严重。改用vector邻接表写法struct node { char data; vectorint son; // 只存存在的儿子下标 } tre[50000]; // 数组一定要开够虽然查找时要遍历son数组多一个 for 循环但省内存而且代码写起来其实就是个 DFS很符合直觉。3. 最终代码逻辑很简单拿着字符串当前字符a[k2]去当前节点k1的son列表里找。找到了 - 递归下一层。找不到 -push_back一个新节点把ind传进去继续递归。#include bits/stdc.h #include vector using namespace std; struct node{ char data;//记录该结点是哪个字母 vectorint son;//存放该结点的儿子在树中的下标 }tre[50000];//要开大一点题目中说文件总长度不超过32K32k三万多字节所以开五万 int cnt;//节点个数 string a; //让tre[1]存放root int len; int ind1;//现在已经添加了ind个节点初始为1因为根节点为root不包含任何字母 void dfs(int k1,int k2){//现在遍历到树第k1个节点字符串遍历到第k2个位置 if(k2len) return; bool flag0; for(int i0;itre[k1].son.size();i){//遍历该节点所有孩子如果和字符串该位置的字母有对应就去找下一个对应 if(tre[tre[k1].son[i]].dataa[k2]){//如果对应上了就进入下一轮遍历 dfs(tre[k1].son[i],k21); flag1; break;//对应上了就不需要再找了退出此轮循环 } } if(flag0){//目前没有能匹配上的 tre[ind].dataa[k2];//把a[k2]创建一个新节点然后储存起来 tre[k1].son.push_back(ind);//把a[k2]节点存进父节点的孩子里就是拼接上去 dfs(ind,k21); } } int main(){ while(cina){ lena.size();//字符串长度 //建树 //长度不超过63个字母 即每次读进来的单词最多63个字符 dfs深度最多63层 dfs(1,0);//从树的第1个节点开始遍历从a字符串的a[0]开始遍历 } coutind; }4. 总结空间换算char是 1 字节题目给多少 K 就乘多少 1024数组宁大勿小。Vector 写法用vector代替定长数组写 Trie 是完全可行的特别适合不想算next[26]或者字符集不只是 26 个字母的情况。下标坑vector存的是下标取数据时记得套两层tre[tre[k1].son[i]]这里最容易晕。