欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-24 13:13:53
广义表链表表示的删除: 从广义表附加头节点开始,逐一分离表头元素,是原子项就直接删除,是子表附加头节点则暂不删除,直接进入子表,再分离表头元素,然后用相同的方法删除,子表删除完成后向上回溯,继续删除上一层子表,如此不断进行直到整个广义表被删除为止 代码(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 }

运行结果:

广义表链表表示的复制删除比较运算的非递归实现(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 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 }

运行结果:

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