refresh是什么意思广义表的运算解读

2021年1月19日发(作者：莫利纳)









黄伟华

《广义表的运算》


































第１页

共
22
页




广义表的运算



学生姓名：黄伟华










指导老师：肖增良


摘


要


这次的课程设计主要是广义表的运算，要求实现广义表的建立、查找、输出、取
表尾 、以及求深度、求逆表等。通过对广义表的运算的掌握，达到更好地理解与运用所学
知识，提高动手能力 的目的。在本课程设计中，系统开发平台为
Windows2000
,
程序设计
语言为
C
语言，程序运行平台为
Windws
98/2000/XP。在程序设计中采用了结构体及栈的
逻辑结构、存储结构，掌握线性表及栈上基本运算的实现。程序 通过调试运行，初步实现
了设计目标，并且经过适当完善后，将可以应用在实际中解决问题。



关键词


堆栈，递归，结点，广义表。



























黄伟华

《广义表的运算》


































第２页

共
22
页



1
引


言

广义表是一种非线性的数据结构，顾名思义，它也是线性表的一种推广 。它被广泛的
应用于人工智能等领域的表处理语言
LISP
语言中。在
LIS P
语言中，广义表是一种最基本
的数据结构。

线性表被定义为一个有限的序 列（
a1
，
a2
，
a3
，
…
，
a n
）其中
ai
被限定为是单个
数据元素。广义表也是
n
个数 据元素
d1
，
d2
，
d3
，
…
，
dn
的有限序列，但不同的是，
广义表中的
di
则既可以是单个元素，还可 以是一个广义表，通常记作：
GL=
（
d1
，
d2
，
d3
，
…
，
dn
）
。
GL
是广义表的名 字，通常广义表的名字用大写字母表示。
n
是广
义表的长度。若其中
di是一个广义表，则称
di
是广义表
GL
的子表。在广义表
GL< br>中，
d1
是广义表
GL
的表头，而广义表
GL
其余部 分组成的表（
d2
，
d3
，
…
，
dn
）称
为广义表的表尾。

1.1
课题背景

当今世界已进入信 息时代，随着计算机科学与技术的迅猛发展，计算机应用已深入到
科研、管理和生产的各个领域，尤其在 企业与经济部门的管理工作中发挥着巨大作用。数
据结构是实现计算机应用的重要基础和有效手段。20
世纪
80
年代，计算技术开始渗透到
大多数学科领域。计算技术的日 新月异，促进着时代的发展，任何一个领域，无不依赖着
计算机的强大的各种功能与计算能力。从计算机 对整个世界的影响来看，学好这门科学显
得无比的重要。学习好《数据结构》课程，却又是学习好计算机 科学与技术的基础，掌握
各种数据的存储结构，就能设计不同的数据结构，为不同领域的需求提供服务， 达到市场
需求。
。

1.2
课程设计目的

本次 课程设计的实验目的是通过该实验掌握较复杂程序的设计。掌握广义表的一些基
本操作，同时对结构体和 堆栈的操作进行复习和实践，充分认识理论知识对应用技术的指
导性作用，进一步加强理论知识与应用相 结合的实践和锻炼。使自己的设计水平和对所学
的知识的应用能力以及分析问题解决问题的能力得到全面 提高。同时，巩固和深化自身的
理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的学 习习惯，提高综
合运用所学的理论知识和方法独立分析和解决问题的能力。













黄伟华

《广义表的运算》


































第３页

共
22
页



1.3
课程设计内容

本课程设计是实现广义表的相关操作，
包括实 现广义表的建立、
查找、
输出、
取表尾、
以及求深度、求逆表等，其框架图如 下图
1.3.1
所示：

广义表的运算

建
立
广
义
表


遍
历
广
义
表

广
义
表
的
查找

求
广
义
表
的
深
度

求
广
义
表
的
表
尾

求
广
义
表
的
逆
表


图
1.3.1
广义表的运算框架图


























黄伟华

《广义表的运算》


































第４页

共
22
页



2
设计思路与方案


2.1
设计思路

1
、建立广义表
CreateGL(char
*&s)
。在生成广 义表之前，用一个数组存储广义表，并用指
针
s
指向数组，通过数组中的元素生成广义 表。基本思想是：在广义表表达式中，遇到左括
号”
(
”时递归构造子表，否则构造原 子结点；遇到逗号时递归构造后续广义表，直到字符
串数组结束，以

作为结束标志。实 现过程如下：

GList *CreateGL(char *&s)


{






读入广义表的一个字符给
ch
；

if (ch!=
空格
')
{
if (ch=='(')
{



递归构造子表；

}

else if (ch==')')



遇到
')'
字符
,
子表为空











else

{



构造原子结点；


}
}
else

串结束
,
子表为空

读入广义表的一个字符给
ch
；


if (ch==',')


递归构造后续子表；





else




处理表的最后一个元素



返回广义表指针

}
2
、遍历广义表
DispGL(GList *g)
。输出广义表采用的算法 思想是：若遇到
tag=1
的结点，
这是一个子表的开始，
先打印输出一个左 括号”
(
”。
如果该子表为空，
则输出一个空格符；
否则递归调用输 出该子表。子表打印输出完后，再打印一个右括号”
)
”。若遇到
tag=0
的
结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇
到
tp=NULL
。其实现过程如下：











黄伟华

《广义表的运算》


































第５页

共
22
页



void DispGL(GList *g)


{

if (g!=NULL)


{


if (g->tag==1)




















{





输出左括号
'('
；

if (g->==NULL)


输出一个空格；

else


递归调用子表；

}
else

输出数据域；

if (g->tag==1)



打印有括号“）
”
；



if (g->tp!=NULL)



输出逗号“，
”
，递归调用输出下一个结点。


}
}
3
、广义表的查找：
FindGListX()
在给定的广义 表种查找数据域为
x
的结点，
采用的算法思想是：
若遇到
tag=0
的原子结
点，如果是要查找的结点，则查找成功
1
；否则，若还有后续元素， 则递归调用本过程在孩
子表中查找，
若还有后续元素，
则递归调用本过程查找后续每个 元素，
直到遇到
hp
域为
NULL
的元素。

设置
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)










黄伟华

《广义表的运算》


































第６页

共
22
页



一个广 义表的表尾指的是除去该广义表的第一个元素剩下的部分。求表尾实现过程如
下：

GList *tail(GList *g)
{

if (g==NULL)









}



{

空表不能求表尾；

}
else if (g->tag==0)
{

原子不能求表尾；

}
将广义表除去第一个元素， 其余的元素复制的广义表
q
中，既为该广义表的表尾。

return q;
5.
求广义表的深度
GLDepth(GList *g)
。
广义表的深度的递归定义是它等于所有子表中表的最大深度加
1
，
若一个表为空或 仅由
单个元素所组成，则深度为
1
。求广义表深度的递归函数
GLDepth
（）如

1































若
h
为空表





GLDepth
（）


实现过程如下：

max{GLDepth(sh)|sh
为
h
的子表
}+1

其他情况


int GLDepth(GList *g)
{














if (g->tag==0)

g=g->;

if (g==NULL)






为原子时返回；


为空表时返回
1
；

while (g!=NULL)
{







if (g->tag==1)
{



}
递归调用求出子表的深度；

if (dep>max)

max
为同一层所求过的子表中深度的最大值；


使
g
指向下一个元素；










黄伟华

《广义表的运算》


































第７页

共
22
页





}
}
返回表的深度
(max+1)
。

6
、求广义表的逆表
NIGList(GList *g,SeqStack *s)
求广义表的逆表的算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，
然后在将栈 中所有的元素出栈打印，函数的实现如下：

将广义表中的元素存入堆栈中：

void NIGList(GList *g,SeqStack *s)
{
















}
将栈中所有元素输出：

void Pop(SeqStack *s)
{
打印栈中元素。

}
if(g!=NULL)
{












}
if (g->tag==1)

{



}
else

将广义表中的元素存入栈中；

if (g->tag==1)
if (g->tp!=NULL)


将广义表中的

存入栈中；


递归将后续表的内容存入栈中。

将广义表中的“
(
”以“
)
”存入栈中；

else


递归调用，将子表中的元素存入栈中；






将广义表中的

以

存入栈中；

2.2
数据结构设计

1
、广义表的存储结构：

由于广义表中的元素本身又可以具有结构，
是一种带有层次的非线性结构，
因此难以用
顺序存储的结构表示。
通常采用链式存储结构，
每个元素可用一个结点表示原子结点结构如下图
2.2.1
、
2.2.2
所示：











黄伟华

《广义表的运算》


































第８页

共
22
页






图
2.2.1
原子结点的存储结构

tag=0
atom


tag=1
*hp
*tp


图
2.2.2
表结点的存储结构


其中
tag< br>是一个标志位，
用来区分当前结点是原子结点还是子表。
当
tag
为< br>1
时，
该结
点是子表，第二个域为
hp
，用以存放子表的地址 ；当
tag
为
0
时，该结点是原子结点，第
二个域为
ato m
，用以存放元素值。
tp
域是用来存放与本元素同一层的下一个元素对应结点
的地址，当该元素是所在层的最后一个元素时，
tp
的值为
NULL
。广义 表及结点类型描述如
下：

typedef char ElemType;
typedef struct GLode







{
int tag;
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;

}
}













黄伟华

《广义表的运算》


































第９页

共
22
页



3
详细实现

首先要将输入的用数组存储的广义表转化 成以广义表的存储结构存储的广义表，这个
过程也就是生成广义表。

查找广义表，查 找广义表要返回一个值
mark
，当
mark=1
时，程序查找到待查的元素 ，
当
mark=0
时，程序没有找到待查元素。

输出广义表，遍历 广义表，输出广义表的遍历结果；取表尾，将广义表从第二个元素
开始复制到另一个广义表中；求广义表 的深度，遍历每一层广义表，将广义表内每层广义
表深度最大的广义表相加为同一层所求过的子表中深度 的最大值；求逆表，将广义表逆向
输出。

3.1
输入广义表

模块简介，流程图，代码

3.2










黄伟华

《广义表的运算》


































第１０页

共
22
页



流程图如下图所示：

开始

建立一个用字符数组存储的
广义表，
用字符指针
s
指向它。

输入广义表

生成数组广义表结构

遍历广义表

建立堆栈

Case:1
查
找
待
查元素，
mark=1
，
找
到
待
查元素，
反之，没
有查到 。

Case:2
求
广
义
表
的
表
尾，并输
出

Case:3
求
广
义
表
的
深
度，并输
出

Case:4
Case:0
求
广
义
清屏

表
的
逆
输出“再
表，并输
见”

出

输出

结束

广义表运算流程图













黄伟华

《广义表的运算》


































第１１页

共
22
页



4
运行环境与结果


4.1
运行环境

本课程设计中，系统开发平台为
Windows XP
,
程序设计语言为
Visual C++6.0
，程
序的运行环境为
Visual C++ 6.0
。
Visual C++
一般分为三个版本
:
学习版、专业版 和企
业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一
种，在 本课程设计中，以
Visual C++ 6.0
为编程环境。

Microsoft Visual C++ 6.0
是
Microsoft
公司的
Microsoft Visual Studio 6.0
开发工具箱中
的一个
C++
程序开发包。
Visual C++
包中除包括
C++
编译器外，还包括所有的库、例
子和为创建Windows
应用程序所需要的文档。自
1993
年
Microsof t
公司推出
Visual
C++1.0
后，随着其新版本的不断问世，
Visual C++
已成为专业程序员进行软件开发的
首选工具。

Visual C++
从最早期的
1.0
版本，发展到最新的
7.0
版本，
Vis ual C++
已经
有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0
版本在编
译器、
MFC
类库、编辑器以及联机帮助系统等方面都比 以前的版本做了较大改进。

虽然微软公司推出了
Visual
C++.NET(Visual
C++7.0)
，但它的应用的很大的局限
性，只适用于
Windows 2000,Windows XP
和
Windows NT4.0
。所以实际中，更多的是
以
Visual C++6.0
为平台。

Visual C++ 6.0
是
Micr osoft
公司推出的目前使用最广泛的基于
Windows
平台的可
视化编 程环境。
Visual C++ 6.0
是在以往版本不断更新的基础上形成的，
由于 其功能强
大，灵活性好，完全课扩展以及具有强大的
Internet
支持，因而在各 种
C++
语言开发
工具中脱颖而出，成为目前最为流行的
C++
语言 集成开发环境。

Visual C++ 6.0
秉承
Visual C++
以前版本的优异特性，
为用户提供了一套良好的可视化
开发环境：
主要包括文 本编辑器、
资源编辑器、
工程创建工具、
Debugger
调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链
接、运行、调试 应用程序。