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

Question

Здравствуйте, я пытаюсь изучить и построить структуры данных в c и хочу постепенно хранить целые числа в стеке. моя структура выглядит следующим образом:

typedef struct STACK_NODE_s *STACK_NODE;
typedef struct STACK_NODE_s{
    STACK_NODE forward;
    void *storage;
} STACK_NODE_t;

typedef struct L_STACK_s{
    STACK_NODE top;
} L_STACK_t, *L_STACK;

Через некоторое время l oop я хочу прочитать и сохранить мои символы в целочисленной форме.

//assume that str is an proper string
//assume that we have a linked stack called LS
int i=0;
int temp;
while(str[i]!='\0'){
    tmp=str[i]-'0';
    push(LS,(void *)&tmp);
}

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

Answer 1

Ответ должен касаться двух отдельных аспектов вашего вопроса: как организовать некоторую коллекцию предметов и откуда взять память для этого.

Первый фрагмент кода / Формат связанного списка

Первый фрагмент кода хорош таким, какой он есть. Он устанавливает связанный список , который имеет свои плюсы и минусы, но очень хорошо работает, если вы заранее не знаете количество элементов, если вы хотите иметь возможность быстро удалять или вставлять элементы куда-то в середине списка, и если вы не возражаете, что поиск одной определенной записи в списке стоит вам O (N) усилие .

Для универсальной c библиотечной реализации ...

... void* так же хорошо, как и ANSI C. Например, в C ++ вы могли бы сделать шаблон, который оставляет открытым тип, который хранится в списке (или, что еще лучше, вы бы напрямую использовали хорошо известную реализацию STL в классе forward_list<int>). К сожалению, ANSI C не имеет ничего похожего. Одним из решений является то, которое вы выбрали, создавайте int объекты и подключайте их адреса в ваш список void*. Другим решением для реализации библиотеки generi c является использование макроса прекомпилятора для типа и определение этого макроса над файлом заголовка, который содержит реализацию generi c. Это похоже на чистое решение C ++, но с прекомпилятором это не типобезопасно, поэтому этот подход далек от совершенства и сопряжен с несколькими рисками.

Второй фрагмент кода / Распределение памяти

Создание Список с void* вместо int (или любым другим типом без указателя) требует, чтобы вы выделяли дополнительную память рядом со списком. То есть, вам нужно не только выделить каждый элемент списка (= переменная типа STACK_NODE_t), но и фактическое значение записи (например, *(int*)(LS->storage)).

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

В любом случае вы не должны использовать указатель на переменную стека (например, локальную переменную внутри функции ) потому что память «за» этой переменной не будет зарезервирована для этой цели после выхода из функции, и тем временем память может использоваться для чего-то другого. Это, однако, то, что делает второй фрагмент кода, по-видимому. Как вы заметили, выбирая этот путь ...

, мы храним адрес одной и той же переменной снова и снова.

Повторное использование позиции памяти для другой записи того же самого список - крайний случай риска, описанного выше.

Answer 2

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