c - 如何从堆栈中删除重复项？

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 4 年前。

Improve this question

任务:假设有一个包含 M 个元素的整数堆栈 S。给出从堆栈 S 中删除所有出现两次或多次的数字的算法。 (使用C/C++编写任务)

注意:我们不得使用 std::stack来解决这个任务。

首先我决定使用C语言，这是我使用的堆栈实现。

int* stack = (int*)malloc(10 * sizeof(int));
int size = 10;
int sp = -1;

bool isempty() {
    return (sp == -1);
}

bool isfull() {
    return (sp == size - 1);
}

void push(int x) {
    if (isfull()) {
        printf("Full!");
    }
    else {
        sp++;
        stack[sp] = x;
    }
}

int pop() {
    int x;
    if (isempty()) {
        printf("Empty!");
    }
    else {
        x = stack[sp];
        sp--;
    }
    return x;
}

void peek() {
    if (!isempty()) {
        printf("%d", stack[sp]);
    }
}

void clear() {
    while (!isempty()) {
        pop();
    }
}

void print() {
    if (!isempty()) {
        for (int i = 0; i < sp+1; i++) {
            printf("%d ", stack[i]);
        }
    }
    printf("\n");
}

我解决这个任务的想法是创建另一个临时堆栈并将主堆栈复制到其中，而不是使用两个for循环进行比较所有元素以及其中我使用 if 语句来检查它们是否相同，如果它们不同，我只是将它们推回到之前清除的堆栈中，通过这种方式我应该跳过所有重复的元素，但由于某种原因，该代码无法正常工作，它让我一直在发送垃圾邮件“Full!”消息。

void removeDuplicates() {
    int* temp = (int*)malloc(10 * sizeof(int));
    int temp_size = 10;
    int temp_sp = -1;

    for (int i = 0; i < sp + 1; i++) {
        temp[i] = stack[i];
    }
    temp_sp = sp;
    clear();

    for (int i = 0; i < temp_sp+1; i++) {
        for (int j = i + 1; j < temp_sp+1; i++) {
            if (!(temp[i] == temp[j])) {
                push(temp[i]);
            }
        }
    }
}

这是我用来测试功能的主要函数:

int main() {
    push(1);
    push(2);
    push(3);
    push(4);
    push(3);
    push(5);

    removeDuplicates();

    print();

    return 0;
}

如果有更简单的方法使用 C++(不是 std::stack )来解决此问题，请告诉我。

Answer 1

this code that is supposed to work for normal array, but not sure if it's right for stack as we might using dynamic memory

您的代码对于堆栈是否正确与动态分配无关，而与堆栈的接口(interface)有关。你知道那是什么吗？这对于解决您的问题绝对重要，而且我没有看到任何迹象表明您知道堆栈的行为方式或尝试研究它。

给你，stack abstract datatype :

• 保留后进先出的顺序
• 允许您将新元素插入堆栈顶部
• 允许您从堆栈顶部弹出最近推送的元素(尚未弹出)。

这就是一切，并且没有随机访问(即，stack[j]永远不会是有效的表达式)，因此对于您的算法来说显然是不可能的显示有效。

如果您还没有堆栈实现 - 编写一个!无论如何，您将需要一个堆栈来编译和测试您的算法。您显示的定义描述了存储，但没有描述接口(interface)。

只需编写两个函数(加上两个用于创建和销毁堆栈的函数，以及一个用于查询大小的可选函数)。

现在来说说算法 - 您只能访问堆栈的顶部元素，因此您需要考虑如何处理您弹出的不元素> 重复。它们必须去某个地方，因为当它们位于主堆栈上时，您无法看到它们下面的情况，而且您不能丢失它们。

<小时/>

您的编辑显示您确实有一个堆栈数据类型，有点:它使用三个全局变量，您必须小心不要破坏它们，并且您不能为临时堆栈重用任何函数，因为它们在那些全局变量。

即使在 C 语言中，我也希望看到类似的内容(基于您上面的未经测试、未编译的示例代码)

struct Stack {
    int size;
    int sp;
    int data[];
};

struct Stack* stack_create(int elements) {
    struct Stack *s = malloc(sizeof(*s) + elements * sizeof(int));
    s->size = elements;
    s->sp = -1;
    return s;
}

bool stack_isEmpty(struct Stack *s) { return s->sp == -1; }
bool stack_isFull(struct Stack *s) { return s->sp == s->size - 1; }
void stack_push(struct Stack *s, int x)
{
    assert(!stack_isFull(s));
    s->data[++s->sp] = x;
}
int stack_pop(struct Stack *s)
{
    assert(!stack_isEmpty(s));
    return s->data[(s->sp)--];
}

因为这样您就可以在主堆栈和临时堆栈上使用相同的操作。

如果removeDuplicates消息应该按照堆栈抽象来实现，那么您需要一个可以按照stack_push实现的算法>、stack_pop 等

如果removeDuplicates消息应该是直接在堆栈实现上操作的内部函数，而不是根据堆栈抽象来实现 - 那么您的基本方法可能没问题(如果离最佳状态还很远)，您只需要学习调试您的代码即可。

我仍然不知道哪一个是正确的(所以我不会投票重新开放)，但它们是完全不同的问题。