最新数据结构一元多项式课程设计报告

《数据结构课程设计》报告学号：JV144033姓名：朱凌年级：2014级专业：软件工程指导老师：施东东黄晓梅完成日期：2016年9月安徽大学江淮学院理工部1一元多项式计算一、实验内容（一元多项式的计算问题）要求能够按照指数降序排列建立并输出一元多项式；能够完成两个一元多项式的相加、相减，并将结果输入二、需求分析本程序关键点是如何将输入的两个多项式相加、相减操作。①如何将输入的一元多项式按指数的降序排列②如何确定要输入的多项式的项数；③如何将输入的两个一元多项式显示出来。④如何将输入的两个一元多项式进行相加操作。⑤如何将输入的两个一元多项式进行相减操作。本程序是通过链表实现一元多项式的相加减操作。三、概要设计、详细设计（1）多项式的输入先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；（2）两个多项式的加法“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针A所指结点的指数值指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去；②指针A所指结点的指数值指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去；③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。图2相加得到的和多项式上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的2基本操作来完成。（3）两个多项式的减法两个多项式的减法实现，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反数c.coef=-c.coef;，然后多项式一和多项式二相加，这样就实现了多项式的相减。流程图如上。（4）两个多项式相加就是两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多形式”中的一项，所有指数不同的项均直接移位至“和多项式”中，流程图如图4：1、算法思想：（1）输入并建立多项式——InitList()（2）输入多项式，输出形式为整数序列，这个输入功能在主函数实现（3）多项式a和b相加，建立多项式a+b，输出相加的多项式——AddPolyn(A，B)（4）多项式a和b相减，建立多项式a-b，相减的功能调用的依然是相加的子函数2、算法描述：A:建立多项式链表多项式单链表可以用尾插法建表来生成。LNode*InitList()//创建链表{LNode*L;L=(LNode*)malloc(sizeof(LNode));L-next=NULL;return(L);}voidChaLNode(LNode*L,ElemTypex)//插入链表函数{LNode*s,*p;s=(LNode*)malloc(sizeof(LNode));s-data=x;p=L;while(p-next)p=p-next;s-next=NULL;p-next=s;}B:按照指数降序排列voidInvert(LNode*L)//逆序输出链表{LNode*p,*q,*r;p=L-next;q=p-next;while(q!=NULL){r=q-next;q-next=p;p=q;q=r;}3L-next-next=NULL;L-next=p;}C：比较if(a-expnb-expn)｛pre=p;p=p-next;｝//如果多项式a的指数小于多项式b的指数，则指针P后移if(a-expnb-expn)｛pre-next=q;pre=pre-next;q=q-next;｝//如果多项式a的指数小于多项式b的指数，q后移这个模块主要是比较两个多项式的指数大小D、两个一元多项式的相加while(p&&q)//判断q,p是不是为空，如果不为空则继续往下进行{a=p-data.expn;b=q-data.expn;if(ab){pre=p;p=p-next;//p后移}if(a==b){sum=p-data.coef+q-data.coef;//当a，b相等，即指数相同，则系数相加if(sum!=0)//判断sum是为0，如果不为0则保留该节点{p-data.coef=sum;B=q;pre=p;p=p-next;q=q-next；free(B);}Else//如果sum为0即系数为0，则删除该节点{temp=p;p=p-next;pre-next=p;free(temp);B=q;q=q-next;free(B);}}if(ab){pre-next=q;pre=pre-next;q=q-next;}}if(q)//如果q中还有剩余，那么把q中剩余的项加到pre-next中pre-next=q;return(A);}4两个一元多项式相加的法则是：两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多项式”中的一项；所有指数不同的项均直接移位至“和多项式”中。如果和为零，则删除该节点。E：输出一个一元多项式voidPrint(LNode*L)//输出多项式{LNode*p;intflag=0;floati=1.0;p=L-next;while(p){if(p-data.coef0)//系数小于0直接输出{if(p-data.coef!=-1){if(p-data.expn!=0){if(p-data.expn!=printf(%.2f*X^%-2f,p-data.coef,p-data.expn);if(p-data.expn==1)printf(%.2f*X,p-data.coef);}if(p-data.expn==0printf(%.2f,p-data.coef);}if(p-data.coef==-1){if(p-data.expn!=0){if(p-data.expn!=1)printf(-X^%-2f,p-data.expn);if(p-data.expn==1)printf(-X);}if(p-data.expn==0)printf(-%2f,i);}}if(p-data.coef0)//系数大于0时，考虑是否为第一项，是则去掉加号输出，不是则输出第一项{if(flag){if(p-data.coef!=1){if(p-data.expn!=0){if(p-data.expn!=1)printf(+%.2f*X^%-2f,p-data.coef,p-data.expn);if(p-data.expn==1)printf(+%.2f*X,p-data.coef);}if(p-data.expn==0)printf(+%.2f,p-data.coef);}if(p-data.coef==1){if(p-data.expn!=0){if(p-data.expn!=1)5printf(+X^%-2f,p-data.expn);elseprintf(+X);}if(p-data.expn==0)printf(+%.2f,i);}}if(!flag)//是第一项{if(p-data.coef!=1){if(p-data.expn!=0){if(p-data.expn!=1)printf(%.2f*X^%-2f,p-data.coef,p-data.expn);elseprintf(%.2f*X,p-data.coef);}if(p-data.expn==0)printf(%.2f,p-data.coef);}if(p-data.coef==1){if(p-data.expn!=0){if(p-data.expn!=1)printf(X^%-2f,p-data.expn);elseprintf(X);}if(p-data.expn==0)printf(%.2f,i);}}}if(p-data.coef==0)//系数为0直接输出0{printf(0);}p=p-next;flag++;}printf(\n);}F：一元多项式相减两个多项式的减法实现，并没有单独的建立一个子函数来实现这个功能，和多项式的相加一样，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反数c.coef=-c.coef;，然后多项式一和多项式二相加，这样就实现了多项式的相减，开6始我建立一个实现多项式减法的子函数，最后为了程序的简洁最后还是改成了调用多项式相加函数G：逆序输出链表的实现voidInvert(LNode*L)//逆序输出链表{LNode*p,*q,*r;p=L-next;q=p-next;while(q!=NULL){r=q-next;q-next=p;p=q;q=r;}L-next-next=NULL;L-next=p;}H、main（）主函数voidmain(){LNode*La,*Lb;ElemTypec;inta,i,k;for(;1;){La=InitList();Lb=InitList();Menu();printf(请选择功能：);scanf(%d,&k);printf(\n);switch(k){case1:printf(\t\t===========一元多项式相加===========\t\t);printf(\n\n\n输入多项式一的项数:);scanf(%d,&a);if(a=0){printf(a不能小于1!\n);printf(请从新输入多项式一的项数：);scanf(%d,&a);}for(i=0;ia;i++){printf(输入多项式一第%d项系数和指数:,i+1);scanf(%f%f,&c.coef,&c.expn);while((int)c.expn!=c.expn){printf(输入指数不是整数，请重新输入!);scanf(%f,&c.expn);}7ChaLNode(La,c);}printf(输入多项式二的项数:);scanf(%d,&a);if(a=0){printf(a不能小于1!\n);printf(请从新输入多项式一的项数：);scanf(%d,&a);}for(i=0;ia;i++){printf(输入多项式二第%d项系数和指数:,i+1);scanf(%f%f,&c.coef,&c.expn);while((int)c.expn!=c.expn){printf(输入指数不是整数，请重新输入!);scanf(%f,&c.expn);}ChaLNode(Lb,c);}printf(多项式一为：);Print(La);printf(\n);printf(多项式二为：);Print(Lb);printf(\n);printf(多项式和为：);AddPolyn(La,Lb);Invert(La)；Print(La);printf(\n);break;case0:break;default:printf(输入错误，重新输入!);}if(k==0)break;printf(\n\n\n);}}在主函数中调用函数进行多项式的输入、输出，运用选择语句来选择加法、减法进行操作四、调试分析调试中遇到的问题与解决办法1、语法错误及修改，编译中出现的语法问题主要在于子函数和变量的定义，括号的8配对，关键字和函数名的书写，以及库函数的规范使用，这些问题都可以通过提示，对应的将其解决2、我通过调试运行后发现，计算完成打印结果后马上就会退出。程序在运