其实书上就有的，清华大学严蔚敏编的那本，我这有不是很成熟的一个，仅供借鉴
题目:一元稀疏多项式计算器
班级:0307XX班
姓名:XXX
学号:0307XXXX
完成日期:2009-5-9
一、需求分析
(1) 输入的形式和输入值的范围
输入的形式: 先输入两个多项式的项数n;
然后从第1项开始,分别输入多项式各项的系数和指数;:
(先输入系数，后输入指数):
输入想要做的多项式运算类型:
输入值的范围:多项式各项的系数没有特殊要求,但是指数应该为正数
(2) 输出的形式
程序会自动输出两个一元稀疏多项式(序列按指数升序排列)
根据所选择的多项式运算类型,做出相应的数学运算,并且输出运算结果:一元稀疏多项式 (序列按指数降序排列)
(3) 程序功能
多项式的基本运算类型:加法、减法、乘法
(4) 测试数据
(见测试结果)
二、概要设计
抽象数据类型的定义
typedef struct LNode
{
float coef;
int expn;
LNode* next;
}term, *link;
typedef struct
{
link head,tail;
int len;
}polynomial,* Lpoly;
三、详细设计
建一个空的表
int InitList( polynomial &p) //建一个空的表
{
link h;
h=(link)malloc(sizeof(term));
if(!h)
return ERROR;
p.head=p.tail=h;
h->next=NULL;
p.len=0;
return 1;
}
判断是否有指数相同的节点
link LocateElem(polynomial p,term e) //判断是否有指数相同的节点
{
link ha;
ha=p.head->next;
int n=p.len;
while(n)
{
if(e.expn==ha->expn)
return ha;
ha=ha->next;
n--;
}
return 0;
}
判断第一个比e大的节点
link LocateElem2(polynomial p,term e) //判断第一个比e大的节点
{
link ha;
ha=p.head;
int n=p.len;
while(n)
{
if(e.expn
return ha;
ha=ha->next;
n--;
}
return 0;
}
产生值为e的节点
int MakeNode(link& p,term e) //产生值为e的节点
{
p=(link)malloc(sizeof(term));
if(!p)
return ERROR;
p->coef=e.coef;
p->expn=e.expn;
return 1;
}
按照指数从小到大次序建立一个多项式链表
void CreatPolyn(polynomial& p,int m) //按照指数从小到大次序建立一个多项式链表
{
InitList(p);
link h=p.head,s,t1,t2; //h为中间的结点的位置指针
h->coef=0.0;
h->expn=-1;
term e;
cout<<"请输入p的系数和指数:"<
{
cin>>e.coef>>e.expn;
t1=LocateElem(p,e);
t2=LocateElem2(p,e);
if(!t1) //判断是否有指数相同的结点
{
if(MakeNode(s,e)) //是为产生结点的指针
{
if(!t2) //使新的节点按指数的顺序插入链表中
{
h->next=s;
h=h->next;
h->next=NULL;
p.len++;
}
else
{
s->next=t2->next;
t2->next=s;
p.len++;
}
}
}
else
{
t1->coef+=e.coef; //指数相同的话就直接在相同指数的节点上加上e的系数
}
}
p.tail=h;
}
输出一元稀疏多项式 (序列按指数升序排列)
void PrintPolyn(polynomial p)
{
cout<<"该一元稀疏多项式输出即为(序列按指数升序排列):"<
for (int i = 1;i <= p.len;i++,q = q->next)
{
if (q->coef == 0.0) //系数为 0,该项无需打印
continue;
if (q->coef > 0.0 && i != 1) // 系数为正数,且不是第一项时，打印" + "号
cout<<"+";
if (q->coef != 1.0) //系数非 1 时，需要打印出系数
cout<
if (q->expn !=0) //指数非 0 时，需要打印出指数
cout<<"X^"<
}
cout<
比较节点的指数大小
int CmpPolynExpn(link pa,link pb) //比较节点的指数大小
{
if(pa->expn>pb->expn)
return 1;
if(pa->expn==pb->expn)
return 0;
if(pa->expn
return -1;
}
去掉h后面的节点q返回地址
int DelFirst(link h,link& q) //去掉h后面的节点q返回地址
{
q=h->next;
if(!q) //h为尾节点则报错
return ERROR;
h->next=h->next->next;
return 1;
}
多项式的长度计算
void LenPolyn(polynomial& p) //多项式的长度计算
{
link pa=p.head;
int i=0;
while(pa->next!=0)
{
i++;
pa=pa->next;
}
p.len=i;
}
多项式加法
polynomial AddPolyn(polynomial& pa,polynomial& pb) //多项式加法
{
polynomial c;
InitList(c);
link hc=c.head,ha=pa.head,hb=pb.head; //qa qb 为当前操作的结点的指针 ha hb为qa qb的上一个结点的指针
link qc=hc,qa=ha->next,qb=hb->next;
while(qa&&qb)
{
switch(CmpPolynExpn(qa,qb)) //-1 表示a中的小 0 表示一样大 1 表示b的小
{
case -1:
qc->next=qa;
qc=qa;
ha=qa;
qa=qa->next;
break;
case 0:
qa->coef+=qb->coef;
if(qa->coef==0) //当系数我0时候将节点free掉
{
DelFirst(ha,qa);
free(qa);
DelFirst(hb,qb);
free(qb);
qa=ha->next;qb=hb->next;
}
else
{
qc->next=qa;
qc=qa;
qa=qa->next;qb=qb->next;
}
break;
case 1:
qc->next=qb;
qc=qb;
hb=qb;
qb=qb->next;
break;
}
}
if(!qa) //将剩余的结点导入c中
{
qc->next=qb;
c.tail=pb.tail;
}
else
{
qc->next=qa;
c.tail=pa.tail;
}
LenPolyn(c);
return c;
}
多项式减法
polynomial SubPolyn(polynomial& pa,polynomial& pb) //多项式减法
{
polynomial c1;
InitList(c1);
link hc=c1.head,ha=pa.head,hb=pb.head;
link qc=hc,qa=ha->next,qb=hb->next;
while(qa&&qb)
{
switch(CmpPolynExpn(qa,qb))
{
case -1:
qc->next=qa;
qc=qa;
ha=qa;
qa=qa->next;
break;
case 0:
qa->coef=abs(qa->coef-qb->coef);
if(qa->coef==0)
{
DelFirst(ha,qa);
free(qa);
DelFirst(hb,qb);
free(qb);
qa=ha->next;qb=hb->next;
}
else
{
qc->next=qa;
qc=qa;
qa=qa->next;qb=qb->next;
}
break;
case 1:
qb->coef=-qb->coef;
qc->next=qb;
qc=qb;
hb=qb;
qb=qb->next;
break;
}
}
if(!qa)
{
qc->next=qb;
while(qb!=0)
{
qb->coef=-qb->coef;
qb=qb->next;
}
c1.tail=pb.tail;
}
else
{
qc->next=qa;
c1.tail=pa.tail;
}
LenPolyn(c1);
return c1;
}
四、调试分析
(1)调试过程中遇到的问题及其解决方法
A.问题:库函数 malloc 调用错误
解决方法:函数 malloc 的声明
void * malloc (unsigned size )
可以强制类型转换,前面为指针类型,后面为所分配的内存空间的大小
用于申请一段新的地址,参数 size 为需要内存空间的长度
B.问题:函数的指针类型的形式参数重复定义
解决方法:在函数定义的形式参数列表中, 指针类型的形式参数定义注意事项:
采用值传递,内存空间已经自动分配完毕;
采用引用传递,内存空间需要自动分配;
C.问题:在 for 循环语句中,循环变量使用控制错误
解决方法: 在 for 循环语句中,应该意识到:
循环变量的执行次数总是比循环体的执行次数多一次;
即最后一次的循环体执行完毕之后,循环变量又执行了一次,但是循环体却没有再执行了
D.问题: C++ 中编译出错信息: "cannot open Debug/*.exe for writing"
解决方法: 第一次编译运行后，没有关掉那个程序，所以更改后再次编译就提示不能写入;那么打开任务管理器看看那个进程在不在，可能关了窗口，但程序还没有结束;
记得编译前关闭程序，或者到任务管理器的看看进程是否存在，有的话结束掉
E.问题: AV(Access Violation) 错误
解决方法: 访问不再有效的内存,
大多数的情况下,出现这个错误要么是因为你试图访问一块已经被释放的内存,要么是想使用一个还未创建对象的指针。
F.问题: C++ 中编译出错信息: left operand must be l-value
解决方法: l-value应该是个left-value，也就是左值，只有变量和看作指针的内存空间可以被看作是左值
(2)经验与体会
A.在线性链表中进行遍历操作的两种常用控制手段:
a. 利用该线性链表的长度 L.length
b. 利用该线性链表的尾指针 NULL
B.在书写程序时,应该注意 return 语句在程序中的位置,因为在顺序结构中一旦使用到了 return 语句,return 语句后面的所有程序代码都无法再执行.
C.在对线性链表的操作中,
如果是加工型操作,则需要在形参列表中用引用传递的方式返回该线性链表 L;
如果是引用型操作,则不需要在形参列表中用引用传递的方式返回该线性链表 L;
D.在程序调试过程中,如果发现许多地方犯了同一类错误,则应该一次性将这一类错误全部调试好,这样可以提高程序调试的效率
E.返回链表类型的数据元素应该是链表结点,而不是该链表结点中的数据域 data
五、用户使用说明
本程序操作步骤：
(1) 初始化多项式P1
输入多项式 P1 的项数；
然后从第1项开始,分别输入多项式各项的系数和指数(先输入系数，后输入指数)；
程序会自动输出该一元稀疏多项式P1 (序列按指数升序排列)
(2) 初始化多项式P2
输入多项式 P2 的项数；
然后从第1项开始,分别输入多项式各项的系数和指数(先输入系数，后输入指数)；
程序会自动输出该一元稀疏多项式P2 (序列按指数升序排列)
(3) 输入想要做的多项式运算类型:
相加 1 相减 2:
(4)本程序会自动根据所选择的多项式运算类型,做出相应的数学运算,并且输出运算结果:一元稀疏多项式 (序列按指数升序排列)
六、测试结果
键盘输入与屏幕输出:
A
请输入p1的数目:3 (输入值)
请输入p的系数和指数:
1
3
4
6
7
9
该一元稀疏多项式输出即为(序列按指数升序排列):
X^3+4X^6+7X^9
请输入p2的数目:5 (输入值)
请输入p的系数和指数:
2
5
8
9
87
7
8
5
2
47
该一元稀疏多项式输出即为(序列按指数升序排列):
10X^5+87X^7+8X^9+2X^47
相加 1 相减 2:
1 (输入值)
多项式的和:
该一元稀疏多项式输出即为(序列按指数升序排列):
X^3+10X^5+4X^6+87X^7+15X^9+2X^47
Press any key to continue
B
请输入p1的数目:3
请输入p的系数和指数:
1
3
4
6
7
9
该一元稀疏多项式输出即为(序列按指数升序排列):
X^3+4X^6+7X^9
请输入p2的数目:4
请输入p的系数和指数:
6
5
6
5
8
9
5
526
该一元稀疏多项式输出即为(序列按指数升序排列):
12X^5+8X^9+5X^526
相加 1 相减 2:
2
多项式的差:
该一元稀疏多项式输出即为(序列按指数升序排列):
X^3-12X^5+4X^6+X^9-5X^526
Press any key to continue
七、附录
带有注释的源程序(见源程序文件)
那是相当麻烦啊。。。。这个还是比较不麻烦的，书上还有用伪代码的。。。
分多我就送你一个
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024