Независимый стек данных - Программирование на C

Question

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

int arr[5]; //creates an integer array of size 5 for stack use
char arr[5]; //creates a character array of size 5 for stack use

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

Изначально я думал о реализации этого как объединение, но подход не только сложен, но и несовершенен. Любые другие предложения?

Answer 1

Я бы использовал такую ​​структуру:

struct THolder
{
   int dataType; // this is a value representing the type
   void *val; // this is the value 
};

Затем используйте массив THolder для хранения ваших значений.

Answer 2

Это действительно просто вариант ответа Пабло Санта-Круса, но я думаю, что он выглядит аккуратнее:

typedef enum { integer, real, other } type_t;

typedef struct {
    type_t type;
    union {
        int normal_int;     /* valid when type == integer */
        double large_float; /* valid when type == real */
        void * other;       /* valid when type == other */
    } content;
} stack_data_t;

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

Вы могли бы изучить магию препроцессора, полагаясь на зависимое от компилятора ключевое слово typeof , чтобы сделать это автоматически, но это, вероятно, ничего не изменит, но разрушитпортативность.

Answer 3

Некоторые люди предложили void* участника.В дополнение к этому решению я хотел бы предложить альтернативу (при условии, что ваш стек представляет собой связанный список структур, выделенных кучей):

struct stack_node
{
   struct stack_node *next;
   char data[];
};

data[] - это конструкция C99.data должен быть последним участником;это использует тот факт, что мы можем заполнить произвольные количества после адреса структуры.Если вы используете компилятор не-C99, вам, возможно, придется сделать какой-нибудь схематичный трюк, например, объявив его как data[0].

Тогда вы можете сделать что-то вроде этого:

struct stack_node*
allocate_stack_node(size_t extra_size)
{
   return malloc(sizeof(struct stack_node) + extra_size);
}

/* In some other function... */

struct stack_node *ptr = allocate_stack_node(sizeof(int));

int *p = (int*)ptr->data;

Если этовыглядит уродливо и хакерски, это ... Но преимущество здесь в том, что вы все равно получаете общее благо, не вводя больше косвенности (таким образом, немного быстрее время доступа для ptr->data, чем если бы это было void*, указывающее на другое местоположение изструктура.)

Обновление: Я также хотел бы отметить, что приведенный мной пример кода может иметь проблемы, если ваша машина имеет другие требования выравнивания для int, чем char.Это подразумевается как иллюстративный пример;YMMV.

Answer 4

Я создал библиотеку, которая работает для любого типа данных:

    List new_list(int,int);

создает новый список, например:

    List list=new_list(TYPE_INT,sizeof(int));
    //This will create an list of integers
    Error append(List*,void*);

добавляет элемент в список.* Append принимает в качестве аргумента два указателя, если вы хотите сохранить указатель на список, не передавайте указатель указателем

например:

    //using the int list from above

      int a=5;
      Error err;
      err=append(&list,&a)

      //for an list of pointers
      List listptr=new_list(TYPE_CUSTOM,sizeof(int*));
      int num=7;
      int *ptr=#

      append(&listptr,ptr);


      //for list of structs
      struct Foo
      {
        int num;
        float *ptr;
      };

      List list=new_list(TYPE_CUSTOM,sizeof(struct Foo));
      struct Foo x;
      x.num=9;
      x.ptr=NULL;

      append(&list,&x);

Ошибка get (List *, int);

Получает данные по указанному индексу.При вызове текущего списка poiter будет указывать на данные.

например:

    List list=new_list(TYPE_INT,sizeof(int));

    int i;
    for(i=1;i<=10;i++)
      append(&list,&i);

    //This will print the element at index 2
    get(&list,2);
    printf("%d",*(int*)list.current);

Ошибка pop (List *, int);

Pops и элемент из указанного индекса

Например:

      List list=new_list(TYPE_INT,sizeof(int));

      int i;
      for(i=1;i<=10;i++)
        append(&list,&i);

      //element in the index 2 will be deleted, 
      //the current pointer will point to a location that has a copy of the data  

      pop(&list,2);
      printf("%d",*(int*)list.current);

      //To use the list as stack, pop at index list.len-1
      pop(&list,list.len-1);

      //To use the list as queue, pop at index 0
      pop(&list,0);

Ошибка слияния (Список, Список);

Слияние двух списков одного типа.Если типы различаются, в объекте Error возвращается сообщение об ошибке;

например:

     //Merge two elements of type int
     //List 2 will come after list 1
     Error err;
     err=merge(&list1,&list2);
    Iterator get_iterator(List*);

Получить итератор в список.при инициализации будет иметь указатель на первый элемент списка.

например:

    Iterator ite=get_iterator(&list);
    Error next(Iterator*);

Получить следующий элемент списка.

например:

// Как перебрать список целых чисел

      Iterator itr;
      for(itr=get_iterator(&list);  ite.content!=NULL;  next(ite))
        printf("%d",*(int*)ite.content);

https://github.com/malayh/C-List

Answer 5

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

#define GENERIC_STACK(name, type, typeid, elements) \
  struct name##_stack { \
    unsigned int TypeID; \
    type Data[elements]; \
  } name = { .TypeID = typeid }

Конечно, ваш «TypeID» должен был бы разрешить все возможные согласованные типы, которые вы ожидаете;может возникнуть проблема, если вы намереваетесь использовать целые структуры или другие определяемые пользователем типы.

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