一元稀疏多项式加法运算实验报告

实验题目 元项式加法运算
班级：数学班 姓名： 学号： 日期：2012
需求分析
1）程序功：
11 输入两稀疏元n次项式
12 计算两项式
项式相加运算规：两元项式中指数相子项应系数相加非零构成项式中项两元项式中指数子项分复制项式中
13项式ab相加建立项式a+b输出项式
2）输入输出：
21输入求指数递增序指定输入格式输入系数0子项：系数指数直遇输入结束标志（系数指数00）时候停止
22输出项式输出形式整数序列：nc1e1c2e2………cnen中n项式项数ciei分第i项系数指数序列指数降序排列
3）测试数：
1(2x+5x^831x^11)+(75x^8+11x^9)(31x^11+11x^9+2x+7)
2(6x^3x+44x^212x^9+12x^9)(6x^3+54x^2x^2+78x^15
)(78x^1512x^9+12x^3x)
3(1+x+x^2+x^3+x^4+x^5)+(x^3x^4)(1+x+x^2+x^5)
4(x+x^3)+(xx^3)0
5(x+x^100)+(x^100+x^200)(x+2x^100+x^200)
6(x+x^2+x^3)+0x+x^2+x^3
二概设计
1）建立头指针head项数m元项式 建立新结点接收数 调Insert函数插入结点
Polyn CreatePolyn(Polyn headint m){
int i
Polyn p
phead(Polyn)malloc(sizeof(struct Polynomial))
head>nextNULL
for(i0i {
p(Polyn)malloc(sizeof(struct Polynomial))
printf(请输入第d项系数指数i+1)
scanf(f d&p>coef&p>expn)
Insert(phead)
}
return head
}
2）程序包括4模板：
21程序模块：
main()
{
输入项式A
输入项式B
计算AB项式输出
}
22建立链表：
Polyn CreatePolyn(Polyn headint m){
23项式相加：
Polyn AddPolyn(Polyn paPolyn pb){
24输出项式：
void PrintPolyn(Polyn P){
3）模块间层次关系：

三详细设计
1）项式数类型定义：
typedef struct Polynomial{
float coef 系数
int expn 指数
struct Polynomial *next
}*PolynPolynomial
2）详细设计思路：
解决项式相加必须项式必须首先建立两项式里采链表方式存储链表结点结构体定义
序数coef
指数expn
指针域next
运尾插法建立两条单链表单链表polyn ppolyn h分表示两元项式aba+b求运算等单链表插入问题（单链表polyn p中结点插入单链表polyn h中）项式中结点须生成
实现处理设pq分指单链表polyapolyb前项较pq结点指数项列运算规：
① p>expnexpn结点p指结点应项式中项令指针p移
② p>expnq>expn两结点中系数相加0时修改结点p系数
③ p>expn>q>expn结点q指结点应项式中项结点q插入结点p前令指针q原链表移
3）函数间调关系图图
main


intput add output

init

四调试分析
1）调试中遇问题解决方法：
11遇问题：
a输入项式时输入实型系数忽略程序中指定类型整型产生错误输出结果
b程序运行结果出现形0*3项符合惯
c输出表达符合数学表达方式
12解决方法：
a输入整型系数考虑修改程序中系数类型时间原没修改
b项式加法函数中两项式中指数相加项数系数相加时考虑系数0情况时应删结点作项式中项
c输出函数设计中考虑点：
项式第项系数正时显示+号项显示+号
指数零时输出指数部分
指数1时输出指数1
系数1时输出系数
考虑种综合情况输出含11xx正确方法等
2）算法时间复杂度：
假设两项式分mn项建立俩项式时间复杂度O（m）O(n)两项式相加时间复杂度O(m+n)输出含n子项项式时间复杂度O（n）算法总时间复杂度O（m+n）
五说明测试结果：
1）输入a项数：

2）输入a系数指数：

3）类似输入b项数系数指数
4．）选择操作：

5）输出b项式：

6）输出项式：


六源程序：
#include
#include 定义项式项
typedef struct Polynomial{
float coef 系数
int expn 指数
struct Polynomial *next
}*PolynPolynomial
void Insert(Polyn pPolyn h){
if(p>coef0) free(p) 系数0话释放结点
else
{
Polyn q1q2
q1h
q2h>next
while(q2&& p>expn < q2>expn)
{ 查找插入位置
q1q2
q2q2>next
}
if(q2&& p>expn q2>expn)
{ 指数相相合
q2>coef + p>coef
free(p)
if(q2>coef)
{ 系数0话释放结点
q1>nextq2>next
free(q2)
}
}
else
{ 指数新时结点插入
p>nextq2
q1>nextp
}
}
}
Polyn CreatePolyn(Polyn headint m){ 建立头指针head项数m元项式
int i
Polyn p
phead(Polyn)malloc(sizeof(struct Polynomial))
head>nextNULL
for(i0i {
p(Polyn)malloc(sizeof(struct Polynomial)) 建立新结点接收数
printf(请输入第d项系数指数i+1)
scanf(f d&p>coef&p>expn)
Insert(phead) 调Insert函数插入结点
}
return head
}
void DestroyPolyn(Polyn p){ 销毁项式p
Polyn q1q2
q1p>next
q2q1>next
while(q1>next)
{
free(q1)
q1q2
q2q2>next
}
}
void PrintPolyn(Polyn P){
Polyn qP>next
int flag1 项数计数器
if(q)
{ 项式空输出0
putchar(＇0＇)
printf(＼n)
return
}
while(q)
{
if(q>coef>0&& flag1) putchar(＇+＇) 系数0第项
if(q>coef1&&q>coef1)
{ 系数非11普通情况
printf(gq>coef)
if(q>expn1) putchar(＇X＇)
else if(q>expn) printf(X^dq>expn)
}
else
{
if(q>coef1)
{
if(q>expn) putchar(＇1＇)
else if(q>expn1) putchar(＇X＇)
else printf(X^dq>expn)
}
if(q>coef1)
{
if(q>expn) printf(1)
else if(q>expn1) printf(X)
else printf(X^dq>expn)
}
}
qq>next
flag++
}
printf(＼n)
}
int compare(Polyn aPolyn b){
if(a&&b)
{
if(b||a>expn>b>expn) return 1
else if(a||a>expnexpn) return 1
else return 0
}
else if(a&&b) return 1 a项式已空b项式非空
else return 1 b项式已空a项式非空
}
Polyn AddPolyn(Polyn paPolyn pb){ 求解建立项式a+b返回头指针
Polyn qapa>next
Polyn qbpb>next
Polyn headchcqc
hc(Polyn)malloc(sizeof(struct Polynomial)) 建立头结点
hc>nextNULL
headchc
while(qa||qb)
{
qc(Polyn)malloc(sizeof(struct Polynomial))
switch(compare(qaqb)){
case 1
{
qc>coefqa>coef
qc>expnqa>expn
qaqa>next
break
}
case 0
{
qc>coefqa>coef+qb>coef
qc>expnqa>expn
qaqa>next
qbqb>next
break
}
case 1
{
qc>coefqb>coef
qc>expnqb>expn
qbqb>next
break
}
}
if(qc>coef0)
{
qc>nexthc>next
hc>nextqc
hcqc
}
else free(qc) 相加系数0时释放该结点
}
return headc
}
void main()
{
int mna
char flag
Polyn pa0pb0pc
printf(请输入项式a项数)
scanf(d&m)
paCreatePolyn(pam) 建立项式a
printf(请输入项式b项数)
scanf(d&n)
pbCreatePolyn(pbn) 建立项式b
输出菜单
printf( ************************************************************＼n)
printf( * 项式操作程序 *＼n)
printf( * *＼n)
printf( * 1输出元稀疏项式a 2输出元稀疏项式b *＼n)
printf( * *＼n)
printf( * 3输出元稀疏项式a+b 4退出程序 *＼n)
printf( * *＼n)
printf( ************************************************************＼n)
while(a)
{
printf(＼n请您选择操作项目：)
scanf( c&flag)
switch(flag)
{
case＇1＇
{
printf(＼n 项式a)
PrintPolyn(pa)
break
}
case＇2＇
{
printf(＼n 项式b)
PrintPolyn(pb)
break
}
case＇3＇
{
pcAddPolyn(papb)
printf(＼n a+b)
PrintPolyn(pc)
break
}
case＇4＇
{
printf(＼n 运行结束＼n)
DestroyPolyn(pa)
DestroyPolyn(pb)
a0
break
}
default
printf(＼n 输入错误＼n)
}
}
}
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档