在 C 中使用链表乘以多项式的算法

Question

您能否在不添加任何新函数的情况下为我的两个多项式相乘函数提供一些帮助？我的程序有效，但它只将 P 的所有元素与 Q 的第一个元素相乘。之后，我想将 Q 的指针移动到第二个元素直到最后一个，但我不知道如何做。这是乘法函数：

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;
        }
    }
    
}

完整代码：

#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;
        }
    }
    
}

Answer 1

此代码存在一些相当严重的问题。

pomnozi 以不止一种方式损坏。外层循环从 P 的第一个成员乘以 Q 的第一个成员开始，然后立即推进 P，这样第一个成员就再也不会出现了。但是你需要将P的第一个成员乘以Q的所有个成员，因此你只能在P 之后 ] 它乘以所有成员 Q.
但是如果你只是把P = P->next移动到内循环之后的位置，你会把P的成员乘以Q的第一个成员两次。您根本不需要外部乘法。所有的工作都应该在内循环中完成。
给定 P 的成员，pomnozi 的内部循环遍历 Q 的成员。一旦 Q 耗尽，代码应该返回并将 Q 乘以 P 的下一个成员，但它不能，因为 Q 现在是 NULL 并且没有办法恢复它。您需要记住 Q 是什么，并在外循环的每次迭代中重新初始化它。
sortUnos 不检查多项式是否已经有一个具有给定指数的成员，因此，尝试乘以例如(x+1) * (x+1)（假设 pomnozi 固定）将导致 x 在结果中插入两次。

您应该能够通过使用交互式 调试器.

自己找到这些东西

还有其他问题。例如，第一个节点实际上不包含任何有意义数据的链表的表示非常容易出错和误导。

在 C 中使用链表乘以多项式的算法

Algorithm for multiplying polynomials using linked list in C

c

linked-list

polynomials