Search code examples
clinked-listpolynomials

Algorithm for multiplying polynomials using linked list in C

Can you provide me little help with my function for multiplification of two polynomials without adding any new functions? My program works, but it only multiplies all elements of P with the first element of Q. After that, I would like to move the pointer of Q to the second element till the last but I can't figure out how. This is function for multiplification:

void multiply(Position Z, Position P, Position Q) {
    P = P->next;
    Q = Q->next;

    while (P != NULL&&Q!=NULL) {
        Z->coeff = P->coeff * Q->coeff;
        Z->exp = P->exp + Q->exp;
        sortedInput(Z, Z->coeff , Z->exp);
        P = P->next;
        
        while(Q!= NULL) {
            Z->coeff = P->coeff * Q->coeff;
            Z->exp = P->exp + Q->exp;
            sortedInput(Z, Z->coeff , Z->exp);
            Q = Q->next;
        }
    }
    
}

Whole code:

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

typedef struct polinom* Pozicija;

struct polinom {
    int koef;
    int exp;
    Pozicija next;
};

void citaj(Pozicija, char*);

void ispis(Pozicija);
void sortUnos(Pozicija, int, int);
void zbroji(Pozicija, Pozicija, Pozicija);
void pomnozi(Pozicija, Pozicija, Pozicija);

int main() {
    struct polinom P1, P2, Z, U;
    P1.next = NULL;
    P2.next = NULL;
    Z.next = NULL;
    U.next = NULL;

    citaj(&P1, "P1.txt");
    printf("Prvi polinom: ");
    ispis(&P1);

    citaj(&P2, "P2.txt");
    printf("Drugi polinom: ");
    ispis(&P2);
    
    printf("\nZbroj:");
    zbroji(&Z, &P1, &P2);
    ispis(&Z);

    printf("\nUmnozak: ");
    pomnozi(&U, &P1, &P2);
    ispis(&U);
}
void citaj(Pozicija P, char* ime) {
    FILE* dat;
    int k, e;

    Pozicija q = NULL;
    q = (Pozicija)malloc(sizeof(struct polinom));
    
    dat = fopen(ime, "r");
    if (dat == NULL)
        printf("Greska!\n");
    else {
        while (feof(dat) == 0) {
            fscanf(dat, "%d %d", &k, &e);
            
            sortUnos(P, k, e);
            q->koef = k;
            q->exp = e;
        }
    }
    fclose(dat);
}
void ispis(Pozicija P) {
    P = P->next;
    while (P != NULL)
    {
        printf("%dx^%d", P->koef, P->exp);
        P = P->next;
        if (P != NULL)
            printf("+");
    }
    printf("\n");
}

void sortUnos(Pozicija P, int k, int e) {
    Pozicija q;
    
    while (P->next != NULL && P->next->exp > e)
        P = P->next;
    q = (Pozicija)malloc(sizeof(struct polinom));

    q->exp = e;
    q->koef = k;

    q->next = P->next;
    P->next = q;
}
void zbroji(Pozicija Z, Pozicija P, Pozicija Q) {
    P = P->next;
    Q = Q->next;
    while (P != NULL && Q != NULL) {
        if (P->exp == Q->exp)
        {
            Z->koef = P->koef + Q->koef;
            Z->exp = P->exp;
            sortUnos(Z, Z->koef, Z->exp);
            P = P->next;
            Q = Q->next;
        }
        else if (P->exp < Q->exp) {
            Z->koef = Q->koef;
            Z->exp = Q->exp;
            sortUnos(Z, Z->koef, Z->exp);
            Q = Q->next;
        }
        else if (P->exp > Q->exp) {
            Z->koef = P->koef;
            Z->exp = P->exp;
            sortUnos(Z, Z->koef, Z->exp);
            P = P->next;
        }
        
        
    }
    if (P == NULL) {
        while (Q != NULL) {
            Z->koef = Q->koef;
            Z->exp = Q->exp;
            sortUnos(Z, Z->koef, Z->exp);
            Q = Q->next;
        }
    }
    else if (Q == NULL) {
        while (P != NULL)
        {
            Z->koef = P->koef;
            Z->exp = P->exp;
            sortUnos(Z, Z->koef, Z->exp);
            P = P->next;
        }
    }   
}
void pomnozi(Pozicija Z, Pozicija P, Pozicija Q) {
    P = P->next;
    Q = Q->next;

    while (P != NULL&&Q!=NULL) {
        Z->koef = P->koef * Q->koef;
        Z->exp = P->exp + Q->exp;
        sortUnos(Z, Z->koef, Z->exp);
        P = P->next;
        
        while(Q!= NULL) {
            Z->koef = P->koef * Q->koef;
            Z->exp = P->exp + Q->exp;
            sortUnos(Z, Z->koef, Z->exp);
            Q = Q->next;
        }
    }
    
}
Solution

  • There are some rather serious problems with this code.

    1. pomnozi is broken in more than one way. The outer loop starts with multiplying the first member of P by the first member of Q, and immediately advances P so that the first member is never seen again. But you need to multiply the first member of P by all members of Q, therefore you can only advance P after it is multiplied by all members of Q.
    2. But if you just move P = P->next to a position after the inner loop, you will multiply members of P by the first member of Q twice. You don't need the outer multiplication at all. All the work should be done in the inner loop.
    3. Given a member of P, the inner loop of pomnozi goes over members of Q. Once Q is exhausted, the code should go back and multiply Q by the next member of P, but it cannot, because Q is now NULL and there is no way to recover it. You need to remember what Q was, and re-initialize it in each iteration of the outer loop.
    4. sortUnos does not check whether the polynomial already has a member with a given exponent, thus, an attempt to multiply e.g. (x+1) * (x+1) (supposing pomnozi is fixed) will result in x being inserted in the result twice.

    You should be able to find these things yourself by using an interactive debugger.

    There are also other problems. For example, a representation of a linked list where the first node doesn't actually hold any meaningful data is highly error-prone and misleading.