我应该如何实现C Dymanic链表的容量？

Question

我知道当你在OOP语言中使用它作为ADT时，它很容易实现。

但是，如果像C这样的结构化语言应该做什么？

我应该使用全局变量吗？

我应该在每个节点中保留一个额外的变量吗？

还是什么？

我已经实施了我的动态堆栈，如this。

正如你所看到的，没有容量检查。

Answer 1

如果你想实现一个链表的容量限制，最好的办法是有一个每个列表的限制。下面的结构将允许：

// List structure: first/last pointers plus remaining capacity. 
typedef struct { 
    tNode *first; 
    tNode *last; 
    size_t freeCount; 
} tList; 

// Node structure: value pointer and next. 
typedef struct sNode { 
    void *val; 
    struct sNode *next; 
} tNode; 

然后你初始化你的极限每个列表：

// Creates an empty list. 
tList *makeList (size_t limit) { 
    tList *list = malloc (sizeof (tList)); 
    if (list == NULL) 
     return NULL; 
    list->freeCount = limit; 
    list->first = list->last = NULL; 
} 

// Destroys a list after clearing it if necessary. 
void destroyList (tList list) { 
    void *val = getNode (list); 
    while (val != NULL) { 
     free (val); 
     val = getNode (list); 
    } 
    free (list); 
} 

之后，添加节点，如果freeCount为零会失败，否则会增加一个节点，递减freeCount。删除节点将增加freeCount，是这样的：

// Puts an item on to the list end. 
int putNode (tList *list, void *val, size_t sz) { 
    // No more capacity. 
    if (list->freeCount == 0) return -1; 

    // Try to make node, returning error if no memory. 
    tNode *node = malloc (sizeof (tNode)); 
    if (node == NULL) return -1; 

    // Try to duplicate payload, clean up and return if no memory. 
    node->val = malloc (sz); 
    if (node->val == NULL) { 
     free (node); 
     return -1; 
    } 

    // Initialise node. 
    memcpy (node->val, val, sz) 
    node->next = NULL; 

    // Adjust remaining capacity and insert into list. 
    list->freeCount--; 
    if (list->first == NULL) { 
     list->first = list->last = node; 
    } else { 
     list->last->next = node; 
     list->last = node; 
    } 

    return 0; 
} 

 

// Gets an item from the list. 
void *getNode (tList *list) { 
    // If empty, just return NULL. 
    if (list->first == NULL) 
     return NULL; 

    // Get first node and remove it from list. 
    tNode node = list->first; 
    list->first = list->first->next; 

    // Get the payload and free the node. 
    void *val = node->val; 
    free (node); 

    // Adjust remianing capacity and return payload. 
    list->freeCount++; 
    return val; 
} 

通知所有正常的错误情况如何有（无记忆，列表为空等等）以及的当您已达到满容量时尝试添加节点的额外限制（当freeCount为零时）。

Answer 2

链接/动态堆栈通过向其顶部添加一个新的动态分配节点而增长。现在内存永远不是无限的，在动态增长的一个点上，内存不足，你将无法创建新的节点。这可以视为一个计算器。