中北大学
数据结构
课程设计说明书
2011年12月20日
1.设计任务概述（包括系统总体框图及功能描述）
在这次的课程设计中我选择的题目是顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。分别采用顺序结构和链式存储结构，利用多项得结果，最后得多项式中
不含有重复阶项和零系数得项。除此之外，还得分为降幂和升幂两种排序方式。
一元多项式计算器模块调用图
2.本设计所采用的数据结构（如：链表、栈、树、图等）
顺序存储结构和链式存储结构。
3.功能模块详细设计
本程序主要分为四大模块：
①主程序模块
②输入模块：通过Getpolyn函数输入
③输出模块（升幂降幂）：PrintPolyn函数实现输出
④数据处理模块（多项式的加减乘）：通过一元多项式的Polynomial基本操作实现
3.1 详细设计思想
动态链表结构下的一元多项式的加法、减法、乘法的实现。
设有一元多项式Am(x)和Bn(x).
Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm
Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn
实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。（1）输入形式和输入值范围：
输入的系数为float类型，输入的幂为int类型
请选择:1
请输入你要运算的第一个一元多项式的项数:
2
请输入第1项的系数和指数:
系数:1
指数:1
请输入第2项的系数和指数:
系数:1
指数:2
（2）输出形式
请选择:5
一元多项式A为：
x+x^2
一元多项式B为：
4x^4+5x^5+6x^6
（3）程序所能达到的功能
1) 首先判定多项式是否稀疏;
2) 采用动态存储结构实现;
3) 结果M(x)中无重复阶项和无零系数项；
4) 要求输出结果的升幂和降幂两种排列情况
（4）测试数据：包括正确地输入及其输出结果和含有错误的输入及其输出结果。
正确的输入：
请选择:5
一元多项式A为：
x+x^2
一元多项式B为：
4x^4+5x^5+6x^6
错误的输入：
请输入第1项的系数和指数:
系数:1
指数:1
请输入第2项的系数和指数:
系数:2
指数:1
输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式
请输入第1项的系数和指数:
……………………….
3.2 核心代码
#include
#include
typedef struct
{ float coef; //系数
int expn; //指数
}term;
typedef struct LNode
{ term data; //term多项式值
struct LNode *next;
}LNode,*LinkList;
typedef LinkList polynomail;
/*比较指数*/
int cmp(term a,term b)
{ if(a.expn>b.expn) return 1;
if(a.expn==b.expn) return 0;
if(a.expn else exit(-2); } /*又小到大排列*/ void arrange1(polynomail pa) { polynomail h=pa,p,q,r; if(pa==NULL) exit(-2); for(p=pa;p->next!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;)//大的沉底 { for(p=h;p->next!=r&&p!=r;p=p->next) if(cmp(p->next->data,p->next->next->data)==1) { q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; } r=p;//r指向参与比较的最后一个，不断向前移动 } } /*由大到小排序*/ void arrange2(polynomail pa) { polynomail h=pa,p,q,r; if(pa==NULL) exit(-2); for(p=pa;p->next!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;)//小的沉底 { for(p=h;p->next!=r&&p!=r;p=p->next) if(cmp(p->next->next->data,p->next->data)==1) { q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; } r=p;//r指向参与比较的最后一个，不断向前移动 } } /*打印多项式,求项数*/ int printpolyn(polynomail P) { int i; polynomail q; if(P==NULL) printf("无项！\n"); else if(P->next==NULL) printf("Y=0\n"); else { printf("该多项式为Y=");q=P->next;i=1; if(q->data.coef!=0&&q->data.expn!=0) { printf("%.2fX^%d",q->data.coef,q->data.expn); i++; } if(q->data.expn==0&&q->data.coef!=0) printf("%.2f",q->data.coef);//打印第一项 q=q->next; if(q==NULL) {printf("\n");return 1;} while(1)//while中，打印剩下项中系数非零的项， { if(q->data.coef!=0&&q->data.expn!=0) { if(q->data.coef>0) printf("+"); printf("%.2fX^%d",q->data.coef,q->data.expn); i++; } if(q->data.expn==0&&q->data.coef!=0) { if(q->data.coef>0) printf("+"); printf("%f",q->data.coef); } q=q->next; if(q==NULL) { printf("\n"); break; } } } return 1; } /*1、创建并初始化多项式链表*/ polynomail creatpolyn(polynomail P,int m) { polynomail r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode)); r=P; for(i=0;i { s=(LNode*)malloc(sizeof(LNode)); printf("请输入第%d项的系数和指数：",i+1); scanf("%f%d",&s->data.coef,&s->data.expn); r->next=s; r=s; } r->next=NULL; if(P->next->next!=NULL) { for(q=P->next;q!=NULL/*&&q->next!=NULL*/;q=q->next)//合并同类项for(p=q->next,r=q;p!=NULL;) if(q->data.expn==p->data.expn) { q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); } else { r=r->next; p=p->next; } } return P; } /*2、两多项式相加*/ polynomail addpolyn(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r;int j; p=pa->next;q=pb->next; newp=(LNode*)malloc(sizeof(LNode)); r=newp; while(p&&q) { s=(LNode*)malloc(sizeof(LNode)); switch(cmp(p->data,q->data)) {case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef+q->data.coef; if(s->data.coef!=0.0) { s->data.expn=p->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case 1: s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; }//switch }//while while(p) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; } while(q) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; } r->next=NULL; for(q=newp->next;q->next!=NULL;q=q->next)//合并同类项for(p=q;p!=NULL&&p->next!=NULL;p=p->next) if(q->data.expn==p->next->data.expn) { q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); } printf("升序1 , 降序2\n"); printf("选择:"); scanf("%d",&j); if(j==1) arrange1(newp); else arrange2(newp); return newp; } /*3、两多项式相减*/ polynomail subpolyn(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r,Q; int j; p=pa->next;q=pb->next; newp=(LNode*)malloc(sizeof(LNode)); r=newp; while(p&&q) { s=(LNode*)malloc(sizeof(LNode)); switch(cmp(p->data,q->data)) {case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef-q->data.coef; if(s->data.coef!=0.0) { s->data.expn=p->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case 1: s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; }//switch }//while while(p) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; } while(q) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; } r->next=NULL; if(newp->next!=NULL&&newp->next->next!=NULL)//合并同类项{ for(q=newp->next;q!=NULL;q=q->next) for(p=q->next,r=q;p!=NULL;) if(q->data.expn==p->data.expn) { q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); } else { r=r->next; p=p->next; } } printf("升序1 , 降序2\n"); printf("选择:"); scanf("%d",&j); if(j==1) arrange1(newp); else arrange2(newp); return newp;} /*4两多项式相乘*/ polynomail mulpolyn(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode)); r=newp; for(p=pa->next;p!=NULL;p=p->next) for(q=pb->next;q!=NULL;q=q->next) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef*q->data.coef; s->data.expn=p->data.expn+q->data.expn; r->next=s; r=s;} r->next=NULL; printf("升序1 , 降序2\n"); printf("选择:"); scanf("%d",&j); if(j==1) arrange1(newp); else arrange2(newp); for(;i!=0;i--) {for(q=newp->next;q->next!=NULL;q=q->next)//合并同类项for(p=q;p!=NULL&&p->next!=NULL;p=p->next) if(q->data.expn==p->next->data.expn) { q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); } } return newp; } /*5、销毁已建立的两个多项式*/ void delpolyn(polynomail pa,polynomail pb) { polynomail p,q; p=pa; while(p!=NULL) { q=p; p=p->next; free(q); } p=pb; while(p!=NULL) { q=p; p=p->next; free(q); } printf("两个多项式已经销毁\n"); } void main() { polynomail pa=NULL,pb=NULL; polynomail p,q; polynomail addp=NULL,subp=NULL,mulp=NULL; int n,m; int sign='y'; printf("1、创建两个一元多项式\n"); printf("2、两多项式相加得一新多项式\n"); printf("3、两多项式相减得一新多项式\n"); printf("4、两多项式相乘得一新多项式\n"); printf("5、销毁已建立的两个多项式\n"); printf("6、退出\n"); printf("\n"); while(sign!='n') { printf("请选择："); scanf("%d",&n); switch(n) {case 1: if(pa!=NULL) { printf("已建立两个一元多项式，请选择其他操作！"); break; } printf("请输入第一个多项式：\n"); printf("要输入几项："); scanf("%d",&m); while(m==0) { printf("m不能为0，请重新输入m:"); scanf("%d",&m); } pa=creatpolyn(pa,m); printpolyn(pa); printf("请输入第二个多项式：\n"); printf("要输入几项："); scanf("%d",&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa==NULL) { printf("请先创建两个一元多项式！\n"); break; } addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa==NULL) { printf("请先创建两个一元多项式！\n"); break; } subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa==NULL) { printf("请先创建两个一元多项式！\n"); break; } mulp=mulpolyn(pa,pb); printpolyn(mulp); break; case 5: if(pa==NULL) { printf("请先创建两个一元多项式！\n"); break; } delpolyn(pa,pb); pa=pb=NULL; break; case 6: if(addp!=NULL) { p=addp; while(p!=NULL) { q=p; p=p->next; free(q); } } if(subp!=NULL) { p=subp; while(p!=NULL) { q=p; p=p->next; free(q); } } exit(-2); }//switch }//while } …………………………… 3.3 程序运行结果（拷屏） 程序运行后初始界面 创建两个多项式 两个多项式的加法、减法乘法运算以及结果以升幂和降幂形式排列 4.课程设计心得、存在问题及解决方法 该程序基本实现了要求的顺序结构、动态链表结构下的一元多项式的加法、减法、乘法等功能。代码较为冗余，可读性较差，可以多添加一些提示语句以及注释。 编写的程序不但要拿来使用，还要给别人查看，以便代码的维护。所以代码编写的风格尽量规范，清晰。变量要尽量少定义，结构夜采用简单的。另外，对指针的使用要小心，尽量在定义的时候就进行初始化，避免野指针，指针的使用涉及到内存的分配。 在这次课程设计中我又进一步地了解了数据结构中算法的核心思想的重要性，懂得了一个程序地好坏关键在于算法是否优秀，一个好的优秀的算法可以使我们的程序更加完善，安全性更高以及有更高的效率。这次设计中我发现了自己的许多不足，如对指针的机制掌握的还不是很透彻，有的时候会出现指针指向错误以及空指针的错误,还有不能很好地分析自己算法地复杂度以及不能很好地使用控制机制使自己的程序流畅地运行。