广义表的运算问题论文

《广义表的运算问题论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2008～2009学年第二学期课程数据结构与算法课程设计名称广义表运算问题学生姓名***学号***专业班级07计科(1)指导教师王昆仑/胡春玲2009年6月一、问题分析和任务定义1、题目15：广义表运算问题2、要求和任务：本设计要求实现广义表的建立、查找、输出、取表尾以及求深度、求逆表等。3、广义表的输入和输出程序中，要求建立一个广义表，以右括弧结束。如：建立一个广义表,以右括号结束：（（a），b，（c，d）））输出的是6种有关广义表的操作如下：1输出广义表2广义表深度3广义表表头4广义表表尾5广义表逆置6广义表查找0退出系统若不

2、进行任何运算，则退出。4、算法测试用例设计（（a），b，（c，d））（a，（b，c））（a）二、数据结构的选择和概要设计1、数据结构广义表的概念：广义表是n（n≥0）个元素(a1，a2，…，ai，…，an)的有限序列；其中，n为广义表的长度，ai或者是原子或者是一个广义表，当它是广义表时，称其为原广义表的子表。其中：①广义表是递归定义的，因为在定义广义表时用到了广义表的概念。②广义表用圆括号括起来，用逗号分隔其中的元素，记作L=(a1，a2，…，ai，…，an)，其中L是广义表的名字。③通常，用大写字母表示广义表，用小写字母表示原子。④若广义表L非空（n≥1），则a1

3、是广义表L的表头，其余元素构成的子表（a2，…，an)为广义表L的表尾。⑤广义表的元素可以是原子，也可以是子表，而且子表还可以有子表……，因此，广义表是以多层次的结构。⑥任何一个非空广义表，其表头可能是原子，也可以是广义表，而其表尾必定是广义表。由于任一非空的广义表都可以分解成表头和表尾两部分，因此一个表结点至少应包含两个域：表头指针域和表尾指针域，分别指向该广义表的表头和表尾；而一个原子结点中只需要存储该原子的值。为了区分原子结点和表结点，可为它们分别加上一个标志域。这样，一个表结点可由3个域构成：标志域tag=1，表头指针域hp和下一元素结点next。而一个原子结

4、点只需两个域：标志域tag=0和值域atom。广义表的单链存储结构结点类型如下：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{inttag;//公共部分,区分原子和表结点union//原子结点和表结点的联合部分{charatom;//原子结点的值域structGLNode*hp;//表结点表头指针};structGLNode*next;//下一个元素结点}GList;2、设计思想广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，但广义表比

5、数组更为复杂，广义表是一种递归定义的线性结构，因此它兼有线性结构和层次结构的特点，它的存储表示和操作的实现和树的操作很类似。程序的开始，先定义广义表的结点类型，采用枚举类型区分原子ATOM和子表LIST。采用联合体定义原子结点的值域atom和表头指针域hp。再输入一个广义表，在程序中可以定义一个数组用来存放广义表中的关键字。编写各个功能函数时，先了解算法的思想，绘出流程图，根据流程图进一步编写，则要简单得多。之后编写一个功能选择函数choose（），并在此函数中打印运行界面，通过输入代码，来进行不同功能的操作。在运行界面中，通过一个while循环，能让用户进行循环操作

6、，直至退出系统。3、广义表的运算问题流程图（1）结构图表1函数名功能CreatGList（）创建广义表PrintGList（）输出广义表GListDepth（）广义表求深度GlistHead（）广义表取表头GlistTail（）广义表取表尾Traverselist（）广义表逆置Locate（）广义表元素查找Choose（）菜单选择函数Main（）主函数mainCreateGListchoosePrintGListGListDepthGListHeadGListTailTraverselistLocate图1结构图（2）流程图开始输入数据如果数据值不为“＃”如果数据值为

7、“（”则指向此元素的指针的标志量为LIST递归调用本函数，建立此广义表的表头指针所指的元素指向此元素的指针的标志量为ATOM,且元素值为所输入数值输入数据如果输入数据为“，”递归调用本函数，建立此广义表下一个元素如果为“）”下一个元素的地址为空结束图2广义表的创建开始调用建表函数，建立广义表调用菜单函数如果为1调用输出广义表函数如果为2调用求深度函数如果为3调用取表头函数如果为4调用取表尾函数如果为5调用求逆表函数如果为6调用查找函数如果为0退出结束图3主函数三、详细设计和编码1、菜单函数intchoose(){intsn;printf("-----