数据结构课程设计报告一元多项式计算2.doc

实验报告 2009级 信息与计算科学 2011年11月12日 姓名 王祎 学号 2009114112 实验题目 编写一个程序用单链表存储多项式，并实现两个多项式相加的函数 概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 基本算法： 1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图1所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入  2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图2所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 图表 2 3、多项式的减法 （1）功能：将两多项式相减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图3所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 详细设计 #includestdio.h #includemalloc.h typedef struct Polynomial{ float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h){ if(p-coef==0) free(p); //系数为0的话释放结点 else{ Polyn q1,q2; q1=h;q2=h-next; while(q2p-expnq2-expn){ //查找插入位置 q1=q2; q2=q2-next; } if(q2p-expn==q2-expn){ //将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef){ //系数为0的话释放结点 q1-next=q2-next; free(q2); } } else{ //指数为新时将结点插入 p-next=q2; q1-next=p; } } }//Insert Polyn CreatePolyn(Polyn head,int m){//建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head-next=NULL; for(i=0;im;i++){ p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(请输入第%d项的系数与指数:,i+1); scanf(%f %d,p-coef,p-expn); Insert(p,head); //调用Insert函数插入结点 } return head; }//CreatePolyn void DestroyPolyn(Polyn p){//销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next){ free(q1); q1=q2;//指针后移 q2=q2-next; } } void PrintPolyn(Polyn P){ Polyn q=P-next; int flag=1;//项数计数器 if(!q) { //若多项式为空，输出0 putchar(0); printf(\n); return; } while (q){ if(q-coef0flag!=1) putchar(+); //系数大于0且不是第一项 if(q-c