2

OOP言語でADTとして使用する場合、実装は非常に簡単です。

しかし、Cのような構造化された言語の場合はどうすればよいでしょうか。

グローバル変数を使用する必要がありますか？

すべてのノードに追加の変数を保持する必要がありますか？

または何？

私はこのようにダイナミックスタックを実装しました。

ご覧のとおり、容量チェックはありません。

4

2 に答える 2

3

リンクリストに容量制限を実装する場合は、リストごとに制限を設けるのが最善の方法です。次の構造はそれを可能にします：

// 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フルキャパシティーに達したとき（がゼロのとき）にノードを追加しようとするという追加の制限があることに注意してください。

于 2010-10-17T09:11:34.250 に答える
1

リンク/動的スタックは、動的に割り当てられた新しいノードをその最上位に追加することで拡大します。現在、メモリは無制限ではありません。動的に成長するある時点で、メモリが不足し、新しいノードを作成できなくなります。これは、stackoverflowとして扱うことができます。

于 2010-10-17T08:16:28.783 に答える