(第3种)用单链表存储一元多项式，并实现两个多项式相加运算

短命女 2022-09-14 14:26 165阅读 0赞

**本次代码是纯c语言版本的**

#include<stdio.h>
    #include<stdlib.h>
    typedef struct//定义存放多项式的数组类型
    {
    	double coef;//系数
    	int exp;//指数
    }narray[10];
    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 main()
    {
    	LinkList ha,hb,hc;
    	narray a={
       {7,0},{3,1},{9,8},{5,17}};
    	narray b={
       {8,1},{22,7},{-9,8}};
    	hc=ha=create(a,4);
    	printf("多项式A：");show(ha);
    	hb=create(b,3);
    	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=0;i<n;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);
    }

**输出**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_17_color_FFFFFF_t_70_g_se_x_16][]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/39301dffd2154ebdb97b440e0fcc625f.png