一元多项式相加的实验报告
- 格式：docx
- 大小：24.21 KB
- 文档页数：8
《数据结构》实验报告
1、实验名称:实现一元多项式的加法
2、实验日期: 2011-3-7
3、基本要求：
1）编程实现一元多项式的加法；
2）设计一个测试主函数。
4、实验目的：
通过实验使学生掌握链表的最基本和最主要的操作：插入和删除
操作。
5、测试数据：
随意输入两个一元多项式的系数和指数：
第一个：系数：4 8 6 7；指数：2 3 4 5
第二个：系数：5 9 3 8；指数：1 3 5 6
两式相加后输出结果。
6、
算法思想或算法步骤:
1） 用尾插入法创建单链表
（PLoy *create_Ploy_LinkList(void)）
2）输出单链表中所有结点的值，得到一元多项式
（void output_Ploy_LinkList(PLoy *L, char ch)）
3）进行多项式的相加，采用链式存储表示加法，根据结点类型定
义，若指数不同，则进行链表的合并；若指数相同，则进行系数相加；
若和为0，则去掉结点；若和不为0，则修改结点的系数域。
（PLoy *add_ploy(PLoy *La, PLoy *Lb)）
7、模块划分：
1）头文件stdiob.h。头文件stdiob.h中包括：结点结构体定义、
一元多项式的系数和指数的输入、一元多项式的输出以及两式相加输
出结果的操作等；
2）实现文件yydxsxj.cpp。包含主函数int main()，其功能是
测试所设计的一元多项式加法的正确性。
8、数据结构：
链表中的结点的结构体定义如下：
typedef struct Node
{
float coef; /*系数部分*/
int expn; /*指数部分*/
struct Node *next ;
} PloyNode;
9、源程序：
源程序存放在两个文件中，即头文件stdiob.h和实现文件
yydxsxj.cpp。
//头文件stdiob.h
typedef struct Node
{
float coef; /*系数部分*/
int expn; /*指数部分*/
struct Node *next ;
} PloyNode;
PloyNode *create_Ploy_LinkList(void)
{
/* 尾插入法创建单链表,链表的头结点head作为返回值 */
float coef ; int expn ;
PloyNode *head, *p, *q;
head=p=(PloyNode *)malloc(sizeof(PloyNode));
p->next=NULL; /* 创建单链表的表头结点head */
while (1)
{
printf("\n请输入一元多项式的系数(0表示结束): ") ;
scanf("%f",&coef);
if (coef==0) break ;
else
{
printf("\n请输入一元多项式的指数: ") ;
scanf("%d",&expn);
q=(PloyNode *)malloc(sizeof(PloyNode));
q->coef=coef ; /* 指数部分赋值 */
q->expn=expn ; /* 系数部分赋值 */
q->next=p->next; p->next=q; p=q ;
/* 钩链，新创建的结点总是作为最后一个结点 */
}
}
return(head);
}
void output_Ploy_LinkList(PloyNode *L, char ch)
/* 输出以L为头结点的单链表中所有结点的值 */
{
PloyNode *p;
p=L->next; /* 使p指向第一个结点 */
if (p==NULL) printf("\n此多项式为空!!\n\n") ;
else
{
printf("f(x)= \n",ch) ;
while (p!=NULL)
{
if (p->coef>0)
printf("%+g",p->coef) ;
else printf("%g",p->coef) ;
if (p->expn!=0)
{
printf("X^") ;
printf("%d",p->expn);
}
p=p->next;
}
} /* 移动指针p */
printf("\n\n") ;
}
PloyNode *add_Ploy(PloyNode *La, PloyNode *Lb)
{
PloyNode *Lc , *pc , *pa , *pb ,*ptr ; float x ;
Lc=pc=La ; pa=La->next ; pb=Lb->next ;
if(pa==NULL&&pb==NULL)printf("两个式子之和也为空项");
while (pa!=NULL&&pb!=NULL)
{
if (pa->expn< pb->expn)
{
pc->next=pa ; pc=pa ; pa=pa->next ; }
else
{
if (pa->expn>pb->expn)
{ pc->next=pb ; pc=pb ; pb=pb->next ; }
else
{
x=pa->coef+pb->coef ;
if (x==0)
{ ptr=pa ; pa=pa->next ;
ptr=pb ; pb=pb->next ;
}
else
{ pc->next=pa ; pa->coef=x ;
pc=pa ; pa=pa->next ;
ptr=pb ; pb=pb->next ;
}
}
}
}
if (pa==NULL) pc->next=pb ;
else pc->next=pa ;
return (Lc) ;
}
//实现文件yydxsxj.cpp
#include
#include
#include"stdiob.h"
using namespace std;
int main()
{
PloyNode * pa,* pb;
char pc,pd;
cout<<"请输入第一个多项式(按指数递增顺序输入):"<
output_Ploy_LinkList(pa,pc);
cout<<"请输入第二个多项式(按指数递增顺序输入):"<
output_Ploy_LinkList(pb,pd);
cout<<"多项式相加结果是:"<
output_Ploy_LinkList(pa,pc);
return 0;}
10、测试情况：
1）程序运行输出为：
第一个多项式为：f(x)=+4x^2+8x^3+6x^4+7x^5
第二个多项式为：f(x)=+5x^1+9x^3+3x^5+8x^6
两式相加之和为：f(x)=+5x^1+4x^2+17x^3+6x^410x^5+8x^6
2）测试结果分析：
程序运行结果和预测的完全相同，说明所设计的一元多项式的加
法是正确的。
