一元多项式相加数据结构实验一1307班谭淇蔚.docx
《一元多项式相加数据结构实验一1307班谭淇蔚.docx》由会员分享，可在线阅读，更多相关《一元多项式相加数据结构实验一1307班谭淇蔚.docx（32页珍藏版）》请在冰点文库上搜索。
一元多项式相加数据结构实验一1307班谭淇蔚
中南大学
《数据结构与算法》课程实验
实验报告
题目实验一线性表的操作
学生谭淇蔚
学生学号3901130721
专业班级软件工程1307班
完成日期2014年3月31日星期一
实验一线性表的操作〔一元多项式相加〕
1.需求分析
我们使用电脑处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。
而数据存储结构有两种：
顺序存储结构和链式存储结构。
线性表是最常用且最简单的一种数据结构。
所以我们做的是实验一-----------线性表的操作。
实验的目的是掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算以及熟练运用掌握的线性表的操作，实现一元n次多项式的加法运算。
学习实现一元n次多项式的加法是符号多项式的操作，是表处理的典型用例，需要注意的是：
顺序存储结构指的是用数组方法，使用数组方法实现时，在插入和删除的方面，数组不如链表灵活，方法复杂，删除其中一个需要将其后的数组元素改变位置，使其数组保持原有的顺序结构，在查找方面较链表简单，只需要知道其下标就可以知道。
链接存储结构指的是用链表方法,值得注意的是，删除和插入较为灵活，不需要变动大多数元素，但是查找过程相对于数组这种顺序存储结构来说较为复杂，耗时巨大。
我们要学习的是通过对两种方法基本操作的掌握来做到实现一元n次多项式的相加减。
我们程序的任务是：
能进行简单的线性表操作〔插入、删除、查找〕以及线性表合并等运算。
能通过这些基本操作实现一元多项式相加。
明确规定：
输入的形式：
按照提示〔比方：
“请您输入第一个结构体数组的项数〔不超过50项〕：
”、“请您输入第二个结构体数组的项数〔不超过50项〕：
”、“请输入第n项的系数”、“请输入第n项的指数”等等〕，先输入多项式的项数，之后顺次输入每一项的系数与指数。
输入值的范围：
项数没有要求，但不能过于巨大；系数取为float型数据，指数取为int型数据，
输出的形式：
按照提示〔比方：
“您输入的第一个多项式为：
”、“您输入的第二个多项式为：
”等等〕，会输出原输入的多项式和经过排序和合并之后的降幂型多项式。
同时，系数会以保留小数点后两位数字的形式输出；假设指数输入时为小数，则输出时会自动截取其整数部分。
程序所能到达的功能：
程序可以对输入的序列紊乱的多项式进行加工，使之按照降幂排列，之后对两多项式进行加法运算〔包括系数为负的加法〕，最后输出最终的多项式。
测试数
正确数据：
输入：
2*X^3+2*X^6+2*X^7+2*X^8+2*X^10和-
3*X^10+4*X^8+2*X^7+3*X^5+3*X^3
输出：
7.00*X^2+8.00*X^1+2.00
错误数据：
输入：
-8*X^1.5+4*X^2和3*X^2+12*X^1.6
输出：
7.00*X^2+4.00*X^1
2．概要设计
〔1〕链接存储结构：
structnode
{
floatcoef;
intexpo;
structnode*next;
}chainLink;
函数主体部分，利用头指针进行链表操作，利用display进行打印出屏幕，利用order函数对其进行降幂排序，当两个多项式已经创建完毕时，利用add函数进行两个多项式相加。
〔2〕顺序存储结构
抽象数据类型为结构体数组：
structpoly
{
floatcoef;
intexp;
};
函数主体部分，会引用指针进行参数传递，在函数主体部分定义了3个结构体数组同时定义其所对应的指针，利用用户输入，利用print函数将其打印出来，再用sort函数将其降序排列，做完两个结构体数组后，接着利用add函数将两个多项式相加。
3．详细设计
〔1〕链接存储结构：
结构体定义：
structnode
{
intcoef;//系数
intexp;//指数
structnode*next;//指针域
}chainLink;//创建chainLink的node结点对象
〔值得注意的是，与顺序存储结构不同的是，内部还定义了指针域〕
功能函数介绍：
structnode*create（）//定义建立多项式函数，并返回链表头指针
{
structnode*h=NULL,*q,*p;//定义结构体头指针h，标记指针p和q，p是创造新节点的标记指针，q是链接链表的指针；
inti=1,N;//定义多项式的项数N及标记数i
cout<<"请输入多项式的项数：
\n";
cin>>N;
p=0;//指针初始化；
q=0;//本地指针初始化；
for（;i<=N;i++）
{
p=（structnode*）malloc（sizeof（chainLink））;//为一个新节点分配空间
cout<<"请输入第"<\n";
cin>>（*p）.coef;
cout<<"请输入第"<\n";
cin>>（*p）.exp;
if（i==1）{h=p;q=p;}//建立头节点
else
{
q->next=p;
q=p;
}
}
q->next=NULL;//p,q都成为新链表的尾指针；
p->next=NULL;
returnh;
}
PS：
值得注意的是，我在里面P，q指针均使其值为0，是让其为空指针，对其进行初始化，在visualstudio2013版中，如果不进行初始化，会被报错。
打印函数display:
voiddisplay（structnode*h）
{
structnode*p;//定义标记指针，输出链表
p=h;
while（p!
=NULL）
{
if（p->coef==0）
{
structnode*d;
d=h;
while（d->next!
=p）
{
d=d->next;
}
d->next=p->next;
p=p->next;//删去系数为0的节点；
}
else
{
if（p->coef<0）//系数为负时应加上括号,让式子容易看清；
{
if（p->exp==0）cout<<（*p）.coef<<"+";
elsecout<<"（"<<（*p）.coef<<"）"<<"*X^"<<（*p）.exp<<"+";
}
else
{
if（p->exp==0）cout<<（*p）.coef<<"+";
elseif（p->exp!
=0&&p->exp!
=1）
{
cout<<（*p）.coef<<"*X^"<<（*p）.exp<<"+";
}
elsecout<<（*p）.coef<<"*X+";
}
p=p->next;
}
}
cout<<"\b\b\n";
}
PS:
打印函数display中，值得注意的是系数为负时，应该加括号。
其次，当指数为1时，没必要写成X^1这种形式。
系数为0的项也应该删去，这里我定义一个d指针，用来找到系数为0的项前一个结点的指针，然后进行删除该系数为0的节点的操作，其实和老师上课中的处理差不多，都是使用一个指针保护原有指针，用while循环找到系数为0的项的前驱，以便进行删除节点操作。
排序函数order：
structnode*order（structnode*h）//定义排序函数，并返回整理后的链表的头指针
{
structnode*p,*q,*t,*h1,*h2;//定义三个结构体标记指针和两个头指针
h1=h;//建立一个新的链表，头指针为h，指向原链表的第一个节点，之后将原链表中的节点一个一个的插入此链表，进行排序
h2=h1->next;//将原来的链表建立成待排序链表
h1->next=NULL;//截断第一个原链表中的节点
while（h2!
=NULL）
{
q=h1;
p=q->next;
t=h2;//从待排序链表中选出一个节点准备插入到新链表中
h2=h2->next;//移动待排序链表的头指针，便于进行下一次挑选
t->next=NULL;
if（t->exp>q->exp）//应插入头指针之前的情况
{
t->next=q;
h1=t;
continue;
}
if（p==NULL&&t->exp<=q->exp）q->next=t;//应插入表尾的情况
while（p!
=NULL）
{
if（t->exp>p->exp）
{
q->next=t;
t->next=p;
break;
}
else
{
q=q->next;
p=p->next;
}
}
if（p==NULL）q->next=t;
}
returnh1;//新链表即为按降幂顺序排好的链表，返回其头指针
}
Order函数其实是利用了3个头指针，具体操作看代码即可，其实很容易懂。
相加函数add：
structnode*add（structnode*h1,structnode*h2）//定义加法函数，并返回结果的链表的头指针
{
structnode*p,*q,*head,*r;//定义结构体头指针head和标记指针p,q,r
p=h1;
q=h2;
head=（structnode*）malloc（sizeof（chainLink））;//为结果多项式分配头指针
if（p->exp>=q->exp）{head=h1;p=p->next;}
else
{
if（p->expexp）{head=h2;q=q->next;}
else{p->coef=p->coef+q->coef;head=p;p=p->next;q=q->next;}
}
r=head;
while（p!
=NULL&&q!
=NULL）
{
if（p->exp>q->exp）{r->next=p;p=p->next;}
else
{
if（p->expexp）{r->next=q;q=q->next;}
else{p->coef=p->coef+q->coef;r->next=p;p=p->next;q=q->next;}
}
r=r->next;
}
if（p==NULL&&q==NULL）r->next=NULL;
else
{
if（p==NULL）r->next=q;
if（q==NULL）r->next=p;
}
returnhead;
}
add函数大部分其实和老师PPT思路差不多。
比较两个多项式中指数大小，然后分别对其余两个进行操作。
〔2〕顺序存储结构
结构体定义：
structpoly
{
floatcoef;
intexp;
};//结构体数组定义
主函数结构体数组的创建以及导引指针的创建：
polyp[50],*po=p;
polyp1[50],*po1=p1;
polyp2[100],*po2=p2;//定义三个结构体数组，用于存放多项式,定义三个指针变量；
print函数以及参数调用代码：
voidprint（structpoly*s[],intn）
{
for（inti=0;i{
if（i==n-1）cout<<（*s）[i].coef<<"*X^"<<（*s）[i].exp;
else
cout<<（*s）[i].coef<<"*X^"<<（*s）[i].exp<<"+";
}
}//输出数组
主函数中调用print函数的具体形式：
print（&po,n1）;
sort函数的代码：
voidsort（structpoly*s[],intn）
{
inti,temp1,j;//定义数组中的循环标记数据i与j，和整型标记temp1
floattemp2;//定义单精度型标记temp2
for（i=0;ifor（j=i+1;j{
if（（*s）[j].exp>（*s）[i].exp）
{
temp1=（*s）[j].exp;
（*s）[j].exp=（*s）[i].exp;
（*s）[i].exp=temp1;
temp2=（*s）[j].coef;
（*s）[j].coef=（*s）[i].coef;
（*s）[i].coef=temp2;
}
}
for（i=0;i{
if（（*s）[i].exp==（*s）[i+1].exp）
{
（*s）[i+1].coef=（*s）[i].coef+（*s）[i+1].coef;
if（i==n-2）
{
（*s）[i].coef=（*s）[i+1].coef;
（*s）[i+1].coef=0;
}
else
{
for（j=i;j{
（*s）[j].coef=（*s）[j+1].coef;
（*s）[j].exp=（*s）[j+1].exp;
}
（*s）[j].coef=0;
i--;
}
}
}
}
事实上sort函数是采用逆冒泡法排序，让指数部分大的排在前面，与选择排序不同，选择排序是相邻的交换，直到最小的排在前面为止。
Sort函数在主函数中的调用：
sort（&po,n1）;
add函数的代码：
voidadd（structpoly*s[],structpoly*s1[],structpoly*s2[],intn1,intn2）
{
inti=0,j=0,p,m;//定义数组中的循环标记数据i,j,p,m
for（p=0;;p++）
{
if（（*s）[i].exp==（*s1）[j].exp）
{
（*s2）[p].coef=（*s）[i].coef+（*s1）[j].coef;
（*s2）[p].exp=（*s）[i].exp;
i++;
j++;
}
else
{
if（（*s）[i].exp>（*s1）[j].exp）
{
（*s2）[p].coef=（*s）[i].coef;
（*s2）[p].exp=（*s）[i].exp;
i++;
}
else
{
（*s2）[p].coef=（*s1）[j].coef;
（*s2）[p].exp=（*s1）[j].exp;
j++;
}
}
if（i==n1||j==n2）
{
p++;
break;
}
}
if（i==n1）
for（;j{
（*s2）[p].coef=（*s1）[j].coef;
（*s2）[p].exp=（*s1）[j].exp;
p++;
}
else
for（;i{
（*s2）[p].coef=（*s）[i].coef;
（*s2）[p].exp=（*s）[i].exp;
p++;
}
for（m=0;m{
if（（*s2）[m].coef<0）
{
if（（*s2）[m].exp==0）cout<<（*s2）[m].coef<<"+";
elsecout<<（*s2）[m].coef<<"*X^"<<（*s2）[m].exp<<"+";
}
elseif（（*s2）[m].coef>0）
{
if（（*s2）[m].exp==0）cout<<（*s2）[m].coef<<"+";
else//printf（"%.2f*X^%d+",dxs2[m].coef,dxs2[m].exp）;
cout<<（*s2）[m].coef<<"*X^"<<（*s2）[m].exp<<"+";
}
}
cout<<"\b\b\n";
}
add函数在主函数中的调用：
add（&po,&po1,&po2,n1,n2）;
4．调试分析
〔1〕链接存储结构：
设计过程，注意指针保护，如果一步不小心，容易造成头指针消失，所以需要指针来保护头指针，至于其他方面倒是没有什么问题。
总的来说，代码长度170，算不上特别多，该有的功能也考虑到了。
〔2〕顺序存储结构
在设计过程中，发现如果不采用指针参数传递结构体数组，而是对单个多项式进行单个功能操作，即对于每一个多项式都会用同功能的函数，只不过不同名称来实现，这样造成代码冗长，我试过写出了286行的代码，但visualstudio2013无法编译如此冗长的代码，所以我决定使用指针导向进行优化，优化后的代码行数是162行，少了100多行，实现功能也比之前多了一些。
虽然没法像我第一次写那286行的代码可以实现动态创建结构体数组，但我认为，这162行的代码的结构体数组50个大小，理应足够计算，如果要更大，建议修改代码中创建结构体数组大小的尺寸。
总体来说，还算不错，知识经过一个寒假忘得七零八落，感觉我还没有完全掌握这类知识，等有时间重新将自己进行优化，也希望老师给予指导。
5．用户使用说明
〔1〕链接存储结构：
按照提示一步步来即可；
举例：
请输入第一个多项式：
请输入多项式的项数：
3
请输入第一项的系数：
2
请输入第一项的指数：
2
请输入第二项的系数：
3
请输入第二项的指数：
5
请输入第三项的系数：
3
请输入第三项的指数：
1
类似如上操作，到时大部分会在屏幕显示。
〔2〕顺序存储结构
按照提示一步步来即可；
举例：
请您输入第一个结构体数组的项数〔不超过50项〕：
2
请您输入第二个结构体数组的项数〔不超过50项〕：
2
现在是输入第一个多项式
请输入第1项系数：
2
请输入第1项指数：
2
请输入第2项系数：
3
请输入第2项指数：
3
现在是输入第二个多项式：
请输入第1项系数：
3
请输入第1项指数：
3
请输入第2项系数：
4
请输入第2项指数：
4
接着屏幕便会显示出来。
6．测试结果
〔1〕链接存储结构：
〔2〕顺序存储结构
7．附录
〔1〕链接存储结构：
#include
usingnamespacestd;
structnode
{
intcoef;//系数
intexp;//指数
structnode*next;//指针域
}chainLink;//创建chainLink的node结点对象
structnode*create（）//定义建立多项式函数，并返回链表头指针
{
structnode*h=NULL,*q,*p;//定义结构体头指针h，标记指针p和q，p是创造新节点的标记指针，q是链接链表的指针；
inti=1,N;//定义多项式的项数N及标记数i
cout<<"请输入多项式的项数：
\n";
cin>>N;
p=0;//指针初始化；
q=0;//本地指针初始化；
for（;i<=N;i++）
{
p=（structnode*）malloc（sizeof（chainLink））;//为一个新节点分配空间
cout<<"请输入第"<\n";
cin>>（*p）.coef;
cout<<"请输入第"<\n";
cin>>（*p）.exp;
if（i==1）{h=p;q=p;}//建立头节点
else
{
q->next=p;
q=p;
}
}
q->next=NULL;//p,q都成为新链表的尾指针；
p->next=NULL;
returnh;
}
voiddisplay（structnode*h）
{
structnode*p;//定义标记指针，输出链表
p=h;
while（p!
=NULL）
{
if（p->coef==0）
{
structnode*d;
d=h;
while（d->next!
=p）
{
d=d->next;
}
d->next=p->next;
p=p->next;//删去系数为0的节点；
}
else
{
if（p->coef<0）//系数为负时应加上括号,让式子容易看清；
{
if（p->exp==0）cout<<（*p）.coef<<"+";
elsecout<<"（"<<（*p）.coef<<"）"<<"*X^"<<（*p）.exp<<"+";
}
else
{
if（p->ex
升级会员 