是否可以拥有不同数据类型的链表？

Question

这只是另一个采访问题.

我们可以有一个不同数据类型的链表,即链表中的每个元素可以有不同的结构或联合元素吗？如果有可能请你举个例子解释一下？

Answer 1

使用union创建数据类型

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

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

使用struct node创建链表.type决定数据的数据类型.

Harsha T,班加罗尔

Answer 2

好吧,在一个链表中,你不需要像喜欢结构一样链接.只要他们有适当的前进和/或后退指针你就可以了.例如:

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,所以当你到达时,你知道要把它投射到什么.

Answer 3

您可以使用联合类型:

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;
}

显然,我从这个例子中省略了一些错误检查和处理代码,我不怀疑它有很多问题,但它应该是说明性的.

Answer 4

您可以让链表中的每个节点都有一个指向您的数据的 void* 。由您决定如何确定该指针指向的数据类型。