Mki's Blog

数据结构(二):多项式加法和乘法

题目描述

题目要求

02-线性结构2 一元多项式的乘法与加法运算 (20 分)
设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分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<stdio.h>
#include<stdlib.h>

typedef struct Node *PToNode;
struct Node {
    int coe; //系数
    int exp; //指数
    PToNode Next;
};
typedef PToNode List;

List Read(int n);
void Print(List L);
List Attach(int n1, int n2, List L);
List Plus(List L1, List L2);
List Multi(List L1, List L2);


List Read(int n) {
    List L, r;
    L = (List)malloc(sizeof(struct Node));   //L是一个开始地址
    L->Next = NULL;
    r = L;

    while(n--){
        List p = (List)malloc(sizeof(struct Node));
        scanf_s("%d %d", &(p->coe), &(p->exp));
        r->Next = p;
        r = p;
    }

    r->Next = NULL;
    return L;
}


void Print(List L) {  //打印多项式->其实是个链表
    List p = L->Next;
    if (p) {
        List r;
        r = L;
        while (r->Next) {
            r = r->Next;
            printf("%d %d ", r->coe,r->exp);
        }
    }
    else {
        printf("NULL");
    }
    printf("\n");
}

/*在链表末尾添加一组数据*/
List Attach(int coe, int exp, List L) {
    List temp,p;
    p = L;
    temp = (List)malloc(sizeof(struct Node));
    temp->coe = coe;
    temp->exp = exp;
    temp->Next = NULL;
    while (L->Next != NULL) 
        L = L->Next;
    L->Next = temp;
    return p;
}


List Plus(List L1, List L2) { //实现两个链表的加法
    List p1, p2, p3, res;
    p3 = (List)malloc(sizeof(struct Node));
    p3->Next = NULL;
    res = p3;
    p1 = L1->Next;
    p2 = L2->Next;

    while (p1&&p2) {
        if (p1->exp > p2->exp) {
            Attach(p2->coe, p2->exp, p3);
            p2 = p2->Next;
            p3 = p3->Next;

        }
        else if (p1->exp < p2->exp) {
            Attach(p1->coe, p1->exp, p3);
            p1 = p1->Next;
            p3 = p3->Next;


        }
        else {
            Attach(p2->coe + p1->coe, p1->exp , p3);
            p1 = p1->Next;
            p2 = p2->Next;
            p3 = p3->Next;

        }
    }
    if (p1 != NULL)
        p3->Next = p1;
    else
        p3->Next = p2;

    return res;
}


List Multi(List L1, List L2) { //链表的乘法
    int flag = 1;
    List p1, p2, p3, res, result, temp, temp_start, temp_node;
    p3 = (List)malloc(sizeof(struct Node));    //头
    p3->Next = NULL;

    result = (List)malloc(sizeof(struct Node));    //头
    result->Next = NULL;
    res = result;
    p1 = L1->Next;
    p2 = L2->Next;
    while (p1) {
        temp_start = (List)malloc(sizeof(struct Node)); //头
        temp_start->Next = NULL;
        temp = temp_start;
        while (p2) {
            temp_node = (List)malloc(sizeof(struct Node)); //节点
            temp_node->coe = (p1->coe)*(p2->coe);          //赋值
            temp_node->exp = (p1->exp)+(p2->exp);
            temp_node->Next = NULL;                       //连接
            temp_start->Next = temp_node;
            temp_start = temp_node;
            p2 = p2->Next;
        }
        if (p3 == NULL) {
            result = Plus(temp, p3);
            flag = 0;
        }
        else{
            result = Plus(temp, result);
        }
        p2 = L2->Next;     //经过第二个while p2->Next已经变成了null,所以要重新给个值
        p1 = p1->Next;
    }
    return result;
}


/*测试*/
int main(void) {
    int n1, n2;
    List L1, L2, L3, L4;

    scanf_s("%d", &n1);
    L1 = Read(n1);
    scanf_s("%d", &n2);
    L2 = Read(n2);
    L3 = Plus(L1, L2);
    L4 = Multi(L1, L2);
    Print(L3);
    Print(L4);

    getchar();
    getchar();
    return 0;
}

多项式的加法就是简单的同x指数加减系数,而乘法可以看作每一项与第二个多项式相乘,然后将所有链表相加的过程。