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

I know it is very easy to implement when you are using it as an ADT in OOP languages.

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

But what should be done in case of structured language like C?

但是在结构化语言如C的情况下应该怎么办?

Should I use a global variable?

我应该使用全局变量吗?

Should I keep an extra variable in every node?

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

Or what?

I have implemented my Dynamic Stack like this.

我已经像这样实现了我的动态堆栈。

As you can see there are no capacity checking.

如您所见,没有容量检查。

2 个解决方案

#1

If you want to implement a capacity limit to a linked list, the best way is to have a per-list limitation. The following structures will allow that:

如果要对链表实施容量限制,最好的方法是使用每个列表限制。以下结构将允许:

// 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;

Then you initialise your limit per list:

然后,您初始化每个列表的限制:

// 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);
}

After that, adding a node will fail if the freeCount is zero, otherwise it will add a node and decrement freeCount. Removing a node will increase freeCount, something like:

之后,如果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;
}

Notice how all the normal error conditions are there (no memory, list empty and so on) as well as the extra limitation of trying to add a node when you've already reached full capacity (when freeCount is zero).

注意所有正常的错误条件是如何存在的(没有内存,列表为空等)以及当你已经达到满容量时(当freeCount为零时)尝试添加节点的额外限制。

#2

Linked/Dynamic stacks grows by adding a new dynamically allocated node to it's top. Now memory is never unlimited, at one point in dynamically growing you'll run out of memory and you won't be able to create a new node. This can be treated as a *.

链接/动态堆栈通过向其顶部添加新的动态分配节点而增长。现在内存永远不会无限制,在动态增长的某一点上,你将耗尽内存并且你将无法创建新节点。这可以视为*。

#1