一元稀疏多项式计算器doc.docx
《一元稀疏多项式计算器doc.docx》由会员分享，可在线阅读，更多相关《一元稀疏多项式计算器doc.docx（17页珍藏版）》请在冰点文库上搜索。
一元稀疏多项式计算器doc
课程名称数据结构课程设计
课题名称一元稀疏多项式计算器
目录
一、课题的主要功能………………………………………………4
二、课题的功能模块的划分………………………………………6
三、主要功能的实现………………………………………………7
四、程序调试………………………………………………………9
五、总结（程序设计心得与体会）…………………………………11
六、附件（所有程序的原代码）……………………………………12
七、评分表…………………………………………………………18
一、课题的主要功能
a、课程题目
一元稀疏多项式计算器
b、需求分析
1、一元稀疏多项式简单计算器的功能是：
1.1输入并建立多项式；
1.2输出多项式，输出形式为整数序列：
n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
1.5多项式a和b相加，建立多项式a+b；
1.6多项式a和b相减，建立多项式a-b；
1.7计算多项式在x处的值。
2、设计思路:
2.1定义线性表的动态分配顺序存储结构；
2.2建立多项式存储结构，定义指针*next
2.3利用链表实现队列的构造。
每次输入一项的系数和指数，可以输出构造的一元多项式
2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。
多项式显示的格式为：
c1x^e1+c2x^e2+…+cnx^en
3、设计思路分析
要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为
序数coef
指数expn
指针域next
运用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polynp中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。
为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：
①若p->expnexpn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。
②若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。
③若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。
二、课题的功能模块的划分
内容包括：
函数CreatePolyn建立一个头指针为head、项数为m的一元多项式，然后调运函数Insert向生成链表中保存多项式项数及每项的指数、系数。
函数CreatePolyn生成多项式a和多项式b。
通过函数compare和函数PrintPolyn对多项式a和多项式b指数、系数进行分析。
当多项式a指数指数大于多项式b指数时，链表保存多项式a系数；当多项式b指数指数大于多项式a指数时，链表保存多项式b系数；当多项式b指数指数等于多项式a指数时，对多项式a和多项式b系数进行加减运算，之后将系数保存在链表中。
函数PolynAddPolyn对多项式a和多项式b进行加运算，调运函数compare、函数PrintPolyn、函数CreatePolyn。
函数SubtractPolyn对多项式a和多项式b进行减运算，其对多项式b中各系数正负取反，然后调用函数PolynAddPolyn进行a+（-b）。
主函数运行分别输入多项式和多项式的项数、系数和指数，然后选择对多项式操作A：
a+b或B：
a-b，从而实现对多项式的加减运算。
函数的调用关系图：
三、主要功能的实现
1、元素类型、结点类型和指针类型：
typedefstructPolynomial{
floatcoef;//系数
intexpn;//指数
structPolynomial*next;
}*Polyn,Polynomial;
2、建立一个头指针为head、项数为m的一元多项式,建立新结点以接收数据,调用Insert函数插入结点:
PolynCreatePolyn（Polynhead,intm）{
inti;
Polynp;
p=head=（Polyn）malloc（sizeof（structPolynomial））;
head->next=NULL;
for（i=0;i{
p=（Polyn）malloc（sizeof（structPolynomial））;
printf（"请输入第%d项的系数与指数:
",i+1）;
scanf（"%f%d",&p->coef,&p->expn）;
Insert（p,head）;
}
returnhead;
}
3、主函数和其他函数：
voidmain（）
{
intm,n,a,x;
charflag;
Polynpa=0,pb=0,pc;
}
floatValuePolyn（Polynhead,intx）//输入x值，计算并返回多项式的值
主要函数的流程图：
四、程序调试
测试数据
a.
；
b.；
c.
；
d.
；
e.
；
五、总结
经过这段为期不久的课程设计，使我对于数据结构有了更深层次的理解,循环队列中对边界条件的处理,满足什么条件为队满,满足什么条件为队空。
在这个过程中。
我也曾因为实践经验缺乏失落过；也曾经仿真成功而热情高涨。
生活就这样；虽然这只是一次极其简单的课程设计；可是平心而论，也耗费我不少的心血。
这让我不得不对我们社会的付出的老一辈；为了我们的生活更美好，他们为我们付出多少心血。
我感觉用心细心地做好一件事情的重要性，在这次课程设计中，体会到了做设计的严谨，更加加深了我对课程设计的兴趣，我觉得我们不仅是在完成一个课题，更是对自我知识的探索以及团队合作的重要性，在此次课程设计过程中，遇到不懂的问题我会及时向老师，同学请教，以更好地完成该项课题设计。
一个人的能力有限；此次的程序设计能够成功，是我自身的努力和寻求老师同学的帮助共同努力作用的结果。
在这一段努力学习的过程中，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。
现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。
只要努力去学习，就会灵活的去应用它。
以后，努力学习好这么课程，让自己拥有更多的知识，才能解决更多的问题。
六、附件
用带表头结点的单链表存储多项式。
#include
#include
typedefstructnode
{
floatcoef;
intexpn;
structnode*next;
}Lnode,*polynmial;
voidcreate（polynmial&L）; //输入并建立多项式L
voiddisplay（polynmialL）; //显示，输出多项式L
voidsort（polynmial&L）; //多项式L按指数排序
voidreverse（polynmial&L）; //逆置
voidselect（）; //用户选择加减操作
voidadd（polynmialLa,polynmialLb,polynmial&Lc）; //多项式La,Lb相加
voidsubtract（polynmialLa,polynmialLb,polynmial&Ld）;//多项式La减去Lb，结果给Ld
voidcreate（polynmial&L）//输入并建立多项式L
{
inti,n;
staticstructnode*p;
scanf（"%d",&n）;
L=（structnode*）malloc（sizeof（structnode））;
L->next=NULL;
for（i=0;i{
p=（structnode*）malloc（sizeof（structnode））;
scanf（"%f%d",&p->coef,&p->expn）;
p->next=L->next;
L->next=p;
}
}
voiddisplay（polynmialL）//显示，输出多项式L
{
structnode*p,*q;
intflag=0;
intk=0;
q=L->next;
while（q）
{
if（q->coef!
=0）
k++;
q=q->next;
}
printf（"%d,",k）;
p=L->next;
if（p->coef!
=0）
{
printf（"%.1f,%d,",p->coef,p->expn）;
flag++;
}
for（p=p->next;p;p=p->next）
{
if（p->coef!
=0）
{
printf（"%.1f,%d,",p->coef,p->expn）;
flag++;
}
}
if（flag==0）
printf（"%d\n",flag）;
else
printf（"\n"）;
}
voidsort（polynmial&L）//多项式L按指数排序
{
polynmialp,q,r,u;
p=L->next;
L->next=NULL;
while（p!
=NULL）
{
r=L;
q=L->next;
while（（q!
=NULL）&&（q->expn<=p->expn））
{
r=q;
q=q->next;
}
u=p->next;
r->next=p;
p->next=q;
p=u;
}
}
voidreverse（polynmial&L）//逆置
{
polynmialH;
staticstructnode*p,*q,*s;
H=（structnode*）malloc（sizeof（structnode））;
H->next=NULL;
p=（structnode*）malloc（sizeof（structnode））;
s=L->next;
p->coef=s->coef;
p->expn=s->expn;
p->next=s->next;
while（s）
{
p->coef=s->coef;
p->expn=s->expn;
p->next=s->next;
q=H->next;
H->next=p;
p->next=q;
p=（structnode*）malloc（sizeof（structnode））;
s=s->next;
}
p=H->next;
q=L->next;
while（p）
{
q->coef=p->coef;
q->expn=p->expn;
q=q->next;
p=p->next;
}
}
voidselect（）//用户选择加减操作
{
printf（"请选择加减操作\n"）;
printf（"1.两个一元多项式相加\n"）;
printf（"2.两个一元多项式相减\n"）;
}
voidadd（polynmialLa,polynmialLb,polynmial&Lc）//多项式La,Lb相加
{
structnode*pa,*pb;
staticstructnode*pc;
Lc=（structnode*）malloc（sizeof（structnode））;
pa=La->next;
pb=Lb->next;
Lc->next=NULL;
while（pa&&pb）
{
pc=（structnode*）malloc（sizeof（structnode））;
if（pa->expnexpn）
{
pc->next=Lc->next;
Lc->next=pc;
pc->coef=pa->coef;
pc->expn=pa->expn;
pa=pa->next;
}
else
if（pa->expn==pb->expn）
{
pc->next=Lc->next;
Lc->next=pc;
pc->expn=pa->expn;
pc->coef=pa->coef+pb->coef;
pa=pa->next;
pb=pb->next;
}
else
{
pc->next=Lc->next;
Lc->next=pc;
pc->coef=pb->coef;
pc->expn=pb->expn;
pb=pb->next;
}
}
while（pa）
{
pc=（structnode*）malloc（sizeof（structnode））;
pc->next=Lc->next;
Lc->next=pc;
pc->coef=pa->coef;
pc->expn=pa->expn;
pa=pa->next;
}
while（pb）
{
pc=（structnode*）malloc（sizeof（structnode））;
pc->next=Lc->next;
Lc->next=pc;
pc->coef=pb->coef;
pc->expn=pb->expn;
pb=pb->next;
}
}
voidsubtract（polynmialLa,polynmialLb,polynmial&Ld）//多项式La减去Lb，结果给Ld
{
structnode*pa,*pb;
staticstructnode*pd;
Ld=（structnode*）malloc（sizeof（structnode））;
pa=La->next;
pb=Lb->next;
Ld->next=NULL;
while（pa&&pb）
{
pd=（structnode*）malloc（sizeof（structnode））;
if（pa->expnexpn）
{
pd->next=Ld->next;
Ld->next=pd;
pd->coef=pa->coef;
pd->expn=pa->expn;
pa=pa->next;
}
else
if（pa->expn==pb->expn）
{
pd->next=Ld->next;
Ld->next=pd;
pd->expn=pa->expn;
pd->coef=pa->coef-pb->coef;
pa=pa->next;
pb=pb->next;
}
else
{
pd->next=Ld->next;
Ld->next=pd;
pd->coef=pb->coef;
pd->expn=pb->expn;
pb=pb->next;
}
}
while（pa）
{
pd=（structnode*）malloc（sizeof（structnode））;
pd->next=Ld->next;
Ld->next=pd;
pd->coef=pa->coef;
pd->expn=pa->expn;
pa=pa->next;
}
while（pb）
{
pd=（structnode*）malloc（sizeof（structnode））;
pd->next=Ld->next;
Ld->next=pd;
pd->coef=-pb->coef;
pd->expn=pb->expn;
pb=pb->next;
}
}
intmain（）
{
intsign;
polynmialLa,Lb,Lc,Ld;
printf（"请输入第一个多项式：
\n"）;
create（La）;
sort（La）;
printf（"请输入第二个多项式：
\n"）;
create（Lb）;
sort（Lb）;
select（）;
scanf（"%d",&sign）;
switch（sign）
{
case1:
printf（"多项式之和为:
\n"）;
add（La,Lb,Lc）;
sort（Lc）;
reverse（Lc）;
display（Lc）;
break;
default:
printf（"多项式之差为:
\n"）;
subtract（La,Lb,Ld）;
sort（Ld）;
reverse（Ld）;
display（Ld）;
break;
}
return0;
}
计算机与通信学院课程设计评分表
课题名称：
一元稀疏多项式计算器
项目
评价
设计方案的合理性与创造性
设计与调试结果
设计说明书的质量
答辩陈述与回答问题情况
课程设计周表现情况
综合成绩
教师签名：
日期：
升级会员 