当前位置:首页 > C语言 >

C语言中实现通用双链表

发布时间:2021-04-30 10:42:03 作者:佚名 阅读:(24)

/**
  * C 和 C++ 的谁好谁坏的争论还在不断的继续,C语言的使用非常的广范,很多大型的系统都是用C 语言来写的。
  * C++ 似乎有更好的编程范式。支持面向对象,模版,省去了很多处理。
  * C++ 最好不要滥用,具体问题,具体分析。
  *
  */
  #include <stdio.h>
  #include <stdlib.h>
  /**
  * 通用链表声明部分
  */
  struct list_head {
  struct list_head *next, *prev;
  };
  #define LIST_HEAD_INIT(name) { &(name), &(name) }
  #define LIST_HEAD(name) \
  struct list_head name = LIST_HEAD_INIT(name)
  #define INIT_LIST_HEAD(ptr) do { \
  (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  } while (0)
  static  void __list_add(struct list_head * new, struct list_head * prev, struct list_head * next);
  static  void list_add(struct list_head *new, struct list_head *head);
  static  void list_add_tail(struct list_head *new, struct list_head *head);
  static  void __list_del(struct list_head * prev, struct list_head * next);
  static  void list_del(struct list_head *entry);
  static  void list_del_init(struct list_head *entry);
  static  int list_empty(struct list_head *head);
  static  void list_splice(struct list_head *list, struct list_head *head);
  #define list_entry(ptr, type, member) \
  ((type *)((char *)(ptr)-(size_t)(&((type *)0)->member)))
  #define list_for_each(pos, head) \
  for (pos = (head)->next; pos != (head); pos = pos->next)
  #define NEW_LIST_NODE(type, node) \
  {\
  node = (struct type *)malloc( sizeof(struct type)); \
  if (node == NULL) exit(-1);\
  }
  #define FREE_LIST(type, p, list_name)\
  {\
  struct type  *posnode;\
  while(!list_empty(&(p)->list_name)) {\
  posnode = list_entry((&(p)->list_name)->next, type, list_name);\
  list_del((&(p)->list_name)->next);\
  free(posnode);\
  }\
  }
  /**
  * 通用链表实现部分
  */
  static  void __list_add(struct list_head * new, struct list_head * prev, struct list_head * next)
  {
  next->prev = new;
  new->next = next;
  new->prev = prev;
  prev->next = new;
  }
  static  void list_add(struct list_head *new, struct list_head *head)
  {
  __list_add(new, head, head->next);
  }
  static  void list_add_tail(struct list_head *new, struct list_head *head)
  {
  __list_add(new, head->prev, head);
  }
  static  void __list_del(struct list_head * prev, struct list_head * next)
  {
  next->prev = prev;
  prev->next = next;
  }
  static  void list_del(struct list_head *entry)
  {
  __list_del(entry->prev, entry->next);
  }
  static  void list_del_init(struct list_head *entry)
  {
  __list_del(entry->prev, entry->next);
  INIT_LIST_HEAD(entry);
  }
  static  int list_empty(struct list_head *head)
  {
  return head->next == head;
  }
  static  void list_splice(struct list_head *list, struct list_head *head)
  {
  struct list_head *first = list->next;
  if (first != list) {
  struct list_head *last = list->prev;
  struct list_head *at = head->next;
  first->prev = head;
  head->next = first;
  last->next = at;
  at->prev = last;
  }
  }
  typedef struct int_list
  {
  struct list_head list;
  int data;
  } int_list, *pint_list;
  void test_int_list()
  {
  struct int_list *dlink, *newnode, *posnode;
  struct list_head *pos;
  int i;
  NEW_LIST_NODE(int_list, dlink);
  INIT_LIST_HEAD(&dlink->list);
  for (i = 1; i < 10; i++)
  {
  NEW_LIST_NODE(int_list, newnode);
  newnode->data = i;
  list_add_tail(&newnode->list, &dlink->list);
  }
  list_for_each(pos, &dlink->list) {
  posnode = list_entry(pos, int_list, list);
  printf("%d ", posnode->data);
  }
  FREE_LIST(int_list, dlink, list);
  printf("\n");
  }
  typedef struct string_list
  {
  struct list_head list;
  char *data;
  } string_list, *pstring_list;
  void test_string_list()
  {
  char * strings[] = {
  "我们",
  "都是",
  "中国",
  "人"
  };
  struct string_list *dlink, *newnode, *posnode;
  struct list_head *pos;
  int i, length;
  length = sizeof(strings) / sizeof(char *);
  NEW_LIST_NODE(string_list, dlink);
  INIT_LIST_HEAD(&dlink->list);
  for (i = 0; i < length; i++)
  {
  NEW_LIST_NODE(string_list, newnode);
  newnode->data = strings[i];
  list_add(&newnode->list, &dlink->list);
  }
  list_for_each(pos, &dlink->list) {
  posnode = list_entry(pos, string_list, list);
  printf("%s ", posnode->data);
  }
  FREE_LIST(string_list, dlink, list);
  printf("\n");
  }
  int main()
  {
  test_int_list();
  test_string_list();
  }


欢迎分享转载→ C语言中实现通用双链表

© 2015-2021 - 吾爱编程网 版权所有 苏ICP备18033726号-1关于我们 - 网站声明 - 联系我们