哪些茶叶是绿茶,长隆欢乐世界万圣节,3d电影下载迅雷
广义表链表表示的删除：
从广义表附加头节点开始，逐一分离表头元素，是原子项就直接删除,是子表附加头节点则暂不删除，直接进入子表，再分离表头元素，然后用相同的方法删除，子表删除完成后向上回溯，继续删除上一层子表，如此不断进行直到整个广义表被删除为止
代码（C++）
我要评论 1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include<string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 };
20 Gen::Gen(int u) :utype(u), tlink(nullptr)
21 {
22 if (u == 0)
23 info.ref = 0;
24 else
25 info.hlink = nullptr;
26 }
27
28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr)
29 {
30 info.value = v;
31 }
32
33 Gen * strtogen();
34
35 int main()
36 {
37 Gen *ptr = strtogen(); //ptr初始化为广义表附加头结点指针
38 bool TF = true;
39 vector<Gen *> stack;
40
41 while (true)
42 {
43 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))
44 {
45 if (TF == true)
46 {
47 stack.push_back(ptr);
48 if (ptr->utype == 0)
49 {
50 if (ptr->tlink == nullptr)
51 {
52 stack.pop_back();
53 TF = false;
54 continue;
55 }
56 ptr = ptr->tlink; //拉链，分理出广义表附加头节点的下一待删除节点
57 stack[stack.size() - 1]->tlink = ptr->tlink;
58 }
59 else
60 {
61 if (ptr->info.hlink == nullptr)
62 TF = false;
63 else
64 {
65 ptr = ptr->info.hlink; //拉链，分离出ptr指向的子表附加头节点在子表中的下一节点
66 stack[stack.size() - 1]->info.hlink = ptr->tlink;
67 }
68 }
69 }
70 else
71 {
72 if (ptr->utype == 0)
73 {
74 delete ptr; //删除附加头节点，至此删除成功，退出
75 break;
76 }
77 else
78 {
79 delete ptr; //删除子表附加头节点，子表删除成功
80 stack.pop_back();
81 ptr = nullptr;
82 }
83 }
84 }
85 else
86 {
87 if (ptr == nullptr)
88 {
89 if (stack[stack.size() - 1]->utype == 0)
90 {
91 if (stack[stack.size() - 1]->tlink == nullptr) //广义表除附加头节点全部删除完毕
92 {
93 TF = false;
94 ptr = stack[stack.size() - 1];
95 stack.pop_back();
96 }
97 else //广义表附加头节点下一子表附加头节点及子表删除完毕
98 {
99 ptr = stack[stack.size() - 1]->tlink;
100 stack[stack.size() - 1]->tlink = ptr->tlink;
101 TF = true;
102 }
103 }
104 else
105 {
106 if (stack[stack.size() - 1]->info.hlink == nullptr) //子表除附加头节点全部删除完毕
107 {
108 TF = false;
109 ptr = stack[stack.size()-1];
110 }
111 else //子表附加头节点下一子表附加头节点及子表删除完毕
112 {
113 ptr = stack[stack.size() - 1]->info.hlink;
114 stack[stack.size() - 1]->info.hlink = ptr->tlink;
115 TF = true;
116 }
117 }
118 }
119 else
120 {
121 if (stack[stack.size() - 1]->utype == 0)
122 {
123 if (stack[stack.size() - 1]->tlink == nullptr) //广义表除附加头节点外还剩一个原子项待删除
124 {
125 delete ptr; //删除之
126 ptr = stack[stack.size() - 1];
127 stack.pop_back();
128 TF = false;
129 }
130 else //广义表头节点后的原子项待删除,其后还有节点待删除
131 {
132 delete ptr;
133 ptr = stack[stack.size() - 1]->tlink;
134 stack[stack.size() - 1]->tlink = ptr->tlink;
135 }
136 }
137 else
138 {
139 if (stack[stack.size() - 1]->info.hlink == nullptr) //子表除附加头节点外还剩一个原子项待删除
140 {
141 delete ptr;
142 ptr = stack[stack.size() - 1];
143 TF = false;
144 }
145 else //子表头节点后的原子项待删除,其后还有节点待删除
146 {
147 delete ptr;
148 ptr = stack[stack.size() - 1]->info.hlink;
149 stack[stack.size() - 1]->info.hlink = ptr->tlink;
150 }
151 }
152 }
153 }
154 }
155 //运行结束后ptr成为野指针,栈空,删除成功
156 cout << "链表形式的广义表删除成功!"<< endl;
157 return 0;
158 }
159
160 Gen * strtogen()
161 {
162 string glist;
163 cout << "请输入广义表的字符串形式" << endl;
164 cin >> glist;
165
166 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
167 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
168 {
169 if (*i == '(')
170 {
171 if (i == glist.cbegin())
172 {
173 ptr = new Gen(0);
174 stack.push_back(ptr);
175 TF = true;
176 }
177 else
178 {
179 Gen *temp = new Gen(1);
180 if (ptr->utype == 1)
181 {
182 if (TF == true)
183 ptr->info.hlink = temp;
184 else
185 ptr->tlink = temp;
186 }
187 else
188 {
189 ptr->tlink = temp;
190 }
191
192 stack.push_back(temp);
193 TF = true;
194 ptr = temp;
195 }
196 }
197 else
198 {
199 if (*i == ')')
200 {
201 ptr = stack[stack.size() - 1];
202 stack.pop_back();
203 TF = false;
204 }
205 else
206 {
207 if (*i != ',')
208 {
209 Gen *temp = new Gen(2, *i);
210 if (ptr->utype == 1)
211 {
212 if (TF == true)
213 ptr->info.hlink = temp;
214 else
215 ptr->tlink = temp;
216 }
217 else
218 {
219 ptr->tlink = temp;
220 }
221
222 ptr = temp;
223 }
224 }
225 }
226 }
227 cout << "已将字符串形式的广义表转换为链表形式" << endl;
228 return ptr;
229 }
广义表链表表示的复制：
就是按广度优先遍历的次序逐一复制，为方便复制，目标表指针总比原表遍历指针慢一步，原表遍历完成后复制就结束了
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 };
20 Gen::Gen(int u) :utype(u), tlink(nullptr)
21 {
22 if (u == 0)
23 info.ref = 0;
24 else
25 info.hlink = nullptr;
26 }
27
28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr)
29 {
30 info.value = v;
31 }
32
33 Gen * strtogen();
34 void suboutput(Gen *head);
35
36 int main()
37 {
38 vector<Gen *> stack1;//源栈
39 vector<Gen *> stack2;//目标栈
40 Gen *ptr1=strtogen(); //ptr1初始化为源广义表附加头节点指针
41 Gen *ptr2=nullptr; //ptr2为目标广义表拷贝指针
42 bool TF = true;
43
44 while (true) //循环开始,将源广义表链表表示拷贝为目标广义表链表表示
45 {
46 if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
47 {
48 if (TF == true)
49 {
50 stack1.push_back(ptr1);
51 if (ptr1->utype == 0)
52 {
53 ptr2 = new Gen(0); //拷贝广义表附加头节点,完成后ptr1递进
54 ptr2->info.ref = ptr1->info.ref;
55 stack2.push_back(ptr2);
56 ptr1 = ptr1->tlink;
57 }
58 else
59 {
60 if (ptr2->utype == 1) //需要把子表附加头节点拷贝至ptr2所指附加头节点后
61 {
62 Gen *temp = new Gen(1);
63 if (ptr2 == stack2[stack2.size() - 1]) //ptr2新进至子表头节点,源广义表子表头节点链接至ptr2所指子表中头节点后
64 ptr2->info.hlink = temp;
65 else
66 ptr2->tlink = temp;
67 ptr2 = temp;
68 stack2.push_back(ptr2);
69 ptr1 = ptr1->info.hlink;
70 }
71 else
72 {
73 Gen *temp = new Gen(1); //由于ptr2指向目标广义表头节点或原子项，所以直接把待拷贝子表头节点链接于其后
74 ptr2->tlink = temp;
75 ptr2 = temp;
76 stack2.push_back(ptr2);
77 ptr1 = ptr1->info.hlink;
78 }
79 }
80 }
81 else
82 {
83 if (ptr1->utype == 0)
84 {
85 ptr2 = stack2[stack2.size() - 1];
86 stack2.pop_back();
87 break; //拷贝完毕，退出，ptr2为目标广义表头节点
88 }
89 else
90 {
91 ptr2 = stack2[stack2.size() - 1];
92 stack2.pop_back();
93 ptr1 = ptr1->tlink;
94 TF = true;
95 }
96 }
97 }
98 else
99 {
100 if (ptr1 == nullptr) //子表拷贝完毕
101 {
102 ptr2 = nullptr;
103 ptr1 = stack1[stack1.size() - 1];
104 stack1.pop_back();
105 TF = false;
106 }
107 else
108 {
109 Gen *temp = new Gen(2, ptr1->info.value); //拷贝原子项
110 if (ptr2->utype == 1 && stack2[stack2.size() - 1] == ptr2)
111 ptr2->info.hlink = temp; //如果ptr2新进至子表头节点，操作和上述相同
112 else
113 ptr2->tlink = temp; //操作和上述相同
114 ptr2 = temp;
115 ptr1 = ptr1->tlink;
116 }
117 }
118 }
119 cout << "复制完成,复制后的广义表为:";
120 suboutput(ptr2); //输出复制后的广义表
121 return 0;
122 }
123
124 Gen * strtogen()
125 {
126 string glist;
127 cout << "请输入广义表的字符串形式" << endl;
128 cin >> glist;
129
130 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
131 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
132 {
133 if (*i == '(')
134 {
135 if (i == glist.cbegin())
136 {
137 ptr = new Gen(0);
138 stack.push_back(ptr);
139 TF = true;
140 }
141 else
142 {
143 Gen *temp = new Gen(1);
144 if (ptr->utype == 1)
145 {
146 if (TF == true)
147 ptr->info.hlink = temp;
148 else
149 ptr->tlink = temp;
150 }
151 else
152 {
153 ptr->tlink = temp;
154 }
155
156 stack.push_back(temp);
157 TF = true;
158 ptr = temp;
159 }
160 }
161 else
162 {
163 if (*i == ')')
164 {
165 ptr = stack[stack.size() - 1];
166 stack.pop_back();
167 TF = false;
168 }
169 else
170 {
171 if (*i != ',')
172 {
173 Gen *temp = new Gen(2, *i);
174 if (ptr->utype == 1)
175 {
176 if (TF == true)
177 ptr->info.hlink = temp;
178 else
179 ptr->tlink = temp;
180 }
181 else
182 {
183 ptr->tlink = temp;
184 }
185
186 ptr = temp;
187 }
188 }
189 }
190 }
191 cout << "已将字符串形式的广义表转换为链表形式" << endl;
192 return ptr;
193 }
194
195 void suboutput(Gen *head)
196 {
197 Gen *ptr = head;
198 bool TF = true;
199 vector<Gen *> stack;
200 while (true)
201 {
202 if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) //注意
203 {
204 if (TF == true)
205 {
206 stack.push_back(ptr);
207 cout << "(";
208 if (ptr->utype == 0) //注意
209 {
210 ptr = ptr->tlink;
211 }
212 else
213 {
214 ptr = ptr->info.hlink;
215 }
216 }
217 else
218 {
219 if (ptr->utype == 0)
220 break;
221 else
222 {
223 ptr = ptr->tlink;
224 TF = true;
225 }
226 }
227 }
228 else
229 {
230 if (ptr == nullptr)
231 {
232 cout << ")";
233 ptr = stack[stack.size() - 1];
234 if (ptr->utype != 0 && ptr->tlink != nullptr) //注意
235 cout << ",";
236 stack.pop_back();
237 TF = false;
238 }
239 else
240 {
241 cout << ptr->info.value;
242 ptr = ptr->tlink;
243 if (ptr != nullptr)
244 cout << ",";
245 }
246 }
247 }
248 cout << endl;
249 }
运行结果：
基于广义表链表表示的比较：
两表指针同步动作，按广度优先遍历逐一比较，比较到某一处节点不等则广义表不等，否则会一直比较至遍历完整个广义表，此时两广义表相等
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <string>
5 using namespace std;
6
7 struct Gen
8 {
9 int utype;
10 union
11 {
12 int ref;
13 struct Gen *hlink;
14 char value;
15 }info;
16 struct Gen *tlink;
17 Gen(int u);
18 Gen(int u, char v);
19 };
20 Gen::Gen(int u) :utype(u), tlink(nullptr)
21 {
22 if (u == 0)
23 info.ref = 0;
24 else
25 info.hlink = nullptr;
26 }
27
28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr)
29 {
30 info.value = v;
31 }
32
33 bool equals(Gen *ptr1, Gen *ptr2); //判断ptr1和ptr2指向的广义表节点是否相等的函数
34 Gen * strtogen();
35
36 int main()
37 {
38 vector<Gen *> stack1; vector<Gen *> stack2;
39 Gen *ptr1 = strtogen(); //指向广义表1附加头节点
40 Gen *ptr2= strtogen(); //指向广义表2附加头节点
41 //两指针同步动作
42 bool TF = true;
43 int isequals = 1; //=1两广义表相等，否则不等
44 while (true)
45 {
46 if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1))
47 {
48 if (TF == true)
49 {
50 if (ptr1->utype == 0)
51 {
52 stack1.push_back(ptr1);
53 stack2.push_back(ptr2);
54 ptr1 = ptr1->tlink; //附加头节点不必比较，跳过
55 ptr2 = ptr2->tlink;
56 }
57 else
58 {
59 if (equals(ptr1, ptr2) == true) //比较表1子表头节点或指针和表2对应位置节点或指针
60 {
61 stack1.push_back(ptr1);
62 stack2.push_back(ptr2);
63 ptr1 = ptr1->info.hlink;
64 ptr2 = ptr2->info.hlink;
65 }
66 else
67 {
68 isequals = 0; //不等,isequals置位，退出
69 break;
70 }
71 }
72 }
73 else
74 {
75 if (ptr1->utype == 0) //比较完成,退出
76 break;
77 else
78 {
79 ptr1 = ptr1->tlink;
80 ptr2 = ptr2->tlink;
81 TF = true;
82 }
83 }
84 }
85 else
86 {
87 if (ptr1 == nullptr)
88 {
89 if (equals(ptr1, ptr2) == true) //比较ptr1或其指向节点和ptr2或其指向节点
90 {
91 ptr1 = stack1[stack1.size() - 1];
92 ptr2 = stack2[stack2.size() - 1];
93 stack1.pop_back();
94 stack2.pop_back();
95 TF = false;
96 }
97 else
98 {
99 isequals = 0;
100 break;
101 }
102 }
103 else
104 {
105 if (equals(ptr1, ptr2) == true) //比较ptr1或其指向的原子项和表2对应位置指针ptr2或其指向的节点
106 {
107 ptr1 = ptr1->tlink;
108 ptr2 = ptr2->tlink;
109 }
110 else
111 {
112 isequals = 0;
113 break;
114 }
115 }
116 }
117 }
118 if (isequals)
119 cout << "两广义表相等";
120 else
121 cout << "两广义表不等";
122 cout << endl;
123 return 0;
124 }
125
126 bool equals(Gen *ptr1, Gen *ptr2) //ptr1和ptr2所指节点相等返回true否则返回false
127 {
128 if (ptr1 == nullptr && ptr2 == nullptr)
129 return true;
130 else
131 {
132 if (ptr1 != nullptr && ptr2 != nullptr)
133 {
134 if (ptr1->utype != ptr2->utype)
135 return false;
136 else
137 {
138 if (ptr1->utype == 1)
139 return true;
140 else
141 {
142 if (ptr1->info.value == ptr2->info.value)
143 return true;
144 else
145 return false;
146 }
147 }
148 }
149 else
150 {
151 return false;
152 }
153 }
154 }
155
156 Gen * strtogen()
157 {
158 string glist;
159 cout << "请输入广义表的字符串形式" << endl;
160 cin >> glist;
161
162 Gen *ptr = nullptr; vector<Gen *> stack; bool TF;
163 for (auto i = glist.cbegin(); i != glist.cend(); ++i)
164 {
165 if (*i == '(')
166 {
167 if (i == glist.cbegin())
168 {
169 ptr = new Gen(0);
170 stack.push_back(ptr);
171 TF = true;
172 }
173 else
174 {
175 Gen *temp = new Gen(1);
176 if (ptr->utype == 1)
177 {
178 if (TF == true)
179 ptr->info.hlink = temp;
180 else
181 ptr->tlink = temp;
182 }
183 else
184 {
185 ptr->tlink = temp;
186 }
187
188 stack.push_back(temp);
189 TF = true;
190 ptr = temp;
191 }
192 }
193 else
194 {
195 if (*i == ')')
196 {
197 ptr = stack[stack.size() - 1];
198 stack.pop_back();
199 TF = false;
200 }
201 else
202 {
203 if (*i != ',')
204 {
205 Gen *temp = new Gen(2, *i);
206 if (ptr->utype == 1)
207 {
208 if (TF == true)
209 ptr->info.hlink = temp;
210 else
211 ptr->tlink = temp;
212 }
213 else
214 {
215 ptr->tlink = temp;
216 }
217
218 ptr = temp;
219 }
220 }
221 }
222 }
223 cout << "已将字符串形式的广义表转换为链表形式" << endl;
224 return ptr;
225 }
运行结果：
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论