一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

 

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

#include <iostream>
using namespace std;

typedef struct PolyNode{
    int coef;
    int expon;
    struct PolyNode *next;
}*Polynomial;

void Attach(int coef,int expon,Polynomial &rear);
Polynomial ReadPoly();
Polynomial Mul(Polynomial P1,Polynomial P2);
void PrintPoly(Polynomial PP);
Polynomial Add(Polynomial P1,Polynomial P2);
 
int main() //程序框架搭建
{
    Polynomial P1, P2, PM, PA;
    P1 = ReadPoly();
    P2 = ReadPoly();

    PM = Mul(P1,P2);
    PrintPoly(PM);
 
    PA = Add(P1, P2);
    PrintPoly(PA);
    return 0;
}
 
//对Rear指针的处理：1.初值为NULL,根据是否为空做不同处理；2.指向一个空节点
//C语言中*rear当前结果表达式尾项指针的指针,这样可以地址传递，从而形参变化实参也跟着变化,当用C++时改用&rear
//函数实现在rear后面插入节点
void Attach(int coef, int expon, Polynomial &rear)  
{
    Polynomial P;
    P = (Polynomial)malloc(sizeof(Polynomial));
    P->coef = coef;
    P->expon = expon;
    P->next = NULL;
    rear->next = P;
    rear= P;
}
 
Polynomial ReadPoly()
{
    Polynomial P, rear, t;
    int coef, expon, N;
    scanf("%d", &N);
    P = (Polynomial)malloc(sizeof(Polynomial)); //链表头空节点
    P->next = NULL;
    rear = P; 
    while (N--)
    {
        scanf("%d %d", &coef, &expon);
        if (coef != 0)  
           Attach(coef, expon, rear); //将当前项插入多项式尾部
    }
    t = P;
    P = P->next;
    free(t); //删除临时生成的头结点
    return P;
}
 
Polynomial Add(Polynomial P1, Polynomial P2)
{
    Polynomial t1, t2;
    t1 = P1;
    t2 = P2;
    //生成新的头结点
    Polynomial P,t,rear;
    P = (Polynomial)malloc(sizeof(Polynomial));
    P->next = NULL;
    rear = P;
    while (t1&&t2)
    {
        if (t1->expon==t2->expon)
        {
            if (t1->coef+t2->coef)  //系数和为0时不添加到尾节点上 
            {
                Attach(t1->coef + t2->coef, t1->expon, rear);
            }
            t1 = t1->next;
            t2 = t2->next;
        }
        else if (t1->expon>t2->expon)
        {
            Attach(t1->coef, t1->expon, rear);
            t1=t1->next;
        }else 
        {
            Attach(t2->coef, t2->expon, rear);
            t2 = t2->next;
        }
    }
    while (t1)
    {
        Attach(t1->coef, t1->expon, rear);
        t1 = t1->next;
    }
    while (t2)
    {
        Attach(t2->coef, t2->expon, rear);
        t2 = t2->next;
    }
    t = P;
    P = P->next;
    free(t);
    return P;
}
 
//多项式乘法方法：
//1. 将乘法运算转换为加法运算，让P1的每一项和P2相乘，在加到结果多项式中
//2. 逐项插入，将P1当前项乘P2当前项，在插入到结果表达式中，关键是要找到插入的位置
//乘法运算中没有尾指针，这里用temp来表示一个临时指针变量 
Polynomial Mul(Polynomial P1, Polynomial P2)
{
    Polynomial P, temp;
    Polynomial t1, t2, t;
    if (!P1||!P2)
    {
        return NULL;
    }
    t1 = P1;
    t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    temp = P;
    while (t2)
    {
        //先用P1的第一项乘以P2,得到初始结果多项式
        Attach(t1->coef*t2->coef, t1->expon + t2->expon, temp);
        t2 = t2->next;
    }
    t1 = t1->next;
    while (t1)
    {
        t2 = P2;
        temp = P; //将尾节点置到头结点来
        while (t2)
        {
            int expon = t1->expon + t2->expon;
            int coef = t1->coef * t2->coef;   //以后的每一项相乘的结果
            while (temp->next&& expon<temp->next->expon) //找插入位置
            {
                temp = temp->next;
            }
            if (temp->next&&temp->next->expon==expon)//判断指数是否相等
            {
                if (temp->next->coef+coef) //判系数是否为0，不为0则系数相加
                {
                    temp->next->coef += coef;
                }
                else  //系数为0删除节点
                {
                    t = temp->next;
                    temp->next = t->next;
                    free(t);
                }
            }
            else  //系数不等则插入位置
            {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = coef;
                t->expon = expon;
                t->next = temp->next;
                temp->next = t;
 
                temp = temp->next;
            }
            t2 = t2->next;
        }
        t1 = t1->next;
    }
    t = P;
    P = P->next;
    free(t);
 
    return P;
}
 
void PrintPoly(Polynomial PP)
{
    int flag = 0;//辅助调整输出格式
    if (!PP)
    {
        cout << "0 0" << endl;/*格式*/
        return;
    }
    while (PP)
    {
        if (!flag) //第一次
        {
            flag = 1;
        }
        else
        {
            printf(" ");
        }
        cout << PP->coef << " "<< PP->expon;
        PP = PP->next;
    }
    printf("
");
}

在C语言中函数的参数传递方式有两种：值传递与地址传递。

值传递的特点是单向传递，即主调函数调用时给形参分配存储单元，把实参的值传递给形参，在调用结束后，形参的存储单元被释放，而形参值的任何变化都不会影响到实参的值，实参的存储单元仍保留并维持数值不变。

地址传递的特点是形参并不存在存储空间，编译系统不为形参数组分配内存。数组名或指针就是一组连续空间的首地址。因此在数组名或指针作函数参数时所进行的传送只是地址传送，形参在取得该首地址之后，与实参共同拥有一段内存空间，形参的变化也就是实参的变化。当使用C++时，可以使用&引用传递来达到同样效果。

/*下面给一个C语言地址传递的例子*/
void Swap(int *px, int *py)
{
    int tmp;
    tmp = *px;
    *px = *py;
    *py = tmp;
    printf("*px = %d, *py = %d
", *px, *py);
}
int main(void)
{
    int a=10;
    int b=20;
    Swap(&a, &b);
    printf("a = %d, b = %d
", a, b);
    return 0;
}


/*运行结果：
*px = 20, *py = 10
a = 20, b = 10
*/