3

ポインターを使用してスタックを実装しましたが、これも想定どおりに機能します。ここで、重複をプッシュせずに、スタックにプッシュする必要があります。たとえば、'2' をスタックにプッシュすると、別の '2' をプッシュしても、スタックには '2' が既に存在するため、'2' は 1 つだけになります。

以下は、新しいプッシュ関数を作成しようとした方法です。スタックをトラバースして、追加する要素をチェックすることになっていることはわかっていますが、それは間違っていると思いますか? 誰でも私を助けることができますか？

    typedef struct Node {
        void *content;
        struct Node *next;
    } Node;

    typedef struct Stack {
        Node *head;
        int count; 
    } Stack;

    void push(Stack *stack, void *newElem) {
        Node *newNode = (Node*) malloc(sizeof(Node));
        if (stack->count > 0) {
             int i;
             for (i = 0, newNode = stack->head; i < stack->count; i++, newNode =
                 newNode->next) {
                   if (newNode->content == newElem) return;
             }
        } else {
            newNode->next = stack->head;
            newNode->content = newElem;
            stack->head = newNode;
            stack->count++;
        }
    }
4

4 に答える 4

3 
if (newNode->content == newElem)

2 つのポインタを比較しています。それらの内容が等しいかどうかを確認したいと思います：

#include <string.h>

if (memcmp(newNode->content, newElem, size) == 0)

値sizeは、呼び出し元によって示される場合があります。あなたの場合、それはsizeof(int).

さらに、スタックをトラバースした後は、要素をデータ構造に追加しません。

于 2013-03-29T19:38:41.830 に答える
2

問題は、スタックが空でなく、スタック内に要素が見つからない場合、何もしないことです。キーワードを取り除き、elseそのコードを無条件にする必要があります。次に、必要かどうかを知る前に新しいノードにスペースを割り当て、さらに悪いことに、新しく割り当てられたポインターをスタックの反復で上書きして、プッシュする必要があるかどうかを確認します。}そのため、末尾の後にmallocを下に移動しますif

于 2013-03-29T19:43:51.130 に答える
1

あなたはすでに働いています

void push(Stack *stack, void *newElem);

右？

では、新しい関数を作成してみませんか

int push_unique(Stack *stack, void *newElem) {
    if (find_value(stack, newElem) != NULL) {
        return 1; // indicate a collision
    }
    push(stack, newElem); // re-use old function
    return 0; // indicate success
}

今、あなたは問題を書くことに減らしました

Node *find_value(Stack *stack, void *value);

…できますか？

于 2013-03-29T19:52:43.910 に答える
1

あなたがそれに気づいたかどうかはわかりませんが、提案された実装は、リンクされたリストに対して線形検索を実行しています。スタックに 2,000 個の要素をプッシュし、各要素値の平均 2 つの重複がある場合、それはリンク リストの平均 2,000 回の検索であり、500 ～ 750 個のリンクの間で平均されます (いつ、IE:どの順序で重複が提示されるかによって異なります)。これには 100 万回以上の比較が必要です。

上記の find_value() でのはるかに効率的な重複検出は、検索時間 O(1) のハッシュ テーブル、または検索時間 O(log N) のツリーを使用できます。スタックにプッシュする可能性のある値の数がわかっている場合は前者、リアルタイムでソケットからデータを受信するときのように数が不明な場合は後者です。(前者の場合、はるかに遅く、より冗長なリンクリストの代わりに、スタックを配列に実装できます)

どちらの場合でも、ハッシュテーブルを適切に維持するには、pop() 関数をハッシュテーブルの hashpop() 関数とペアにする必要があります。これにより、一致する値がハッシュテーブルから削除されます。

Hashtable を使用すると、スタックは、find_value() から返された、要素のハッシュ位置にある要素の値を指すことができます。ただし、自己均衡ツリーでは、ノードの位置、つまり要素の値が常に変化するため、要素の値をスタックとツリーに格納する必要があります。非常にタイトなメモリ環境で書いていない限り、2 番目のデータ構造が提供するパフォーマンスは、メモリの適度なコストに見合うだけの価値があります。

于 2013-04-28T09:36:32.270 に答える