【数据结构】多项式乘法与加法（c语言链表实现）

小咪咪 2021-11-17 00:44 367阅读 0赞

# 设计函数分别求两个一元多项式的乘积与和。 #

### 输入格式: ###

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

### 输出格式: ###

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

### 输入样例: ###

4 3 4 -5 2 6 1 -2 0  
3 5 20 -7 4 3 1

### 输出样例: ###

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1  
5 20 -4 4 -5 2 9 1 -2 0

## 题意理解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190729170310790.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

## 求解思路 ##

### 1.多项式表示 ###

#### 数据结构设计 ####

//将struct与typedef分开定义
    typedef struct PolyNode *Polynomial;	//使用 typedef 给一个还未完全声明的类型 PolyNode 起了一个新别名Polynomial
    struct PolyNode{
    	int coef;			//系数
    	int expon;			//指数
    	Polynomial link;	//指向下一个域的指针（声明link，类型是Polynomial，Polynomial表示的是结构体的别名）
    };

![在这里插入图片描述][20190729161415122.png]

### 2.程序框架 ###

int main()
    {
    	Polynomial P1,P2,PP,PS;
    	//读入多项式1，P1、P2都是链表结构的指针
    	P1=ReadPoly();
    	//读入多项式2
    	P2=ReadPoly();
    	//乘法运算并输出，返回的也是指针
    	PP=Mult(P1,P2);
    	PrintPoly(PP);	
    	//加法运算并输出
    	PS=Add(P1,P2);
    	PrintPoly(PS);
    	return 0;
    }

### 3.读多项式 ###

题目要求先输入有多少项，再一对对输入系数和指数，中间用空格分隔

> Rear初值是多少？

两种处理方法：

1.  Rear初值为NULL，在Attach函数中根据Rear是否为NULL做不同处理
2.  Rear指向一个空结点，最后再删除空结点（一致性更强）  
    ![在这里插入图片描述][20190729162758138.png]

Polynomial ReadPoly()
    {
    	Polynomial P,Rear,t;
    	int c,e,N;
    	//先读入一个整数
    	scanf("%d",&N);
    	//链表头空结点
    	P=(Polynomial)malloc(sizeof(struct PolyNode));
    	P->link=NULL;
    	Rear=P;
    	//再一对对读系数指数
    	while(N--)
    	{
    		scanf("%d %d",&c,&e);
    		//每读入一个结点，插在当前结果表达式的后面。rear要改变，所以传指针
    		Attach(c,e,&Rear);
    	}
    	//删除临时生成的头节点
    	t=P;
    	P=P->link;
    	free(t);
    	return P;
    }

![在这里插入图片描述][20190729162821939.png]  
![在这里插入图片描述][20190729163016507.png]

//传入系数、指数、Polynomial类型的指针（Polynomial本身也是指针）
    void Attach(int c,int e,Polynomial *pRear)
    {
    	Polynomial P;
    
    	//申请新结点，结点类型为结构体PolyNode
    	P=(Polynomial)malloc(sizeof(struct PolyNode));
    	//对新结点赋值
    	P->coef=c;
    	P->expon=e;
    	P->link=NULL;
    	(*pRear)->link=P;
    	*pRear=P;	//修改pRear的值
    }

### 4.加法实现 ###

int compare(int e1,int e2){
        if(e1>e2) return 1;
        else if(e1<e2) return -1;
        else return 0;
    }
    
    Polynomial Add(Polynomial P1,Polynomial P2){
        Polynomial PS,rear,temp;
        int sum;
        //构造空结点，rear指向当前处理结果的尾巴
        PS=(Polynomial)malloc(sizeof(struct PolyNode));
        PS->link=NULL;
        rear=PS;
        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);//coef=0 then do nothing
                    P1=P1->link;
                    P2=P2->link;
                    break;
            }
        }
        while(P1){
            Attach(P1->coef,P1->expon,&rear);
            P1=P1->link;
        }
        while(P2){
            Attach(P2->coef,P2->expon,&rear);
            P2=P2->link;
        }
        //rear->link=NULL;
        temp=PS;
        PS=PS->link;
        free(temp);
        return PS;
    }

### 5.乘法实现 ###

将P1当前项(c1i,e1i)乘P2当前项（c2i,e2i),并插入到结果多项式中。关键是要找到**插入位置**（要求指数递减）  
初始结果多项式可由P1第一项乘P2获得（如上）

Polynomial Mult(Polynomial P1,Polynomial P2)
    {
    	Polynomial P,Rear,t1,t2,t;
    	int c,e;
    	//P1、P2相乘， 只要有一个为空，返回null
    	if(!P1||!P2) return NULL;
    	t1=P1;
    	t2=P2;
    	//申请空结点
    	P=(Polynomial)malloc(sizeof(struct PolyNode));
    	P->link=NULL;
    	Rear=P;
    	//先用P1的第一项乘以P2，得到P
    	while(t2){
    		Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
    		t2=t2->link;	//t2往后挪
    	}
    	t1=t1->link;
    	//两重循环 t1每一项乘t2每一项
    	while(t1){
    		t2=P2;
    		Rear=P;	//Rear一开始指向P
    		while(t2){
    			e=t1->expon+t2->expon;	//指数相加得到当前指数
    			c=t1->coef*t2->coef;	//系数相乘得到当前系数
    			//找插入位置。比较指数，将当前结果按照指数降序插进结果多项式
    			while(Rear->link&&Rear->link->expon>e)	//Rear的下一项的指数大于要插入的指数，所以rear还要往后挪
    				Rear=Rear->link;
    			if(Rear->link&&Rear->link->expon==e){	//Rear的下一项的指数等于要插入的指数，要做合并
    				if(Rear->link->coef+c)				//系数相加后不等于0，c加进原来的
    					Rear->link->coef+=c;
    				else{								//系数相加后等于0，删掉
    					t=Rear->link;
    					Rear->link=t->link;
    					free(t);
    				}
    			}else{										//Rear的下一项的指数小于要插入的指数，可以插入
    				t=(Polynomial)malloc(sizeof(struct PolyNode));	//申请一个新结点
    				t->coef=c;t->expon=e;
    				t->link=Rear->link;								//插入新结点
    				Rear->link=t;Rear=Rear->link;
    			}
    			t2=t2->link;
    		}
    		t1=t1->link;
    	}
    	//第一个空结点要删掉
    	t2=P;
    	P=P->link;	//指向下一个位置
    	free(t2);
    
    	return P;
    }

### 6.多项式输出 ###

链表遍历

void PrintPoly(Polynomial P)
    { /* 输出多项式 */
    	int flag = 0; /* 辅助调整输出格式用 */
    	if (!P) {
    		printf("0 0\n"); 
    		return;
    	}
    	while (P) {
    		if (!flag)
    			flag = 1;
    		else
    			printf(" ");
    		printf("%d %d", P->coef, P->expon);
    		P = P->link;
    	}
    	printf("\n");
    }

### 运行结果 ###

![在这里插入图片描述][20190729170151993.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211116/ba481fb4e3fa4b12aa689d9196562ae8.png
[20190729170310790.png]: /images/20211116/36cc2291815d49b5ae08ac0a04ef1912.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211116/1051a8e4f21645329fcf68431387db3c.png
[20190729161415122.png]: /images/20211116/257e8ecd8b61477c879923b9dcf7ec6e.png
[20190729162758138.png]: /images/20211116/50e99d568c6b4d0cb41172da14599f62.png
[20190729162821939.png]: /images/20211116/d1b52f2f31aa4678b9703ab8e0c8cd28.png
[20190729163016507.png]: /images/20211116/d1b001e3548445519c020e300e97f449.png
[20190729170151993.png]: /images/20211116/bc4375bc2a504702b58c2c1016b002c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: /images/20211116/eb6acbcc4ca44f6791aa846d81b61928.png