)
广义表链表表示的删除：
从广义表附加头节点开始，逐一分离表头元素，是原子项就直接删除,是子表附加头节点则暂不删除，直接进入子表，再分离表头元素，然后用相同的方法删除，子表删除完成后向上回溯，继续删除上一层子表，如此不断进行直到整个广义表被删除为止
代码（C++）
#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(); int main() { Gen* ptr = strtogen(); //ptr初始化为广义表附加头结点指针 bool TF = true; vector<Gen*> 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; vector<Gen*> 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() { vector<Gen*> stack1;//源栈 vector<Gen*> 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; vector<Gen*> 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; vector<Gen*> 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() { vector<Gen*> stack1; vector<Gen*> 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; vector<Gen*> 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; }
