数据结构课程设计报告

沈阳航空航天大学。

课程设计报告。

课程设计名称：数据结构课程设计。

课程设计题目：识别广义表头尾演示

院（系）：计算机学院。

专业：软件工程

班级：34010301

学号：2013040103030

姓名：张为

指导教师：丁一军

说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求、数据不实，不予通过。报告和电子数据必须作为实验现象重复的关键依据。

本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。

与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名日期：年月日。

本课程设计主要完成对广义表的建立以及遍历（输出），并且对已建立的广义表实施操作，操作序列为一串由“t”、“h”以及“”组成的字符串。“t”表示对广义表求表尾，“h”表示对广义表求表头，“”表示遍历当前整个广义表。

1.写一个程序，建立广义表的存储结构，演示在此存储结构上实现的广义表求头/求尾操作序列的结果。

2.广义表允许多行输入，其中可以任意输入空格符；

3.广义表存储结构自定；

4.对广义表的操作为一个由t和h组成的字符串；

设计一个广义表允许分多行输入，其中可以任意地输入空格符，原子是不限长的仅由字母或数字组成的串。广义表采用如教科书中图5.8所示结点的存储结构，按表头和表尾的分解方法编写建立广义表存储结构的算法。

对已建立存储结构的广义表施行操作，操作序列为一个仅由“t”（取表尾）或“h”（取表头）组成的串，它可以是空串（此时印出整个广义表），自左至右施行各种操作，再以符号形式显示结果。程序先进行广义表的输入，由程序进行广义表的建立，在打印出来，可检验广义表是否正确的建立。然后进行求头尾的操作序列的输入。

由程序进行对广义表进行求头尾的操作。程序中应该多次运用递归的思想，可以使程序显得更加的简洁高效。

图2.1 系统功能结构图。

建立广义表由函数void creatlist（glist &ls）完成。当用户完成对广义表的输入后，由此函数完成对广义表的建立。此函数运用递归的思想可以对广义表进行任意地建立。

能够输入空格字符，建立为空的广义表。广义表的节点可以为原子，也可以为广义表，能够进行循环的建立直到输入完成，或程序结束。

对广义表进行求头尾操作是由多个函数共同完成，分别是void gettail(glist &l void gethead(glist &ls)，void get_ht(glist ls)，void gl_elem(glist p) void printf_gl(glist ls,int &i)。当输入一串由t和h组成的操作序列后，由函数void get_ht(glist ls)，对求头尾进行函数的调用。如果是求头则调用gethead(glist &ls)，如果是求尾则调用void gettail(glist &ls)，而函数void gl_elem(glist p)是负责对广义表的原子节点进行输出，函数void printf_gl(glist ls,int &i)负责对广义表进行整个的输出。

广义表的存储结构采用的是链式存储结构，每个数据元素可用一个节点表示。由于列表中的数据元素可能为原子或列表，由此需要两种结点：原子结点和表结点。

前者用于表示原子，后者用于表示列表，一个表结点可由3个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需要两个域：标志域和值域。

广义表的存储结构定义形式为：

typedef struct glnode //广义表节点。

glist;

对广义表的结构采用链表的形式进行定义，由于广义表可以是原子也可以是表，所以在结构体中还采用了共用体的数据结构。让原子和节点可以共享存储单元。tag代表节点的类型0为原子，1为表。

hr代表表的头指针，tr代表表的尾指针。data为表的内容。

程序主体由几个关键函数组成：creatlist(glist&ls)、gl_elem(glistp)、printf_gl(glistls,int&i)、gethead(glist&ls)、gettail(glist&ls)、get_ht(glistls)以及main()函数中的三个部分，下面将对这些函数一一介绍。

单独的creatlist()函数并不能创建完整的广义表，需要与main()函数中的第一部分相结合才能共同完成广义表的创建。creatlist()在main中的调用如下：

char c;

c=getchar();

if(c!='

return -1，//广义表第一个字符必须是'('否则终止函数。

glist ls;

creatlist(ls);

在整个程序中采用getchar()函数从键盘缓冲区读取输入的广义表数据。creatlist()函数的完全**如下：

void creatlist(glist &ls ) 建广义表。

else当前输入的广义表非空。

glist p;

ls=(glist)malloc(sizeof(glnode));

ls->tag =1; /表结点。

if(c表头为单原子。

ls->hr=(glist)malloc(sizeof(glnode));

p=ls->hr;

p->tag =0;

p->data=c; /建立原子结点。

else表头为广义表。

creatlist(ls->hr); 对此广义表递归建立存储结构。

c=getchar();

if (c=='

creatlist(ls->tr); 当前广义表未结束，等待输入下一个子表。

else if(c=='

ls->tr =null当前广义表输入结束。

广义表是采用递归的方式定义的，因此creatlist()中广义表也是采用递归的方式建立的。

由于广义表的第一个字符“（”在main()函数中已被读取，因此creatlist()中从键盘数据缓冲区读取的第一个字符是所输入的广义表的第二个字符。若当层广义表非空，则应建立表结点。在建立原子结点时所用的判断方法为if(c!

=’是因为“,”之后的字符要么是“（”要么是原子。在经过**：if(c=='creatlist(ls->tr); 递归建立的广义表的读取的第一个字符只能是原子或者“(”而不可能是“,”因此建立原子结点的判断方法为if(c!

=’当getchar( )读取的字符为“(”时，表示要进入下一层广义表，故使用语句creatlist(ls->hr); 递归建立下一层广义表。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了