1、 数据结构课程设计报告数据结构课程设计报告 广义表的存储与运算广义表的存储与运算 广义表广义表 班 级： 软件 112 班 姓 名： 指导教师： 成 绩： 1 目录目录 需求分析 3 题目 . 3 要求 . 3 对题目分析 3 数据的输入输出 . 3 算法测试设计用例 . 4 概要设计 4 各抽象数据类型的定义 4 广义表的扩展线性链表表示. 4 广义表的图形表示 . 5 带表头结点的链式存储 5 广义表的运算问题流程图 5 详细设计 8 1. 功能目录 . 8 2. 主函数 . 9 3. 字符串变广义表 10 4. 广义表的复制 11 5. 广义表的输出 12 6. 广义表的长度 12 7.
2、 广义表的深度 13 8. 广义表的表头 13 9. 广义表的表尾 14 10. 广义表变为字符串 . 14 11. 查找广义表中的字符 . 15 调试分析 15 测试结果 15 1. 字符串变广义表 16 2. 广义表的复制 16 3. 广义表的长度 17 4. 广义表的深度 17 5. 广义表的表头 18 2 6. 广义表的表尾 18 7. 广义表变为字符串. 19 8. 查找广义表中的字符 . 19 9. 重新设定广义表 20 参考文献 21 3 需求分析需求分析 题目题目 选选择合适的存储结构表示广义表 要求要求 (1)用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功
3、 能。 (2)取广义表 L 的表头和表尾的函数 head(L)和 tail(L)。 (3)能用这两个函数的复合形式求出广义表中的指定元素。 (4)由广义表的字符串形式到广义表的转换函数 StrTo-Lists(S)：Lists，例如 StrTo-Lists(a，(a，b)，c)的值为一个广义表。 (5)由广义表到广义表的字符串形式的转换函数 Lists-To-Str(L)：String。 (6)最好能设置多个广义表。 对题目分析对题目分析 本题主要考察广义表的应用，所以之前先要对广义表要有一定的了解。线性 表被定义为一个有限的序列（a1，a2，a3，an）其中 ai 被限定为是单个数据元素。广
4、 义表也是 n 个数据元素 d1，d2，d3，dn 的有限序列，但不同的是，广义表中的 di 则 既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，dn） 。GL 是广义表的名字，通常广义表的名字用大写字母表示。n 是广义表的长度。若其中 di 是一 个广义表，则称 di 是广义表 GL 的子表。在广义表 GL 中，d1 是广义表 GL 的表头，而广 义表 GL 其余部分组成的表（d2，d3，dn）称为广义表的表尾。由此可见广义表的定 义是递归定义的。因为在定义广义表时，又使用了广义表的概念。线性表被定义为一个有 限的序列（a1，a2，a3，an）其中 ai 被限定为是
5、单个数据元素。广义表也是 n 个数据 元素 d1，d2，d3，dn 的有限序列，但不同的是，广义表中的 di 则既可以是单个元素， 还可以是一个广义表，通常记作：GL=（d1，d2，d3，dn） 。GL 是广义表的名字，通 常广义表的名字用大写字母表示。n 是广义表的长度。若其中 di 是一个广义表，则称 di 是 广义表 GL 的子表。在广义表 GL 中，d1 是广义表 GL 的表头，而广义表 GL 其余部分组成 的表（d2，d3，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为 在定义广义表时，又使用了广义表的概念。 数据的输入输出数据的输入输出 输入：数据要求输入一个广义表
6、 例如： （ （a,b）,c,(d,e)） （(1,2,3）,4） 4 输出：输出 9 种有关广义表的操作如下： 1 字符串变广义表 2 广义表的复制 3 广义表的长度 4 广义表的深度 5 广义表的表头 6 广义表的表尾 7 广义表变为字符串 8 查找广义表中的字符 9 重新设定广义表 0 推出程序 算法测试设计用例算法测试设计用例 （ （a,b）,c,(d,e)） 概要设计概要设计 各抽象数据类型的定义各抽象数据类型的定义 GList：广义表的类型定义 GList *StrToLists(char * / tag 为公共部分，只能为 1 和 0，1 代表 /表结点，0 代表原子结点 union / 原子结点和表结点的联合部分 ElemType data; / 原子结点的值域 struct GLNode *ph; / 表结点的表头的表头指针
