课程设计报告--广义表

《课程设计报告--广义表》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计报告广义表的存储与运算——广义表班级：软件112班姓名：邱日龙指导教师：兰红成绩：信息工程学院2012年12月31日27目录需求分析3题目3要求3对题目分析3数据的输入输出3算法测试设计用例4概要设计4各抽象数据类型的定义4广义表的扩展线性链表表示4广义表的图形表示5带表头结点的链式存储5广义表的运算问题流程图5详细设计81.功能目录82.主函数93.字符串变广义表104.广义表的复制115.广义表的输出126.广义表的长度127.广义表的深度138.广义表的表头139.广义表的表尾1410.广义表变

2、为字符串1411.查找广义表中的字符15调试分析15测试结果151.字符串变广义表162.广义表的复制163.广义表的长度174.广义表的深度175.广义表的表头18276.广义表的表尾187.广义表变为字符串198.查找广义表中的字符199.重新设定广义表20参考文献2127需求分析题目选择合适的存储结构表示广义表要求(1)用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。(2)取广义表L的表头和表尾的函数head(L)和tail(L)。(3)能用这两个函数的复合形式求出广义表中的指定元素。(4

3、)由广义表的字符串形式到广义表的转换函数Str．To-Lists(S)：Lists，例如Str．To-Lists(’(a，(a，b)，c)’)的值为一个广义表。(5)由广义表到广义表的字符串形式的转换函数Lists-To-Str(L)：String。(6)最好能设置多个广义表。对题目分析本题主要考察广义表的应用，所以之前先要对广义表要有一定的了解。线性表被定义为一个有限的序列（a1，a2，a3，…，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2，d3，…，dn的有限序列，但不同的是，广义表中的

4、di则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时，又使用了广义表的概念。线性表被定义为一个有限的序列（a1，a2，a3，…，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2

5、，d3，…，dn的有限序列，但不同的是，广义表中的di则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时，又使用了广义表的概念。数据的输入输出输入：数据要求输入一个广义表例如：（（a,b）,c,(d,

6、e)）（(1,2,3）,4）27输出：输出9种有关广义表的操作如下：1字符串变广义表2广义表的复制3广义表的长度4广义表的深度5广义表的表头6广义表的表尾7广义表变为字符串8查找广义表中的字符9重新设定广义表0推出程序算法测试设计用例（（a,b）,c,(d,e)）概要设计各抽象数据类型的定义GList：广义表的类型定义GList*StrToLists(char*&s)：字符串变为广义表的函数char*ListsToStr(GList*L,intk)：广义表变为字符串的函数GList*CopyGList(GList*p

7、)：复制广义表的函数intlength(GList*L)：计算广义表长度的函数intdepth(GList*L)：计算广义表深度的函数intFind(GList*L,charch)：计算广义表深度的函数voidPrintGList(GList*L)：打印广义表的函数GList*head(GList*&L)：取广义表表头的函数GList*tail(GList*&L)：取广义表表尾的函数广义表的扩展线性链表表示typedefstructGLNode{inttag;//tag为公共部分，只能为1和0，1代表//表结点，0代

8、表原子结点union//原子结点和表结点的联合部分{ElemTypedata;//原子结点的值域structGLNode*ph;//表结点的表头的表头指针}ptr;structGLNode*pt;//相当于线性链表的next，指向下一个元27//素结点}GList;//广义表类型GList是一种扩展的线性链表广义表的图形表示DDDCADDccc