数据结构实验报告,广义表的创建与遍历

《数据结构实验报告,广义表的创建与遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》实验报告班级：姓名：学号：E-mail:日期:2012.11.1◎实验题目：广义表的创建和遍历◎实验目的：加深对广义表的理解，并能掌握其基本应用◎实验内容：创建一个广义表，对其进一、需求分析1、在本程序中，输入为所要创建的广义表，用一串字符串表示(左括弧，右括弧，逗号及原子)2、输出仍为字符串，即对已创建的广义表的遍历3、程序建立一个广义表，并对其进行遍历4、测试数据：输入：()输出：()二概要设计该函数为链式存储结构1.基本操作gets(b);操作结果：输入字符串p=create(s);操作结

2、果：创建广义表，返回广义表的头指针outlist(p);操作结果：输出创建的广义表2.本程序包含三个模块：(1)主函数模块(2)创建广义表模块三详细设计1.元素类型、结点类型、指针类型chartypedefstructGLNode{inttag;charatom;structGLNode*hp,*tp;}GList;typcdefstructnode{inttop;GList*a[maxsize];}St;char*s1.每个模块的分析：(1)主程序模块：intmain()//主函数{charb[maxsi

3、ze],*s;GList*p;printf("谙输入你所要建立的广义表的内容，以字符串的形式输入：V);gets(b);s=b;p=create(s);printf("输出的广义表为：〃)；outlist(p);return(0);}(2)构造广义表模块；GListCreate(char*s)//该函数用来构建一•个广义表{GList*p,*q,*head;//head指向广义表的头结点，p指向当前节点，q用來创建新结点StStack;Stack.top=-l;q=(GList*)malloc(len);p

4、=q;head=p;while(*s!=’)//循环，s指向的字符为空时结束{if(*s==’(’)//遇到左括弧，当前节点的tag标1，当前节点地址入栈，申请新结点，p指向新结点{p-〉tag=l;Stack.top++;Stack.a[Stack.top]=p;q=(GList本)mall()c(len);p->hp=q;p=p->hp;if(*++s^’)’)//如果左括弧后而紧跟着右拈弧，当前节点的表头和表尾皆赋值空p->hp=NULL;p->tp=NULL;elseif(*S==’，’)//遇

5、到逗号创建新节点，当前节点的表尾指针指向新结点，p指向新结点{q=(GList*)malloc(len);p->tp=q;p=p->tp;s十+;}elseif(*s==’)’)//遇到右括弧,表尾指针赋值空，栈顶元素出栈{p->tp=NULL;p=Stack.a[Stack,top];Stack,top~;s++;}else//遇到原子，当前节点tag赋值0,对当前结点原子赋相应值，当前节点表尾指针赋值空{p->tag=0;p-〉atom=*s;p-〉hp=NULL;s++;}}p->tp=NULL;//

6、最后一个结点表尾指针赋值空return(head);//返回头指针(1)输出广义表模块voidoutlist(GList*q)//该函数对广义表遍历{GList*p;//p指向当前结点Stsa;p=q;sa.top=~l;printf(，z(，z);sa.a[++sa.top]=p;p=p->hp;do{while(p->hp!=NULL

7、4-〉1口!=圖丄)//内循环，当前节点的表头表尾指针皆为空时结束{if(p-〉tag==0)printf(，z%c,/z,p->atom);p=p-〉tp;if（p-〉

8、tag==l）printf（"（〃）；sa.top++;sa.a[sa.top]=p;p=p->hp;}}if（p-〉tag==O）printf（〃％c",p->atom）;//当前节点tag等于0，输出原子printf（〃）〃）；//输出右柄弧p=sa.a[sa.top—];//栈顶元素出栈if（p-〉tp二NULL）//表尾结点为空且栈不为空时，输出右括弧，栈顶元素出栈{while（p->tp==NULL&&sa.top!=-l）{printf（〃）"）；p=sa.a[sa.top—];}}if（p-〉

9、tp!=NULL）//表尾指针不为空输出逗号{printf（"/O;p=p-〉tp;}}while（sa.top!=-l）;//栈为空时结束循环}1.完整的程序：（见源文件）.四使用说明、测试分析及结果1.程序使用说明(1)本程序的运行环境为VC6.0。(2)进入演示程序后即显示提示信息：请输入你所要建立的广义表的内容,以字符串的形式输入:输入字符串输出的广义表为:输出广义表2.测试结果当输入()时，输出为()3