Создать универсальный стек, реализованный с помощью связанного списка в C - PullRequest
Новая
       36

Создать универсальный стек, реализованный с помощью связанного списка в C

0 голосов
/ 25 января 2012

Я хочу создать общий стек. Я хочу реализовать это с помощью связанного списка.

Я создал эту структуру stack_l : 

typedef struct stack
 {
   void * data;

   void (*copy)(void *o);

   struct stack *next;

 } stack_l;

У меня есть несколько вопросов:

  • Второе поле структур - это указатель на функцию для копирования новых данных (передача по аргументу в функцию Push). Прототипом функции Push является:

stack_l * Push (stack_l * head, void * d);

  1. Правильно ли передать указатель на функцию copy?
  2. Я должен реализовать это в функции Push ??
  • Необходимо ли создавать функцию NewStack (например) для инициализации поля структур, или лучше иметь только функцию Push, которая создает 1-й элемент, если стек пуст, и добавлять новый элемент сверху, если есть хотя бы один элемент?
  • A void * необходимо выделить с помощью malloc?

1 Ответ

1 голос
/ 25 января 2012

Прежде всего, вам не нужны разные идентификаторы для stack и stack_l. Теперь на ваши вопросы:

Ваша функция Push несовместима с типом поля copy в stack_l. Если вы хотите включить указатель на (member-) функции в вашем struct, чтобы он выглядел как C ++, вам все равно придется передать свой объект этим функциям.

Да, вы должны где-то реализовать свою функциональность, и это не может быть в пределах определения struct stack. Это означает, что вам нужна какая-то функция конструктора (вы можете вызвать ее newStack, если хотите). Ваш конструктор должен по крайней мере инициализировать ваши указатели на функции (если вы хотите сохранить их). Если вы решите не сохранять эти указатели на функции, вы можете поместить код инициализации в свою подпрограмму push, как вы и предлагали: 

stack_l* stackPush(stack_l* head, void* content) {
  // head might be NULL, meaning the stack is "empty" or it might be an actual pointer
  // we don't care
  stack_l* const front = malloc(sizeof(stack_l));
  *front = (stack_l){.data = content, .next = head};
  return front;
}

Обратите внимание, что вы должны явно указать, что такое пустой стек. Так что вы можете захотеть реализовать конструктор для ясности: 

stack_l* stackCreateEmpty() {
  retun NULL;
}

А может быть, даже деструктор: 

void stackDestroyEmpty(stack_l* s) {
  assert(s == NULL && "Tried to destroy non-empty stack.");
}

К вашему последнему вопросу: как вы видите выше, вы должны использовать malloc, чтобы получить место для хранения вашего stack_l объекта, кроме этого вам не нужно выделять дополнительное место для вашего void* члена, как это является частью stack_l.

...