广义表链表表示的删除从广义表附加头节点开始逐一分离表头元素是原子项就直接删除,是子表附加头节点则暂不删除直接进入子表再分离表头元素然后用相同的方法删除子表删除完成后向上回溯继续删除上一层子表如此不断进行直到整个广义表被删除为止代码C#include iostream #include vector #includestring 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; } Gen* strtogen(); int main() { Gen* ptr strtogen(); //ptr初始化为广义表附加头结点指针 bool TF true; vectorGen* stack; while (true) { if (ptr ! nullptr (ptr-utype 0 || ptr-utype 1)) { if (TF true) { stack.push_back(ptr); if (ptr-utype 0) { if (ptr-tlink nullptr) { stack.pop_back(); TF false; continue; } ptr ptr-tlink; //拉链分理出广义表附加头节点的下一待删除节点 stack.back()-tlink ptr-tlink; } else { if (ptr-info.hlink nullptr) TF false; else { ptr ptr-info.hlink; //拉链分离出ptr指向的子表附加头节点在子表中的下一节点 stack.back()-info.hlink ptr-tlink; } } } else { if (ptr-utype 0) { delete ptr; break;//删除附加头节点至此删除成功退出 } else { delete ptr; stack.pop_back(); //删除子表附加头节点子表删除成功 ptr nullptr; } } } else { if (ptr ! nullptr) { delete ptr; } if (stack.back()-utype 0 stack.back()-tlink nullptr || stack.back()-utype ! 0 stack.back()-info.hlink nullptr) { TF false; ptr stack.back(); if (stack.back()-utype 0) { stack.pop_back(); } } else { if (ptr nullptr) TF true; if (stack.back()-utype 0) { ptr stack.back()-tlink; stack.back()-tlink ptr-tlink; } else { ptr stack.back()-info.hlink; stack.back()-info.hlink ptr-tlink; } } } } //运行结束后ptr成为野指针,栈空,删除成功 cout 链表形式的广义表删除成功! endl; return 0; } Gen* strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen* ptr nullptr; vectorGen* stack; bool TF; auto i glist.cbegin(); i; ptr new Gen(0); stack.push_back(ptr); TF true; for (; i ! glist.cend(); i) { Gen* temp; if (*i () { temp new Gen(1); } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; continue; } if (*i ! ,) { temp new Gen(2, *i); } else continue; } if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } if (*i () { stack.push_back(temp); TF true; } ptr temp; } cout 已将字符串形式的广义表转换为链表形式 endl; return ptr; }广义表链表表示的复制就是按广度优先遍历的次序逐一复制为方便复制目标表指针总比原表遍历指针慢一步原表遍历完成后复制就结束了#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; } Gen* strtogen(); void suboutput(Gen* head); int main() { vectorGen* stack1;//源栈 vectorGen* stack2;//目标栈 Gen* ptr1 strtogen(); //ptr1初始化为源广义表附加头节点指针 Gen* ptr2 nullptr; //ptr2为目标广义表拷贝指针 bool TF true; while (true) //循环开始,将源广义表链表表示拷贝为目标广义表链表表示 { bool t (ptr1 ! nullptr) (ptr1-utype 0 || ptr1-utype 1); if (t || ptr1 ! nullptr) { if (t false || TF ptr1-utype ! 0 ptr2-utype 1) { if (t) { stack1.push_back(ptr1); } Gen* temp; if (t) { temp new Gen(1); } else { temp new Gen(2, ptr1-info.value); } if ((t || ptr2-utype 1) ptr2 stack2.back()) { //ptr2新进至子表头节点,源广义表子表头节点链接至ptr2所指子表中头节点后 ptr2-info.hlink temp; } else { ptr2-tlink temp; } ptr2 temp; if (t) { stack2.push_back(ptr2); ptr1 ptr1-info.hlink; } else { ptr1 ptr1-tlink; } } else { if (TF false) { ptr2 stack2.back(); stack2.pop_back(); if (ptr1-utype 0) { break; //拷贝完毕退出ptr2为目标广义表头节点 } else { ptr1 ptr1-tlink; TF true; } } else { stack1.push_back(ptr1); if (ptr1-utype 0) { ptr2 new Gen(0); //拷贝广义表附加头节点,完成后ptr1递进 ptr2-info.ref ptr1-info.ref; ptr1 ptr1-tlink; } else { Gen* temp new Gen(1); //由于ptr2指向目标广义表头节点或原子项所以直接把待拷贝子表头节点链接于其后 ptr2-tlink temp; ptr2 temp; ptr1 ptr1-info.hlink; } stack2.push_back(ptr2); } } } else { ptr2 nullptr; ptr1 stack1.back(); stack1.pop_back(); TF false; } } /*while (true) { if (ptr1 ! nullptr (ptr1-utype 0 || ptr1-utype 1)) { if (TF true) { stack1.push_back(ptr1); if (ptr1-utype 0) { ptr2 new Gen(0); //拷贝广义表附加头节点,完成后ptr1递进 ptr2-info.ref ptr1-info.ref; ptr1 ptr1-tlink; } else { Gen* temp new Gen(1); if (ptr2-utype 1) //需要把子表附加头节点拷贝至ptr2所指附加头节点后 { if (ptr2 stack2.back()) //ptr2新进至子表头节点,源广义表子表头节点链接至ptr2所指子表中头节点后 ptr2-info.hlink temp; else ptr2-tlink temp; } else { ptr2-tlink temp; //由于ptr2指向目标广义表头节点或原子项所以直接把待拷贝子表头节点链接于其后 } ptr2 temp; ptr1 ptr1-info.hlink; } stack2.push_back(ptr2); } else { ptr2 stack2.back(); stack2.pop_back(); if (ptr1-utype 0) { break; //拷贝完毕退出ptr2为目标广义表头节点 } else { ptr1 ptr1-tlink; TF true; } } } else { if (ptr1 nullptr) //子表拷贝完毕 { ptr2 nullptr; ptr1 stack1.back(); stack1.pop_back(); TF false; } else { Gen* temp new Gen(2, ptr1-info.value); //拷贝原子项 if (ptr2-utype 1 stack2[stack2.size() - 1] ptr2) ptr2-info.hlink temp; //如果ptr2新进至子表头节点操作和上述相同 else ptr2-tlink temp; //操作和上述相同 ptr2 temp; ptr1 ptr1-tlink; } } }*/ cout 复制完成,复制后的广义表为:; suboutput(ptr2); //输出复制后的广义表 return 0; } Gen* strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen* ptr nullptr; vectorGen* stack; bool TF; auto i glist.cbegin(); i; ptr new Gen(0); stack.push_back(ptr); TF true; for (; i ! glist.cend(); i) { Gen* temp; if (*i () { temp new Gen(1); } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; continue; } if (*i ! ,) { temp new Gen(2, *i); } else continue; } if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } if (*i () { stack.push_back(temp); TF true; } ptr temp; } cout 已将字符串形式的广义表转换为链表形式 endl; return ptr; } 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-utype 0) break; else { ptr ptr-tlink; TF true; } } } else { if (ptr nullptr) { cout ); ptr stack.back(); 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; }基于广义表链表表示的比较两表指针同步动作按广度优先遍历逐一比较比较到某一处节点不等则广义表不等否则会一直比较至遍历完整个广义表此时两广义表相等#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; } bool equals(Gen* ptr1, Gen* ptr2); //判断ptr1和ptr2指向的广义表节点是否相等的函数 Gen* strtogen(); int main() { vectorGen* stack1; vectorGen* stack2; Gen* ptr1 strtogen(); //指向广义表1附加头节点 Gen* ptr2 strtogen(); //指向广义表2附加头节点 //两指针同步动作 bool TF true; int isequals 1; //1两广义表相等否则不等 while (true) { if (ptr1 ! nullptr (ptr1-utype 0 || ptr1-utype 1)) { if (TF true) { if (ptr1-utype 0 || equals(ptr1, ptr2)) //比较表1子表头节点或指针和表2对应位置节点或指针 { stack1.push_back(ptr1); stack2.push_back(ptr2); if (ptr1-utype ! 0) //附加头节点不必比较跳过 { ptr1 ptr1-info.hlink; ptr2 ptr2-info.hlink; continue; } } else { isequals 0; //不等,isequals置位退出 break; } } else { if (ptr1-utype 0) //比较完成,退出 break; else { TF true; } } } else { if (equals(ptr1, ptr2)) { if (ptr1 nullptr) { ptr1 stack1[stack1.size() - 1]; //比较ptr1或其指向节点和ptr2或其指向节点 ptr2 stack2[stack2.size() - 1]; stack1.pop_back(); stack2.pop_back(); TF false; continue; } //比较ptr1或其指向的原子项和表2对应位置指针ptr2或其指向的节点 } else { isequals 0; break; } } ptr1 ptr1-tlink; ptr2 ptr2-tlink; } if (isequals) cout 两广义表相等; else cout 两广义表不等; cout endl; return 0; } bool equals(Gen* ptr1, Gen* ptr2) //ptr1和ptr2所指节点相等返回true否则返回false { if (ptr1 nullptr ptr2 nullptr) return true; else { if (ptr1 ! nullptr ptr2 ! nullptr) { if (ptr1-utype ! ptr2-utype) return false; else { if (ptr1-utype 1) return true; else { if (ptr1-info.value ptr2-info.value) return true; else return false; } } } else { return false; } } } Gen* strtogen() { string glist; cout 请输入广义表的字符串形式 endl; cin glist; Gen* ptr nullptr; vectorGen* stack; bool TF; auto i glist.cbegin(); i; ptr new Gen(0); stack.push_back(ptr); TF true; for (; i ! glist.cend(); i) { Gen* temp; if (*i () { temp new Gen(1); } else { if (*i )) { ptr stack[stack.size() - 1]; stack.pop_back(); TF false; continue; } if (*i ! ,) { temp new Gen(2, *i); } else continue; } if (ptr-utype 1) { if (TF true) ptr-info.hlink temp; else ptr-tlink temp; } else { ptr-tlink temp; } if (*i () { stack.push_back(temp); TF true; } ptr temp; } cout 已将字符串形式的广义表转换为链表形式 endl; return ptr; }