广义表链表表示的删除：
从广义表附加头节点开始，逐一分离表头元素，是原子项就直接删除,是子表附加头节点则暂不删除，直接进入子表，再分离表头元素，然后用相同的方法删除，子表删除完成后向上回溯，继续删除上一层子表，如此不断进行直到整个广义表被删除为止
代码（C++）
1 #include "stdafx.h" 2 #include <iostream> 3 #include <vector> 4 #include<string> 5 using namespace std; 6 7 struct Gen 8 { 9 int utype; 10 union 11 { 12 int ref; 13 struct Gen *hlink; 14 char value; 15 }info; 16 struct Gen *tlink; 17 Gen(int u); 18 Gen(int u, char v); 19 }; 20 Gen::Gen(int u) :utype(u), tlink(nullptr) 21 { 22 if (u == 0) 23 info.ref = 0; 24 else 25 info.hlink = nullptr; 26 } 27 28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr) 29 { 30 info.value = v; 31 } 32 33 Gen * strtogen(); 34 35 int main() 36 { 37 Gen *ptr = strtogen(); //ptr初始化为广义表附加头结点指针 38 bool TF = true; 39 vector<Gen *> stack; 40 41 while (true) 42 { 43 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) 44 { 45 if (TF == true) 46 { 47 stack.push_back(ptr); 48 if (ptr->utype == 0) 49 { 50 if (ptr->tlink == nullptr) 51 { 52 stack.pop_back(); 53 TF = false; 54 continue; 55 } 56 ptr = ptr->tlink; //拉链，分理出广义表附加头节点的下一待删除节点 57 stack[stack.size() - 1]->tlink = ptr->tlink; 58 } 59 else 60 { 61 if (ptr->info.hlink == nullptr) 62 TF = false; 63 else 64 { 65 ptr = ptr->info.hlink; //拉链，分离出ptr指向的子表附加头节点在子表中的下一节点 66 stack[stack.size() - 1]->info.hlink = ptr->tlink; 67 } 68 } 69 } 70 else 71 { 72 if (ptr->utype == 0) 73 { 74 delete ptr; //删除附加头节点，至此删除成功，退出 75 break; 76 } 77 else 78 { 79 delete ptr; //删除子表附加头节点，子表删除成功 80 stack.pop_back(); 81 ptr = nullptr; 82 } 83 } 84 } 85 else 86 { 87 if (ptr == nullptr) 88 { 89 if (stack[stack.size() - 1]->utype == 0) 90 { 91 if (stack[stack.size() - 1]->tlink == nullptr) //广义表除附加头节点全部删除完毕 92 { 93 TF = false; 94 ptr = stack[stack.size() - 1]; 95 stack.pop_back(); 96 } 97 else //广义表附加头节点下一子表附加头节点及子表删除完毕 98 { 99 ptr = stack[stack.size() - 1]->tlink;100 stack[stack.size() - 1]->tlink = ptr->tlink;101 TF = true;102 }103 }104 else105 {106 if (stack[stack.size() - 1]->info.hlink == nullptr) //子表除附加头节点全部删除完毕107 {108 TF = false;109 ptr = stack[stack.size()-1];110 }111 else //子表附加头节点下一子表附加头节点及子表删除完毕112 {113 ptr = stack[stack.size() - 1]->info.hlink;114 stack[stack.size() - 1]->info.hlink = ptr->tlink;115 TF = true;116 }117 }118 }119 else120 {121 if (stack[stack.size() - 1]->utype == 0)122 {123 if (stack[stack.size() - 1]->tlink == nullptr) //广义表除附加头节点外还剩一个原子项待删除124 {125 delete ptr; //删除之126 ptr = stack[stack.size() - 1];127 stack.pop_back();128 TF = false;129 }130 else //广义表头节点后的原子项待删除,其后还有节点待删除131 {132 delete ptr;133 ptr = stack[stack.size() - 1]->tlink;134 stack[stack.size() - 1]->tlink = ptr->tlink;135 }136 }137 else138 {139 if (stack[stack.size() - 1]->info.hlink == nullptr) //子表除附加头节点外还剩一个原子项待删除140 {141 delete ptr;142 ptr = stack[stack.size() - 1];143 TF = false;144 }145 else //子表头节点后的原子项待删除,其后还有节点待删除146 {147 delete ptr;148 ptr = stack[stack.size() - 1]->info.hlink;149 stack[stack.size() - 1]->info.hlink = ptr->tlink;150 }151 }152 }153 }154 }155 //运行结束后ptr成为野指针,栈空,删除成功156 cout << "链表形式的广义表删除成功!"<< endl;157 return 0;158 }159 160 Gen * strtogen()161 {162 string glist;163 cout << "请输入广义表的字符串形式" << endl;164 cin >> glist;165 166 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;167 for (auto i = glist.cbegin(); i != glist.cend(); ++i)168 {169 if (*i == '(')170 {171 if (i == glist.cbegin())172 {173 ptr = new Gen(0);174 stack.push_back(ptr);175 TF = true;176 }177 else178 {179 Gen *temp = new Gen(1);180 if (ptr->utype == 1)181 {182 if (TF == true)183 ptr->info.hlink = temp;184 else185 ptr->tlink = temp;186 }187 else188 {189 ptr->tlink = temp;190 }191 192 stack.push_back(temp);193 TF = true;194 ptr = temp;195 }196 }197 else198 {199 if (*i == ')')200 {201 ptr = stack[stack.size() - 1];202 stack.pop_back();203 TF = false;204 }205 else206 {207 if (*i != ',')208 {209 Gen *temp = new Gen(2, *i);210 if (ptr->utype == 1)211 {212 if (TF == true)213 ptr->info.hlink = temp;214 else215 ptr->tlink = temp;216 }217 else218 {219 ptr->tlink = temp;220 }221 222 ptr = temp;223 }224 }225 }226 }227 cout << "已将字符串形式的广义表转换为链表形式" << endl;228 return ptr;229 }广义表链表表示的复制：
就是按广度优先遍历的次序逐一复制，为方便复制，目标表指针总比原表遍历指针慢一步，原表遍历完成后复制就结束了
1 #include "stdafx.h" 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 struct Gen 8 { 9 int utype; 10 union 11 { 12 int ref; 13 struct Gen *hlink; 14 char value; 15 }info; 16 struct Gen *tlink; 17 Gen(int u); 18 Gen(int u, char v); 19 }; 20 Gen::Gen(int u) :utype(u), tlink(nullptr) 21 { 22 if (u == 0) 23 info.ref = 0; 24 else 25 info.hlink = nullptr; 26 } 27 28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr) 29 { 30 info.value = v; 31 } 32 33 Gen * strtogen(); 34 void suboutput(Gen *head); 35 36 int main() 37 { 38 vector<Gen *> stack1;//源栈 39 vector<Gen *> stack2;//目标栈 40 Gen *ptr1=strtogen(); //ptr1初始化为源广义表附加头节点指针 41 Gen *ptr2=nullptr; //ptr2为目标广义表拷贝指针 42 bool TF = true; 43 44 while (true) //循环开始,将源广义表链表表示拷贝为目标广义表链表表示 45 { 46 if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1)) 47 { 48 if (TF == true) 49 { 50 stack1.push_back(ptr1); 51 if (ptr1->utype == 0) 52 { 53 ptr2 = new Gen(0); //拷贝广义表附加头节点,完成后ptr1递进 54 ptr2->info.ref = ptr1->info.ref; 55 stack2.push_back(ptr2); 56 ptr1 = ptr1->tlink; 57 } 58 else 59 { 60 if (ptr2->utype == 1) //需要把子表附加头节点拷贝至ptr2所指附加头节点后 61 { 62 Gen *temp = new Gen(1); 63 if (ptr2 == stack2[stack2.size() - 1]) //ptr2新进至子表头节点,源广义表子表头节点链接至ptr2所指子表中头节点后 64 ptr2->info.hlink = temp; 65 else 66 ptr2->tlink = temp; 67 ptr2 = temp; 68 stack2.push_back(ptr2); 69 ptr1 = ptr1->info.hlink; 70 } 71 else 72 { 73 Gen *temp = new Gen(1); //由于ptr2指向目标广义表头节点或原子项，所以直接把待拷贝子表头节点链接于其后 74 ptr2->tlink = temp; 75 ptr2 = temp; 76 stack2.push_back(ptr2); 77 ptr1 = ptr1->info.hlink; 78 } 79 } 80 } 81 else 82 { 83 if (ptr1->utype == 0) 84 { 85 ptr2 = stack2[stack2.size() - 1]; 86 stack2.pop_back(); 87 break; //拷贝完毕，退出，ptr2为目标广义表头节点 88 } 89 else 90 { 91 ptr2 = stack2[stack2.size() - 1]; 92 stack2.pop_back(); 93 ptr1 = ptr1->tlink; 94 TF = true; 95 } 96 } 97 } 98 else 99 {100 if (ptr1 == nullptr) //子表拷贝完毕101 {102 ptr2 = nullptr;103 ptr1 = stack1[stack1.size() - 1];104 stack1.pop_back();105 TF = false;106 }107 else108 {109 Gen *temp = new Gen(2, ptr1->info.value); //拷贝原子项110 if (ptr2->utype == 1 && stack2[stack2.size() - 1] == ptr2)111 ptr2->info.hlink = temp; //如果ptr2新进至子表头节点，操作和上述相同112 else113 ptr2->tlink = temp; //操作和上述相同114 ptr2 = temp;115 ptr1 = ptr1->tlink;116 }117 }118 }119 cout << "复制完成,复制后的广义表为:";120 suboutput(ptr2); //输出复制后的广义表121 return 0;122 }123 124 Gen * strtogen()125 {126 string glist;127 cout << "请输入广义表的字符串形式" << endl;128 cin >> glist;129 130 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;131 for (auto i = glist.cbegin(); i != glist.cend(); ++i)132 {133 if (*i == '(')134 {135 if (i == glist.cbegin())136 {137 ptr = new Gen(0);138 stack.push_back(ptr);139 TF = true;140 }141 else142 {143 Gen *temp = new Gen(1);144 if (ptr->utype == 1)145 {146 if (TF == true)147 ptr->info.hlink = temp;148 else149 ptr->tlink = temp;150 }151 else152 {153 ptr->tlink = temp;154 }155 156 stack.push_back(temp);157 TF = true;158 ptr = temp;159 }160 }161 else162 {163 if (*i == ')')164 {165 ptr = stack[stack.size() - 1];166 stack.pop_back();167 TF = false;168 }169 else170 {171 if (*i != ',')172 {173 Gen *temp = new Gen(2, *i);174 if (ptr->utype == 1)175 {176 if (TF == true)177 ptr->info.hlink = temp;178 else179 ptr->tlink = temp;180 }181 else182 {183 ptr->tlink = temp;184 }185 186 ptr = temp;187 }188 }189 }190 }191 cout << "已将字符串形式的广义表转换为链表形式" << endl;192 return ptr;193 }194 195 void suboutput(Gen *head)196 {197 Gen *ptr = head;198 bool TF = true;199 vector<Gen *> stack;200 while (true)201 {202 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意203 {204 if (TF == true)205 {206 stack.push_back(ptr);207 cout << "(";208 if (ptr->utype == 0) //注意209 {210 ptr = ptr->tlink;211 }212 else213 {214 ptr = ptr->info.hlink;215 }216 }217 else218 {219 if (ptr->utype == 0)220 break;221 else222 {223 ptr = ptr->tlink;224 TF = true;225 }226 }227 }228 else229 {230 if (ptr == nullptr)231 {232 cout << ")";233 ptr = stack[stack.size() - 1];234 if (ptr->utype != 0 && ptr->tlink != nullptr) //注意235 cout << ",";236 stack.pop_back();237 TF = false;238 }239 else240 {241 cout << ptr->info.value;242 ptr = ptr->tlink;243 if (ptr != nullptr)244 cout << ",";245 }246 }247 }248 cout << endl;249 }运行结果：
基于广义表链表表示的比较：
两表指针同步动作，按广度优先遍历逐一比较，比较到某一处节点不等则广义表不等，否则会一直比较至遍历完整个广义表，此时两广义表相等
1 #include "stdafx.h" 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 struct Gen 8 { 9 int utype; 10 union 11 { 12 int ref; 13 struct Gen *hlink; 14 char value; 15 }info; 16 struct Gen *tlink; 17 Gen(int u); 18 Gen(int u, char v); 19 }; 20 Gen::Gen(int u) :utype(u), tlink(nullptr) 21 { 22 if (u == 0) 23 info.ref = 0; 24 else 25 info.hlink = nullptr; 26 } 27 28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr) 29 { 30 info.value = v; 31 } 32 33 bool equals(Gen *ptr1, Gen *ptr2); //判断ptr1和ptr2指向的广义表节点是否相等的函数 34 Gen * strtogen(); 35 36 int main() 37 { 38 vector<Gen *> stack1; vector<Gen *> stack2; 39 Gen *ptr1 = strtogen(); //指向广义表1附加头节点 40 Gen *ptr2= strtogen(); //指向广义表2附加头节点 41 //两指针同步动作 42 bool TF = true; 43 int isequals = 1; //=1两广义表相等，否则不等 44 while (true) 45 { 46 if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1)) 47 { 48 if (TF == true) 49 { 50 if (ptr1->utype == 0) 51 { 52 stack1.push_back(ptr1); 53 stack2.push_back(ptr2); 54 ptr1 = ptr1->tlink; //附加头节点不必比较，跳过 55 ptr2 = ptr2->tlink; 56 } 57 else 58 { 59 if (equals(ptr1, ptr2) == true) //比较表1子表头节点或指针和表2对应位置节点或指针 60 { 61 stack1.push_back(ptr1); 62 stack2.push_back(ptr2); 63 ptr1 = ptr1->info.hlink; 64 ptr2 = ptr2->info.hlink; 65 } 66 else 67 { 68 isequals = 0; //不等,isequals置位，退出 69 break; 70 } 71 } 72 } 73 else 74 { 75 if (ptr1->utype == 0) //比较完成,退出 76 break; 77 else 78 { 79 ptr1 = ptr1->tlink; 80 ptr2 = ptr2->tlink; 81 TF = true; 82 } 83 } 84 } 85 else 86 { 87 if (ptr1 == nullptr) 88 { 89 if (equals(ptr1, ptr2) == true) //比较ptr1或其指向节点和ptr2或其指向节点 90 { 91 ptr1 = stack1[stack1.size() - 1]; 92 ptr2 = stack2[stack2.size() - 1]; 93 stack1.pop_back(); 94 stack2.pop_back(); 95 TF = false; 96 } 97 else 98 { 99 isequals = 0;100 break;101 }102 }103 else104 {105 if (equals(ptr1, ptr2) == true) //比较ptr1或其指向的原子项和表2对应位置指针ptr2或其指向的节点106 {107 ptr1 = ptr1->tlink;108 ptr2 = ptr2->tlink;109 }110 else111 {112 isequals = 0;113 break;114 }115 }116 }117 }118 if (isequals)119 cout << "两广义表相等";120 else121 cout << "两广义表不等";122 cout << endl;123 return 0;124 }125 126 bool equals(Gen *ptr1, Gen *ptr2) //ptr1和ptr2所指节点相等返回true否则返回false127 {128 if (ptr1 == nullptr && ptr2 == nullptr)129 return true;130 else131 {132 if (ptr1 != nullptr && ptr2 != nullptr)133 {134 if (ptr1->utype != ptr2->utype)135 return false;136 else137 {138 if (ptr1->utype == 1)139 return true;140 else141 {142 if (ptr1->info.value == ptr2->info.value)143 return true;144 else145 return false;146 }147 }148 }149 else150 {151 return false;152 }153 }154 }155 156 Gen * strtogen()157 {158 string glist;159 cout << "请输入广义表的字符串形式" << endl;160 cin >> glist;161 162 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;163 for (auto i = glist.cbegin(); i != glist.cend(); ++i)164 {165 if (*i == '(')166 {167 if (i == glist.cbegin())168 {169 ptr = new Gen(0);170 stack.push_back(ptr);171 TF = true;172 }173 else174 {175 Gen *temp = new Gen(1);176 if (ptr->utype == 1)177 {178 if (TF == true)179 ptr->info.hlink = temp;180 else181 ptr->tlink = temp;182 }183 else184 {185 ptr->tlink = temp;186 }187 188 stack.push_back(temp);189 TF = true;190 ptr = temp;191 }192 }193 else194 {195 if (*i == ')')196 {197 ptr = stack[stack.size() - 1];198 stack.pop_back();199 TF = false;200 }201 else202 {203 if (*i != ',')204 {205 Gen *temp = new Gen(2, *i);206 if (ptr->utype == 1)207 {208 if (TF == true)209 ptr->info.hlink = temp;210 else211 ptr->tlink = temp;212 }213 else214 {215 ptr->tlink = temp;216 }217 218 ptr = temp;219 }220 }221 }222 }223 cout << "已将字符串形式的广义表转换为链表形式" << endl;224 return ptr;225 }运行结果：
浙公网安备 33030202000166号