当前位置：文档之家 › 广义表(C++实现)

广义表(C++实现)

  • 格式：pdf
  • 大小：315.13 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

数据结构答案(清华大学出版)

数据结构答案(清华大学出版)
10
若是N维数组，其中任一元素的地址该如何计算？ 若是 维数组，其中任一元素的地址该如何计算？ 维数组 低维优先的地址计算公式，该式称为n维数组的映像函数： 低维优先的地址计算公式，该式称为n维数组的映像函数： 优先的地址计算公式
n
0)＋ Loc(j1,j2,…jn)=LOC(0,0, 0)＋i =1 j )=LOC(0,0,…0)
a11 a12 … a1n ^
… …
am1 am2 … amn ^
^ 注：数组的运算参见下一节实例（稀疏矩阵的转置） 数组的运算参见下一节实例（稀疏矩阵的转置）
13
5.3 矩阵的压缩存储
讨论： 讨论： 1. 什么是压缩存储？ 什么是压缩存储？ 若多个数据元素的值都相同 则只分配一个元素值的存储空间， 值都相同， 若多个数据元素的值都相同，则只分配一个元素值的存储空间， 且零元素不占存储空间。 且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩 一些特殊矩阵， 对称矩阵，对角矩阵，三角矩阵， 阵等。 阵等。 4. 什么叫稀疏矩阵？ 什么叫稀疏矩阵 稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5% 5%） 矩阵中非零元素的个数较少（一般小于5%） 重点介绍稀疏矩阵的压缩和相应的操作。 重点介绍稀疏矩阵的压缩和相应的操作。
8
无论规定行优先或列优先， 无论规定行优先或列优先，只要知道以下三要素便可随时求出 任一元素的地址（这样数组中的任一元素便可以随机存取！ 任一元素的地址（这样数组中的任一元素便可以随机存取！）： ①开始结点的存放地址（即基地址） 开始结点的存放地址（即基地址） 维数和每维的上、下界； ②维数和每维的上、下界； ac1,c2 … ac1,d2 ③每个数组元素所占用的单元数 Amn= … aij … ad1,c2 … ad1,d2 则行优先存储时的地址公式为： 行优先存储时的地址公式为： 存储时的地址公式为 LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L ， aij之前的 数组基址 a 本行前面的

数据结构——用C语言描述(第3版)教学课件第5章 数组与广义表

数据结构——用C语言描述(第3版)教学课件第5章 数组与广义表
第5章 数组和广义表
5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储
5.3.1 三角矩阵 5.3.2 带状矩阵 5.3.3 稀疏矩阵 5.4 广义表 5.5 总结与提高
5.1 数组的定义和运算
数组是一种数据类型。从逻辑结构上看，数组可以 看成是一般线性表的扩充。二维数组可以看成是线 性表的线性表。例如：
Am×n=
a12 a12 ┅
a1j
┅ a1n
a21 a22 ┅
a2j
┅ a2n
┇┇
ai1 ai2 ┅
aij
┇┇
┅ ain
am1 am2 ┅
amj
┅ amn
矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j, …,amj)
我们还可以将数组Am×n看成另外一个线性表: B=(1，,2,，… ，m)，其中i（1≤i ≤m）本身也是一个线性表， 称为行向量，即： I= （ai1，ai2， …，aij ，…，ain）。
Loc[j1,j2,j3]=Loc[c1,c2,c3]+ α1*(j1-c1)+ α2*(j2-c2)+ α3(j3-c3)
=Loc[c1,c2,c3]+ Σαi*(ji-ci) （1≤i≤3）
由公式可知Loc[j1,j2,j3]与j1,j2,j3呈线性关系。 对于ｎ维数组A(c1:d1,c2:d2，…,cn,dn)，我们只要把上式推 广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存储 地址的计算公式。
疏矩阵。
0 12 9 0 0 0 0
0 0 3 0 0 15
0 0 0 00 0 0
12 0 0 0 18 0
M6×7= -3 0 0 0 0 14 0

广义表的操作实现

广义表的操作实现
struct GListNode *tail; //尾链 }subList; } val;
}GLNode;
1
创建广义表
创建广义表就是按照所给的表示具体广义表的字符串str 创建一个广义表h。
对一个广义表的任何操作都可以分解为对表头的操作和 对表尾的操作。同样，创建广义表操作可以分解为创建表 头广义表和创建表尾广义表。因此，创建广义表函数 CreatGList(str)只要递归完成对表头广义表的创建和对表 尾广义表的创建即可。
GLNode *pre; if(h == NULL) return 1; if(h->tag == 0) return 0;
pre = h; for(max = 0; pre != NULL; pre = pre->val.subList.tail) { dep = GListDepth(pre->val.subList.head);
str[++j] = '\0';
//
}
3
else {
} }
str++; strncpy(hstr,str, n-2); hstr[n-2] = '\0'; str--; strcpy(str, "()");
4
GLNode* CreatGList(char str[]) { GLNode *h;
char hstr[200]; int len = strlen(str); if(strcmp(str, "()") == 0) h = NULL; else if(len == 1) { h = (GLNode *)malloc(sizeof(GLNode));

数据结构(c语言版)第五章答案

数据结构(c语言版)第五章答案

第五章1、设二维数组A【8】【10】是一个按行优先顺序存储在内存中的数组，已知A【0】【0】的起始存储位置为1000，每个数组元素占用4个存储单元，求：（1）A【4】【5】的起始存储位置。

A【4】【5】的起始存储位置为1000+（10*4+5）*4=1180；（2）起始存储位置为1184的数组元素的下标。

起始存储位置为1184的数组元素的下标为4（行下标）、6（列下标）。

2、画出下列广义表D=（（c），(e)，(a，(b，c，d))）的图形表示和它们的存储表示。

略，参考第5·2节应用题第5题分析与解答。

3、已知A为稀疏矩阵，试从时间和空间角度比较采用两种不同的存储结构（二维数组和三元组表）实现求∑a(i，j)运算的优缺点。

稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求∑ii a(1≤i≤n)时，由于a【i】【i】随机存取，速度快。

但采用三元组表时，若非零元素个数为t，需3t+3个存储单元（t个分量存各非零元素的行值、列值、元素值），同时还需要三个存储单元存储存稀疏矩阵A的行数、列数和非零元素个数，比二维数组节省存储单元；但在求∑ii a（1≤i≤n）时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。

4、利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间？当m行n列稀疏矩阵中非零元素个数为t，当满足关系3*t<m*n时，利用三元组存储稀疏数组时，才能节省存储空间。

5、求下列各广义表的操作结果。

（1）GetHead((a,(b,c),d))GetHead((a,(b,c),d))=a（2）GetTail((a,(b,c),d))GetTail((a,(b,c),d))=((b,c),d)（3）GetHead(GetTail((a,(b,c),d)))GetHead(GetTail((a,(b,c),d)))=(b,c)（4）GetTail(GetHead((a,(b,c),d)))GetTail(GetHead((a,(b,c),d)))=()第六章1、已知一棵树边的集合为{（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？（11）树的度数是多少？略。

数据结构（C语言版）（第2版）课后习题答案

数据结构（C语言版）（第2版）课后习题答案

数据结构（C语言版）（第2版）课后习题答案数据结构（C语言版）（第2版）课后习题答案目录第1章绪论1 第2章线性表5 第3章栈和队列13 第4章串、数组和广义表26 第5章树和二叉树33 第6章图43 第7章查找54 第8章排序65 第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，。

}，字母字符数据对象是集合C={‘A’，‘B’，。

，‘Z’，‘a’，‘b’，。

，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

Chapter05_数组和广义表_数据结构(C语言版)_严蔚敏_配套ppt课件

Chapter05_数组和广义表_数据结构(C语言版)_严蔚敏_配套ppt课件

M
1 1 2 3 3 4
1 5 3 1 2 4
3 7 -1 -1 -2 2
N
1 1 2 3 4 5
1 3 3 2 4 1
3 -1 -2 -1 2 7
行列下 标调换
1 5 3 1 2 4
1 1 2 3 3 4
3 7 -1 -1 -2 2
按行下 标排序
法1：
按照矩阵M的列序进行转置，即按三元组A的 第二个字段值（列下标）由小到大的顺序进行转置。 为了找到M中每一列中所有的非零元素，需要对其 三元组表a.data从第一行起整个扫描一遍，由于 a.data是以M的行序为主序来存放每个非零元素 的，对于M中具有相同列下标的非零元来讲，先扫 描到的非零元的行下标一定小于后扫描到的非零元 的行下标，由此得到的恰是b.data应有的顺序。
• 压缩的含义
– 为多个值相同的元素只分配一个存贮空间； – 零元素不分配或少分配存贮空间。
• 特殊矩阵：元素值相同或零元素分布有 一定规律的矩阵。 • 稀疏矩阵：元素值相同或零元素分布没 有规律的矩阵。 • 特殊矩阵的压缩存贮实际是将二维数组 的数据元素压缩到一维数组上。
特殊矩阵的压缩存储
特殊矩阵: 非零元在矩阵中的分布有一定规则
常用的稀疏矩阵的存储方法
三元组表示法 顺序存储 行逻辑联接的顺序表 带辅助行向量的二元组表示法 伪地址表示法 带行指针向量的单链表示法 链接存储 散列存储 行列表示法（十字链表） 多链表示法（正交表）
顺序存储
1、三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个 结点对应稀疏矩阵的一个非零元素。其中包括三个 域，分别为该元素的行下标、列下标和值。结点间 的先后顺序按矩阵的行优先顺序排列（跳过零元 素），将线性表用顺序的方法存储在连续的存储区 里。

国家开放大学《数据结构(本)》综合练习题参考答案

10.元素 111，113，115，117 按顺序依次进栈，则该栈的不可能输出序列是（ ） （进栈出栈可以交替进行）。
A. 111，113，115，117 B. 117，115，111，113 C. 117，115，113，111 D. 113，111，117，115 11.图状结构中数据元素的位置之间存在（ ）的关系。 A. 每一个元素都有一个且只有一个直接前驱和一个直接后继 B. 多对多 C. 一对一 D. 一对一 12.以下说法正确的是（ ）。 A. 栈和队列的特点都是后进后出 B. 队列的特点是先进后出 C. 栈的特点是先进先出 D. 栈的特点是先进后出 13.一个单链表中，在 p 所指结点之后插入一个 s 所指的结点时，可执行： s->next=p->next;和（ ）。 A. s=p->next; B. p=s->next;
国家开放大学《数据结构（本）》综合练习题参考答案
一、填空题 1.对稀疏矩阵进行压缩存储，可采用三元组表，一个有 10 行的稀疏矩阵 A 共有 97 个零元素，其相应的三元组表共有 3 个元素。该矩阵 A 有（10）列。 2.结构中的数据元素存在多对多的关系称为（图状）结构。 3.在单向链表中，q 指向 p 所指结点的直接后继结点，要删除 q 所指结点，可以 用操作（p->next;）= q->next;。 4.n 个元素进行冒泡法排序，第 j 趟冒泡要进行（n-j）次元素间的比较。 5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行 下标、列下标和（数组元素）三项信息。 6.中序遍历（二叉排序树）树可得到一个有序序列。 7.队列的操作特点是后进（后出）。 8.待排序的序列为 8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两 趟选择后，结果序列为（1，2，4，8，3，5，9）。 9.n 个元素进行冒泡法排序，通常需要进行（n-1）趟冒泡。 10.广义表（（a，b），d，e（（i，j），k））的长度是（4） 。 11.中序遍历二叉排序树可得到一个（有序）的序列。 12.广义表的（c，a，（a，b），d，e，（（i，j），k））深度是（3）。 13.广义表（c，a，（a，b），d，e，（（i，j），k））的长度是（6）。 14.对稀疏矩阵进行压缩存储，可采用三元组表，一个有 10 行 10 列的稀疏矩阵 A 共有 95 个零元素，其相应的三元组表共有（5）个元素。 15.广义表的（c，a，（a，b），d，e，（（i，j），k））深度是（3）。 16.在对一组记录（50，49，97，22，16，73，65，47，88）进行直接插入排序 时，当把第 7 个记录 65 插入到有序表时，为寻找插入位置需比较（3）次。 17. 循 环 队 列 在 规 定 少 用 一 个 存 储 空 间 的 情 况 下 ， 队 空 的 判 定 条 件 为 （front==rear）。 18.一棵有 5 个叶结点的哈夫曼树，该树中总共有（9）个结点。 19.c 语言中，字符串“E”存储时占（2）个字节。

2022年中南财经政法大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年中南财经政法大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.333、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、就平均性能而言，目前最好的内排序方法是（）排序法。

200721数据结构 作业(高起专、高起本)


比较（
）个元素结点。
A、
B、n
C、
D、
20、设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在），则需修改指针的操作
为（
）。
A、
B、
C、
D、
21、在（
）运算中，使用顺序表比链表好。
A、插入
B、删除
C、根据序号查找
D、根据元素值查找
22、在一个具有 n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度
第 2 页 共 20 页 在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
18、在一个长度为 n 的顺序表中删除第 i 个元素
时，需向前移动（
）个元素。
A、
B、
C、
D、i
19、从一个具有 n 个结点的单链表中查找其值等于 x 的结点时，在查找成功的情况下，需平均
（ ）个。
第 6 页 共 20 页 在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！
A、15
B、16
C、17
D、47
48、设 n , m 为一棵二叉树上的两个结点，在中序遍历序列中 n 在 m 前的条件是（ ）。
A、n 在 m 右方
B、n 在 m 左方
C、n 是 m 的祖先
D、求串长
6、二维数组 M 的成员是 6 个字符（每个字符占一个存储单元）组成的串，行下标 i 的
范围从 0 到 8，列下标 j 的范围从 1 到 10，则存放 M 至少需要（
）个字节。
A、90
B、180

c语言 广义表

c语言广义表C语言中没有内置的广义表数据结构，但可以通过结构体和指针来构建广义表。

广义表是一种含有嵌套元素的数据结构，可以包含原子元素和子表。

下面是一个示例代码，用于实现广义表的基本操作：```c#include <stdio.h>#include <stdlib.h>// 定义广义表的数据结构typedef struct GList {int tag;union {char atom;struct GList *sublist;} value;struct GList *next;} GList;// 创建广义表GList* createGList() {GList *list;char c;scanf("%c", &c);if (c == '#') {list = NULL;} else if (c == '(') {list = (GList *)malloc(sizeof(GList)); list->tag = 1;list->value.sublist = createGList(); list->next = createGList();} else {list = (GList *)malloc(sizeof(GList)); list->tag = 0;list->value.atom = c;list->next = createGList();}return list;}// 打印广义表void printGList(GList *list) {if (list == NULL) {printf("#");} else if (list->tag == 1) {printf("(");printGList(list->value.sublist);printf(")");printGList(list->next);} else {printf("%c", list->value.atom);printGList(list->next);}}// 主函数int main() {printf("请输入广义表：\n");GList *list = createGList();printf("广义表为：");printGList(list);printf("\n");return 0;}```这个示例代码实现了广义表的创建和打印功能。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

广义表在学稀疏矩阵之后就应该学的，只是那时觉得看起来晕晕就跳过了，现在回头学了一下，觉得还是不错的一种结构。

下面是代码:文件"glist.h"view plain1.#include<iostream>2.#include<string>ing namespace std;4.5.enum elemTag {ATOM,LIST};6.class GList;7.8.class GLnode9.{10.private:11. elemTag Tag; //标志是原子还是子表 0:原子 1:子表12.union13. {14.char data; //原子结点值域15.struct//表结点指针域16. {17. GLnode *hp;18. GLnode *tp;19. }ptr;20. };21.friend class GList;22.};23.24.class GList25.{26.public:27. string Decompose(string &str)28. {29.//将非空串str分割成2部分，hstr为第一个','之前的子串，str为后面的30.int n,i,k;31. string ch,hstr;32. n=str.length();33.for(i=0,k=-1;i<n && (ch!="," || k!=0) ;i++)34. {35.//搜索最外层第一个逗号36. ch=str.substr(i,1); //从第i个位置起读1个字符37.if(ch=="(")38. ++k;39.else if(ch==")")40. --k;41. }42.if(i<n)43. {44. hstr=str.substr(1,i-2);//不要左括号，不要逗号，所以是i-245. str="("+str.substr(i,n-i);46. }47.else48. {49. hstr=str.substr(1,n-2);50. str="";51. }52.return hstr;53. }54.55./*----------------------------------------------------56. /从广义表书写形式串S创建采用头尾链表存储表示的广义表T57. /建立广义表头尾结点存储结构的递归定义：58. /基本项：当S为空串时，置空广义表59. / 当S为单字符串时，建立原子结点的子表60. /递归项：假设sub为脱去S最外层括号的子串，记为"s1,s2,s3,..,sn"61. / 每个si为非空字符串，对每个si建立一个表结点62. /--------------------------------------------------------*/63.64.void Create_GList(GLnode *&GL,string S) //创建广义表65. {66. string hsub;67.if(S=="()") //S为空串68. {69. GL=NULL;70. }71.else72. {73.74. GL=new GLnode;75.if(S.length()==1)76. {77. GL->Tag=ATOM;78. GL->data=S[0];79. }80.else81. {82. GL->Tag=LIST;83. hsub=Decompose(S); //从S中分离出表头串hsub84. Create_GList(GL->ptr.hp,hsub);85.if(S.empty())86. {87. GL->ptr.tp=NULL;88. }89.else90. {91. Create_GList(GL->ptr.tp,S);92. }93. }94. }95. }96.97.int GList_Depth(GLnode *GL) //求广义表深度98. {99./*-----------------------------------------100. /当广义表为空表时，深度为1，当广义表为原子时101. /深度为0，当广义表为广义表时，深度的求法为102. /GList_Depth(GL)=1+max{GList_Depth(lsi)}103. /-----------------------------------------*/ 104.105.if(!GL)106.return 1;107.if(GL->Tag==ATOM)108.return 0;109.int dep,max;110. GLnode *p;111.for(max=0,p=GL;p;p=p->ptr.tp)112. {113. dep=GList_Depth(p->ptr.hp);114.if(dep>max)115. max=dep;116. }117.return 1+max;118. }119.120.void Copy_GList(GLnode *GL,GLnode *&T) //T复制GL 121. {122.//当表为空时，复制空表，否则先复制表头在复制表尾123.if(!GL)124. T=NULL;125.else126. {127. T=new GLnode;128. T->Tag=GL->Tag;129.if(GL->Tag==ATOM)130. T->data=GL->data;131.else132. {133. Copy_GList(GL->ptr.hp,T->ptr.hp); 134. Copy_GList(GL->ptr.tp,T->ptr.tp); 135. }136. }137. }138.139./*-----------------------------------------------140. /遍历广义表，如果是空表就输出"()"，如果遇到Tag=0 141. /的结点，则直接输出该结点的值，如果tag=1，说明142. /是一个子表，首先输出左括号，然后递归调用输出数据143. /元素，并当表尾不空的时候输出逗号，最后输出右括号144. /-----------------------------------------------*/ 145.void Traverse_GList(GLnode *L)146. {147.if(!L)148. cout<<"()";149.else150. {151.if(L->Tag==ATOM)152. cout<<L->data;153.else154. {155. GLnode *p=NULL;156. cout<<'(';157. p=L;158.while(p)159. {160. Traverse_GList(p->ptr.hp); 161. p=p->ptr.tp;162.if(p)163. cout<<',';164. }165. cout<<')';166. }167. }168. }169.170.void GetHead(GLnode *GL) //取表头171. {172.//取广义表第一个元素173. cout<<"广义表：";174. Traverse_GList(GL);175. cout<<endl;176.if(!GL || GL->Tag==0 )177. cout<<"原子和空表不能去表头"<<endl;178.else179. {180. GLnode *h=GL->ptr.hp;181.if(h->Tag==ATOM)182. cout<<"表头为："<<h->data<<endl;183.else184. {185. cout<<"表头为：";186. Traverse_GList(h);187. cout<<endl;188. }189. }190. }191.192.void GetTail(GLnode *GL) //取表尾193. {194.//广义表表尾指的是除了第一个元素后所有剩余的元素组成的表195. cout<<"广义表：";196. Traverse_GList(GL);197. cout<<endl;198.199.if(!GL || GL->Tag==0)200. cout<<"原子和空表不能取表尾"<<endl;201.else202. {203. GLnode *t;204. t=GL->ptr.tp;205. cout<<"表尾为：";206. Traverse_GList(t);207. cout<<endl;208. }209. }210.211.int Length_GList_1(GLnode *GL) //求表长，非递归212. {213.//用非递归方式求广义表长度214.int len=0;215.if(GL && GL->Tag==LIST)216. {217.while(GL)218. {219. GL=GL->ptr.tp;220. len++;221. }222.return len;223. }224.else225.return 0;226. }227.228.int Length_GList_2(GLnode *GL) //求表长，递归229. {230.if(!GL)231.return 0;232.return 1+Length_GList_2(GL->ptr.tp);233. }234.235.void Replace_GList(GLnode *p,char x,char y,GLnode *&q) //替换236. {237.//将广义表p中元素x替换成y，构建新广义表q238.if(!p)239. q=NULL;240.else241. {242.if(p->Tag==ATOM)243. {244. q=new GLnode;245. q->Tag=ATOM;246. q->ptr.hp=NULL;247.if(p->data==x)248. q->data=y;249.else250. q->data=p->data;251. }252.else253. {254. GLnode *h,*t;255. Replace_GList(p->ptr.hp,x,y,h);//递归处理表头得到h 256. Replace_GList(p->ptr.tp,x,y,t);//递归处理表尾得到t 257. q=new GLnode;258. q->Tag=LIST;259. q->ptr.hp=h;260. q->ptr.tp=t;261. }262. }263. }264.265.int Is_Same(GLnode *p,GLnode *q)//判断是否相等266. {267.int flag=1;//1表示相等，0表示不相等268.if(p && q)269. {270.if(p->Tag==ATOM && q->Tag==ATOM)271. {272.if(p->data!=q->data)273. flag=0;274.else275. flag=1;276. }277.else if(p->Tag==LIST &&q->Tag==LIST)278. flag=Is_Same(p->ptr.hp,q->ptr.hp);279.else280. flag=0;281.if(flag)282. flag=Is_Same(p->ptr.tp,q->ptr.tp);283. }284.else285. {286.if(p && !q)287. flag=0;288.if(!p && q)289. flag=0;290. }291.return flag;292. }293.void Concat_Glist(GLnode *&GL,GLnode *LG) //连接两个广义表294. {295. GLnode *p=GL;296. GLnode *q=p->ptr.tp;297.while(q->ptr.tp)298. q=q->ptr.tp;299. q->ptr.tp=LG;300. GL=p;301. }302.303.};测试函数"main.cpp"view plain1.#include"glist.h"2.3.int main()4.{5. GList list;6. GLnode *GL=NULL;7. string S;8. cout<<"输入广义表S：";9. cin>>S;10. list.Create_GList(GL,S);11. cout<<"广义表S的深度为："<<list.GList_Depth(GL)<<endl;12. cout<<"广义表S的长度为："<<list.Length_GList_1(GL)<<endl;13. cout<<"广义表S的长度为："<<list.Length_GList_2(GL)<<endl;14.15. list.GetHead(GL);16. list.GetTail(GL);17.18. GLnode *T;19. cout<<"复制广义表"<<endl;20. list.Copy_GList(GL,T);21. cout<<"遍历复制后的广义表T"<<endl;22. list.Traverse_GList(T);23. cout<<endl;24.25. string F;26. cout<<"输入广义表F：";27. cin>>F;28. GList list1;29. GLnode *LG;30. list1.Create_GList(LG,F);31.if(list.Is_Same(GL,LG))32. cout<<"广义表S和F相等"<<endl;33.else34. cout<<"广义表S和F不相等"<<endl;35.36. cout<<"广义表F的长度为："<<list1.Length_GList_2(LG)<<endl;37.38.char x,y;39. cout<<"输入你要替换的字符: ";40. cin>>x;41. cout<<endl;42. cout<<"输入你要替换成哪个字符：";43. cin>>y;44. GLnode *k;45. list1.Replace_GList(LG,x,y,k);46. cout<<"替换后的广义表为：";47. list1.Traverse_GList(k);48. cout<<endl;49.50. cout<<"连接广义表S与被替换字符后的广义表F的表为：";51. list.Concat_Glist(GL,k);52. list.Traverse_GList(GL);53. cout<<endl;54.55.return 0;56.}下面是输出结果view plain1.输入广义表S：((a,b),(c,d))2.广义表S的深度为：23.广义表S的长度为：24.广义表S的长度为：25.广义表：((a,b),(c,d))6.表头为：(a,b)7.广义表：((a,b),(c,d))8.表尾为：((c,d))9.复制广义表10.遍历复制后的广义表T11.((a,b),(c,d))12.输入广义表F：(f,(g,h),(i,i))13.广义表S和F不相等14.广义表F的长度为：315.输入你要替换的字符: i16.17.输入你要替换成哪个字符：x18.替换后的广义表为：(f,(g,h),(x,x))19.连接广义表S与被替换字符后的广义表F的表为：((a,b),(c,d),f,(g,h),(x,x))20.Press any key to continue。