首页 > > 程序设计 > C/C++ >

带附加头节点的广义表运算c++源码分享

2018-06-17 20:47:18来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

之前文章里给出的基于广义表链表表示的运算中用链表表示的广义表除广义表本身外的其他所有子表都是没有附加头节点的，即utype==1的节点(在同一层子表中表示为该子表的子表的表元素)的hlink指针直接指向下一层子表的表头，而不是附加头节点，这是一个疏忽。所以我把所有适用于广义表没有附加头节点的链表表示的相关运算的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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 class Gennode
 37 {
 38 public:
 39     int numnode;
 40     Gen *ptr;
 41     Gennode(Gen *p) :ptr(p), numnode(0) {}
 42 };
 43 
 44 void output(vector<Gennode> &stack);
 45 void suboutput(Gen *head);
 46 Gen * strtogen();
 47 
 48 int main()
 49 {
 50     int depth = 0; int maxdepth = 0;
 51     int flag = 0; int sign = 0;
 52     int subcount = 0;
 53     int emptycount = 0;
 54     bool TF = true;
 55     vector<Gennode> stack;
 56     Gen *ptr=strtogen();//ptr应初始化为指向广义表附加头节点的指针
 57 
 58     while (true)
 59     {
 60         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 61         {
 62             if (TF == true)
 63             {
 64                 sign = 0;
 65 
 66                 if (ptr->utype == 0)
 67                 {
 68                     if (ptr->info.ref == 0)
 69                     {
 70                         Gennode temp(ptr);
 71                         stack.push_back(temp);
 72                         flag = 0;
 73                         ++depth;
 74                     }
 75                     ptr = ptr->tlink;
 76                 }
 77                 else
 78                 {
 79                     ++stack[stack.size() - 1].numnode;
 80                     Gennode temp(ptr);
 81                     stack.push_back(temp);
 82                     flag = 2;
 83                     ++depth;
 84                     ptr = ptr->info.hlink;
 85                 }
 86             }
 87             else
 88             {
 89                 if (ptr->utype == 0)
 90                     break;
 91                 else
 92                 {
 93                     sign = 1;
 94                     ptr = ptr->tlink;
 95                     flag = 1;
 96                     TF = true;
 97                 }
 98             }
 99         }
100         else
101         {
102             if (ptr == nullptr)
103             {
104                 subcount++;
105                 if (flag == 2) //找到一个子空表
106                 {
107                     //栈中存有完整位置信息,输出之
108                     emptycount++;
109                     cout << "第" << subcount << "个子表,为空表:()"<<endl;
110                     cout << "深度:" << depth << " 长度:" << 0 << endl;
111                     cout << "位置:" << endl;
112                     output(stack);
113                 }
114                 else
115                 {
116                     if (flag == 1)
117                     {
118                         //找到一个非空子表
119                         cout << "第" << subcount << "个非空子表:";
120                         suboutput(stack[stack.size() - 1].ptr);
121                         //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
122                         cout << "深度:" << depth << " 长度:" << stack[stack.size() - 1].numnode << endl;
123                         cout << "位置:" << endl;
124                         if (stack[stack.size() - 1].ptr->utype == 0)
125                         {
126                             //当前非空子表为广义表本身,
127                             cout << "该非空子表为广义表本身"<<endl;
128                         }
129                         else
130                         {
131                             //当前非空子表为真子表，栈中存有完整位置信息,输出之
132                             output(stack);
133                         }
134                     }
135                     else
136                     {
137                         emptycount++;
138                         //找到子空表,即为广义表本身,输出之
139                         cout << "第" << subcount << "个子表,为空表:()" << endl;
140                         cout << "深度:" << depth << " 长度:" << 0 << endl;
141                         cout << "位置:" << endl;
142                         cout << "该子空表为广义表本身" << endl;
143                     }
144                 }
145                 if (sign == 0)
146                 {
147                     if (depth > maxdepth)
148                         maxdepth = depth;
149                 }
150                 depth--;
151                 ptr = stack[stack.size() - 1].ptr;
152                 stack.pop_back();
153                 TF = false;
154             }
155             else
156             {
157                 ++stack[stack.size() - 1].numnode;
158                 ptr = ptr->tlink;
159                 flag = 1;
160             }
161         }
162     }
163     cout << "共有" << subcount << "个子表,其中有" << emptycount << "个空表" << endl;
164     cout << "广义表深度:"<< maxdepth<<endl;
165     return 0;
166 }
167 
168 void output(vector<Gennode> &stack)
169 {
170     for (auto i = stack.begin(); i != stack.end() - 1; ++i)
171     {
172         if (i == stack.begin())
173         {
174             cout << "广义表的第" << (*i).numnode << "个表元素";
175         }
176         else
177         {
178             cout << "的第" << (*i).numnode << "个表元素";
179         }
180     }
181     cout << endl;
182 }
183 
184 void suboutput(Gen *head)
185 {
186     Gen *ptr = head;
187     bool TF = true;
188     vector<Gen *> stack;
189     while (true)
190     {
191         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
192         {
193             if (TF == true)
194             {
195                 if (ptr->utype == 0)   //注意
196                 {
197                     if (ptr->info.ref == 0)
198                     {
199                         stack.push_back(ptr);
200                         cout << "(";
201                     }
202                     ptr = ptr->tlink;
203                 }
204                 else
205                 {
206                     stack.push_back(ptr);
207                     cout << "(";
208                     ptr = ptr->info.hlink;
209                 }
210             }
211             else
212             {
213                 if (ptr == head)
214                     break;
215                 else
216                 {
217                     ptr = ptr->tlink;
218                     TF = true;
219                 }
220             }
221         }
222         else
223         {
224             if (ptr == nullptr)
225             {
226                 cout << ")";
227                 ptr = stack[stack.size() - 1];
228                 if (ptr->tlink != nullptr && ptr != head)    //注意
229                     cout << ",";
230                 stack.pop_back();
231                 TF = false;
232             }
233             else
234             {
235                 cout << ptr->info.value;
236                 ptr = ptr->tlink;
237                 if (ptr != nullptr)
238                     cout << ",";
239             }
240         }
241     }
242     cout << endl;
243 }
244 
245 Gen * strtogen()
246 {
247     string glist;
248     cout << "请输入广义表的字符串形式" << endl;
249     cin >> glist;
250 
251     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
252     int ref = 0;
253     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
254     {
255         if (*i == '(')
256         {
257             if (i == glist.cbegin())
258             {
259                 ptr = new Gen(0, 0);
260                 stack.push_back(ptr);
261                 TF = true;
262             }
263             else
264             {
265                 Gen *temp = new Gen(1);
266                 if (ptr->utype == 1)
267                 {
268                     if (TF == true)
269                         ptr->info.hlink->tlink = temp;
270                     else
271                         ptr->tlink = temp;
272                 }
273                 else
274                 {
275                     ptr->tlink = temp;
276                 }
277 
278                 stack.push_back(temp);
279                 TF = true;
280                 ptr = temp;
281                 temp = new Gen(0, ++ref);
282                 ptr->info.hlink = temp;
283             }
284         }
285         else
286         {
287             if (*i == ')')
288             {
289                 ptr = stack[stack.size() - 1];
290                 stack.pop_back();
291                 TF = false;
292             }
293             else
294             {
295                 if (*i != ',')
296                 {
297                     Gen *temp = new Gen(2, *i);
298                     if (ptr->utype == 1)
299                     {
300                         if (TF == true)
301                             ptr->info.hlink->tlink = temp;
302                         else
303                             ptr->tlink = temp;
304                     }
305                     else
306                     {
307                         ptr->tlink = temp;
308                     }
309 
310                     ptr = temp;
311                 }
312             }
313         }
314     }    
315     return ptr;
316 }

在广义表中搜索给定值

 

  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 class Gennode
 37 {
 38 public:
 39     int numnode;
 40     Gen *ptr;
 41     vector<int> position;
 42     Gennode(Gen *p) :ptr(p), numnode(0) {}
 43 };
 44 
 45 void output(vector<Gennode> &stack);
 46 void suboutput(Gen *head);
 47 Gen * strtogen();
 48 
 49 int main()
 50 {
 51     int depth = 0; 
 52     int flag = 0; 
 53     int subcount = 0;
 54     bool TF = true;
 55     char key;
 56     vector<Gennode> stack;
 57     Gen *ptr= strtogen();//ptr应初始化为指向广义表附加头节点的指针
 58     cout << "请输入要搜索的值:" << endl;
 59     cin >> key;
 60 
 61     while (true)
 62     {
 63         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 64         {
 65             if (TF == true)
 66             {
 67 
 68                 if (ptr->utype == 0)
 69                 {
 70                     if (ptr->info.ref == 0)
 71                     {
 72                         Gennode temp(ptr);
 73                         stack.push_back(temp);
 74                         flag = 0;
 75                         depth++;
 76                     }
 77                     ptr = ptr->tlink;
 78                 }
 79                 else
 80                 {
 81                     ++stack[stack.size() - 1].numnode;
 82                     Gennode temp(ptr);
 83                     stack.push_back(temp);
 84                     flag = 2;
 85                     depth++;
 86                     ptr = ptr->info.hlink;
 87                 }
 88             }
 89             else
 90             {
 91                 if (ptr->utype == 0)
 92                     break;
 93                 else
 94                 {
 95                     ptr = ptr->tlink;
 96                     flag = 1;
 97                     TF = true;
 98                 }
 99             }
100         }
101         else
102         {
103             if (ptr == nullptr)
104             {
105                     if (flag != 2 && flag!=0) 
106                     {
107                         if (stack[stack.size() - 1].position.size()!=0)
108                         {
109                             subcount++;
110                             cout << "第" << subcount << "个含" << key << "的非空子表:";
111                                 suboutput(stack[stack.size() - 1].ptr);
112                                 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
113                                 cout << key << "是其中第";
114                             for (auto i = stack[stack.size() - 1].position.begin(); i < stack[stack.size() - 1].position.end(); ++i)
115                             {
116                                 if (i == stack[stack.size() - 1].position.begin())
117                                     cout << *i;
118                                 else
119                                     cout << "," << *i;
120                             }
121                             cout << "个表元素" << endl;
122                             cout << "该表深度:" << depth << " 长度:" << stack[stack.size() - 1].numnode << endl;
123                             cout << "位置:" << endl;
124                             if (stack[stack.size() - 1].ptr->utype == 0)
125                             {
126                                 //当前非空子表为广义表本身
127                                 cout << "该非空子表为广义表本身" << endl;
128                             }
129                             else
130                             {
131                                 //当前非空子表为真子表，栈中存有完整位置信息,输出之
132                                 output(stack);
133                             }
134                             cout << endl;
135                         }
136                     }
137                 depth--;
138                 ptr = stack[stack.size() - 1].ptr;
139                 stack.pop_back();
140                 TF = false;
141             }
142             else
143             {
144                 ++stack[stack.size() - 1].numnode;
145                 if (ptr->info.value == key)
146                 {
147                     stack[stack.size() - 1].position.push_back(stack[stack.size() - 1].numnode);
148                 }
149                 ptr = ptr->tlink;
150                 flag = 1;
151             }
152         }
153     }
154     cout << "共有" << subcount << "个子表含有" << key << endl;
155     return 0;
156 }
157 
158 void output(vector<Gennode> &stack)
159 {
160     for (auto i = stack.begin(); i != stack.end() - 1; ++i)
161     {
162         if (i == stack.begin())
163         {
164             cout << "广义表的第" << (*i).numnode << "个表元素";
165         }
166         else
167         {
168             cout << "的第" << (*i).numnode << "个表元素";
169         }
170     }
171     cout << endl;
172 }
173 
174 void suboutput(Gen *head)
175 {
176     Gen *ptr = head;
177     bool TF = true;
178     vector<Gen *> stack;
179     while (true)
180     {
181         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
182         {
183             if (TF == true)
184             {
185                 if (ptr->utype == 0)   //注意
186                 {
187                     if (ptr->info.ref == 0)
188                     {
189                         stack.push_back(ptr);
190                         cout << "(";
191                     }
192                     ptr = ptr->tlink;
193                 }
194                 else
195                 {
196                     stack.push_back(ptr);
197                     cout << "(";
198                     ptr = ptr->info.hlink;
199                 }
200             }
201             else
202             {
203                 if (ptr == head)
204                     break;
205                 else
206                 {
207                     ptr = ptr->tlink;
208                     TF = true;
209                 }
210             }
211         }
212         else
213         {
214             if (ptr == nullptr)
215             {
216                 cout << ")";
217                 ptr = stack[stack.size() - 1];
218                 if (ptr->tlink != nullptr && ptr != head)    //注意
219                     cout << ",";
220                 stack.pop_back();
221                 TF = false;
222             }
223             else
224             {
225                 cout << ptr->info.value;
226                 ptr = ptr->tlink;
227                 if (ptr != nullptr)
228                     cout << ",";
229             }
230         }
231     }
232     cout << endl;
233 }
234 
235 Gen * strtogen()
236 {
237     string glist;
238     cout << "请输入广义表的字符串形式" << endl;
239     cin >> glist;
240 
241     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
242     int ref = 0;
243     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
244     {
245         if (*i == '(')
246         {
247             if (i == glist.cbegin())
248             {
249                 ptr = new Gen(0, 0);
250                 stack.push_back(ptr);
251                 TF = true;
252             }
253             else
254             {
255                 Gen *temp = new Gen(1);
256                 if (ptr->utype == 1)
257                 {
258                     if (TF == true)
259                         ptr->info.hlink->tlink = temp;
260                     else
261                         ptr->tlink = temp;
262                 }
263                 else
264                 {
265                     ptr->tlink = temp;
266                 }
267 
268                 stack.push_back(temp);
269                 TF = true;
270                 ptr = temp;
271                 temp = new Gen(0, ++ref);
272                 ptr->info.hlink = temp;
273             }
274         }
275         else
276         {
277             if (*i == ')')
278             {
279                 ptr = stack[stack.size() - 1];
280                 stack.pop_back();
281                 TF = false;
282             }
283             else
284             {
285                 if (*i != ',')
286                 {
287                     Gen *temp = new Gen(2, *i);
288                     if (ptr->utype == 1)
289                     {
290                         if (TF == true)
291                             ptr->info.hlink->tlink = temp;
292                         else
293                             ptr->tlink = temp;
294                     }
295                     else
296                     {
297                         ptr->tlink = temp;
298                     }
299 
300                     ptr = temp;
301                 }
302             }
303         }
304     }
305     return ptr;
306 }

 

删除广义表链表表示

 

  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 Gen * strtogen();
 37 
 38 int main()
 39 {
 40     Gen *ptr = strtogen(); //ptr初始化为广义表附加头结点指针
 41     bool TF = true;
 42     vector<Gen *> stack;
 43 
 44     while (true)
 45     {
 46         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 47         {
 48             if (TF == true)
 49             {
 50                 if (ptr->utype != 0 || ptr->info.ref == 0)
 51                 {
 52                     stack.push_back(ptr);
 53                     if (ptr->utype == 0)
 54                     {
 55                         if (ptr->tlink == nullptr)
 56                         {
 57                             stack.pop_back();
 58                             TF = false;
 59                             continue;
 60                         }
 61                         ptr = ptr->tlink;
 62                         stack[stack.size() - 1]->tlink = ptr->tlink;
 63                     }
 64                     else
 65                     {
 66                         if (ptr->info.hlink->tlink == nullptr)
 67                         {
 68                             delete ptr->info.hlink;
 69                             ptr->info.hlink = nullptr;
 70                             TF = false;
 71                         }
 72                         else
 73                         {
 74                             ptr = ptr->info.hlink;
 75                             stack[stack.size() - 1]->info.hlink = ptr->tlink;
 76                         }
 77                     }
 78                 }
 79                 else
 80                 {
 81                     delete ptr;
 82                     ptr = nullptr;
 83                 }
 84             }
 85             else
 86             {
 87                 if (ptr->utype == 0)
 88                 {
 89                     delete ptr;
 90                     break;
 91                 }
 92                 else
 93                 {
 94                     delete ptr;
 95                     stack.pop_back();
 96                     ptr = nullptr;
 97                 }
 98             }
 99         }
100         else
101         {
102             if (ptr == nullptr)
103             {
104                 if (stack[stack.size() - 1]->utype == 0)
105                 {
106                     if (stack[stack.size() - 1]->tlink == nullptr)
107                     {
108                         TF = false;
109                         ptr = stack[stack.size() - 1];
110                         stack.pop_back();
111                     }
112                     else
113                     {
114                         ptr = stack[stack.size() - 1]->tlink;
115                         stack[stack.size() - 1]->tlink = ptr->tlink;
116                         TF = true;
117                     }
118                 }
119                 else
120                 {
121                     if (stack[stack.size() - 1]->info.hlink == nullptr)
122                     {
123                         TF = false;
124                         ptr = stack[stack.size()-1];
125                     }
126                     else
127                     {
128                         ptr = stack[stack.size() - 1]->info.hlink;
129                         stack[stack.size() - 1]->info.hlink = ptr->tlink;
130                         TF = true;
131                     }
132                 }
133             }
134             else
135             {
136                 if (stack[stack.size() - 1]->utype == 0)
137                 {
138                     if (stack[stack.size() - 1]->tlink == nullptr)
139                     {
140                         delete ptr;
141                         ptr = stack[stack.size() - 1];
142                         stack.pop_back();
143                         TF = false;
144                     }
145                     else
146                     {
147                         delete ptr;
148                         ptr = stack[stack.size() - 1]->tlink;
149                         stack[stack.size() - 1]->tlink = ptr->tlink;
150                     }
151                 }
152                 else
153                 {
154                     if (stack[stack.size() - 1]->info.hlink == nullptr)
155                     {
156                         delete ptr;
157                         ptr = stack[stack.size() - 1];
158                         TF = false;
159                     }
160                     else
161                     {
162                         delete ptr;
163                         ptr = stack[stack.size() - 1]->info.hlink;
164                         stack[stack.size() - 1]->info.hlink = ptr->tlink;
165                     }
166                 }
167             }
168         }
169     }
170     //运行结束后ptr成为野指针,栈空,删除成功
171     cout << "链表形式的广义表删除成功!"<< endl;
172     return 0;
173 }
174 
175 Gen * strtogen()
176 {
177     string glist;
178     cout << "请输入广义表的字符串形式" << endl;
179     cin >> glist;
180 
181     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
182     int ref = 0;
183     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
184     {
185         if (*i == '(')
186         {
187             if (i == glist.cbegin())
188             {
189                 ptr = new Gen(0, 0);
190                 stack.push_back(ptr);
191                 TF = true;
192             }
193             else
194             {
195                 Gen *temp = new Gen(1);
196                 if (ptr->utype == 1)
197                 {
198                     if (TF == true)
199                         ptr->info.hlink->tlink = temp;
200                     else
201                         ptr->tlink = temp;
202                 }
203                 else
204                 {
205                     ptr->tlink = temp;
206                 }
207 
208                 stack.push_back(temp);
209                 TF = true;
210                 ptr = temp;
211                 temp = new Gen(0, ++ref);
212                 ptr->info.hlink = temp;
213             }
214         }
215         else
216         {
217             if (*i == ')')
218             {
219                 ptr = stack[stack.size() - 1];
220                 stack.pop_back();
221                 TF = false;
222             }
223             else
224             {
225                 if (*i != ',')
226                 {
227                     Gen *temp = new Gen(2, *i);
228                     if (ptr->utype == 1)
229                     {
230                         if (TF == true)
231                             ptr->info.hlink->tlink = temp;
232                         else
233                             ptr->tlink = temp;
234                     }
235                     else
236                     {
237                         ptr->tlink = temp;
238                     }
239 
240                     ptr = temp;
241                 }
242             }
243         }
244     }
245     return ptr;
246 }

 

求指定深度的所有子表

 

  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 class Gennode
 37 {
 38 public:
 39     int numnode;
 40     Gen *ptr;
 41     Gennode(Gen *p) :ptr(p), numnode(0) {}
 42 };
 43 
 44 void output(vector<Gennode> &stack);
 45 void suboutput(Gen *head);
 46 Gen * strtogen();
 47 
 48 int main()
 49 {
 50     int depth = 0; int maxdepth;
 51     int flag = 0; 
 52     int subcount = 0; int emptycount = 0;
 53     bool TF = true;
 54     vector<Gennode> stack;
 55     Gen *ptr=strtogen();//ptr应初始化为指向广义表附加头节点的指针
 56     cout << "请输入指定深度:" << endl;
 57     cin >> maxdepth;
 58     while (true)
 59     {
 60         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 61         {
 62             if (TF == true)
 63             {
 64                 if (ptr->utype != 0 || ptr->info.ref == 0)
 65                 {
 66                     if (depth == maxdepth)
 67                     {
 68                         ptr = ptr->tlink;
 69                         flag = 1;
 70                         ++stack[stack.size() - 1].numnode;
 71                         continue;
 72                     }
 73                     depth++;
 74 
 75                     if (ptr->utype == 0)
 76                     {
 77                         Gennode temp(ptr);
 78                         stack.push_back(temp);
 79                         flag = 0;
 80                         ptr = ptr->tlink;
 81                     }
 82                     else
 83                     {
 84                         ++stack[stack.size() - 1].numnode;
 85                         Gennode temp(ptr);
 86                         stack.push_back(temp);
 87                         flag = 2;
 88                         ptr = ptr->info.hlink;
 89                     }
 90                 }
 91                 else
 92                 {
 93                     ptr = ptr->tlink;
 94                 }
 95             }
 96             else
 97             {
 98                 if (ptr->utype == 0)
 99                     break;
100                 else
101                 {
102                     ptr = ptr->tlink;
103                     flag = 1;
104                     TF = true;
105                 }
106             }
107         }
108         else
109         {
110             if (ptr == nullptr)
111             {
112                 if (depth == maxdepth)
113                 {
114                     subcount++;
115                     if (flag == 2) //找到一个子空表
116                     {
117                         ++emptycount;
118                         //栈中存有完整位置信息,输出之
119                         cout << "第" << subcount << "个指定深度的子表,为空表:()" << endl;
120                         cout << " 长度:" << 0 << endl;
121                         cout << "位置:" << endl;
122                         output(stack);
123                     }
124                     else
125                     {
126                         if (flag == 1)
127                         {
128                             //找到一个非空子表
129                             cout << "第" << subcount << "个指定深度的子表(非空):";
130                                 suboutput(stack[stack.size() - 1].ptr);
131                                 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
132                                 cout << " 长度:" << stack[stack.size() - 1].numnode << endl;
133                             cout << "位置:" << endl;
134                             if (stack[stack.size() - 1].ptr->utype == 0)
135                             {
136                                 //当前非空子表为广义表本身,
137                                 cout << "该非空子表为广义表本身" << endl;
138                             }
139                             else
140                             {
141                                 //当前非空子表为真子表，栈中存有完整位置信息,输出之
142                                 output(stack);
143                             }
144                         }
145                         else
146                         {
147                             ++emptycount;
148                             //找到子空表,即为广义表本身,输出之
149                             cout << "第" << subcount << "个指定深度的子表,为空表:()" << endl;
150                             cout << " 长度:" << 0 << endl;
151                             cout << "位置:" << endl;
152                             cout << "该子空表为广义表本身" << endl;
153                         }
154                     }
155                 }
156 
157                 depth--;
158                 ptr = stack[stack.size() - 1].ptr;
159                 stack.pop_back();
160                 TF = false;
161             }
162             else
163             {
164                 ++stack[stack.size() - 1].numnode;
165                 ptr = ptr->tlink;
166                 flag = 1;
167             }
168         }
169     }
170     cout << "共有" << subcount << "个指定深度的子表,其中有" << emptycount << "个空表" << endl;
171     return 0;
172 }
173 
174 void output(vector<Gennode> &stack)
175 {
176     for (auto i = stack.begin(); i != stack.end() - 1; ++i)
177     {
178         if (i == stack.begin())
179         {
180             cout << "广义表的第" << (*i).numnode << "个表元素";
181         }
182         else
183         {
184             cout << "的第" << (*i).numnode << "个表元素";
185         }
186     }
187     cout << endl;
188 }
189 
190 void suboutput(Gen *head)
191 {
192     Gen *ptr = head;
193     bool TF = true;
194     vector<Gen *> stack;
195     while (true)
196     {
197         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
198         {
199             if (TF == true)
200             {
201                 if (ptr->utype == 0)   //注意
202                 {
203                     if (ptr->info.ref == 0)
204                     {
205                         stack.push_back(ptr);
206                         cout << "(";
207                     }
208                     ptr = ptr->tlink;
209                 }
210                 else
211                 {
212                     stack.push_back(ptr);
213                     cout << "(";
214                     ptr = ptr->info.hlink;
215                 }
216             }
217             else
218             {
219                 if (ptr == head)
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->tlink != nullptr && ptr != head)    //注意
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 }
250 
251 Gen * strtogen()
252 {
253     string glist;
254     cout << "请输入广义表的字符串形式" << endl;
255     cin >> glist;
256 
257     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
258     int ref = 0;
259     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
260     {
261         if (*i == '(')
262         {
263             if (i == glist.cbegin())
264             {
265                 ptr = new Gen(0, 0);
266                 stack.push_back(ptr);
267                 TF = true;
268             }
269             else
270             {
271                 Gen *temp = new Gen(1);
272                 if (ptr->utype == 1)
273                 {
274                     if (TF == true)
275                         ptr->info.hlink->tlink = temp;
276                     else
277                         ptr->tlink = temp;
278                 }
279                 else
280                 {
281                     ptr->tlink = temp;
282                 }
283 
284                 stack.push_back(temp);
285                 TF = true;
286                 ptr = temp;
287                 temp = new Gen(0, ++ref);
288                 ptr->info.hlink = temp;
289             }
290         }
291         else
292         {
293             if (*i == ')')
294             {
295                 ptr = stack[stack.size() - 1];
296                 stack.pop_back();
297                 TF = false;
298             }
299             else
300             {
301                 if (*i != ',')
302                 {
303                     Gen *temp = new Gen(2, *i);
304                     if (ptr->utype == 1)
305                     {
306                         if (TF == true)
307                             ptr->info.hlink->tlink = temp;
308                         else
309                             ptr->tlink = temp;
310                     }
311                     else
312                     {
313                         ptr->tlink = temp;
314                     }
315 
316                     ptr = temp;
317                 }
318             }
319         }
320     }
321     return ptr;
322 }

 

计算各子表在广义表字符串中的起始终止位置

 

  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 class Gennode
 37 {
 38 public:
 39     int numnode;
 40     Gen *ptr;
 41     Gennode(Gen *p) :ptr(p), numnode(0) {}
 42 };
 43 
 44 class position
 45 {
 46 public:
 47     int place;
 48     int index;
 49     position(int p, int i) :place(p), index(i) {}
 50 };
 51 
 52 void suboutput(Gen *head);
 53 Gen * strtogen();
 54 
 55 int main()
 56 {
 57     int flag = 0;
 58     bool TF = true;
 59     vector<Gennode> stack;
 60     vector<position> match;
 61     int left = 0, right = 0, total = 0;
 62     Gen *ptr = strtogen();//ptr应初始化为指向广义表附加头节点的指针
 63 
 64     while (true)
 65     {
 66         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 67         {
 68             if (TF == true)
 69             {
 70                 if (ptr->utype != 0 || ptr->info.ref == 0)
 71                 {
 72                     ++left;
 73                     ++total;
 74                     position temp(total, left);
 75                     match.push_back(temp);
 76                     if (ptr->utype == 0)
 77                     {
 78                         Gennode temp(ptr);
 79                         stack.push_back(temp);
 80                         flag = 0;
 81                         ptr = ptr->tlink;
 82                     }
 83                     else
 84                     {
 85                         ++stack[stack.size() - 1].numnode;
 86                         Gennode temp(ptr);
 87                         stack.push_back(temp);
 88                         flag = 2;
 89                         ptr = ptr->info.hlink;
 90                     }
 91                 }
 92                 else
 93                 {
 94                     ptr = ptr->tlink;
 95                 }
 96             }
 97             else
 98             {
 99                 if (ptr->utype == 0)
100                     break;
101                 else
102                 {
103                     ptr = ptr->tlink;
104                     flag = 1;
105                     TF = true;
106                 }
107             }
108         }
109         else
110         {
111             if (ptr == nullptr)
112             {
113                 ++right;
114                 ++total;
115                     if (flag == 2) //找到一个子空表
116                     {
117                         cout << "子表 ():";
118                     }
119                     else
120                     {
121                         if (flag == 1)
122                         {
123                             //找到一个非空子表
124                             cout << "子表 ";
125                             suboutput(stack[stack.size() - 1].ptr);
126                                 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
127                             cout << ":";
128                         }
129                         else
130                         {
131                             cout << "子表 ():";
132                         }
133                     }
134                     cout << endl;
135                     cout << " 长度:" << stack[stack.size() - 1].numnode << endl;
136                     cout << "(为从左至右数起第" << match[match.size() - 1].index << "个 ";
137                         cout << ")为第" << right << "个 ";
138                     cout << "(下标为" << match[match.size() - 1].place << " )下标为" << total << endl;
139                     cout << endl;
140                     match.pop_back();
141 
142                 ptr = stack[stack.size() - 1].ptr;
143                 if (ptr->utype != 0 && ptr->tlink != nullptr)
144                     ++total;
145                 stack.pop_back();
146                 TF = false;
147             }
148             else
149             {
150                 ++stack[stack.size() - 1].numnode;
151                 ++total;
152                 ptr = ptr->tlink;
153                 if (ptr != nullptr)
154                     ++total;
155                 flag = 1;
156             }
157         }
158     }
159     return 0;
160 }
161 
162 void suboutput(Gen *head)
163 {
164     Gen *ptr = head;
165     bool TF = true;
166     vector<Gen *> stack;
167     while (true)
168     {
169         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
170         {
171             if (TF == true)
172             {
173                 if (ptr->utype == 0)   //注意
174                 {
175                     if (ptr->info.ref == 0)
176                     {
177                         stack.push_back(ptr);
178                         cout << "(";
179                     }
180                     ptr = ptr->tlink;
181                 }
182                 else
183                 {
184                     stack.push_back(ptr);
185                     cout << "(";
186                     ptr = ptr->info.hlink;
187                 }
188             }
189             else
190             {
191                 if (ptr == head)
192                     break;
193                 else
194                 {
195                     ptr = ptr->tlink;
196                     TF = true;
197                 }
198             }
199         }
200         else
201         {
202             if (ptr == nullptr)
203             {
204                 cout << ")";
205                 ptr = stack[stack.size() - 1];
206                 if (ptr->tlink != nullptr && ptr != head)    //注意
207                     cout << ",";
208                 stack.pop_back();
209                 TF = false;
210             }
211             else
212             {
213                 cout << ptr->info.value;
214                 ptr = ptr->tlink;
215                 if (ptr != nullptr)
216                     cout << ",";
217             }
218         }
219     }
220 }
221 
222 Gen * strtogen()
223 {
224     string glist;
225     cout << "请输入广义表的字符串形式" << endl;
226     cin >> glist;
227 
228     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
229     int ref = 0;
230     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
231     {
232         if (*i == '(')
233         {
234             if (i == glist.cbegin())
235             {
236                 ptr = new Gen(0, 0);
237                 stack.push_back(ptr);
238                 TF = true;
239             }
240             else
241             {
242                 Gen *temp = new Gen(1);
243                 if (ptr->utype == 1)
244                 {
245                     if (TF == true)
246                         ptr->info.hlink->tlink = temp;
247                     else
248                         ptr->tlink = temp;
249                 }
250                 else
251                 {
252                     ptr->tlink = temp;
253                 }
254 
255                 stack.push_back(temp);
256                 TF = true;
257                 ptr = temp;
258                 temp = new Gen(0, ++ref);
259                 ptr->info.hlink = temp;
260             }
261         }
262         else
263         {
264             if (*i == ')')
265             {
266                 ptr = stack[stack.size() - 1];
267                 stack.pop_back();
268                 TF = false;
269             }
270             else
271             {
272                 if (*i != ',')
273                 {
274                     Gen *temp = new Gen(2, *i);
275                     if (ptr->utype == 1)
276                     {
277                         if (TF == true)
278                             ptr->info.hlink->tlink = temp;
279                         else
280                             ptr->tlink = temp;
281                     }
282                     else
283                     {
284                         ptr->tlink = temp;
285                     }
286 
287                     ptr = temp;
288                 }
289             }
290         }
291     }
292     return ptr;
293 }

 

基于链表表示拷贝广义表

 

  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 Gen * strtogen();
 37 void suboutput(Gen *head);
 38 
 39 int main()
 40 {
 41     vector<Gen *> stack1;//源栈 
 42     vector<Gen *> stack2;//目标栈
 43     Gen *ptr1=strtogen(); //ptr1初始化为源广义表附加头节点指针
 44     Gen *ptr2=nullptr; //ptr2为目标广义表拷贝指针
 45     bool TF = true;
 46 
 47     while (true)
 48     {
 49         if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
 50         {
 51             if (TF == true)
 52             {
 53                 if (ptr1->utype == 0)
 54                 {
 55                     Gen *temp = new Gen(0, ptr1->info.ref);
 56                     if (ptr1->info.ref == 0)
 57                     {
 58                         stack1.push_back(ptr1);
 59                         stack2.push_back(temp);
 60                     }
 61                     else
 62                     {
 63                         ptr2->info.hlink = temp;
 64                     }
 65                     ptr2 = temp;
 66                     ptr1 = ptr1->tlink;
 67                 }
 68                 else
 69                 {
 70                     Gen *temp = new Gen(1);
 71                     temp->info.hlink = new Gen(0, ptr1->info.hlink->info.ref);
 72                     if (ptr2->utype == 1)
 73                     {
 74                         if (ptr2 == stack2[stack2.size() - 1])
 75                             ptr2->info.hlink->tlink = temp;
 76                         else
 77                             ptr2->tlink = temp;
 78                     }
 79                     else
 80                     {
 81                         ptr2->tlink = temp;
 82                     }
 83                     ptr2 = temp;
 84                     stack2.push_back(ptr2);
 85                     stack1.push_back(ptr1);
 86                     ptr1 = ptr1->info.hlink->tlink;
 87                 }
 88             }
 89             else
 90             {
 91                 if (ptr1->utype == 0)
 92                 {
 93                     ptr2 = stack2[stack2.size() - 1];
 94                     stack2.pop_back();
 95                     break; //拷贝完毕
 96                 }
 97                 else
 98                 {
 99                     ptr2 = stack2[stack2.size() - 1];
100                     stack2.pop_back();
101                     ptr1 = ptr1->tlink;
102                     TF = true;
103                 }
104             }
105         }
106         else
107         {
108             if (ptr1 == nullptr)
109             {
110                 ptr2 = nullptr;
111                 ptr1 = stack1[stack1.size() - 1];
112                 stack1.pop_back();
113                 TF = false;
114             }
115             else
116             {
117                 Gen *temp = new Gen(2, ptr1->info.value);
118                 if (ptr2->utype == 1 && stack2[stack2.size() - 1] == ptr2)
119                     ptr2->info.hlink->tlink = temp;
120                 else
121                     ptr2->tlink = temp;
122                 ptr2 = temp;
123                 ptr1 = ptr1->tlink;
124             }
125         }
126     }
127     cout << "复制完成,复制后的广义表为:";
128     suboutput(ptr2);
129     return 0;
130 }
131 
132 void suboutput(Gen *head)
133 {
134     Gen *ptr = head;
135     bool TF = true;
136     vector<Gen *> stack;
137     while (true)
138     {
139         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
140         {
141             if (TF == true)
142             {
143                 if (ptr->utype == 0)   //注意
144                 {
145                     if (ptr->info.ref == 0)
146                     {
147                         stack.push_back(ptr);
148                         cout << "(";
149                     }
150                     ptr = ptr->tlink;
151                 }
152                 else
153                 {
154                     stack.push_back(ptr);
155                     cout << "(";
156                     ptr = ptr->info.hlink;
157                 }
158             }
159             else
160             {
161                 if (ptr == head)
162                     break;
163                 else
164                 {
165                     ptr = ptr->tlink;
166                     TF = true;
167                 }
168             }
169         }
170         else
171         {
172             if (ptr == nullptr)
173             {
174                 cout << ")";
175                 ptr = stack[stack.size() - 1];
176                 if (ptr->tlink != nullptr && ptr != head)    //注意
177                     cout << ",";
178                 stack.pop_back();
179                 TF = false;
180             }
181             else
182             {
183                 cout << ptr->info.value;
184                 ptr = ptr->tlink;
185                 if (ptr != nullptr)
186                     cout << ",";
187             }
188         }
189     }
190     cout << endl;
191 }
192 
193 Gen * strtogen()
194 {
195     string glist;
196     cout << "请输入广义表的字符串形式" << endl;
197     cin >> glist;
198 
199     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
200     int ref = 0;
201     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
202     {
203         if (*i == '(')
204         {
205             if (i == glist.cbegin())
206             {
207                 ptr = new Gen(0, 0);
208                 stack.push_back(ptr);
209                 TF = true;
210             }
211             else
212             {
213                 Gen *temp = new Gen(1);
214                 if (ptr->utype == 1)
215                 {
216                     if (TF == true)
217                         ptr->info.hlink->tlink = temp;
218                     else
219                         ptr->tlink = temp;
220                 }
221                 else
222                 {
223                     ptr->tlink = temp;
224                 }
225 
226                 stack.push_back(temp);
227                 TF = true;
228                 ptr = temp;
229                 temp = new Gen(0, ++ref);
230                 ptr->info.hlink = temp;
231             }
232         }
233         else
234         {
235             if (*i == ')')
236             {
237                 ptr = stack[stack.size() - 1];
238                 stack.pop_back();
239                 TF = false;
240             }
241             else
242             {
243                 if (*i != ',')
244                 {
245                     Gen *temp = new Gen(2, *i);
246                     if (ptr->utype == 1)
247                     {
248                         if (TF == true)
249                             ptr->info.hlink->tlink = temp;
250                         else
251                             ptr->tlink = temp;
252                     }
253                     else
254                     {
255                         ptr->tlink = temp;
256                     }
257 
258                     ptr = temp;
259                 }
260             }
261         }
262     }
263     return ptr;
264 }

 

基于链表表示比较广义表

 

  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 
 36 bool equals(Gen *ptr1, Gen *ptr2);
 37 Gen * strtogen();
 38 
 39 int main()
 40 {
 41     vector<Gen *> stack1; vector<Gen *> stack2;
 42     Gen *ptr1 = strtogen(); //指向广义表1附加头节点
 43     Gen *ptr2 = strtogen(); //指向广义表2附加头节点
 44     //两指针同步动作
 45     bool TF = true;
 46     int isequals = 1;
 47     while (true)
 48     {
 49         if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
 50         {
 51             if (TF == true)
 52             {
 53                 if (ptr1->utype == 0)
 54                 {
 55                     stack1.push_back(ptr1);
 56                     stack2.push_back(ptr2);
 57                     ptr1 = ptr1->tlink;
 58                     ptr2 = ptr2->tlink;
 59                 }
 60                 else
 61                 {
 62                     if (equals(ptr1, ptr2) == true)
 63                     {
 64                         stack1.push_back(ptr1);
 65                         stack2.push_back(ptr2);
 66                         ptr1 = ptr1->info.hlink->tlink;
 67                         ptr2 = ptr2->info.hlink->tlink;
 68                     }
 69                     else
 70                     {
 71                         isequals = 0;
 72                         break;
 73                     }
 74                 }
 75             }
 76             else
 77             {
 78                 if (ptr1->utype == 0)
 79                     break;
 80                 else
 81                 {
 82                     ptr1 = ptr1->tlink;
 83                     ptr2 = ptr2->tlink;
 84                     TF = true;
 85                 }
 86             }
 87         }
 88         else
 89         {
 90             if (ptr1 == nullptr)
 91             {
 92                 if (equals(ptr1, ptr2) == true)
 93                 {
 94                     ptr1 = stack1[stack1.size() - 1];
 95                     ptr2 = stack2[stack2.size() - 1];
 96                     stack1.pop_back();
 97                     stack2.pop_back();
 98                     TF = false;
 99                 }
100                 else
101                 {
102                     isequals = 0;
103                     break;
104                 }
105             }
106             else
107             {
108                 if (equals(ptr1, ptr2) == true)
109                 {
110                     ptr1 = ptr1->tlink;
111                     ptr2 = ptr2->tlink;
112                 }
113                 else
114                 {
115                     isequals = 0;
116                     break;
117                 }
118             }
119         }
120     }
121     if (isequals)
122         cout << "两广义表相等";
123     else
124         cout << "两广义表不等";
125     cout << endl;
126     return 0;
127 }
128 
129 bool equals(Gen *ptr1, Gen *ptr2)
130 {
131     if (ptr1 == nullptr && ptr2 == nullptr)
132         return true;
133     else
134     {
135         if (ptr1 != nullptr && ptr2 != nullptr)
136         {
137             if (ptr1->utype != ptr2->utype)
138                 return false;
139             else
140             {
141                 if (ptr1->utype == 1)
142                     return true;
143                 else
144                 {
145                     if (ptr1->info.value == ptr2->info.value)
146                         return true;
147                     else
148                         return false;
149                 }
150             }
151         }
152         else
153         {
154             return false;
155         }
156     }
157 }
158 
159 Gen *strtogen()
160 {
161     string glist;
162     cout << "请输入广义表的字符串形式" << endl;
163     cin >> glist;
164 
165     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
166     int ref = 0;
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, 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->tlink = 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                 temp = new Gen(0, ++ref);
196                 ptr->info.hlink = temp;
197             }
198         }
199         else
200         {
201             if (*i == ')')
202             {
203                 ptr = stack[stack.size() - 1];
204                 stack.pop_back();
205                 TF = false;
206             }
207             else
208             {
209                 if (*i != ',')
210                 {
211                     Gen *temp = new Gen(2, *i);
212                     if (ptr->utype == 1)
213                     {
214                         if (TF == true)
215                             ptr->info.hlink->tlink = temp;
216                         else
217                             ptr->tlink = temp;
218                     }
219                     else
220                     {
221                         ptr->tlink = temp;
222                     }
223 
224                     ptr = temp;
225                 }
226             }
227         }
228     }
229     return ptr;
230 }

 

广义表字符串形式和链表表示的转换

 

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <string>
  4 #include <vector>
  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     Gen(int u, int r);
 20 };
 21 Gen::Gen(int u) :utype(u), tlink(nullptr)
 22 {
 23     info.hlink = nullptr;
 24 }
 25 
 26 Gen::Gen(int u, int r) :utype(u), tlink(nullptr)
 27 {
 28     info.ref = r;
 29 }
 30 
 31 Gen::Gen(int u, char v) :utype(u), tlink(nullptr)
 32 {
 33     info.value = v;
 34 }
 35 int main()
 36 {
 37     string glist;
 38     cout << "请输入广义表的字符串形式" << endl;
 39     cin >> glist;
 40 
 41     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
 42     int ref = 0;
 43     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
 44     {
 45         if (*i == '(')
 46         {
 47             if (i == glist.cbegin())
 48             {
 49                 ptr = new Gen(0, 0);
 50                 stack.push_back(ptr);
 51                 TF = true;
 52             }
 53             else
 54             {
 55                 Gen *temp = new Gen(1);
 56                 if (ptr->utype == 1)
 57                 {
 58                     if (TF == true)
 59                         ptr->info.hlink->tlink = temp;
 60                     else
 61                         ptr->tlink = temp;
 62                 }
 63                 else
 64                 {
 65                     ptr->tlink = temp;
 66                 }
 67 
 68                 stack.push_back(temp);
 69                 TF = true;
 70                 ptr = temp;
 71                 temp = new Gen(0, ++ref);
 72                 ptr->info.hlink = temp;
 73             }
 74         }
 75         else
 76         {
 77             if (*i == ')')
 78             {
 79                 ptr = stack[stack.size() - 1];
 80                 stack.pop_back();
 81                 TF = false;
 82             }
 83             else
 84             {
 85                 if (*i != ',')
 86                 {
 87                     Gen *temp = new Gen(2, *i);
 88                     if (ptr->utype == 1)
 89                     {
 90                         if (TF == true)
 91                             ptr->info.hlink->tlink = temp;
 92                         else
 93                             ptr->tlink = temp;
 94                     }
 95                     else
 96                     {
 97                         ptr->tlink = temp;
 98                     }
 99 
100                     ptr = temp;
101                 }
102             }
103         }
104     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
105     cout << "已将广义表的字符串形式转换为带附加头节点的链表形式" << endl;
106     cout << "链表表示对应的广义表形式为:" << endl;
107     TF = true;
108     while (true)
109     { 
110         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
111         {
112             if (TF == true)
113             {
114                 if (ptr->utype == 0)   //注意
115                 {
116                     if (ptr->info.ref == 0)
117                     {
118                         stack.push_back(ptr);
119                         cout << "(";
120                     }
121                     ptr = ptr->tlink;
122                 }
123                 else
124                 {
125                     stack.push_back(ptr);
126                     cout << "(";
127                     ptr = ptr->info.hlink;
128                 }
129             }
130             else
131             {
132                 if (ptr->utype == 0)
133                     break;
134                 else
135                 {
136                     ptr = ptr->tlink;
137                     TF = true;
138                 }
139             }
140         }
141         else
142         {
143             if (ptr == nullptr)
144             {
145                 cout << ")";
146                 ptr = stack[stack.size() - 1];       
147                 if (ptr->utype != 0 && ptr->tlink != nullptr)    //注意
148                     cout << ",";
149                 stack.pop_back();
150                 TF = false;
151             }
152             else
153             {
154                 cout << ptr->info.value;
155                 ptr = ptr->tlink;
156                 if (ptr != nullptr)
157                     cout << ",";
158             }
159         }
160     }
161     cout << endl;
162     return 0;
163 }

 

广义表的链表表示和多叉树的相互转换

 

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <string>
  5 using namespace std;
  6 
  7 class Knode
  8 {
  9 public:
 10     char data;
 11     Knode **p;
 12     Knode(int k, char ch);
 13 };
 14 
 15 Knode::Knode(int k, char ch='\0')
 16 {
 17     data = ch;
 18     p = new Knode *[k]();
 19 }
 20 
 21 class Path    
 22 {
 23 public:
 24     Knode *current;   
 25     int direction;  
 26     Path(Knode *ptr, int d) :current(ptr), direction(d) {}
 27 };
 28 
 29 struct Gen
 30 {
 31     int utype;
 32     union
 33     {
 34         int ref;
 35         struct Gen *hlink;
 36         char value;
 37     }info;
 38     struct Gen *tlink;
 39     Gen(int u);
 40     Gen(int u, char v);
 41     Gen(int u, int r);
 42 };
 43 Gen::Gen(int u) :utype(u), tlink(nullptr)
 44 {
 45     info.hlink = nullptr;
 46 }
 47 
 48 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 49 {
 50     info.ref = r;
 51 }
 52 
 53 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 54 {
 55     info.value = v;
 56 }
 57 
 58 class Gennode
 59 {
 60 public:
 61     int numnode;
 62     Gen *ptr;
 63     Gennode(Gen *p) :ptr(p), numnode(-1) {}
 64 };
 65 
 66 int Search(Knode *ptr, int d, const int k);
 67 int Enable(Knode *ptr, int m);
 68 void suboutput(Gen *head);
 69 Gen * strtogen(string &glist);
 70 int maxlength(string &glist);
 71 
 72 int main()
 73 {
 74     string glist;
 75     cout << "请输入广义表的字符串形式" << endl;
 76     cin >> glist;
 77     Gen *ptr = strtogen(glist);//ptr初始化为指向广义表附加头结点的指针
 78     int k = maxlength(glist);
 79     bool TF = true; vector<Knode *> treestack; vector<Gennode> genstack;
 80     Knode *dest = nullptr;
 81     while (true)
 82     {
 83         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 84         {
 85             if (TF == true)
 86             {
 87                 if (ptr->utype == 0)
 88                 {
 89                     if (ptr->info.ref == 0)
 90                     {
 91                         Gennode temp(ptr);
 92                         genstack.push_back(temp);
 93                         dest = new Knode(k);
 94                         treestack.push_back(dest);
 95                     }
 96                     ptr = ptr->tlink;
 97                 }
 98                 else
 99                 {
100                     Knode *temp = new Knode(k);
101                     dest->p[++genstack[genstack.size() - 1].numnode] = temp;
102                     dest = temp;
103                     treestack.push_back(dest);
104                     Gennode temp2(ptr);
105                     genstack.push_back(temp2);
106                     ptr = ptr->info.hlink;
107                 }
108             }
109             else
110             {
111                 if (ptr->utype == 0)
112                     break;
113                 else
114                 {
115                     ptr = ptr->tlink;
116                     TF = true;
117                 }
118             }
119         }
120         else
121         {
122             if (ptr == nullptr)
123             {
124                 treestack.pop_back();
125                 if (treestack.size() != 0)
126                     dest = treestack[treestack.size() - 1];
127 
128                 ptr = genstack[genstack.size() - 1].ptr;
129                 genstack.pop_back();
130                 TF = false;
131             }
132             else
133             {
134                 Knode *temp = new Knode(k, ptr->info.value);
135                 dest->p[++genstack[genstack.size() - 1].numnode] = temp;
136                 ptr = ptr->tlink;
137             }
138         }
139     }  //dest即为根节点指针
140 
141     cout << "已将广义表链表表示转化为K叉树" << endl;
142     vector<Path> treestack2; vector<Gen *> genstack2;
143     int ref = 0;
144     Gen *p = new Gen(0, ref); 
145     genstack2.push_back(p);
146 
147     Knode *ptr1 = dest;
148     int d = 0;
149 
150     while (true)
151     {
152         if (Search(ptr1, d, k) == 0)
153         {
154             if (ptr1 == dest)
155             {
156                 p = genstack2[genstack2.size() - 1];
157                 break;   //p即为广义表附加头结点指针
158             }
159             else
160             {
161                 if (d == 0)
162                 {
163                     Gen *temp;
164                     if (ptr1->data == '\0')
165                     {
166                         temp = new Gen(1);
167                         temp->info.hlink = new Gen(0, ++ref);
168                     }
169                     else
170                         temp = new Gen(2, ptr1->data);
171 
172                     if (p->utype == 1)
173                     {
174                         if (TF == true)
175                         {
176                             p->info.hlink->tlink = temp;
177                             if (temp->utype == 1)
178                                 TF = false;
179                         }
180                         else
181                         {
182                             p->tlink = temp;
183                         }
184                     }
185                     else
186                     {
187                         p->tlink = temp;
188                         if (temp->utype == 1)
189                             TF = false;
190                     }
191                     p = temp;
192                     d = treestack2[treestack2.size() - 1].direction;
193                     ptr1 = treestack2[treestack2.size() - 1].current;
194                 }
195                 else
196                 {
197                     p = genstack2[genstack2.size() - 1];
198                     genstack2.pop_back();
199                     treestack2.pop_back();
200                     d = treestack2[treestack2.size() - 1].direction;
201                     ptr1 = treestack2[treestack2.size() - 1].current;
202                     TF = false;
203                 }
204             }
205         }
206         else
207         {
208             Knode *interval = nullptr;
209             if (d == 0)
210             {
211                 if (ptr1 != dest)
212                 {
213                     Gen *temp = new Gen(1);
214                     temp->info.hlink = new Gen(0, ++ref);
215                     if (p->utype == 1)
216                     {
217                         if (TF == true)
218                         {
219                             p->info.hlink->tlink = temp;
220                         }
221                         else
222                         {
223                             p->tlink = temp;
224                         }
225                     }
226                     else
227                     {
228                         p->tlink = temp;
229                     }
230                     p = temp;
231                     genstack2.push_back(p);
232                     TF = true;
233                 }
234                 Path temp = Path(ptr1, Search(ptr1, d, k));
235                 interval = ptr1->p[temp.direction - 1];
236                 treestack2.push_back(temp);
237             }
238             else
239             {
240                 treestack2[treestack2.size() - 1].direction = Search(ptr1, d, k);
241                 interval = ptr1->p[treestack2[treestack2.size() - 1].direction - 1];
242             }
243             ptr1 = interval;
244             d = 0;
245         }
246     }
247     cout << "已将K叉树转换为广义表链表表示"<<endl;
248     cout << "链表表示对应的广义表形式为:"<<endl;
249     suboutput(p);
250     return 0;
251 }
252 int Search(Knode *ptr, int d, const int k)
253 {
254     int m = d;
255     for (m++; m <= k; m++)
256     {
257         if (Enable(ptr, m) == 1)
258             return m;
259     }
260     return 0;
261 }
262 
263 int Enable(Knode *ptr, int m)
264 {
265     if (ptr->p[m - 1] != nullptr)
266         return 1;
267     else
268         return 0;
269 }
270 
271 void suboutput(Gen *head)
272 {
273     Gen *ptr = head;
274     bool TF = true;
275     vector<Gen *> stack;
276     while (true)
277     {
278         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
279         {
280             if (TF == true)
281             {
282                 if (ptr->utype == 0)   //注意
283                 {
284                     if (ptr->info.ref == 0)
285                     {
286                         stack.push_back(ptr);
287                         cout << "(";
288                     }
289                     ptr = ptr->tlink;
290                 }
291                 else
292                 {
293                     stack.push_back(ptr);
294                     cout << "(";
295                     ptr = ptr->info.hlink;
296                 }
297             }
298             else
299             {
300                 if (ptr == head)
301                     break;
302                 else
303                 {
304                     ptr = ptr->tlink;
305                     TF = true;
306                 }
307             }
308         }
309         else
310         {
311             if (ptr == nullptr)
312             {
313                 cout << ")";
314                 ptr = stack[stack.size() - 1];
315                 if (ptr->tlink != nullptr && ptr != head)    //注意
316                     cout << ",";
317                 stack.pop_back();
318                 TF = false;
319             }
320             else
321             {
322                 cout << ptr->info.value;
323                 ptr = ptr->tlink;
324                 if (ptr != nullptr)
325                     cout << ",";
326             }
327         }
328     }
329     cout << endl;
330 }
331 
332 Gen * strtogen(string &glist)
333 {
334     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
335     int ref = 0;
336     for (auto i = glist.cbegin(); i != glist.cend(); ++i)
337     {
338         if (*i == '(')
339         {
340             if (i == glist.cbegin())
341             {
342                 ptr = new Gen(0, 0);
343                 stack.push_back(ptr);
344                 TF = true;
345             }
346             else
347             {
348                 Gen *temp = new Gen(1);
349                 if (ptr->utype == 1)
350                 {
351                     if (TF == true)
352                         ptr->info.hlink->tlink = temp;
353                     else
354                         ptr->tlink = temp;
355                 }
356                 else
357                 {
358                     ptr->tlink = temp;
359                 }
360 
361                 stack.push_back(temp);
362                 TF = true;
363                 ptr = temp;
364                 temp = new Gen(0, ++ref);
365                 ptr->info.hlink = temp;
366             }
367         }
368         else
369         {
370             if (*i == ')')
371             {
372                 ptr = stack[stack.size() - 1];
373                 stack.pop_back();
374                 TF = false;
375             }
376             else
377             {
378                 if (*i != ',')
379                 {
380                     Gen *temp = new Gen(2, *i);
381                     if (ptr->utype == 1)
382                     {
383                         if (TF == true)
384                             ptr->info.hlink->tlink = temp;
385                         else
386                             ptr->tlink = temp;
387                     }
388                     else
389                     {
390                         ptr->tlink = temp;
391                     }
392 
393                     ptr = temp;
394                 }
395             }
396         }
397     }
398     cout << "已将字符串形式转换为链表表示"<<endl;
399     return ptr;
400 }
401 
402 int maxlength(string &glist)
403 {
404     int maxlen = 0; vector<int> stack;
405     for (const auto &s : glist)
406     {
407         if (s == '(')
408         {
409             if (stack.size() != 0)
410                ++stack[stack.size() - 1];
411             stack.push_back(0);
412         }
413         else if (s == ')')
414         {
415             if (stack[stack.size() - 1] > maxlen)
416                 maxlen = stack[stack.size() - 1];
417             stack.pop_back();
418         }
419         else if (s != ',')
420         {
421             ++stack[stack.size() - 1];
422         }
423     }
424     return maxlen;
425 }

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：洛谷P2181 对角线(组合数)

下一篇：enote笔记语言（3）（ver0.3）

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签