使用链表创建多项式并将它们相加

Question

我在 polynomial 中遇到过很多使用双指针作为参数创建多项式的代码，在下面的代码中我有一个问题，为什么要为 Node 类型的下一个指针创建一个新节点。如果可能的话，有人可以向我解释这段代码的工作原理。

struct Node 
{ 
    int coeff; 
    int pow; 
    struct Node *next; 
}; 

// Function to create new node 
void create_node(int x, int y, struct Node **temp) 
{ 
    struct Node *r, *z; 
    z = *temp; 
    if(z == NULL) 
    { 
        r =(struct Node*)malloc(sizeof(struct Node)); 
        r->coeff = x; 
        r->pow = y; 
        *temp = r; 
        r->next = (struct Node*)malloc(sizeof(struct Node)); 
        r = r->next; 
        r->next = NULL; 
    } 
    else
    { 
        r->coeff = x; 
        r->pow = y; 
        r->next = (struct Node*)malloc(sizeof(struct Node)); 
        r = r->next; 
        r->next = NULL; 
    } 
}

函数的调用是从 main 中以这种方式完成的：

    struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; 

        // Create first list of 5x^2 + 4x^1 + 2x^0 
        create_node(5,2,&poly1); 
        create_node(4,1,&poly1); 
        create_node(2,0,&poly1); 
// Create second list of 5x^1 + 5x^0 
    create_node(5,1,&poly2); 
    create_node(5,0,&poly2);

Answer 1

why a new node is created for the next pointer of type Node.

只是因为作者想那样做。代码也可以这样写。但是显示的代码具有未定义的行为，因为 r 在 else 部分中被取消引用而没有首先初始化并且很可能是一个无效的指针值。

必须从 *temp（z - 请画出更好的名称）遍历所有现有节点，然后附加一个新节点：

void create_node(int x, int y, struct Node **temp)
{
    struct Node *r, *z;
    z = *temp;
    if (!z)
    {
        r = malloc(sizeof(struct Node)); // do not cast the result of malloc()!
        r->coeff = x;
        r->pow = y;
        r->next = 0;
        *temp = r;
    }
    else
    {
        r = z;
        while (r->next)
            r = r->next;

        r->next = malloc(sizeof(struct Node));
        r = r->next;
        r->coeff = x;
        r->pow = y;
        r->next = 0;
    }
}

Answer 2

不需要特例；相反，只需使用指向指针的指针：

void create_node(int x, int y, struct Node **temp) 
{ 
    struct Node *this;
    this = malloc(sizeof *this);
    this->next = *temp;    // steal the parent's pointer.
    this->coeff = x;    
    this->pow = y;    
    *temp = this;          // and put ourself in front of it
}

请注意，如果原始列表为空，*temp 将为NULL，并且this->next 也将设置为NULL。（这就是我们想要的）

使用链表创建多项式并将它们相加

creating polynomial using linked list and adding them

c

linked-list

data-structures

polynomials