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

一元多项式计算—加，减

摘要(题目) 一元多项式计算
任务：能够根据指数降序排列建立并输出多项式；
能够完成两个多项式相加、相减，并将结果输入；

目录

1.引言
2.需求分析
3.概要设计
4.具体设计
5.测试结果
6.调试分析
7.设计体会
8.结束语

一:引言:
经过C语言使用链式存放结构实现一元多项式加法、减法和乘法运算。按指数降序排列。

二：需求分析
建立一元多项式并根据指数降序排列输出多项式，将一元多项式输入并存放在内存中，能够完成两个多项式加减运算并输出结果

三：概要设计
存放结构：一元多项式表示在计算机内能够用链表来表示，为了节省存放空间，只存放多项式中系数非零项。链表中每一个结点存放多项式一个系数非零项，它包含三个域，分别存放该项系数、指数和指向下一个多项式项结点指针。创建一元多项式链表，对一元多项式运算中会出现多种可能情况进行分析，实现一元多项式相加、相减操作。
1． 单连表抽象数据类型定义：
ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={<ai-1,ai>| ai-1, ai∈D,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()
{
//定义一个单连表；
cout<<endl<<" *****************欢迎来到一元多项式计算程序
*************** "<<endl;
LNode *L1,*L2;
Polyn(L1,L2); }
2.1 加，减操作模块——实现加减操作
各模块之间调用关系以下：

主程序模块

加法操作模块 减法操作模块

用户菜单
多项式链表
各函数
退出
指针数组
主函数
基础算法：
1、输入输出
（1）功效：将要进行运算多项式输入输出。
（2）数据流入：要输入多项式系数和指数。
（3）数据流出：合并同类项后多项式。
（4）程序步骤图：多项式输入步骤图图1所表示。
（5）测试关键点：输入多项式是否正确，若输入错误则重新输入

图表 1

开始
申请结点空间
+++++++++++++++++++++++++++++++++++++++++++++++++++++++

num
输入多项式项数

指针数组temp[i]中（i=1~num）
输入多项式各项系数 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<stdio.h>
#include<malloc.h>
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<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
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<m;i++){
p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据
printf("请输入第%d项系数和指数:",i+1);
scanf("%f %d",&p->coef,&p->expn);
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",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");
}//PrintPolyn
int compare(Polyn a,Polyn b){
if(a&&b){
if(!b||a->expn>b->expn) return 1;
else if(!a||a->expn<b->expn) return -1;
else return 0;
}
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",&m);
pa=CreatePolyn(pa,m);//建立多项式a
printf("请输入b项数:");
scanf("%d",&n);
pb=CreatePolyn(pb,n);//建立多项式a
//输出菜单
printf("**********************************************\n");
printf("操作提醒：\n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n");
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(flag<1||flag>4) printf("Error!!!\n");continue;
}//for
DestroyPolyn(pa);
DestroyPolyn(pb);
return 0;
}