一元多项式.cpp

一元多项式相加数据结构算法

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

struct _SExpNode
{
    int data1;
    int data2;
    struct _SExpNode *next;
};
typedef struct _SExpNode SExpNode;

SExpNode* InputExp()
{
    SExpNode *p,*q,*pNewNode ;
    q=NULL;
    p=NULL;
    int i;
    int iCoefficient;
    int iExponential;
    printf("请按照次序输入系数和指数：（按指数由高到低输入,系数或指数为0表示输入结束！）\n\n");
    for(i=1; ; i++)
    {
        printf("第%d项系数: ",i);
        scanf("%d",&iCoefficient);
        if (iCoefficient)
        {
            printf("第%d项指数: ", i);
            scanf("%d",&iExponential);
            pNewNode=(SExpNode *)malloc(sizeof(SExpNode));
            pNewNode->data1=iCoefficient;
            pNewNode->data2=iExponential;
            if(i==1) p=pNewNode;
            else q->next=pNewNode;
            q=pNewNode;
            if (iExponential==0) break;
        }
        else break;
    }
    printf("\n");
    if(q!=NULL) q->next=NULL;
    return p;
}
void PrintExp(SExpNode *pExp)
{
    SExpNode *pNode;
    if (pExp)
    {
        pNode =pExp->next;
        printf("%d",pExp->data1);
        if (pExp->data2)
        {
            printf("x");
            if (pExp->data2!= 1) printf("^%d",pExp->data2);
        }
        while (pNode!= NULL)
        {
            if (pNode->data1 > 0)printf("+%d",pNode->data1);
            else printf("%d",pNode->data1);
            if (pNode->data2)
            {
                printf("x");
                if (pNode->data2 != 1) printf("^%d",pNode->data2);
            }
            pNode=pNode->next;
        }
    }
    else printf("0");
}
SExpNode* ExpAdd(SExpNode *pExp1,SExpNode *pExp2)
{
    SExpNode * pExp3,* temp,*s;
    temp=NULL;
    pExp3=NULL;
    while(pExp1 && pExp2)
    {
        s=(SExpNode *)malloc(sizeof(SExpNode));
        if(pExp1->data2 > pExp2->data2)
        {
            s->data1=pExp1->data1;
            s->data2=pExp1->data2;
            if (pExp3 == NULL) pExp3=s;
            else temp->next=s;
            temp=s;
            pExp1=pExp1->next;
        }
        else if(pExp1->data2 < pExp2->data2)
        {
            s->data1=pExp2->data1;
            s->data2=pExp2->data2;
            if (pExp3==NULL) pExp3=s;
            else temp->next=s;
            temp=s;
            pExp2=pExp2->next;
        }
        else
        {
            s->data1=pExp2-> data1+ pExp1->data1;
            s->data2=pExp1->data2;
            if (s->data1)
            {
                if (pExp3==NULL) pExp3=s;
                else temp->next=s;
                temp=s;
            }
            pExp1=pExp1->next;
            pExp2=pExp2->next;
        }
    }
    if(pExp1) temp->next=pExp1;
    if(pExp2) temp->next=pExp2;
    return pExp3;
}
SExpNode* InputExpEx(int iIdx)
{
    SExpNode* pNode;
    printf("*****************************************************\n");
    printf("请输入第 %d 个表达式：\n", iIdx);
    pNode = InputExp();
    printf("第 %d 个表达式为： ", iIdx);
    PrintExp(pNode);
    printf("\n");
    return pNode;
}
void main()
{
    SExpNode *pExp1, *pExp2, *pAdd;
    int i;
    do{
        printf("\n  一元多项式相加算法 \n\n");
        printf("           283_金理华\n\n");
        pExp1 = InputExpEx(1); // 第一个表达式
        pExp2 = InputExpEx(2); // 第二个表达式
        getchar();
        printf("****************************************************");
        printf("\n表达式1为： "); PrintExp(pExp1);
        printf("\n表达式2为： "); PrintExp(pExp2);
        pAdd= ExpAdd(pExp1, pExp2);
        printf("\n\n相加结果为： "); PrintExp(pAdd);
        printf("\n\n退出请按0，继续请按1:"); scanf("%d",&i);
    }while(i==1);
}