博客

C语言—链表实现一元多项式的加减乘

  • Post author:
  • Post category:其他


一元多项式的表示及相加

在数学上，一个一元多项式Pn(x)可以按照升幂写成：

Pn(x)=p0+p1x+p2x^2+….pnx^n

这个表达式由系数（coef），指数（expn）两部分组成，由此我们可以用链表(带有头结点)表示一个一元多项式，如下：

采用上述链表方式，我们可以创建两个链表来分别存放两个一元多项式表达式，然后再将他们相加，减，乘后的结果分别保存到新创建的链表中。

具体实现如下：

Polynomial_AddSubMult.h头文件： 

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

#define EPS 0.000001 //判断系数是否为0

typedef struct Polynomial
{
	float coef;//系数
	int expn;//指数
	struct Polynomial *next;
}Polynomial,*LinkList;

void InitLinkList(LinkList Head);//初始化链表（带有头结点）

//输入一元多项式的系数，指数（按照多项式指数升幂输入）
void InsertTail(LinkList Head,float ceof,int expn);

//完成一元多项式的加法运算Result_Add = Headf + heafg;
void AddPolynomial(LinkList Headf,LinkList Headg,LinkList Result_Add);

//完成一元多项式的减法运算Result_Sub = Headf - heafg;
void SubPolynomial(LinkList Headf,LinkList Headg,LinkList Result_Sub);

//完成一元多项式的乘法运算Result_Mult = Headf * heafg;
void MultPolynomial(LinkList Headf,LinkList Headg,LinkList Result_Mult,LinkList Headd,LinkList Headd2);

int GetLegth(LinkList Head);

int IsEmpty(LinkList Head);

void Delete_Head(LinkList plist);

void Clear(LinkList Head);

void Destory(LinkList Head);

void Show(LinkList Head);

函数说明：Polynomial_AddSubMult.c 

#include"Polynomial_AddSubMult.h"
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<math.h>

static LinkList _ApplyNode(float ceof,int expn,LinkList next)//申请空间，作为内部函数，不能对外访问
{
	LinkList s = (LinkList)malloc(sizeof(Polynomial));
	if(s == NULL)
	{
		printf("_ApplyNode：Application Node Failed\n");
		return NULL;
	}

	s->coef = ceof;
	s->expn = expn;
	s->next = next;

	return s;
}

void InitLinkList(LinkList Head)
{
	assert(Head != NULL);
	if(Head == NULL)
	{
		printf("InitLinkList：Empty HeadNode\n");
		return ;
	}
	Head->next = NULL;
}

void InsertTail(LinkList Head,float ceof,int expn)
{
	assert(Head != NULL);
	if(Head == NULL)
	{
		printf("InsertTail：Empty HeadNode\n");
		return ;
	}

	LinkList p = Head;
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = _ApplyNode(ceof,expn,NULL);
}
//完成一元多项式的加法运算Headr = Headf + heafg;
void AddPolynomial(LinkList Headf,LinkList Headg,LinkList Result_Add)
{
	if(Headf == NULL || Headg == NULL || Result_Add == NULL)
	{
		printf("AddPolynomial：Empty LinkList\n");
		return;
	}

	LinkList pf = Headf->next,pg = Headg->next;

	while (pf != NULL && pg != NULL)
	{
		if(pf->expn > pg->expn)
		{			
			InsertTail(Result_Add,pg->coef ,pg->expn);
			pg = pg->next;
		}
		else if(pf->expn < pg->expn)
		{
			InsertTail(Result_Add,pf->coef ,pf->expn);
			pf = pf->next;
		}
		else
		{
			if ((pf->coef + pg->coef) > EPS)//防止两个表达式中出现指数相同，系数互为相反数的情况
			{
				InsertTail(Result_Add,pf->coef + pg->coef,pf->expn);
				pf = pf->next;
				pg = pg->next;			
			}
			else
			{
				pf = pf->next;
				pg = pg->next;		
			}
		}
	}
	//下面两个while循环是表示如果还有一个表达式没有遍历完，可以最后直接插入到结果表达式结尾
	while (pf != NULL)
	{
		InsertTail(Result_Add,pf->coef ,pf->expn);
		pf = pf->next;
	}
	while (pg != NULL)
	{
		InsertTail(Result_Add,pg->coef ,pg->expn);
		pg = pg->next;
	}
}

//完成一元多项式的减法运算Result_Sub = Headf - heafg;
void SubPolynomial(LinkList Headf,LinkList Headg,LinkList Result_Sub)
{
	
	if(Result_Sub == NULL || Headg == NULL || Headf == NULL)
	{
		printf("SubPolynomial：Empty LinkList\n");
		return;
	}

	LinkList pf = Headf->next,pg = Headg->next;

	while (pf != NULL && pg != NULL)
	{
		if(pf->expn > pg->expn)
		{
			InsertTail(Result_Sub,-pg->coef ,pg->expn);
			pg = pg->next;			
		}
		else if(pf->expn < pg->expn)
		{
			InsertTail(Result_Sub,pf->coef ,pf->expn);
			pf = pf->next;
		}
		else if( (pf->coef - pg->coef) > EPS) //系数相减不为0
		{
			InsertTail(Result_Sub,pf->coef - pg->coef,pf->expn);		
			pf = pf->next;
			pg = pg->next;		
		}
		else if( (pg->coef - pf->coef) > EPS)
		{
			InsertTail(Result_Sub,pf->coef - pg->coef,pf->expn);		
			pf = pf->next;
			pg = pg->next;		
		}
		else
		{
			pf = pf->next;
			pg = pg->next;		
		}
	}
	while (pf != NULL)
	{
		InsertTail(Result_Sub,pf->coef ,pf->expn);
		pf = pf->next;
	}
	while (pg != NULL)
	{
		InsertTail(Result_Sub,-pg->coef ,pg->expn);
		pg = pg->next;
	}
}
//完成一元多项式的乘法运算Result_Mult = Headf * heafg;
void MultPolynomial(LinkList Headf,LinkList Headg,LinkList Result_Mult,LinkList Headd1,LinkList Headd2)
{
	if(IsEmpty(Headf) || IsEmpty(Headg) || Result_Mult == NULL)
	{
		printf("MultPolynomial：Empty LinkList\n");
		return;
	}

	LinkList pf = Headf->next,pg = Headg->next;
	
	for(int i = 0;pf != NULL;pf = pf->next,i++)
	{
		Clear(Result_Mult);
		for(pg = Headg->next;pg != NULL;pg = pg->next)
		{
			if(i % 2 == 0 )
			{
				InsertTail(Headd1,pf->coef * pg->coef,pf->expn + pg->expn);
			}
			else
			{
				InsertTail(Headd2,pf->coef * pg->coef,pf->expn + pg->expn);
			}
		}
		AddPolynomial(Headd1,Headd2,Result_Mult);
		Clear(Headd1);
		Clear(Headd2);
		
		if( i % 2 == 0)
		{
			LinkList s  = Result_Mult->next;
			while (s != NULL)
			{
				InsertTail(Headd1,s->coef,s->expn);
				s = s->next;
			}
		}
		else
		{
			LinkList s  = Result_Mult->next;
			while (s != NULL)
			{
				InsertTail(Headd2,s->coef,s->expn);
				s = s->next;
			}
		}	
	}
}

//头删除,
void Delete_Head(LinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
	{
		printf("The Single LinkList is NULL\n");
		return;
	}

	LinkList q = plist->next;
	if(q != NULL)
	{
		plist->next = q->next;  
	}
	
	free(q);	
}
void Clear(LinkList Head)
{
	assert(Head != NULL);
	if(Head == NULL)
	{
		printf("GetLegth：Empty HeadNode\n");
		return ;
	}
	
	while (!IsEmpty(Head))
	{
		Delete_Head(Head);
	}
}

int GetLegth(LinkList Head)
{
	assert(Head != NULL);
	if(Head == NULL)
	{
		printf("GetLegth：Empty HeadNode\n");
		return 1;
	}

	int length = 0;
	LinkList s = Head->next;
	while (s != NULL)
	{
		length++;
		s = s->next;
	}

	return length;
}

int IsEmpty(LinkList Head)
{
	return (Head->next == NULL || Head == NULL);
}

void Destory(LinkList Head)
{
	assert(Head != NULL);
	if(Head == NULL)
	{
		printf("Destory：Empty HeadNode\n");
		return ;
	}

}

void Show(LinkList Head)
{
	assert(Head != NULL);
	if(Head == NULL)
	{
		printf("Show：Empty HeadNode\n");
		return ;
	}
	LinkList p = Head->next;
	while (p != NULL)
	{
		printf("%4.2fx^%d",p->coef,p->expn);
		
		if(p->next != NULL)
		{	
			if(p->next->coef > EOF)
			{
				printf(" + ");
			}
		}
		p = p->next;
	}
	printf("\n");
}

主函数：main.c 

#include"Polynomial_AddSubMult.h"
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

int main()
{
	Polynomial Headf,Headg,Headd1,Headd2;
	Polynomial Result_Add,Result_Sub,Result_Mult;//这里创建三个链表分别保存相加，减，乘后的结果，目的是使他们之间的结果互不影响

	InitLinkList(&Headf);
	InitLinkList(&Headg);
	InitLinkList(&Headd1);
	InitLinkList(&Headd2);
	InitLinkList(&Result_Add);
	InitLinkList(&Result_Sub);
	InitLinkList(&Result_Mult);

	//分别插入两个一元多项式的系数，指数
	InsertTail(&Headf,3,0);
	InsertTail(&Headf,6,3);
	InsertTail(&Headf,4,5);

	InsertTail(&Headg,2,0);
	InsertTail(&Headg,3,1);
	InsertTail(&Headg,8,2);

	Show(&Headf);
	Show(&Headg);

	AddPolynomial(&Headf,&Headg,&Result_Add);
	printf("一元多项式相加后的结果：");
	Show(&Result_Add);
		
	MultPolynomial(&Headf,&Headg,&Result_Mult,&Headd1,&Headd2);
	printf("一元多项式相乘后的结果：");
	Show(&Result_Mult);

	SubPolynomial(&Headf,&Headg,&Result_Sub);
	printf("一元多项式相减后的结果：");
	Show(&Result_Sub);
	
	Destory(&Headf);
	Destory(&Headg);
	Destory(&Headd1);
	Destory(&Headd2);
	Destory(&Result_Add);
	Destory(&Result_Sub);
	Destory(&Result_Mult);

	return 0;
}

最后给出代码运行结果：


！！！

以上代码过于复杂，但有一个优点就是两个多项式之间的加、减、乘之间互相不影响，但会浪费大量空间。

以后我们给出优化代码来实现一元多向表达式的加、减、乘。


版权声明：本文为qq_44423388原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。