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

一时失言乱红尘 2022-09-14 14:27 184阅读 0赞

# **前期提要** #

**本次代码纯c语言，可以支持输入两个多项式的项式、系数、指数。**

#include<stdio.h>
    #include<stdlib.h>
    typedef struct arrays//定义存放多项式的数组类型
    {
    	double coef;//系数
    	int exp;//指数
    }narray;
    typedef struct pnode//定义单链表节点类型
    {
    	double coef;
    	int exp;
    	struct pnode *next;
    }Node,*LinkList;
    int i;
    
    LinkList create(narray a[],int n);
    void show(LinkList L);
    LinkList add(LinkList ha,LinkList hb);
    void destroy(LinkList L);
    int reader(narray a[]);
    
    int main()
    {
    	LinkList ha,hb,hc;int n1,n2;
    	//narray a={
       {7,0},{3,1},{9,8},{5,17}};
    	//narray b={
       {8,1},{22,7},{-9,8}};
    	narray a[10],b[10];
    	n1=reader(a);n2=reader(b);
    	hc=ha=create(a,n1);
    	printf("多项式A：");show(ha);
    	hb=create(b,n2);
    	printf("多项式B：");show(hb);
    	hc=add(ha,hb);
    	printf("多项式H：");show(hc);
    	destroy(hc);destroy(ha);destroy(hb);
    }
    
    LinkList create(narray a[],int n)
    {
    	LinkList s,q,pre,L;
    	L=(LinkList)malloc(sizeof(Node));
    	L->next=NULL;
    	for(i=1;i<n+1;i++)
    	{
    		s=(LinkList)malloc(sizeof(Node));
    		s->coef=a[i].coef;//用新节点s来录入信息
    		s->exp=a[i].exp;
    		pre=L;//节点pre来保留q的前驱，初值为头节点
    		q=L->next;//q初始化，指向首元节点
    		while(q&&q->exp<s->exp)//通过比较指数找到第一个大于输入项指数的项*q
    		{
    			pre=q;//pre保留q的前头
    			q=q->next;//向下next
    		}
    		s->next=q;//q插到新节点s后头
    		pre->next=s;//q的原前头屁股连接s
    	}return L;
    }
    
    void show(LinkList L)
    {
    	int first=1;
    	Node *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");
    }
    
    LinkList add(LinkList ha,LinkList hb)
    {
    	double c;
    	LinkList pa=ha->next,pb=hb->next,s,tc,hc;//将两个指针指向两个链表
    	hc=(LinkList)malloc(sizeof(Node));//创建个新链表
    	hc->next=NULL;
    	tc=hc;//指针指向新链表
    	while(pa!=NULL&&pb!=NULL)
    	{
    		if(pa->exp>pb->exp)
    		{
    			s=(LinkList)malloc(sizeof(Node));
    			s->exp=pb->exp;s->coef=pb->coef;
    			tc->next=s;tc=s;
    			pb=pb->next;
    		}
    		else if(pa->exp<pb->exp)
    		{
    			s=(LinkList)malloc(sizeof(Node));
    			s->exp=pa->exp;s->coef=pa->coef;
    			tc->next=s;tc=s;
    			pa=pa->next;
    		}
    		else//遇到相同的指数，开始运算
    		{
    			c=pa->coef+pb->coef;
    			if(c!=0)
    			{
    				s=(LinkList)malloc(sizeof(Node));
    				s->exp=pa->exp;s->coef=c;
    			    tc->next=s;tc=s;
    			}//c=0，就是直接跳下去
    			pa=pa->next;
    			pb=pb->next;
    		}
    	}
    	if(pb!=NULL)pa=pb;
    	while(pa!=NULL)
    	{
    		s=(LinkList)malloc(sizeof(Node));
    		s->exp=pa->exp;s->coef=pa->coef;
    		tc->next=s;tc=s;
    		pa=pa->next;
    	}
    	tc->next=NULL;
    	return hc;
    }
    void destroy(LinkList L)
    {
    	LinkList p=L,q=p->next;
    	while(q!=NULL)
    	{
    		free(p);
    		p=q;
    		q=p->next;
    	}
    	free(p);
    	free(q);
    }
    
    int reader(narray stu[])
    {
    	int i,n;
    	static int j=1;
    	printf("这里是多项式相加代码\n");
    	printf("请输入第%d个多项式的项个数\n",j);
    	scanf("%d",&n);
    	printf("请输入第%d个多项式的全部系数:\n",j);
    	for(i=1;i<n+1;i++)
    	   {
    	     scanf("%lf",&stu[i].coef);
    	    }
    	 printf("请输入第%d个多项式的全部指数:\n",j);
    	 for(i=1;i<n+1;i++)
    	   {
    		 scanf("%d",&stu[i].exp);
    	    }
    	 j++;
    	return n;
    }

# 测试数据 #

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

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

**输入**

4
    7 3 9 5
    0 1 8 17
    3
    8 22 -9
    1 7 8

**输出**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_13_color_FFFFFF_t_70_g_se_x_16][]

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