(四)数据结构之线性表的简单应用：多项式求和

素颜马尾好姑娘i 2022-06-08 06:14 205阅读 0赞

## 1、基本思路 ##

采用不带头结点的单向链表，按照指数递减的顺序排列各项。

算法思路：  
a、两个指针P1和P2分别指向这两个多项式第一个结点，不断循环：  
i、P1->expon == P2->expon ： 系数相加，如果结果不为0，则作为多项式对应项系数，同时，P1和P2都分别指向下一项。  
ii、P1->expon > P2->expon ： 将P1的当前项存入多项式，并让P1指向下一项  
iii、P1->expon < P2->expon ：将P2的当前项存入结果多项式，并让P2指向下一项。  
b、当某一多项式处理完后，将另一个多项式的所有结点依次复制到结果多项式中去。

## 2、具体实现 ##

### 2.1 基本数据结构 ###

/* 多项式的基本数据结构 */
    typedef struct PolyNode 
    {
    	int coef; 			// 系数
    	int expon; 			// 指数
    	struct PolyNode *link; 	// 指向下一个节点的指针
    }*Polynomial;

由于使用的是单链表的操作来实现具体的多项式求和问题，所以基本的插入操作可以参考这篇文章 [http://blog.csdn.net/tech\_pro/article/details/78011875][http_blog.csdn.net_tech_pro_article_details_78011875]的链式存储单向链表的简单实现。

### 2.2 多项式相加操作 ###

/* 实现多项式P1和P2相加 */
    Polynomial PolyAdd (Polynomial P1, Polynomial P2)
    {
    	Polynomial front, rear, temp;
    	int sum;
    	
    	rear = (Polynomial) malloc(sizeof(struct PolyNode));
    	front = rear; 			/* 由front 记录结果多项式链表头结点 */
    	while ( P1 && P2 ) 		/* 当两个多项式都有非零项待处理时 */
    	{
    		switch ( Compare(P1->expon, P2->expon) ) 
    		{
    		case 1:
    			Attach( P1->coef, P1->expon, &rear);
    			P1 = P1->link;
    			break;
    		case -1:
    			Attach(P2->coef, P2->expon, &rear);
    			P2 = P2->link;
    			break;
    		case 0:
    			sum = P1->coef + P2->coef;
    			if ( sum ) Attach(sum, P1->expon, &rear);
    			P1 = P1->link;
    			P2 = P2->link;
    			break;
    		}
    	}
    	
    	/* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */
    	for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
    	for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear);
    	rear->link = NULL;
    	
    	temp = front;
    	front = front->link; 	/*令front指向结果多项式第一个非零项 */
    	free(temp); 			/* 释放临时空表头结点 */
    	return front;
    }

里面会调用这个函数：Attach，它的功能是构造一个多项式结点并把该多项式结点插入到指定多项式链表的末尾，它的具体实现如下：

/* 构造一个多项式结点并把该多项式结点插入到指定多项式链表的末尾 */
    void Attach( int coef, int expon, Polynomial *PtrRear )
    { 
    	Polynomial P;
    	P =(Polynomial)malloc(sizeof(struct PolyNode)); 	/* 申请新结点 */
    	if(P == NULL)
    	{
    		printf("Attach malloc is failed!\n");
    		return;
    	}
    	P->coef = coef; 			/* 对新结点赋值 */
    	P->expon = expon;
    
    	/* 将P指向的新结点插入到当前结果表达式尾项的后面 */
    	(*PtrRear)->link = P;
    	*PtrRear = P; 				/* 修改PtrRear值 */
    }

### 2.3 完整的示例代码实现 ###

/* 基于单向链表的多项式求和问题 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 多项式的基本数据结构 */
    typedef struct PolyNode 
    {
    	int coef; 			// 系数
    	int expon; 			// 指数
    	struct PolyNode *link; 	// 指向下一个节点的指针
    }*Polynomial;
    
    /* 查找链表中第K个元素 */
    Polynomial FindKth( int K, Polynomial PtrP )
    { 
    	Polynomial p = PtrP;
    	int i = 1;
    	while (p !=NULL && i < K )
    	{
    		p = p->link;
    		i++;
    	}
    	if ( i == K ) return p;	/* 找到第K个，返回指针 */
    	else return NULL;		/* 否则返回空 */
    }
    
    
    /* 在第i个结点位置上插入一个新结点 */
    Polynomial Insert( int coef, int expon, int i, Polynomial PtrP )
    { 
    	Polynomial p, s;
    	if ( i == 1 ) 
    	{ 
    		/* 新结点插入在表头 */
    		s = (Polynomial)malloc(sizeof(struct PolyNode)); /*申请、填装结点*/
    		s->coef = coef;
    		s->expon = expon;
    		s->link = PtrP;
    		return s; /*返回新表头指针*/
    	}
    	p = FindKth( i-1, PtrP ); /* 查找第i-1个结点 */
    	if ( p == NULL ) 
    	{ 
    		/* 第i-1个不存在，不能插入 */
    		printf("the node of i-1 is not exist!\n");
    		return NULL;
    	}
    	else 
    	{
    		s = (Polynomial)malloc(sizeof(struct PolyNode)); /*申请、填装结点*/
    		s->coef = coef;
    		s->expon = expon;
    		s->link = p->link; /*新结点插入在第i-1个结点的后面*/
    		p->link= s;
    		return PtrP;
    	}
    }
    
    /* 删除第i个结点 */
    Polynomial Delete( int i, Polynomial PtrP )
    { 
    	Polynomial p, s;
    	if ( i == 1 ) 
    	{ 
    		/* 若要删除的是表的第一个结点 */
    		s = PtrP; 								/*s指向第1个结点*/
    		if (PtrP!=NULL) PtrP = PtrP->link; 		/*从链表中删除*/
    		else return NULL;
    		free(s); 								/*释放被删除结点 */
    		return PtrP;
    	}
    	p = FindKth( i-1, PtrP ); /*查找第i-1个结点*/
    	if ( p == NULL ) 
    	{
    		printf("the node of i-1 is not exist!\n"); return NULL;
    	} 
    	else if ( p->link == NULL )
    	{
    		printf("the node of i is not exist!\n"); return NULL;
    	} 
    	else 
    	{
    		s = p->link; 		/*s指向第i个结点*/
    		p->link = s->link; 	/*从链表中删除*/
    		free(s); 			/*释放被删除结点 */
    		return PtrP;
    	}
    }
    
    /* 销毁一个链表，释放内存空间 */
    void MakeDestroy(Polynomial PtrP)
    {
    	Polynomial PtrTemp = PtrP;
    	Polynomial PtrNext;
    	while(PtrTemp)
    	{
    		PtrNext = PtrTemp->link;
    		free(PtrTemp);
    		PtrTemp = PtrNext;
    	}
    }
    
    /* 遍历多项式 */
    void Traversal(Polynomial PtrP )
    {
    	while(PtrP)
    	{
    		printf("%d-%d ", PtrP->coef, PtrP->expon);
    		PtrP = PtrP->link;
    	}
    	printf("\n");
    }
    
    
    /* 构造一个多项式结点并把该多项式结点插入到指定多项式链表的末尾 */
    void Attach( int coef, int expon, Polynomial *PtrRear )
    { 
    	Polynomial P;
    	P =(Polynomial)malloc(sizeof(struct PolyNode)); 	/* 申请新结点 */
    	if(P == NULL)
    	{
    		printf("Attach malloc is failed!\n");
    		return;
    	}
    	P->coef = coef; 			/* 对新结点赋值 */
    	P->expon = expon;
    
    	/* 将P指向的新结点插入到当前结果表达式尾项的后面 */
    	(*PtrRear)->link = P;
    	*PtrRear = P; 				/* 修改PtrRear值 */
    }
    
    /* 比较两个数的大小 */
    int Compare(int expon1, int expon2)
    {
    	if(expon1 > expon2) return 1;
    	else if (expon1 < expon2) return -1;
    	else return 0;
    }
    
    /* 实现多项式P1和P2相加 */
    Polynomial PolyAdd (Polynomial P1, Polynomial P2)
    {
    	Polynomial front, rear, temp;
    	int sum;
    	
    	rear = (Polynomial) malloc(sizeof(struct PolyNode));
    	front = rear; 			/* 由front 记录结果多项式链表头结点 */
    	while ( P1 && P2 ) 		/* 当两个多项式都有非零项待处理时 */
    	{
    		switch ( Compare(P1->expon, P2->expon) ) 
    		{
    		case 1:
    			Attach( P1->coef, P1->expon, &rear);
    			P1 = P1->link;
    			break;
    		case -1:
    			Attach(P2->coef, P2->expon, &rear);
    			P2 = P2->link;
    			break;
    		case 0:
    			sum = P1->coef + P2->coef;
    			if ( sum ) Attach(sum, P1->expon, &rear);
    			P1 = P1->link;
    			P2 = P2->link;
    			break;
    		}
    	}
    	
    	/* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */
    	for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
    	for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear);
    	rear->link = NULL;
    	
    	temp = front;
    	front = front->link; 	/*令front指向结果多项式第一个非零项 */
    	free(temp); 			/* 释放临时空表头结点 */
    	return front;
    }
    
    
    /* 程序入口 */
    int main()
    {
    	int i;
    	Polynomial P1 = NULL;
    	Polynomial P2 = NULL;
    	Polynomial P3 = NULL;
    	int coef;
    	int expon;
    
    	/* 输入第一个五项的多项式 */
    	printf("Input 5 items <coef expon> : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d %d", &coef, &expon);
    		P1 = Insert(coef, expon, i+1, P1);
    	}
    
    	printf("Input 4 items <coef expon> : ");
    	/* 输入第二个四项的多项式 */
    	for(i = 0; i < 4; i++)
    	{
    		scanf("%d %d", &coef, &expon);
    		P2 = Insert(coef, expon, i+1, P2);
    	}
    
    	/* 进行多项式求和 */
    	P3 = PolyAdd(P1, P2);
    
    	printf("************************************Traversal*******************************\n");
    	/* 遍历三个多项式 */
    	Traversal(P1);
    	Traversal(P2);
    	Traversal(P3);
    
    	/* 销毁三个多项式链表 */
    	MakeDestroy(P1);
    	MakeDestroy(P2);
    	MakeDestroy(P3);
    	
    	return 0;
    }

[http_blog.csdn.net_tech_pro_article_details_78011875]: http://blog.csdn.net/tech_pro/article/details/78011875