一元多项式的计算数据结构优秀课程设计.doc

一元多项式计算加，减 摘要(题目) 一元多项式计算任务：能够根据指数降序排列建立并输出多项式；能够完成两个多项式相加、相减，并将结果输入； 目录 1.引言 2.需求分析3.概要设计4.具体设计5.测试结果6.调试分析7.设计体会8.结束语一:引言:经过C语言使用链式存放结构实现一元多项式加法、减法和乘法运算。按指数降序排列。 二：需求分析建立一元多项式并根据指数降序排列输出多项式，将一元多项式输入并存放在内存中，能够完成两个多项式加减运算并输出结果三：概要设计存放结构：一元多项式表示在计算机内能够用链表来表示，为了节省存放空间，只存放多项式中系数非零项。链表中每一个结点存放多项式一个系数非零项，它包含三个域，分别存放该项系数、指数和指向下一个多项式项结点指针。创建一元多项式链表，对一元多项式运算中会出现多种可能情况进行分析，实现一元多项式相加、相减操作。1 单连表抽象数据类型定义： ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=| ai-1, aiD,i=2,n 基础操作： 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() /定义一个单连表； coutendl *欢迎来到一元多项式计算程序 * endl; LNode *L1,*L2; Polyn(L1,L2); 2.1 加，减操作模块实现加减操作 各模块之间调用关系以下： 主程序模块 加法操作模块 减法操作模块用户菜单多项式链表各函数退出指针数组主函数基础算法：1、输入输出（1）功效：将要进行运算多项式输入输出。（2）数据流入：要输入多项式系数和指数。（3）数据流出：合并同类项后多项式。（4）程序步骤图：多项式输入步骤图图1所表示。（5）测试关键点：输入多项式是否正确，若输入错误则重新输入 图表 1开始申请结点空间+num输入多项式项数指针数组tempi中（i=1num）输入多项式各项系数 x, 指数 y输出已输入多项式 合并同类项结束否是是否输入正确 2、多项式加法（1）功效：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后结果。（4）程序步骤图：多项式加法步骤图图2所表示。（5）测试关键点：两多项式是否为空，为空则提醒重新输入，不然，进行运算。图表 2开始定义存放结果空链 r是 否输出存放多项式和链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存放多项式2空链Q是否为空存放多项式1空链P是否为空合并同类项 3、多项式减法（1）功效：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后结果。（4）程序步骤图：多项式减法步骤图图3所表示。（5）测试关键点：两多项式是否为空，为空则提醒重新输入，不然，进行运算。 图表 3开始定义存放结果空链 r是 否输出存放多项式和链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存放多项式2空链Q是否为空存放多项式1空链P是否为空合并同类项 四具体设计 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#includetypedef 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-expnexpn) /查找插入位置 q1=q2; q2=q2-next; 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; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolynvoid 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-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1一般情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; /while printf(n);/PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空/comparePolyn 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;/AddPolynPolyn 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;/SubtractPolynint main() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式头指针，pa和pb在使用前付初值NULL printf(请输入a项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输入b项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式a /输出菜单 printf(*n); printf(操作提醒：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn); printf(t4.退出n*n); for(;flag=0) printf(实施操作：); scanf(%d,&flag); 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(flag4) printf(Error!n);continue; /for DestroyPolyn(pa); DestroyPolyn(pb); return 0;