undefinedfix
Sign in

C language chain header node pointer field does not assign an error?

cstlr edited in Sun, 07 Aug 2022

Using single linked list to realize addition and multiplication of polynomials

A very basic data structure topic, implemented with C language

The main functions and main functions are as follows

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

//多项式结构体
typedef struct PolyNode *Polynomial;
struct PolyNode{
    int coef;//系数
    int expon;//指数
    Polynomial link;//指向后一个节点的指针域
};

Polynomial ReadPoly();//读多项式
void Attach(int c, int e, Polynomial *pRear);//构造多项式
Polynomial Mult(Polynomial P1, Polynomial P2);//多项式乘法
Polynomial Add(Polynomial P1, Polynomial P2);//多项式加法
void PrintPoly(Polynomial P);//输出多项式

int main(int argc, const char * argv[]) {
    // insert code here...
    Polynomial P1, P2, PP, PS;
    P1 = ReadPoly();//读取两个多项式
    P2 = ReadPoly();
    PP = Mult(P1, P2);
    PrintPoly(PP);
    PS = Add(P1, P2);
    PrintPoly(PS);
    return 0;
}

Polynomial ReadPoly(){
    Polynomial P, Rear, t;
    int c, e, N;
    scanf("%d", &N);
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while (N--) {
        scanf("%d %d", &c, &e);
        Attach(c, e, &Rear);
    }
    t = P;
    P = P->link;
    free(t);
    return P;
}

//Attach函数要构建链表表示多项式
void Attach(int c, int e, Polynomial *pRear){
    Polynomial P;
    
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->link = (*pRear)->link;
    (*pRear)->link = P;
    *pRear = P;
}

//加法
Polynomial Add(Polynomial P1, Polynomial P2){
    Polynomial front, rear, t1, t2;
    int sum;
    t1 = P1;
    t2 = P2;
    front = (Polynomial)malloc(sizeof(struct PolyNode));
    front->link = NULL;
    rear = front;
    while (t1 && t2) {
        if (t1->expon == t2->expon) {
            sum = t1->coef + t2->coef;
            if(sum)
                Attach(sum, t1->expon, &rear);
            t1 = t1->link;
            t2 = t2->link;
        }
        else if (t1->expon > t2->expon){
            Attach(t1->coef, t1->expon, &rear);
            t1 = t1->link;
        }
        else if (t1->expon < t2->expon){
            Attach(t2->coef, t2->expon, &rear);
            t2 = t2->link;
        }
    }
    while (t1){
        Attach(t1->coef, t1->expon, &rear);
        t1 = t1->link;
    }
    while (t2){
        Attach(t2->coef, t2->expon, &rear);
        t2 = t2->link;
    }
    rear = front;
    front = front->link;
    free(rear);
    return front;
}

//乘法
Polynomial Mult(Polynomial P1, Polynomial P2){
    Polynomial P, Rear, t1, t2, t;
    int c, e;
    
    if (!P1 || !P2)
        return NULL;
    
    t1 = P1;
    t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    
    P->link = NULL;//**为什么要让p指向空?**
    
    Rear = P;
    while (t2) {
        Attach(t1->coef*t2->coef, t1->expon+t2->expon, &Rear);
        t2 = t2->link;
    }
    t1 = t1->link;
    while (t1) {
        t2 = P2;
        Rear = P;
        while (t2) {
            c = t1->coef * t2->coef;
            e = t1->expon + t2->expon;
            while (Rear->link && Rear->link->expon > e)
                Rear = Rear->link;
            if (Rear->link && Rear->link->expon == e) {
                if (Rear->link->coef + c)
                    Rear->link->coef += c;
                else {
                    t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            }
            else {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->link = Rear->link;
                Rear->link = t;
                Rear = Rear->link;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    Rear = P;
    P = P->link;
    free(Rear);
    return P;
}

The problem is that after I delete the p - > link = null in multiplication, the multiplication and addition of the whole algorithm are wrong. Why?

Polynomial P, Rear, t1, t2, t;
int c, e;

if (!P1 || !P2)
    return NULL;

t1 = P1;
t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));

P->link = NULL;//**为什么要让p指向空?**

Rear = P;
1 Replies
SpenserWilson1
commented on Sun, 07 Aug 2022

If you don't set null, it means that your polynomial list probably doesn't have an end tag (because the space allocated by malloc won't all be set to 0). So when traversing the linked list later, we access the garbage address, causing the program to crash.

lock This question has been locked and the reply function has been disabled.