开发笔记:广义表——头尾链表存储表示的定义与相关操作

作者：ahhylwjj | 来源：互联网 | 2023-09-09 17:32

本文由编程笔记#小编为大家整理，主要介绍了广义表——头尾链表存储表示的定义与相关操作相关的知识，希望对你有一定的参考价值。

1 /****************************************************
2 * *
3 * 文件夹: ▲05 数组和广义表5 GeneralizedList-H&T *
4 * *
5 * 文件名: GeneralizedList-H-T.h *
6 * *
7 * 内容: 广义表（头尾链表存储表示）相关操作列表 *
8 * *
9 ****************************************************/
10
11 #ifndef GENERALIZEDLIST_H_T_H
12 #define GENERALIZEDLIST_H_T_H
13
14 #include
15 #include //提供malloc、realloc、free、exit原型
16 #include "../../01 绪论/Status.h" //**▲01 绪论**//
17 #include "../../04 串/01 SequenceString/SequenceString.c" //**▲04 串**//
18
19 /* 广义表（头尾链表存储表示）类型定义 */
20 typedef enum{ Head, Tail }Mark;
21 typedef enum{ Atom, List }ElemTag; //Atom==0：原子结点，List==1：表结点
22 typedef char AtomType; //原子类型
23 typedef struct GLNode
24 {
25 union{ int mark; }; //匿名联合，仅在第8章广义表遍历算法中使用
26
27 ElemTag tag; //公共部分，用于区分原子结点和表结点
28 union //原子结点和表结点的联合部分
29 {
30 AtomType atom; //atom是原子结点的值域，AtomType由用户定义
31 struct
32 {
33 struct GLNode *hp; //指向表头
34 struct GLNode *tp; //指向表尾
35 }ptr; //表结点的指针域
36 }Union;
37 }GLNode;
38 typedef GLNode* GList; //广义表类型
39
40 /* 广义表（头尾链表存储）函数列表 */
41 /* ★每一层去掉括号考察★ */
42 void InitGList_GL_H_T(GList *L);
43 /*━━━━━━━━━━━━━━━━━━━┓
44 ┃(01)初始化广义链表（创建空的广义表）。┃
45 ┗━━━━━━━━━━━━━━━━━━━*/
46
47 void sever_GL_H_T_1(SString hstr, SString str);
48 /*━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
49 ┃(02-1)算法5.8：将非空串str分割成两部分:hsub为第一个‘,‘之前的子串,str为之后的子串。┃
50 ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━*/
51
52 void CreateGList_GL_H_T_1(GList *L, SString S);
53 /*━━━━━━━━━━━━━━━┓
54 ┃(03-1)算法5.7：由S创建广义表。┃
55 ┗━━━━━━━━━━━━━━━*/
56
57 void sever_GL_H_T_2(SString hstr, SString str);
58 /*━━━━━━━━━━━━━━━━━━━━━━━━━━┓
59 ┃(02-2)将非空串str分割成两部分:hsub做表头,str做表尾。┃
60 ┗━━━━━━━━━━━━━━━━━━━━━━━━━━*/
61
62 void CreateGList_GL_H_T_2(GList *L, SString S);
63 /*━━━━━━━━━━━┓
64 ┃(03-2)由S创建广义表。 ┃
65 ┗━━━━━━━━━━━*/
66
67 void ClearGList_GL_H_T(GList *L);
68 /*━━━━━━━━━━━━━━┓
69 ┃(04)清空广义表（无法销毁）。┃
70 ┗━━━━━━━━━━━━━━*/
71
72 void CopyGList_GL_H_T(GList *T, GList L);
73 /*━━━━━━━━━━━━━┓
74 ┃(05)算法5.6：复制广义表。 ┃
75 ┗━━━━━━━━━━━━━*/
76
77 int GListLength_GL_H_T(GList L);
78 /*━━━━━━━━━┓
79 ┃(06)求广义表长度。┃
80 ┗━━━━━━━━━*/
81
82 int GListDepth_GL_H_T(GList L);
83 /*━━━━━━━━━━━━━━┓
84 ┃(07)算法5.5：求广义表深度。 ┃
85 ┗━━━━━━━━━━━━━━*/
86
87 Status GListEmpty_GL_H_T(GList L);
88 /*━━━━━━━━━━━━┓
89 ┃(08)判断广义表是否为空。┃
90 ┗━━━━━━━━━━━━*/
91
92 GList GetHead_GL_H_T(GList L);
93 /*━━━━━━━┓
94 ┃(09)获取表头。┃
95 ┗━━━━━━━*/
96
97 GList GetTail_GL_H_T(GList L);
98 /*━━━━━━━┓
99 ┃(10)获取表尾。┃
100 ┗━━━━━━━*/
101
102 void InsertFirst_GL_H_T(GList *L, GList e);
103 /*━━━━━━━━━━━━━━━┓
104 ┃(11)插入e为广义表第一个元素。 ┃
105 ┗━━━━━━━━━━━━━━━*/
106
107 void DeleteFirst_GL_H_T(GList *L, GList *e);
108 /*━━━━━━━━━━━━━━━┓
109 ┃(12)删除广义表表头并用e返回。 ┃
110 ┗━━━━━━━━━━━━━━━*/
111
112 void Traverse_GL_H_T(GList L, void(Visit)(AtomType));
113 /*━━━━━━━━┓
114 ┃(13)遍历广义表。┃
115 ┗━━━━━━━━*/
116
117 void Output_GL_H_T(GList L, Mark mark);
118 /*━━━━━━━━━━━━━━━━━━┓
119 ┃(14)带括号输出广义表L，mark为标记。 ┃
120 ┗━━━━━━━━━━━━━━━━━━*/
121
122 #endif

1 /****************************************************
2 * *
3 * 文件夹: ▲05 数组和广义表5 GeneralizedList-H&T *
4 * *
5 * 文件名: GeneralizedList-H-T.c *
6 * *
7 * 算法: 5.5、5.6、5.7、5.8 *
8 * *
9 ****************************************************/
10
11 #ifndef GENERALIZEDLIST_H_T_C
12 #define GENERALIZEDLIST_H_T_C
13
14 #include "GeneralizedList-H-T.h" //**▲05 数组和广义表**//
15
16 void InitGList_GL_H_T(GList *L)
17 {
18 *L = NULL; //初始化了一个空表，长度为0，深度为1
19 }
20
21 /*════╗
22 ║ 算法5.8║
23 ╚════*/
24 /* 假设广义表各字符间无空格，且输入正确 */
25 void sever_GL_H_T_1(SString hstr, SString str) //str最外层已无括号
26 {
27 int i, k, n;
28 SString ch;
29
30 n = StrLength_Sq(str);
31
32 i = k = 0;
33 do
34 {
35 ++i;
36 SubString_Sq(ch, str, i, 1);
37 if(ch[1]==‘(‘)
38 ++k;
39 if(ch[1]==‘)‘)
40 --k;
41 }while(i1]!=‘,‘ || k!=0));
42
43 if(i<n)
44 {
45 SubString_Sq(hstr, str, 1, i-1);
46 SubString_Sq(str, str, i+1, n-i);
47 }
48 else
49 {
50 StrCopy_Sq(hstr, str);
51 ClearString_Sq(str);
52 }
53 }
54
55 /*════╗
56 ║ 算法5.7║
57 ╚════*/
58 void CreateGList_GL_H_T_1(GList *L, SString S)
59 {
60 SString emp, hsub, sub;
61 GList p, q;
62
63 StrAssign_Sq(emp, "()");
64
65 if(!StrCompare_Sq(S, emp)) //S代表空表
66 *L = NULL; //创建空表
67 else
68 {
69 *L = (GList)malloc(sizeof(GLNode));
70 if(!*L)
71 exit(OVERFLOW);
72
73 if(StrLength_Sq(S)==1) //创建单原子广义表
74 {
75 (*L)->tag = Atom;
76 (*L)->Union.atom = S[1];
77
78 (*L)->mark = 0; //GarbageCollection.c
79 }
80 else
81 {
82 (*L)->tag = List;
83
84 (*L)->mark = 0; //GarbageCollection.c
85
86 p = *L;
87
88 SubString_Sq(sub, S, 2, StrLength_Sq(S)-2); //去掉最外层括号
89
90 do //重复建n个子表
91 {
92 sever_GL_H_T_1(hsub, sub); //分离出表头串hsub
93 CreateGList_GL_H_T_1(&(p->Union.ptr.hp), hsub);
94 q = p;
95 if(!StrEmpty_Sq(sub)) //表尾不为空，处理表尾
96 {
97 p = (GList)malloc(sizeof(GLNode));
98 if(!p)
99 exit(OVERFLOW);
100
101 p->tag = List;
102
103 p->mark = 0; //GarbageCollection.c
104
105 q->Union.ptr.tp = p;
106 }
107 }while(!StrEmpty_Sq(sub));
108 q->Union.ptr.tp = NULL;
109 }
110 }
111 }
112
113 /* 另一种创建广义表的算法，与上述算法略有不同 */
114 /* 假设广义表各字符间无空格，且输入正确 */
115 void sever_GL_H_T_2(SString hstr, SString str) //将str分解为表头元素和表尾元素两部分
116 {
117 int i = 1;
118 int k = 0;
119 int n;
120 SString tmp;
121
122 SubString_Sq(tmp, str, 2, StrLength_Sq(str)-2);
123
124 n = StrLength_Sq(tmp);
125
126 while(i‘,‘ || k!=0))
127 {
128 if(tmp[i]==‘(‘)
129 k++;
130 if(tmp[i]==‘)‘)
131 k--;
132 i++;
133 }
134
135 if(i<n)
136 SubString_Sq(hstr, tmp, 1, i-1);
137 else
138 StrCopy_Sq(hstr, tmp);
139
140 StrDelete_Sq(str, 2, i);
141 }
142
143 void CreateGList_GL_H_T_2(GList *L, SString S)
144 {
145 SString hsub, sub, emp;
146 GList p, q;
147
148 StrAssign_Sq(emp, "()");
149
150 if(!StrCompare_Sq(S, emp))
151 *L = NULL;
152 else
153 {
154 *L = (GList)malloc(sizeof(GLNode));
155
156 if(StrLength_Sq(S)==1)
157 {
158 (*L)->tag = Atom;
159 (*L)->Union.atom = S[1];
160 }
161 else
162 {
163 (*L)->tag = List;
164 p = *L;
165
166 StrCopy_Sq(sub, S);
167
168 do
169 {
170 sever_GL_H_T_2(hsub, sub);
171 CreateGList_GL_H_T_2(&(p->Union.ptr.hp), hsub);
172
173 if(StrCompare_Sq(sub, emp))
174 {
175 q = p;
176 p = (GList)malloc(sizeof(GLNode));
177 p->tag = List;
178 q->Union.ptr.tp = p;
179 }
180 }while(StrCompare_Sq(sub, emp));
181 p->Union.ptr.tp = NULL;
182 }
183 }
184 }
185
186 void ClearGList_GL_H_T(GList *L)
187 {
188 GList p, q;
189
190 if(*L)
191 {
192 if((*L)->tag==Atom)
193 {
194 free(*L); //删除原子结点
195 *L = NULL;
196 }
197 else //删除表结点
198 {
199 p = (*L)->Union.ptr.hp;
200 q = (*L)->Union.ptr.tp;
201 free(*L);
202 *L = NULL;
203 ClearGList_GL_H_T(&p);
204 ClearGList_GL_H_T(&q);
205 }
206 }
207 }
208
209 /*════╗
210 ║ 算法5.6║
211 ╚════*/
212 void CopyGList_GL_H_T(GList *T, GList L)
213 {
214 if(!L)
215 *T = NULL;
216 else
217 {
218 *T = (GList)malloc(sizeof(GLNode)); //建表结点
219 if(!*T)
220 exit(OVERFLOW);
221
222 (*T)->tag = L->tag;
223
224 if(L->tag==Atom) //复制单原子
225 (*T)->Union.atom = L->Union.atom;
226 else //复制表头和表尾
227 {
228 CopyGList_GL_H_T(&((*T)->Union.ptr.hp), L->Union.ptr.hp);
229 CopyGList_GL_H_T(&((*T)->Union.ptr.tp), L->Union.ptr.tp);
230 }
231 }
232 }
233
234 int GListLength_GL_H_T(GList L)
235 {
236 int count;
237
238 for(count=0; L; count++,L=L->Union.ptr.tp)
239 ;
240
241 return count;
242 }
243
244 /*════╗
245 ║ 算法5.5║
246 ╚════*/
247 int GListDepth_GL_H_T(GList L)
248 {
249 int max, deep;
250 GList p;
251
252 if(!L) //空表深度为1
253 return 1;
254
255 if(L->tag==Atom) //原子深度为0
256 return 0;
257
258 for(max=0,p=L; p; p=p->Union.ptr.tp)
259 {
260 deep = GListDepth_GL_H_T(p->Union.ptr.hp);
261 if(deep>max)
262 max = deep;
263 }
264
265 return max + 1; //非空表的深度是各元素最大深度加一
266 }
267
268 Status GListEmpty_GL_H_T(GList L)
269 {
270 if(!L)
271 return TRUE;
272 else
273 return FALSE;
274 }
275
276 GList GetHead_GL_H_T(GList L)
277 {
278 GList p;
279
280 if(!L)
281 {
282 printf("广义表为空表，无法获取表头！
");
283 exit(ERROR);
284 }
285
286 CopyGList_GL_H_T(&p, L->Union.ptr.hp);
287
288 return p;
289 }
290
291 GList GetTail_GL_H_T(GList L)
292 {
293 GList p;
294
295 if(!L)
296 {
297 printf("广义表为空表，无法获取表尾！
");
298 exit(ERROR);
299 }
300
301 CopyGList_GL_H_T(&p, L->Union.ptr.tp);
302
303 return p;
304 }
305
306 void InsertFirst_GL_H_T(GList *L, GList e)
307 {
308 GList g;
309
310 g = (GList)malloc(sizeof(GLNode));
311 if(!g)
312 exit(OVERFLOW);
313
314 g->tag = 1;
315 g->Union.ptr.hp = e;
316 g->Union.ptr.tp = *L;
317 *L = g;
318 }
319
320 void DeleteFirst_GL_H_T(GList *L, GList *e)
321 {
322 GList p;
323
324 if(!(*L))
325 {
326 printf("广义表为空表，删除表头失败！
");
327 exit(ERROR);
328 }
329
330 p = *L;
331 *L = (*L)->Union.ptr.tp;
332
333 CopyGList_GL_H_T(e, p->Union.ptr.hp);
334
335 free(p);
336 p = NULL;
337 }
338
339 void Traverse_GL_H_T(GList L, void(Visit)(AtomType))
340 {
341 if(L)
342 {
343 if(L->tag==Atom)
344 Visit(L->Union.atom);
345 else
346 {
347 Traverse_GL_H_T(L->Union.ptr.hp, Visit);
348 Traverse_GL_H_T(L->Union.ptr.tp, Visit);
349 }
350 }
351 }
352
353 void Output_GL_H_T(GList L, Mark mark)
354 {
355 if(!L) //L为空
356 {
357 if(mark==Head) //mark=0代表广义表指针来自表头
358 printf("()");
359 else //mark=1代表广义表指针来自表尾
360 printf(")");
361 }
362 else //L不为空时
363 {
364 if(L->tag==Atom) //对于原子结点，输出原子
365 printf("%c",L->Union.atom);
366 else //对于表结点，要对表头、表尾分别讨论
367 {
368 if(mark==Head)
369 printf("(");
370 else
371 printf(",");
372
373 Output_GL_H_T(L->Union.ptr.hp, Head);
374 Output_GL_H_T(L->Union.ptr.tp, Tail);
375 }
376 }
377 }
378
379 #endif

推荐阅读

copy
C#学习教程：使用RSACryptoServiceProvider进行公钥加密分享

使用RSACryptoServiceProvider进行公钥加密我已经在CodeProject上发表了一篇文章，解释了如何使用RSA提供程序进行加密和解密：RSA私钥加密虽然200 ... [详细]

蜡笔小新 2024-09-29 18:06:38
int
c++ bmp图像保存之后为全黑

最近自己做一个工具最后涉及到一个存储成bmp位图的形式，由于这部分并不是整个project的重点我就从网上找了例子改了改，但是目前的问题是有很多时候都是存储的bmp全黑,我也并不知道是怎么回事。 ... [详细]

蜡笔小新 2024-09-30 13:15:34
数组
C#学习教程：C＃按值复制数组分享

C＃按值复制数组我有一个类型化的数组MyType[]types;我想制作这个数组的独立副本。我试过这个MyType[]types2newMyType[types.Length];t ... [详细]

蜡笔小新 2024-09-29 13:08:34
main
黑马程序员——OC语言——内存管理

———Java培训、Android培训、iOS培训、.Net培训、期待与您交流！———一、引用计数器每个OC对象都有自己的引用计数器，表示“对象被引用 ... [详细]

蜡笔小新 2024-09-28 12:42:08
main
【第7周项目4字符串加密】

*Copyright(c)2016,烟台大学计算机与控制工程学院Allrightsreserved.文件名称：字符串加密.cpp作者：彭友程完成日期&# ... [详细]

蜡笔小新 2024-09-27 22:14:40
python
以下不是python文件读写方法的是Python 文件I/O

Python文件IO本章只讲述所有基本的IO函数，更多函数请参考Python标准文档。打印到屏幕最简单的输出方法是用print语句，你可以给它传递 ... [详细]

蜡笔小新 2024-09-30 14:49:29
js
MyBatis模糊查询和多条件查询

MyBatis模糊查询和多条件查询一、ISmbmsUserDao层根据姓名模糊查询publicListgetUser();多条件查询publicList ... [详细]

蜡笔小新 2024-09-30 13:26:10
main
Java 中的 FileStore getUsableSpace()方法，带示例

Java中的FileStoregetUsableSpace()方法，带示例 ... [详细]

蜡笔小新 2024-09-30 12:40:44
int
什么是Maven神器？

本文翻译自：WhatisaMavenartifact?什么是神器？为什么Maven需要它？#1楼参考：https:sta ... [详细]

蜡笔小新 2024-09-30 10:32:49
text
Mysql MySqlBulkLoader在.NET平台下的批量插入

批量导入publicboolTranBatchImpo ... [详细]

蜡笔小新 2024-09-30 10:20:25
text
openssl 实现https 网站

下面是一个用openssl实现获取https网页内容的demo，整个流程比较简单，主要封装的API如下staticinthttps_init(http ... [详细]

蜡笔小新 2024-09-29 16:41:10
数组
删除数组中的第一级标识符。 - Remove first levels of identifier in array

Ithinkthishasbeenupbefore,butcouldntfindanyanswertoit.Ifitsalreadyansweredplease ... [详细]

蜡笔小新 2024-09-29 12:47:47
js
根据时间更改网站背景的脚本。热！

我在网上找到了它，并以自己的方式对其进行了自定义；作者的功劳就在那里。实际上，这是一个用于更改背景颜色的脚本，并且在我看来& ... [详细]

蜡笔小新 2024-09-28 12:47:14
int
org.apache.hadoop.mapreduce.lib.input.MultipleInputs.addInputPath()方法的使用及代码示例

本文整理了Java中org.apache.hadoop.mapreduce.lib.input.MultipleInputs.addInputPath()方法的一些代码 ... [详细]

蜡笔小新 2024-09-28 10:57:44
int
org.assertj.core.api.AbstractCharSequenceAssert.hasSize()方法的使用及代码示例

本文整理了Java中org.assertj.core.api.AbstractCharSequenceAssert.hasSize()方法的一些代码示例，展示了 ... [详细]

蜡笔小新 2024-09-28 10:08:14

ahhylwjj

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章