快捷搜索:

C语言的那些小秘密之链表(一)

C语言的那些小秘密之链表(一)

  链表,一个对于学习过C语言的人都是再熟悉不过的概念了,可能很多学习过链表的人都觉得链表没什么值得太在意的地方,可是如果你走进linux内核,去看看linux内核里面链表的实现方式,你不得不为之惊叹。可能有人会觉得linux内核链表实现方式仅此而已,但是你要知道,如果你没有见到这样的实现方式之前,能写出那样的链表嘛?所以在写链表的文章时,我深知自己不可能用一篇文章来讲解完链表的知识点,所以我特地分为三个部分(单链表、双链表、linux内核链表,而其中linux内核链表单独拿出来讲是因为它的特殊性,在后面的博客中我们再来细谈它)来进行讲解,尽可能用简短的文字描述加上简单易懂的代码来向读者讲解我所理解的链表,希望我所讲的链表能都对你有所帮助。接下来言归正传,开始我们的链表之旅。

本文引用地址:

  那么什么是链表呢?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成,即链表中的每个元素,结点可以在运行时动态生成。每个结点均由两个部分所组成:一个是存储数据元素的数据域,另一个是存储相邻结点地址的指针域。相比于线性表顺序结构,链表比较方便插入和删除操作。

  对于链表我们可以将其分为单链表、双向链表和循环链表等。首先我们先讲讲单链表。

  所谓单链表,是指数据结点是单向排列的。一个单链表结点,其结构类型分为两部分:

  1、数据域:用来存储本身数据

  2、指针域:用来存储下一个结点地址或者说指向其直接后继的指针。

  如下图所示:


C语言的那些小秘密之链表(一)


  注意:如果有图中的红色箭头部分,则变为了单向循环链表。

  那什么又是双链表呢?双向链表其实是单链表的改进。当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。

  在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。

  如下图所示:


C语言的那些小秘密之链表(一)


  注意:如果有图中的红色箭头部分,则变为了双向循环链表。

  看完了上面的介绍之后,我想读者对于链表算是有了一个大致的了解。那么接下来我们的任务就是学习如何使用链表,我们从最简单的代码开始,教会读者来学习使用链表,首先我们来看一个单链表的创建。为了便于讲解,我在此就把所有的代码放到一个源文件中来执行了,当然读者在实际编写代码的过程中不管是为了维护还是阅读都应该使用头文件,而不要在一个源文件中一条龙似地写到底。

  #include

  #include

  #include

  #include

  #define N 3

  #undef _EXAM_ASSERT_TEST_ //禁用

  //#define _EXAM_ASSERT_TEST_ //启用

  #ifdef _EXAM_ASSERT_TEST_ //启用断言测试

  void assert_report( const char * file_name, const char * function_name, unsigned int line_no )

  {

  printf( "\n[EXAM]Error Report file_name: %s, function_name: %s, line %u\n",

  file_name, function_name, line_no );

  abort();

  }

  #define ASSERT_REPORT( condition ) \

  do{ \

  if ( condition ) \

  NULL; \

  else \

  assert_report( __FILE__, __func__, __LINE__ ); \

  }while(0)

  #else // 禁用断言测试

  #define ASSERT_REPORT( condition ) NULL

  #endif /* end of ASSERT */

  typedef enum _SListReturn

  {

  SLIST_RETURN_OK

  }SListReturn;

  typedef struct node

  {

  char name[10];

  int score;

  struct node *link;

  }stud;

  stud * creat(int n)

  {

  stud *p,*h,*s;

  int i;

  if((h=(stud *)malloc(sizeof(stud)))==NULL)

  {

  printf("分配内存空间失败!");

  exit(0);

  }

  h->name[0]='\0';

  h->score=0;

  h->link=NULL;

  p=h;

  for(i=0;i

  {

  if((s= (stud *) malloc(sizeof(stud)))==NULL)

  {

  printf("分配内存空间失败!");

  exit(0);

  }

  p->link=s;

  printf("请输入第%d个人的姓名:",i+1);

  scanf("%s",s->name);

  printf("请输入第%d个人的成绩:",i+1);

  scanf("%d",&s->score);

  s->link=NULL;

  p=s;

  }

  return h;

  }

  SListReturn destroy(stud* head)

  {

  stud* tmp,*next;

  tmp=head;

  while(tmp!=NULL)

  {

  next=tmp->link;

  tmp->link=NULL;

  free(tmp);

  tmp=next;

  }

  return SLIST_RETURN_OK;

  }

  SListReturn print(stud* head)

  {

  stud* tmp=head->link;

  while(tmp!=NULL)

  {

  printf("%s的成绩为%d\t",tmp->name,tmp->score);

  tmp=tmp->link;

  }

  return SLIST_RETURN_OK;

  }

  void main()

  {

  int number;

  stud *head;

  number=N;

  head=creat(number);

  ASSERT_REPORT(print(head)==SLIST_RETURN_OK);

  ASSERT_REPORT(destroy(head)==SLIST_RETURN_OK);

  }

  运行结果为:

  root@ubuntu:/home/paixu# ./tt

  请输入第1个人的姓名:rewq

  请输入第1个人的成绩:123

  请输入第2个人的姓名:fdsa

  请输入第2个人的成绩:456

  请输入第3个人的姓名:vcxz

  请输入第3个人的成绩:789

  rewq成绩为123 fdsa成绩为456 vcxz成绩为789

您可能还会对下面的文章感兴趣: