我應該如何實現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

鏈接/動態堆棧通過向其頂部添加一個新的動態分配節點而增長。現在內存永遠不是無限的，在動態增長的一個點上，內存不足，你將無法創建新的節點。這可以視爲一個計算器。