推送到包含C中唯一唯一值的堆栈

Question

我已经实现了一个带指针的堆栈，它的工作方式也是如此。现在，我需要它推送到堆栈，而不是推送副本。例如，如果我将'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++;
        }
    }

Answer 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);

你能做到吗？

Answer 2

if (newNode->content == newElem)

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

#include <string.h>

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

值size可以由呼叫者指示。在你的情况下，它应该是sizeof(int)。

此外，一旦遍历了堆栈，就不会将元素添加到数据结构中。

Answer 3

问题是，如果您的堆栈非空，并且您没有找到堆栈中已有的元素，则不会执行任何操作。您需要摆脱else关键字并使该代码无条件。然后，在知道是否需要之前为新节点分配空间，更糟糕的是，在堆栈上迭代时覆盖新分配的指针，看看是否需要推送它。因此，在}结束if后，将malloc向下移动

Answer 4

我不确定你是否意识到这一点，但你提议的实现是在链表上执行线性搜索。如果您在堆栈上推送2,000个元素，每个元素值平均重复2个，那么对链接列表进行2,000次搜索，平均在500-750个链接之间（这取决于何时，IE：什么顺序，重复项呈现给搜索功能。这需要100万+比较。不漂亮。

上面的find_value（）中的更有效的重复检测可以使用具有搜索时间O（1）的搜索时间O（log N）的搜索时间O（1）或树的哈希表。前者如果您知道有多少值可能会进入堆栈，而后者如果数量未知，就像实时从套接字接收数据一样。 （如果前者你可以在一个数组中实现你的堆栈，而不是一个更慢，更详细的链表）

在任何一种情况下，为了正确维护哈希表，你的pop（）函数需要与哈希表hashpop（）函数配对，这将从哈希表中删除匹配值。

使用Hashtable，您的堆栈可以指向位于其散列位置的元素值 - 从find_value（）返回。但是，使用自平衡树，节点的位置以及元素值将一直在变化，因此您需要将元素的值存储在堆栈和树中。除非您在非常紧凑的内存环境中编写，否则第二个数据结构所能提供的性能将非常值得在内存中适度降低成本。