定然-章程英文
题目：广义表的运算
摘
要
：
这次的课程设计主要是广义表的运算，要求实现 广义表的建立、查找、输出、
取表尾、以及求深度、求逆表等。通过对广义表的运算的掌握，达到更好地 理解与运用所
学知识，提高动手能力的目的。在本课程设计中，系统开发平台为
Windows 2000
,
程序设
计语言为
C
语言，程序运行平台为
Win dws
98/2000/XP
。在程序设计中采用了结构体及栈
的逻辑结构、存储结 构，掌握线性表及栈上基本运算的实现。程序通过调试运行，初步实
现了设计目标，并且经过适当完善后 ，将可以应用在实际中解决问题。
关键词
：
堆栈，递归，结点，广义表。
１
共
21
页
第１页
一
.
引
言
广义表是一种非线性的数据结构，是线性表的一 种推广。它被广泛的应用于人工智能
等领域的表处理语言
LISP
语言中。在
LISP
语言中，广义表是一种最基本的数据结构。
线性表被定义为一个
n >=0
个元素的有限的序列。线性表的元素仅限于原子项。
原子是结构上不可分割的成分，它可以是一个数或一个结构。
若放松对表元素的这种
限制，容许它们具有其自身结构，这样 就产生了广义表的概念。
广义表是
n(n>=0)
个元素
a1，
a2
，
a3
，
…
，
an
的有序数列 ，其中
ai
或者原子，
或者一个广义表。通常记作
GL=
（
a1
，
a2
，
a3
，
…
，
an
）
。
GL
是广义表的名字，
n
为
它的长度。若
ai< br>是广义表，则通常称它为
GL
的子表。为了区分原子和广义表，书
写时用大写字 母表示广义表，用小写字母表示原子。若广义表
GL
非空（
n>=1
）
，则
a1
是
GL
的表头，而广义表
GL
其余部分组成的表 （
a2
，
a3
，
…
，
an
）称为广义表的
表尾。
1.1
课题背景
当今世界已进入信 息时代，随着计算机科学与技术的迅猛发展，计算机应用已深入到
科研、管理和生产的各个领域，尤其在 企业与经济部门的管理工作中发挥着巨大作用。数
据结构是实现计算机应用的重要基础和有效手段。20
世纪
80
年代，计算技术开始渗透到
大多数学科领域。计算技术的日 新月异，促进着时代的发展，任何一个领域，无不依赖着
计算机的强大的各种功能与计算能力。从计算机 对整个世界的影响来看，学好这门科学显
得无比的重要。学习好《数据结构》课程，却又是学习好计算机 科学与技术的基础，掌握
各种数据的存储结构，就能设计不同的数据结构，为不同领域的需求提供服务， 达到市场
需求。
1.2
课程设计目的
本次 课程设计的实验目的是通过该实验掌握较复杂程序的设计。掌握广义表的一些基
本操作，同时对结构体和 堆栈的操作进行复习和实践，充分认识理论知识对应用技术的指
导性作用，进一步加强理论知识与应用相 结合的实践和锻炼。使自己的设计水平和对所学
的知识的应用能力以及分析问题解决问题的能力得到全面 提高。同时，巩固和深化自身的
理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的学 习习惯，提高综
合运用所学的理论知识和方法独立分析和解决问题的能力。
２
共
21
页
第２页
1.3
课程设计内容
本课程设计是实 现广义表的相关操作，
包括实现广义表的建立、
查找、
输出、
取表尾、
以及求深度、求逆表等，其框架图如下图
1.3.1
所示：
广义表的运算
建
立
广
义
表
遍
历
广
义
表
广
义
表
的
查找
求
广
义
表
的
深
度
求
广
义
表
的
表
尾
求
广
义
表
的
逆
表
图
1.3.1
广义表的运算框架图
二．设计思路与方案
2.1
设计思路
1
、建立广义表
CreateGL(char
*&s)
。在生成广 义表之前，用一个数组存储广义表，并用指
针
s
指向数组，通过数组中的元素生成广义 表。基本思想是：在广义表表达式中，遇到左括
号”
(
”时递归构造子表，否则构造原 子结点；遇到逗号时递归构造后续广义表，直到字符
串数组结束，以
作为结束标志。实 现过程如下：
GList *CreateGL(char *&s)
{
读入广义表的一个字符给
ch
；
if (ch!=
空格
')
{
建立一个新节点；
if (ch=='(')
{
递归构造子表；
}
else if (ch==')')
３
共
21
页
第３页
遇到
')'
字符
,
子表为空
else
{
构造原子结点；
}
}
else
串结束
,
子表为空
读入广义表的一个字符给
ch
；
if (ch==',')
递归构造后续子表；
else
处理表的最后一个元素
返回广义表指针
}
2
、遍历广义表
DispGL(GList *g)
。输出广义表采用的算法 思想是：若遇到
tag=1
的结点，
这是一个子表的开始，
先打印输出一个左 括号”
(
”。
如果该子表为空，
则输出一个空格符；
否则递归调用输 出该子表。子表打印输出完后，再打印一个右括号”
)
”。若遇到
tag=0
的
结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇
到
tp=NULL
。其实现过程如下：
void DispGL(GList *g)
{
}
if (g!=NULL)
{
if (g->tag==1)
{
输出左括号
'('
；
if (g->==NULL)
输出一个空格；
else
递归调用子表；
}
}
else
输出数据域；
if (g->tag==1)
打印有括号“）
”
；
if (g->tp!=NULL)
输出逗号“，
”
，递归调用输出下一个结点。
４
共
21
页
第４页
3
、广义表的查找：
FindGListX()
在给定的广义表 种查找数据域为
x
的结点，
采用的算法思想是：
若遇到
tag=0< br>的原子结
点，如果是要查找的结点，则查找成功
1
；否则，若还有后续元素，则 递归调用本过程在孩
子表中查找，
若还有后续元素，
则递归调用本过程查找后续每个元 素，
直到遇到
hp
域为
NULL
的元素。
设置< br>mark
标志查找结果；
mark=1
；表示查找成功，否则查找失败。
本函数实现过程如下：
FindGListX(GList *g,char x,int &mark)
{
if(g!=NULL){
if (g->tag == 0 && g-> ==x)
{
查找成功
mark = 1;
}
else
if(g->tag == 1)
递归调用查找后续元素；
递归查找调用后续元素；
}
}
4
、求广义表的表尾：
tail(GList *s)
一个广义表的表尾指的是除去该广义表的第一个元素剩下的部分。求表尾实现过程如
下 ：
GList *tail(GList *g)
{
if (g==NULL)
{
空表不能求表尾；
}
else if (g->tag==0)
{
原子不能求表尾；
}
将广义表除去第一个元素，其余的元素复 制的广义表
q
中，既为该广义表的表尾。
return q;
}
5.
求广义表的深度
GLDepth(GList *g)
。
广义表的深度的递归定义是它等于所有子表中表的最大深度加
1< br>，
若一个表为空或仅由
单个元素所组成，则深度为
1
。求广义表深度的 递归函数
GLDepth
（）如
５
共
21
页
第５页
1
若
h
为空表
GLDepth
（）
实现过程如下：
max{GLDepth(sh)|sh
为
h
的子表
}+1
其他情况
int GLDepth(GList *g)
{
}
6
、求广义表的逆表
NIGList(GList *g,SeqStack *s)
求广义表的逆表的算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，
然后在将栈 中所有的元素出栈打印，函数的实现如下：
将广义表中的元素存入堆栈中：
void NIGList(GList *g,SeqStack *s)
{
if(g!=NULL)
{
if (g->tag==1)
{
将广义表中的“
(
”以“
)
”存入栈中；
else
递归调用，将子表中的元素存入栈中；
if (g->tag==0)
g=g->;
if (g==NULL)
为原子时返回；
为空表时返回
1
；
while (g!=NULL)
{
}
返回表的深度
(max+1)
。
if (g->tag==1)
{
}
递归调用求出子表的深度；
if (dep>max)
max
为同一层所求过的子表中深度的最大值；
使
g
指向下一个元素；
６
共
21
页
第６页
}
}
}
else
将广义表中的元素存入栈中；
if (g->tag==1)
if (g->tp!=NULL)
将广义表中的
存入栈中；
递归将后续表的内容存入栈中。
将广义表中的
以
存入栈中；
将栈中所有元素输出：
void Pop(SeqStack *s)
{
打印栈中元素。
}
2.2
数据结构设计
1
、广义表的存储结构：
由于广义表中的元素本身又可以具有结构，
是一种带有层次的非线性结构，
因此难以用
顺序存储的结构表示。
通常采用链式存储结构，
每个元素可用一个结点表示原子结点结构如下图
2.2.1
、
2.2.2
所示：
图
2.2.1
原子结点的存储结构
tag=0
atom
tag=1
*hp
*tp
图
2.2.2
表结点的存储结构
其中
tag
是一 个标志位，
用来区分当前结点是原子结点还是子表。
当
tag
为
1< br>时，
该结
点是子表，第二个域为
hp
，用以存放子表的地址；当
tag
为
0
时，该结点是原子结点，第
二个域为
atom
，用以存放元素值。
tp
域是用来存放与本元素同一层的下一个元素对应结点
的地址， 当该元素是所在层的最后一个元素时，
tp
的值为
NULL
。广义表及结点类 型描述如
下：
typedef char ElemType;
typedef struct GLode
{
int tag;
７
共
21
页
第７页
union
{
ElemType atom;
struct GLode *hp;
} val;
struct GLode *tp;
} GList;
2
、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下：
typedef char ElemType;
typedef struct
{
ElemType data[maxlen]
int top;
}SeqStack;
else
{
return 0;
}
}
三．程序实现
首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个
过程也就是生成广义 表。
查找广义表，查找广义表要返回一个值
mark
，当
mark =1
时，程序查找到待查的元素，
当
mark=0
时，程序没有找到待查元素 。
输出广义表，遍历广义表，输出广义表的遍历结果；取表尾，将广义表从第二个元素
开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义
表深度最大的 广义表相加为同一层所求过的子表中深度的最大值；求逆表，将广义表逆向
输出。
８
共
21
页
第８页
3.1
源程序代码
#include
#include
#include
#define maxlen 100
typedef char ElemType;
typedef struct GLode//
广义表结构体的定义
{
int tag;
union
{
ElemType atom;
struct GLode *hp;
} val;
struct GLode *tp;
} GList;
typedef struct //
栈结构的定义
{
ElemType data[maxlen]
int top;
}SeqStack;
//
生成广义表
GList *CreateGL(char *&s)
{
GList *h;
char ch;
ch=*s;
s++;
if (ch!='0')
{
h=(GList *)malloc(sizeof(GList));
if (ch=='(')
{
h->tag=1;
h->=CreateGL(s);
}
else if (ch==')')
h=NULL;
else
{
h->tag=0;
h->=ch;
}
９
共
21
页
第９页
}
else
h=NULL;
ch=*s;
s++;
if (h!=NULL)
if (ch==',')
h->tp=CreateGL(s);
else
h->tp=NULL;
return h;
}
//
遍历广义表
void DispGL(GList *g)
{
if (g!=NULL)
{
if (g->tag==1)
{
printf(
if (g->==NULL)
printf(
else
DispGL(g->);
}
else
printf(
if (g->tag==1)
printf(
if (g->tp!=NULL)
{
printf(
DispGL(g->tp);
}
}
}
//
求广义表的深度
int GLDepth(GList *g)
{
int max=0,dep;
if (g->tag==0)
return 0;
g=g->;
if
(g==NULL)
１０
共
21
页
第１０页
定然-章程英文
定然-章程英文
定然-章程英文
定然-章程英文
定然-章程英文
定然-章程英文
定然-章程英文
定然-章程英文
本文更新与2021-01-19 23:10，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/535282.html