Каков наилучший способ реализации динамически изменяемого размера стека в C? - PullRequest
Новая
       14

Каков наилучший способ реализации динамически изменяемого размера стека в C?

2 голосов
/ 13 января 2010

Каков лучший правильный способ реализации динамически изменяемого размера стека в C?

Например, я хочу выделить объем памяти для стека, но когда этот стек заполняется, выделенная память удваивается для размещения новых данных и т. Д.

У меня есть стек, реализованный в минуту с использованием простого массива пустых указателей, таким образом, я могу хранить указатели всех типов, поэтому его можно использовать многократно. Когда я пытаюсь реализовать это, используя malloc () / realloc (), я сталкиваюсь с ошибками при выполнении математических указателей из-за пустых указателей, не имеющих назначенного размера.

Каков лучший правильный способ реализации динамически изменяемого размера стека в C?

EDIT:

Я пытался что-то вроде этого кода (проверка ошибок удалена), но теперь я понимаю, что не могу взаимодействовать с пустыми указателями, подобными этому. Так что я просто думаю, как сделать что-то подобное на законных основаниях. Это большое учебное упражнение для меня, так как я никогда не сталкивался с C. 

#include <stdio.h>
#include <stdlib.h>

#include "stack.h"

static int index = 0;

void* CreateStack(void)
{
    void *stack = malloc(INITIAL_STACK_SIZE);
    return stack;
}

void* Pop(void *stack)
{
    return stack + index--;
}

void Push(void *stack, void *value)
{
    *(stack + index) = value;
}

void FreeStack(void *stack)
{
    free(stack);
}

Ответы [ 5 ]

4 голосов
/ 13 января 2010

Я думаю, проблема в том, что вы используете неверный размер в своих вызовах. Вам не нужен размер указателя - вам нужен размер самого указателя.

3 голосов
/ 13 января 2010

звучит так, как будто вы делаете 

malloc(n * sizeof(void))

прямо или косвенно, вам нужно 

malloc(n * sizeof(void*))

конечно, реальный ответ - std :: stack (на c ++)

1 голос
/ 13 января 2010

Я отвечал на это раньше, как часть предыдущего вопроса:

https://stackoverflow.com/questions/2006726/which-would-you-prefer-to-have-to-maintain/2007647#2007647

Вам придется немного адаптировать вещи - замените char * на void *, переименуйте «addString» в «push» и напишите «pop» функцию. Да, и добавьте проверку ошибок в вызовах malloc и realloc, которая была опущена в этом ответе, потому что она была опущена в коде опрашивающего.

Как говорит Нейл, хотя "лучший" очень субъективен. Растущий массив - это только один из способов реализации стека. В зависимости от модели использования и ваших требований к сложности кода, скорости и использованию памяти вам может потребоваться связанный список или стратегия гибридного списка / массива, аналогичная классу std::deque в C ++.

1 голос
/ 13 января 2010

Один из методов - использовать массив для стека. Следите за емкостью массива. Если массив заполнится, выделите новый массив, скопируйте старые элементы в новый массив, затем удалите старый массив.

Другой вариант - использовать связанный список в качестве основы для стека. Это позволяет динамическое распределение для каждого нового элемента.

0 голосов
/ 13 января 2010

Используйте Код Дэйва Хансона из C Интерфейсы и реализации . Это отличная книга, и вы увидите, как сделать трюк с динамическим массивом. Элегантный и эффективный, и многоразовый! Код можно загрузить бесплатно.

...