多项式的表示及相加

问题描述

数据结构（C语言）用单链表存储一元多项式，并实现两个多项式的相加运算

基本要求

（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，……，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
（3）多项式a和b相加，建立多项式a+b。

思路分析

由于多项式有指数和系数，所以结构体中应该定义三个值：指数，系数，next。然后提示用户输入，第一个多项式的项数，每一项的系数和指数，第二个多项式的项数，每一项的系数和指数。申请两个链表存放他们的系数和指数。

这里以y=1x^2 +2x^3为例

比较两个多项式的指数，如果第一个多项式大，第二个多项式指针就向后一位。
相反如果第二个多项式大，第一个就向后指一位。

如果第一个多项式的指数等于第二个多项式，就让他们的系数相加。

直到有一个多项式到了最后一位，退出循环，不在比较。将指针指向不为空的那个多项式。最后输出，即可。

源代码

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;//系数
	ElementType Number;//指数 
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L );

int main()
{
    List L,L1,L2,p1,p2,p;
	printf("请输入第一个多项式\n");
    L1 = Read();
    printf("请输入第二个多项式\n");
    L2=Read();
    printf("第一个多项式:");
    Print(L1);
    printf("第二个多项式:");
    Print(L2);
    p1=L1->Next;
    p2=L2->Next;
    L=p=L1;// 用L1的头结点作为L的头结点  
    while(p1&&p2){
        if(p1->Number > p2->Number){
            p->Next=p2;
            p=p2;
            p2=p2->Next;
        }else if(p1->Number < p2->Number){
            p->Next=p1;
            p=p1;
            p1=p1->Next;
        }else{
            p1->Data=p1->Data + p2->Data;
            p->Next=p1;
            p=p1;
            p1=p1->Next;
            p2=p2->Next;
        }
    }
    p->Next=p1?p1:p2;
    printf("相加结果:");
    Print(L);
    return 0;
}

List Read(){
    int m,n;
	List L,head;
    head = L = (List)malloc(sizeof(struct Node));
    printf("请输入多项式的项数\n");
    scanf("%d",&n);
	for(int i=0;i<n;i++){
		L->Next = (List)malloc(sizeof(struct Node));
		printf("请输入每一项的系数和指数\n");
        scanf("%d%d",&(L->Next->Data),&(L->Next->Number));
        L = L->Next;	
	}
	return head;
}

void Print( List L ){
	List p=L->Next;
	printf("y=");
	while(p){
        printf("%dx^%d", p->Data,p->Number);
        if((p->Next)!=NULL){
            printf("+");
        }
        p=p->Next;
	}
	//printf("%dx^%d", p->Data,p->Number);
	printf("\n");
}

运行截图