专业课程设计一元稀疏多项式计算器程序

课程设计结果学院:计算机工程学院班级:计算机科学和技术班学生姓名:学号:设计地点（单位）：

设计题目:一元稀疏多项式计算器程序完成日期：年月日成绩(五级记分制):________________老师署名:_________________________

荆楚理工学院课程设计任务书设计题目：学生姓名王巍课程名称数据结果13级计算机科学和技术1班地点起止时间设计内容及要求设计参数进度要求参考资料其它说明1.本表应在每次实施前一周由负责老师填写二份，教研室审批后交学院院立案，一份由负责老师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用，在设计内容、参数、要求等方面应有所区分。教研室主任：指导老师：目录1需求分析 12设计概要 22.1基础结构 22.2基础功效模块图 23算法思想 33.1建立多项式 33.2多项式相加 33.3多项式相减 33.4链表输出 34具体设计 44.1函数功效介绍 44.2结构体定义 44.3产生链表函数 44.4插入结点 54.5多项式相加函数 54.6多项式相减函数 74.7主函数 75 测试结果及运行效果 10参考文件 13附录全部代码 141需求分析1、一元多项式简单计算器基础功效是：1.1输入并建立多项式；1.2输出多项式，输出形式为整数序列n,c1,e1,c2,e2,…,cn,en，其中n是多项式项数，ci和ei分别是第I项系数和指数，序列指指数降序排列；1.3多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。实现提醒：用带头结点单链表存放多项式，多项式项数存在头结点2、设计思绪：2.1定义线性表动态分配次序存放结构；2.2建立多项式存放结构，定义指针*next2.3利用链表实现队列结构。每次输入一项系数和指数，能够输出结构一元多项式2.4演示程序以用户和计算机对话方法实施，即在计算机终站上显示“提醒信息”以后，由用户在键盘上输入演示程序中要求运行命令；最终依据对应输入数据（滤去输入中非法字符）建立多项式和多项式相加运行结果在屏幕上显示。多项式显示格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思绪分析：要处理多项式相加，必需要有多项式，所以必需首先建立两个多项式，在这里采取链表方法存放链表，所以我将结点结构体定义为序数coef指数expn指针域next利用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b求和运算等同于单链表插入问题（将单链表polynp中结点插入到单链表polynh中），所以“和多项式”中结点无须另生成。为了实现处理，设p、q分别指向单链表polya和polyb目前项，比较p、q结点指数项，由此得到下列运算规则：①若p->expn<q->expn，则结点p所指结点应是“和多项式”中一项，令指针p后移。②若p->expn=q->expn，则将两个结点中系数相加，当和不为0时修改结点p系数。③若p->expn>q->expn，则结点q所指结点应是“和多项式”中一项，将结点q插入在结点p之前，且令指针q在原来链表上后移。2设计概要2.1基础结构1、元素类型、结点类型和指针类型：typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;2、建立一个头指针为head、项数为m一元多项式,建立新结点以接收数据,调用Insert函数插入结点: PolynCreatePolyn(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));printf("请输入第%d项系数和指数:",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head); }returnhead;3、主函数和其它函数：voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;}floatValuePolyn(Polynhead,intx)//输入x值，计算并返回多项式值2.2基础功效模块图3算法思想3.1建立多项式一元多项式是由多个项和组成，将一元多项式每个项用一结点表示，该结点中应包含该项系数、该项指数、指向下一项指针，能够用线性表来依次输入各项结点，从而完成多项式链表建立，为了使原多项式各项次序不变，故采取尾插法建表。3.2多项式相加多项式相加关键是经过将多项式每一项指数cxpn进行比较，当指数expn相同时，将两个结点中系数coef相加存放在第一个链表中，然后释放第二条链表中这个结点。当两个结点中指数expn不相同时，按高次在前低次在后降序插入到链表当中。3.3多项式相减多项式相减过程，其实就是相同指数项系数相减，对于不一样指数项，若是被减多项式，则将该结点复制输出，若是减多项式，则将该结点系数变为原系数相反数输出，将结果用降幂输出函数输出。3.4链表输出 PrintPolyn(PolynP)函数接收链表头结点地址，然后依次输出两个链表合并后链表中每个结点中系数和指数。4具体设计4.1函数功效介绍voidmain()//该函数依据用户选择，完成指定操作函数并依据用户选择，完成指定操作PolynCreatePolyn(Polynhead,intm)/*制造链表头结点，并调用voidInsert(Polynp,Polynh)函数实现依据多项式项数创建对应数量个节点链表*/voidInsert(Polynp,Polynh)/*向存放链表多项式中插入结点*/voidDestroyPolyn(Polynp)/*该函数用来释放结点，在加减操作中当多项式一项系数为0或两项指数相同进行相加或相减时可用次函数来释放对应结点*/intcompare(Polyna,Polynb)//该函数用于判定两个链表在加减状态中结点状态PolynAddPolyn(Polynpa,Polynpb)//该函数用于实现多项式相加操作PolynSubtractPolyn(Polynpa,Polynpb)//该函数用于实现多项式相减操作floatValuePolyn(Polynhead,intx)//该函数用于对多项式求值voidPrintPolyn(PolynP)//该函数用于链表输出4.2结构体定义typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;//指向结构体指针}*Polyn,Polynomial;定义一个结构体，结构体中包含3个组员分别是：folat型coef用于存放多项式中一项系数,int型expn用于存放多项式中一项指数，指向结构体本身类型指针next，定义了结构体我们就可用利用创建一个单链表方法对一个多项式各项系数和指数进行存放、处理。4.3产生链表函数PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf("请输入第%d项系数和指数:",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//调用Insert函数插入结点 }returnhead;}CreatePolyn函数接收两个参数，分别是链表头结点和多项式项数，使head指向链表头结点，然后利用for语句循环调用Insert函数，这么就能够动态分配内存，依据用户输入项数来制造结点。4.4插入结点 voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系数为0话释放结点else {Polynq1,q2;q1=h; q2=h->next;while(q2&&p->expn<q2->expn) {//查找插入位置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; } }}Insert函数接收两个指针，分别是p(p永远指向带插入那个结点)，和链表头指针，首先依次判定链表中每个结点中组员coef（多项式系数）是否为0，假如为0则释放该结点，若系数不为0，则经过q1、q2查找插入结点位置。4.5多项式相加函数PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc->next=NULL;headc=hc;while(qa||qb) {qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1: {qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break; }case0: {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; } }if(qc->coef!=0) {qc->next=hc->next;hc->next=qc;hc=qc; }elsefree(qc);//当相加系数为0时，释放该结点 }returnheadc;}PolynAddPolyn(Polynpa,Polynpb)函数接收链表a、链表b头结点便于实现对两个多项式进行操作，在函数中又调用intcompare(Polyna,Polynb)，a多项式已空，但b多项式非空函数返回-1，b多项式已空，但a多项式非空，不一样返回值，能够明确让PolynAddPolyn(Polynpa,Polynpb)进行对应操作。4.6多项式相减函数PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b，返回其头指针Polynh=pb;Polynp=pb->next;Polynpd;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;returnpd;}floatValuePolyn(Polynhead,intx){//输入x值，计算并返回多项式值 Polynp;inti,t; floatsum=0;for(p=head->next;p;p=p->next) {t=1;for(i=p->expn;i!=0;) {if(i<0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法 }sum+=p->coef*t; }returnsum;}PolynSubtractPolyn(Polynpa,Polynpb)函数作用用于进行多项式相减操作，其实现方法实质是在调用PolynAddPolyn(Polynpa,Polynpb)函数同时将被减多项式每项系数取其相反数进行相加运算。4.7主函数 voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;printf("请输入a项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式aprintf("请输入b项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式b//输出菜单printf("**************************************************\n");printf("*多项式操作程序*\n");printf("**\n"); printf("*A:输出多项式aB:输出多项式b*\n"); printf("**\n"); printf("*C:代入x值计算aD:代入x值计算b*\n"); printf("**\n"); printf("*E:输出a+bF:输出a-b*\n"); printf("**\n");printf("*G:退出程序*\n"); printf("**\n");printf("*************************************************\n"); while(a) {printf("\n请选择操作：");scanf("%c",&flag); switch(flag) { case'A': case'a': { printf("\n多项式a="); PrintPolyn(pa); break; } case'B': case'b': { printf("\n多项式b="); PrintPolyn(pb); break; }case'C': case'c': { printf("输入x值：x="); scanf("%d",&x); printf("\nx=%d时，a=%.3f\n",x,ValuePolyn(pa,x)); break; }case'D': case'd': { printf("输入x值：x="); scanf("%d",&x); printf("\nx=%d时，b=%.3f\n",x,ValuePolyn(pb,x)); break; } case'E': case'e': { pc=AddPolyn(pa,pb);printf("\na+b="); PrintPolyn(pc); break; }case'F': case'f': { pc=SubtractPolyn(pa,pb);printf("\na-b="); PrintPolyn(pc); break; } case'G': case'g': { printf("\n感谢使用此程序！\n"); DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; }default: printf("\n您选择错误，请重新选择!\n"); } }}主函数，运行以后出现欢迎使用界面并提醒用户输入，多项式项数，每项系数，指数由用户依次输入。然后程序反馈给用户一个对两个多项式进行对应操作提醒，程序用switch语句实现用户依据提醒键入对应字符便调用实现对应函数，若输入字符超不在程序提醒输入字符集合内则输出“您选择错误，请重新选择!”。5 测试结果及运行效果程序运行后出现“欢迎使用”信息，用户依据提醒输入多项式a项数，图6-1，始建立第一个多项式。图5-1程序运行后界面以a=2X2+X5+1,b=X2+3X4+X+X3为例键入多项式项数，各项指数、系数，程序提醒用户键入需进行操作相对应字符，图6-2：图5-2输入多项式信息后键入对应字符后，程序实现了用户所需求功效，经数次测试，程序运行得到结果正确无误，达成设计此程序目标，以之前输入两个多项式为例，键入对应命令按钮，程序进行对应操作，图6-3所表示：图5-3输入对应操作命令后得到结果参考文件[1]刘觉夫,王更生等编著.C++程序设计.北京：北京邮电大学出版社,.[2]曾辉,王更生,李广丽等编著.C++程序设计实训教程.北京：北京邮电大学出版社,1998.[3]谭浩强编著.C++面向对象程序设计.北京：北京清华大学出版社,.[4]谭浩强.C++面向对象程序设计.北京：清华大学出版社，.[5]谭浩强.C++程序设计实践指导.北京：清华大学出版社,.[6]刘玉英,张怡芳等.C++试验指导和课程设计.人民邮电出版社,.附录全部代码#include<stdio.h>#include<stdlib.h>//定义多项式项typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系数为0话释放结点else {Polynq1,q2;q1=h; q2=h->next;while(q2&&p->expn<q2->expn) {//查找插入位置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; } }}PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf("请输入第%d项系数和指数:",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//调用Insert函数插入结点 }returnhead;}voidDestroyPolyn(Polynp){//销毁多项式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next) {free(q1);q1=q2;q2=q2->next; }}voidPrintPolyn(PolynP){ Polynq=P->next;intflag=1;//项数计数器if(!q) {//若多项式为空，输出0putchar('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",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn); }else {if(q->coef==1) {if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn); }if(q->coef==-1) {if(!q->expn)printf("-1");elseif(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn); } }q=q->next;flag++; }printf("\n");}intcompare(Polyna,Polynb){if(a&&b) {if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->expn)return-1;elsereturn0; }elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc->next=NULL;headc=hc;while(qa||qb) {qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1: {qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break; }case0: {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; } }if(qc->coef!=0) {qc->next=hc->next;hc->next=qc;hc=qc; }elsefree(qc);//当相加系数为0时，释放该结点 }returnheadc;}PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b，返回其头指针Polynh=pb;Polynp=pb->next;Polynpd;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;returnpd;}floatValuePolyn(Polynhead,intx){//输入x值，计算并返回多项式值 Polynp;inti,t; floatsum=0;for(p=head->next;p;p=p->next) {t=1;for(i=p->expn;i!=0;) {if(i<0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法 }sum+=p->coef*t; }returnsum;}voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;printf("请输入a项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式aprintf("请输入b项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式b//输出菜单 printf("*A:输出多项式aB:输出多项式b*\n"); printf("*