1

在我的链表中，我试图避免malloc添加一个额外的节点而不添加一堆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额外节点”，malloc 是为了保持对 temp->next 的引用。如果我不使用if检查并且总是分配额外的内存，我最终会得到以下结果：

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

我缺少分配的哪一部分导致对 temp->next 的引用丢失？一般来说，我对指针和内存管理真的很糟糕，所以这可能是一个可怕的问题。

4

2 回答 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;
    }

调整你的代码

现在您知道如何执行此操作，它将大大减少您的代码，如下所示：

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;
}
于 2013-10-06T22:27:10.923 回答
0

此外，您会发现，对于存储上述中缀表达式，二叉树效果更好。您使用操作 (+,-,*,/,^) 表示树的节点，并且您还有一个括号树（它下面的所有内容都是一个表达式，用括号括起来。

当你浏览你的表达式时，你会构建一棵树，你会发现你可以递归地做。

打印出你的树是使用深度优先、左节点右遍历完成的。

于 2013-10-07T19:16:11.030 回答