我已经实现了一个带有指针的堆栈，它的工作方式也像假设的那样。现在，我需要把它压入堆栈，而不是压入一个副本。例如，如果我将'2'压入堆栈，再压入一个'2'仍然会导致堆栈中只有一个'2'，因为它已经存在了。
下面是我如何尝试创建新的push函数。我知道我应该遍历堆栈并检查我要添加的元素，但我猜我做错了?有人能帮我吗?
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++;
}
}
if (newNode->content == newElem)
您正在比较两个指针。我猜你想检查它们的内容是否相等:
#include <string.h>
if (memcmp(newNode->content, newElem, size) == 0)
size可以由呼叫方指定。在您的例子中，应该是sizeof(int)。
此外，一旦遍历堆栈，就不需要将元素添加到数据结构中。
问题是如果你的堆栈不是空的，而你没有找到已经在堆栈中的元素，你什么也没做。你需要去掉else关键字，并使该代码成为无条件的。然后，在知道是否需要新节点之前，就为它分配空间，更糟糕的是，在堆栈上迭代时覆盖新分配的指针，以查看是否需要将其压入。因此将malloc移到if
}之后您已经有一个工作
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);
…你能做到吗?
我不确定您是否意识到这一点，但是您建议的实现是在链表上执行线性搜索。如果你将2000个元素压入到一个堆栈中，每个元素值平均有2个重复，那么在一个链表中进行2000次搜索，平均在500-750个链接之间(这取决于什么时候，也就是什么顺序，重复的内容以何种方式呈现给搜索函数)。这需要100万次以上的比较。不漂亮。
在上面的find_value()中更有效的重复检测可以使用哈希表，搜索时间为O(1)，或者使用树，搜索时间为O(log N)。前者如果你知道有多少值可能被推到堆栈上，后者如果数字未知，比如从套接字实时接收数据。(如果前者，您可以在数组中实现堆栈，而不是更慢，更详细的链表)
无论哪种情况，要正确维护散列表，都需要将pop()函数与散列表hashpop()函数配对，该函数将从散列表中删除匹配的值。
使用哈希表，您的堆栈可以只指向位于其哈希位置的元素的值-从find_value()返回。然而，使用自平衡树时，节点的位置以及元素的值将一直在变化，因此您需要将元素的值存储在堆栈和树中。除非您是在一个非常紧张的内存环境中编写代码，否则第二种数据结构所提供的性能将非常值得在内存中付出适度的代价。