使用 3 种不同的 typedef 在 C 中实现单链表

Question

因此，我的任务是在 C 中编写 Singly Linked List 的完整实现。

我之前写过stack和dynamic vector的实现，但是这次，链表让我有点困惑，因为使用了3个不同的typedef。

我很高兴收到您对我的代码的评论和提示。

我会像往常一样制作一个测试文件，但由于所有 void * 转换，我很难写一个。

我不会添加所有 14 个函数，我只会添加我最不确定的函数。

所以我们必须遵循下面的typedefs和给定的prototypes。所以两者都不能改变。

我还必须添加一个 "虚拟节点" 作为最后一个节点，这意味着总会有一个 "虚拟节点" 表示它之前的节点是 "real" 列表中的最后一个节点。这是说明的一部分。

typedef struct slist slist_ty;

typedef struct slist_node slist_node_ty;

typedef slist_node_ty *slist_iter_ty;

这是我对结构的实现： 他们要求我们在理论上允许节点中的任何类型的数据，这就是我写 void *.

的原因

struct slist
{
    slist_iter_ty head;
    slist_iter_ty end;
};

struct slist_node
{
    void *data;
    slist_iter_ty next;
};

这些是函数：

/* Creates an empty single-linked list and returns pointer to the head */
/* returns NULL on failure*/
/* Complexity: O(1) */
slist_ty *SlistCreate(void)
{
    slist_ty *new_list = (slist_ty *)malloc(sizeof(slist_ty));
    if (NULL == new_list)
    {
        fprintf(stderr, "Failed to allocate memory\n");
        return(NULL);
    }
    
    new_list->head = NULL;
    /* create a dummy node that will represent the end of the list */
    new_list->end = (slist_node *)malloc(sizeof(slist_node));
    if (NULL == new_list->end)
    {
        fprintf(stderr, "Failed to allocate memory\n");
        free(new_list);
        return(NULL);
    }
    
    new_list->end->data = NULL;
    new_list->end->next = NULL;
    
    return(new_list->head);
}

/* Deletes entire List */
/* Complexity: O(n) */
void SlistDestroy(slist_ty *slist)
{
    slist_iter_ty temp = NULL;
    
    assert(slist);
    
    while(NULL != slist->head)
    {
        tmp = slist->head;
        slist->head = temp;
        free(temp);
    }
    
    free(slist->end);
    slist->end = NULL;
    
    free(slist);
    slist = NULL;
}

/* Insters the element after the iterator, returns iterator to the new node */
/* TODO Undefined behaviour if iter is slist_END */
/* Complexity: O(1) */
slist_iter_ty SlistInsert(slist_iter_ty iter, void *data)
{
    slist_iter_ty new_node = NULL;
    
    assert(iter);
    assert(iter->next);
    assert(data);
    
    new_node->data = data;
    new_node->next = iter->next;
    iter->next = new_node;
    
    return(new_node);
}
    
    
    /* Returns iterator to end of the list */
    /* Complexity: O(1) */
    slist_iter_ty SlistIteratorEnd(const slist_ty *slist)
    {
        slist_iter_ty iterator = slist->head;
        
        assert (slist);
        
        if (NULL == slist->head)
        {
            return(NULL);
        }
        
        while (NULL != iterator->next->data)
        {
            iterator = iterator->next;
        }
        
        return(iterator);
    }

我请求反馈的问题是：

我应该 free 制作任何新的 slist_iter_ty 吗？比如我在上一个函数中做了一个slist_iter_ty类型的iterator，目的是为了帮我遍历列表。但是我无法释放迭代器，因为我需要 return 它作为 return 值。

我在SlistInsert函数里也做了一个new_node

它会作为 SlistDestroy 函数的一部分被释放吗？

谢谢。

Answer 1

slist - 是列表。当你创建这个列表时你使用 malloc 所以当你想销毁它时你需要释放列表。

另外 - 您每次使用插入时都使用了 malloc。所以当你想销毁列表时，你需要从所有节点清空它 - 所以你需要一个节点一个节点地释放

我看到你在 slist 插入中没有使用 malloc - 你怎么能不使用 malloc 来保留数据？

销毁函数中

 while(NULL != slist->head)
{
    tmp = slist->head;
    slist->head = temp;
    free(temp);
}

我想你的意思是：

while(NULL != slist->head)
{
    tmp = slist->head;
    slist->head = slist->head->next;
    free(tmp);
}

在插入函数中

slist_iter_ty new_node = NULL;

你应该写什么：

new_node = (slist_iter_ty) malloc(sizeof(slist_node));

in slist 结束函数

slist_iter_ty SlistIteratorEnd(const slist_ty *slist)

你可以 return（在你断言之后 :)）：

return (slist->end);

（否则它不会是 O(1) 它将是 O(n)）

使用 3 种不同的 typedef 在 C 中实现单链表

Singly Linked List Implementation in C using 3 different typedefs

c

pointers

linked-list

data-structures

singly-linked-list