单链表的应用（多项式相加）

目录

题目内容

算法分析

概要设计

 流程图

代码块

运行结果

题目内容

      完成两个多项式的相加操作：已知有两个多项式Pm(x)、Qm(x)，设计算法实现Pm(x)+Qm(x)运算，而且对加法运算不重新开辟存储空间。要求用链式存储结构实现。例如：Pm(x)=5x^3+2x=1,Qm(x)=3x^3+x^2-2x-3,其计算输出结果为：8x^3+1x^2-2。

算法分析

   本设计使用单链表实现。

两个多项式相加算法的实现，首先是将两个多项式分别用链表进行存放。可以设置两个指针LA1和LB1分别从多项式Pm(x)和Qm(x)的首结点移动，比较LA1和LB1所指结点的指数项，则可以分下面三种情况进行处理：

1. 若LA1->exp<LB1->exp,则LA1所指结点为多项式中的一项，LA1指针在原来的基础上向后移动一个位置。
2. 若LA1->exp=LB1->exp,将对应项的系数相加，然后分两种情况处理：如果系数项的和为0，则释放LA1和LB1所指向的结点；如果系数项的和不为零，则修改LA1所指向结点的系数域，释放LB1结点。
3. 若LA1->exp>LB1->exp,则LB1所指向结点为多项式中的一项，LB1指针在原来的基础上向后移动一个位置。

概要设计

程序中设计了四个函数：

1. 函数Init()用来初始化一个空链表
2. 函数CreateFromTail()用来创建一个链表，这里是用尾插法来创建链表
3. 函数Polyadd()用来实现两个多项式相加算法
4. 函数Print()用来输出多项式

 流程图

 代码块

/**
* @author:sy
* @date:2021-9-30
* @version:1.0
* @ Description：完成两个多项式相加操作
*/ 
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct poly
{
	int exp;  //指数幂
	int coef; //系数
	struct poly*next;  //指针域 
}PNode,*PLinklist;
int Init(PLinklist*head)  //链表初始化
{
	*head=(PLinklist)malloc(sizeof(PNode));
	if(*head)
	{
		(*head)->next=NULL;
		return 1;
	}
	else
	return 0;
 } 
int CreateFromTail(PLinklist *head)  //尾插法创建链表
 {
 	PNode *pTemp,*pHead;
 	int c;   //存放系数
	int exp; //存放指数
	int i=1; //计数器提示用户输入第几项
	pHead=*head;
	scanf("%d,%d",&c,&exp);
	while(c!=0)   //系数为0表示结束输入
	{
		pTemp=(PLinklist)malloc(sizeof(PNode));
		if(pTemp)
		{
			pTemp->exp=exp;  //接收指数
			pTemp->coef=c;   //接收系数
			pTemp->next=NULL;
			pHead->next=pTemp;
			pHead=pTemp;
			scanf("%d,%d",&c,&exp); 
		}
		else
		return 0;
	 } 
	 return 1;
  } 
void Polyadd(PLinklist LA,PLinklist LB)  //两个多项式相加，该方法中两个表都是按指数顺序增长
  {
  	//对指数进行对比分三类情况：A<B时将A链到LA后，A＝＝Ｂ时比较系数，A＞Ｂ时将B链到表中
	  PNode*LA1=LA->next;  //用于在LA中移动
	  PNode*LB1=LB->next;  //用于在LB中移动
	  //LA与LB在充当LA1和LB1 的前驱
	  PNode*temp; //保存要删除的结点
	  int sum=0;  //存放系数的和
	  while(LA1&&LB1)
	  {
	  	if(LA1->exp<LB1->exp)
	  	{
	  		LA->next=LA1; //LA的当前结点可能是LB1或LA1
			LA=LA->next;
			LA1=LA1->next;
		  }
		  else if(LA1->exp==LB1->exp) //指数相等系数相加
		  {
		  	sum=LA1->coef+LB1->coef;
		  	if(sum)  //系数不为0，结果存入LA1中，同时删除结点LB1
			{
				LA1->coef=sum;
				LA->next=LA1;
				LA=LA->next;
				LA1=LA1->next;
				temp=LB1;
				LB1=LB1->next;
				free(temp);
			 } 
			 else  //系数为0时的情况下删除两个结点
			 {
			 	temp=LA1;
			 	LA1=LA1->next;
			 	free(temp);
			 	temp=LB1;
			 	LB1=LB1->next;
			 	free(temp);
			  } 
		   } 
		   else
		   {
		   	LA->next=LB1;
		   	LA=LA->next;
		   	LB1=LB1->next;
		   }
	   } 
	   if(LA1)   //将剩余结点链入链表
	        LA->next=LA1;
		else
		    LA->next=LB1; 
} 
void Print(PLinklist head) //输出多项式
{
	head=head->next;
	while(head)
	{
		if(head->exp)
		   printf("%dx^%d",head->coef,head->exp);
		else
		   printf("%d",head->coef);
		if(head->next)
		   printf("+");
		else
		   break;
		head=head->next;
	}
 } 
 int main()
 {
 	PLinklist LA; //多项式列表LA
	PLinklist LB; //多项式列表LB
	Init(&LA);
	Init(&LB);
	printf("输入第一个多项式的系数，指数(例如10，2)输入0，0结束输入\n");
	CreateFromTail(&LA);
	printf("输入第二个多项式的系数，指数(例如10，2)输入0，0结束输入\n");
	CreateFromTail(&LB);
	Print(LA);
	printf("\n");
	Print(LB);
	printf("\n");
	Polyadd(LA,LB);
	printf("两个多项式相加的结果:\n");
	Print(LA); //相加后结果保存在LA中，打印LA 
	printf("\n");
 }

运行结果

注意：这里两个多项式按指数增长输入，运行如下：