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

池 州 学 院
CHIZHOU COLLEGE

《数据结构》
课程设计汇报

学 号： 57 54 39 37 20 25 27
姓 名： 周田 张永鹏 武警 温凯侨 李坤
米昌华 阮健健
班 级： 10计算机科学和技术（2）班
指导老师：
成 绩：

数学和计算机科学系
一、 课程设计基础情况

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项指数值
输 出 计 算 后 多 项 式
摘取b指数值到“和多项式”
按指数值按降序排列
摘取a指数值到“和多项式”
释放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 销毁一元多项式P
Void DestroyPolyn（polynomailP）；
销毁一元多项式P
voidPrintPoly（polynomail P）；
//打印输入一元多项式P
IntPolynLength（polynnomail P);
//返回一元多项式P中项数
void CreatPolyn（polynomail&Pa.polunomail&Pb);
//完成多项式相加运算，即:Pa=Pa+Pb,并贤惠一元多项式Pb
voidSubtractPolyn（polunomail&Papolunomail&Pb）；
//完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
//基础操作算法描述
Int cmp(tem a，temp b）；
//依a指数值<（或=）（或>b住数值，分别返回-1、0和+1
Void CreatePolyn（polynomail&P,int m){
//输入m项系数和指数，建立表示一元多项式有序链表P
InitList（P）； h=GetHead（P）；
E.coef=0.0； e.expn=-1； SerCurElem（h，e）；//设置头结点数据元素
For （i=1；i<=m；++i） { //依次输入m个非零项
Scanf（e.coef，e.epn）；
If（！LocateElem（P，e，q，（*cmp）（））） {//目前链表中不存在该指数项
If(MakeNode（s，e）） InsFirst（q，s）； //生成节点并插入链表
}
}
}//CreatPolun

三、 具体设计

1、算法实现

(1) 输入一元多项式函数：

void shuchu(pnode *head)
{
pnode *p;
int one_time=1;

p=head;

while(p!=NULL) /*假如不为空*/
{
if(one_time==1)
{
if(p->zhishu==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->xishu<0) /*假如系数是小于0话就输出系数x^指数形式*/
printf("%5.2fX^%d",p->xishu,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->xishu<0) /*假如系数是小于0话就输出系数x^指数形式*/
printf("%5.2fX^%d",p->xishu,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->zhishu<q->zhishu) /*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->zhishu<q->zhishu) /*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; /*返回头接点*/
}

2、 程序代码

/*一元多项式计算*/
/*程序功效：能够根据指数降序排列建立并输出多项式；能够完成两个多项式相加、相减，并将结果输出；*/
/*提醒：输入完一元多项式以后，输入“0 0”结束本一元多项式输入*/
/*注意：系数只正确到百分位，最大系数只能为999.99,指数为整数.假如需要输入更大系数，能够对程序中5.2%f进行对应修改*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>
/*建立结构体*/
typedef struct pnode
{
float xishu; /*系数 */
int zhishu; /*指数 */
struct pnode *next; /*下一个指针*/
}pnode;

/*用头插法生成一个多项式，系数和指数输入0时退出输入*/
pnode * creat()
{
int m;
float n;
pnode *head,*rear,*s; /*head为头指针，rear和s为临时指针*/

head=(pnode *)malloc(sizeof(pnode));
rear=head; /*指向头*/
scanf("%f",&n); /*系数*/
scanf("%d",&m); /*输入指数*/
while(n!=0) /*输入0退出*/
{
s=(pnode *)malloc(sizeof(pnode));
s->xishu=n;
s->zhishu=m;
s->next=NULL;
rear->next=s; /*头插法*/
rear=s;
scanf("%f",&n); /*输入系数*/
scanf("%d",&m); /*输入指数*/
}
head=head->next; /*第一个头没有用到*/
return head;
}
/*调整多项式*/
void tiaozhen(pnode *head)
{
pnode *p,*q,*t;
float temp;

p=head;
while(p!=NULL)
{
q=p;
t=q->next;

while(t!=NULL)
{
if(t->zhishu>q->zhishu)
q=t;
t=t->next;
}
temp=p->xishu;p->xishu=q->xishu;q->xishu=temp;
temp=p->zhishu;p->zhishu=q->zhishu;q->zhishu=temp;
p=p->next;
}
}

/*显示一个多项式*/
void shuchu(pnode *head)
{
pnode *p;
int one_time=1;

p=head;

while(p!=NULL) /*假如不为空*/
{
if(one_time==1)
{
if(p->zhishu==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->xishu<0) /*假如系数是小于0话就输出系数x^指数形式*/
printf("%5.2fX^%d",p->xishu,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->xishu<0) /*假如系数是小于0话就输出系数x^指数形式*/
printf("%5.2fX^%d",p->xishu,p->zhishu);
}
p=p->next; /*指向下一个指针*/
}
printf("\n");
}

/*两个多项式加法运算*/
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->zhishu<q->zhishu) /*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; /*返回头接点*/
}

/*两个多项式减法运算*/
pnode * sub(pnode *heada,pnode *headb)
{
pnode *headc,*p,*q,*s,*r;
float x; /*x为系数相减*/
p=heada; /*指向第一个多项式头*/
q=headb; /*指向第二个多项式头*/

headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/
r=headc;

while(p!=NULL&&q!=NULL) /*两个多项式某一项全部不为空时*/

{
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->zhishu<q->zhishu) /*p系数小于q系数话*/
{
s=(pnode *)malloc(sizeof(pnode));
s->xishu=-q->xishu; /*建立节点系数为原来相反数*/
s->zhishu=q->zhishu;
r->next=s;
r=s;
q=q->next;
}
else
{
s=(pnode *)malloc(sizeof(pnode));
s->xishu=p->xishu;
s->zhishu=p->zhishu;
r->next=s;
r=s;
p=p->next; /*p向右移动*/
}
}
while(p!=NULL) /*当第2个多项式空，第1个数不为空时，将第一个数剩下全用新节点产生*/
{
s=(pnode *)malloc(sizeof(pnode));
s->xishu=p->xishu;
s->zhishu=p->zhishu;
r->next=s;
r=s;
p=p->next;
}
while(q!=NULL) /*当第1个多项式空，第1个数不为空时，将第2个数剩下全用新节点产生*/
{
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; /*返回头接点*/
}
void add_main()
{
pnode * a,*b,*c;

printf("\n输入第一个一元多项式:\n系数 指数\n");
a=creat();
tiaozhen(a);

printf("\n输入第二个一元多项式:\n系数 指数\n");
b=creat();
tiaozhen(b);

c=add(a,b);

printf("第一个一元多项式以下:");shuchu(a);
printf("第二个一元多项式以下:");shuchu(b);
printf("两式相加以下:");shuchu(c);
}

void sub_main()
{
pnode * a,*b,*c;
printf("\n输入第一个一元多项式:\n系数 指数\n");
a=creat();
tiaozhen(a);

printf("\n输入第二个一元多项式:\n系数 指数\n");
b=creat();
tiaozhen(b);

c=sub(a,b);

printf("第一个一元多项式以下:");shuchu(a);
printf("第二个一元多项式以下:");shuchu(b);
printf("两式相减以下:");shuchu(c);
}
void open()
{
printf("\n ****************************************************\n");
printf(" 功效项: * 1 两个一元多项式相加;2 两个一元多项式相减;0 退出 *\n");
printf(" ****************************************************\n\n请选择操作: ");
}

void main()
{
int choose;
open();

while(choose!=0)
{
scanf("%d",&choose);
getchar();
switch(choose)
{
case 0:return;
case 1:
printf("\n 两个一元多项式相加\n");
add_main();choose=-1;open();break;
case 2:
printf("\n 两个一元多项式相减\n");
sub_main();choose=-1;open();break;
default:
printf("没有该选项!请重新选择操作!\n\n");
open();
}
}
}

四、 测试方案及结果

1、测试方案

在Visual C++ 6.0环境中调试运行。

2、结果及分析

程序运行截图以下：

五、 结论及体会

经过一周努力，最终我们课程设计出来了，主程序完全符合本课程设计要求。
此次课程设计对于我们来说难度是很大。因为对于数据结构课程设计，需要有扎实C语言编程能力，而我们这组人C编程全部通常。所以我们花了大半个星期时间才把主程序写出来。写过程中有不少挫折。我们刚开始是先写出一个能键盘输入两个一元二次方程并先对每一个方程按指数降序排序。但过了很长时间全部没法实现两函数相加减。以后花了很大力气，查阅了两本资料书才实现了对两函数相加（减），其实关键还是对链表插入和删除操作。
总来说此次课程设计学到了很多知识，让我们对C语言知识有了更多了解，也愈加深了对C语言和数据结构认识。对有些不懂知识点现在也掌握了，学会了链表建立，受益匪浅。

六、 任务分配

周田、张永鹏：编写修改主函数，并对设计汇报进行修改。

武警：给出程序设计方案，并画出程序步骤图。

李坤：编写C语言伪代码。

温凯侨：编写算法思想。

阮健健、米昌华：资料搜集及对课程设计总结。

七、评级
周田、张永鹏：A
武警、温凯侨、李坤：B
阮健健、米昌华：C