品欧影视,母鸡养殖场,开机速度优化
之前文章里给出的基于广义表链表表示的运算中用链表表示的广义表除广义表本身外的其他所有子表都是没有附加头节点的，即utype==1的节点(在同一层子表中表示为该子表的子表的表元素)的hlink指针直接指向下一层子表的表头，而不是附加头节点，这是一个疏忽。所以我把所有适用于广义表没有附加头节点的链表表示的相关运算的c++实现进行了修改，修改后的源码可以适用于有附加头节点的情形，完成的功能保持不变。
找出所有子表及相关属性
我要评论 1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 class Gennode
37 {
38 public:
39 int numnode;
40 Gen *ptr;
41 Gennode(Gen *p) :ptr(p), numnode(0) {}
42 };
43
44 void output(vector<Gennode> &stack);
45 void suboutput(Gen *head);
46 Gen * strtogen();
47
48 int main()
49 {
50 int depth = 0; int maxdepth = 0;
51 int flag = 0; int sign = 0;
52 int subcount = 0;
53 int emptycount = 0;
54 bool TF = true;
55 vector<Gennode> stack;
56 Gen *ptr=strtogen();//ptr应初始化为指向广义表附加头节点的指针
57
58 while (true)
59 {
60 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
61 {
62 if (TF == true)
63 {
64 sign = 0;
65
66 if (ptr->utype == 0)
67 {
68 if (ptr->info.ref == 0)
69 {
70 Gennode temp(ptr);
71 stack.push_back(temp);
72 flag = 0;
73 ++depth;
74 }
75 ptr = ptr->tlink;
76 }
77 else
78 {
79 ++stack[stack.size() - 1].numnode;
80 Gennode temp(ptr);
81 stack.push_back(temp);
82 flag = 2;
83 ++depth;
84 ptr = ptr->info.hlink;
85 }
86 }
87 else
88 {
89 if (ptr->utype == 0)
90 break;
91 else
92 {
93 sign = 1;
94 ptr = ptr->tlink;
95 flag = 1;
96 TF = true;
97 }
98 }
99 }
100 else
101 {
102 if (ptr == nullptr)
103 {
104 subcount++;
105 if (flag == 2) //找到一个子空表
106 {
107 //栈中存有完整位置信息,输出之
108 emptycount++;
109 cout << "第" << subcount << "个子表,为空表:()"<<endl;
110 cout << "深度:" << depth << " 长度:" << 0 << endl;
111 cout << "位置:" << endl;
112 output(stack);
113 }
114 else
115 {
116 if (flag == 1)
117 {
118 //找到一个非空子表
119 cout << "第" << subcount << "个非空子表:";
120 suboutput(stack[stack.size() - 1].ptr);
121 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
122 cout << "深度:" << depth << " 长度:" << stack[stack.size() - 1].numnode << endl;
123 cout << "位置:" << endl;
124 if (stack[stack.size() - 1].ptr->utype == 0)
125 {
126 //当前非空子表为广义表本身,
127 cout << "该非空子表为广义表本身"<<endl;
128 }
129 else
130 {
131 //当前非空子表为真子表，栈中存有完整位置信息,输出之
132 output(stack);
133 }
134 }
135 else
136 {
137 emptycount++;
138 //找到子空表,即为广义表本身,输出之
139 cout << "第" << subcount << "个子表,为空表:()" << endl;
140 cout << "深度:" << depth << " 长度:" << 0 << endl;
141 cout << "位置:" << endl;
142 cout << "该子空表为广义表本身" << endl;
143 }
144 }
145 if (sign == 0)
146 {
147 if (depth > maxdepth)
148 maxdepth = depth;
149 }
150 depth--;
151 ptr = stack[stack.size() - 1].ptr;
152 stack.pop_back();
153 TF = false;
154 }
155 else
156 {
157 ++stack[stack.size() - 1].numnode;
158 ptr = ptr->tlink;
159 flag = 1;
160 }
161 }
162 }
163 cout << "共有" << subcount << "个子表,其中有" << emptycount << "个空表" << endl;
164 cout << "广义表深度:"<< maxdepth<<endl;
165 return 0;
166 }
167
168 void output(vector<Gennode> &stack)
169 {
170 for (auto i = stack.begin(); i != stack.end() - 1; ++i)
171 {
172 if (i == stack.begin())
173 {
174 cout << "广义表的第" << (*i).numnode << "个表元素";
175 }
176 else
177 {
178 cout << "的第" << (*i).numnode << "个表元素";
179 }
180 }
181 cout << endl;
182 }
183
184 void suboutput(Gen *head)
185 {
186 Gen *ptr = head;
187 bool TF = true;
188 vector<Gen *> stack;
189 while (true)
190 {
191 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意
192 {
193 if (TF == true)
194 {
195 if (ptr->utype == 0) //注意
196 {
197 if (ptr->info.ref == 0)
198 {
199 stack.push_back(ptr);
200 cout << "(";
201 }
202 ptr = ptr->tlink;
203 }
204 else
205 {
206 stack.push_back(ptr);
207 cout << "(";
208 ptr = ptr->info.hlink;
209 }
210 }
211 else
212 {
213 if (ptr == head)
214 break;
215 else
216 {
217 ptr = ptr->tlink;
218 TF = true;
219 }
220 }
221 }
222 else
223 {
224 if (ptr == nullptr)
225 {
226 cout << ")";
227 ptr = stack[stack.size() - 1];
228 if (ptr->tlink != nullptr && ptr != head) //注意
229 cout << ",";
230 stack.pop_back();
231 TF = false;
232 }
233 else
234 {
235 cout << ptr->info.value;
236 ptr = ptr->tlink;
237 if (ptr != nullptr)
238 cout << ",";
239 }
240 }
241 }
242 cout << endl;
243 }
244
245 Gen * strtogen()
246 {
247 string glist;
248 cout << "请输入广义表的字符串形式" << endl;
249 cin >> glist;
250
251 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
252 int ref = 0;
253 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
254 {
255 if (*i == '(')
256 {
257 if (i == glist.cbegin())
258 {
259 ptr = new Gen(0, 0);
260 stack.push_back(ptr);
261 TF = true;
262 }
263 else
264 {
265 Gen *temp = new Gen(1);
266 if (ptr->utype == 1)
267 {
268 if (TF == true)
269 ptr->info.hlink->tlink = temp;
270 else
271 ptr->tlink = temp;
272 }
273 else
274 {
275 ptr->tlink = temp;
276 }
277
278 stack.push_back(temp);
279 TF = true;
280 ptr = temp;
281 temp = new Gen(0, ++ref);
282 ptr->info.hlink = temp;
283 }
284 }
285 else
286 {
287 if (*i == ')')
288 {
289 ptr = stack[stack.size() - 1];
290 stack.pop_back();
291 TF = false;
292 }
293 else
294 {
295 if (*i != ',')
296 {
297 Gen *temp = new Gen(2, *i);
298 if (ptr->utype == 1)
299 {
300 if (TF == true)
301 ptr->info.hlink->tlink = temp;
302 else
303 ptr->tlink = temp;
304 }
305 else
306 {
307 ptr->tlink = temp;
308 }
309
310 ptr = temp;
311 }
312 }
313 }
314 }
315 return ptr;
316 }
在广义表中搜索给定值
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 class Gennode
37 {
38 public:
39 int numnode;
40 Gen *ptr;
41 vector<int> position;
42 Gennode(Gen *p) :ptr(p), numnode(0) {}
43 };
44
45 void output(vector<Gennode> &stack);
46 void suboutput(Gen *head);
47 Gen * strtogen();
48
49 int main()
50 {
51 int depth = 0;
52 int flag = 0;
53 int subcount = 0;
54 bool TF = true;
55 char key;
56 vector<Gennode> stack;
57 Gen *ptr= strtogen();//ptr应初始化为指向广义表附加头节点的指针
58 cout << "请输入要搜索的值:" << endl;
59 cin >> key;
60
61 while (true)
62 {
63 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
64 {
65 if (TF == true)
66 {
67
68 if (ptr->utype == 0)
69 {
70 if (ptr->info.ref == 0)
71 {
72 Gennode temp(ptr);
73 stack.push_back(temp);
74 flag = 0;
75 depth++;
76 }
77 ptr = ptr->tlink;
78 }
79 else
80 {
81 ++stack[stack.size() - 1].numnode;
82 Gennode temp(ptr);
83 stack.push_back(temp);
84 flag = 2;
85 depth++;
86 ptr = ptr->info.hlink;
87 }
88 }
89 else
90 {
91 if (ptr->utype == 0)
92 break;
93 else
94 {
95 ptr = ptr->tlink;
96 flag = 1;
97 TF = true;
98 }
99 }
100 }
101 else
102 {
103 if (ptr == nullptr)
104 {
105 if (flag != 2 && flag!=0)
106 {
107 if (stack[stack.size() - 1].position.size()!=0)
108 {
109 subcount++;
110 cout << "第" << subcount << "个含" << key << "的非空子表:";
111 suboutput(stack[stack.size() - 1].ptr);
112 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
113 cout << key << "是其中第";
114 for (auto i = stack[stack.size() - 1].position.begin(); i < stack[stack.size() - 1].position.end(); ++i)
115 {
116 if (i == stack[stack.size() - 1].position.begin())
117 cout << *i;
118 else
119 cout << "," << *i;
120 }
121 cout << "个表元素" << endl;
122 cout << "该表深度:" << depth << " 长度:" << stack[stack.size() - 1].numnode << endl;
123 cout << "位置:" << endl;
124 if (stack[stack.size() - 1].ptr->utype == 0)
125 {
126 //当前非空子表为广义表本身
127 cout << "该非空子表为广义表本身" << endl;
128 }
129 else
130 {
131 //当前非空子表为真子表，栈中存有完整位置信息,输出之
132 output(stack);
133 }
134 cout << endl;
135 }
136 }
137 depth--;
138 ptr = stack[stack.size() - 1].ptr;
139 stack.pop_back();
140 TF = false;
141 }
142 else
143 {
144 ++stack[stack.size() - 1].numnode;
145 if (ptr->info.value == key)
146 {
147 stack[stack.size() - 1].position.push_back(stack[stack.size() - 1].numnode);
148 }
149 ptr = ptr->tlink;
150 flag = 1;
151 }
152 }
153 }
154 cout << "共有" << subcount << "个子表含有" << key << endl;
155 return 0;
156 }
157
158 void output(vector<Gennode> &stack)
159 {
160 for (auto i = stack.begin(); i != stack.end() - 1; ++i)
161 {
162 if (i == stack.begin())
163 {
164 cout << "广义表的第" << (*i).numnode << "个表元素";
165 }
166 else
167 {
168 cout << "的第" << (*i).numnode << "个表元素";
169 }
170 }
171 cout << endl;
172 }
173
174 void suboutput(Gen *head)
175 {
176 Gen *ptr = head;
177 bool TF = true;
178 vector<Gen *> stack;
179 while (true)
180 {
181 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意
182 {
183 if (TF == true)
184 {
185 if (ptr->utype == 0) //注意
186 {
187 if (ptr->info.ref == 0)
188 {
189 stack.push_back(ptr);
190 cout << "(";
191 }
192 ptr = ptr->tlink;
193 }
194 else
195 {
196 stack.push_back(ptr);
197 cout << "(";
198 ptr = ptr->info.hlink;
199 }
200 }
201 else
202 {
203 if (ptr == head)
204 break;
205 else
206 {
207 ptr = ptr->tlink;
208 TF = true;
209 }
210 }
211 }
212 else
213 {
214 if (ptr == nullptr)
215 {
216 cout << ")";
217 ptr = stack[stack.size() - 1];
218 if (ptr->tlink != nullptr && ptr != head) //注意
219 cout << ",";
220 stack.pop_back();
221 TF = false;
222 }
223 else
224 {
225 cout << ptr->info.value;
226 ptr = ptr->tlink;
227 if (ptr != nullptr)
228 cout << ",";
229 }
230 }
231 }
232 cout << endl;
233 }
234
235 Gen * strtogen()
236 {
237 string glist;
238 cout << "请输入广义表的字符串形式" << endl;
239 cin >> glist;
240
241 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
242 int ref = 0;
243 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
244 {
245 if (*i == '(')
246 {
247 if (i == glist.cbegin())
248 {
249 ptr = new Gen(0, 0);
250 stack.push_back(ptr);
251 TF = true;
252 }
253 else
254 {
255 Gen *temp = new Gen(1);
256 if (ptr->utype == 1)
257 {
258 if (TF == true)
259 ptr->info.hlink->tlink = temp;
260 else
261 ptr->tlink = temp;
262 }
263 else
264 {
265 ptr->tlink = temp;
266 }
267
268 stack.push_back(temp);
269 TF = true;
270 ptr = temp;
271 temp = new Gen(0, ++ref);
272 ptr->info.hlink = temp;
273 }
274 }
275 else
276 {
277 if (*i == ')')
278 {
279 ptr = stack[stack.size() - 1];
280 stack.pop_back();
281 TF = false;
282 }
283 else
284 {
285 if (*i != ',')
286 {
287 Gen *temp = new Gen(2, *i);
288 if (ptr->utype == 1)
289 {
290 if (TF == true)
291 ptr->info.hlink->tlink = temp;
292 else
293 ptr->tlink = temp;
294 }
295 else
296 {
297 ptr->tlink = temp;
298 }
299
300 ptr = temp;
301 }
302 }
303 }
304 }
305 return ptr;
306 }
删除广义表链表表示
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include<string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 Gen * strtogen();
37
38 int main()
39 {
40 Gen *ptr = strtogen(); //ptr初始化为广义表附加头结点指针
41 bool TF = true;
42 vector<Gen *> stack;
43
44 while (true)
45 {
46 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
47 {
48 if (TF == true)
49 {
50 if (ptr->utype != 0 || ptr->info.ref == 0)
51 {
52 stack.push_back(ptr);
53 if (ptr->utype == 0)
54 {
55 if (ptr->tlink == nullptr)
56 {
57 stack.pop_back();
58 TF = false;
59 continue;
60 }
61 ptr = ptr->tlink;
62 stack[stack.size() - 1]->tlink = ptr->tlink;
63 }
64 else
65 {
66 if (ptr->info.hlink->tlink == nullptr)
67 {
68 delete ptr->info.hlink;
69 ptr->info.hlink = nullptr;
70 TF = false;
71 }
72 else
73 {
74 ptr = ptr->info.hlink;
75 stack[stack.size() - 1]->info.hlink = ptr->tlink;
76 }
77 }
78 }
79 else
80 {
81 delete ptr;
82 ptr = nullptr;
83 }
84 }
85 else
86 {
87 if (ptr->utype == 0)
88 {
89 delete ptr;
90 break;
91 }
92 else
93 {
94 delete ptr;
95 stack.pop_back();
96 ptr = nullptr;
97 }
98 }
99 }
100 else
101 {
102 if (ptr == nullptr)
103 {
104 if (stack[stack.size() - 1]->utype == 0)
105 {
106 if (stack[stack.size() - 1]->tlink == nullptr)
107 {
108 TF = false;
109 ptr = stack[stack.size() - 1];
110 stack.pop_back();
111 }
112 else
113 {
114 ptr = stack[stack.size() - 1]->tlink;
115 stack[stack.size() - 1]->tlink = ptr->tlink;
116 TF = true;
117 }
118 }
119 else
120 {
121 if (stack[stack.size() - 1]->info.hlink == nullptr)
122 {
123 TF = false;
124 ptr = stack[stack.size()-1];
125 }
126 else
127 {
128 ptr = stack[stack.size() - 1]->info.hlink;
129 stack[stack.size() - 1]->info.hlink = ptr->tlink;
130 TF = true;
131 }
132 }
133 }
134 else
135 {
136 if (stack[stack.size() - 1]->utype == 0)
137 {
138 if (stack[stack.size() - 1]->tlink == nullptr)
139 {
140 delete ptr;
141 ptr = stack[stack.size() - 1];
142 stack.pop_back();
143 TF = false;
144 }
145 else
146 {
147 delete ptr;
148 ptr = stack[stack.size() - 1]->tlink;
149 stack[stack.size() - 1]->tlink = ptr->tlink;
150 }
151 }
152 else
153 {
154 if (stack[stack.size() - 1]->info.hlink == nullptr)
155 {
156 delete ptr;
157 ptr = stack[stack.size() - 1];
158 TF = false;
159 }
160 else
161 {
162 delete ptr;
163 ptr = stack[stack.size() - 1]->info.hlink;
164 stack[stack.size() - 1]->info.hlink = ptr->tlink;
165 }
166 }
167 }
168 }
169 }
170 //运行结束后ptr成为野指针,栈空,删除成功
171 cout << "链表形式的广义表删除成功!"<< endl;
172 return 0;
173 }
174
175 Gen * strtogen()
176 {
177 string glist;
178 cout << "请输入广义表的字符串形式" << endl;
179 cin >> glist;
180
181 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
182 int ref = 0;
183 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
184 {
185 if (*i == '(')
186 {
187 if (i == glist.cbegin())
188 {
189 ptr = new Gen(0, 0);
190 stack.push_back(ptr);
191 TF = true;
192 }
193 else
194 {
195 Gen *temp = new Gen(1);
196 if (ptr->utype == 1)
197 {
198 if (TF == true)
199 ptr->info.hlink->tlink = temp;
200 else
201 ptr->tlink = temp;
202 }
203 else
204 {
205 ptr->tlink = temp;
206 }
207
208 stack.push_back(temp);
209 TF = true;
210 ptr = temp;
211 temp = new Gen(0, ++ref);
212 ptr->info.hlink = temp;
213 }
214 }
215 else
216 {
217 if (*i == ')')
218 {
219 ptr = stack[stack.size() - 1];
220 stack.pop_back();
221 TF = false;
222 }
223 else
224 {
225 if (*i != ',')
226 {
227 Gen *temp = new Gen(2, *i);
228 if (ptr->utype == 1)
229 {
230 if (TF == true)
231 ptr->info.hlink->tlink = temp;
232 else
233 ptr->tlink = temp;
234 }
235 else
236 {
237 ptr->tlink = temp;
238 }
239
240 ptr = temp;
241 }
242 }
243 }
244 }
245 return ptr;
246 }
求指定深度的所有子表
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 class Gennode
37 {
38 public:
39 int numnode;
40 Gen *ptr;
41 Gennode(Gen *p) :ptr(p), numnode(0) {}
42 };
43
44 void output(vector<Gennode> &stack);
45 void suboutput(Gen *head);
46 Gen * strtogen();
47
48 int main()
49 {
50 int depth = 0; int maxdepth;
51 int flag = 0;
52 int subcount = 0; int emptycount = 0;
53 bool TF = true;
54 vector<Gennode> stack;
55 Gen *ptr=strtogen();//ptr应初始化为指向广义表附加头节点的指针
56 cout << "请输入指定深度:" << endl;
57 cin >> maxdepth;
58 while (true)
59 {
60 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
61 {
62 if (TF == true)
63 {
64 if (ptr->utype != 0 || ptr->info.ref == 0)
65 {
66 if (depth == maxdepth)
67 {
68 ptr = ptr->tlink;
69 flag = 1;
70 ++stack[stack.size() - 1].numnode;
71 continue;
72 }
73 depth++;
74
75 if (ptr->utype == 0)
76 {
77 Gennode temp(ptr);
78 stack.push_back(temp);
79 flag = 0;
80 ptr = ptr->tlink;
81 }
82 else
83 {
84 ++stack[stack.size() - 1].numnode;
85 Gennode temp(ptr);
86 stack.push_back(temp);
87 flag = 2;
88 ptr = ptr->info.hlink;
89 }
90 }
91 else
92 {
93 ptr = ptr->tlink;
94 }
95 }
96 else
97 {
98 if (ptr->utype == 0)
99 break;
100 else
101 {
102 ptr = ptr->tlink;
103 flag = 1;
104 TF = true;
105 }
106 }
107 }
108 else
109 {
110 if (ptr == nullptr)
111 {
112 if (depth == maxdepth)
113 {
114 subcount++;
115 if (flag == 2) //找到一个子空表
116 {
117 ++emptycount;
118 //栈中存有完整位置信息,输出之
119 cout << "第" << subcount << "个指定深度的子表,为空表:()" << endl;
120 cout << " 长度:" << 0 << endl;
121 cout << "位置:" << endl;
122 output(stack);
123 }
124 else
125 {
126 if (flag == 1)
127 {
128 //找到一个非空子表
129 cout << "第" << subcount << "个指定深度的子表(非空):";
130 suboutput(stack[stack.size() - 1].ptr);
131 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
132 cout << " 长度:" << stack[stack.size() - 1].numnode << endl;
133 cout << "位置:" << endl;
134 if (stack[stack.size() - 1].ptr->utype == 0)
135 {
136 //当前非空子表为广义表本身,
137 cout << "该非空子表为广义表本身" << endl;
138 }
139 else
140 {
141 //当前非空子表为真子表，栈中存有完整位置信息,输出之
142 output(stack);
143 }
144 }
145 else
146 {
147 ++emptycount;
148 //找到子空表,即为广义表本身,输出之
149 cout << "第" << subcount << "个指定深度的子表,为空表:()" << endl;
150 cout << " 长度:" << 0 << endl;
151 cout << "位置:" << endl;
152 cout << "该子空表为广义表本身" << endl;
153 }
154 }
155 }
156
157 depth--;
158 ptr = stack[stack.size() - 1].ptr;
159 stack.pop_back();
160 TF = false;
161 }
162 else
163 {
164 ++stack[stack.size() - 1].numnode;
165 ptr = ptr->tlink;
166 flag = 1;
167 }
168 }
169 }
170 cout << "共有" << subcount << "个指定深度的子表,其中有" << emptycount << "个空表" << endl;
171 return 0;
172 }
173
174 void output(vector<Gennode> &stack)
175 {
176 for (auto i = stack.begin(); i != stack.end() - 1; ++i)
177 {
178 if (i == stack.begin())
179 {
180 cout << "广义表的第" << (*i).numnode << "个表元素";
181 }
182 else
183 {
184 cout << "的第" << (*i).numnode << "个表元素";
185 }
186 }
187 cout << endl;
188 }
189
190 void suboutput(Gen *head)
191 {
192 Gen *ptr = head;
193 bool TF = true;
194 vector<Gen *> stack;
195 while (true)
196 {
197 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意
198 {
199 if (TF == true)
200 {
201 if (ptr->utype == 0) //注意
202 {
203 if (ptr->info.ref == 0)
204 {
205 stack.push_back(ptr);
206 cout << "(";
207 }
208 ptr = ptr->tlink;
209 }
210 else
211 {
212 stack.push_back(ptr);
213 cout << "(";
214 ptr = ptr->info.hlink;
215 }
216 }
217 else
218 {
219 if (ptr == head)
220 break;
221 else
222 {
223 ptr = ptr->tlink;
224 TF = true;
225 }
226 }
227 }
228 else
229 {
230 if (ptr == nullptr)
231 {
232 cout << ")";
233 ptr = stack[stack.size() - 1];
234 if (ptr->tlink != nullptr && ptr != head) //注意
235 cout << ",";
236 stack.pop_back();
237 TF = false;
238 }
239 else
240 {
241 cout << ptr->info.value;
242 ptr = ptr->tlink;
243 if (ptr != nullptr)
244 cout << ",";
245 }
246 }
247 }
248 cout << endl;
249 }
250
251 Gen * strtogen()
252 {
253 string glist;
254 cout << "请输入广义表的字符串形式" << endl;
255 cin >> glist;
256
257 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
258 int ref = 0;
259 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
260 {
261 if (*i == '(')
262 {
263 if (i == glist.cbegin())
264 {
265 ptr = new Gen(0, 0);
266 stack.push_back(ptr);
267 TF = true;
268 }
269 else
270 {
271 Gen *temp = new Gen(1);
272 if (ptr->utype == 1)
273 {
274 if (TF == true)
275 ptr->info.hlink->tlink = temp;
276 else
277 ptr->tlink = temp;
278 }
279 else
280 {
281 ptr->tlink = temp;
282 }
283
284 stack.push_back(temp);
285 TF = true;
286 ptr = temp;
287 temp = new Gen(0, ++ref);
288 ptr->info.hlink = temp;
289 }
290 }
291 else
292 {
293 if (*i == ')')
294 {
295 ptr = stack[stack.size() - 1];
296 stack.pop_back();
297 TF = false;
298 }
299 else
300 {
301 if (*i != ',')
302 {
303 Gen *temp = new Gen(2, *i);
304 if (ptr->utype == 1)
305 {
306 if (TF == true)
307 ptr->info.hlink->tlink = temp;
308 else
309 ptr->tlink = temp;
310 }
311 else
312 {
313 ptr->tlink = temp;
314 }
315
316 ptr = temp;
317 }
318 }
319 }
320 }
321 return ptr;
322 }
计算各子表在广义表字符串中的起始终止位置
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 class Gennode
37 {
38 public:
39 int numnode;
40 Gen *ptr;
41 Gennode(Gen *p) :ptr(p), numnode(0) {}
42 };
43
44 class position
45 {
46 public:
47 int place;
48 int index;
49 position(int p, int i) :place(p), index(i) {}
50 };
51
52 void suboutput(Gen *head);
53 Gen * strtogen();
54
55 int main()
56 {
57 int flag = 0;
58 bool TF = true;
59 vector<Gennode> stack;
60 vector<position> match;
61 int left = 0, right = 0, total = 0;
62 Gen *ptr = strtogen();//ptr应初始化为指向广义表附加头节点的指针
63
64 while (true)
65 {
66 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
67 {
68 if (TF == true)
69 {
70 if (ptr->utype != 0 || ptr->info.ref == 0)
71 {
72 ++left;
73 ++total;
74 position temp(total, left);
75 match.push_back(temp);
76 if (ptr->utype == 0)
77 {
78 Gennode temp(ptr);
79 stack.push_back(temp);
80 flag = 0;
81 ptr = ptr->tlink;
82 }
83 else
84 {
85 ++stack[stack.size() - 1].numnode;
86 Gennode temp(ptr);
87 stack.push_back(temp);
88 flag = 2;
89 ptr = ptr->info.hlink;
90 }
91 }
92 else
93 {
94 ptr = ptr->tlink;
95 }
96 }
97 else
98 {
99 if (ptr->utype == 0)
100 break;
101 else
102 {
103 ptr = ptr->tlink;
104 flag = 1;
105 TF = true;
106 }
107 }
108 }
109 else
110 {
111 if (ptr == nullptr)
112 {
113 ++right;
114 ++total;
115 if (flag == 2) //找到一个子空表
116 {
117 cout << "子表 ():";
118 }
119 else
120 {
121 if (flag == 1)
122 {
123 //找到一个非空子表
124 cout << "子表 ";
125 suboutput(stack[stack.size() - 1].ptr);
126 //输出之,输出函数直接套用扫描链表输出广义表,最后要输出换行符
127 cout << ":";
128 }
129 else
130 {
131 cout << "子表 ():";
132 }
133 }
134 cout << endl;
135 cout << " 长度:" << stack[stack.size() - 1].numnode << endl;
136 cout << "(为从左至右数起第" << match[match.size() - 1].index << "个 ";
137 cout << ")为第" << right << "个 ";
138 cout << "(下标为" << match[match.size() - 1].place << " )下标为" << total << endl;
139 cout << endl;
140 match.pop_back();
141
142 ptr = stack[stack.size() - 1].ptr;
143 if (ptr->utype != 0 && ptr->tlink != nullptr)
144 ++total;
145 stack.pop_back();
146 TF = false;
147 }
148 else
149 {
150 ++stack[stack.size() - 1].numnode;
151 ++total;
152 ptr = ptr->tlink;
153 if (ptr != nullptr)
154 ++total;
155 flag = 1;
156 }
157 }
158 }
159 return 0;
160 }
161
162 void suboutput(Gen *head)
163 {
164 Gen *ptr = head;
165 bool TF = true;
166 vector<Gen *> stack;
167 while (true)
168 {
169 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意
170 {
171 if (TF == true)
172 {
173 if (ptr->utype == 0) //注意
174 {
175 if (ptr->info.ref == 0)
176 {
177 stack.push_back(ptr);
178 cout << "(";
179 }
180 ptr = ptr->tlink;
181 }
182 else
183 {
184 stack.push_back(ptr);
185 cout << "(";
186 ptr = ptr->info.hlink;
187 }
188 }
189 else
190 {
191 if (ptr == head)
192 break;
193 else
194 {
195 ptr = ptr->tlink;
196 TF = true;
197 }
198 }
199 }
200 else
201 {
202 if (ptr == nullptr)
203 {
204 cout << ")";
205 ptr = stack[stack.size() - 1];
206 if (ptr->tlink != nullptr && ptr != head) //注意
207 cout << ",";
208 stack.pop_back();
209 TF = false;
210 }
211 else
212 {
213 cout << ptr->info.value;
214 ptr = ptr->tlink;
215 if (ptr != nullptr)
216 cout << ",";
217 }
218 }
219 }
220 }
221
222 Gen * strtogen()
223 {
224 string glist;
225 cout << "请输入广义表的字符串形式" << endl;
226 cin >> glist;
227
228 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
229 int ref = 0;
230 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
231 {
232 if (*i == '(')
233 {
234 if (i == glist.cbegin())
235 {
236 ptr = new Gen(0, 0);
237 stack.push_back(ptr);
238 TF = true;
239 }
240 else
241 {
242 Gen *temp = new Gen(1);
243 if (ptr->utype == 1)
244 {
245 if (TF == true)
246 ptr->info.hlink->tlink = temp;
247 else
248 ptr->tlink = temp;
249 }
250 else
251 {
252 ptr->tlink = temp;
253 }
254
255 stack.push_back(temp);
256 TF = true;
257 ptr = temp;
258 temp = new Gen(0, ++ref);
259 ptr->info.hlink = temp;
260 }
261 }
262 else
263 {
264 if (*i == ')')
265 {
266 ptr = stack[stack.size() - 1];
267 stack.pop_back();
268 TF = false;
269 }
270 else
271 {
272 if (*i != ',')
273 {
274 Gen *temp = new Gen(2, *i);
275 if (ptr->utype == 1)
276 {
277 if (TF == true)
278 ptr->info.hlink->tlink = temp;
279 else
280 ptr->tlink = temp;
281 }
282 else
283 {
284 ptr->tlink = temp;
285 }
286
287 ptr = temp;
288 }
289 }
290 }
291 }
292 return ptr;
293 }
基于链表表示拷贝广义表
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 Gen * strtogen();
37 void suboutput(Gen *head);
38
39 int main()
40 {
41 vector<Gen *> stack1;//源栈
42 vector<Gen *> stack2;//目标栈
43 Gen *ptr1=strtogen(); //ptr1初始化为源广义表附加头节点指针
44 Gen *ptr2=nullptr; //ptr2为目标广义表拷贝指针
45 bool TF = true;
46
47 while (true)
48 {
49 if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
50 {
51 if (TF == true)
52 {
53 if (ptr1->utype == 0)
54 {
55 Gen *temp = new Gen(0, ptr1->info.ref);
56 if (ptr1->info.ref == 0)
57 {
58 stack1.push_back(ptr1);
59 stack2.push_back(temp);
60 }
61 else
62 {
63 ptr2->info.hlink = temp;
64 }
65 ptr2 = temp;
66 ptr1 = ptr1->tlink;
67 }
68 else
69 {
70 Gen *temp = new Gen(1);
71 temp->info.hlink = new Gen(0, ptr1->info.hlink->info.ref);
72 if (ptr2->utype == 1)
73 {
74 if (ptr2 == stack2[stack2.size() - 1])
75 ptr2->info.hlink->tlink = temp;
76 else
77 ptr2->tlink = temp;
78 }
79 else
80 {
81 ptr2->tlink = temp;
82 }
83 ptr2 = temp;
84 stack2.push_back(ptr2);
85 stack1.push_back(ptr1);
86 ptr1 = ptr1->info.hlink->tlink;
87 }
88 }
89 else
90 {
91 if (ptr1->utype == 0)
92 {
93 ptr2 = stack2[stack2.size() - 1];
94 stack2.pop_back();
95 break; //拷贝完毕
96 }
97 else
98 {
99 ptr2 = stack2[stack2.size() - 1];
100 stack2.pop_back();
101 ptr1 = ptr1->tlink;
102 TF = true;
103 }
104 }
105 }
106 else
107 {
108 if (ptr1 == nullptr)
109 {
110 ptr2 = nullptr;
111 ptr1 = stack1[stack1.size() - 1];
112 stack1.pop_back();
113 TF = false;
114 }
115 else
116 {
117 Gen *temp = new Gen(2, ptr1->info.value);
118 if (ptr2->utype == 1 && stack2[stack2.size() - 1] == ptr2)
119 ptr2->info.hlink->tlink = temp;
120 else
121 ptr2->tlink = temp;
122 ptr2 = temp;
123 ptr1 = ptr1->tlink;
124 }
125 }
126 }
127 cout << "复制完成,复制后的广义表为:";
128 suboutput(ptr2);
129 return 0;
130 }
131
132 void suboutput(Gen *head)
133 {
134 Gen *ptr = head;
135 bool TF = true;
136 vector<Gen *> stack;
137 while (true)
138 {
139 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意
140 {
141 if (TF == true)
142 {
143 if (ptr->utype == 0) //注意
144 {
145 if (ptr->info.ref == 0)
146 {
147 stack.push_back(ptr);
148 cout << "(";
149 }
150 ptr = ptr->tlink;
151 }
152 else
153 {
154 stack.push_back(ptr);
155 cout << "(";
156 ptr = ptr->info.hlink;
157 }
158 }
159 else
160 {
161 if (ptr == head)
162 break;
163 else
164 {
165 ptr = ptr->tlink;
166 TF = true;
167 }
168 }
169 }
170 else
171 {
172 if (ptr == nullptr)
173 {
174 cout << ")";
175 ptr = stack[stack.size() - 1];
176 if (ptr->tlink != nullptr && ptr != head) //注意
177 cout << ",";
178 stack.pop_back();
179 TF = false;
180 }
181 else
182 {
183 cout << ptr->info.value;
184 ptr = ptr->tlink;
185 if (ptr != nullptr)
186 cout << ",";
187 }
188 }
189 }
190 cout << endl;
191 }
192
193 Gen * strtogen()
194 {
195 string glist;
196 cout << "请输入广义表的字符串形式" << endl;
197 cin >> glist;
198
199 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
200 int ref = 0;
201 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
202 {
203 if (*i == '(')
204 {
205 if (i == glist.cbegin())
206 {
207 ptr = new Gen(0, 0);
208 stack.push_back(ptr);
209 TF = true;
210 }
211 else
212 {
213 Gen *temp = new Gen(1);
214 if (ptr->utype == 1)
215 {
216 if (TF == true)
217 ptr->info.hlink->tlink = temp;
218 else
219 ptr->tlink = temp;
220 }
221 else
222 {
223 ptr->tlink = temp;
224 }
225
226 stack.push_back(temp);
227 TF = true;
228 ptr = temp;
229 temp = new Gen(0, ++ref);
230 ptr->info.hlink = temp;
231 }
232 }
233 else
234 {
235 if (*i == ')')
236 {
237 ptr = stack[stack.size() - 1];
238 stack.pop_back();
239 TF = false;
240 }
241 else
242 {
243 if (*i != ',')
244 {
245 Gen *temp = new Gen(2, *i);
246 if (ptr->utype == 1)
247 {
248 if (TF == true)
249 ptr->info.hlink->tlink = temp;
250 else
251 ptr->tlink = temp;
252 }
253 else
254 {
255 ptr->tlink = temp;
256 }
257
258 ptr = temp;
259 }
260 }
261 }
262 }
263 return ptr;
264 }
基于链表表示比较广义表
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) : utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
30
31 Gen::Gen(int u, char v) : utype(u), tlink(nullptr)
32 {
33 info.value = v;
34 }
35
36 bool equals(Gen *ptr1, Gen *ptr2);
37 Gen * strtogen();
38
39 int main()
40 {
41 vector<Gen *> stack1; vector<Gen *> stack2;
42 Gen *ptr1 = strtogen(); //指向广义表1附加头节点
43 Gen *ptr2 = strtogen(); //指向广义表2附加头节点
44 //两指针同步动作
45 bool TF = true;
46 int isequals = 1;
47 while (true)
48 {
49 if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
50 {
51 if (TF == true)
52 {
53 if (ptr1->utype == 0)
54 {
55 stack1.push_back(ptr1);
56 stack2.push_back(ptr2);
57 ptr1 = ptr1->tlink;
58 ptr2 = ptr2->tlink;
59 }
60 else
61 {
62 if (equals(ptr1, ptr2) == true)
63 {
64 stack1.push_back(ptr1);
65 stack2.push_back(ptr2);
66 ptr1 = ptr1->info.hlink->tlink;
67 ptr2 = ptr2->info.hlink->tlink;
68 }
69 else
70 {
71 isequals = 0;
72 break;
73 }
74 }
75 }
76 else
77 {
78 if (ptr1->utype == 0)
79 break;
80 else
81 {
82 ptr1 = ptr1->tlink;
83 ptr2 = ptr2->tlink;
84 TF = true;
85 }
86 }
87 }
88 else
89 {
90 if (ptr1 == nullptr)
91 {
92 if (equals(ptr1, ptr2) == true)
93 {
94 ptr1 = stack1[stack1.size() - 1];
95 ptr2 = stack2[stack2.size() - 1];
96 stack1.pop_back();
97 stack2.pop_back();
98 TF = false;
99 }
100 else
101 {
102 isequals = 0;
103 break;
104 }
105 }
106 else
107 {
108 if (equals(ptr1, ptr2) == true)
109 {
110 ptr1 = ptr1->tlink;
111 ptr2 = ptr2->tlink;
112 }
113 else
114 {
115 isequals = 0;
116 break;
117 }
118 }
119 }
120 }
121 if (isequals)
122 cout << "两广义表相等";
123 else
124 cout << "两广义表不等";
125 cout << endl;
126 return 0;
127 }
128
129 bool equals(Gen *ptr1, Gen *ptr2)
130 {
131 if (ptr1 == nullptr && ptr2 == nullptr)
132 return true;
133 else
134 {
135 if (ptr1 != nullptr && ptr2 != nullptr)
136 {
137 if (ptr1->utype != ptr2->utype)
138 return false;
139 else
140 {
141 if (ptr1->utype == 1)
142 return true;
143 else
144 {
145 if (ptr1->info.value == ptr2->info.value)
146 return true;
147 else
148 return false;
149 }
150 }
151 }
152 else
153 {
154 return false;
155 }
156 }
157 }
158
159 Gen *strtogen()
160 {
161 string glist;
162 cout << "请输入广义表的字符串形式" << endl;
163 cin >> glist;
164
165 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
166 int ref = 0;
167 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
168 {
169 if (*i == '(')
170 {
171 if (i == glist.cbegin())
172 {
173 ptr = new Gen(0, 0);
174 stack.push_back(ptr);
175 TF = true;
176 }
177 else
178 {
179 Gen *temp = new Gen(1);
180 if (ptr->utype == 1)
181 {
182 if (TF == true)
183 ptr->info.hlink->tlink = temp;
184 else
185 ptr->tlink = temp;
186 }
187 else
188 {
189 ptr->tlink = temp;
190 }
191
192 stack.push_back(temp);
193 TF = true;
194 ptr = temp;
195 temp = new Gen(0, ++ref);
196 ptr->info.hlink = temp;
197 }
198 }
199 else
200 {
201 if (*i == ')')
202 {
203 ptr = stack[stack.size() - 1];
204 stack.pop_back();
205 TF = false;
206 }
207 else
208 {
209 if (*i != ',')
210 {
211 Gen *temp = new Gen(2, *i);
212 if (ptr->utype == 1)
213 {
214 if (TF == true)
215 ptr->info.hlink->tlink = temp;
216 else
217 ptr->tlink = temp;
218 }
219 else
220 {
221 ptr->tlink = temp;
222 }
223
224 ptr = temp;
225 }
226 }
227 }
228 }
229 return ptr;
230 }
广义表字符串形式和链表表示的转换
1 #include "stdafx.h"
2 #include <iostream>
3 #include <string>
4 #include <vector>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 Gen(int u, int r);
20 };
21 Gen::Gen(int u) :utype(u), tlink(nullptr)
22 {
23 info.hlink = nullptr;
24 }
25
26 Gen::Gen(int u, int r) :utype(u), tlink(nullptr)
27 {
28 info.ref = r;
29 }
-
您可能感兴趣的文章:
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！
点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论