文档介绍：西南科技大学
数据结构
实验报告
专业班级____软件1004____
任课教师____李学俊_____ _
姓名______杨强_______
学号____20101469_____
实验地点____东六E108_____
2011年11月22日
实验一
一元多项式的加法、减法及乘乘法运算
【问题描述】
一元多项式的所有运算都可以用其加减运算加以实现。设计一个程序,实现一元多 项式的加法、减法及乘法运算。
【基本要求】
(1)、分别采用顺序存储和单链表作存储结构。在顺序存储中,一个多项式对应一个结构体数组,数组中的每个节点对应该多项式中的一项,所以每个节点至少包括系数域、指数域。在链式存储中,一个多项式对应一个单链表,链表中的每个节点对应该多项式中的一项,所以每个节点至少包括系数域、指数域及指向下一项的指针域。
(2)、一元多项式要求从键盘上加以接收。
(3)、运算规则如数学上的多项式的计算,要求能够在屏幕上输出相应的数据。
【主要功能】
实现两个单链表的加法、减法及乘法运算。
【思路分析】
存储结构: 链式存储;
算法:
加法:两个多项式由键盘接收,输入包括系数部分和指数部分,程序接收完数据后,将按指数对多项式的项进行排序,然后合并同类项,即得到最简多项式。将两个多项式进行合并同类项操作,即达到多项式相加的目的。
减法:在多项式的减法操作时,将减数的各项系数取反,再与被减多项式进行合并可得多项式相减的结果。
乘法:首先进行指数的加减运算,然后做累加,即得多项式相乘的结果。
【关键函数】
void sort_HtoL(LinkList *L); //对表L中各项按降序排列
void Simplify(LinkList *L); //对表L进行化简
void Sum(LinkList *LA,LinkList *LB,LinkList *&LC) //执行相加运算
void Sub(LinkList *LA, LinkList *LB) //执行相减运算
void Multi(LinkList *LA, LinkList *LB, LinkList *&L)//执行相乘运算
【具体算法】
//按指数降序排列;
void sort_HtoL(LinkList *L)
{
LinkList *p, *q;
int temp_coef, temp_exp;
for(p=L->next; p->next != NULL; p=p->next)
for(q=p->next; q != NULL; q=q->next)
{
if(p->exp < q->exp)
{
temp_exp = p->exp; //交换指数;
p->exp = q->exp;
q->exp = temp_exp;
temp_coef = p->coef; //同时交换系数;
p->coef = q->coef;
q->coef = temp_coef;
}
}
}
//合并同类项;
void Simplify(LinkList *L)
{
LinkList *p;
p = L->next;
while(p->next != NULL)
{
if(p->exp == p->next->exp)
{
p->coef = p->coef + p->next->coef; //合并;
p->next = p->next->next;
}
else
{
p = p->next;
}
}
}
//LA + LB = LC;
void Sum(LinkList *LA,LinkList *LB,LinkList *&LC)
{
LinkList *p,*q,*s,*r;
p=LA->next;
q=LB->next;
int temp;
LC=(LinkList *)malloc(sizeof(LinkList)); //创建头结点;
r = LC;
while (p!=NULL && q!=NULL)
{
if (p->exp > q->exp)
{
s=(LinkList *)malloc(sizeof(LinkList)); //复制结点;
s = p;
r->next=s;
r=s;
p=p->next; //指向LA的p指针后移;
}
else if (p->exp < q->exp)
{
s=(LinkList *)malloc(sizeof(Link