广义表的运算.doc.doc

《广义表的运算.doc.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、黄伟华《广义表的运算》第２３页共22页广义表的运算学生姓名：黄伟华指导老师：肖增良摘要这次的课程设计主要是广义表的运算，要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。通过对广义表的运算的掌握，达到更好地理解与运用所学知识，提高动手能力的目的。在本课程设计中，系统开发平台为Windows2000,程序设计语言为C语言，程序运行平台为Windws98/2000/XP。在程序设计中采用了结构体及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在实际中

2、解决问题。关键词堆栈，递归，结点，广义表。黄伟华《广义表的运算》第２３页共22页1引言广义表是一种非线性的数据结构，顾名思义，它也是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构。线性表被定义为一个有限的序列（a1，a2，a3，…，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2，d3，…，dn的有限序列，但不同的是，广义表中的di则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通

3、常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。1.1课题背景当今世界已进入信息时代，随着计算机科学与技术的迅猛发展，计算机应用已深入到科研、管理和生产的各个领域，尤其在企业与经济部门的管理工作中发挥着巨大作用。数据结构是实现计算机应用的重要基础和有效手段。20世纪80年代，计算技术开始渗透到大多数学科领域。计算技术的日新月异，促进着时代的发展，任何一个领域，无不依赖着计算机的

4、强大的各种功能与计算能力。从计算机对整个世界的影响来看，学好这门科学显得无比的重要。学习好《数据结构》课程，却又是学习好计算机科学与技术的基础，掌握各种数据的存储结构，就能设计不同的数据结构，为不同领域的需求提供服务，达到市场需求。。1.2课程设计目的本次课程设计的实验目的是通过该实验掌握较复杂程序的设计。掌握广义表的一些基本操作，同时对结构体和堆栈的操作进行复习和实践，充分认识理论知识对应用技术的指导性作用，进一步加强理论知识与应用相结合的实践和锻炼。使自己的设计水平和对所学的知识的应用能力以及分析问题解决问题的能力得到全面提高。同时

5、，巩固和深化自身的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的学习习惯，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。黄伟华《广义表的运算》第２３页共22页1.3课程设计内容本课程设计是实现广义表的相关操作，包括实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等，其框架图如下图1.3.1所示：建立广义表广义表的运算遍历广义表广义表的查找求广义表的深度求广义表的表尾求广义表的逆表图1.3.1广义表的运算框架图黄伟华《广义表的运算》第２３页共22页2设计思路与方案2.1设计思路1、建立广义表Create

6、GL(char*&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以""作为结束标志。实现过程如下：GList*CreateGL(char*&s){读入广义表的一个字符给ch；if(ch!=空格'){if(ch=='('){递归构造子表；}elseif(ch==')')遇到')'字符,子表为空else{构造原子结点；}}else串结束,子表为空读入广义表的一个

7、字符给ch；if(ch==',')递归构造后续子表；else处理表的最后一个元素返回广义表指针}2、遍历广义表DispGL(GList*g)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号”(”。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完后，再打印一个右括号”)”。若遇到tag=0的结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇到tp=NULL。其实现过程如下：黄伟华《广义表的运算》第２３页共22页voidDispGL(GLis

8、t*g){if(g!=NULL){if(g->tag==1){输出左括号'('；if(g->val.hp==NULL)输出一个空格；else递归调用子表；}else输出数据域；if(g->tag==1)打印