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

用非递归方法实现共享表运算

2018-06-17 21:15:03来源：未知阅读 ()

这里把无共享表的广义表的运算代码(基于附加头节点的链表表示)稍作修改，得到了基于附加头节点链表表示的共享表运算代码，这里就不详细注释了，可以参考之前发布的无共享表运算代码的注释来帮助理解，在共享表运算代码里映射表标准库类型map起到了重要作用

广义表(包括共享表情形)字符串形式和链表表示的相互转换：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <string>
  4 #include <vector>
  5 #include <map>
  6 using namespace std;
  7 
  8 struct Gen
  9 {
 10     int utype;
 11     union
 12     {
 13         int ref;
 14         struct Gen *hlink;
 15         char value;
 16     }info;
 17     struct Gen *tlink;
 18     Gen(int u);
 19     Gen(int u, char v);
 20     Gen(int u, int r);
 21 };
 22 Gen::Gen(int u) :utype(u), tlink(nullptr)
 23 {
 24     info.hlink = nullptr;
 25 }
 26 
 27 Gen::Gen(int u, int r) :utype(u), tlink(nullptr)
 28 {
 29     info.ref = r;
 30 }
 31 
 32 Gen::Gen(int u, char v) :utype(u), tlink(nullptr)
 33 {
 34     info.value = v;
 35 }
 36 
 37 class info
 38 {
 39 public:
 40     vector<int> left;
 41     vector<int> right;
 42     Gen *share = nullptr;
 43     vector<int>::size_type position = 0;
 44 };
 45 
 46 void creatsharelist(string &glist, map<string, info> &sharelist);
 47 map<string, info>::iterator Search(int left, map<string, info> &sharelist);
 48 
 49 int main()
 50 {
 51     string glist;
 52     cout << "请输入广义表的字符串形式" << endl;
 53     cin >> glist;
 54     map<string, info> sharelist;
 55 
 56     creatsharelist(glist, sharelist);
 57 
 58     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
 59     int ref = 0;
 60     for (string::size_type i = 0; i != glist.size(); ++i)
 61     {
 62         if (glist[i] == '(')
 63         {
 64             if (i == 0)
 65             {
 66                 ptr = new Gen(0, 0);
 67                 stack.push_back(ptr);
 68                 TF = true;
 69             }
 70             else
 71             {
 72                 Gen *temp = new Gen(1);
 73                 if (ptr->utype == 1)
 74                 {
 75                     if (TF == true)
 76                         ptr->info.hlink->tlink = temp;
 77                     else
 78                         ptr->tlink = temp;
 79                 }
 80                 else
 81                 {
 82                     ptr->tlink = temp;
 83                 }
 84 
 85                 auto p = Search(i + 1, sharelist);
 86                 if (p != sharelist.end() && p->second.share != nullptr)
 87                 {
 88                     temp->info.hlink = p->second.share;
 89                     ++p->second.share->info.ref;
 90                     TF = false;
 91                     ptr = temp;
 92                     i = p->second.right[p->second.position-1]-1;
 93                     continue;
 94                 }
 95                 else
 96                 {
 97                     stack.push_back(temp);
 98                     TF = true;
 99                     ptr = temp;
100                     temp = new Gen(0, 1);
101                     ptr->info.hlink = temp;
102                     if (p != sharelist.end())
103                        p->second.share = ptr->info.hlink;
104                 }
105             }
106         }
107         else
108         {
109             if (glist[i] == ')')
110             {
111                 ptr = stack[stack.size() - 1];
112                 stack.pop_back();
113                 TF = false;
114             }
115             else
116             {
117                 if (glist[i] != ',')
118                 {
119                     Gen *temp = new Gen(2, glist[i]);
120                     if (ptr->utype == 1)
121                     {
122                         if (TF == true)
123                             ptr->info.hlink->tlink = temp;
124                         else
125                             ptr->tlink = temp;
126                     }
127                     else
128                     {
129                         ptr->tlink = temp;
130                     }
131 
132                     ptr = temp;
133                 }
134             }
135         }
136     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
137     cout << "已将广义表的字符串形式转换为带附加头节点的链表形式" << endl;
138     cout << "链表表示对应的广义表形式为:" << endl;
139     TF = true;
140     while (true)
141     { 
142         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
143         {
144             if (TF == true)
145             {
146                 if (ptr->utype == 0)   //注意
147                 {
148                     if (ptr->info.ref == 0)
149                     {
150                         stack.push_back(ptr);
151                         cout << "(";
152                     }
153                     ptr = ptr->tlink;
154                 }
155                 else
156                 {
157                     stack.push_back(ptr);
158                     cout << "(";
159                     ptr = ptr->info.hlink;
160                 }
161             }
162             else
163             {
164                 if (ptr->utype == 0)
165                     break;
166                 else
167                 {
168                     ptr = ptr->tlink;
169                     TF = true;
170                 }
171             }
172         }
173         else
174         {
175             if (ptr == nullptr)
176             {
177                 cout << ")";
178                 ptr = stack[stack.size() - 1];       
179                 if (ptr->utype != 0 && ptr->tlink != nullptr)    //注意
180                     cout << ",";
181                 stack.pop_back();
182                 TF = false;
183             }
184             else
185             {
186                 cout << ptr->info.value;
187                 ptr = ptr->tlink;
188                 if (ptr != nullptr)
189                     cout << ",";
190             }
191         }
192     }
193     cout << endl;
194     return 0;
195 }
196 
197 void creatsharelist(string &glist, map<string, info> &sharelist)
198 {
199     vector<int> stack;
200     int total = 0;
201     for (const auto &s : glist)
202     {
203         if (s == '(')
204         { 
205             ++total;
206             stack.push_back(total);
207         }
208         else if (s == ')')
209         {
210             ++total;
211             string temp = glist.substr(stack[stack.size() - 1] - 1, total - stack[stack.size() - 1] + 1);
212             auto p = sharelist.find(temp);
213             if (p == sharelist.end())
214             {
215                 auto q = sharelist.insert(make_pair(temp, *(new info)));
216                 q.first->second.left.push_back(stack[stack.size() - 1]);
217                 q.first->second.right.push_back(total);
218             }
219             else
220             {
221                 p->second.left.push_back(stack[stack.size() - 1]);
222                 p->second.right.push_back(total);
223             }
224             stack.pop_back();
225         }
226         else
227         {
228             ++total;
229         }
230     }
231 
232     auto m = sharelist.begin();
233     while (m != sharelist.end())
234     {
235         if (m->second.left.size() == 1)
236             m = sharelist.erase(m);
237         else
238             ++m;
239     }
240 }
241 
242 map<string, info>::iterator Search(int left, map<string, info> &sharelist)
243 {
244     auto p = sharelist.begin();
245     for (; p != sharelist.end(); ++p)
246     {
247         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
248         {
249             ++p->second.position;
250             return p;
251         }
252     }
253     return p;
254 }

广义表(包括共享表情形)字符串形式和多叉树（包括共享树）

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <string>
  4 #include <vector>
  5 #include <map>
  6 using namespace std;
  7 
  8 class Knode
  9 {
 10 public:
 11     char data;
 12     int ref;
 13     Knode **p;
 14     Knode(int k, int r, char ch);
 15 };
 16 
 17 Knode::Knode(int k, int r, char ch = '\0')
 18 {
 19     ref = r;
 20     data = ch;
 21     p = new Knode *[k]();
 22 }
 23 
 24 class Gennode
 25 {
 26 public:
 27     int numnode;
 28     Knode *ptr;
 29     Gennode(Knode *p) :ptr(p), numnode(-1) {}
 30 };
 31 
 32 class Path
 33 {
 34 public:
 35     Knode *current;
 36     int direction;
 37     Path(Knode *ptr, int d) :current(ptr), direction(d) {}
 38 };
 39 
 40 class info
 41 {
 42 public:
 43     vector<int> left;
 44     vector<int> right;
 45     Knode *share = nullptr;
 46     vector<int>::size_type position = 0;
 47 };
 48 
 49 int Search(Knode *ptr, int d, const int k);
 50 int Enable(Knode *ptr, int m);
 51 int creatsharelist(string &glist, map<string, info> &sharelist);
 52 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 53 
 54 int main()
 55 {
 56     string glist;
 57     cout << "请输入广义表的字符串形式" << endl;
 58     cin >> glist;
 59     map<string, info> sharelist;
 60 
 61     Knode *ptr = nullptr; vector<Gennode> stack; int k = creatsharelist(glist, sharelist);
 62     for (string::size_type i = 0; i != glist.size(); ++i)
 63     {
 64         if (glist[i] == '(')
 65         {
 66             if (i == 0)
 67             {
 68                 ptr = new Knode(k, 0);
 69                 Gennode temp(ptr);
 70                 stack.push_back(temp);
 71             }
 72             else
 73             {
 74                 auto p = Searchshare(i + 1, sharelist);
 75                 if (p != sharelist.end())
 76                 {
 77                     if (p->second.share != nullptr)
 78                     {
 79                         ptr->p[++stack[stack.size() - 1].numnode] = p->second.share;
 80                         ++p->second.share->ref;
 81                         i = p->second.right[p->second.position - 1] - 1;
 82                         continue;
 83                     }
 84                 }
 85                 Knode *temp = new Knode(k, 1);
 86                 ptr->p[++stack[stack.size() - 1].numnode] = temp;
 87                 ptr = temp;
 88                 Gennode temp2(ptr);
 89                 stack.push_back(temp2);
 90                 if (p != sharelist.end())
 91                     p->second.share = ptr;
 92             }
 93         }
 94         else
 95         {
 96             if (glist[i] == ')')
 97             {
 98                 stack.pop_back();
 99                 if (stack.size() != 0)
100                     ptr = stack[stack.size() - 1].ptr;
101             }
102             else
103             {
104                 if (glist[i] != ',')
105                 {
106                     Knode *temp = new Knode(k, 1, glist[i]);
107                     ptr->p[++stack[stack.size() - 1].numnode] = temp;
108                 }
109             }
110         }
111     }//扫描完后ptr即为k叉树根节点指针
112     cout << "已将字符串形式的广义表转换为K叉树" << endl;
113 
114     vector<Path> treestack;
115     Knode *const dest = ptr;
116     int d = 0;
117 
118     cout << "该K叉树对应的广义表形式为:" << endl;
119     cout << "(";
120     while (true)
121     {
122         if (Search(ptr, d, k) == 0)
123         {
124             if (ptr == dest)
125             {
126                 cout << ")";
127                 break;
128             }
129             else
130             {
131                 if (d == 0)
132                 {
133                     if (ptr->data == '\0')
134                     {
135                         cout << "()";
136                     }
137                     else
138                     {
139                         cout << ptr->data;
140                     }
141                 }
142                 else
143                 {
144                     cout << ")";
145                     treestack.pop_back();
146                 }
147                 ptr = treestack[treestack.size() - 1].current;
148                 d = treestack[treestack.size() - 1].direction;
149             }
150         }
151         else
152         {
153             Knode *interval = nullptr;
154             if (d == 0)
155             {
156                 if (ptr != dest)
157                     cout << "(";
158                 Path temp(ptr, Search(ptr, d, k));
159                 interval = ptr->p[temp.direction-1];
160                 treestack.push_back(temp);
161             }
162             else
163             {
164                 cout << ",";
165                 treestack[treestack.size() - 1].direction = Search(ptr, d, k);
166                 interval = ptr->p[treestack[treestack.size() - 1].direction - 1];
167             }
168             ptr = interval;
169             d = 0;
170         }
171     }
172     return 0;
173 }
174 
175 int Search(Knode *ptr, int d, const int k)
176 {
177     int m = d;
178     for (m++; m <= k; m++)
179     {
180         if (Enable(ptr, m) == 1)
181             return m;
182     }
183     return 0;
184 }
185 
186 int Enable(Knode *ptr, int m)
187 {
188     if (ptr->p[m - 1] != nullptr)
189         return 1;
190     else
191         return 0;
192 }
193 
194 int creatsharelist(string &glist, map<string, info> &sharelist)
195 {
196     class node
197     {
198     public:
199         int left;
200         int numnode=0;
201         node(int l) :left(l) {}
202     };
203 
204     vector<node> stack;
205     int total = 0, maxlen=0;
206     for (const auto &s : glist)
207     {
208         if (s == '(')
209         {
210             if (stack.size() != 0)
211                 ++stack[stack.size() - 1].numnode;
212             ++total;
213             stack.push_back(*(new node(total)));
214         }
215         else if (s == ')')
216         {
217             ++total;
218             string temp = glist.substr(stack[stack.size() - 1].left - 1, total - stack[stack.size() - 1].left + 1);
219             auto p = sharelist.find(temp);
220             if (p == sharelist.end())
221             {
222                 if (stack[stack.size() - 1].numnode>maxlen)
223                     maxlen = stack[stack.size() - 1].numnode;
224 
225                 auto q = sharelist.insert(make_pair(temp, *(new info)));
226                 q.first->second.left.push_back(stack[stack.size() - 1].left);
227                 q.first->second.right.push_back(total);
228             }
229             else
230             {
231                 p->second.left.push_back(stack[stack.size() - 1].left);
232                 p->second.right.push_back(total);
233             }
234             stack.pop_back();
235         }
236         else
237         {
238             if (s!=',')
239                 ++stack[stack.size() - 1].numnode;
240             ++total;
241         }
242     }
243 
244     auto m = sharelist.begin();
245     while (m != sharelist.end())
246     {
247         if (m->second.left.size() == 1)
248             m = sharelist.erase(m);
249         else
250             ++m;
251     }
252 
253     return maxlen;
254 }
255 
256 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
257 {
258     auto p = sharelist.begin();
259     for (; p != sharelist.end(); ++p)
260     {
261         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
262         {
263             ++p->second.position;
264             return p;
265         }
266     }
267     return p;
268 }

广义表（包括共享表情形）链表表示和多叉树（包括共享树情形）的相互转换：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <string>
  5 #include <map>
  6 using namespace std;
  7 
  8 class Knode
  9 {
 10 public:
 11     char data;
 12     int ref;
 13     Knode **p;
 14     Knode(int k, int r, char ch);
 15 };
 16 
 17 Knode::Knode(int k, int r, char ch = '\0')
 18 {
 19     ref = r;
 20     data = ch;
 21     p = new Knode *[k]();
 22 }
 23 
 24 class Path    
 25 {
 26 public:
 27     Knode *current;   
 28     int direction;  
 29     Path(Knode *ptr, int d) :current(ptr), direction(d) {}
 30 };
 31 
 32 struct Gen
 33 {
 34     int utype;
 35     union
 36     {
 37         int ref;
 38         struct Gen *hlink;
 39         char value;
 40     }info;
 41     struct Gen *tlink;
 42     Gen(int u);
 43     Gen(int u, char v);
 44     Gen(int u, int r);
 45 };
 46 Gen::Gen(int u) :utype(u), tlink(nullptr)
 47 {
 48     info.hlink = nullptr;
 49 }
 50 
 51 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 52 {
 53     info.ref = r;
 54 }
 55 
 56 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 57 {
 58     info.value = v;
 59 }
 60 
 61 class Gennode
 62 {
 63 public:
 64     int numnode;
 65     Gen *ptr;
 66     Gennode(Gen *p) :ptr(p), numnode(-1) {}
 67 };
 68 
 69 class info
 70 {
 71 public:
 72     vector<int> left;
 73     vector<int> right;
 74     Gen *share = nullptr;
 75     vector<int>::size_type position = 0;
 76 };
 77 
 78 int Search(Knode *ptr, int d, const int k);
 79 int Enable(Knode *ptr, int m);
 80 void suboutput(Gen *head);
 81 Gen * strtogen(string &glist, int &k);
 82 int creatsharelist(string &glist, map<string, info> &sharelist);
 83 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 84 
 85 int main()
 86 {
 87     string glist;
 88     cout << "请输入广义表的字符串形式" << endl;
 89     cin >> glist;
 90     int k;
 91     Gen *ptr = strtogen(glist, k);//ptr初始化为指向广义表附加头结点的指针
 92     bool TF = true; vector<Knode *> treestack; vector<Gennode> genstack;
 93     map<Gen *, Knode *> sharelist;
 94     Knode *dest = nullptr;
 95     while (true)
 96     {
 97         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 98         {
 99             if (TF == true)
100             {
101                 if (ptr->utype == 0)
102                 {
103                     if (ptr->info.ref == 0)
104                     {
105                         Gennode temp(ptr);
106                         genstack.push_back(temp);
107                         dest = new Knode(k, 0);
108                         treestack.push_back(dest);
109                     }
110                     ptr = ptr->tlink;
111                 }
112                 else
113                 {
114                     if (ptr->info.hlink->info.ref > 1)
115                     {
116                         auto p = sharelist.find(ptr->info.hlink);
117                         if (p != sharelist.end())
118                         {
119                             dest->p[++genstack[genstack.size() - 1].numnode] = p->second;
120                             ++p->second->ref;
121                             TF = false;
122                             continue;
123                         }
124                     }
125 
126                     Knode *temp = new Knode(k, 1);
127                     dest->p[++genstack[genstack.size() - 1].numnode] = temp;
128                     dest = temp;
129                     treestack.push_back(dest);
130                     Gennode temp2(ptr);
131                     genstack.push_back(temp2);
132                     ptr = ptr->info.hlink;
133                     if (ptr->info.ref > 1)
134                         sharelist.insert(make_pair(ptr, dest));
135                 }
136             }
137             else
138             {
139                 if (ptr->utype == 0)
140                     break;
141                 else
142                 {
143                     ptr = ptr->tlink;
144                     TF = true;
145                 }
146             }
147         }
148         else
149         {
150             if (ptr == nullptr)
151             {
152                 treestack.pop_back();
153                 if (treestack.size() != 0)
154                     dest = treestack[treestack.size() - 1];
155 
156                 ptr = genstack[genstack.size() - 1].ptr;
157                 genstack.pop_back();
158                 TF = false;
159             }
160             else
161             {
162                 Knode *temp = new Knode(k, 1, ptr->info.value);
163                 dest->p[++genstack[genstack.size() - 1].numnode] = temp;
164                 ptr = ptr->tlink;
165             }
166         }
167     }  //dest即为根节点指针
168 
169     cout << "已将广义表链表表示转化为K叉树" << endl;
170     vector<Path> treestack2; vector<Gen *> genstack2;
171     map<Knode *, Gen *> sharetree;
172     Gen *p = new Gen(0, 0); 
173     genstack2.push_back(p);
174 
175     Knode *ptr1 = dest;
176     int d = 0;
177 
178     while (true)
179     {
180         if (Search(ptr1, d, k) == 0)
181         {
182             if (ptr1 == dest)
183             {
184                 p = genstack2[genstack2.size() - 1];
185                 break;   //p即为广义表附加头结点指针
186             }
187             else
188             {
189                 if (d == 0)
190                 {
191                     Gen *temp;
192                     if (ptr1->data == '\0')
193                     {
194                         if (ptr1->ref>1)
195                         {
196                             auto q = sharetree.find(ptr1);
197                             temp = new Gen(1);
198                             if (q != sharetree.end())
199                             {
200                                 temp->info.hlink = q->second;
201                                 ++q->second->info.ref;
202                             }
203                             else
204                             {
205                                 temp->info.hlink = new Gen(0, 1);
206                                 sharetree.insert(make_pair(ptr1, temp->info.hlink));
207                             }
208                         }
209                         else
210                         {
211                             temp = new Gen(1);
212                             temp->info.hlink = new Gen(0, 1);
213                         }
214                     }
215                     else
216                     { 
217                         temp = new Gen(2, ptr1->data);
218                     }
219 
220                     if (p->utype == 1)
221                     {
222                         if (TF == true)
223                         {
224                             p->info.hlink->tlink = temp;
225                             if (temp->utype == 1)
226                                 TF = false;
227                         }
228                         else
229                         {
230                             p->tlink = temp;
231                         }
232                     }
233                     else
234                     {
235                         p->tlink = temp;
236                         if (temp->utype == 1)
237                             TF = false;
238                     }
239                     p = temp;
240                     d = treestack2[treestack2.size() - 1].direction;
241                     ptr1 = treestack2[treestack2.size() - 1].current;
242                 }
243                 else
244                 {
245                     p = genstack2[genstack2.size() - 1];
246                     genstack2.pop_back();
247                     treestack2.pop_back();
248                     d = treestack2[treestack2.size() - 1].direction;
249                     ptr1 = treestack2[treestack2.size() - 1].current;
250                     TF = false;
251                 }
252             }
253         }
254         else
255         {
256             Knode *interval = nullptr;
257             if (d == 0)
258             {
259                 if (ptr1 != dest)
260                 {
261                     Gen *temp = new Gen(1);
262                     if (ptr1->ref > 1)
263                     {
264                         auto q = sharetree.find(ptr1);
265                         if (q != sharetree.end())
266                         {
267                             temp->info.hlink = q->second;
268                             ++q->second->info.ref;
269                         }
270                         else
271                         {
272                             temp->info.hlink = new Gen(0, 1);
273                             sharetree.insert(make_pair(ptr1, temp->info.hlink));
274                         }
275                     }
276                     else
277                     {
278                         temp->info.hlink = new Gen(0, 1);
279                     }
280                     
281                     if (p->utype == 1)
282                     {
283                         if (TF == true)
284                         {
285                             p->info.hlink->tlink = temp;
286                         }
287                         else
288                         {
289                             p->tlink = temp;
290                         }
291                     }
292                     else
293                     {
294                         p->tlink = temp;
295                     }
296 
297                     p = temp;
298                     if (p->info.hlink->info.ref > 1)
299                     {
300                         d = treestack2[treestack2.size() - 1].direction;
301                         ptr1 = treestack2[treestack2.size() - 1].current;
302                         TF = false;
303                         continue;
304                     }
305                     else
306                     {
307                         genstack2.push_back(p);
308                         TF = true;
309                     }
310                 }
311                 Path temp = Path(ptr1, Search(ptr1, d, k));
312                 interval = ptr1->p[temp.direction - 1];
313                 treestack2.push_back(temp);
314             }
315             else
316             {
317                 treestack2[treestack2.size() - 1].direction = Search(ptr1, d, k);
318                 interval = ptr1->p[treestack2[treestack2.size() - 1].direction - 1];
319             }
320             ptr1 = interval;
321             d = 0;
322         }
323     }
324     cout << "已将K叉树转换为广义表链表表示"<<endl;
325     cout << "链表表示对应的广义表形式为:"<<endl;
326     suboutput(p);
327     return 0;
328 }
329 int Search(Knode *ptr, int d, const int k)
330 {
331     int m = d;
332     for (m++; m <= k; m++)
333     {
334         if (Enable(ptr, m) == 1)
335             return m;
336     }
337     return 0;
338 }
339 
340 int Enable(Knode *ptr, int m)
341 {
342     if (ptr->p[m - 1] != nullptr)
343         return 1;
344     else
345         return 0;
346 }
347 
348 void suboutput(Gen *head)
349 {
350     Gen *ptr = head;
351     bool TF = true;
352     vector<Gen *> stack;
353     while (true)
354     {
355         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
356         {
357             if (TF == true)
358             {
359                 if (ptr->utype == 0)   //注意
360                 {
361                     if (ptr->info.ref == 0)
362                     {
363                         stack.push_back(ptr);
364                         cout << "(";
365                     }
366                     ptr = ptr->tlink;
367                 }
368                 else
369                 {
370                     stack.push_back(ptr);
371                     cout << "(";
372                     ptr = ptr->info.hlink;
373                 }
374             }
375             else
376             {
377                 if (ptr == head)
378                     break;
379                 else
380                 {
381                     ptr = ptr->tlink;
382                     TF = true;
383                 }
384             }
385         }
386         else
387         {
388             if (ptr == nullptr)
389             {
390                 cout << ")";
391                 ptr = stack[stack.size() - 1];
392                 if (ptr->tlink != nullptr && ptr != head)    //注意
393                     cout << ",";
394                 stack.pop_back();
395                 TF = false;
396             }
397             else
398             {
399                 cout << ptr->info.value;
400                 ptr = ptr->tlink;
401                 if (ptr != nullptr)
402                     cout << ",";
403             }
404         }
405     }
406     cout << endl;
407 }
408 
409 Gen * strtogen(string &glist, int &k)
410 {
411     map<string, info> sharelist;
412 
413     k=creatsharelist(glist, sharelist);
414 
415     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
416     int ref = 0;
417     for (string::size_type i = 0; i != glist.size(); ++i)
418     {
419         if (glist[i] == '(')
420         {
421             if (i == 0)
422             {
423                 ptr = new Gen(0, 0);
424                 stack.push_back(ptr);
425                 TF = true;
426             }
427             else
428             {
429                 Gen *temp = new Gen(1);
430                 if (ptr->utype == 1)
431                 {
432                     if (TF == true)
433                         ptr->info.hlink->tlink = temp;
434                     else
435                         ptr->tlink = temp;
436                 }
437                 else
438                 {
439                     ptr->tlink = temp;
440                 }
441 
442                 auto p = Searchshare(i + 1, sharelist);
443                 if (p != sharelist.end() && p->second.share != nullptr)
444                 {
445                     temp->info.hlink = p->second.share;
446                     ++p->second.share->info.ref;
447                     TF = false;
448                     ptr = temp;
449                     i = p->second.right[p->second.position - 1] - 1;
450                     continue;
451                 }
452                 else
453                 {
454                     stack.push_back(temp);
455                     TF = true;
456                     ptr = temp;
457                     temp = new Gen(0, 1);
458                     ptr->info.hlink = temp;
459                     if (p != sharelist.end())
460                         p->second.share = ptr->info.hlink;
461                 }
462             }
463         }
464         else
465         {
466             if (glist[i] == ')')
467             {
468                 ptr = stack[stack.size() - 1];
469                 stack.pop_back();
470                 TF = false;
471             }
472             else
473             {
474                 if (glist[i] != ',')
475                 {
476                     Gen *temp = new Gen(2, glist[i]);
477                     if (ptr->utype == 1)
478                     {
479                         if (TF == true)
480                             ptr->info.hlink->tlink = temp;
481                         else
482                             ptr->tlink = temp;
483                     }
484                     else
485                     {
486                         ptr->tlink = temp;
487                     }
488 
489                     ptr = temp;
490                 }
491             }
492         }
493     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
494     cout << "已将字符串形式转换为链表表示"<<endl;
495     return ptr;
496 }
497 
498 int creatsharelist(string &glist, map<string, info> &sharelist)
499 {
500         class node
501         {
502         public:
503             int left;
504             int numnode = 0;
505             node(int l) :left(l) {}
506         };
507 
508         vector<node> stack;
509         int total = 0, maxlen = 0;
510         for (const auto &s : glist)
511         {
512             if (s == '(')
513             {
514                 if (stack.size() != 0)
515                     ++stack[stack.size() - 1].numnode;
516                 ++total;
517                 stack.push_back(*(new node(total)));
518             }
519             else if (s == ')')
520             {
521                 ++total;
522                 string temp = glist.substr(stack[stack.size() - 1].left - 1, total - stack[stack.size() - 1].left + 1);
523                 auto p = sharelist.find(temp);
524                 if (p == sharelist.end())
525                 {
526                     if (stack[stack.size() - 1].numnode>maxlen)
527                         maxlen = stack[stack.size() - 1].numnode;
528 
529                     auto q = sharelist.insert(make_pair(temp, *(new info)));
530                     q.first->second.left.push_back(stack[stack.size() - 1].left);
531                     q.first->second.right.push_back(total);
532                 }
533                 else
534                 {
535                     p->second.left.push_back(stack[stack.size() - 1].left);
536                     p->second.right.push_back(total);
537                 }
538                 stack.pop_back();
539             }
540             else
541             {
542                 if (s != ',')
543                     ++stack[stack.size() - 1].numnode;
544                 ++total;
545             }
546         }
547 
548         auto m = sharelist.begin();
549         while (m != sharelist.end())
550         {
551             if (m->second.left.size() == 1)
552                 m = sharelist.erase(m);
553             else
554                 ++m;
555         }
556 
557         return maxlen;
558 }
559 
560 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
561 {
562     auto p = sharelist.begin();
563     for (; p != sharelist.end(); ++p)
564     {
565         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
566         {
567             ++p->second.position;
568             return p;
569         }
570     }
571     return p;
572 }

共享树链表表示的删除：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include<string>
  5 #include <map>
  6 using namespace std;
  7 
  8 struct Gen
  9 {
 10     int utype;
 11     union
 12     {
 13         int ref;
 14         struct Gen *hlink;
 15         char value;
 16     }info;
 17     struct Gen *tlink;
 18     Gen(int u);
 19     Gen(int u, char v);
 20     Gen(int u, int r);
 21 };
 22 Gen::Gen(int u) :utype(u), tlink(nullptr)
 23 {
 24     info.hlink = nullptr;
 25 }
 26 
 27 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 28 {
 29     info.ref = r;
 30 }
 31 
 32 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 33 {
 34     info.value = v;
 35 }
 36 
 37 class info
 38 {
 39 public:
 40     vector<int> left;
 41     vector<int> right;
 42     Gen *share = nullptr;
 43     vector<int>::size_type position = 0;
 44 };
 45 
 46 Gen * strtogen();
 47 void creatsharelist(string &glist, map<string, info> &sharelist);
 48 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 49 
 50 int main()
 51 {
 52     Gen *ptr = strtogen(); //ptr初始化为广义表附加头结点指针
 53     bool TF = true;
 54     vector<Gen *> stack;
 55 
 56     while (true)
 57     {
 58         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 59         {
 60             if (TF == true)
 61             {
 62                     stack.push_back(ptr);
 63                     if (ptr->utype == 0)
 64                     {
 65                         if (ptr->tlink == nullptr)
 66                         {
 67                             stack.pop_back();
 68                             TF = false;
 69                             continue;
 70                         }
 71                         ptr = ptr->tlink;
 72                         stack[stack.size() - 1]->tlink = ptr->tlink;
 73                     }
 74                     else
 75                     {
 76                         if (--ptr->info.hlink->info.ref > 0)
 77                         {
 78                             TF = false;
 79                             continue;
 80                         }
 81                         else
 82                         {
 83                             if (ptr->info.hlink->tlink == nullptr)
 84                             {
 85                                 delete ptr->info.hlink;
 86                                 ptr->info.hlink = nullptr;
 87                                 TF = false;
 88                             }
 89                             else
 90                             {
 91                                 ptr = ptr->info.hlink;
 92                                 stack[stack.size() - 1]->info.hlink = ptr->tlink;
 93                                 delete ptr;
 94                                 ptr = nullptr;
 95                             }
 96                         }
 97                     }
 98             }
 99             else
100             {
101                 if (ptr->utype == 0)
102                 {
103                     delete ptr;
104                     break;
105                 }
106                 else
107                 {
108                     stack.pop_back();
109                     delete ptr;
110                     ptr = nullptr;
111                 }
112             }
113         }
114         else
115         {
116             if (ptr == nullptr)
117             {
118                 if (stack[stack.size() - 1]->utype == 0)
119                 {
120                     if (stack[stack.size() - 1]->tlink == nullptr)
121                     {
122                         TF = false;
123                         ptr = stack[stack.size() - 1];
124                         stack.pop_back();
125                     }
126                     else
127                     {
128                         ptr = stack[stack.size() - 1]->tlink;
129                         stack[stack.size() - 1]->tlink = ptr->tlink;
130                         TF = true;
131                     }
132                 }
133                 else
134                 {
135                     if (stack[stack.size() - 1]->info.hlink == nullptr)
136                     {
137                         TF = false;
138                         ptr = stack[stack.size()-1];
139                     }
140                     else
141                     {
142                         ptr = stack[stack.size() - 1]->info.hlink;
143                         stack[stack.size() - 1]->info.hlink = ptr->tlink;
144                         TF = true;
145                     }
146                 }
147             }
148             else
149             {
150                 if (stack[stack.size() - 1]->utype == 0)
151                 {
152                     if (stack[stack.size() - 1]->tlink == nullptr)
153                     {
154                         delete ptr;
155                         ptr = stack[stack.size() - 1];
156                         stack.pop_back();
157                         TF = false;
158                     }
159                     else
160                     {
161                         delete ptr;
162                         ptr = stack[stack.size() - 1]->tlink;
163                         stack[stack.size() - 1]->tlink = ptr->tlink;
164                     }
165                 }
166                 else
167                 {
168                     if (stack[stack.size() - 1]->info.hlink == nullptr)
169                     {
170                         delete ptr;
171                         ptr = stack[stack.size() - 1];
172                         TF = false;
173                     }
174                     else
175                     {
176                         delete ptr;
177                         ptr = stack[stack.size() - 1]->info.hlink;
178                         stack[stack.size() - 1]->info.hlink = ptr->tlink;
179                     }
180                 }
181             }
182         }
183     }
184     //运行结束后ptr成为野指针,栈空,删除成功
185     cout << "链表形式的广义表删除成功!"<< endl;
186     return 0;
187 }
188 
189 Gen * strtogen()
190 {
191     string glist;
192     cout << "请输入广义表的字符串形式" << endl;
193     cin >> glist;
194     map<string, info> sharelist;
195 
196     creatsharelist(glist, sharelist);
197 
198     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
199     int ref = 0;
200     for (string::size_type i = 0; i != glist.size(); ++i)
201     {
202         if (glist[i] == '(')
203         {
204             if (i == 0)
205             {
206                 ptr = new Gen(0, 0);
207                 stack.push_back(ptr);
208                 TF = true;
209             }
210             else
211             {
212                 Gen *temp = new Gen(1);
213                 if (ptr->utype == 1)
214                 {
215                     if (TF == true)
216                         ptr->info.hlink->tlink = temp;
217                     else
218                         ptr->tlink = temp;
219                 }
220                 else
221                 {
222                     ptr->tlink = temp;
223                 }
224 
225                 auto p = Searchshare(i + 1, sharelist);
226                 if (p != sharelist.end() && p->second.share != nullptr)
227                 {
228                     temp->info.hlink = p->second.share;
229                     ++p->second.share->info.ref;
230                     TF = false;
231                     ptr = temp;
232                     i = p->second.right[p->second.position - 1] - 1;
233                     continue;
234                 }
235                 else
236                 {
237                     stack.push_back(temp);
238                     TF = true;
239                     ptr = temp;
240                     temp = new Gen(0, 1);
241                     ptr->info.hlink = temp;
242                     if (p != sharelist.end())
243                         p->second.share = ptr->info.hlink;
244                 }
245             }
246         }
247         else
248         {
249             if (glist[i] == ')')
250             {
251                 ptr = stack[stack.size() - 1];
252                 stack.pop_back();
253                 TF = false;
254             }
255             else
256             {
257                 if (glist[i] != ',')
258                 {
259                     Gen *temp = new Gen(2, glist[i]);
260                     if (ptr->utype == 1)
261                     {
262                         if (TF == true)
263                             ptr->info.hlink->tlink = temp;
264                         else
265                             ptr->tlink = temp;
266                     }
267                     else
268                     {
269                         ptr->tlink = temp;
270                     }
271 
272                     ptr = temp;
273                 }
274             }
275         }
276     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
277     cout << "已将字符串形式转换为链表表示" << endl;
278     return ptr;
279 }
280 
281 void creatsharelist(string &glist, map<string, info> &sharelist)
282 {
283     vector<int> stack;
284     int total = 0;
285     for (const auto &s : glist)
286     {
287         if (s == '(')
288         {
289             ++total;
290             stack.push_back(total);
291         }
292         else if (s == ')')
293         {
294             ++total;
295             string temp = glist.substr(stack[stack.size() - 1] - 1, total - stack[stack.size() - 1] + 1);
296             auto p = sharelist.find(temp);
297             if (p == sharelist.end())
298             {
299                 auto q = sharelist.insert(make_pair(temp, *(new info)));
300                 q.first->second.left.push_back(stack[stack.size() - 1]);
301                 q.first->second.right.push_back(total);
302             }
303             else
304             {
305                 p->second.left.push_back(stack[stack.size() - 1]);
306                 p->second.right.push_back(total);
307             }
308             stack.pop_back();
309         }
310         else
311         {
312             ++total;
313         }
314     }
315 
316     auto m = sharelist.begin();
317     while (m != sharelist.end())
318     {
319         if (m->second.left.size() == 1)
320             m = sharelist.erase(m);
321         else
322             ++m;
323     }
324 }
325 
326 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
327 {
328     auto p = sharelist.begin();
329     for (; p != sharelist.end(); ++p)
330     {
331         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
332         {
333             ++p->second.position;
334             return p;
335         }
336     }
337     return p;
338 }

共享表链表表示复制：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <string>
  5 #include <map>
  6 using namespace std;
  7 
  8 struct Gen
  9 {
 10     int utype;
 11     union
 12     {
 13         int ref;
 14         struct Gen *hlink;
 15         char value;
 16     }info;
 17     struct Gen *tlink;
 18     Gen(int u);
 19     Gen(int u, char v);
 20     Gen(int u, int r);
 21 };
 22 Gen::Gen(int u) :utype(u), tlink(nullptr)
 23 {
 24     info.hlink = nullptr;
 25 }
 26 
 27 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 28 {
 29     info.ref = r;
 30 }
 31 
 32 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 33 {
 34     info.value = v;
 35 }
 36 
 37 class info
 38 {
 39 public:
 40     vector<int> left;
 41     vector<int> right;
 42     Gen *share = nullptr;
 43     vector<int>::size_type position = 0;
 44 };
 45 
 46 Gen * strtogen();
 47 void suboutput(Gen *head);
 48 void creatsharelist(string &glist, map<string, info> &sharelist);
 49 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 50 
 51 int main()
 52 {
 53     vector<Gen *> stack1;//源栈 
 54     vector<Gen *> stack2;//目标栈
 55     map<Gen *, Gen *> share;
 56     Gen *ptr1=strtogen(); //ptr1初始化为源广义表附加头节点指针
 57     Gen *ptr2=nullptr; //ptr2为目标广义表拷贝指针
 58     bool TF = true;
 59 
 60     while (true)
 61     {
 62         if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
 63         {
 64             if (TF == true)
 65             {
 66                 if (ptr1->utype == 0)
 67                 {
 68                     Gen *temp = new Gen(0, ptr1->info.ref);
 69                     if (ptr1->info.ref == 0)
 70                     {
 71                         stack1.push_back(ptr1);
 72                         stack2.push_back(temp);
 73                     }
 74                     else
 75                     {
 76                         ptr2->info.hlink = temp;
 77                     }
 78                     ptr2 = temp;
 79                     ptr1 = ptr1->tlink;
 80                 }
 81                 else
 82                 {
 83                     Gen *temp = new Gen(1);
 84                     if (ptr1->info.hlink->info.ref > 1)
 85                     {
 86                         auto p = share.find(ptr1->info.hlink);
 87                         if (p != share.end())
 88                         {
 89                             temp->info.hlink = p->second;
 90                             TF = false;
 91                         }
 92                         else
 93                         {
 94                             temp->info.hlink = new Gen(0, ptr1->info.hlink->info.ref);
 95                             share.insert(make_pair(ptr1->info.hlink, temp->info.hlink));
 96                         }
 97                     }
 98                     else
 99                     {
100                         temp->info.hlink = new Gen(0, ptr1->info.hlink->info.ref);
101                     }
102 
103                     if (ptr2->utype == 1)
104                     {
105                         if (ptr2 == stack2[stack2.size() - 1])
106                             ptr2->info.hlink->tlink = temp;
107                         else
108                             ptr2->tlink = temp;
109                     }
110                     else
111                     {
112                         ptr2->tlink = temp;
113                     }
114                     ptr2 = temp;
115 
116                     if (TF==false)
117                     {
118                         ptr1 = ptr1->tlink;
119                         TF = true;
120                     }
121                     else
122                     {
123                         stack2.push_back(ptr2);
124                         stack1.push_back(ptr1);
125                         ptr1 = ptr1->info.hlink->tlink;
126                     }
127                 }
128             }
129             else
130             {
131                 if (ptr1->utype == 0)
132                 {
133                     ptr2 = stack2[stack2.size() - 1];
134                     stack2.pop_back();
135                     break; //拷贝完毕
136                 }
137                 else
138                 {
139                     ptr2 = stack2[stack2.size() - 1];
140                     stack2.pop_back();
141                     ptr1 = ptr1->tlink;
142                     TF = true;
143                 }
144             }
145         }
146         else
147         {
148             if (ptr1 == nullptr)
149             {
150                 ptr2 = nullptr;
151                 ptr1 = stack1[stack1.size() - 1];
152                 stack1.pop_back();
153                 TF = false;
154             }
155             else
156             {
157                 Gen *temp = new Gen(2, ptr1->info.value);
158                 if (ptr2->utype == 1 && stack2[stack2.size() - 1] == ptr2)
159                     ptr2->info.hlink->tlink = temp;
160                 else
161                     ptr2->tlink = temp;
162                 ptr2 = temp;
163                 ptr1 = ptr1->tlink;
164             }
165         }
166     }
167     cout << "复制完成,复制后的广义表为:";
168     suboutput(ptr2);
169     return 0;
170 }
171 
172 void suboutput(Gen *head)
173 {
174     Gen *ptr = head;
175     bool TF = true;
176     vector<Gen *> stack;
177     while (true)
178     {
179         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
180         {
181             if (TF == true)
182             {
183                 if (ptr->utype == 0)   //注意
184                 {
185                     if (ptr->info.ref == 0)
186                     {
187                         stack.push_back(ptr);
188                         cout << "(";
189                     }
190                     ptr = ptr->tlink;
191                 }
192                 else
193                 {
194                     stack.push_back(ptr);
195                     cout << "(";
196                     ptr = ptr->info.hlink;
197                 }
198             }
199             else
200             {
201                 if (ptr == head)
202                     break;
203                 else
204                 {
205                     ptr = ptr->tlink;
206                     TF = true;
207                 }
208             }
209         }
210         else
211         {
212             if (ptr == nullptr)
213             {
214                 cout << ")";
215                 ptr = stack[stack.size() - 1];
216                 if (ptr->tlink != nullptr && ptr != head)    //注意
217                     cout << ",";
218                 stack.pop_back();
219                 TF = false;
220             }
221             else
222             {
223                 cout << ptr->info.value;
224                 ptr = ptr->tlink;
225                 if (ptr != nullptr)
226                     cout << ",";
227             }
228         }
229     }
230     cout << endl;
231 }
232 
233 Gen * strtogen()
234 {
235     string glist;
236     cout << "请输入广义表的字符串形式" << endl;
237     cin >> glist;
238     map<string, info> sharelist;
239 
240     creatsharelist(glist, sharelist);
241 
242     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
243     int ref = 0;
244     for (string::size_type i = 0; i != glist.size(); ++i)
245     {
246         if (glist[i] == '(')
247         {
248             if (i == 0)
249             {
250                 ptr = new Gen(0, 0);
251                 stack.push_back(ptr);
252                 TF = true;
253             }
254             else
255             {
256                 Gen *temp = new Gen(1);
257                 if (ptr->utype == 1)
258                 {
259                     if (TF == true)
260                         ptr->info.hlink->tlink = temp;
261                     else
262                         ptr->tlink = temp;
263                 }
264                 else
265                 {
266                     ptr->tlink = temp;
267                 }
268 
269                 auto p = Searchshare(i + 1, sharelist);
270                 if (p != sharelist.end() && p->second.share != nullptr)
271                 {
272                     temp->info.hlink = p->second.share;
273                     ++p->second.share->info.ref;
274                     TF = false;
275                     ptr = temp;
276                     i = p->second.right[p->second.position - 1] - 1;
277                     continue;
278                 }
279                 else
280                 {
281                     stack.push_back(temp);
282                     TF = true;
283                     ptr = temp;
284                     temp = new Gen(0, 1);
285                     ptr->info.hlink = temp;
286                     if (p != sharelist.end())
287                         p->second.share = ptr->info.hlink;
288                 }
289             }
290         }
291         else
292         {
293             if (glist[i] == ')')
294             {
295                 ptr = stack[stack.size() - 1];
296                 stack.pop_back();
297                 TF = false;
298             }
299             else
300             {
301                 if (glist[i] != ',')
302                 {
303                     Gen *temp = new Gen(2, glist[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     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
321     cout << "已将字符串形式转换为链表表示" << endl;
322     return ptr;
323 }
324 
325 void creatsharelist(string &glist, map<string, info> &sharelist)
326 {
327     vector<int> stack;
328     int total = 0;
329     for (const auto &s : glist)
330     {
331         if (s == '(')
332         {
333             ++total;
334             stack.push_back(total);
335         }
336         else if (s == ')')
337         {
338             ++total;
339             string temp = glist.substr(stack[stack.size() - 1] - 1, total - stack[stack.size() - 1] + 1);
340             auto p = sharelist.find(temp);
341             if (p == sharelist.end())
342             {
343                 auto q = sharelist.insert(make_pair(temp, *(new info)));
344                 q.first->second.left.push_back(stack[stack.size() - 1]);
345                 q.first->second.right.push_back(total);
346             }
347             else
348             {
349                 p->second.left.push_back(stack[stack.size() - 1]);
350                 p->second.right.push_back(total);
351             }
352             stack.pop_back();
353         }
354         else
355         {
356             ++total;
357         }
358     }
359 
360     auto m = sharelist.begin();
361     while (m != sharelist.end())
362     {
363         if (m->second.left.size() == 1)
364             m = sharelist.erase(m);
365         else
366             ++m;
367     }
368 }
369 
370 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
371 {
372     auto p = sharelist.begin();
373     for (; p != sharelist.end(); ++p)
374     {
375         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
376         {
377             ++p->second.position;
378             return p;
379         }
380     }
381     return p;
382 }

带共享子树的多叉树删除：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <string>
  5 #include <map>
  6 using namespace std;
  7 
  8 class Knode
  9 {
 10 public:
 11     char data;
 12     int ref;
 13     Knode **p;
 14     Knode(int k, int r, char ch);
 15 };
 16 
 17 Knode::Knode(int k, int r, char ch = '\0')
 18 {
 19     ref = r;
 20     data = ch;
 21     p = new Knode *[k]();
 22 }
 23 
 24 class Path
 25 {
 26 public:
 27     Knode *ptr;
 28     int num;
 29     Path(Knode *ptr, int d) :ptr(ptr), num(d) {}
 30 };
 31 
 32 class Gennode
 33 {
 34 public:
 35     int numnode;
 36     Knode *ptr;
 37     Gennode(Knode *p) :ptr(p), numnode(-1) {}
 38 };
 39 
 40 class info
 41 {
 42 public:
 43     vector<int> left;
 44     vector<int> right;
 45     Knode *share = nullptr;
 46     vector<int>::size_type position = 0;
 47 };
 48 
 49 int Search(Knode *ptr, int d, const int k);
 50 int Enable(Knode *ptr, int m);
 51 int creatsharelist(string &glist, map<string, info> &sharelist);
 52 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 53 Knode *strtoktree(string &glist, int &k);
 54 
 55 int main()
 56 {
 57     string glist;
 58     cout << "请输入K叉树的广义表形式" << endl;
 59     cin >> glist;
 60     int k;
 61     Knode *ptr=strtoktree(glist, k), *root=ptr;//初始化为根节点指针
 62     int d = 0;
 63     vector<Path> stack;
 64 
 65     while (true)
 66     {
 67         if (Search(ptr, d, k) == 0)
 68         {
 69             if (ptr == root)
 70             {
 71                 delete ptr;
 72                 stack.pop_back();
 73                 break;
 74             }
 75             else
 76             {
 77                 if (d == 0)
 78                 {
 79                     stack[stack.size() - 1].ptr->p[stack[stack.size() - 1].num - 1] = nullptr;
 80                     if (ptr->data != '\0' || --ptr->ref == 0)
 81                     {
 82                         delete ptr;
 83                     }
 84                 }
 85                 else
 86                 {
 87                     stack.pop_back();
 88                     stack[stack.size() - 1].ptr->p[stack[stack.size() - 1].num - 1] = nullptr;
 89                     delete ptr;
 90                 }
 91                 ptr = stack[stack.size() - 1].ptr;
 92                 d = stack[stack.size() - 1].num;
 93             }
 94         }
 95         else
 96         {
 97             Knode *interval;
 98             if (d == 0)
 99             {
100                 if (ptr->ref != 0)
101                 {
102                     if (--ptr->ref > 0)
103                     {
104                         stack[stack.size() - 1].ptr->p[stack[stack.size() - 1].num - 1] = nullptr;
105                         ptr = stack[stack.size() - 1].ptr;
106                         d = stack[stack.size() - 1].num;
107                         continue;
108                     }
109                 }
110                 Path temp(ptr, Search(ptr, d, k));
111                 interval = ptr->p[Search(ptr, d, k) - 1];
112                 stack.push_back(temp);
113             }
114             else
115             {
116                 stack[stack.size() - 1].num = Search(ptr, d, k);
117                 interval = ptr->p[Search(ptr, d, k) - 1];
118             }
119             ptr = interval;
120             d = 0;
121         }
122     }
123     cout << "K叉树删除成功!" << endl;
124     return 0;
125 }
126 
127 int Search(Knode *ptr, int d, const int k)
128 {
129     int m = d;
130     for (m++; m <= k; m++)
131     {
132         if (Enable(ptr, m) == 1)
133             return m;
134     }
135     return 0;
136 }
137 
138 int Enable(Knode *ptr, int m)
139 {
140     if (ptr->p[m - 1] != nullptr)
141         return 1;
142     else
143         return 0;
144 }
145 
146 int creatsharelist(string &glist, map<string, info> &sharelist)
147 {
148     class node
149     {
150     public:
151         int left;
152         int numnode = 0;
153         node(int l) :left(l) {}
154     };
155 
156     vector<node> stack;
157     int total = 0, maxlen = 0;
158     for (const auto &s : glist)
159     {
160         if (s == '(')
161         {
162             if (stack.size() != 0)
163                 ++stack[stack.size() - 1].numnode;
164             ++total;
165             stack.push_back(*(new node(total)));
166         }
167         else if (s == ')')
168         {
169             ++total;
170             string temp = glist.substr(stack[stack.size() - 1].left - 1, total - stack[stack.size() - 1].left + 1);
171             auto p = sharelist.find(temp);
172             if (p == sharelist.end())
173             {
174                 if (stack[stack.size() - 1].numnode>maxlen)
175                     maxlen = stack[stack.size() - 1].numnode;
176 
177                 auto q = sharelist.insert(make_pair(temp, *(new info)));
178                 q.first->second.left.push_back(stack[stack.size() - 1].left);
179                 q.first->second.right.push_back(total);
180             }
181             else
182             {
183                 p->second.left.push_back(stack[stack.size() - 1].left);
184                 p->second.right.push_back(total);
185             }
186             stack.pop_back();
187         }
188         else
189         {
190             if (s != ',')
191                 ++stack[stack.size() - 1].numnode;
192             ++total;
193         }
194     }
195 
196     auto m = sharelist.begin();
197     while (m != sharelist.end())
198     {
199         if (m->second.left.size() == 1)
200             m = sharelist.erase(m);
201         else
202             ++m;
203     }
204 
205     return maxlen;
206 }
207 
208 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
209 {
210     auto p = sharelist.begin();
211     for (; p != sharelist.end(); ++p)
212     {
213         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
214         {
215             ++p->second.position;
216             return p;
217         }
218     }
219     return p;
220 }
221 
222 Knode *strtoktree(string &glist, int &k)
223 {
224     map<string, info> sharelist;
225 
226     Knode *ptr = nullptr; vector<Gennode> stack; k = creatsharelist(glist, sharelist);
227     for (string::size_type i = 0; i != glist.size(); ++i)
228     {
229         if (glist[i] == '(')
230         {
231             if (i == 0)
232             {
233                 ptr = new Knode(k, 0);
234                 Gennode temp(ptr);
235                 stack.push_back(temp);
236             }
237             else
238             {
239                 auto p = Searchshare(i + 1, sharelist);
240                 if (p != sharelist.end())
241                 {
242                     if (p->second.share != nullptr)
243                     {
244                         ptr->p[++stack[stack.size() - 1].numnode] = p->second.share;
245                         ++p->second.share->ref;
246                         i = p->second.right[p->second.position - 1] - 1;
247                         continue;
248                     }
249                 }
250                 Knode *temp = new Knode(k, 1);
251                 ptr->p[++stack[stack.size() - 1].numnode] = temp;
252                 ptr = temp;
253                 Gennode temp2(ptr);
254                 stack.push_back(temp2);
255                 if (p != sharelist.end())
256                     p->second.share = ptr;
257             }
258         }
259         else
260         {
261             if (glist[i] == ')')
262             {
263                 stack.pop_back();
264                 if (stack.size() != 0)
265                     ptr = stack[stack.size() - 1].ptr;
266             }
267             else
268             {
269                 if (glist[i] != ',')
270                 {
271                     Knode *temp = new Knode(k, 1, glist[i]);
272                     ptr->p[++stack[stack.size() - 1].numnode] = temp;
273                 }
274             }
275         }
276     }
277     cout << "已将字符串形式的广义表转换为K叉树" << endl;
278     return ptr;
279 }

带共享子树的多叉树复制：

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

求链表表示的共享表深度：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <string>
  5 #include <map>
  6 using namespace std;
  7 
  8 struct Gen
  9 {
 10     int utype;
 11     union
 12     {
 13         int ref;
 14         struct Gen *hlink;
 15         char value;
 16     }info;
 17     struct Gen *tlink;
 18     Gen(int u);
 19     Gen(int u, char v);
 20     Gen(int u, int r);
 21 };
 22 Gen::Gen(int u) :utype(u), tlink(nullptr)
 23 {
 24     info.hlink = nullptr;
 25 }
 26 
 27 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 28 {
 29     info.ref = r;
 30 }
 31 
 32 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 33 {
 34     info.value = v;
 35 }
 36 
 37 class info
 38 {
 39 public:
 40     vector<int> left;
 41     vector<int> right;
 42     Gen *share = nullptr;
 43     vector<int>::size_type position = 0;
 44 };
 45 
 46 void suboutput(Gen *head);
 47 Gen * strtogen();
 48 void creatsharelist(string &glist, map<string, info> &sharelist);
 49 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 50 
 51 int main()
 52 {
 53     int depth = 0; int maxdepth = 0;
 54     int sign = 0;
 55     bool TF = true;
 56     vector<Gen *> stack;
 57     map<Gen *, int> sharemaxdep;
 58     Gen *ptr=strtogen();//ptr应初始化为指向广义表附加头节点的指针
 59 
 60     while (true)
 61     {
 62         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 63         {
 64             if (TF == true)
 65             {        
 66                 if (ptr->utype == 0)
 67                 {
 68                     if (ptr->info.ref == 0)
 69                     {
 70                         sign = 0;
 71                         stack.push_back(ptr);
 72                         ++depth;
 73                     }
 74                     ptr = ptr->tlink;
 75                 }
 76                 else
 77                 {
 78                     sign = 0;
 79                     if (ptr->info.hlink->info.ref > 1)
 80                     {
 81                         auto p = sharemaxdep.find(ptr->info.hlink);
 82                         if (p != sharemaxdep.end())
 83                         {
 84                             if (depth + 1 > p->second)
 85                                 p->second = depth + 1;
 86                             else
 87                             {
 88                                 sign = 1;
 89                                 ptr = ptr->tlink;
 90                                 continue;
 91                             }
 92                         }
 93                         else
 94                         {
 95                             sharemaxdep.insert(make_pair(ptr->info.hlink, depth+1));
 96                         }
 97                     }
 98                     stack.push_back(ptr);
 99                     ++depth;
100                     ptr = ptr->info.hlink;
101                 }
102             }
103             else
104             {
105                 if (ptr->utype == 0)
106                     break;
107                 else
108                 {
109                     sign = 1;
110                     ptr = ptr->tlink;
111                     TF = true;
112                 }
113             }
114         }
115         else
116         {
117             if (ptr == nullptr)
118             {
119                 if (sign == 0)
120                 {
121                     if (depth > maxdepth)
122                         maxdepth = depth;
123                 }
124                 depth--;
125                 ptr = stack[stack.size() - 1];
126                 stack.pop_back();
127                 TF = false;
128             }
129             else
130             {
131                 ptr = ptr->tlink;
132             }
133         }
134     }
135     cout << "广义表深度:"<< maxdepth<<endl;
136     return 0;
137 }
138 
139 void suboutput(Gen *head)
140 {
141     Gen *ptr = head;
142     bool TF = true;
143     vector<Gen *> stack;
144     while (true)
145     {
146         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
147         {
148             if (TF == true)
149             {
150                 if (ptr->utype == 0)   //注意
151                 {
152                     if (ptr->info.ref == 0)
153                     {
154                         stack.push_back(ptr);
155                         cout << "(";
156                     }
157                     ptr = ptr->tlink;
158                 }
159                 else
160                 {
161                     stack.push_back(ptr);
162                     cout << "(";
163                     ptr = ptr->info.hlink;
164                 }
165             }
166             else
167             {
168                 if (ptr == head)
169                     break;
170                 else
171                 {
172                     ptr = ptr->tlink;
173                     TF = true;
174                 }
175             }
176         }
177         else
178         {
179             if (ptr == nullptr)
180             {
181                 cout << ")";
182                 ptr = stack[stack.size() - 1];
183                 if (ptr->tlink != nullptr && ptr != head)    //注意
184                     cout << ",";
185                 stack.pop_back();
186                 TF = false;
187             }
188             else
189             {
190                 cout << ptr->info.value;
191                 ptr = ptr->tlink;
192                 if (ptr != nullptr)
193                     cout << ",";
194             }
195         }
196     }
197     cout << endl;
198 }
199 
200 Gen * strtogen()
201 {
202     string glist;
203     cout << "请输入广义表的字符串形式" << endl;
204     cin >> glist;
205     map<string, info> sharelist;
206 
207     creatsharelist(glist, sharelist);
208 
209     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
210     int ref = 0;
211     for (string::size_type i = 0; i != glist.size(); ++i)
212     {
213         if (glist[i] == '(')
214         {
215             if (i == 0)
216             {
217                 ptr = new Gen(0, 0);
218                 stack.push_back(ptr);
219                 TF = true;
220             }
221             else
222             {
223                 Gen *temp = new Gen(1);
224                 if (ptr->utype == 1)
225                 {
226                     if (TF == true)
227                         ptr->info.hlink->tlink = temp;
228                     else
229                         ptr->tlink = temp;
230                 }
231                 else
232                 {
233                     ptr->tlink = temp;
234                 }
235 
236                 auto p = Searchshare(i + 1, sharelist);
237                 if (p != sharelist.end() && p->second.share != nullptr)
238                 {
239                     temp->info.hlink = p->second.share;
240                     ++p->second.share->info.ref;
241                     TF = false;
242                     ptr = temp;
243                     i = p->second.right[p->second.position - 1] - 1;
244                     continue;
245                 }
246                 else
247                 {
248                     stack.push_back(temp);
249                     TF = true;
250                     ptr = temp;
251                     temp = new Gen(0, 1);
252                     ptr->info.hlink = temp;
253                     if (p != sharelist.end())
254                         p->second.share = ptr->info.hlink;
255                 }
256             }
257         }
258         else
259         {
260             if (glist[i] == ')')
261             {
262                 ptr = stack[stack.size() - 1];
263                 stack.pop_back();
264                 TF = false;
265             }
266             else
267             {
268                 if (glist[i] != ',')
269                 {
270                     Gen *temp = new Gen(2, glist[i]);
271                     if (ptr->utype == 1)
272                     {
273                         if (TF == true)
274                             ptr->info.hlink->tlink = temp;
275                         else
276                             ptr->tlink = temp;
277                     }
278                     else
279                     {
280                         ptr->tlink = temp;
281                     }
282 
283                     ptr = temp;
284                 }
285             }
286         }
287     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
288     cout << "已将字符串形式转换为链表表示" << endl;
289     return ptr;
290 }
291 
292 void creatsharelist(string &glist, map<string, info> &sharelist)
293 {
294     vector<int> stack;
295     int total = 0;
296     for (const auto &s : glist)
297     {
298         if (s == '(')
299         {
300             ++total;
301             stack.push_back(total);
302         }
303         else if (s == ')')
304         {
305             ++total;
306             string temp = glist.substr(stack[stack.size() - 1] - 1, total - stack[stack.size() - 1] + 1);
307             auto p = sharelist.find(temp);
308             if (p == sharelist.end())
309             {
310                 auto q = sharelist.insert(make_pair(temp, *(new info)));
311                 q.first->second.left.push_back(stack[stack.size() - 1]);
312                 q.first->second.right.push_back(total);
313             }
314             else
315             {
316                 p->second.left.push_back(stack[stack.size() - 1]);
317                 p->second.right.push_back(total);
318             }
319             stack.pop_back();
320         }
321         else
322         {
323             ++total;
324         }
325     }
326 
327     auto m = sharelist.begin();
328     while (m != sharelist.end())
329     {
330         if (m->second.left.size() == 1)
331             m = sharelist.erase(m);
332         else
333             ++m;
334     }
335 }
336 
337 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
338 {
339     auto p = sharelist.begin();
340     for (; p != sharelist.end(); ++p)
341     {
342         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
343         {
344             ++p->second.position;
345             return p;
346         }
347     }
348     return p;
349 }

从共享表中搜索并删除指定值：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <string>
  5 #include <map>
  6 #include <algorithm>
  7 using namespace std;
  8 
  9 struct Gen
 10 {
 11     int utype;
 12     union
 13     {
 14         int ref;
 15         struct Gen *hlink;
 16         char value;
 17     }info;
 18     struct Gen *tlink;
 19     Gen(int u);
 20     Gen(int u, char v);
 21     Gen(int u, int r);
 22 };
 23 Gen::Gen(int u) :utype(u), tlink(nullptr)
 24 {
 25     info.hlink = nullptr;
 26 }
 27 
 28 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
 29 {
 30     info.ref = r;
 31 }
 32 
 33 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
 34 {
 35     info.value = v;
 36 }
 37 
 38 class info
 39 {
 40 public:
 41     vector<int> left;
 42     vector<int> right;
 43     Gen *share = nullptr;
 44     vector<int>::size_type position = 0;
 45 };
 46 
 47 Gen *strtogen();
 48 void suboutput(Gen *head);
 49 void creatsharelist(string &glist, map<string, info> &sharelist);
 50 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist);
 51 
 52 int main()
 53 {  
 54     bool TF = true;
 55     char key;
 56     vector<Gen *> stack;
 57     vector<Gen *> share;
 58     Gen *ptr= strtogen();//ptr应初始化为指向广义表附加头节点的指针
 59     Gen *before = ptr;
 60     cout << "请输入要删除的值:" << endl;
 61     cin >> key;
 62 
 63     while (true)
 64     {
 65         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
 66         {
 67             if (TF == true)
 68             {
 69                 if (ptr->utype == 0)
 70                 {
 71                     if (ptr->info.ref == 0)
 72                     {
 73                         stack.push_back(ptr);
 74                     }
 75                     else
 76                     {
 77                         before = before->info.hlink;
 78                     }
 79                     ptr = ptr->tlink;
 80                 }
 81                 else
 82                 {
 83                     if (ptr->info.hlink->info.ref > 1)
 84                     {
 85                         auto p = find(share.begin(), share.end(), ptr->info.hlink);
 86                         if (p != share.end())
 87                         {
 88                                 ptr = ptr->tlink;
 89                                 before = before->tlink;
 90                                 continue;
 91                         }
 92                         else
 93                         {
 94                                 share.push_back(ptr->info.hlink);
 95                         }
 96                     }
 97                     stack.push_back(ptr);
 98                     before = before->tlink;
 99                     ptr = ptr->info.hlink;
100                 }
101             }
102             else
103             {
104                 if (ptr->utype == 0)
105                     break;
106                 else
107                 {
108                     before = ptr;
109                     ptr = ptr->tlink;
110                     TF = true;
111                 }
112             }
113         }
114         else
115         {
116             if (ptr == nullptr)
117             {
118                 before = before->tlink;
119                 ptr = stack[stack.size() - 1];
120                 stack.pop_back();
121                 TF = false;
122             }
123             else
124             {
125                 if (ptr->info.value == key)
126                 {
127                     before->tlink = ptr->tlink;
128                     delete ptr;
129                     ptr = before->tlink;
130                 }
131                 else
132                 {
133                     before = before->tlink;
134                     ptr = ptr->tlink;
135                 }
136             }
137         }
138     }
139     cout << "删除后的广义表为:";
140     suboutput(ptr);
141     return 0;
142 }
143 
144 void suboutput(Gen *head)
145 {
146     Gen *ptr = head;
147     bool TF = true;
148     vector<Gen *> stack;
149     while (true)
150     {
151         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意
152         {
153             if (TF == true)
154             {
155                 if (ptr->utype == 0)   //注意
156                 {
157                     if (ptr->info.ref == 0)
158                     {
159                         stack.push_back(ptr);
160                         cout << "(";
161                     }
162                     ptr = ptr->tlink;
163                 }
164                 else
165                 {
166                     stack.push_back(ptr);
167                     cout << "(";
168                     ptr = ptr->info.hlink;
169                 }
170             }
171             else
172             {
173                 if (ptr == head)
174                     break;
175                 else
176                 {
177                     ptr = ptr->tlink;
178                     TF = true;
179                 }
180             }
181         }
182         else
183         {
184             if (ptr == nullptr)
185             {
186                 cout << ")";
187                 ptr = stack[stack.size() - 1];
188                 if (ptr->tlink != nullptr && ptr != head)    //注意
189                     cout << ",";
190                 stack.pop_back();
191                 TF = false;
192             }
193             else
194             {
195                 cout << ptr->info.value;
196                 ptr = ptr->tlink;
197                 if (ptr != nullptr)
198                     cout << ",";
199             }
200         }
201     }
202     cout << endl;
203 }
204 
205 Gen * strtogen()
206 {
207     string glist;
208     cout << "请输入广义表的字符串形式" << endl;
209     cin >> glist;
210     map<string, info> sharelist;
211 
212     creatsharelist(glist, sharelist);
213 
214     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
215     int ref = 0;
216     for (string::size_type i = 0; i != glist.size(); ++i)
217     {
218         if (glist[i] == '(')
219         {
220             if (i == 0)
221             {
222                 ptr = new Gen(0, 0);
223                 stack.push_back(ptr);
224                 TF = true;
225             }
226             else
227             {
228                 Gen *temp = new Gen(1);
229                 if (ptr->utype == 1)
230                 {
231                     if (TF == true)
232                         ptr->info.hlink->tlink = temp;
233                     else
234                         ptr->tlink = temp;
235                 }
236                 else
237                 {
238                     ptr->tlink = temp;
239                 }
240 
241                 auto p = Searchshare(i + 1, sharelist);
242                 if (p != sharelist.end() && p->second.share != nullptr)
243                 {
244                     temp->info.hlink = p->second.share;
245                     ++p->second.share->info.ref;
246                     TF = false;
247                     ptr = temp;
248                     i = p->second.right[p->second.position - 1] - 1;
249                     continue;
250                 }
251                 else
252                 {
253                     stack.push_back(temp);
254                     TF = true;
255                     ptr = temp;
256                     temp = new Gen(0, 1);
257                     ptr->info.hlink = temp;
258                     if (p != sharelist.end())
259                         p->second.share = ptr->info.hlink;
260                 }
261             }
262         }
263         else
264         {
265             if (glist[i] == ')')
266             {
267                 ptr = stack[stack.size() - 1];
268                 stack.pop_back();
269                 TF = false;
270             }
271             else
272             {
273                 if (glist[i] != ',')
274                 {
275                     Gen *temp = new Gen(2, glist[i]);
276                     if (ptr->utype == 1)
277                     {
278                         if (TF == true)
279                             ptr->info.hlink->tlink = temp;
280                         else
281                             ptr->tlink = temp;
282                     }
283                     else
284                     {
285                         ptr->tlink = temp;
286                     }
287 
288                     ptr = temp;
289                 }
290             }
291         }
292     }    //扫描完毕此时ptr指向广义表链表表示的附加头结点,栈空
293     cout << "已将字符串形式转换为链表表示" << endl;
294     return ptr;
295 }
296 
297 void creatsharelist(string &glist, map<string, info> &sharelist)
298 {
299     vector<int> stack;
300     int total = 0;
301     for (const auto &s : glist)
302     {
303         if (s == '(')
304         {
305             ++total;
306             stack.push_back(total);
307         }
308         else if (s == ')')
309         {
310             ++total;
311             string temp = glist.substr(stack[stack.size() - 1] - 1, total - stack[stack.size() - 1] + 1);
312             auto p = sharelist.find(temp);
313             if (p == sharelist.end())
314             {
315                 auto q = sharelist.insert(make_pair(temp, *(new info)));
316                 q.first->second.left.push_back(stack[stack.size() - 1]);
317                 q.first->second.right.push_back(total);
318             }
319             else
320             {
321                 p->second.left.push_back(stack[stack.size() - 1]);
322                 p->second.right.push_back(total);
323             }
324             stack.pop_back();
325         }
326         else
327         {
328             ++total;
329         }
330     }
331 
332     auto m = sharelist.begin();
333     while (m != sharelist.end())
334     {
335         if (m->second.left.size() == 1)
336             m = sharelist.erase(m);
337         else
338             ++m;
339     }
340 }
341 
342 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)
343 {
344     auto p = sharelist.begin();
345     for (; p != sharelist.end(); ++p)
346     {
347         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)
348         {
349             ++p->second.position;
350             return p;
351         }
352     }
353     return p;
354 }