实验一、线性结构综合应用
一、实验题目：顺序表的应用
二、实验内容：一元多项式求和。
把任意给定的两个一元多项式P(x) ,Q(x) 输入计算机，计算它们的和并输出计算结果。
三、设计分析：
实现要定义的一元多项式应采用链式存储结构。根据一元多项式相加的运
算法则，对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成新多项式的一项；对于两个多项式中所有指数不同的项，分别复制到新多项式中。新多项式不必另外生成，而是在原来的两个多项式中摘取结点即可。
采用顺序存储结构存储多项式系数A，使多项式的某些运算变得更简洁。但在实际使用时，多项式的阶数可能很高，不同的多项式阶数可能相差很大，这使顺序存储结构的最大长度难以确定。而且，最高次幂与最低次幂项之间缺项很多时，采用顺序存储结构显然十分浪费存储空间，因此，一般情况下多采用链式存储结构来存储高阶多项式。
在用线性链表来存储一个多项式时，多项式中的每个非零项系数对应一个结点，结点由数据元素项和指针组成。数据元素项中包含系数和指数值，
设计中先定义定义数据元素中的数据，其中有指数、系数级指针next等。并要先构造一元多项式。在定义输出、删除、合并等模块。
假设指针qa和qb分别指向多项式A和B中当前进行操作的某个结点，比较这个结点的指数项，可能有三种情况：
① 指针qa->exp<qb->exp,则摘取qa指针所指结点插入到和多项式中；
② 指针qa->exp<qb->exp,则摘取qb指针所指结点插入到和多项式中；
③ 指针qa->exp=qb->exp,则将系数相加，若和数不为零，则修改qa->coef的值，同时释放qb所指结点，反之，从多项式A的链表中删除相应的结点，并释放指针Pa和Pb所指结点；
还有就是在输入是采取的降序输入，也好使两个多项式进行合并。并输出。在主函数中将前面也的这些功能都运用起来就可以了
四、程序代码：
#include<iostream>
#define NULL 0
using namespace std;
typedef struct Polynomial
{
float coef; //系数
int exp; //指数
struct Polynomial *next;
}Polynomial;
Polynomial *CreatPolyn()
{ //输入m项的系数和指数，建立一元多项式
float mod;
int ind;
Polynomial *H,*p,*s;
H=new Polynomial;
s=H;
潣瑵?请输入多项式的系数和指数：(按0结束输入)<<endl;
cin>>mod>>ind;
while(mod){
p=(Polynomial *)new Polynomial;
p->coef=mod;
p->exp=ind;
s->next=p;
s=p;
cin>>mod>>ind;
}
s->next=NULL;
return H;
}
void Print(Polynomial *pa)
{ //打印输出一元多项式p
while(pa->next!=NULL) {
pa=pa->next;
cout<<pa->coef<<*x^<<pa->exp;
if(pa->next!=NULL&&pa->next->coef>0)
cout<<+;
}
}
void Delete(Polynomial *pa)
{ //删除一元多项式
Polynomial *p,*q;
p=pa->next;
while(p){
q=p;
p=p->next;
delete q;
}
pa->next=NULL;
}
void AddPolyn(Polynomial *pa,Polynomial *pb)
{ //用于链表的合并使用完成多项式的相加运算
float sum;
Polynomial *p,*q,*pre,*temp;
p=pa->next;
q=pb->next;
pre=pa;
while(p!=NULL&&q!=NULL)
{
if(p->exp>q->exp)
{
pre->next=p;
pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp)
{
sum=p->coef+q->coef;
if(sum!=0) {
p->coef=sum;
pre->next=p;
pre=pre->next;
p=p->next;
temp=q;
q=q->next;
delete temp;
}
else
{
temp=p->next;
delete p;
p=temp;
temp=q->next;
delete q;
q=temp;
}
}
else
{
pre->next=q;
pre=pre->next;
q=q->next;
}
}
if(p!=NULL) //将多项式A中剩余的结点加入到和多项式中
pre->next=p;
else
pre->next=q;
}
int main()
{
int c;
int t=1;
while(t){
cout<<******************菜单*****************<<endl<<endl;
cout<<.创建并显示一元多项式A和B，计算一元多项式A加B并显示和<<endl<<endl;
cout<<.退出程序.<<endl;
cin>>c;
switch(c)
{
case 1:Polynomial *p1,*p2;
p1=CreatPolyn();
潣瑵?一元多项式A是: ;
Print(p1);
cout<<endl;
p2=CreatPolyn();
潣瑵?一元多项式B是: ;
Print(p2);
cout<<endl;
AddPolyn(p1,p2);
潣瑵?一元多项式A加B的和是: ;
Print(p1);
cout<<endl;
Delete(p1);
break;
case 2:t=0;
break;
}
}system(pause);
return 0;
}
五、测试用例：
六、实验总结
通过这次实验，对于链表的应用知识有了更加深刻的认识，虽然中间出了很多问题，但是经 过调试以后都得以解决。提高了自己的动手能力。．