广义表的运算.doc

黄伟华 广义表的运算 第页 共22页 广义表的运算 学生姓名：黄伟华 指导老师：肖增良 摘 要 这次的课程设计主要是广义表的运算，要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。通过对广义表的运算的掌握，达到更好地理解与运用所学知识，提高动手能力的目的。在本课程设计中，系统开发平台为Windows2000,程序设计语言为C语言，程序运行平台为Windws 98/2000/XP。在程序设计中采用了结构体及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在实际中解决问题。 关键词 堆栈，递归，结点，广义表。 1 引 言广义表是一种非线性的数据结构，顾名思义，它也是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构。线性表被定义为一个有限的序列（a1，a2，a3，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2，d3，dn的有限序列，但不同的是，广义表中的di 则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，dn）称为广义表的表尾。1.1 课题背景当今世界已进入信息时代，随着计算机科学与技术的迅猛发展，计算机应用已深入到科研、管理和生产的各个领域，尤其在企业与经济部门的管理工作中发挥着巨大作用。数据结构是实现计算机应用的重要基础和有效手段。20世纪80年代，计算技术开始渗透到大多数学科领域。计算技术的日新月异，促进着时代的发展，任何一个领域，无不依赖着计算机的强大的各种功能与计算能力。从计算机对整个世界的影响来看，学好这门科学显得无比的重要。学习好数据结构课程，却又是学习好计算机科学与技术的基础，掌握各种数据的存储结构，就能设计不同的数据结构，为不同领域的需求提供服务，达到市场需求。1.2 课程设计目的本次课程设计的实验目的是通过该实验掌握较复杂程序的设计。掌握广义表的一些基本操作，同时对结构体和堆栈的操作进行复习和实践，充分认识理论知识对应用技术的指导性作用，进一步加强理论知识与应用相结合的实践和锻炼。使自己的设计水平和对所学的知识的应用能力以及分析问题解决问题的能力得到全面提高。同时，巩固和深化自身的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的学习习惯，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。1.3课程设计内容本课程设计是实现广义表的相关操作，包括实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等，其框架图如下图1.3.1所示：建立广义表广义表的运算遍历广义表广义表的查找求广义表的深度求广义表的表尾求广义表的逆表图1.3.1广义表的运算框架图2 设计思路与方案2.1设计思路1、建立广义表CreateGL(char *&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以0作为结束标志。实现过程如下：GList *CreateGL(char *&s) 读入广义表的一个字符给ch； if (ch!=空格) if (ch=() 递归构造子表；else if (ch=) 遇到)字符,子表为空else构造原子结点；else 串结束,子表为空读入广义表的一个字符给ch；if (ch=,) 递归构造后续子表；else 处理表的最后一个元素 返回广义表指针2、遍历广义表DispGL(GList *g)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号”(”。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完后，再打印一个右括号”)”。若遇到tag=0的结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇到tp=NULL。其实现过程如下：void DispGL(GList *g)if (g!=NULL) if (g-tag=1) 输出左括号(；if (g-val.hp=NULL) 输出一个空格；else 递归调用子表；else输出数据域；if (g-tag=1)打印有括号“）”；if (g-tp!=NULL)输出逗号“，”，递归调用输出下一个结点。3、广义表的查找：FindGListX()在给定的广义表种查找数据域为x的结点，采用的算法思想是：若遇到tag=0的原子结点，如果是要查找的结点，则查找成功1；否则，若还有后续元素，则递归调用本过程在孩子表中查找，若还有后续元素，则递归调用本过程查找后续每个元素，直到遇到hp域为NULL的元素。设置mark标志查找结果；mark=1；表示查找成功，否则查找失败。本函数实现过程如下：FindGListX(GList *g,char x,int &mark)if(g!=NULL)if (g-tag = 0 & g-val.atom =x) 查找成功mark = 1;elseif(g-tag = 1) 递归调用查找后续元素；递归查找调用后续元素；4、求广义表的表尾：tail(GList *s)一个广义表的表尾指的是除去该广义表的第一个元素剩下的部分。求表尾实现过程如下：GList *tail(GList *g)if (g=NULL) 空表不能求表尾；else if (g-tag=0) 原子不能求表尾；将广义表除去第一个元素，其余的元素复制的广义表q中，既为该广义表的表尾。return q;5.求广义表的深度GLDepth(GList *g)。广义表的深度的递归定义是它等于所有子表中表的最大深度加1，若一个表为空或仅由单个元素所组成，则深度为1。求广义表深度的递归函数GLDepth（）如 GLDepth（）1 若h为空表maxGLDepth(sh)|sh为h的子表+1 其他情况实现过程如下：int GLDepth(GList *g) if (g-tag=0)为原子时返回；g=g-val.hp;if (g=NULL)为空表时返回1；while (g!=NULL) if (g-tag=1) 递归调用求出子表的深度；if (depmax) max为同一层所求过的子表中深度的最大值； 使g指向下一个元素；返回表的深度(max+1) 。 6、求广义表的逆表NIGList(GList *g,SeqStack *s)求广义表的逆表的算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，然后在将栈中所有的元素出栈打印，函数的实现如下：将广义表中的元素存入堆栈中：void NIGList(GList *g,SeqStack *s)if(g!=NULL) if (g-tag=1) 将广义表中的“(”以“)”存入栈中；else 递归调用，将子表中的元素存入栈中；else将广义表中的元素存入栈中；if (g-tag=1) 将广义表中的)以(存入栈中；if (g-tp!=NULL) 将广义表中的,存入栈中； 递归将后续表的内容存入栈中。将栈中所有元素输出：void Pop(SeqStack *s) 打印栈中元素。2.2数据结构设计1、广义表的存储结构：由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用顺序存储的结构表示。通常采用链式存储结构，每个元素可用一个结点表示原子结点结构如下图2.2.1、2.2.2所示：tag=0atom图2.2.1原子结点的存储结构tag=1*hp*tp 图2.2.2表结点的存储结构其中tag是一个标志位，用来区分当前结点是原子结点还是子表。当tag为1时，该结点是子表，第二个域为hp，用以存放子表的地址；当tag为0时，该结点是原子结点，第二个域为atom，用以存放元素值。tp域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，tp的值为NULL。广义表及结点类型描述如下：typedef char ElemType;typedef struct GLode int tag; union ElemType atom; struct GLode *hp; val; struct GLode *tp; GList;2、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下：typedef char ElemType;typedef struct ElemType datamaxlen ; int top;SeqStack; else return 0; 3详细实现首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个过程也就是生成广义表。查找广义表，查找广义表要返回一个值mark，当mark=1时，程序查找到待查的元素，当mark=0时，程序没有找到待查元素。输出广义表，遍历广义表，输出广义表的遍历结果；取表尾，将广义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值；求逆表，将广义表逆向输出。3.1 输入广义表模块简介，流程图，代码3.2 Case:0Case:4Case:3Case:2Case:1开始建立一个用字符数组存储的广义表，用字符指针s指向它。生成数组广义表结构遍历广义表输入广义表建立堆栈查找待查元素，mark=1，找到待查元素，反之，没有查到。求广义表的表尾，并输出求广义表的深度，并输出求广义表的逆表，并输出清屏输出“再见”输出结束流程图如下图所示：广义表运算流程图4 运行环境与结果4.1运行环境本课程设计中，系统开发平台为Windows XP,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。 Visual C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。4.2运行结果一、本程序运行过程时带有提示性语句，用户可以根据需要和提示进行操作：1、运行程序，程序提示输入广义表，出现运行界面；2、查找广义表中的元素。选择1，程序提示，输入要查找的元素，若该元素在广义表中，程序显示：找到待查元素。否则显示:找不到待查元素；3、求广义表的表尾。选择2，程序输出所求广义表的表尾；4、求广义表的深度。选择3，程序输出广义表的深度；5、求广义表的逆表。选择4，程序输出广义表的逆表；6、选择0，退出广义表的运算，程序终止；7、每次操作结束以后，会有提示语句：是否继续执行其他操作(选择1、继续 ；0、停止)。二、运行界面运行界面如下图：输入一个广义表(a,b,(c,d)按回车键，如下图选择相关操作，如1，回车显示如下：输入一个存在的元素，如a，回车显示如下：输入不存在的元素，如e,回车后显示：选择1返回，选择2，求广义表的表尾，如图：求深度,如下图：求逆表，如下图按0退出，显示如下：5 总结长达两周的数据结构课程设计实习即将结束了。这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的广义表的运算，但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容，编程能力也有了一定的提高。同时也学会了许多解决问题的方法。因为是第一次做课程设计，难免会遇到过各种各样的问题，遇到问题自然就知道了自己的不足之处：1，对书本知识掌握得不够牢固；2，无法灵活运用所学知识；3，对程序整体的结构设计不够严谨；4，排错能力还有待提高。通过这次课程设计我懂得了理论与实际相结合的重要性：我们必须牢固掌握基础知识，并进行拓展，把所学的理论知识与实践相结合起来，不断在实践中发现问题，并从中找出自己的不足之处，不断改进，从理论和实践中得出结论，提高自己的实际动手能力和独立思考的能力。同时，通过这次课程设计，我认识到了数据结构的重要性，发现了书中算法的魅力，并从中汲取了大量对自身有帮助的知识。这次数据结构课程设计给我的最大的启示就是：什么事，做了不一定能成功，但不去做，就一定不会成功！与其临渊羡鱼，不如退而结网。通过此次课程设计给我的启示，在以后的学习生活中，我会通过不断的实践和挑战来完善自己，为自己的理想而奋斗！参考文献1 严蔚敏 吴伟名 数据结构（C语言版）请华大学出版社 20042 苏小红 陈惠鹏 孙志岗 C语言大学实用教程 电子工业出版社 2007.2 3 苏德富 钟诚等 数据结构（C语言） 第二版 重庆大学出版社 20064 黄国兴 章炯民 数据结构与算法 北京：机械工业出版社，2004年7月第一版5 王昆仑 李红 数据结构与算法 北京：中国铁道出版社，2007年6月第一版6 Pascal之父Niklaus Wirth 算法 + 数据结构 = 程序 科学出版社 20017 苏运霖数据结构与算法中南工业大学出版社 20028 Shaffer数据结构与算法分析(C+版、JAVA版) 电子工业出版社 19999 谭浩强C程序设计(第三版) 清华大学出版社 2009年1月10 谭浩强 张基温程序设计教程 清华大学出版社 2008年3月11 谭浩强.计算机C语言教程M.北京：电子工业出版 2001 12 麻志毅C语言解析教程(原书第4版) 机械工业出版社 200213 徐孝凯，魏荣数据结构,机械工业出版社，1996年14 徐孝凯数据结构简明教程，清华大学出版社，1995年15 陈文博，朱青数据结构与算法，机械工业出版社，1996年16 许卓群，张乃孝，杨冬青，唐世渭数据结构，高等教育出版社，1988年附录：源程序代码#include #include #include#define maxlen 100typedef char ElemType;typedef struct GLode/广义表结构体的定义int tag;unionElemType atom;struct GLode *hp; val;struct GLode *tp; GList;typedef struct /栈结构的定义ElemType datamaxlen ;int top;SeqStack;/生成广义表GList *CreateGL(char *&s)GList *h;char ch;ch=*s; s+; if (ch!=0) h=(GList *)malloc(sizeof(GList);if (ch=() h-tag=1;h-val.hp=CreateGL(s);else if (ch=)h=NULL;elseh-tag=0;h-val.atom=ch;elseh=NULL; ch=*s;s+;if (h!=NULL)if (ch=,) h-tp=CreateGL(s); else h-tp=NULL; return h; /遍历广义表void DispGL(GList *g)if (g!=NULL)if (g-tag=1) printf(); if (g-val.hp=NULL)printf();elseDispGL(g-val.hp); elseprintf(%c, g-val.atom); if (g-tag=1)printf();if (g-tp!=NULL)printf(,);DispGL(g-tp); /求广义表的深度int GLDepth(GList *g) int max=0,dep;if (g-tag=0)return 0;g=g-val.hp;if (g=NULL)return 1;while (g!=NULL)if (g-tag=1)dep=GLDepth(g);if (depmax)max=dep; g=g-tp; return(max+1);/求广义表的表尾GList *tail(GList *g) GList *p=g-val.hp;GList *t;if (g=NULL)printf(空表不能求表尾n);return NULL;else if (g-tag=0)printf(原子不能求表尾n);return NULL;p=p-tp;t=(GList *)malloc(sizeof(GList);t-tag=1;t-tp=NULL;t-val.hp=p;return t;/查找函数void FindGListX(GList *g,char x,int &mark)if(g!=NULL)if (g-tag = 0 & g-val.atom =x)mark = 1;elseif(g-tag = 1) FindGListX(g-val.hp,x,mark);FindGListX(g-tp,x,mark);/求广义表的逆表void NIGList(GList *g,SeqStack *s)if(g!=NULL)if (g-tag=1)s-top+;s-datas-top=);if (g-val.hp=NULL)printf();elseNIGList(g-val.hp,s); elses-top+;s-datas-top=g-val.atom;if (g-tag=1)s-top+; s-datas-top=(; if (g-tp!=NULL)s-top+;s-datas-top=,; NIGList(g-tp,s); /广义表的输出void Pop(SeqStack *s) while(s-top=0) printf(%c,s-datas-top);s-top-;/以下主函数用于调试void main()GList *g,*gt;printf(请输入一个广义表:如(