首页 文章

避免链接列表中的额外Malloc（node-> next = NULL）

提问于
浏览 次
1

在我的链表中，我试图避免添加一个额外的节点而不添加一堆 if 语句等 . 我有以下内容：

polynomial create()
{
    polynomial head = NULL;
    polynomial temp = NULL;
    int numTerms, coefficient, exponent;
    int counter = 0;

    printf("Enter the number of terms in the polynomial: ");
    scanf ("%d", &numTerms);
    printf("\n");

    if (numTerms == 0) {
        head = malloc(sizeof(term));
        head->coef = 0; head->exp = 0; head->next = NULL;
        return head;
    }
    while (numTerms != counter) {
        // Ask for input
        printf("Enter the coefficient and exponent of term %d: ", (counter + 1));
        scanf("%d %d", &coefficient, &exponent);
        printf("\n");

        // Create the term
        if (temp == NULL) temp = malloc(sizeof(term));
        temp->coef = coefficient; temp->exp = exponent; temp->next = NULL;
        //if((numTerms - 1) != counter) temp->next = malloc(sizeof(term)); -- this is my workaround
        printf("Created: %d %d\n", temp->coef, temp->exp);

        // If this is the first node created, mark the head
        if (counter == 0) head = temp;
        // Increment the list and counter
        temp = temp->next;
        counter ++;
    }
    return head;
}

但是当我去打印多项式时（我有一个完美的功能），我得到以下结果：

Polynomial 1: 3x^4 - >在这种情况下，对head-> next的引用为NULL

所以我尝试了以下解决方法 - 只为新节点预先分配内存，但前提是这是用户输入的最后一次迭代 . 这通过以下方式实现：

用_替换 temp->next = NULL;

if((numTerms - 1) != counter) temp->next = malloc(sizeof(term));

numTerms - 1 阻止添加'extra node'，而malloc用于保持对temp-> next的引用 . 如果我不使用 if 检查并且总是分配额外的内存，我最终会得到以下结果：

Polynomial 1: 3x^4 - 7x^2 + 5 + 10621224x^10617028

我错过了哪一部分分配会导致对temp-> next的引用丢失？对于指针和内存管理，我真的非常糟糕，所以这可能是一个可怕的问题 .

c linked-list malloc

2 回答

  • 4

    你做得比实际需要的要困难得多 . 考虑符合以下内容的链表的简单节点群：

    • 假设NULL表示空列表

    • 分配头指针，而不必为每次分配测试它 .

    • 一个，每个节点只需要一个分配 .

    • 节点以条目顺序显示在列表中 . 列表中的第一个节点是您输入的第一个节点，第二个节点是您输入的第二个节点，等等 .

    有了它，请参阅下面的一般算法以及它如何适应您的代码：

    struct node
{
    // your fields here
    struct node *next;
};

struct node* populate_list()
{
    struct node *head = NULL;
    struct node **pp = &head;
    int i=0, count=0;

    // TODO: set count: get your insertion limit here. 

    // now run the insertion loop
    for (i=0; i<count; ++i)
    {
        struct node *p = malloc(sizeof(*p));

        // TODO: initialize your node members here

        // save to our current tail-pointer, which is initially
        //  also the head pointer. then advance to the new tail
        //  pointer and continue the loop
        *pp = p;
        pp = &p->next;
    }

    // terminate the list.
    *pp = NULL;

    // and return the head pointer.
    return head;
}

    注意： p 仅用于清晰 . 您可以轻松地将该循环体减少到以下，这是完全有效的：

    // now run the insertion loop
    for (i=0; i<count; ++i)
    {
        *pp = malloc(sizeof(**pp));

        // TODO: initialize your node members here
        //  using (*pp)->member for access

        // save next pointer and continue.    
        pp = &(*pp)->next;
    }

    Adapting Your Code

    既然你知道如何做到这一点，它会大大减少你的代码：

    polynomial create()
{
    polynomial head = NULL;
    polynomial *pp = &head;

    int numTerms, coefficient, exponent;
    int counter = 0;

    // prompt for valid number of terms.
    printf("Enter the number of terms in the polynomial: ");
    scanf ("%d", &numTerms);

    while (numTerms != counter)
    {
        // Ask for input
        printf("Enter the coefficient and exponent of term %d: ", (counter + 1));
        if (scanf("%d %d", &coefficient, &exponent) == 2)
        {
            *pp = malloc(sizeof(**pp));
            (*pp)->coef = coefficient;
            (*pp)->exp = exponent;
            pp = &(*pp)->next;
            ++counter;
        }
        else
        {   // eat the line and try again.
            scanf("%*[^\n]\n")
        }
    }
    *pp = NULL;

    return head;
}
    回复于
  • 0

    此外，您将发现存储中缀表达式（如上所述）对二叉树的效果要好得多 . 您使用操作（， - ，*，/，^）表示树的节点，并且还有一个括号树（其下的所有内容都是一个表达式，用括号括起来 .

    当您浏览表达式时，您将构建一个树，您将发现它可以递归执行 .

    打印树是使用深度优先，左节点右遍历完成的 .

    回复于

相关问题