一、实验名称：多项式相加

二、实验学时：4学时

三、实验目的

1.理解单链表的结构特性和基本操作算法；

2.掌握利用单链表实现两个多项式相加算法。

四、实验内容(步骤)

1.创建两个一元多项式；

2.输出一元多项式；

3.实现两个一元多项式相加；

4.输出相加后的一元多项式。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

根据一元多项式相加的运算规则有：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式”中。“和多项式”链表中的结点无须另外生成，可以从两个多项式的链表中摘取。

算法思路：假设指针 p 和 q 分别指向多项式 P 和 Q 中当前进行比较的某个结点，则比较两个结点中的指数项有3种情况：一是指针 p 所指结点的指数值 < 指针 q 所指结点的指数值，则应该摘取 p 所指结点插入到“多项式”链表中；二是指针 p 所指结点的指数值 > 指针 q 所指结点的指数值，则应该摘取 q 所指结点插入到“多项式”链表中；三是指针 p 所指结点的指数值 = 指针 q 所指结点的指数值，则将两个结点的系数相加，若和数不为零，则修改 p 所指结点的系数值，同时释放 q 所指结点，反之从多项式 P 的链表中删除相应结点，并释放 p 和 q 所指结点。

实验源代码

#include<iostream>
#include<stdlib.h>
#define flag -1          // 定义数据输入结束的标志数据
using namespace std;

//typedef int DataType;
typedef struct
{
	float coef; // 多项式系数 
	int expn; // 指数 
}DataType; // DataType 相当于 struct 

typedef struct Node
{
	DataType data;
	struct Node *next;
}LNode,*LinkList;

void CreateLinkList_tail(LinkList L)  // 尾插法 
{
	LNode *s,*r; // s为指向当前插入元素的指针，r为尾指针。
	DataType x;
	r=L;
	cin>>x.coef>>x.expn; // 分别输入多项式的系数、指数
	while(x.coef!=flag)    // 当该结点中系数为 -1 时，输入结束。
	{
		s=(LinkList)malloc(sizeof(LNode)); // 为当前插入元素的指针分配地址空间 
		s->data=x;
		r->next=s;
		r=s;
		cin>>x.coef>>x.expn;
	}
	r->next=NULL;
}

LinkList Add_L(LinkList P,LinkList Q) // 两个多项式相加
{
	LNode *p,*q; // p 和 q 分别指向多项式 P 和 Q 中当前进行比较的某个结点
	LNode *r,*s; // r 指向和多项式链表的尾指针，s 指向待释放指针。
	float sum; // sum 记录相同指数结点的系数和
	p=P->next; // p 一开始指向第一个元素的结点（非头结点）
	q=Q->next; // q 一开始指向第一个元素的结点（非头结点）
	r=P; // r 初始指向 P 多项式链表，并始终指向和多项式尾结点
	while(p&&q)
	{   
		if((p->data).expn < (q->data).expn)
		{// 第1种情况：p 所指结点的指数值小于 q 所指结点的指数值
         // 此时 P 链表结点插入到和多项式尾部，且 r 指针后移
			r->next=p;
			r=r->next;
			p=p->next; 
		}
		else if((p->data).expn > (q->data).expn)
		{// 第2种情况：p 所指结点的指数值大于 q 所指结点的指数值
         // 此时 Q 链表结点插入到和多项式尾部，且 r 指针后移
			r->next=q;
			r=r->next;
			q=q->next;
		}
		else
		{// 第3种情况中又分为2种情况
			sum=(p->data).coef+(q->data).coef; // 求出指数值相同的两个结点对应的系数之和
			if(sum!=0)
			{// 1）系数之和不为0时
             // 系数和重新赋值给 p 并插入和多项式尾部，释放 q 所指结点，另将 q 后移
				(p->data).coef=sum;
				r->next=p;
				r=r->next;
				p=p->next;
				s=q;
				q=q->next;
				free(s); 
			}
			else
			{// 2）系数之和为0时
             // 无须插入结点到和多项式尾部，释放 p、q 所指结点，另将 p、q 后移
				s=p;
				p=p->next;
				free(s);
				s=q;
				q=q->next;
				free(s); 
			}
		}
	}
	if(p) // 若链表 P 还有待处理的结点，链接 P 链表中剩下结点
	    r->next=p;
	else  // 否则，链接 Q 链表中剩下结点
	    r->next=q;
	free(Q); // 释放 Q 的头结点
	return P; // 返回和多项式头链表
}

void printlinklist(LinkList L) // 输出链表
{
	LNode *p;
	p=L->next; // p指向第一个元素的结点（非头结点）
	while(p)
	{
		cout<<p->data.coef<<"*x^"<<p->data.expn;
		p=p->next; // p指向下一个结点
		if(p && p->data.coef>0) // 若当前结点不为空且系数大于0，则在该数之前添加一个“+”号
		    cout<<"+";
		
	}
	cout<<endl;
}

int main()
{
	LinkList L,Q,P; // 等价于 LNode *L,*Q,*P; 
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL; // 建立空链表 L
	
    Q=(LinkList)malloc(sizeof(LNode));
	Q->next=NULL; // 建立空链表 Q
	
    CreateLinkList_tail(L); // 创建第1个多项式 L
	cout<<"第1个多项式："; 
	printlinklist(L); // 输出第1个多项式 L
	
    CreateLinkList_tail(Q); // 创建第2个多项式 Q
	cout<<"第2个多项式：";
	printlinklist(Q); // 输出第2个多项式 Q
	
    P=Add_L(L,Q); // P为和多项式，将多项式 L 与多项式 Q 相加后的和多项式赋给 P
	cout<<"两个多项式相加："; 
	printlinklist(P); // 输出和多项式 P

    return 0;
}

运行结果