链表，一个关于学习过C言语的人都是再了解不过的概念了，或许许多学习过链表的人都觉得链表没什么值得太介意的当地，可是假如你走进linux内核，去看看linux内核里边链表的完成办法，你不得不为之惊叹。或许有人会觉得linux内核链表完成办法仅此而已，可是你要知道，假如你没有见到这样的完成办法之前，能写出那样的链表嘛?所以在写链表的文章时，我深知自己不或许用一篇文章来解说完链表的知识点，所以我特别分为三个部分(单链表、双链表、linux内核链表，而其间linux内核链表独自拿出来讲是因为它的特殊性，在后边的博客中咱们再来细谈它)来进行解说，尽或许用简略的文字描述加上简略易懂的代码来向读者解说我所了解的链表，期望我所讲的链表能都对你有所协助。接下来言归正传，开端咱们的链表之旅。
那么什么是链表呢?链表是一种物理存储单元上非接连、非次第的存储结构，数据元素的逻辑次第是经过链表中的指针链接次第完成的。链表由一系列结点组成，即链表中的每个元素，结点可以在运转时动态生成。每个结点均由两个部分所组成：一个是存储数据元素的数据域，另一个是存储相邻结点地址的指针域。比较于线性表次第结构，链表比较便利刺进和删去操作。
关于链表咱们可以将其分为单链表、双向链表和循环链表等。首要咱们先讲讲单链表。
所谓单链表，是指数据结点是单向摆放的。一个单链表结点，其结构类型分为两部分：
1、数据域：用来存储自身数据
2、指针域：用来存储下一个结点地址或许说指向其直接后继的指针。
如下图所示：
留意：假如有图中的赤色箭头部分，则变为了单向循环链表。
那什么又是双链表呢?双向链表其实是单链表的改进。当咱们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又有必要从表头开端查找。这是由单链表结点的结构所约束的。因为单链表每个结点只要一个存储直接后继结点地址的链域，那么能不能界说一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这便是双向链表。
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域;一个存储直接前驱结点地址，一般称之为左链域。
如下图所示：
留意：假如有图中的赤色箭头部分，则变为了双向循环链表。
看完了上面的介绍之后，我想读者关于链表算是有了一个大致的了解。那么接下来咱们的使命便是学习怎么运用链表，咱们从最简略的代码开端，教会读者来学习运用链表，首要咱们来看一个单链表的创立。为了便于解说，我在此就把一切的代码放到一个源文件中来执行了，当然读者在实践编写代码的过程中不论是为了保护仍是阅览都应该运用头文件，而不要在一个源文件中一条龙似地写究竟。
#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
看了上面的代码，假如读过我之前写的那篇《C言语的那些小秘密之断语》的读者就知道，在这段代码的赤色部分咱们运用了自己完成的断语，学以致用嘛，一切特此在这儿拿出来运用下，假如还没有看那篇文章的读者，我主张你看看，究竟断语仍是很有用的。代码的蓝色部分也算是一个特征点，因为曾经或许咱们在自己的代码中都是回来一些int型值或许NULL之类的，使得代码的回来值不可以直观的体现出运转成果，也使得代码的可读性比较差，一切为了改进咱们的代码，咱们要学习自己界说回来类型，做到尽或许的从各个方面去改进咱们编写的代码。在这儿咱们自己用枚举型的数据结构来界说了回来类型，因为代码的联系，我这儿只是运用了一个回来类型SLIST_RETURN_OK，依据自己代码的需求读者可以自己增加编写更多的回来值，我只是是在这儿举出一个比如。如：
typedef enum _SListReturn
{
SLIST_RETURN_OK,
SLIST_RETURN_STOP,
SLIST_RETURN_FAIL
}SListReturn;
现在咱们从以上代码中选出部分代码来加注释进行解说。
stud *p,*h,*s; /* *h保存表头结点的指针，*p指向当时结点的前一个结点，*s指向当时结点*/
h->link=NULL; /*把表头结点的链域置空*/
p=h; /*p指向表头结点*/
p->link=s; /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/
在代码中除了创立链表的函数外，咱们还运用了两个函数，一个是SListReturn print(stud* head)函数，经过该函数咱们打印输出链表中的数据。另一个函数是SListReturn destroy(stud* head)，经过该函数咱们对请求的链表空间进行开释。经过以上函数我想读者应该知道了怎么创立一个链表和处理链表中的数据，在这儿我只是是对数据做了打印操作，假如读者有爱好可以进行其他的操作。
以上代码完成了单链表的创立，可是链表的常用操作还有查找、刺进、删去等没有解说，删去操作与刺进操作相似，就不在这儿逐个解说了，在此咱们以查找和刺进为例进行解说，可是读者在编写删去操作的时分别忘了把删去的结点开释掉。接下来咱们就来看看一段查找和刺进的操作。
代码功能为在查找到的结点后边增加一个新的结点。
#include
#include
#include
#include
#define N 3 /*N为人数*/
//#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[20];
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; /*p指向表头结点*/
for(i=0;i
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("分配内存空间失利!");
exit(0);
}
p->link=s; /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/
printf("请输入第%d个人的名字:",i+1);
scanf("%s",s->name); /*名字*/
printf("请输入第%d个人的成果:",i+1);
scanf("%d",&s->score); /*分数*/
s->link=NULL;
p=s;
}
return(h);
}
stud * search(stud *h,char *x) /*查找函数*/
{
stud *p;
char *y;
p=h->link;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->link;
}
if(p==NULL)
printf("没有查找到该数据!");
}
SListReturn insert(stud *p) /*刺进函数，在指针p后刺进*/
{
char stu_name[20];
int stu_score;
stud *s; /*指针s是保存新结点地址的*/
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("分配内存空间失利!");
exit(0);
}
printf("请输入你要刺进的人的名字:");
scanf("%s",stu_name);
printf("请输入你要刺进的人的成果:");
scanf("%d",&stu_score);
strcpy(s->name,stu_name); /*把指针stuname所指向的数组元素复制给新结点的数据域*/
s->score=stu_score;
s->link=p->link; /*把新结点的链域指向本来p结点的后继结点*/
p->link=s; /*p结点的链域指向新结点*/
return SLIST_RETURN_OK;
}
SListReturn destroy(stud* head)
{
stud* tmp,*next;
tmp=head;
int i=0;
while(tmp!=NULL)
{
next=tmp->link;
tmp->link=NULL;
free(tmp);
tmp=next;
i++;
printf("第%d次开释\n",i);
}
return SLIST_RETURN_OK;
}
SListReturn print(stud* head)
{
stud* tmp=head->link;
while(tmp!=NULL)
{
printf("%s成果为%d\n",tmp->name,tmp->score);
tmp=tmp->link;
}
return SLIST_RETURN_OK;
}
void main()
{
int number; /*保存人数的变量*/
char fname[10]; /*保存输入的要查找的人的名字*/
stud *head,*searchpoint; /*head是保存单链表的表头结点地址的指针*/
number=N;
head=creat(number); /*把所新建的单链表表头地址赋给head*/
printf("请输入你要查找的人的名字:");
scanf("%s",fname);
searchpoint=search(head,fname); /*查找并回来查找到的结点指针*/
insert(searchpoint); /*调用刺进函数*/
print(head);
destroy(head);
//ASSERT_REPORT(print(head)==SLIST_RETURN_OK);
//ASSERT_REPORT(destroy(head)==SLIST_RETURN_OK);
}
运转成果为：
以防图片翻开失利，在此特别加上文字描述。
请输入第1个人的名字:rewq
请输入第1个人的成果:123
请输入第2个人的名字:fdsa
请输入第2个人的成果:456
请输入第3个人的名字:vcxz
请输入第3个人的成果:789
请输入你要查找的人的名字:fdsa
请输入你要刺进的人的名字:ghjk
请输入你要刺进的人的成果:369
rewq成果为123
fdsa成果为456
ghjk成果为369
vcxz成果为789
第1次开释
第2次开释
第3次开释
第4次开释
第5次开释
Press any key to continue
代码中的要害部分都加了注释来进行阐明，所以在此就不做逐个解说了，只说几个值得留意的当地，那便是destroy()函数的完成，或许有许多人对这儿的操作不是很了解，因为关于开释成功与否都没有可以直观的显示出来，就算写对了也仍是不太坚信，这个时分咱们就要自己来加点东西了。所以在此特别教读者一个办法，来进行简略的验证，经过i++;、 printf("第%d次开释\n",i);句子来完成打印开释了多少个结点，和咱们创立的结点数目进行比较即可，在本代码中咱们一开端创立了4个结点(留意：包含头结点)，之后又刺进了一个结点，所以总需求开释5个结点，看看打印的成果就知道咱们的函数完成正确了，当然还有许多验证的办法，在此仅是例举一个简略的办法。
总不能没玩没了的写下去吧，所以暂时到此为止，到下一篇博客咱们接着讲。因为自己水平有限，博客中的不当或过错之处在所难免，殷切期望读者批评指正。一起也欢迎读者一起讨论相关的内容，假如愿意沟通的话请留下你名贵的定见。
linux操作系统文章专题：linux操作系统详解（linux不再难明）
