数学与软件科学学院实验报告学期：2011至2012第2学期2012年3月16日课程名称:数据结构专业:信息与计算科学班级级班实验编号：实验二实验项目线性表及其基本操作实验指导教师：姓名：学号：实验成绩：一．实验目的(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序；(3)掌握线性表的顺序存储结构和动态存储结构之区分。二．实验内容(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算；(4)约瑟夫问题的求解。注：存储结构可以选用静态数组、动态数组、静态链表或动态链表之一。对链表也可以采用循环链表（含单向或双向）。三．实验准备1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。四．实验步骤注释：以下是实验报告的所有的程序代码可能用到的预处理语句有：#include<stdio.h>#include<stdlib.h>#include<conio.h>#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineOVERFLOW0#defineOK0#defineERROR0#defineTRUE1#defineFALSE01.问题描述输入两个形如的一元多项式Pa,Pb，然后对这两个多项式做加法运算并得出它们的结果，形式如下：Pc=Pa+Pb=a0+b0+(a1+b1)x+(a2+b2)x2+···(an+bn)xn2.算法的基本思想使用动态链表的结构来存储两个一元多项式的每项的系数与指数；先由用户输入两个一元多项式，然后分别输出两个一元多项式，求解两个多项式的加法运算的实质上就是先合并两个多项式的同类项，再输入x的值，然后对合并后的多项式采用一个循环的结构来求解此多项式的每一项的值，然后依次遍历链表的每个系数和指数来实现累加得到两个一元多项式作加法运算后的值。3.算法的数据结构（1）定义函数块返回的状态类型：typedefintStatus;一元多项式的存储结构的类型：/*PolyNodeisPolynomial’sanode,PolynisPolynomial’sname*/typedefstructPolyNode{floatcoef;/*Polynomial'scoefficient*/intexpn;/*Polynomial'sexponential*/structPolyNode*next;/*Pointtothenext*/}PolyNode,*Polyn;4.算法描述根据题意分析可知，一元多项式的加法运算可以分以下四个模块来进行编写程序代码：模块一：先创建两个需要做加法运算的一元多项式Pa,Pb;1.先分别输入一元多项式Pa,Pb的项数；/*InputthenumberofPolynomialPa*/printf("PleaseinputPolynomialPanumberofitems:");scanf("%d",&m);/*InputthenumberofPolynomialPb*/printf("PleaseinputPolynomialPbnumberofitems:");scanf("%d",&n);2.然后分配结点创建一元多项式Pa,Pb；heada=CreatePoly(m);/*createPolynomialPa*/DispPoly(heada);/*OutputPolynomialPa*/headb=CreatePoly(n);/*createPolynomialPb*/DispPoly(headb);/*OutputPolynomialPb*/模块二：对两个多项式进行求加法运算，得出运算后的多项式Pc;/*AddPolynomialPatoPb*/head=UnionPoly(heada,headb);DispPoly(head);/*OutputPolynomialPc*/模块三：输入多项式的x的值，并计算加法运算后的多项式Pc的值；/*InputPolynomial’sxvalue*/printf("Pleaseinputx'svalueis:");scanf("%d",&x);nSum=AddPoly(head,x);/*calculatePolynomial’svalue*/printf("PolynomialPaaddPbis%f",nSum);模块四：输出多项式加法运算后的值