1、- 1 - 数据结构 课程设计报告 题 目 广义表运算的验算设计 学 号 姓 名 班 级 06 级计算机教育班 专 业 学 院 指导教师 完成日期 I 目目 录录 广义表运算的验证 1 一、需求分析 1 二、概要设计 1 三、详细设计 3 四、测试与分析 6 五、源程序清单 7 结 论 12 参考文献. 错误错误! !未定义书签。未定义书签。 课程设计指导教师评语. 13 1 广义表运算的验证广义表运算的验证 一、一、 需求分析需求分析 广义表是 n(n0)个元素 a1,a2,an 的有限序列，其中 an 或者是原子，或者 是一个广义表。通常记作 LS=（a1,a2,an） 。LS 是广义表的
2、名字，n 为它的长 度。若 ai 是广义表，则称它为 LS 的子表。 一般用圆括号将广义表括起来，用逗号恰分隔其中的元素。为了区分原子和广义 表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表 LS 非空（n 1),则 a1 是 LS 的表头，其余元素组成的表 a2,an 称为 LS 的表尾。一个表 展开后所含括号的层数称为广义表的深度。 11 广义表有许多运算，其基本运算有：建立广义表、打印广义表、复制等等。 由于广义表是一种递归的数据结构，所以实现广义表的运算一般采用递归算法。 12 基本要求 (1) 输入的形式和输入值的范围：在程序的运行界面，接受键盘的直接输入，输 入值的范围
3、是英文大小字母、数字和各种运算符号。 (2) 输出的形式：当输入一个广义表之后例如输入(3,4),(4,5)则依次会输出”广义 表:(3,4),(4,5);count :4;sum:16;depth:2;copy after: (3,4),(4,5)然后选择是输出 表头还是表尾如果选择表头则会输出(3,4)如果是选择表尾则会输出(4,5)。” (3) 程序主要功能：本程序主要是用单链表实现广义表的建立、输出广义表、广 义表的复制，并求出广义表的表头、广义表的表尾、广义表的深度、广义表原子 结点个数、广义表原子结点数据域之和 。 二、二、概要设计概要设计 1、 数据结构：用 struct 定义一
4、个结构类型的数据作为广义表的类型，且在结构 体中定义一个 union 共用型的数据， 并且在其中定义一个指向子表结点的结构体 指针，另外也 struct 中定义指向下一个表结点的结构体的指针 。 2、 程序模块： 1） 、广义表的建立 creat_GL(s)：首先提示用用户输入广义表的字符串，要求构 成广义表的合法字符为：大写或小写字母、空格字符、圆括号和逗号，并且设广 义表的原子为单个字母。 2） 、输出广义表 prn_GL(p)：对给定存储结构的广义表，打印输出其表示格式。 3） 、广义表的复制 copy_GL(p)：对已知的广义表复制输出另外一个与已知表一 2 模一样的广义表。 4） 、
5、求广义表深度 depth(p)：求一个表展开后所含括号的层数，它是广义表的一 种度量。 5） 、求广义表原子结点个数 count(p)：求出一个广义表中所有的原子结点个数。 6） 、求广义表原子结点数据域之和 sum(p)：求出一个广义表中所有原子结点的 数据域的和。 7） 、求出广义表的表头 head(p)：按照广义表表头的定义，编写求表头的算法。 8） 、求出广义表的表尾 tail(p)：按照广义表表尾的定义，编写求表尾的算法。 3、各模块之间的调用关系以及算法设计 create_GL(),copy_GL(),tail(),head()都是返回一个指针，通过调用 prn_GL()来实现最后
6、的输出。count()，sum(),depth()这三个函数因为最后返回 都是整型的数据，所以是可以通过 printf 语句来完成对它们的输出操作. 主要的功能都是利用递归调用来实现的 。 4、主程序的流程 首先用定义四个 NODE 类型的指针，并定义一个字符数组和一个字符型的指针 并提示用户输入广义表，然后调用 creat_GL()函数来创建再调用 prn_GL()函数 来输出，然后调用 count() sum ()和 depth()函数并用三条 printf 命令来输出其结 果；然后调用 copy_GL()函数来实现复制输入的广义表，并利用 prn_GL()来实 现对其的输出；最后是利用一个 swith()让用户选择是输头还是表尾，再分别调 用 tail()和 head()这两个函数，然后再一次利用 prn_GL()便可。实现具体代码如 下： void main() N
