多项式乘法

什么是多项式？

由若干个单项式相加组成的代数式叫做多项式（若有减法：减一个数等于加上它的相反数）。
多项式中的每个单项式叫做多项式的项，这些单项式中的最高项次数，就是这个多项式的次数。 多项式中不含字母的项叫做常数项。

在C语言中怎么表示？

最简单直观的方式就是：

将多项式对应的系数储存在数组中，而数组下标就是项的指数

最后写出相应的代码

#include <stdio.h>

int main()
{
    int i, j, m, n;

    scanf("%d", &m);
    double a[m + 1];
    for (i = 0; i <= m; i++)
        scanf("%lf", &a[i]);

    scanf("%d", &n);
    double b[n + 1];
    for (i = 0; i <= n; i++)
        scanf("%lf", &b[i]);

    double c[m + n + 1];
    for (i = 0; i <= m + n; i++)
        c[i] = 0;

    for (i = 0; i <= m; i++)
        for (j = 0; j <= n; j++)
            c[i + j] += a[i] * b[j];
 
    printf("%f*x^%d", c[0], 0);
    for (i = 1; i <= m + n; i++)
        printf(" + %f*x^%d", c[i], i);

    return 0;
}

测试一下

例如

(1 + 2x + 3x ^2)·(1 + 2x)=1 + 4x + 7x ^2 + 6x ^3

结果

下一篇：多项式除法

https://blog.csdn.net/m0_52313753/article/details/112585857

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

输入格式:

输入分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

题意理解

求解思路

1.多项式表示

数据结构设计

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

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指向一个空结点，最后再删除空结点（一致性更强）
   

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;
}

//传入系数、指数、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");
}

运行结果

• 问题描述

一元多项式A 、B 按降次排列，用带头结点的链表存储，求 C=A ×B，试编程实现。

• 代码实现

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

typedef struct Lnode{
	int coef;	//定义系数
	int exp;	//定义指数
	struct Lnode *next;	//指向下一项 
}Lnode; 

void Read(Lnode *node);		//读取函数 
void Write(Lnode *node);	//输出函数 
void Mul(Lnode *node_a,Lnode *node_b,Lnode *node_c);	//乘法运算 
void Add(Lnode *node_a,Lnode *node_b);					//加法运算 

int main(void)
{	
	Lnode *lnode_a=(Lnode *)malloc(sizeof(Lnode));	//多项式A 
	Lnode *lnode_b=(Lnode *)malloc(sizeof(Lnode));	//多项式B 
	Lnode *lnode_c=(Lnode *)malloc(sizeof(Lnode));	//结果多项式C 
	lnode_c->next=NULL;
	printf("请输入多项式A:\n");
	Read(lnode_a);
	printf("\n请输入多项式B:\n");
	Read(lnode_b);
	Mul(lnode_a->next,lnode_b->next,lnode_c);
	printf("\n多项式A、B之积C为：\n");
	Write(lnode_c->next);
	
	return 0;
}

void Read(Lnode *node)
{
	int kaiguan=1; 	char r=getchar();			//kaiguan开关，用于判断存取为系数还是指数 
	node->next=(Lnode *)malloc(sizeof(Lnode));	//建立头结点 
	node=node->next;	node->coef=0;	node->exp=0;
	while(r!='\n')
	{
		if(r=='+')
		{
			node->next = ( Lnode* )malloc( sizeof( Lnode ) ); 
			node=node->next;	node->coef=0;	node->exp=0;
			kaiguan=1-kaiguan;
		}
		else	if(r=='x'||r=='X')	kaiguan=1-kaiguan;				//调整开关状态 
		else	if(kaiguan)	node->coef=10*(node->coef) + (r-48);	// ascII码存取数字 
		else	node->exp=10*(node->exp) + (r-48);
		r=getchar();
	}
	
		node->next=NULL;
}

void Write(Lnode *node)
{
	printf("%dX^%d ",node->coef,node->exp);
	node=node->next;
	while(node->next != NULL)
	{
		printf("+ %dX^%d ",node->coef,node->exp);
		node=node->next;
	}
	if(node->exp != 0)
		printf("+ %dX^%d",node->coef,node->exp);
	else if(node->coef != 0)
		printf("+ %d",node->coef);
}

void Mul(Lnode *node_a,Lnode *node_b,Lnode *node_c)
{
	Lnode *node_d=(Lnode *)malloc(sizeof(Lnode));	//D用于存放B的每一项与A的乘积 
	Lnode *memmory=node_d; 							//memmory记住D的头结点 
	Lnode *head=node_a;								//head记住A的头结点 
	node_d->next=(Lnode *)malloc(sizeof(Lnode));
	while(node_b!=NULL) 
	{
		while(node_a!=NULL)
		{	
			node_d=node_d->next;
			node_d->exp=node_a->exp+node_b->exp;
			node_d->coef=node_a->coef*node_b->coef;
			node_d->next=(Lnode *)malloc(sizeof(Lnode));
			node_a=node_a->next;
		}
		node_d->next=NULL;							 
		Add(node_c,memmory);						//将每次D的结果加入到C中 
		node_d=(Lnode *)malloc(sizeof(Lnode));
		memmory=node_d; 
		node_d->next=(Lnode *)malloc(sizeof(Lnode));
		node_a=head;
		node_b=node_b->next;
	}
}

void Add(Lnode *node_a,Lnode *node_b)
{	
	Lnode *node_c=node_a,*node_d=node_b->next;	//C的地址为A的前一项，D的地址与B同时 
	node_a=node_a->next;						//将B的每一项加入至A中，无需新建一个单链表；					
	node_b=node_b->next;                        //也可新建一个单链表，同时比较A、B的第一项，依次向后延申 
	while(node_b!=NULL)
	{
		if(node_a==NULL)
		{
			node_a=(Lnode *)malloc(sizeof(Lnode));
			node_a->exp=0;
			node_a->coef=0;
			node_a->next=NULL;
		}
		if(node_a->exp==node_b->exp)
		{
			node_a->coef=node_a->coef+node_b->coef;
			node_a=node_a->next;
			node_b=node_b->next;
			node_c=node_c->next;
			node_d=node_d->next;
		}
		else if(node_a->exp > node_b->exp)
		{
			node_a=node_a->next;
			node_c=node_c->next;
		}
		else if(node_a->exp < node_b->exp)
		{
			node_c->next=node_b;
			node_b=node_b->next;
			node_d->next=node_a;
			node_d=node_b;
			node_c=node_c->next;
		}
	}
}

• 知识总结

1. 线性表是具有相同特性数据元素的一个有限序列，其中序列所含元素的个数叫做线性表的长度。
2. 线性表的存储结构：顺序存储结构、链式存储结构。前者为顺序表，后者为链表。
3. 顺序表的两个特性：随机访问特性、占用连续的存储空间（存储分配只能预先进行）。
4. 链表的三个特性：不支持随机访问、结点的存储空间利用率稍低于线性表、支持存储空间的动态分配。
5. 带头结点的单链表 head=head->next 时链表为空；不带头结点时 head=NULL 时链表为空。
6. 顺序表和链表的比较

      (1)  基于空间的比较

          1）存储分配：顺序表  一次性分配； 链表  多次分配

          2）存储密度：顺序表  密度=1      ； 链表  密度<1

      (2)  基于时间的比较

          1） 存取方式：顺序表  随机存储  ；  链表  顺序存储

          2）  插入/删除 移动元素个数： 顺序表  近一半元素；链表  不移动元素