数据结构--链表实现求多项式乘积

超、凢脫俗 2023-10-01 13:06 46阅读 0赞

## 数据结构–链表实现多项式求和&&求积 ##

*  首先，数据的组织形式：使用数组来存储结构体数据相对比较简单。但是为了熟悉链表的使用，这里使用链表。
 *  多项式的表示：输入的时候先输入系数，然后输入指数。输出同样是这样。

### 难点： ###

*  求多项式乘积不像求和，因为后插入数据的指数可能比前一个数据要大，所以需要进行判断。

//链表实现一个多项式的相加和相乘
    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct PolyNode* Polynomial;
    struct PolyNode
    {
        
    	int coef;
    	int expon;
    	Polynomial link;
    };
    void attach(int c, int e, Polynomial* pRear)
    {
        
    	Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));
    	P->coef = c;
    	P->expon = e;
    	P->link = NULL;
    	(*pRear)->link = P;
    	*pRear = P;
    }
    Polynomial readPoly()
    {
        
    	int num1 = 0, c = 0, e = 0;
    	printf("请输入多项式的系数：");
    	scanf("%d", &num1);
    	Polynomial Head = (Polynomial)malloc(sizeof(struct PolyNode));     //构造一个空的头节点
    	Polynomial Rear = Head;
    	Head->link = NULL;
    	while (num1--)
    	{
        
    		scanf("%d %d", &c, &e);
    		attach(c, e, &Rear);
    	}
    	Polynomial T = Head;
    	Head = Head->link;
    	free(T);
    	return Head;
    }
    int compare(int a, int b)
    {
        
    	if (a > b) return 1;
    	else if (a == b) return 0;
    	else return -1;
    }
    Polynomial polyAdd(Polynomial P1, Polynomial P2)
    {
        
    	Polynomial Head, Rear, T;
    	Head = (Polynomial)malloc(sizeof(struct PolyNode));
    	Head->link = NULL;
    	Rear = Head;
    	//比较指数大小，指数大的加入结果多项式，然后指针后移。
    	int sum = 0;
    	while (P1 && P2)
    	{
        
    		switch (compare(P1->expon, P2->expon))
    		{
        
    		case 1:
    			attach(P1->coef, P1->expon, &Rear);
    			P1 = P1->link;
    			break;
    		case 0:
    			sum = P1->coef + P2->coef;
    			if (sum) attach(sum, P1->expon, &Rear);
    			P1 = P1->link; P2 = P2->link;
    			break;
    		case -1:
    			attach(P2->coef, P2->expon, &Rear);
    			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);
    	T = Head;
    	Head = Head->link;
    	free(T);
    	return Head;
    }
    void printPoly(Polynomial P)
    {
        
    	int flag = 0;
    	while (P)
    	{
        
    		if (flag)
    		{
        
    			printf(" ");
    		}
    		else
    		{
        
    			flag = 1;
    		}
    		printf("%d %d", P->coef, P->expon);
    		P = P->link;
    	}
    }
    Polynomial polyMulti(Polynomial P1, Polynomial P2)
    {
        
    	Polynomial T1, T2, Head, Rear, P;            //需要使用多项式首元素的指针，因此设置了T1，T2
    	Head = (Polynomial)malloc(sizeof(struct PolyNode));
    	Head->link = NULL;
    	Rear = Head;
    	T1 = P1;
    	while (T1)
    	{
        
    		T2 = P2; Rear = Head;
    		while (T2)
    		{
        
    			//进行排序插入
    			int c = T1->coef * T2->coef;
    			int e = T1->expon + T2->expon;
    			while (Rear->link && Rear->link->expon > e)
    			{
        
    				Rear = Rear->link;
    			}
    			if (Rear->link && Rear->link->expon == e)
    			{
        
    				if (c + Rear->link->coef) Rear->link->coef = c + Rear->link->coef;
    				else
    				{
        
    					Polynomial tmp = Rear->link;
    					Rear->link = tmp->link;
    					free(tmp);
    				}
    			}
    			else
    			{
        
    				P = (Polynomial)malloc(sizeof(struct PolyNode));
    				P->coef = c;
    				P->expon = e;
    				P->link = Rear->link;
    				Rear->link = P;
    				Rear = Rear->link;
    			}
    			T2 = T2->link;
    		}
    		T1 = T1->link;
    	}
    	Polynomial ttt = Head;
    	Head = ttt->link;
    	free(ttt);
    	return Head;
    }
    int main()
    {
        
    	//输入多项式1 && 输入多项式2
    	Polynomial P1 = readPoly();
    	Polynomial P2 = readPoly();
    	//计算多项式和并输出
    	Polynomial P3 = polyAdd(P1, P2);
    	printPoly(P3);
    	//计算多项式乘积并输出
    	Polynomial P4 = polyMulti(P1, P2);
    	printf("\n");
    	printPoly(P4);
    	return 0;
    }

### 结果如下 ###

如求多项式：  
3x4\+5x2\+6x1\+2 和  
5x20\+7x4\+3x 的乘积  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Ya36ZuoR2llR2ll_size_20_color_FFFFFF_t_70_g_se_x_16]  
和是：5x20\+10x4\+5x2\+9x+2  
乘积为：15x24\+25x22\+30x21\+…

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Ya36ZuoR2llR2ll_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/e1b9a734727240a38d8877f6bd75e6af.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Ya36ZuoR2llR2ll,size_20,color_FFFFFF,t_70,g_se,x_16