用单链表存储一元多项式，并实现两个多项式相加运算。（c与c++）

梦里梦外; 2022-09-13 11:28 183阅读 0赞

# **测试数据** #

**A17(x)=7+3x+9x8+5x17**

**B8(x)=8x+22x7-9x8**

#  #

# c语言版本 #

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 20
    typedef struct//定义存放多项式的数组类型
    {
    	double coef;//系数
    	int exp;//指数
    }polyarray[MAX];
    typedef struct pnode//定义单链表节点类型
    {
    	double coef;
    	int exp;
    	struct pnode *next;
    }polynode;
    
    polynode *create(polyarray a,int n);
    void show(polynode *L);
    void destroy(polynode *L);
    void sort(polynode *head);
    polynode *add(polynode *ha,polynode *hb);
    
    void show(polynode *L)
    {
    	int first=1;
    	polynode *p=L->next;
    	while(p!=NULL)
    	{
    		if(first)
    			first=0;
    		else if(p->coef>0)
    			printf("+");
    		if(p->exp==0)
    			printf("%g",p->coef);
    		else if(p->exp==1)
    			printf("%gx",p->coef);
    		else
    			printf("%gx^%d",p->coef,p->exp);
    		p=p->next;
    	}
    	printf("\n");
    }
    void destroy(polynode *L)
    {
    	polynode *p=L,*q=p->next;
    	while(q!=NULL)
    	{
    		free(p);
    		p=q;
    		q=p->next;
    	}
    	free(p);
    }
    polynode *create(polyarray a,int n)
    {
    	polynode *s,*r,*L;
    	int i;
    	L=(polynode *)malloc(sizeof(polynode));
    	L->next=NULL;
    	r=L;
    	for(i=0;i<n;i++)
    	{
    		s=(polynode *)malloc(sizeof(polynode));
    		s->coef=a[i].coef;
    		s->exp=a[i].exp;
    		r->next=s;
    		r=s;
    	}
    	r->next=NULL;
    	return L;
    }
    void sort(polynode *head)//按exp域递减排序
    {
    	polynode *p=head->next,*q,*r;
    	if(p!=NULL)
    	{
    		r=p->next;
    		p->next=NULL;
    		p=r;
    		while(p!=NULL)
    		{
    			r=p->next;
    			q=head;
    			while(q->next!=NULL&&q->next->exp>p->exp)
    				q=q->next;
    			p->next=q->next;
    			q->next=p;
    			p=r;
    		}
    	}
    }
    polynode *add(polynode *ha,polynode *hb)
    {
    	double c;
    	polynode *pa=ha->next,*pb=hb->next,*s,*tc,*hc;
    	hc=(polynode *)malloc(sizeof(polynode));
    	tc=hc;
    	while(pa!=NULL&&pb!=NULL)
    	{
    		if(pa->exp>pb->exp)
    		{
    			s=(polynode *)malloc(sizeof(polynode));
    			s->exp=pa->exp;s->coef=pa->coef;
    			tc->next=s;tc=s;
    			pa=pa->next;
    		}
    		else if(pa->exp<pb->exp)
    		{
    			s=(polynode *)malloc(sizeof(polynode));
    			s->exp=pb->exp;s->coef=pb->coef;
    			tc->next=s;tc=s;
    			pb=pb->next;
    		}
    		else
    		{
    			c=pa->coef+pb->coef;
    			if(c!=0)
    			{
    				s=(polynode *)malloc(sizeof(polynode));
    				s->exp=pa->exp;s->coef=c;
    			    tc->next=s;tc=s;
    			}
    			pa=pa->next;
    			pb=pb->next;
    		}
    	}
    	if(pb!=NULL)pa=pb;
    	while(pa!=NULL)
    	{
    		s=(polynode *)malloc(sizeof(polynode));
    		s->exp=pa->exp;s->coef=pa->coef;
    		tc->next=s;tc=s;
    		pa=pa->next;
    	}
    	tc->next=NULL;
    	return hc;
    }
    int main()
    {
    	polynode *ha,*hb,*hc;
    	polyarray a={
       {7,0},{3,1},{9,8},{5,17}};
    	polyarray b={
       {8,1},{22,7},{-9,8}};
    	hc=ha=create(a,4);
    	hb=create(b,3);
    	printf("原多项式A:  ");show(ha);
    	printf("原多项式B:  ");show(hb);
    	sort(ha);
    	sort(hb);
    	printf("有序多项式A:  ");show(ha);
    	printf("有序多项式B:  ");show(hb);
    	hc=add(ha,hb);
    	printf("多项式相加:  ");show(hc);
    	destroy(ha);
    	destroy(hb);
    	destroy(hc);
    	return 0;
    }

**输出**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_13_color_FFFFFF_t_70_g_se_x_16][]

**有的时候，c++与c语言不尽相同，比如引用\*&。**

# **c++版本** #

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 20
    typedef struct//定义存放多项式的数组类型
    {
    	double coef;//系数
    	int exp;//指数
    }polyarray[MAX];
    typedef struct pnode//定义单链表节点类型
    {
    	double coef;
    	int exp;
    	struct pnode *next;
    }polynode;
    
    void create(polynode *&L,polyarray a,int n);
    void show(polynode *L);
    void destroy(polynode *&L);
    void sort(polynode *head);
    void add(polynode *ha,polynode *hb,polynode *&hc);
    
    void show(polynode *L)
    {
    	int first=1;
    	polynode *p=L->next;
    	while(p!=NULL)
    	{
    		if(first)
    			first=0;
    		else if(p->coef>0)
    			printf("+");
    		if(p->exp==0)
    			printf("%g",p->coef);
    		else if(p->exp==1)
    			printf("%gx",p->coef);
    		else
    			printf("%gx^%d",p->coef,p->exp);
    		p=p->next;
    	}
    	printf("\n");
    }
    void destroy(polynode *&L)
    {
    	polynode *p=L,*q=p->next;
    	while(q!=NULL)
    	{
    		free(p);
    		p=q;
    		q=p->next;
    	}
    	free(p);
    }
    void create(polynode *&L,polyarray a,int n)
    {
    	polynode *s,*r;
    	int i;
    	L=(polynode *)malloc(sizeof(polynode));
    	L->next=NULL;
    	r=L;
    	for(i=0;i<n;i++)
    	{
    		s=(polynode *)malloc(sizeof(polynode));
    		s->coef=a[i].coef;
    		s->exp=a[i].exp;
    		r->next=s;
    		r=s;
    	}
    	r->next=NULL;
    }
    void sort(polynode *head)//按exp域递减排序
    {
    	polynode *p=head->next,*q,*r;
    	if(p!=NULL)
    	{
    		r=p->next;
    		p->next=NULL;
    		p=r;
    		while(p!=NULL)
    		{
    			r=p->next;
    			q=head;
    			while(q->next!=NULL&&q->next->exp>p->exp)
    				q=q->next;
    			p->next=q->next;
    			q->next=p;
    			p=r;
    		}
    	}
    }
    void add(polynode *ha,polynode *hb,polynode *&hc)
    {
    	double c;
    	polynode *pa=ha->next,*pb=hb->next,*s,*tc;
    	hc=(polynode *)malloc(sizeof(polynode));
    	tc=hc;
    	while(pa!=NULL&&pb!=NULL)
    	{
    		if(pa->exp>pb->exp)
    		{
    			s=(polynode *)malloc(sizeof(polynode));
    			s->exp=pa->exp;s->coef=pa->coef;
    			tc->next=s;tc=s;
    			pa=pa->next;
    		}
    		else if(pa->exp<pb->exp)
    		{
    			s=(polynode *)malloc(sizeof(polynode));
    			s->exp=pb->exp;s->coef=pb->coef;
    			tc->next=s;tc=s;
    			pb=pb->next;
    		}
    		else
    		{
    			c=pa->coef+pb->coef;
    			if(c!=0)
    			{
    				s=(polynode *)malloc(sizeof(polynode));
    				s->exp=pa->exp;s->coef=c;
    			    tc->next=s;tc=s;
    			}
    			pa=pa->next;
    			pb=pb->next;
    		}
    	}
    	if(pb!=NULL)pa=pb;
    	while(pa!=NULL)
    	{
    		s=(polynode *)malloc(sizeof(polynode));
    		s->exp=pa->exp;s->coef=pa->coef;
    		tc->next=s;tc=s;
    		pa=pa->next;
    	}
    	tc->next=NULL;
    }
    int main()
    {
    	polynode *ha,*hb,*hc;
    	polyarray a={
       {7,0},{3,1},{9,8},{5,17}};
    	polyarray b={
       {8,1},{22,7},{-9,8}};
    	create(ha,a,4);
    	create(hb,b,3);
    	printf("原多项式A:  ");show(ha);
    	printf("原多项式B:  ");show(hb);
    	sort(ha);
    	sort(hb);
    	printf("有序多项式A:  ");show(ha);
    	printf("有序多项式B:  ");show(hb);
    	add(ha,hb,hc);
    	printf("多项式相加:  ");show(hc);
    	destroy(ha);
    	destroy(hb);
    	destroy(hc);
    	return 0;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/acc486ea281c44cd939a292654892d8a.png