多项式相乘C实现.doc

西安郵電大学

数据结构设计报告

题 目： 多项式相乘

院系名称： 计算机学院
专业名称： 软件工程
班 级：
学生姓名：
学号（8位）：
指导教师：
设计起止时间：

一. 设计目的
以动态单链表为存储结构，使用排序等操作实现多项式的乘法运算

二. 设计内容
用一个单链表来表示一个一元多项式；
在创建多项式的过程中，可以按指数的任意顺序输入，并且可在同一多项式中输入指数相同的多个项；
在进行乘法操作之前，输出参与操作的两个多项式。要求输出的多项式按指数升序排列，同指数的多项合并，项数的正负号显示合理。
对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；
结果多项式要求以动态链表为存储结构，复用原多项式的结点空间；
输出结果多项式要求按指数升序排列，同指数的多项要合并，项数的正负号要求显示合理。
三．概要设计
主函数main()
1．功能模块图；

创建多项式LB=creat()
创建多项式LA=creat()

调用Polysort( )排序
调用print()输出LB
调用Polysort( )排序
调用print()输出LA

对多项式LA,LB相乘LC=Polymul(LA,LB)

调用Polysort( )排序

调用print()输出LC

2．各个模块详细的功能描述。
多项式链表升序排序函数
Polylist Polysort(Polylist head)
根据幂次的高低排序的同时并合同类项，幂次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为0则释放两项空间。
多项式创建函数
Polylist creat()
多项式相乘函数
Polylist Polymul(Polylist LA,Polylist LB)

输出函数
void print(Polylist head)
分三种情况：系数输出、符号输出、指数输出
四．详细设计
1.各功能函数的数据流程图
Polysort()开始

head==NULL？

first=p->next; p->next=NULL; move=first;
Y

p->exp= =move->exp

p->exp= =move->exp
N
N
y
p->coef+=move->coef; free(move);
p->next= =NULL
y
head->next=move; move->next=p;

p->coef= =0
y
head->next=move; move->next=p;

q=p; p=p->next;
q->next=p->next; free(p);
y

While(1)

p=head->next; q=head;
move=first;

return head

结束

2．重点设计及编码
（1）多项式链表升序排序函数
Polylist Polysort(Polylist head)
{
Polynode *first,*move,*p,*q; //first移动指针 move 被移动项指针p,q临时指针
q=head;
p=head->next;
if(p==NULL) return head; //判断链表是否为空；
first=p->next;
p->next=NULL;
move=first;
while(move!=NULL) //直接插入排序（链表排序）
{
first=first->next;
if(p->exp==move->exp) //判断待插入项指数是否与首项相等；
{
p->coef+=move->coef; //系数相加；
free(move); //释放空间；
if(p->coef==0) //若系数相加和为0；
{
q->next=p->next;
free(p); //释放空间；
}
}
else if(p->exp>move->exp) //判断待插入项指数是否大于第一个项的指数；
{
head->next=move;
move->next=p;
}
else if(p->next==NULL) //判断下一项是否为空；
{
p->next=move;
move->next=NULL;
}
else //待插入项指数插入位置在首末项之间；
{
q=p; //移动临时变量指针p,q
p=p->next;
while(1)
{
if(p->exp==move->exp) //判断待插入项指数是否与首项相等；
{
p->coef+=move->coef;//系数相加；
free(move); //释放空间；
if(p->coef==0)
{
q->next=p->next;//若系数相加和为0；
free(p); //释放空间；
}
break;
}
if(p->exp>move->exp) //判断待插入项指数是否大于当前项的指数；
{
q->next=move;
move->next=p;
break;
}
if(p->next==NULL) //判断下一项是否为空；
{
p->next=move;
move->next=NULL;
break;
}
q=p; //移动临时变量指针p,q；
p=p->next;
}
}
p=head->next; //使p,q指针重新指到初始化位置；
q=head;
move=first;
}
return head; //返回头结点；
}

（2）多项式创建函数
Polylist creat()
{
Polynode *head,*p,*newnode; //head：头指针 newnode:新结点指针 p：临时指针变量

int c,e; //ceof（系数）和exp（指数）；
head=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点，并使之成为头结点；
p=head;
printf("\n\t请输入多项式中元素的系数和指数:\n");
scanf("%d %d",&c,&e);
while(c||e) //ceof（系数）和exp（指数）不全为0；
{
if(c==0)
{scanf("%d %d",&c,&e);continue;} //若c为0，不开辟新结点；
newnode=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点；
newnode->coef=c;
newnode->exp=e;
p->next=newnode;
p=newnode;
scanf("%d %d",&c,&e);//输入新结点的系数和指数；
}
p->next=NULL; //为最后的结点的next赋空；
head=Polysort(head); //调用Polysort排序函数对多项式链表进行降序排序；
return head; //返回头结点；
}

（3）多项式相乘函数
Polylist Polymul(Polylist LA,Polylist LB)
{
Polynode *head,*p,*q,*t,*newnode; //head：头指针 newnode:新结点指针 p,q,t：临时指针变量；
p=LA->next;
q=LB->next;
head=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点，并使之成为新链表的头结点；
t=head;
while(p!=NULL)
{
while(q!=NULL)
{
newnode=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点；
t->next=newnode;
t=t->next;
t->coef=p->coef*q->coef; //项之系数为LA,LB两项系数之积；
t->exp=p->exp+q->exp; //项之指数为LA,LB两项指数之和；
q=q->next;
}
p=p->next; //p指针移动；
q=LB->next; //q指针复位为LB->next；
}
t->next=NULL; //为最后的结点的next赋空；
head=Polysort(head); //调用Polysort排序函数对多项式链表进行降序排序；
return head; //返回头结点；
}
（4）输出函数
void print(Polylist head)
{
Polynode *p;

p=head->next;
if(p==NULL)
printf("0");
else
while(p!=NULL)
{
//系数输出
if(p->coef==-1)
printf("-");
else if(p->coef!=1)
printf("%d",p->coef);

//符号输出
if(p->exp!=0&&p->exp!=1)
printf("X^");
else if(p->exp==1)
printf("X");

//指数输出
if(p->exp==0&&(p->coef==-1||p->coef==1))
printf("1");
if(p->exp<0)
printf("(%d)",p->exp);
else if(p->exp!=1&&p->exp!=0)
printf("%d",p->exp);
p=p->next;
if(p!=NULL&&p->coef>0)
printf("+");
}
printf("\n");
}
五．测试数据及运行结果
1．正常测试数据和运行结果

2．异常测试数据及运行结果
如输入的字符不是数字，则无法处理，
如：a 2 程序无法继续运行
六．调试情况，设计技巧及体会
1．改进方案
多项式相成这个程序缺少对异常的处理，如果用户输入一些异常的字符程序将无法继续运行，甚至导致死机。
改进：加入异常处理，将各种用户可能的输入都包含在内。
2．体会
心得体会：此程序是使用链表完成的，一直以来比较习惯用顺序表，通过这个程序加深了对链表的理解。程序的排序部分较为复杂，根据幂次的高低排序的同时并合了同类项，幂次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为0则释放两项空间。其实想这段算法时很容易，真正实现却是相当不容易，可能是平时写的代码太少，真正把思想转换成代码困难还是比较大。
七．参考文献
《C语言程序设计》 王曙燕主编 科学出版社

《数据结构——C语言描述》 耿国华 高等教育出版社

《数据结构》 严蔚敏 清华大学出版社
八．附录：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct Polynode
{
int coef;//系数
int exp;//指数
struct Polynode *next;
}Polynode,*Polylist;

//多项式链表升序排序
Polylist Polysort(Polylist head)
{
Polynode *first,*move,*p,*q; //first移动指针变量 move 被移动项指针变量p,q临时指针变量
q=head;
p=head->next;
if(p==NULL) return head; //判断链表是否为空；
first=p->next;
p->next=NULL;
move=first;
while(move!=NULL) //直接插入排序（链表排序）
{
first=first->next;
if(p->exp==move->exp) //判断待插入项指数是否与首项相等；
{
p->coef+=move->coef; //系数相加；
free(move); //释放空间；
if(p->coef==0) //若系数相加和为0；
{
q->next=p->next;
free(p); //释放空间；
}
}
else if(p->exp>move->exp) //判断待插入项指数是否大于第一个项的指数；
{
head->next=move;
move->next=p;
}
else if(p->next==NULL) //判断下一项是否为空；
{
p->next=move;
move->next=NULL;
}
else //待插入项指数插入位置在首末项之间；
{
q=p; //移动临时变量指针p,q
p=p->next;
while(1)
{
if(p->exp==move->exp) //判断待插入项指数是否与首项相等；
{
p->coef+=move->coef;//系数相加；
free(move); //释放空间；
if(p->coef==0)
{
q->next=p->next;//若系数相加和为0；
free(p); //释放空间；
}
break;
}
if(p->exp>move->exp) //判断待插入项指数是否大于当前项的指数；
{
q->next=move;
move->next=p;
break;
}
if(p->next==NULL) //判断下一项是否为空；
{
p->next=move;
move->next=NULL;
break;
}
q=p; //移动临时变量指针p,q；
p=p->next;
}
}
p=head->next; //使p,q指针重新指到初始化位置；
q=head;
move=first;
}
return head; //返回头结点；
}

//多项式创建(头插法)
Polylist creat()
{
Polynode *head,*p,*newnode; //head：头指针 newnode:新结点指针 p：临时指针变量

int c,e; //ceof（系数）和exp（指数）；
head=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点，并使之成为头结点；
p=head;
printf("\n\t请输入多项式中元素的系数和指数:\n");
scanf("%d %d",&c,&e);
while(c||e) //ceof（系数）和exp（指数）不全为0；
{
if(c==0)
{scanf("%d %d",&c,&e);continue;} //若c为0，不开辟新结点；
newnode=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点；
newnode->coef=c;
newnode->exp=e;
p->next=newnode;
p=newnode;
scanf("%d %d",&c,&e);//输入新结点的系数和指数；
}
p->next=NULL; //为最后的结点的next赋空；
head=Polysort(head); //调用Polysort排序函数对多项式链表进行降序排序；
return head; //返回头结点；
}
//多项式相乘
Polylist Polymul(Polylist LA,Polylist LB)
{
Polynode *head,*p,*q,*t,*newnode; //head：头指针 newnode:新结点指针 p,q,t：临时指针变量；
p=LA->next;
q=LB->next;
head=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点，并使之成为新链表的头结点；
t=head;
while(p!=NULL)
{
while(q!=NULL)
{
newnode=(Polynode *)malloc(sizeof(Polynode));//开辟一个新结点；
t->next=newnode;
t=t->next;
t->coef=p->coef*q->coef; //项之系数为LA,LB两项系数之积；
t->exp=p->exp+q->exp; //项之指数为LA,LB两项指数之和；
q=q->next;
}
p=p->next; //p指针移动；
q=LB->next; //q指针复位为LB->next；
}
t->next=NULL; //为最后的结点的next赋空；
head=Polysort(head); //调用Polysort排序函数对多项式链表进行降序排序；
return head; //返回头结点；
}
//输出函数
void print(Polylist head)
{
Polynode *p;

p=head->next;
if(p==NULL)
printf("0");
else
while(p!=NULL)
{
//系数输出
if(p->coef==-1)
printf("-");
else if(p->coef!=1)
printf("%d",p->coef);

//符号输出
if(p->exp!=0&&p->exp!=1)
printf("X^");
else if(p->exp==1)
printf("X");

//指数输出
if(p->exp==0&&(p->coef==-1||p->coef==1))
printf("1");
if(p->exp<0)
printf("(%d)",p->exp);
else if(p->exp!=1&&p->exp!=0)
printf("%d",p->exp);
p=p->next;
if(p!=NULL&&p->coef>0)
printf("+");
}
printf("\n");
}

void main()
{
Polylist LA,LB,LC;
printf("\t\t\t请输入一元多项式 A：\n");
printf("\t请输入一元多项式 A：\n");
LA=creat(); //创建多项式LA；
print(LA); //输出多项式LA；

printf("\t请输入一元多项式 B：\n");
LB=creat(); //创建多项式LB；
print(LB); //输出多项式LB；

LC=Polymul(LA,LB); //对多项式LA,LB相乘；

printf("两多项式相乘结果LC：");
print(LC); //输出多项式LC；
}

欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力。赠语； 1、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就做得更好，来给人笑吧！ 2、现在你不玩命的学，以后命玩你。3、我不知道年少轻狂，我只知道胜者为王。4、不要做金钱、权利的奴隶；应学会做“金钱、权利”的主人。5、什么时候离光明最近？那就是你觉得黑暗太黑的时候。6、最值得欣赏的风景，是自己奋斗的足迹。 7、压力不是有人比你努力，而是那些比你牛×几倍的人依然比你努力。