一元多项式计算(数据结构课程设计).doc

《数据结构》课程设计报告学 号： 57 54 39 37 20 25 27 姓 名： 周田 张永鹏 武警 温凯侨 李坤 米昌华 阮健健 班 级： 10 计算机科学与技术（2）班 指导教师： 成 绩： 数学与计算机科学系池 州 学 院CHIZHOU COLLEGE一、 课程设计基本情况1、设计名称一元多项式计算2、主要功能能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；3、设计平台电脑、Visual c++ 6.0二、 系统设计1、算法思想根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减） ，若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算为了节省空间，我采用两个链表分别存放多项式a 和多项式 b，对于最后计算所得的多项式则利用多项式 a 进行存储。

主要用到了单链表的插入和删除操作1)一元多项式加法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点P 的指数小于 q 的指数的话就应该复制 q 的节点到多项式中P 的指数大于 q的指数的话，就应该复制 p 节点到多项式中当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生2)一元多项式的减法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点p的指数小于 q 的指数的话，就应该复制 q 的节点到多项式中P 的指数大于 q的指数的话就应该复制 p 的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数2、概要设计(1)主函数流程图：（注：a 代表第一个一元二次方程，b 代表第二个一元二次方程） 开 始定义结构体定义函数类型及名称构造指数比较函数排列顺序(降序）用单链接储存 a,b 项目的系数和指数开 始 进 行 加 减 法 运 算输 出 构 造 出 的 多 项 式指数不同输出多项式，求项数创建并初始化多项式链表输 入 系 数 和 指 数 指数相同合并同类项 按指数排序结 束将 单 链 表 的 节 点 释 放，使 已 建 立 的 多 项 式 销 毁a 项的指数值=b 项的指数值 选 择 语 句a 项指数值b 项指数值(2)一元多项式计算算法用类 C 语言表示：Typedef struct00{ //项的表示，多项式的项作为 LinkList 的数据元素Float coef； //细数Int expn；// 指数}term，ElemType ；//两个类型名： term 用于本 ADT，ElemType 为 LinkList 的数据对象名Typedef LinkList polynomial： //用带表头的节点的有序链表表示多项式//基本操作的函数原型说明Void CreatePolyn（polynomail&P ） ；//输入 n 的系数和指数，建立表示一元多项式的有序链表 P 销毁一元多项式PVoid DestroyPolyn（polynomailP） ；销毁一元多项式 PvoidPrintPoly（polynomail P ） ；//打印输入一元多项式 PIntPolynLength（polynnomail P);//返回一元多项式 P 中的项数void CreatPolyn（polynomail//完成多项式相加运算，即:Pa=Pa+Pb,并贤惠一元多项式 PbvoidSubtractPolyn（polunomail&Papolunomail&Pb） ；//完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式 Pb//基本操作的算法描述Int cmp(tem a，temp b） ；//依 a 的指数值b 的住数值，分别返回-1、0 和+1Void CreatePolyn（polynomail&P,int m){//输入 m 项的系数和指数，建立表示一元多项式的有序链表 PInitList（P） ； h=GetHead（P） ；E.coef=0.0； e.expn=-1； SerCurElem（h，e ） ；//设置头结点的数据元素For （i=1 ；izhishu==0) /*如果指数为 0 的话，直接输出系数*/ printf("%5.2f",p->xishu); /*如果系数是正的话前面就要加+ 号*/ else if(p->xishu==1||p->xishu==-1) printf("X^%d",p->zhishu); /*如果系数是 1 的话就直接输出+x*/ /*如果系数是-1 的话就直接输出-x 号*/ else if(p->xishu>0) /*如果系数是大于 0 的话就输出+系数 x^指数的形式*/ printf("%5.2fX^%d",p->xishu,p->zhishu); else if(p->xishuxishu,p->zhishu); one_time=0; } else{ if(p->zhishu==0) /*如果指数为 0 的话，直接输出系数*/ { if(p->xishu>0) printf("+%5.2f",p->xishu); /*如果系数是正的话前面就要加 +号*/ } else if(p->xishu==1) /*如果系数是 1 的话就直接输出+x 号*/ printf("+X^%d",p->zhishu); else if(p->xishu==-1) /*如果系数是-1 的话就直接输出-x 号*/ printf("X^%d",p->zhishu); else if(p->xishu>0) /*如果系数是大于 0 的话就输出+系数 x^指数的形式*/ printf("+%5.2fX^%d",p->xishu,p->zhishu); else if(p->xishuxishu,p->zhishu); } p=p->next; /*指向下一个指针 */ } printf("\n"); } (2)加法函数/*两个多项式的加法运算*/ pnode * add(pnode *heada,pnode *headb) { pnode *headc,*p,*q,*s,*r; /*headc 为头指针，r,s 为临时指针，p 指向第 1 个多项式并向右移动，q 指向第 2 个多项式并向右移动*/ float x; /*x 为系数的求和 */ p=heada; /*指向第一个多项式的头*/ q=headb; /*指向第二个多项式的头*/ headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/ r=headc; while(p!=NULL&&q!=NULL) /*2 个多项式的某一项都不为空时 */ { if(p->zhishu==q->zhishu) /*指数相等的话*/ { x=p->xishu+q->xishu; /*系数就应该相加*/ if(x!=0) /*相加的和不为 0 的话*/ { s=(pnode *)malloc(sizeof(pnode)); /*用头插法建立一个新的节点 */ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; } q=q->next;p=p->next; /*2 个多项式都向右移*/ } else if(p->zhishuzhishu) /*p 的系数小于 q 的系数的话，就应该复制 q 节点到多项式中*/ { s=(pnode *)malloc(sizeof(pnode)); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q 向右移动*/ } else/*p 的系数大于 q 的系数的话，就应该复制 p 节点到多项式中*/ { s=(pnode *)malloc(sizeof(pnode)); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p 向右移动*/ } } /*当第 2 个多项式空，第 1 个数不为空时，将第一个数剩下的全用新节点产生 */ while(p!=NULL) { s=(pnode *)malloc(sizeof(pnode)); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; } /*当第 1 个多项式空，第 1 个数不为空时，将第 2 个数剩下的全用新节点产生*/ while(q!=NULL) { s=(pnode *)malloc(sizeof(pnode)); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; } r->next=NULL; /*最后指向空 */ headc=headc->next; /*第一个头没有用到 */ return headc; /*返回头接点*/ } (3)减法函数/*两个多项式的加法运算*/ pnode * add(pnode *heada,pnode *headb) { pnode *headc,*p,*q,*s,*r; /*headc 为头指针，r,s 为临时指针，p 指向第 1 个多项式并向右移动，q 指向第 2 个多项式并向右移动*/ float x; /*x 为系数的求和 */ p=heada; /*指向第一个多项式的头*/ q=headb; /*指向第二个多项式的头*/ headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/ r=headc; while(p!=NULL&&q!=NULL) /*2 个多项式的某一项都不为空时 */ { if(p->zhishu==q->zhishu) /*指数相等的话*/ { x=p->xishu+q->xishu; /*系数就应该相加*/ if(x!=0) /*相加的和不为 0 的话*/ { s=(pnode *)malloc(sizeof(pnode)); /*用头插法建立一个新的节点 */ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; } q=q->next;p=p->next; /*2 个多项式都向右移*/ } else if(p->zhishuzhishu) /*p 的系数小于 q 的系数的话，就应该复制 q 节点到多项式中*/ { s=(pnode *)malloc(sizeof(pnode)); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q 向右移动*/ } else/*p 的系数大于 q 的系数的话，就应该复制 p 。