一元多项式的计算设计报告
班级：10信息与计算科学 学号： 姓名：
一：任务：能够按照指数降序排列建立并输出多项式；
能够完成两个多项式的相加、相减，并将结果输入；
二：需求分析
建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果
三：概要设计
存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，
只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1． 单连表的抽象数据类型定义：
ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ InitList（＆L） //操作结果：构造一个空的线性表 CreatPolyn(&L) //操作结果：构造一个以单连表存储的多项试 DispPolyn(L) //操作结果：显示多项试 Polyn(&pa,&pb) //操作结果：显示两个多项试相加，相减的结果 } ADT List 2． 本程序包含模块： typedef struct LNode //定义单链表 { }LNode,*LinkList; void InitList(LinkList &L) //定义一个空表 { } void CreatPolyn(LinkList &L) //用单链表定义一个多项式 { } void DispPolyn(LinkList L) //显示输入的多项式 { } void Polyn(LinkList &pa,LinkList &pb) {} void main() { //定义一个单连表； cout< 主程序模块 加法操作模块 减法操作模块 主函数 多项式链表 用户菜单 退出 指针数组 各函数 基本算法： 1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图1所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入 图表 1 开始 申请结点空间 输入多项式的项数 输入多项式各项的系数 x, 指数 y 输出已输入的多项式 否 是 是否输入正确 合并同类项 结束 2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图2所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 图表 2 开始 定义存储结果的空链 r 的空存储多项式1链P是否为空 否 的空存储多项式2 链Q是否为空 同指数项系数相加后存入r 输出存储多项式的和的链r 合并同类项 是 是 否 直接把q中各项存入r 直接把p中各项存入r结束 3、多项式的减法 （1）功能：将两多项式相减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图3所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 图表 3 合并同类项 输出存储多项式的和的链r 否 同指数项系数相加后存入r直接把q中各项存入r 把p中各项系数改变符号后存入存储多项式2的空链Q是否为空 存储多项式1的空链P是否为空 否 是 是 定义存储结果的空链 r 开始 结束 四．详细设计 1. 根据题目要求采用单连表存储结构 typedef struct LNode //定义单链表 { }LNode,*LinkList; void InitList(LinkList &L) //定义一个空表 { } void CreatPolyn(LinkList &L) //用单链表定义一个多项式 { } void DispPolyn(LinkList L) //显示输入的多项式 { } void Polyn(LinkList &pa,LinkList &pb) {} 2．主函数 main void main() { LNode *L1,*L2; Polyn(L1,L2); } 2. 函数的调用关系层次结构 多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输入的多项式 DispPolyn } 五. 调试分析 采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过程 中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两个多 项式的相加、相减;将从新得到的单连表结果输出；该算法的时间复杂度为两个 多项式的项式之和 六：调试结果 1. 测试的数据及结果 2. 算法的时间复杂度及改进 算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。 问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。 七. 心得体会：一元多项式计算是一个的单链表的运用， 通过这个程序可 以测我们以前的学习情 况，看看我们是否对单链表真正的理解。 一元多项式计算器的基本功能定为： (1) 建立多项式 (2) 输出多项式 (3) 两个多项式相加，建立并输出和多项式 (4) 两 个多项式相减，建立并输出差多项式能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输出； 源程序： #include 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(q2&&p->expn if(q2&&p->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;i printf(\"请输入第%d项的系数与指数:\ scanf(\"%f %d\ 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->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况 printf(\"%g\ if(q->expn==1) putchar('X'); else if(q->expn) printf(\"X^%d\ } else{ if(q->coef==1){ if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf(\"X^%d\ } if(q->coef==-1){ if(!q->expn) printf(\"-1\"); else if(q->expn==1) printf(\"-X\"); else printf(\"-X^%d\ } } q=q->next; flag++; }//while printf(\"\\n\"); }//PrintPolyn int compare(Polyn a,Polyn b){ if(a&&b){ if(!b||a->expn>b->expn) return 1; else if(!a||a->expn else if(!a&&b) return -1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 }//compare Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)){ case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } }//switch if(qc->coef!=0){ qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 }//while return headc; }//AddPolyn Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p){ //将pb的系数取反 p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1; return pd; }//SubtractPolyn int main(){ int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(\"请输入a的项数:\"); scanf(\"%d\ pa=CreatePolyn(pa,m);//建立多项式a printf(\"请输入b的项数:\"); scanf(\"%d\ pb=CreatePolyn(pb,n);//建立多项式a //输出菜单 printf(\"**********************************************\\n\"); printf(\"操作提示：\\n\1.输出多项式a和b\\n\2.建立多项式a+b\\n\3.建立多项式a-b\\n\"); printf(\"\4. 退 出 \\n**********************************************\\n\"); for(;;flag=0){ printf(\"执行操作：\"); scanf(\"%d\ if(flag==1){ printf(\"多项式a：\");PrintPolyn(pa); printf(\"多项式b：\");PrintPolyn(pb);continue; } if(flag==2){ pc=AddPolyn(pa,pb); printf(\"多项式a+b：\");PrintPolyn(pc); DestroyPolyn(pc);continue; } if(flag==3){ pd=SubtractPolyn(pa,pb); printf(\"多项式a-b：\");PrintPolyn(pd); DestroyPolyn(pd);continue; } if(flag==4) break; if(flag<1||flag>4) printf(\"Error!!!\\n\");continue; }//for DestroyPolyn(pa); DestroyPolyn(pb); return 0; } 因篇幅问题不能全部显示，请点此查看更多更全内容