Действительно ли возможно иметь связанный список различных типов данных?

Использовать объединение для создания типа данных

union u_tag{
    char ch;
    int d;
    double dl;
};

struct node {
    char type;
    union u_tag u;
    struct node *next;
};

Используйте узел структуры для создания связанного списка. Тип решает, каков тип данных.

Харша Т., Бангалор

Что ж, в связном списке вам НЕ ОБЯЗАТЕЛЬНО связывать подобные структуры вместе. Пока у них есть соответствующие указатели вперед и / или назад, все в порядке. Например:

struct BaseLink
{
   BaseLink* pNext;
   BaseLink* pPrev;
   int       typeId;
};

struct StringLink
{
    BaseLink baseLink;
    char* pString;
};

struct IntLink
{
    BaseLink baseLink;
    int   nInt;
};

Таким образом, у вас будет связанный список, который идет от BaseLink к BaseLink. Дополнительные данные не проблема. Вы хотите видеть это как StringLink? Затем преобразуйте BaseLink в StringLink.

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

Вы можете использовать тип объединения:

enum type_tag {INT_TYPE, DOUBLE_TYPE, STRING_TYPE, R1_TYPE, R2_TYPE, ...};
struct node {
  union {
    int ival;
    double dval;
    char *sval;
    struct recordType1 r1val;
    struct recordType2 r2val;
    ...
  } data;
  enum type_tag dataType;
  struct node *prev;
  struct node *next;
};

Другой метод, который я изучил, - это использовать void * для данных и прикреплять указатели к функциям, которые обрабатывают типизированные вещи:

/**
 * Define a key type for indexing and searching
 */
typedef ... key_t;                 

/**
 * Define the list node type
 */
struct node {
  void *data;
  struct node *prev;
  struct node *next;
  void *(*cpy)(void *);            // make a deep copy of the data
  void (*del)(void *);             // delete the data
  char *(*dpy)(void *);            // format the data for display as a string
  int (*match)(void *, key_t);     // match against a key value
};

/**
 * Define functions for handling a specific data type
 */
void *copyARecordType(void *data)
{
  struct aRecordType v = *(struct aRecordType *) data;
  struct aRecordType *new = malloc(sizeof *new);
  if (new)
  {
    // copy elements of v to new
  }
  return new;
}

void deleteARecordType(void *data) {...}
char *displayARecordType(void *data) {...}
int matchARecordType(void *data, key_t key) {...}

/**
 * Define functions for handling a different type
 */
void *copyADifferentRecordType(void *data) {...}
void deleteADifferentRecordType(void *data) {...}
char *displayADifferentRecordType(void *data) {...}
int matchADifferentRecordType(void *data, key_t key) {...}

/**
 * Function for creating new list nodes
 */
struct node *createNode(void *data, void *(*cpy)(void *), void (*del)(void *), 
    char *(*dpy)(void *), int (*match)(void *, key_t))
{
  struct node *new = malloc(sizeof *new);
  if (new)
  {
    new->cpy = cpy;
    new->del = del;
    new->dpy = dpy;
    new->match = match;
    new->data = new->cpy(data);
    new->prev = new->next = NULL;
  }
  return new;
}

/**
 * Function for deleting list nodes
 */
void deleteNode(struct node *p)
{
  if (p)
    p->del(p->data);
  free(p);
}

/**
 * Add new node to the list; for this example, we just add to the end
 * as in a FIFO queue.  
 */
void addNode(struct node *head, void *data, void *(*cpy)(void*), 
  void (*del)(void *), char *(*dpy)(void *), int (*match)(void*, key_t))
{
  struct node *new = createNode(data, cpy, del, dpy, match);
  if (!head->next)
    head->next = new;
  else
  {
    struct node *cur = head->next;
    while (cur->next != NULL)
      cur = cur->next;
    cur->next = new;
    new->prev = cur;
  }
}

/**
 * Examples of how all of this would be used.
 */
int main(void)
{
  struct aRecordType r1 = {...};
  struct aDifferentRecordType r2 = {...};

  struct node list, *p;
  addNode(&list, &r1, copyARecordType, deleteARecordType, displayARecordType,
    matchARecordType);
  addNode(&list, &r2, copyADifferentRecordType, deleteADifferentRecordType,
    displayADifferentRecordType, matchADifferentRecordType);
  p = list.next;
  while (p)
  {
    printf("Data at node %p: %s\n", (void*) p, p->dpy(p->data));
    p = p->next;
  }
  return 0;
}

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

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

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

typedef struct
{
    /* linked list stuff here */    

    char m_type;
    void* m_data;
} 
Node;

См. этот вопрос .

На самом деле, вам не нужно сначала помещать указатель в структуру, вы можете поместить его где угодно, а затем найти начало структуры с помощью макроса containerof (). Ядро linux делает это с помощью связанных списков.

http://isis.poly.edu/kulesh/stuff/src/klist/

Просто к сведению, в C # вы можете использовать Object в качестве элемента данных.

class Node
{
     Node next;
     Object Data;
}

Затем пользователь может использовать что-то вроде этого, чтобы узнать, какой Object узел хранит:

if (obj.GetType() == this.GetType()) //
{

}

Я использую эти макросы для создания общих связанных списков. Вы просто создаете свою собственную структуру и используете макрос list_link где-нибудь как член структуры. Дайте этому макросу один аргумент, называющий структуру (без ключевого слова struct ). Это реализует двусвязный список без фиктивного узла (например, последний узел связывается обратно с первым узлом). Якорь - это указатель на первый узел, который в начале инициализируется list_init (якорь) , присваивая ему lvalue (разыменованный указатель на него - это lvalue). Затем вы можете использовать другие макросы в заголовке. Прочтите источник для комментариев о каждой доступной функции макроса. Это на 100% реализовано в макросах.

http://phil.ipal.org/pre-release/list-0.0.5.tar.bz2