广义表链表表示的复制删除比较运算的非递归实现(c++)

广义表链表表示的删除：

从广义表附加头节点开始，逐一分离表头元素，是原子项就直接删除,是子表附加头节点则暂不删除，直接进入子表，再分离表头元素，然后用相同的方法删除，子表删除完成后向上回溯，继续删除上一层子表，如此不断进行直到整个广义表被删除为止

代码（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                 else
105                 {
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             else
120             {
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                 else
138                 {
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             else
178             {
179                 Gen *temp = new Gen(1);
180                 if (ptr->utype == 1)
181                 {
182                     if (TF == true)
183                         ptr->info.hlink = temp;
184                     else
185                         ptr->tlink = temp;
186                 }
187                 else
188                 {
189                     ptr->tlink = temp;
190                 }
191 
192                 stack.push_back(temp);
193                 TF = true;
194                 ptr = temp;
195             }
196         }
197         else
198         {
199             if (*i == ')')
200             {
201                 ptr = stack[stack.size() - 1];
202                 stack.pop_back();
203                 TF = false;
204             }
205             else
206             {
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                         else
215                             ptr->tlink = temp;
216                     }
217                     else
218                     {
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             else
108             {
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                 else
113                     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             else
142             {
143                 Gen *temp = new Gen(1);
144                 if (ptr->utype == 1)
145                 {
146                     if (TF == true)
147                         ptr->info.hlink = temp;
148                     else
149                         ptr->tlink = temp;
150                 }
151                 else
152                 {
153                     ptr->tlink = temp;
154                 }
155 
156                 stack.push_back(temp);
157                 TF = true;
158                 ptr = temp;
159             }
160         }
161         else
162         {
163             if (*i == ')')
164             {
165                 ptr = stack[stack.size() - 1];
166                 stack.pop_back();
167                 TF = false;
168             }
169             else
170             {
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                         else
179                             ptr->tlink = temp;
180                     }
181                     else
182                     {
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                 else
213                 {
214                     ptr = ptr->info.hlink;
215                 }
216             }
217             else
218             {
219                 if (ptr->utype == 0)
220                     break;
221                 else
222                 {
223                     ptr = ptr->tlink;
224                     TF = true;
225                 }
226             }
227         }
228         else
229         {
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             else
240             {
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             else
104             {
105                 if (equals(ptr1, ptr2) == true)  //比较ptr1或其指向的原子项和表2对应位置指针ptr2或其指向的节点
106                 {
107                     ptr1 = ptr1->tlink;
108                     ptr2 = ptr2->tlink;
109                 }
110                 else
111                 {
112                     isequals = 0;
113                     break;
114                 }
115             }
116         }
117     }
118     if (isequals)
119         cout << "两广义表相等";
120     else
121         cout << "两广义表不等";
122     cout << endl;
123     return 0;
124 }
125 
126 bool equals(Gen *ptr1, Gen *ptr2)   //ptr1和ptr2所指节点相等返回true否则返回false
127 {
128     if (ptr1 == nullptr && ptr2 == nullptr)
129         return true;
130     else
131     {
132         if (ptr1 != nullptr && ptr2 != nullptr)
133         {
134             if (ptr1->utype != ptr2->utype)
135                 return false;
136             else
137             {
138                 if (ptr1->utype == 1)
139                     return true;
140                 else
141                 {
142                     if (ptr1->info.value == ptr2->info.value)
143                         return true;
144                     else
145                         return false;
146                 }
147             }
148         }
149         else
150         {
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             else
174             {
175                 Gen *temp = new Gen(1);
176                 if (ptr->utype == 1)
177                 {
178                     if (TF == true)
179                         ptr->info.hlink = temp;
180                     else
181                         ptr->tlink = temp;
182                 }
183                 else
184                 {
185                     ptr->tlink = temp;
186                 }
187 
188                 stack.push_back(temp);
189                 TF = true;
190                 ptr = temp;
191             }
192         }
193         else
194         {
195             if (*i == ')')
196             {
197                 ptr = stack[stack.size() - 1];
198                 stack.pop_back();
199                 TF = false;
200             }
201             else
202             {
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                         else
211                             ptr->tlink = temp;
212                     }
213                     else
214                     {
215                         ptr->tlink = temp;
216                     }
217 
218                     ptr = temp;
219                 }
220             }
221         }
222     }
223     cout << "已将字符串形式的广义表转换为链表形式" << endl;
224     return ptr;
225 }

运行结果：