数据结构-广义表的建立与输出

《数据结构》实验报告◎实验题目:广义表的建立与输出◎实验目的：1、掌握使用VisualC++6.0上机调试程序的根本方法；掌握广义表的存储结构，学会广义表的建立与输出；提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。◎实验内容：利用链式存储结构建立广义表，然后输出该广义表，在本实验中不使用递归的方法，而是用一个栈存储结点的指针，以此完成实验要求。一、需求分析1、输入的形式和输入值的范围：根据提示，输入广义表，按回车结束。2、输出的形式：输出结果为上一步所输入的广义表。3、程序所能到达的功能：输入广义表后，该程序可以建立广义表的链式存储结构，之后按照一定的顺序访问结点并输出相应的值，从而完成广义表的输出。4、测试数据：输入广义表:((),a,b,((c,(d,()))),((())))输出结果为:((),a,b,((c,(d,()))),((())))是否继续?〔是,输入1;否,输入0〕:1输入广义表:广义表未建立是否继续?〔是,输入1;否,输入0〕:0Pressanykeytocontinue二概要设计1、广义表是一种递归的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以其存储结构采用动态链式结构。每个结点的形式如下列图所示。tag为标记域：假设tag=0,表示该结点的sublist域不为空，假设tag=1,表示该结点为表结点，那么sublist域中存放相应子表第一个元素对应结点的地址；data域：存放广义表中的字母；sublist域：存放相应子表第一个元素对应结点的地址；next域：存放与本元素同一层的下一个元素所在结点的地址，当本元素是所在层的最后一个元素时，next域为空。广义表的建立本程序中利用数组存储所输入的广义表，然后从头到尾扫描数组中的每一个字符根据字符的不同分别执行不同的操作，并用一个存储结点指针的栈辅助完成。在扫描前先申请一个结点作为头结点，也是当前指针所指结点，在广义表的建立的过程中，每次申请一个新结点，需对其进行初始化，即令标记域为0，data域为空。按照本程序的思路，广义表(a,(b,c),())的链式存储结构如下列图所示。广义表建立的具体过程见详细设计局部。广义表的输出在广义表的输出过程中也需利用一个存储结点指针的栈辅助完成，初始时栈为空，广义表输出结束后栈也为空，所以在开始时将头结点入栈，之后根据当前指针所指结点的特性的不同执行不同的操作，以栈空作为广义表输出的结束条件。广义表输出的具体过程见详细设计局部。4、本程序的根本操作和模块：建立广义表的函数：Create(GLNode*G,SeqStack&K,chars[]) 输出广义表的函数：Display(GLNode*G,SeqStack&K)主函数：main()函数的调用关系如下列图所示:开始开始CreateCreate函数是是DisplayDisplay函数是否继续是否继续否否结束结束三详细设计元素类型、结点类型1、广义表结点的类型描述typedefstructLNode{ inttag; //tag为结点中的标记域 chardata; //data用于存储广义表中的字母 structLNode*sublist,*next; //sublist为指向下层的指针，next为指向同一层的指针 }GLNode;顺序栈的类型描述typedefstruct { GLNode*pin[20]; //指针数组，用于存储广义表结点指针 inttop; //栈顶指针 }SeqStack;每个模块的分析主程序模块main(){ ①定义数组，存储输入的字符串 ②定义并申请头结点 ③初始化顺序栈 ④while(1) { 调用输入广义表的函数，建立广义表的链式存储结构 调用输出广义表的函数，输出所建立的广义表 选择是否继续，假设是，那么重新执行循环中的操作；假设否，那么退出循环 }}建立广义表的函数voidCreate(GLNode*G,SeqStack&K,chars[]) { ①定义表示当前结点的指针p，和表示新申请结点的指针q令p指向头结点，且头结点的next域为空。 ②输入广义表 ③从头到尾扫描输入的字符，进入以下循环，当遇到空字符时结束循环for(j=0;s[j]!='\0';j++) { ◎假设字符为'('，执行以下操作 { 当前结点的标记域赋值为1，表示存在子表 当前结点的指针进栈申请新结点并令其标记域为0，data域为空字符 当前结点p的sublist域指向新结点q 将新结点指针赋给当前结点p } ◎假设字符为','，执行以下操作 { 申请新结点并令其标记域为0，data域为空字符 当前结点p的next域指向新结点q 将新结点指针赋给当前结点p } ◎假设字符为')'，执行以下操作 { 令当前结点p的next域为空 出栈，将栈顶元素赋给当前结点q } ◎假设字符为字母，执行以下操作 { 令当前结点p的data域为该字母 令当前结点的sublist域为空 }}}输出广义表的函数voidDisplay(GLNode*G,SeqStack&K) { ①定义表示当前结点的指针p，并令p指向头结点。 ②指向头结点的指针p入栈,使栈不空，输出广义表里的第一个左括号'('。 ③将当前结点p的sublist域所指结点赋给p。④当栈不空时执行以下操作 while(K.top!=-1) { ◎假设当前结点指针p不为空，执行以下操作 { 假设当前结点标记域为1,执行以下操作 { 输出'('，并当前结点指针p入栈 将当前结点p的sublist域所指结点赋给p } 假设当前结点标记域为0,执行以下操作 { 假设当前结点p的date域存有字母那么输出该字母 假设当前结点p的next域不为空，表示不是该层的结束，输出',' 将当前结点p的next域所指结点赋给p } } ◎假设当前结点指针为空，执行以下操作 { 输出')' 出栈，将栈顶元素赋给当前结点p， 假设当前结点p的next域不为空，表示不是该层的结束，输出',' 将当前结点p的next域所指结点赋给p } }}四使用说明、测试分析及结果程序使用说明：本程序运行环境为VisualC++6.0；根据界面提示进行操作,注意输入的字符为西文字符测试结果与分析：页面提示“输入广义表：”输入“((),a,b,((c,(d,()))),((())))”，按回车确定，页面显示如下：“ 输出结果为:((),a,b,((c,(d,()))),((())))是否继续?〔是,输入1;否,输入0〕: ”输入序号“1”，按回车确定，表示继续操作。页面提示“输入广义表：”不输入广义表，直接按回车确定，那么页面显示如下：“ 广义表未建立是否继续?〔是,输入1;否,输入0〕: ”输入序号“0”，按回车确定，表示结束操作，页面显示如下：“ Pressanykeytocontinue ”由上测试结果分析得，该程序功能满足题目要求。调试过程中遇到的问题及解决方法①当代码编写完成后，编译过程出现了很多小错误，比方语句末尾漏掉分号，使用了某些变量却未定义，但这些问题很快发现并及时纠正；②在建立广义表的函数中，建立结点后对其data域赋值不完整，一些特殊结点指针域的说明也不完整，导致输出结果有问题。于是回头进一步梳理思路，是细节局部更加严谨，最后修改正确；③更多的问题出现在了输出广义表的函数中，刚开始出现广义表的输出少括号或多括号的情况，这里有一局部原因是建立广义表的函数的问题，两局部同时作的修改。之后又出现输入复杂的广义表时，局部字母不能输出，多重括号的输出也只能输出两个，认真分析后，发现还是对广义表中右括号的处理不够完善，于是在输出时，进一步细化了输出结果的条件，比方对“〔a,b)”和“〔〕”这两种形式采取不同的输出条件和输出结果。在不断地查找问题和完善中，最终修改正确。运行界面五、实验总结因为本次实验花费了很多时间思考算法，所以在编写程序上花费的时间不算太多，我在10月26日晚上写完代码，并于当天修改正确。在本次编写程序过程中，问题主要发生在输出广义表的函数上，反复查找思路中不严谨的地方，结合对输入广义表的函数的修改，一点一点地改良，最后才得以修改正确。在上次试验完成后便开始思考和与别人讨论可以实现题目要求的算法，最初的算法不够完善，主要只考虑了简单的广义表，但是对广义表中出现多层括号等一些特殊情况的思考不够深入，在与同学进行了讨论后，最后确定下来本实验中所采用的思路。因为所用教材上对广义表的讲解很少，所以参考了一些其它资料。本次实验，我很感谢老师和同学对我的指点。通过本次实验，对广义表的存储结构有了更深的认识，对一些细节更加理解，收获了很多。教师评语： 首先，我强调一下要注意细节，不管是对你而言简单的局部还是复杂的局部，这些都会影响你程序的编译和调试，另外，在充分考虑并设计好程序后在进行编写操作这是一个良好的习惯，这样能够提高你的编程效率，降低出错的可能性，当然，最好的话细分模块是一个比拟好的习惯，当然这主要是针对大型程序而言。实验成绩：99指导教师签名：批阅日期：代码：#include<stdio.h>#include<stdlib.h>//——————————————————————————————————————————typedefstructLNode //广义表结点的类型描述{ inttag; //tag为结点中的标记域 chardata; //data用于存储广义表中的字母 structLNode*sublist,*next; //sublist为指向该结点下一层的指针，next为指向该结点同一层的指针}GLNode;//——————————————————————————————————————————typedefstruct //顺序栈的类型描述{ GLNode*pin[20]; //指针数组，用于存储广义表结点指针 inttop; //栈顶指针}SeqStack;//——————————————————————————————————————————voidCreate(GLNode*G,SeqStack&K,chars[]) //建立广义表函数{ GLNode*p,*q; //p指针指向当前结点,q指针指向新申请的结点 intj; //j用于标记输入的字符在数组中的位置 printf("输入广义表:"); //提示输入广义表的 gets(s); p=G; //令p指向头结点 p->next=NULL; //头结点的next域为空 for(j=0;s[j]!='\0';j++) //进入循环，建立广义表 { if(s[j]=='(') //假设字符为'('，执行以下操作 { p->tag=1; //当前结点的标记域赋值为1，表示存在子表 K.top++; //当前结点的指针进栈 K.pin[K.top]=p; q=(GLNode*)malloc(sizeof(GLNode)); //申请新结点 q->tag=0; //初始化新结点，标记域赋值为0，data域赋空字符 q->data=NULL; p->sublist=q; //当前结点的sublist域指向新申请的结点 p=q; //令新申请的结点成为当前结点 } else { if(s[j]==',') //假设字符为','，执行以下操作 { q=(GLNode*)malloc(sizeof(GLNode)); //申请新结点 q->tag=0; //初始化新结点，标记域赋值为0，data域赋空字符 q->data=NULL; p->next=q; //当前结点的next域指向新申请的结点 p=q; //令新申请的结点成为当前结点 } else { if(s[j]==')') //假设字符为')'，执行以下操作 { p->next=NULL; //令当前结点的next域为空 p=K.pin[K.top]; //出栈，令当前结点为栈顶元素 K.top--; } else //假设字符为字母，执行以下操作 { p->data=s[j]; //令当前结点的data域为该字母 p->sublist=NULL; //当前结点的sublist域为空 } } } }}//——————————————————————————————————————————voidDisplay(GLNode*G,SeqStack&K) //输出广义表的函数{ printf("输出结果为:"); //提示以下结果为输出的广义表 GLNode*p; //p指针指向当前结点 p=G; //初始时p指针指向头结点 K.top++; //指向头结点的指针入栈 K.pin[K.top]=p; printf("("); //输出第一个'(' p=p->sublist; //令当前结点的sublist域所指结点为新的当前结点 while(K.top!=-1) //当栈不为空时执行以下操作 { if(p!=NULL) //假设当前结点指针不为空，执行以下操作 { if(p->tag==1) //假设当前结点标记域为1,执行以下操作 { printf("("); //输出'(' K.top++; //当前结点指针入栈 K.pin[K.top]=p; p=p->sublist; //令当前结点的sublist域成为当前结点 } else //假设当前结点标记域为0,执行以下操作 { if(p->data!=NULL) //假设当前结点的date域存有字母那么输出该字母 printf("%c",p->data); if(p->next!=NULL)printf(","); //假设当前结点的next域不为空，表示不是该层的最后一个结点，输出',' p=p->next; //令当前结点的next域成为当前结点 } } else //假设当前结点指针为空，执行以下操作 { p=K.pin[K.top];