#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
	float coef;
	int index;
	struct LNode *next; 
}LNode,*Polynomial;
void CreatePoly(Polynomial *AB,int size);
Polynomial AddPolyn(Polynomial A,Polynomial B);
void PrintPoly(Polynomial A);
void main(){
	Polynomial A,B;//如果在main函数对A初始化分配地址，则可以直接穿A即指向首地址的指针 
	Polynomial p;
	int LA,LB;//两个多项式的长度
	printf("请输入第一个多项式的项数：");
	scanf("%d",&LA); 
	CreatePoly(&A,LA);//因为开始声明的A是野指针，只有地址传递让其指向分配的地址空间 ， 
	//声明一个变量时操作系统会分配内存存储该变量，指针也是变量 
	//&A即指针存放A的地址，而不是A指向的地址，A是野指针，指向地址未知 
	PrintPoly(A);
	printf("请输入第二个多项式的项数：");
	scanf("%d",&LB);
	CreatePoly(&B,LB); 
	PrintPoly(B);
	p = AddPolyn(A,B);//经过创建A已经不是野指针，而是指向单链表，故此处可直接穿指针
	printf("和多项式为："); 
	PrintPoly(p);
} 

void CreatePoly(Polynomial *AB,int size){//多项式的项数 //*AB是双重指针 
	*AB = (Polynomial)malloc(sizeof(LNode));//分配头结点 //此时*AB就和mian中的A等价，即指针AB指向了存放A的地址 *AB=A;对*AB初始化即相当于对A初始化 
//AB=&A;*AB=A;即初始化让A指向了分配的空间	
	LNode *r,*s;
	r = *AB;
	int i = 0;
	for(i=0;i<size;i++){
		s = (LNode*)malloc(sizeof(LNode));
		printf("请输入系数和指数(空格隔开):");//scanf会跳过空格，逗号会产生错误 
		scanf_s("%f %d",&s->coef,&s->index); 
		r->next = s;
		r = s;
	} 
	r->next = NULL;
	
	
}
void PrintPoly(Polynomial A){
	LNode *p;
	p = A->next;
	while(p){
		printf("%.2f X^%d",p->coef,p->index);
		//将多项式连接起来显示,最后一个结点无符号故在每一个结点之前输出加减号 
		p = p->next; 
		if(p!=NULL){
			if(p->coef>=0)
				printf("+");
			else
				printf("-");
		} 
	}
	printf("\n");
} 
Polynomial AddPolyn(Polynomial A,Polynomial B){
	LNode *a,*b;//分别指向A，B 
	LNode *Deletea,*Deleteb;//用来指向系数为0时要释放的结点 
	a = A->next;
	b = B->next; 
	Polynomial C;
	LNode *Crear;//指针，用来指向和多项式的头和尾
	//可以考虑给C一个头结点，
	C = (Polynomial)malloc(sizeof(LNode));
	C->next  = NULL;
	Crear =  C; 
	while(a!=NULL&&b!=NULL){
		if((a->index)<(b->index)){
			Crear->next = a;
			Crear = a;
			a = a->next;
		}//if
		else if(a->index==b->index){
			if(a->coef+b->coef==0){
				 Deletea = a;
				 a = a->next;
				 Deleteb = b;
				 b = b->next;
				 free(Deletea);
				 free(Deleteb); 
			}//if
			else{ 
				a->coef+=b->coef;//两个结点合并为一个，删除一个 
				Crear->next = a;
				Crear = a;
				Deleteb = b;
				b = b->next;				
				a = a->next;
				free(Deleteb);
			}//else
		}
		else{
			Crear->next = b;
			Crear = b;
			b = b->next;
		}
	}//while 
//一轮处理结束一个多项式以全部处理还有一个未处理完 注意上面以经->next 
	while(a!=NULL){
		Crear->next = a; 
		Crear = a;
		a =a->next; 
	}
	while(b!=NULL){
		Crear->next = b;
		Crear = b;
		b =b->next; 
	}		
	return C;
//	Crear = Chead = NULL;//C不带头结点太复杂 
//	while(a!=NULL&&b!=NULL){
//		if(a->index<b->index){
//			if(Chead==NULL){//没有头结点直接第一个结点需单独处理 
//				Chead = a;
//				Crear = a; 
//			}
//			else{
//				Crear->next = a;//将小阶结点插入C 
//			}
//			a  = a->next;
//		}
//		else if(a->index==b->index){
//			if(a->coef+b->coef==0){
//				 Deletea = a;
//				 a = a->next;
//				 Deleteb = b;
//				 b = b->next;
//				 free(Deletea);
//				 free(Deleteb); 
//			}
//			else{
//				if(Chead==NULL){//没有头结点直接第一个结点需单独处理 
//					a->coef+=b->coef;//两个结点合并为一个，删除一个 
//					Chead = a;
//					Crear = a; 
//					Deleteb = b;
//					b = b->next;
//					a = a->next;
//					free(Deleteb);
//				}
//				else{
//					Crear->next = a;//将小阶结点插入C 
//				}
//				a  = a->next;
//			}
//		}
//	} 


}

二、 实验内容及要求
任务描述
设有一元多项式Am(x)和Bn(X)，编程实现多项式Am(x)和Bn(x)的加法、减法和乘法运算。其中多项 式描述为：

Am(x)=A0+A1x1+A2x2+A3x3+….+Amxm；
Bn(x)=B0+B1x1+B2x2+B3x3+….+Bnxn。

程序源代码：

DS.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;

LinkList.h

#include <DS.h>
typedef struct LNode
{
    int data;
    int index;
    struct LNode *next;
}LNode, *LinkList;

LinkList makeList();  //生成一个空链表
void Insert(LinkList L, int data, int index);  //添加
void Delete(LinkList L, LinkList position);    //删除
LinkList Find(LinkList L, int index);          //查找
LinkList makeFirstList();   //输入第一个多项式
LinkList makeSecondList();  //输入第二个多项式
LinkList sum(LinkList L1, LinkList L2);   //加法
LinkList sub(LinkList L1, LinkList L2);   //减法
LinkList mul(LinkList L1, LinkList L2);   //乘法
int getFlag();    //排序方式
void ascOrder(LinkList L);      //升幂排列
void descOrder(LinkList L);     //降幂排列
void exportResult(LinkList L,int flag);   //输出结果

LinkList.c

#include <LinkList.h>

LinkList makeList()
{
    LinkList L = (LinkList)malloc(sizeof(struct LNode));
    L->data = 0;
    L->index = 0;
    L->next = NULL;
    return L;
}

void Insert(LinkList L,int data,int index)
{
    LinkList p = L;
    LinkList q = (LinkList)malloc(sizeof(struct LNode));
    q->next = NULL;
    q->data = data;
    q->index = index;
    q->next = p->next;
    p->next = q;
}

void Delete(LinkList L,LinkList position)
{
    LinkList p = L->next;
    LinkList q = L;
    while (p)
    {
        if (p == position)
        {
            q->next = p->next;
            free(p);
            break;
        }
        q = p;
        p = p->next;
    }
}

LinkList Find(LinkList L, int index)
{
    LinkList p = L->next;
    while (p)
    {
        if (p->index == index)
        {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

LinkList makeFirstList()
{
    int n,data,index;
    LinkList L1 = makeList();
    printf("*************欢迎使用一元多项式计算器*************\n\n");
    printf("请输入第一个多项式的项数:\n");
    scanf("%d",&n);
    printf("请输入第一个多项式:\n");
    //printf("(注意:1^2+2^3 应表示为 1 2 2 3, 后面同理)\n");
    for(int i=0; i<n; i++)
    {
        scanf("%d",&data);
        scanf("%d",&index);
        if(data != 0)
        {
            Insert(L1,data,index);
        }
    }
    return L1;
}

LinkList makeSecondList()
{
    int n,data,index;
    LinkList L2 = makeList();
    printf("请输入第二个多项式的项数:\n");
    scanf("%d",&n);
    printf("请输入第二个多项式:\n");
    for(int i=0; i<n; i++)
    {
        scanf("%d",&data);
        scanf("%d",&index);
        if(data != 0)
        {
            Insert(L2,data,index);
        }
    }
    return L2;
}

LinkList sum(LinkList L1,LinkList L2)
{
    int data;
    LinkList L3 = makeList();
    LinkList p1 = L1->next;
    LinkList p2 = L2->next;
    LinkList p;
    LinkList q;
    while(p1!=NULL)
    {
        p = Find(L2,p1->index);
        if(p!=NULL)
        {
            data = p1->data + p->data;
            if(data == 0) {}
            else
                Insert(L3,data,p1->index);
            q = p1;
            p1 = p1->next;
            Delete(L1,q);
            Delete(L2,p);
        }
        else
        {
            Insert(L3,p1->data,p1->index);
            q = p1;
            p1 = p1->next;
            Delete(L1,q);
        }
    }
    p1 = L1->next;
    p2 = L2->next;
    while(p2!=NULL)
    {
        q = Find(L1,p2->index);
        if(q!=NULL)
        {
            data = p2->data + q->data;
            Insert(L3,data,p2->index);
            p = p2;
            p2 = p2->next;
            Delete(L2,p);
            Delete(L1,q);
        }
        else
        {
            Insert(L3,p2->data,p2->index);
            p = p2;
            p2 = p2->next;
            Delete(L2,p);
        }
    }
    return L3;
}

LinkList sub(LinkList L1,LinkList L2)
{
    LinkList L3 = makeList();
    LinkList p2 = L2->next;
    while(p2!=NULL)
    {
        p2->data = (-1) * p2->data;
        p2 = p2->next;
    }
    L3 = sum(L1,L2);
    return L3;
}

LinkList mul(LinkList L1,LinkList L2)
{
    int data,index;
    LinkList L3  = makeList();
    LinkList p1 = L1->next;
    LinkList p2 = L2->next;
    LinkList p;
    while(p1!=NULL)
    {
        p2 = L2->next;
        while(p2!=NULL)
        {
            data = p1->data * p2->data;
            index = p1->index + p2->index;
            p = Find(L3,index);
            if(data == 0)
            {
                p2 = p2->next;
                continue;
            }
            if(p!=NULL)
            {
                p->data += data;
            }
            else
            {
                Insert(L3,data,index);
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    return L3;
}

int getFlag()
{
    int flag;
    printf("请输入排序方式:\n");
    printf("0.升幂\n");
    printf("1.降幂\n");
    scanf("%d",&flag);
    return flag;
}

void descOrder(LinkList L)
{
    int data,index;
    LinkList p1 = L->next;
    LinkList p2 = L->next;
    while(p1!=NULL)
    {
        p2 = L->next;
        while(p2!=NULL)
        {
            if(p1->index > p2->index)
            {
                data = p1->data;
                index = p1->index;
                p1->data = p2->data;
                p1->index = p2->index;
                p2->data = data;
                p2->index = index;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

void ascOrder(LinkList L)
{
    int data,index;
    LinkList p1 = L->next;
    LinkList p2 = L->next;
    while(p1!=NULL)
    {
        p2 = L->next;
        while(p2!=NULL)
        {
            if(p1->index < p2->index)
            {
                data = p1->data;
                index = p1->index;
                p1->data = p2->data;
                p1->index = p2->index;
                p2->data = data;
                p2->index = index;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

void exportResult(LinkList L,int flag)
{
    if(flag == 0)
    {
        ascOrder(L);  //升幂排列
    }
    else if(flag == 1)
    {
        descOrder(L);  //降幂排列
    }
    printf("运算的结果为:\n");
    LinkList p = L->next;


    if(!p)
    {
        printf("0 0");//零多项式输出0 0
    }
    else
    {
        while(p)
        {
            //只有项的系数不为0时才能输出
            if(p->data != 0)
            {
                //当指数为0时，只输出系数
                if(p->index==0) printf("%d",p->data);
                //系数和指数都为1，输出x
                else if(p->data == 1 && p->index == 1) printf("x");
                //系数为-1，指数为1，输出-x
                else if(p->data == -1 && p->index == 1) printf("-x");
                //系数为1，指数不为1，不输出系数
                else if(p->data == 1 && p->index != 1) printf("x^%d",p->index);
                //系数为-1，但是指数不为1，系数只输出-
                else if(p->data == -1 && p->index != 1) printf("-x^%d",p->index);
                //系数不是1或-1，指数为1，不输出指数
                else if((p->data != 1 || p->data != -1) && p->index == 1)  printf("%dx",p->data);
                //系数不是1或-1，指数不为1，系数和指数都输出
                else if((p->data != 1 || p->data != -1) && p->index != 1)  printf("%dx^%d",p->data,p->index);

                //如果有下一项且下一项的系数为大于0的数，则输出+
                if(p->next && p->next->data > 0) printf("+");
                p = p->next;
            }
        }
    }
    printf("\n");
}

main.c

#include <LinkList.h>
int main()
{
    char p;
    int flag;
    LinkList L1 = makeFirstList();
    LinkList L2 = makeSecondList();
    printf("请输入想要进行的运算:\n");
    getchar();
    scanf("%c",&p);
    flag = getFlag();
    switch(p)
    {
    case '+':
        //printf("进行了加法运算!!!\n");
        exportResult(sum(L1,L2),flag);
        break;
    case '-':
        //printf("进行了减法运算!!!\n");
        exportResult(sub(L1,L2),flag);
        break;
    case '*':
        //printf("进行了乘法运算!!!\n");
        exportResult(mul(L1,L2),flag);
        break;
    }
    return 0;
}

测试：

求个赞。。。

输入：第一个一元多项式A； 第二个一元多项式B。 以（0，0）作为输入结束。

输出：多项式A和多项式B的和。

样例输入

5,3 7,8 9,15 0,0
2,0 6,3 -7,8 0,0

样例输出

2x^0+11x^3+9x^15

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

typedef struct LinkNode{
	int coef;//系数
	int index;//指数
	struct LinkNode *next; 
}LinkNode,*LinkList; 

LinkList createLinkNode(){
	LinkList L=(LinkList) malloc(sizeof(LinkNode));
	L->next=NULL;	
	printf("请输入多项式（系数,指数）：");
	LinkNode *q=L,*p;
	int coef,index;
	scanf("%d,%d",&coef,&index);
	while(!(coef==0&&index==0)){
		p=(LinkNode *)malloc(sizeof(LinkNode));
		p->next=NULL;
		p->coef=coef;
		p->index=index;
		q->next=p;
		q=p;
		printf("请继续输入多项式（系数,指数）：");
		scanf("%d,%d",&coef,&index);
	}
	return L;
}

void add(LinkList &L1,LinkList &L2){
	LinkNode *p1,*temp;
	while(L2->next!=NULL){
		p1=L1;
		while(p1->next!=NULL&&p1->next->index!=L2->next->index){
			p1=p1->next;
		}
		temp=L2->next;
		L2->next=temp->next;
		temp->next=NULL;
		if(p1->next==NULL){
			temp->next=p1->next;
			p1->next=temp;
		}else{
			p1->next->coef+=temp->coef;
			free(temp);
			if(p1->next->coef==0){
				temp=p1->next;
				p1->next=temp->next;
				free(temp);
			}
		}
	}
	free(L2);
}

int main(){
	LinkList L1=createLinkNode();
	LinkList L2=createLinkNode();
	add(L1,L2);
	LinkNode *p=L1->next;
	if(p==NULL)return 0;
	while(p!=NULL&&p->next!=NULL){
		printf("%dx^%d+",p->coef,p->index);
		p=p->next;
	}
	if(p!=NULL)printf("%dx^%d",p->coef,p->index);
	return 0;
}