广义表的运算问题论文

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

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

2、　　　如：建立一个广义表,以右括号结束：　　　（（a），b，（c，d）））　输出的是6种有关广义表的操作如下：　1输出广义表2广义表深度　　　3广义表表头4广义表表尾　5广义表逆置6广义表查找　　0退出系统　若不进行任何运算，则退出。　　　4、算法测试用例设计　（（a），b，（c，d））（a，（b，c））（a）　　　　　二、数据结构的选择和概要设计　　　1、数据结构　广义表的概念：　　广义表是n（n≥0）个元素(a1，a2，…，ai，…，an)的有限序列；其中，n为广义表的长度，ai或者是原子或者是一个广义表，当它是广义表

3、时，称其为原广义表的子表。　其中：　　　①广义表是递归定义的，因为在定义广义表时用到了广义表的概念。　　　②广义表用圆括号括起来，用逗号分隔其中的元素，记作L=(a1，a2，…，ai，…，an)，其中L是广义表的名字。　　③通常，用大写字母表示广义表，用小写字母表示原子。　　④若广义表L非空（n≥1），则a1是广义表L的表头，其余元素构成的子表（a2，…，an)为广义表L的表尾。　　⑤广义表的元素可以是原子，也可以是子表，而且子表还可以有子表……，因此，广义表是以多层次的结构。　　⑥任何一个非空广义表，其表头可能是原子，也

4、可以是广义表，而其表尾必定是广义表。　　由于任一非空的广义表都可以分解成表头和表尾两部分，因此一个表结点至少应包含两个域：表头指针域和表尾指针域，分别指向该广义表的表头和表尾；而一个原子结点中只需要存储该原子的值。为了区分原子结点和表结点，可为它们分别加上一个标志域。这样，一个表结点可由3个域构成：标志域tag=1，表头指针域hp和下一元素结点next。而一个原子结点只需两个域：标志域tag=0和值域atom。　　广义表的单链存储结构结点类型如下：　typedefenum{ATOM,LIST}ElemTag;//ATOM=

5、=0:原子,LIST==1:子表　　typedefstructGLNode　　{　inttag;//公共部分,区分原子和表结点　　union//原子结点和表结点的联合部分　{　charatom;//原子结点的值域　　　structGLNode*hp;//表结点表头指针　　　};　　　structGLNode*next;//下一个元素结点　}GList;　2、设计思想　广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，但广义表比数组更为复杂，广义表是一种递归定义的线性结构，因此它兼有线性结构和

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

7、　　3、广义表的运算问题流程图　　　（1）结构图　　　表1　函数名　　功能　　　CreatGList（）　　　创建广义表　　　PrintGList（）　　输出广义表　GListDepth（）　　　广义表求深度　GlistHead（）　　广义表取表头　　　GlistTail（）　　　广义表取表尾　Traverselist（）　　　广义表逆置　　　Locate（）　　广义表元素查找　Choose（）　　　菜单选择函数　Main（）　主函数　　　main　CreateGList　　choose　PrintGList　GListD

8、epth　　　GListHead　　　GListTail　Traverselist　　　Locate　　　图1结构图　　（2）流程图　开始　　　输入数据　　如果数据值不为“＃”　如果数据值为“（”　　　则指向此元素的指针的标志量为LIST　　　递归调用本函数，建立此广义表的表头指针所指的元素　　　指向此