六《数据结构》实验一线性表一、实验目的：掌握线性表的基本操作及在链式存储结构上的实现。二、实验环境：PC机、TurboC或VisualC++三、实验描述：一元多项式的相加四、实验要求：（1）建立两个一元多项式A、B，按指数降序排列（2）实现A+B，输出其运算结果五、实验步骤：用带头结点的单链表存储多项式A、B，多项式的类型定义如下：typedefstruct{//项的表示，多项式的项作为LinkList的数据元素floatcoef；//系数intexpn；//指数}term,ElemType;typedefstructLnode{ElemTypedata;StructLnode*next;}*LinkList;typedefLinkListpolynomial；//用带头结点的有序（按指数递增）单链表表示多项式基本操作：intcmp(terma,termb)//比较a于b的指数，分别返回-1，0，1voidCreatPolyn(polynomial&p,intm)//输入m项的系数和指数，建立表示一元多项式的有序单链表pvoidPrintPolyn(polynomalp)//输出多项式的各项voidAddPolyn(polynomial&pa,polynomial&pb)//多项式相加：pa=pa+pb，利用两个多项式的结点构成“和多项式”程序流程polynomalA,B;//定义多项式A，Bintm,n;//定义多项式A，B的项数CreatPolyn(A,m);//创建有m项的多项式A，PrintPolyn(A);//输出多项式A；CreatPolyn(B,n);//创建有n项的多项式BPrintPolyn(B);//输出多项式BAddPolyn(A,B);//两个多项式相加A=A+BPrintPolyn(A);//输出相加的结果A测试数据：1）（2x+5x8-3.1x11）+(7-5x8+11x9)=(7+2x+11x9-3.1x11)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(x+x3)+(-x-x3)=0(x+x2+x3)+0=(x+x2+x3)实验二树一、实验目的：掌握二叉树的存储结构及先序、中序和后序三种基本遍历、层次遍历操作。二、实验环境：PC机、TurboC或VisualC++三、实验描述：二叉树的建立与遍历四、实验要求：（1）采用递归方式建立二叉树（2）采用非递归方式建立二叉树（3）采用先序、中序和后序三种方式遍历该二叉树（4）按层次遍历该二叉树五、实验步骤：定义二叉树的结点类型及二叉树类型（2）递归方式建立二叉树（算法参见课本）（3）三种方式遍历二叉树（算法参见课本）（4）层次遍历该二叉树（5）非递归方式（按层次）建立二叉树提示：以三元组（F，C，L/R）形式表示输入一棵二叉树的诸边（F：表示双亲结点的标识，C表示孩子结点标识，L/R表示作为F的左右孩子的标识）。创建一个队列BQ，用于将输入的二叉树每个结点的起始地址及结点的值保存起来按层次输入二叉树的每一个结点（以三元组形式），创建每一个新结点P，同时把该结点的起始地址及值入队BQ每输入一个三元组，查找BQ中与F相同的值（查找父结点的起始地址），根据L/R的信息，将该结点作为F的左或右孩子（F->Lchild=P或F->Rchild=P）程序流程创建二叉树；先序遍历二叉树中序遍历二叉树后序遍历二叉树按层次遍历该二叉树测试数据（略）实验三图一、实验目的：掌握图的存储结构及深度优先遍历和广度优先遍历操作。二、实验环境：PC机、TurboC或VisualC++三、实验描述：在连通的无向图上访问全部的结点四、实验要求：（1）以邻接表为存储结构，建立一个无向图（2）以用户指定的顶点为起点，实现图的深度和广度优先遍历，分别输出结点的访问序列五、实验步骤：定义邻接表的存储类型（见课本P163页）基本操作StatusCreateGraph(ALGraph&G)//采用邻接表表示法，构造无向图GvoidDFSTraverse(ALGraphG,Status(*Visit)(intv))//对图G作深度优先遍历voidBFSTraverse(ALGraphG,Status(*Visit)(intv))//对图G作广度优先遍历voidVisit(intv)//访问顶点v程序流程CreateGraph(ALGraph&G)DFSTraverse(ALGraphG,Status(*Visit)(intv))BFSTraverse(