张翔-0604011022-广义表的运算问题

1、合肥学院计算机科学与技术系课程设计报告20082009学年第1学期课程 数据结构与算法 课程设计名称广义表的运算问题学生姓名张翔学号0604011022专业班级06计科(1)班指导教师 王昆仑、胡春玲 2008年09月一、问题分析和任务定义1、【题目15】：广义表的运算问题。2、要求和任务： 本设计要求实现广义表的建立、查找、输出、取表尾以及求深度、求逆表等。3、数据的输入、输出：输入：数据要求输入一个广义表，在各项数据输入完毕后要多输入一个右括号。例如： 建立广义表，结束请多输一个右括号 (a,(b,c),d)输出：输出的是6种有关广义表的操作如下： 1 广义表的输出 2 广义表求深度 3

2、广义表取表头 4 广义表取表尾 5 广义表求逆表6 广义表的查找（此项操作种要求用户输入要查找的项）0 退出系统4、算法测试用例设计： (a,(b,c),d)二、数据结构的选择和概要设计1、数据结构在此问题中，使用到的数据结构有：广义表广义表的定义：广义表是n(n0)个元素a1，a2，ai，an的有限序列。  其中：    ai-或者是原子或者是一个广义表。  广义表通常记作：              GList=( a1，

3、a2，ai，an)。  GList是广义表的名字，n为它的长度。 若ai是广义表，则称它为Ls的子表。注意：    广义表通常用圆括号括起来，用逗号分隔其中的元素。    为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。    若广义表GList非空(n1)，则al是GList的表头，其余元素组成的表(a1，a2，an)称为GList的表尾。    广义表是递归定义的广义表的双链存储法接点类型描述如下：typedef enumATOM, LIS

4、T,BTOMElemTag; /*ATOM=0:原子,LIST=1:子表*/typedef struct GLNode int tag; /*公共部分,区分原子A和表结点*/ union /*原子结点和表结点的联合部分*/ char atom;/*原子结点的值域*/ struct GLNode *sublist;/*表结点表头指针*/ ; struct GLNode *next;/*下一个元素结点*/GList; 广义表的图形表示：A = ( ) B = (6, 2) C = (a, (5, 3, x) D = (B, C, A)DABC62a53x共享表A空表B62线性表Ca53x纯表 图1

5、带表头结点的链式存贮表示举例:D = (B, C, A) = (6, 2), (a, (5, 3, x), ( )0101 16 1200 3 3 3 01 3 2a 0 15 13 2xABDC 图22、设计思想 广义表是线性表的一种推广，但它并不是线性表。课本上在介绍广义表的计本概念的基础上，介绍了广义表的存储及应用。广义表浓缩了线性表、数组等常见的数据结构的特点，在有效利用存储空间方面更胜一筹，目前在文本处理、人工智能、代数操作和计算机图形方面等各个领域都具有应用价值。所以在我当时拿到这个题目的时候，虽然它只有短短的几行字，但是我深深的感觉到了它的难度，在后来课程设计中，也证实了我的感觉

6、，每个功能都实在是太难实现了，所以只有各个击破了。设计程序时，先起草了流程图，通过流程图来看，就使得程序鲜明易懂，接下来先写好了主函数，通过主函数的调用，实现题目要求的各个功能，使得程序模块化，便于编写，即使不会写的子函数，也可以先空着，等待以后想到好的方法后再对其进行操作，同时在程序界面上也做了美化，使人感觉舒畅，另外通过一个循环，能让用户进行循环操作，不至于每次只能进行一项操作,这个循环用的和线性表里的循环有点类似，但其实现的操作不同，当然有了以前实验的基础，这次编写起来，也感觉轻松了不少。3、广义表的运算问题流程图 （1） 结构图mainCreateGList menu_selectPr

7、intGListGListDepthGListHeadGListTailTraverselistFind 图 3 结构图（2）流程图开始输入数据如果数据值不为“”如果数据值为“（”则指向此元素的指针的标志量为LIST调用此函数，建立此广义表的表头指针所指的元素指向此元素的指针的标志量为ATOM,且元素值为所输入数值输入数据如果输入数据为“，”调用此函数，建立此广义表下一个元素如果为“）”下一个元素的地址为空 结 束 图 4 建广义表 开 始如果广义表的标志量为LIST输出“（”如果广义表表头指针不为空调用此函数，输出广义表表头指针所指元素输出此元素如果下一个元素不为空输出“，”调用此函数，输出

8、广义表下一个元素结 束 图 5 广义表的输出 开 始广义表如果存在返回1变量max的初值为0如果元素地址不为空如果元素标志量为LIST调用此函数，求广义表表头指针的深度，值付给变量dep指针指向下一个元素若果dep>maxdep付给max返回值为max +1 结 束 图 6 广义表深度 开 始调用建表函数，建立广义表调用菜单函数如果为1调用输出广义表函数如果输入的为2调用求深度函数如果为3调用取表头函数如果为4调用取表尾函数如果为5调用求逆表函数如果为6调用查找函数如果为0再 见 结 束 图 7 主函数三、详细设计和编码1.函数名称 menu_select int menu_select

9、( ) int sn; printf(" 广义表相关运算n"); printf("=n"); printf(" 1 广义表的输出n"); printf(" 2 广义表求深度n"); printf(" 3 广义表取表头n"); printf(" 4 广义表取表尾n"); printf(" 5 广义表求逆表n");printf(" 6 广义表的查找n");printf(" 0 退出系统n"); printf("

10、=n"); printf(" 请选择06：n"); for( ; ; ) scanf( "%d", &sn); if( sn <0|sn>6) printf("nt输入错误，重选06：n"); else break;return sn;函数功能： 此函数为功能菜单选择函数，当在主函数中输完广义表并回车后，便调用此函数，由这个函数打印出有关广义表运算的各项操作，并通过循环，提供用户循环执行各项选择操作，当输入的数据超出范围时，提示错误信息，返回到操作菜单，让用户重新选择要进行的操作。 2.主函数：int m

11、ain()int main( ) GList *gl; printf("建立广义表，结束请多输一个右括号n"); CreateGList(&gl); for(; ;) switch(menu_select() case 1:printf("您输入的广义表为："); printGList(gl);printf("n");break; case 2:printf("广义表的深度为：");printf("%dn", GListDepth(gl->sublist);printf("

12、;n"); break; case 3:printf("广义表取表头n"); GListHead(gl);printf("n");break; case 4:printf("广义表取表尾n"); printf("("); GListTail(gl); printf(")");printf("n");break; case 5:printf("广义表求逆表n"); TraverseList(gl);printf("n");bre

13、ak; case 6:char ch; printf("请输入要查找的元素n"); scanf("%c",&ch);Find(gl, ch);printf("n");break; case 0:printf("再见");printf("n");exit(0);break; return 0;函数功能：主函数在整个函数中所起的作用是举足轻重的，这是很显而易见的，当程序运行时，首先执行的就是主函数，在此主函数中，首先打印提示信息，提示用户输入广义表，并在结束时多输一个右括号，这是由于下面Cr

14、eateGList函数的递归的原因，待用户输入完成后，将输入的信息保存到内存中，并调用menu_select()函数，通过这个函数，提示用户输入有关操作，当用户输入某一个操作时，通过switch(menu_select()对用户所输入的信息进行匹配，匹配后调用相关的子函数，从而实现各项函数的功能。3. 函数名称:CreateGListint i=0;int a10;void CreateGList(GList *gl) char ch; scanf("%c", &ch); getchar(); if(ch = '#') *gl = NULL; els

15、e if(ch = '(') *gl = (GList *)malloc(sizeof(GList); (*gl)->tag = LIST; CreateGList(&(*gl)->sublist); else *gl = (GList *)malloc(sizeof(GList); (*gl)->tag = ATOM; (*gl)->atom = ch; ai=ch; i+; scanf("%c", &ch); getchar(); if(ch = ',') CreateGList(&(*gl

16、)->next); else if(ch = ')') (*gl)->next =NULL; 函数功能：此函数为构建函数，为整个程序中的基础函数，其他函数都是以此函数为基础，来进行实现各项功能的。在实现此函数时，先定义初始化一个整型数据i=0和一个数组a10，构建时，先输入保存用户输入的数据，如果输入的是“#”，表示广义表为空表， 否则就输出第一个左括号，接下来的元素项如果是子表，便递归调用CreateGList()，打印子表，若是原子项，则直接输出，并将此输入的数据保存在数组ai中，同时i+，然后继续输入保存用户所输入的数据，若是“，”，则递归调用CreateGL

17、ist（）函数，继续第一步的操作，当遇到“）”时，结束。4. 函数名称:PrintGListvoid PrintGList(GList *gl) if(gl->tag = LIST) printf("("); if(gl->sublist = NULL)printf("#");elsePrintGList(gl->sublist); printf(")"); else printf("%c", gl->atom); if(gl->next !=NULL) printf(",

18、");PrintGList(gl->next);函数功能：此函数为结果及界面的输出函数，是用户直接接触到的函数，当然亦是非常重要的，一个好的函数，不仅要程序的功能完善，更要界面的实用性、可操作性强，在这个函数中，分子表和原子两种，若是子表，利用头结点指针，递归打印子表，如果为原子的话，直接打印该原子，接下来判断下一结点是否为空，不为空的话就输出“，”，继续递归打印，执行上一步的操作。5.函数名称:GListDepthint GListDepth(GList *gl) int max, dep; if(!gl) return 1; for(max = 0; gl; gl = gl

19、->next) if(gl->tag = LIST) dep = GListDepth(gl->sublist); if(dep > max) max = dep; return max + 1; 函数功能：此函数为求广义表的深度函数，广义表深度的递归定义是：它等于所有子表中表的最大深度加1。若一个表为空，则深度为1。设dep表示任一子表的深度，max表示所有子表中的最大depth表示广义表的深度，则有：    depth=max+l当一个表不包含任何子表时，其深度为l，所以max的初值应为0。从这个函数可以看出，当广义表为一个空表或仅由单

20、元素组成时，不进入下一的递归调用，而结束本次调用并返回l。当广义表含有子表时才会进入求子表深度的递归返回后修改max的值，使之成为所求过的本层次子表中深度的最大值。6.函数名称:GListHeadvoid GListHead(GList *gl) GLNode *p;p=gl->sublist;PrintGListHead(p);7.函数名称：GListTailvoid GListTail(GList *gl) GLNode *p,*q;q=gl->sublist;p=q->next;PrintGList(p); 函数功能：这两个函数是用来求广义表的表头、表尾的函数。当广义表

21、非空时，称第一个元素为的表头；称广义表中除去表头后其余元素组成的广义表为的表尾。例如：广义表(a, (b)的表头是单元素a，表尾是广义表(b)。根据广义表对表头和表尾的定义可知：对任意一个非空的广义表，其表头可能是单元素，也可能是广义表，而其表尾一定是广义表。注意表尾的深度（即括号的嵌套层数），表尾是由除了表头以外的其余元素组成的广义表，所以，需要在表尾的直接元素外面再加一层括号。8.函数名称：TraverseListvoid TraverseList(GList *gl)printf("("); GListTail(gl); printf(",");

22、GListHead(gl);printf(")");函数功能：此函数用来实现广义表求逆表的运算。广义表的逆表就是将广义表的表头跟表尾倒置，输出即可。9.函数名称:PrintGListHeadvoid PrintGListHead(GList *gl) if(gl->tag = LIST) printf("("); if(gl->sublist = NULL)printf("#");elsePrintGListHead(gl->sublist); printf(")"); elseprintf(&q

23、uot;%c", gl->atom);函数功能：此函数用来辅助输出广义表的表头，利用递归调用，不断打印表头（原子或子表）。10.函数名称Findvoid Find(GList *gl,char ch)int j;scanf("%c",&ch);for (j=0;j<=i;j+)if(aj=ch)printf ("查找成功，位置为%dn",j+1);break;if(j>i)printf("查找失败,元素不存在此广义表中!n");函数功能：此函数用来实现广义表的查找，将数组中的元素与用户输入的元素进行

24、比较，若相等，则查找成功，输出此元素的位置信息，当查找超出范围时，输出查找失败信息。四、上机调试在上机调试的过程中，程序出现了很多的问题:1、调试时出现错误，提示未为广义表申请空间。2、广义表输入正确时，按Enter键，无显示。经检查发现未写出结束语。当广义表输完后应多输一个右括号表示输入完毕。3、在输出广义表时，发现输出不正确。仔细查看输出的结果，发现所有的右括号都未输出。返回程序中，发现输出完广义表的最后一元素时，未写出输出右括号语句。4、由于“，”号不做为广义表的元素，所以在用gl->next时不能输出“，”，所以在输出函数中应写出输出“，”的语句。5、在调用查找函数时，虽然已写出

25、输入要查找的元素，但输出结果直接显示查找失败。也就是说输入元素语句没有执行。为了弄明白为什么没有执行，我依次在此语句的上下分别写了句输出“c“的语句，发现都能输出。然后又将主函数中输入元素语句写在查找函数中，此输入元素语句依然不能执行。在偶然的机会下，发现此语句执行成功。返回来看程序，发现当此输入此语句在主函数中和查找函数中都有写出时，此语句就能执行。五测试结果及其分析测试用例：(a,(b,c),d)数据输入： ( a , ( b , c ) , d ) 图8输入时要按照提示输入，结束时要多输一个右括号，这是由于递归的原因。执行操作：1、广义表的输出： 图9输入“1”时，执行的操作是广义表的输

26、出，调用此函数，输出广义表。2、广义表求深度： 图10输入“2”所执行的操作是求广义表的深度，在调用求深度函数时，返回max+1，即子表的深度加一。3、广义表取表头： 图11输出广义表的表头。4、广义表取表尾： 图12输出广义表的表尾。5、广义表求逆表：图13输出逆置后的广义表。6、广义表的查找（由用户输入要查找的项）： 图14此项为广义表的查找，要求用户输入要查找的元素，并输出查找后的信息。0、退出系统：图15退出系统。六、时间、空间复杂度时间复杂度：仅有一重循环，执行的次数为10，所以时间复杂度也为10。空间复杂度：在初始输入时，数据保存在a10这个数组中，所以程序的空间复杂度应为10。七

27、、用户使用说明用户在使用过程中，需按照程序指定的要求标准化的输入，才能得到如期的结果。例如在原始数据输入时，需要换行输入，在输入完成后要多加一个"("。运行环境为Microsoft Visual C+ 6.0八、心得体会数据结构的课程设计，今天终于算是完工了，从来都没独自解决这么大的一个程序了，虽然里面不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。看着自己的成果，真的很高兴，很有成就感。在这次课程设计中，我学到了很多东西，广义表在书中所占了比例不多，具体操作书上也没有详细的介绍，所以在编程序的时候给我带来了很大的难度，正是

28、由于这个难度，使我认识到，不能完全的依赖书本上提供的信息，要有自己的分析、推广能力，虽然书上广义表介绍的不多，可是以前学的顺序表、线性表等的都可以拿来作为参考，通过以前的那些程序的实现，来对广义表进行操作。当然了，现在说起来是感觉比较轻松，可是在实际编程的时候，确实是困难重重。通过这次课程设计，我深深的感觉到实践的重要性，以前在课堂上听课，感觉什么都懂，学的知识都好简单，可是在实践的时候却是无从下手，不过还好有以前c+课程设计的经历做铺垫，在稳定下心情后，慢慢的就开始着手搞程序了，通过上网、去图书馆查资料，就这样一点一点地把程序的各个功能都实现了。通过这次课程设计后，我认为以后要更加注重知识的

29、应用性，不能只停留在课本上，这样学出来的都是死的知识，不能活学活用，以后所学的每个知识点，我都要争取独立的上机完成，一方面可以巩固学过的知识，另一方面又加强了动手操作能力，相信这种能力在以后的工作学习中都是非常重要的。 希望像数据结构课程设计这样的实践型课程学校能多多的开展，能增强我们的动手操作能力、独立解决问题的能力。九、参考文献1.王昆仑、李红.数据结构与算法.北京：中国铁道出版社,2007年1月2.谭浩强.C程序设计.北京：清华大学出版社,2005年7月3.谭浩强.C程序设计指导.北京：清华大学出版社,2005年7月4.郑莉、董渊.C+语言程序设计.北京：清华大学出版社,2003年12月

30、5.李春葆.数据结构 习题与解析.北京：清华大学出版社,2002年4月 附录：源程序#include <iostream>#include <stdlib.h>#include <string>using namespace std;#define NULL 0typedef enumATOM, LIST,BTOMElemTag; /*ATOM=0:原子,LIST=1:子表*/typedef struct GLNode int tag; /*公共部分,区分原子A和表结点*/ union /*原子结点和表结点的联合部分*/ char atom;/*原子结点的值

31、域*/ struct GLNode *sublist;/*表结点表头指针*/ ; struct GLNode *next;/*下一个元素结点*/GList;void CreateGList(GList *gl); void PrintGList(GList *gl);int GListDepth(GList *gl);void GListHead(GList *gl);void GListTail(GList *gl);void TraverseList(GList *gl);void PrintGListHead(GList *gl);void Find(GList *gl,char ch)

32、;int menu_select( );int i=0;int a10;/*函数名称:CreateGList*/void CreateGList(GList *gl) /*函数名称:CreateGList*/ char ch; scanf("%c", &ch); getchar(); /*吞食scanf留下的换行*/ if(ch = '#') /*如果输入的是#表示为空*/ *gl = NULL; else if(ch = '(') /*如果是左括号就递归构件子表*/ *gl = (GList *)malloc(sizeof(GLis

33、t); (*gl)->tag = LIST; CreateGList(&(*gl)->sublist); else /*就是只有原子的情况下*/ *gl = (GList *)malloc(sizeof(GList); (*gl)->tag = ATOM; (*gl)->atom = ch; ai=ch; /不能写成ai=(*gl)->atom; i+; scanf("%c", &ch); /*此处输入的必为逗号或者右括*/ getchar(); if(ch = ',') /*如果是逗号就递归构件下一个子表*/

34、CreateGList(&(*gl)->next); else if(ch = ')') /*如果是右括号就结束*/ (*gl)->next =NULL; /*函数名称:PrintGList*/void PrintGList(GList *gl) /*函数名称:PrintGList*/if(gl->tag = LIST) printf("("); /*先输出左括号*/if(gl->sublist = NULL)printf("#");elsePrintGList(gl->sublist); /*递归打

35、印子表*/ printf(")"); /*结束打印右括号*/else printf("%c", gl->atom); if(gl->next !=NULL) printf(", ");PrintGList(gl->next);/*函数名称:GListDepth*/int GListDepth(GList *gl) /*函数名称:GListDepth*/ int max, dep; if(!gl) return 1; for(max = 0; gl; gl = gl->next) if(gl->tag =

36、LIST) dep = GListDepth(gl->sublist); /*求以gl->sublist的子表深度*/ if(dep > max) max = dep; return max + 1; /*各元素的深度的最大值加一*/*函数名称:GListHead*/void GListHead(GList *gl) /*函数名称:GListHead*/GLNode *p;p=gl->sublist;PrintGListHead(p);/*函数名称：GListTail*/void GListTail(GList *gl) /*函数名称：GListTail*/GLNode

37、 *p,*q;q=gl->sublist;p=q->next;PrintGList(p); /*函数名称：TraverseList*/void TraverseList(GList *gl)printf("("); GListTail(gl); printf(","); GListHead(gl);printf(")");/*函数名称:PrintGListHead*/void PrintGListHead(GList *gl) if(gl->tag = LIST) printf("("); /*先

38、输出左括号*/if(gl->sublist = NULL)printf("#");elsePrintGListHead(gl->sublist); /*递归打印子表*/printf(")"); /*结束打印右括号*/elseprintf("%c", gl->atom);/*函数名称Find*/void Find(GList *gl,char ch)int j;scanf("%c",&ch);for (j=0;j<=i;j+)if(aj=ch)printf ("查找成功，位置为%dn",j+1);break;if(j>i)printf("查找失败,元素不存在此广义表中!n");