Вопрос:
ЗАДАЧА: Допустим, существует целочисленный стек S с M элементами. Дайте алгоритм, который удалит все те числа из стека S, которые появляются два или более раз. (напишите задачу, используя C/C++)
ПРИМЕЧАНИЕ. Нам не разрешается использовать std::stack для решения этой задачи.
Прежде всего я решил использовать язык Си, и это реализация стека, которую я использую.
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 для сравнения всех элементов и внутри, которые я использовал, если для проверки был задан одинаковый или нет, если они не совпадают. просто поместил их обратно в стек, который был ранее очищен, поэтому я должен пропустить все дублирующиеся элементы, но по какой-то причине этот код не работает должным образом, он продолжает рассылать мне сообщение “Полный!” сообщение.
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), дайте мне знать.
Лучший ответ:
этот код, который должен работать для обычного массива, но не уверен, что он подходит для стека, как мы могли бы использовать динамическую память
Правильность вашего кода для стеков не имеет ничего общего с динамическим размещением, и все, что связано с интерфейсом стека. Ты знаешь что это? Это абсолютно необходимо для решения вашей проблемы, и я не вижу намека на то, что вы либо знаете, как ведет себя стек, либо пытались его исследовать.
Вот вам, абстрактный тип стека:
- сохраняет в порядке очередности
- позволяет вставить новый элемент на вершину стека
- позволяет вам вытолкнуть последний добавленный элемент (который еще не был извлечен) из верхней части стека.
Это все, и нет произвольного доступа (т. stack[j] никогда не будет корректным выражением), поэтому алгоритм, который вы показали, не может работать.
Если у вас уже нет реализации стека – напишите ее! Вам все равно понадобится стек для компиляции и проверки вашего алгоритма. Определения, которые вы показываете, описывают хранилище, но не интерфейс.
В коде есть только две функции (плюс две для создания и уничтожения стека и, опционально, одна для запроса размера).
Теперь об алгоритме – вы можете когда-либо получить доступ только к верхнему элементу стека, поэтому вам нужно подумать о том, что делать с элементами, которые вы pop, которые не являются дубликатами. Они должны куда-то идти, потому что вы не можете видеть их под своим стеком, и вы не должны их терять.
Ваше редактирование показывает, что у вас есть тип данных стека, вроде: он использует три глобальные переменные, которые вы должны позаботиться, чтобы не сломать, и вы не можете повторно использовать любую функцию для вашего временного стека, потому что они работают с этими глобальными переменными.
Даже в 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 сообщение removeDuplicates реализовано в терминах абстракции стека, вам необходим алгоритм, который вы можете реализовать в терминах stack_push, stack_pop и т.д.
Если removeDuplicates сообщение removeDuplicates является внутренней функцией, работающей непосредственно над реализацией стека, а не реализуемой в терминах абстракции стека – тогда ваш базовый подход, вероятно, в порядке (если он очень далек от оптимального), и вам просто нужно изучить отладить ваш код.
Я до сих пор не знаю, какой из них является правдой (поэтому я не буду голосовать, чтобы открыть заново), но это совершенно разные вопросы.
Ответ №1
Я вижу несколько проблем с вашим текущим кодом:
В петле
for (k = j; k < size; k++) { stack[k] = stack[k + 1]; }
вы выходите за пределы, потому что вы используете stack[k+1]. Как бы вы это исправить?
Но затем, после того как вы переместили все элементы на 1, новый stack[j] может стать еще одним дубликатом stack[i]. Как бы вы это исправить? Вы могли бы рассмотреть возможность использования while цикл.
Вы используете глобальную переменную size которая является размером стека. Но есть также переменная sp которая является указателем стека и указывает на часть используемого стека. Так что вместо зацикливания по size вы должны зацикливаться на sp.
Обратите внимание, на что указывает указатель стека: значение -1 означает, что стек пуст, поэтому любые другие значения указывают на текущее значение в верхней части стека. (Это важно, потому что другая интерпретация указателя стека состоит в том, что он указывает на следующий свободный элемент стека.)
Это sp конечно уменьшается с каждым дубликатом, который вы удаляете из стека.
