多项式相加

数据结构之多项式

代码

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

#define ERROR -1
#define OK 1

typedef int ElemType;
typedef int status;

//指数升序排列,第一项不存值,由于用了cpp的引用特性,需要用cpp的编译器

typedef struct mulnode{
    ElemType coef;//系数
    ElemType expo;//指数
    struct mulnode *next;
}mulnode,*mult;

status AddItem(mult &List,ElemType coef,ElemType expo){
    mult q,temp;
    mult p = List;
    q = (mult) malloc(sizeof(mulnode));
    q->coef = coef;q->expo = expo;q->next = NULL;
    while (p->next!=NULL&&p->next->expo<expo){
        p = p->next;
    }
    if(p->next!=NULL&&p->next->expo==expo){
        p->next->coef+=coef;
        return OK;
    }
    q->next = p->next;
    p->next = q;
    return OK;
}

//初始化并赋初值为0
status InitMult(mult &p,int count){
    ElemType coef,expo;
    mult temp;//临时节点指针
    p = (mult) malloc(sizeof(mulnode));
    if(!p) return ERROR;
    p->coef = 0;
    p->expo = 0;
    p->next = NULL;
    while (count--){
        scanf("%d %d",&coef,&expo);
        AddItem(p,coef,expo);
    }
    return OK;
}

status ReadMult(mult p){
    while (p){
        printf("(%d,%d)  ",p->coef,p->expo);
        p = p->next;
    }
    printf("\n----------------------------------------\n");
    return OK;
}

//多项式相加，结果存到p3
status AddMult(mult &p1,mult &p2,mult &p3){
    mult pa,pb,pre,T;
    pa = p1->next;
    pb = p2->next;
    pre = p3;
    while (pa&&pb){
        T = (mult) malloc(sizeof(mulnode));
        T->next = NULL;
        if(pa->expo<pb->expo){
            T->coef = pa->coef;
            T->expo = pa->expo;
            pa = pa->next;
        } else if(pa->expo == pb->expo){
            T->coef = pa->coef+pb->coef;
            T->expo = pa->expo;
            pa = pa->next;
            pb = pb->next;
        } else{
            T->coef = pb->coef;
            T->expo = pb->expo;
            pb = pb->next;
        }
        pre->next = T;
        pre = pre->next;
    }
    pre->next = pa?pa:pb;
    return OK;
}


int main() {
    mult p1,p2,p3;
    int p1_length,p2_length;
    printf("请输入p1多项式长度:\n");
    scanf("%d",&p1_length);
    printf("请输入p2多项式长度:\n");
    scanf("%d",&p2_length);
    InitMult(p1,p1_length);
    InitMult(p2,p2_length);
    InitMult(p3,0);
    ReadMult(p1);
    ReadMult(p2);
    AddMult(p1,p2,p3);
    ReadMult(p3);
    return 0;
}