数据结构课程笔记--（2）一元多项式的和还有相乘

以你之姓@ 2022-07-29 06:22 96阅读 0赞

1.题目

![Center][]

\------链表的读取

#include<stdio.h>
    #include<malloc.h>
    #define LEN sizeof(struct PolyNode)
    struct PolyNode{
        int coef;
        int expon;
        struct PolyNode *next;
    } ;
    int n;
    struct PolyNode * creat(int N){  //4 3 4 -5 2  6 1  -2 0
        struct PolyNode *head;
        struct PolyNode *p1,*p2;
        n = 1;
        p1 = p2 = (struct PolyNode *)malloc(LEN);
        while(n <= N){
            if(n==1){
                scanf("%d %d",&p1->coef,&p1->expon);
                head=p1;
            }else{
                p2 = p1;
                p1 = (struct PolyNode *)malloc(LEN);
                scanf("%d%d",&p1->coef,&p1->expon);
                p2->next=p1;
            }
            n = n+1;
        }
        p1->next = NULL;
        return (head);
    }
    void print(struct PolyNode *head){
        struct PolyNode *p;
        printf("\nNow,There %d records are:\n",n);
        p = head;
        if(head != NULL)
            do
            {
                printf("%d %d ",p->coef,p->expon);
                p = p->next;
            }while(p!=NULL);
    }
    void main(){
        int N;
        struct PolyNode *head1;
        struct PolyNode *head2;
        struct PolyNode *head;
        scanf("%d",&N);
        head1 = creat(N);
        scanf("%d",&N);
        head2 = creat(N);
        print(head1);
    print(head2);
    }

\----------多项式相乘和相加

1.#include <stdio.h>  
    2.#include <stdlib.h>   
    3.  
    4.typedef struct node{  
    5.    int coefficient;  
    6.    int exponent;  
    7.    struct node * next;  
    8.} PolyNode, *Polynomial;  
    9.  
    10.Polynomial ReadPoly();  
    11.void Attach(int c, int e, Polynomial * Rear);  
    12.Polynomial MultPoly(Polynomial P1, Polynomial P2);  
    13.Polynomial AddPoly(Polynomial P1, Polynomial P2);  
    14.void PrintPoly(Polynomial P);  
    15.  
    16.int main(int argc, char const *argv[])  
    17.{  
    18.    Polynomial Poly1, Poly2, PolySum, PolyMul;  
    19.  
    20.    Poly1 = ReadPoly();  
    21.    Poly2 = ReadPoly();  
    22.    PolyMul = MultPoly(Poly1, Poly2);  
    23.    PrintPoly(PolyMul);  
    24.    PolySum = AddPoly(Poly1, Poly2);  
    25.    PrintPoly(PolySum);  
    26.  
    27.    return 0;  
    28.}  
    29.  
    30.Polynomial ReadPoly()  
    31.{  
    32.    Polynomial P, Rear, temp;  
    33.    P = (PolyNode*)malloc(sizeof(PolyNode));  
    34.    P->next = NULL;  
    35.    Rear = P;  
    36.    int N, c, e;  
    37.    scanf("%d", &N);  
    38.    while(N--){  
    39.        scanf("%d %d", &c, &e);  
    40.        Attach(c, e, &Rear);  
    41.    }  
    42.    temp = P;  
    43.    P = P->next;   
    44.    free(temp);  
    45.    return P;  
    46.}  
    47.  
    48.void Attach(int c, int e, Polynomial * pRear)  
    49.{  
    50.    Polynomial P;  
    51.    P = (PolyNode*)malloc(sizeof(PolyNode));  
    52.    P->coefficient = c;  
    53.    P->exponent = e;  
    54.    P->next = NULL;  
    55.    (*pRear)->next = P;  
    56.    *pRear = P;  
    57.}  
    58.  
    59.Polynomial MultPoly(Polynomial P1, Polynomial P2)  
    60.{  
    61.    Polynomial P, temp1, temp2, Rear, temp;  
    62.    int c, e;  
    63.    if(!P1 || !P2)  
    64.        return NULL;  
    65.    temp1 = P1;  
    66.    temp2 = P2;  
    67.    P = (PolyNode*)malloc(sizeof(PolyNode));  
    68.    P->next = NULL;  
    69.    Rear = P;  
    70.    while(temp2){  
    71.        c = temp1->coefficient * temp2->coefficient;  
    72.        e = temp1->exponent + temp2->exponent;  
    73.        if(c != 0){  
    74.            Attach(c, e, &Rear);  
    75.            temp2 = temp2->next;  
    76.        }  
    77.    }  
    78.    temp1 = temp1->next;  
    79.    while(temp1){  
    80.        temp2 = P2, Rear = P;  
    81.        while(temp2){  
    82.            c = temp1->coefficient * temp2->coefficient;  
    83.            e = temp1->exponent + temp2->exponent;  
    84.            if(c != 0){  
    85.                while(Rear->next && Rear->next->exponent > e)  
    86.                    Rear = Rear->next;  
    87.                if(Rear->next && Rear->next->exponent == e){  
    88.                    if(Rear->next->coefficient + c)  
    89.                        Rear->next->coefficient += c;  
    90.                    else{  
    91.                        temp = Rear->next;  
    92.                        Rear->next = temp->next;  
    93.                        free(temp);  
    94.                    }  
    95.                }  
    96.                else{  
    97.                    temp = (PolyNode*)malloc(sizeof(PolyNode));  
    98.                    temp->coefficient = c;  
    99.                    temp->exponent = e;  
    100.                    temp->next = Rear->next;  
    101.                    Rear->next = temp;  
    102.                    Rear = Rear->next;  
    103.                }  
    104.                temp2 = temp2->next;  
    105.            }  
    106.        }  
    107.        temp1 = temp1->next;  
    108.    }  
    109.    temp = P;  
    110.    P = P->next;  
    111.    free(temp);  
    112.    return P;  
    113.}  
    114.  
    115.Polynomial AddPoly(Polynomial P1, Polynomial P2)  
    116.{  
    117.    Polynomial P, temp1, temp2, Rear, temp;  
    118.    if(!P1 && !P2){  
    119.        if(!P1)  
    120.            return P2;  
    121.        else  
    122.            return P1;  
    123.    }  
    124.    P = (PolyNode*)malloc(sizeof(PolyNode));  
    125.    P->next = NULL;  
    126.    Rear = P;  
    127.    temp1 = P1;  
    128.    temp2 = P2;  
    129.    while(temp1 && temp2){  
    130.        if(temp1->exponent > temp2->exponent){  
    131.            if(temp1->coefficient){  
    132.                Attach(temp1->coefficient, temp1->exponent, &Rear);                 
    133.            }  
    134.            temp1 = temp1->next;  
    135.        }  
    136.        else if(temp1->exponent == temp2->exponent){  
    137.            if(temp1->coefficient + temp2->coefficient){  
    138.                Attach(temp1->coefficient + temp2->coefficient, temp1->exponent, &Rear);  
    139.            }  
    140.            temp1 = temp1->next;  
    141.            temp2 = temp2->next;  
    142.        }  
    143.        else{  
    144.            if(temp2->coefficient){  
    145.                Attach(temp2->coefficient, temp2->exponent, &Rear);                 
    146.            }  
    147.            temp2 = temp2->next;  
    148.        }  
    149.    }  
    150.    while(temp1){  
    151.        Attach(temp1->coefficient, temp1->exponent, &Rear);  
    152.        temp1 = temp1->next;  
    153.    }  
    154.    while(temp2){  
    155.        Attach(temp2->coefficient, temp2->exponent, &Rear);  
    156.        temp2 = temp2->next;  
    157.    }  
    158.    temp = P;  
    159.    P = P->next;  
    160.    free(temp);  
    161.    return P;  
    162.}  
    163.  
    164.void PrintPoly(Polynomial P)  
    165.{  
    166.    int flag = 0;  
    167.    if(!P){  
    168.        printf("0 0");  
    169.    }  
    170.    while(P){  
    171.        if (!flag)  
    172.            flag = 1;  
    173.        else  
    174.            printf(" ");  
    175.        printf("%d %d", P->coefficient, P->exponent);  
    176.        P = P->next;  
    177.    }  
    178.    printf("\n");  
    179.}

[Center]: /images/20220728/7e0726fe173c49998789bc16c539768d.png