对广义表的链表表示的深度优先遍历的实现要点是,从广义表的附加头节点开始向后顺序访问对原子节点访问结束后递进至下一节点每遇到子表的附加头节点就进入该子表所在的下一层继续向下遍历在下一层的子表中同样也是访问并经过原子节点一遇到子表附加头节点就立即向下进入子表继续遍历就这样不断向下遍历最终进入空表或没有子表的非空表并遍历完成后就立即回溯至上一层子表并按照上述规则继续向后遍历子表遍历完成就再回溯至上上层子表然后继续遍历就这样反复不断地回溯和向下遍历直到最后一次回溯至原广义表并向后完成遍历后整个广义表的深度优先遍历也就结束了。利用广义表的深度优先遍历可以完成诸多有实用价值的运算如找出所有子表及对应的深度长度在广义表中的位置求出子表数目找出最长最短子表深度最深子表找出所有空表的深度位置数目在广义表中搜索给定关键字找出包含关键字的所有子表及其在子表中的位置找出所有空表以及不包含子表的子表确定各个子表左右括号的起始终止位置以及序数找出给定深度的所有子表等等。下面就来讨论以上部分运算的实现1找出所有子表及对应的深度长度在广义表中的位置和子表的数目用栈实现栈节点保存子表附加头节点的指针,及已统计到的子表表元素数目。遍历过程中每遇到子表附加头节点就把子表对应栈节点入栈遍历完子表后将对应栈节点出栈,遇到原子项将原子项所在子表的栈节点的表元素计数变量加一遇到下一层子表的附加头节点也要将本层子表的栈节点计数变量加一。最后遍历完广义表后栈中只剩下广义表本身对应的栈节点取出其中指针赋予指针变量使其指向广义表附加头节点然后出栈就完成了遍历。遍历过程中需要使用指针变量指向并访问广义表各个链表节点指针的动作方式和深度优先遍历要点所述是一致的指针从子表表尾继续前进时会成为空指针此时就遍历完子表栈顶节点的计数变量就是子表长度栈大小就是子表深度栈中节点序列指出了子表在广义表中的位置栈顶节点指针就是指向子表附加头节点的指针利用该指针可输出子表。至于子表数目用计数变量进行简单统计就可以得到。具体C代码实现如下(本文所有代码在visual studio 2017编译环境下调试通过)#include stdafx.h #include iostream #include vector #include string using namespace std; struct Gen //广义表链表表示的节点结构体类型 { int utype; //节点类型,0表示广义表附加头结点,1表示子表附加头结点,2表示原子数据项 union { int ref; //联合体类型,utype0时ref为引用计数,1时hlink为指向子表第一个节点指针,2时value为原子项的数据值 struct Gen *hlink; char value; }info; //联合体变量info struct Gen *tlink; //指向该节点所在链表下一节点的指针 Gen(int u); Gen(int u, char v); //构造函数声明 }; Gen::Gen(int u) :utype(u), tlink(nullptr) //utype0或1时初始化节点 { if (u 0) info.ref 0; else info.hlink nullptr; } Gen::Gen(int u, char v) :utype(u), tlink(nullptr) //utype2,valuev时初始化节点 { info.value v; } class Gennode //深度优先遍历广义表链表表示时辅助遍历过程的类型 { public: int numnode; //子表中当前已统计的节点数,遍历完子表后即为子表长度 Gen *ptr; //指向子表附加头节点的指针 Gennode(Gen *p) :ptr(p), numnode(0) {} //初始化 }; void output(vectorGennode stack); //输出stack栈中存放的子表位置信息 void suboutput(Gen *head); //输出head指向的子表 Gen * strtogen(); //将字符串形式的广义表转换为链表表示 int main() { int depth 0; int maxdepth 0; //子表深度最大深度初始化 int flag 0; int sign 0; //flag用于在找到子表后标志当前子表是非空表非空子表还是为空的广义表本身,sign标志当前子表是否还有子表,0没有1有 int subcount 0; //子表计数 int emptycount 0; //空表计数 bool TF true; //true递进至新的一层,false从上一层回溯至本层 vectorGennode stack; //辅助遍历过程的栈 Gen *ptrstrtogen();//ptr初始化为指向广义表附加头节点的指针 while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) //ptr指向广义表或子表附加头节点 { if (TF true) //新进至本层 { sign 0; depth; if (ptr-utype 0) //从广义表附加头节点开始 { Gennode temp(ptr); stack.push_back(temp); //附加头节点指针入栈 flag 0; ptr ptr-tlink; //ptr递进至下一节点 } else //到达本层子表附加头节点 { stack[stack.size() - 1].numnode; //子表为表元素所以将本层子表的已统计节点数加一 Gennode temp(ptr); stack.push_back(temp); //子表附加头节点入栈 flag 2; ptr ptr-info.hlink; //递进至子表第一个表元素 } } else { if (ptr-utype 0) //ptr指针回溯至广义表附加头节点遍历完成退出 break; else //从子表回溯至本层上该子表的附加头节点 { sign 1; ptr ptr-tlink; //继续递进至本层下一下一节点 flag 1; TF true; } } } else { if (ptr nullptr) //找到一个子表 { subcount; if (flag 2) //找到一个子空表 { emptycount; cout 第 subcount 个子表,为空表:()endl; //输出子表信息 cout 深度: depth 长度: 0 endl; cout 位置: endl; output(stack); //栈中存有完整位置信息输出 } else { if (flag 1) { //找到一个非空子表 cout 第 subcount 个非空子表:; suboutput(stack[stack.size() - 1].ptr); //输出该子表 cout 深度: depth 长度: stack[stack.size() - 1].numnode endl; cout 位置: endl; if (stack[stack.size() - 1].ptr-utype 0) { //当前非空子表为广义表本身, cout 该非空子表为广义表本身endl; } else { //当前非空子表为真子表栈中存有完整位置信息,输出 output(stack); } } else { emptycount; //找到子空表,即为广义表本身,输出之 cout 第 subcount 个子表,为空表:() endl; cout 深度: depth 长度: 0 endl; cout 位置: endl; cout 该子空表为广义表本身 endl; } } if (sign 0) //该子表为空表或没有子表的子表 { if (depth maxdepth) maxdepth depth; //比较确定最大深度 } depth--; ptr stack[stack.size() - 1].ptr; //ptr回溯至上一层 stack.pop_back(); TF false; } else //找到本层的一个原子数据项 { stack[stack.size() - 1].numnode; //本层子表节点计数加一 ptr ptr-tlink; //ptr向后递进 flag 1; } } } cout 共有 subcount 个子表,其中有 emptycount 个空表 endl; //输出子表数目空表数目广义表深度 cout 广义表深度: maxdepthendl; return 0; } void output(vectorGennode stack) { for (auto i stack.begin(); i ! stack.end() - 1; i) //遍历stack栈输出子表位置信息 { if (i stack.begin()) { cout 广义表的第 (*i).numnode 个表元素; } else { cout 的第 (*i).numnode 个表元素; } } cout endl; } void suboutput(Gen *head) { Gen *ptr head; bool TF true; vectorGen * stack; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) //注意 { if (TF true) { stack.push_back(ptr); cout (; if (ptr-utype 0) //注意 { ptr ptr-tlink; } else { ptr ptr-info.hlink; } } else { if (ptr head) break; else { ptr ptr-tlink; TF true; } } } else { if (ptr nullptr) { cout ); ptr stack[stack.size() - 1]; if (ptr-utype ! 0 ptr-tlink ! nullptr) //注意 cout ,; stack.pop_back(); TF false; } else { cout ptr-info.value; ptr ptr-tlink; if (ptr ! nullptr) cout ,; } } } cout endl; } Gen * strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen *ptr nullptr; vectorGen * stack; bool TF; for (auto i glist.cbegin(); i ! glist.cend(); i) { if (*i () { if (i glist.cbegin()) { ptr new Gen(0); stack.push_back(ptr); TF true; } else { Gen *temp new Gen(1); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } stack.push_back(temp); TF true; ptr temp; } } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; } else { if (*i ! ,) { Gen *temp new Gen(2, *i); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } ptr temp; } } } } return ptr; }运行示例以上代码调用了两个函数suboutput和strtogen分别用来输出广义表链表表示对应的字符串表示和将字符串形式的广义表转化为链表表示(2)在广义表中搜索给定关键字找出包含关键字的所有子表及其在子表中的位置:这里需要在Gennode类型中新增一个vector对象position用来存放关键字在子表中的位置,每在子表中找到一个关键字就要把其位置存入position尾端。遍历子表后根据position是否为空可断定子表是否含关键字不为空的话顺序输出关键字位置即可#include stdafx.h #include iostream #include vector #include string using namespace std; struct Gen { int utype; union { int ref; struct Gen *hlink; char value; }info; struct Gen *tlink; Gen(int u); Gen(int u, char v); }; Gen::Gen(int u) :utype(u), tlink(nullptr) { if (u 0) info.ref 0; else info.hlink nullptr; } Gen::Gen(int u, char v) :utype(u), tlink(nullptr) { info.value v; } class Gennode { public: int numnode; Gen *ptr; vectorint position; Gennode(Gen *p) :ptr(p), numnode(0) {} }; void output(vectorGennode stack); void suboutput(Gen *head); Gen * strtogen(); int main() { int depth 0; int flag 0; int subcount 0; //含指定值的子表计数 bool TF true; char key; //待搜索的关键字 vectorGennode stack; Gen *ptr strtogen();//ptr初始化为指向广义表附加头节点的指针 cout 请输入要搜索的值: endl; //输入要搜索的关键字 cin key; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) { if (TF true) { depth; if (ptr-utype 0) { Gennode temp(ptr); stack.push_back(temp); flag 0; ptr ptr-tlink; } else { stack[stack.size() - 1].numnode; Gennode temp(ptr); stack.push_back(temp); flag 2; ptr ptr-info.hlink; } } else { if (ptr-utype 0) //搜索完毕退出 break; else { ptr ptr-tlink; flag 1; TF true; } } } else { if (ptr nullptr) { if (flag ! 2 flag!0) //当前找到的子表非空这样才可能包含关键字 { if (stack[stack.size() - 1].position.size()!0) //当前非空子表包含关键字 { subcount; cout 第 subcount 个含 key 的非空子表:; suboutput(stack[stack.size() - 1].ptr); //输出含关键字的非空子表 cout key 是其中第; //输出关键字在非空子表中的位置 for (auto i stack[stack.size() - 1].position.begin(); i stack[stack.size() - 1].position.end(); i) { if (i stack[stack.size() - 1].position.begin()) cout *i; else cout , *i; } cout 个表元素 endl; cout 该表深度: depth 长度: stack[stack.size() - 1].numnode endl; cout 位置: endl; if (stack[stack.size() - 1].ptr-utype 0) { //当前非空子表为广义表本身 cout 该非空子表为广义表本身 endl; } else { //当前非空子表为真子表栈中存有完整位置信息,输出之 output(stack); } cout endl; } } depth--; ptr stack[stack.size() - 1].ptr; stack.pop_back(); TF false; } else { stack[stack.size() - 1].numnode; if (ptr-info.value key) //搜索到关键字 { stack[stack.size() - 1].position.push_back(stack[stack.size() - 1].numnode); //关键字在其所在子表的下一位置压入记录子表关键字位置的stack栈顶的position栈 } ptr ptr-tlink; flag 1; } } } cout 共有 subcount 个子表含有 key endl; return 0; } void output(vectorGennode stack) { for (auto i stack.begin(); i ! stack.end() - 1; i) { if (i stack.begin()) { cout 广义表的第 (*i).numnode 个表元素; } else { cout 的第 (*i).numnode 个表元素; } } cout endl; } void suboutput(Gen *head) { Gen *ptr head; bool TF true; vectorGen * stack; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) //注意 { if (TF true) { stack.push_back(ptr); cout (; if (ptr-utype 0) //注意 { ptr ptr-tlink; } else { ptr ptr-info.hlink; } } else { if (ptr head) break; else { ptr ptr-tlink; TF true; } } } else { if (ptr nullptr) { cout ); ptr stack[stack.size() - 1]; if (ptr-utype ! 0 ptr-tlink ! nullptr) //注意 cout ,; stack.pop_back(); TF false; } else { cout ptr-info.value; ptr ptr-tlink; if (ptr ! nullptr) cout ,; } } } cout endl; } Gen * strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen *ptr nullptr; vectorGen * stack; bool TF; for (auto i glist.cbegin(); i ! glist.cend(); i) { if (*i () { if (i glist.cbegin()) { ptr new Gen(0); stack.push_back(ptr); TF true; } else { Gen *temp new Gen(1); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } stack.push_back(temp); TF true; ptr temp; } } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; } else { if (*i ! ,) { Gen *temp new Gen(2, *i); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } ptr temp; } } } } return ptr; }(3)在广义表中搜索指定深度子表:每进入新的一层子表先检查下一层子表是否超过指定深度若超过不进入下一层子表直接跳过。每找到新子表检验深度即可#include stdafx.h #include iostream #include vector #include string using namespace std; struct Gen { int utype; union { int ref; struct Gen *hlink; char value; }info; struct Gen *tlink; Gen(int u); Gen(int u, char v); }; Gen::Gen(int u) :utype(u), tlink(nullptr) { if (u 0) info.ref 0; else info.hlink nullptr; } Gen::Gen(int u, char v) :utype(u), tlink(nullptr) { info.value v; } class Gennode { public: int numnode; Gen *ptr; Gennode(Gen *p) :ptr(p), numnode(0) {} }; void output(vectorGennode stack); void suboutput(Gen *head); Gen * strtogen(); int main() { int depth 0; int maxdepth; int flag 0; int subcount 0; int emptycount 0; bool TF true; vectorGennode stack; Gen *ptrstrtogen();//ptr初始化为指向广义表附加头节点的指针 cout 请输入指定深度: endl; //输入想要求出的相同深度子表的深度 cin maxdepth; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) { if (TF true) { if (depth maxdepth) //下一层深度大于指定深度不进入下一层继续递进至本层下一节点 { ptr ptr-tlink; flag 1; stack[stack.size() - 1].numnode; continue; } depth; if (ptr-utype 0) { Gennode temp(ptr); stack.push_back(temp); flag 0; ptr ptr-tlink; } else { stack[stack.size() - 1].numnode; Gennode temp(ptr); stack.push_back(temp); flag 2; ptr ptr-info.hlink; } } else { if (ptr-utype 0) break; else { ptr ptr-tlink; flag 1; TF true; } } } else { if (ptr nullptr) { if (depth maxdepth) //找到指定深度子表 { subcount; if (flag 2) //找到一个指定深度子空表 { emptycount; cout 第 subcount 个指定深度的子表,为空表:() endl; cout 长度: 0 endl; cout 位置: endl; output(stack); } else { if (flag 1) { //找到一个指定深度非空子表 cout 第 subcount 个指定深度的子表(非空):; suboutput(stack[stack.size() - 1].ptr); //输出之该指定深度子表 cout 长度: stack[stack.size() - 1].numnode endl; cout 位置: endl; if (stack[stack.size() - 1].ptr-utype 0) { //当前非空子表为广义表本身, cout 该非空子表为广义表本身 endl; } else { //当前非空子表为真子表栈中存有完整位置信息,输出 output(stack); } } else { emptycount; //找到指定深度子空表,即为广义表本身,输出之 cout 第 subcount 个指定深度的子表,为空表:() endl; cout 长度: 0 endl; cout 位置: endl; cout 该子空表为广义表本身 endl; } } } depth--; ptr stack[stack.size() - 1].ptr; stack.pop_back(); TF false; } else { stack[stack.size() - 1].numnode; ptr ptr-tlink; flag 1; } } } cout 共有 subcount 个指定深度的子表,其中有 emptycount 个空表 endl; return 0; } void output(vectorGennode stack) { for (auto i stack.begin(); i ! stack.end() - 1; i) { if (i stack.begin()) { cout 广义表的第 (*i).numnode 个表元素; } else { cout 的第 (*i).numnode 个表元素; } } cout endl; } void suboutput(Gen *head) { Gen *ptr head; bool TF true; vectorGen * stack; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) //注意 { if (TF true) { stack.push_back(ptr); cout (; if (ptr-utype 0) //注意 { ptr ptr-tlink; } else { ptr ptr-info.hlink; } } else { if (ptr head) break; else { ptr ptr-tlink; TF true; } } } else { if (ptr nullptr) { cout ); ptr stack[stack.size() - 1]; if (ptr-utype ! 0 ptr-tlink ! nullptr) //注意 cout ,; stack.pop_back(); TF false; } else { cout ptr-info.value; ptr ptr-tlink; if (ptr ! nullptr) cout ,; } } } cout endl; } Gen * strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen *ptr nullptr; vectorGen * stack; bool TF; for (auto i glist.cbegin(); i ! glist.cend(); i) { if (*i () { if (i glist.cbegin()) { ptr new Gen(0); stack.push_back(ptr); TF true; } else { Gen *temp new Gen(1); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } stack.push_back(temp); TF true; ptr temp; } } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; } else { if (*i ! ,) { Gen *temp new Gen(2, *i); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } ptr temp; } } } } return ptr; }(4)确定各个子表左右括号的起始终止位置以及序数需要栈position记录入栈左括号序数位置left,right分别记录左右括号序数,遇到左括号left增一,右括号right增一扫描到附加头节点即左括号时左括号序数位置进栈遍历完子表后栈顶元素存放子表左括号位置叙述右括号位置序数由right,total给出,输出即可然后出栈#include stdafx.h #include iostream #include vector #include string using namespace std; struct Gen { int utype; union { int ref; struct Gen *hlink; char value; }info; struct Gen *tlink; Gen(int u); Gen(int u, char v); }; Gen::Gen(int u) :utype(u), tlink(nullptr) { if (u 0) info.ref 0; else info.hlink nullptr; } Gen::Gen(int u, char v) :utype(u), tlink(nullptr) { info.value v; } class Gennode { public: int numnode; Gen *ptr; Gennode(Gen *p) :ptr(p), numnode(0) {} }; class position //位置节点记录入栈左括号的序数和在字符串中的位置 { public: int place; //位置 int index; //序数 position(int p, int i) :place(p), index(i) {} }; void suboutput(Gen *head); Gen * strtogen(); int main() { int flag 0; bool TF true; vectorGennode stack; vectorposition match; //记录左括号位置序数的栈 int left 0, right 0, total 0; //初始化左括号序数,右括号序数,和当前在字符串广义表中遍历到的位置 Gen *ptr strtogen();//ptr初始化为指向广义表附加头节点的指针 while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) { if (TF true) { left; //扫描到附加头节点对应左括号因此left,total加一 total; position temp(total, left); //入栈 match.push_back(temp); if (ptr-utype 0) { Gennode temp(ptr); stack.push_back(temp); flag 0; ptr ptr-tlink; } else { stack[stack.size() - 1].numnode; Gennode temp(ptr); stack.push_back(temp); flag 2; ptr ptr-info.hlink; } } else { if (ptr-utype 0) break; else { ptr ptr-tlink; flag 1; TF true; } } } else { if (ptr nullptr) { right; //子表遍历完毕对应右括号因此right,total加一 total; if (flag 2) //找到一个子空表 { cout 子表 ():; } else { if (flag 1) { //找到一个非空子表 cout 子表 ; suboutput(stack[stack.size() - 1].ptr); //输出非空子表 cout :; } else //找到空表为广义表本身 { cout 子表 ():; } } cout endl; cout 长度: stack[stack.size() - 1].numnode endl; cout (为从左至右数起第 match[match.size() - 1].index 个 ; //输出当前子表左右括号序数位置 cout )为第 right 个 ; cout (下标为 match[match.size() - 1].place )下标为 total endl; cout endl; match.pop_back(); //出栈 ptr stack[stack.size() - 1].ptr; if (ptr-utype ! 0 ptr-tlink ! nullptr) total; //当前子表右括号后应跟逗号故total加一 stack.pop_back(); TF false; } else { stack[stack.size() - 1].numnode; total; //对原子项total应加一 ptr ptr-tlink; if (ptr ! nullptr) total; //原子项后跟逗号total加一 flag 1; } } } return 0; } void suboutput(Gen *head) { Gen *ptr head; bool TF true; vectorGen * stack; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) //注意 { if (TF true) { stack.push_back(ptr); cout (; if (ptr-utype 0) //注意 { ptr ptr-tlink; } else { ptr ptr-info.hlink; } } else { if (ptrhead) break; else { ptr ptr-tlink; TF true; } } } else { if (ptr nullptr) { cout ); ptr stack[stack.size() - 1]; if (ptr-utype ! 0 ptr-tlink ! nullptr) //注意 cout ,; stack.pop_back(); TF false; } else { cout ptr-info.value; ptr ptr-tlink; if (ptr ! nullptr) cout ,; } } } } Gen * strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen *ptr nullptr; vectorGen * stack; bool TF; for (auto i glist.cbegin(); i ! glist.cend(); i) { if (*i () { if (i glist.cbegin()) { ptr new Gen(0); stack.push_back(ptr); TF true; } else { Gen *temp new Gen(1); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } stack.push_back(temp); TF true; ptr temp; } } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; } else { if (*i ! ,) { Gen *temp new Gen(2, *i); if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } ptr temp; } } } } return ptr; }还有其他诸多未在上方给出实现的运算都很容易实现有兴趣可以自己尝试