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

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

课程设计成果

学 院: 计算机工程学院 班 级: 计算机科学与技术 班
学生姓名: 学 号:
设计地点（单位）：
设计题目: 一元稀疏多项式计算器程序

完成日期： 年 月 日

成绩(五级记分制):_____ _ __________
教师签名:__________ _______________

荆楚理工学院课程设计任务书
设计题目：
学生姓名
王巍
课程名称
数据结果
专业班级
13级计算机科学与技术1班
地 点

起止时间

设计内容及要求

设计
参数

进度
要求

参考资料

其它

说明
1.本表应在每次实施前一周由负责教师填写二份，教研室审批后交学院院备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。
教研室主任： 指导教师： 年 月 日

目 录

1 需求分析 1
2 设计概要 2
2.1基本结构 2
2.2 基本功能模块图 2
3算法思想 3
3.1建立多项式 3
3.2多项式相加 3
3.3多项式相减 3
3.4链表的输出 3
4 详细设计 4
4.1 函数功能介绍 4
4.2结构体的定义 4
4.3产生链表函数 4
4.4插入结点 5
4.5多项式的相加函数 5
4.6多项式相减函数 7
4.7主函数 7
5 测试结果及运行效果 10
参考文献 13
附录 全部代码 14

1 需求分析
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 建立多项式存储结构，定义指针*next
2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式
2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en
3、设计思路分析：
要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为
序数coef
指数expn
指针域next
运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。
为了实现处理，设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、元素类型、结点类型和指针类型：
typedef struct Polynomial{
float coef; //系数
int expn; //指数
struct Polynomial *next;
}*Polyn,Polynomial;
2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点:
Polyn CreatePolyn(Polyn head,int 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);
}
return head;
3、主函数和其他函数：
void main()
{
int m,n,a,x;
char flag;
Polyn pa=0,pb=0,pc;
}
float ValuePolyn(Polyn head,int x) //输入x值，计算并返回多项式的值
2.2 基本功能模块图

3算法思想
3.1建立多项式
一元多项式是由多个项的和组成的，将一元多项式的每个项用一结点表示，该
结点中应包括该项的系数、该项的指数、指向下一项的指针，可以用线性表来
依次输入各项结点，从而完成多项式链表的建立，为了使原多项式各项顺序不
变，故采用尾插法建表。
3.2多项式相加
多项式的相加主要是通过将多项式的每一项的指数cxpn进行比较，当指数expn相同时，将两个结点中的系数coef相加存放在第一个链表中，然后释放第二条链表中的这个结点。当两个结点中的指数expn不相同时，按高次在前低次在后降序的插入到链表当中。
3.3多项式相减
多项式的相减过程，其实就是相同指数的项的系数相减，对于不同指数的项，若是被减多项式，则将该结点复制输出，若是减多项式，则将该结点的系数变为原系数的相反数输出，将结果用降幂输出函数输出。
3.4链表的输出
PrintPolyn(Polyn P)函数接收链表的头结点地址，然后依次输出两个链表合并后的链表中的每个结点的中的系数和指数。

4 详细设计
4.1 函数功能介绍
void main() //该函数根据用户的选择，完成指定的操作函数并根据用户的选择，完成指定的操作

Polyn CreatePolyn(Polyn head,int m) /*制造链表的头结点，并调用void Insert(Polyn p,Polyn h)函数实现根据多项式项数创建对应数量个节点的链表 */

void Insert(Polyn p,Polyn h) /*向存储链表的多项式中插入结点 */

void DestroyPolyn(Polyn p) /* 该函数用来释放结点，在加减操作中当多项式一项的系数为0或两项的指数相同进行相加或相减时可用次函数来释放对应的结点*/

int compare(Polyn a,Polyn b) //该函数用于判断两个链表在加减状态中结点的状态

Polyn AddPolyn(Polyn pa,Polyn pb) //该函数用于实现多项式的相加操作

Polyn SubtractPolyn(Polyn pa,Polyn pb) //该函数用于实现多项式的相减操作

float ValuePolyn(Polyn head,int x) //该函数用于对多项式求值

void PrintPolyn(Polyn P) //该函数用于链表的输出
4.2结构体的定义
typedef struct Polynomial{
float coef; //系数
int expn; //指数
struct Polynomial *next; //指向结构体的指针
}*Polyn,Polynomial;
定义一个结构体，结构体中包含3个成员分别是：folat型的coef用于存放多项式中一项的系数,int型的expn用于存放多项式中一项的指数，指向结构体本身类型的指针next，定义了结构体我们就可用利用创建一个单链表的方式对一个多项式的各项的系数和指数进行存储、处理。
4.3产生链表函数
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函数接收两个参数，分别是链表的头结点和多项式的项数，使head指向链表的头结点，然后利用for语句循环调用Insert函数，这样就可以动态的分配内存，根据用户输入的项数来制造结点。
4.4插入结点
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函数接收两个指针，分别是p(p永远指向带插入的那个结点)，和链表的头指针，首先依次判断链表中每个结点中的成员coef（多项式的系数）是否为0，如果为0则释放该结点，若系数不为0，则通过q1、q2查找插入结点的位置。
4.5多项式的相加函数
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;
}
}
if(qc->coef!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else free(qc); //当相加系数为0时，释放该结点
}
return headc;
}
Polyn AddPolyn(Polyn pa,Polyn pb)函数接收链表a、链表b的头结点便于实现对两个多项式进行操作，在函数中又调用int compare(Polyn a,Polyn b)，a多项式已空，但b多项式非空函数返回-1，b多项式已空，但a多项式非空，不同的返回值，可以明确的让Polyn AddPolyn(Polyn pa,Polyn pb)进行相应的操作。
4.6多项式相减函数
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;
}
float ValuePolyn(Polyn head,int x){ //输入x值，计算并返回多项式的值
Polyn p;
int i,t;
float sum=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;
}
return sum;
}
Polyn SubtractPolyn(Polyn pa,Polyn pb)函数的作用用于进行多项式的相减操作，其实现方式实质是在调用Polyn AddPolyn(Polyn pa,Polyn pb)函数同时将被减多项式的每项的系数取其相反数进行相加运算。
4.7主函数
void main()
{
int m,n,a,x;
char flag;
Polyn pa=0,pb=0,pc;
printf("请输入a的项数:");
scanf("%d",&m);
pa=CreatePolyn(pa,m); //建立多项式a
printf("请输入b的项数:");
scanf("%d",&n);
pb=CreatePolyn(pb,n); //建立多项式b
//输出菜单
printf(" **************************************************\n");
printf(" * 多项式操作程序 *\n");
printf(" * *\n");
printf(" * A:输出多项式a B:输出多项式b *\n");
printf(" * *\n");
printf(" * C:代入x的值计算a D:代入x的值计算b *\n");
printf(" * *\n");
printf(" * E:输出a+b F:输出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("\n x=%d时，a=%.3f\n",x,ValuePolyn(pa,x));
break;
}
case'D':
case'd':
{
printf("输入x的值：x=");
scanf("%d",&x);
printf("\n x=%d时，b=%.3f\n",x,ValuePolyn(pb,x));
break;
}
case'E':
case'e':
{
pc=AddPolyn(pa,pb);
printf("\n a+b=");
PrintPolyn(pc);
break;
}
case'F':
case'f':
{
pc=SubtractPolyn(pa,pb);
printf("\n a-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++程序设计.北京：北京邮电大学出版社,2003.
[2] 曾辉,王更生,李广丽等编著.C++程序设计实训教程.北京：北京邮电大学出版社,1998.
[3] 谭浩强编著.C++面向对象程序设计.北京：北京清华大学出版社,2001.
[4] 谭浩强. C++面向对象程序设计.北京：清华大学出版社，2006.
[5] 谭浩强. C++程序设计实践指导.北京：清华大学出版社,2005.
[6] 刘玉英,张怡芳等.C++实验指导与课程设计.人民邮电出版社,2007.
附录 全部代码
#include<stdio.h>
#include<stdlib.h> //定义多项式的项
typedef struct Polynomial{
float coef; //系数
int expn; //指数
struct Polynomial *next;
}*Polyn,Polynomial;
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;
}
}
}
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;
}
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++;
}
printf("\n");
}
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多项式非空
}
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;
}
}
if(qc->coef!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else free(qc); //当相加系数为0时，释放该结点
}
return headc;
}
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;
}
float ValuePolyn(Polyn head,int x