3

我已经实现了一个带有指针的堆栈，它也像它假设的那样工作。现在，我需要它推送到堆栈，而不是推送副本。例如，如果我将“2”压入堆栈，再压入另一个“2”仍然会导致堆栈中只有一个“2”，因为它已经存在。

下面是我如何尝试创建新的推送功能。我知道我想遍历堆栈并检查我要添加的元素，但我想我做错了吗？谁能帮我吗？

    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)

您正在比较两个指针。我猜你想检查它们的内容是否相等：

#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 万次以上的比较。不漂亮。

A MUCH more efficient duplicate detection in find_value() above could use a hash table, with search time O(1), or a tree, with search time O(log N). The former if you know how many values you're potentially pushing onto the stack, and the latter if the number is unknown, like when receiving data from a socket in real-time. (if the former you could implement your stack in an array instead of a much slower, and more verbose linked-list)

In either case, to properly maintain the hashtable, your pop() function would need to be paired with a hashtable hashpop() function, which would remove the matching value from the hashtable.

With a Hashtable, your stack could just point to the element's value sitting in it's hash location - returned from find_value(). With a self-balancing tree however, the location of the node, and thus the element value, would be changing all the time, so you'd need to store the element's value in the stack, and the tree. Unless you're writing in a very tight memory environment, the performance the 2nd data structure would afford would be well worth the modest cost in memory.

于 2013-04-28T09:36:32.270 回答