使用malloc创建一个链表

Question

我使用malloc来分配列表中的新节点，但我的代码的某个部分出现了错误；以下解决方案仅适用于删除和插入

#include <stdio.h>
#include <malloc.h>
struct Node{
    int value;
    struct Node * Next;
    struct Node * Previous;

};
typedef struct Node Node;
struct List{
    int Count;
    int Total;
    Node * First;
    Node * Last;
};
typedef struct List List;
List Create();
void Add(List a,int value);
void Remove(List a,Node * b);
List Create()
{
    List a;
    a.Count=0;
    return a;
}
void Add(List a,int value)
{
    Node * b = (Node *)malloc(sizeof(Node));
    if(b==NULL)
        printf("Memory allocation error n");
    b->value=value;
    if(a.Count==0)
    {
        b->Next=NULL;
        b->Previous=NULL;
        a.First=b;
    }
    else
    {
        b->Next=NULL;
        b->Previous=a.Last;
        a.Last->Next=b;
    }
    ++a.Count;
    a.Total+=value;
    a.Last=b;
    }
void Remove(List a,Node * b)
{
    if(a.Count>1)
    {
        if(a.Last==b)
        {
            b->Previous->Next=NULL;
        }
        else
        {
            b->Previous->Next=b->Next;
            b->Next->Previous=b->Previous;
        }
        }
    free(b);
    }

在删除功能中，在最后一个else条件下，我不确定使用b->Next->Previous是否可以，并且会起作用；使用->运算符时，我是处理节点指针还是处理它的值？

Answer 1

简短的回答是：是的，b->Next->Previous很好——它是struct Node*，就像右手边的b->Previous一样。

我认为您的错误在于对Count的处理：它是按Add()递增的，但Remove()并没有递减。事实上，由于列表本身只需要知道它是否为空，您可以删除它，然后查看a.First == NULL是否为空。（你的a.Count == 1测试同样可以用a.First != NULL && a.First->Next == NULL测试代替。）

如果您在API中承诺Count，那么当列表本身工作时，您可以将其添加回来。相同的"先删除后添加"可能对Total有用。把这两者都看作是缓存。

一个更好的解决方案是实现一个循环列表：

struct List
{
    Node Anchor;
    //...
};
List Create()
{
    List l;
    l.Anchor.Next = l.Anchor.Previous = &l;
    return l;
}
bool IsEmpty(List const* l)
{
    // Both or neither point at 'l'.
    assert((l->Anchor.Next == l) == (l->Anchor.Previous == l));
    return l->Anchor.Next == l;
}
// Add a node 'n' to some list after 'ln'.
void AddAfter(Node* n, Node* ln)
{
    n->Previous = ln;
    n->Next = ln->Next;
    n->Next->Previous = n->Previous->Next = n;
}
Node* Remove(Node* n)
{
   n->Previous->Next = n->Next;
   n->Next->Previous = n->Previous;
   n->Next = n->Previous = n;  // nice and proper
   return x;
}

现在，空列表不再需要特殊情况。我让Remove()返回节点本身，以便于在列表之间移动节点（AddAfter(Remove(somenode), &otherlist.Anchor)）或移除和删除注释（free(Remove(somenode))）。

这里的一个缺点是，我的Anchor节点现在为永远不会使用的数据浪费空间，但这很容易修复。