笔者作为一名C语言的初学者,在刚接触链表时,几乎找不到教程能用很通俗易懂的语言去讲解链表。大多数时候找到的关于链表的教程,或许是生硬的塞给读者一大段代码,或许是使用了一些过于专业的词汇,对于萌新非常地不友好。这就是我写这篇教程的原因。




好吧,即使这篇教程会相对简单,但是在阅读之前,读者还是需要首先简单了解结构体部分和指针部分的内容。



好,那我们就开始吧。

首先通俗地解释一下:链表是一种特殊的结构体,创建链表只需要下面这些代码:

struct node { int num; struct node *next; };
到此为止,你就成功建立了一个链表。

 

我们来详细分析一下:首先我们使用了创建结构体的标准格式,创建了一个struct node,
struct node有两个成员(int, struct node),在这个结构中,int类型非常的平淡无奇,而struct
node本来是我们定义的结构体,但是在结构体里面的成员里再次出现(这时很多教程就会告诉你这是C语言里先使用后定义的特例云云,但我们不管),并且定义了一个指针变量,根据我们对指针的了解,某一类型的指针指向相同类型的数据(void是空指针,int型指针指向整形变量,char型指针指向字符型变量),那么struct
node型指针就指向struct node型结构,我们先看一个图了解一下:





那么这个特殊的指针是怎么运作呢?

 

这个特殊的指针,指向另一个结构,而这个结构同样拥有一个指向其他结构的指针,就构成了这样一个关系:






循环下去,就会产生一条“链”,链表分为单向链表
<https://baike.baidu.com/item/%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8>,双向链表
<https://baike.baidu.com/item/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8>以及循环链表
<https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8>
,大家可以自行去了解不同种类的链表,这里我们以单向链表为例子,分析一下对链表的操作。(请先行了解malloc函数的作用,它是必不可少的)
#include <stdio.h> #include <stdlib.h> struct node { int num; struct node
*next; }; int main() { struct node *head; //声明表头head(链表开始的位置) head=NULL;
//建一个空表 struct node *p1,*p2; int i=1; //利用malloc()申请分配节点(也就是一个地址) p1=p2=(struct
node*)malloc(sizeof(struct node)); //新节点 printf("请输入值,值小于等于0结束,值存放地址为:p1_ADDR=
%d\n",p1); scanf("%d",&p1->num); p1->no=i; p1->next=NULL; while(p1->num>0)
//输入的节点数值大于0 { if(head==NULL) head=p1; //空表,接入表头 else p2->next=p1; //非空表,接到表尾
p2=p1; p1=(struct node*)malloc(sizeof(struct node)); //下一个新节点 i=i+1;
printf("请输入值,值小于等于0结束,值存放地址为:p%d_ADDR= %d\n",i,p2);
scanf("%d",&p1->num);//输入节点的值 p1->no=i; //判断一下是否有后续节点要接入链表,若无则结束; } free(p1);
//申请到的没录入,所以释放掉 p1=NULL; //使指向空 p2->next = NULL; //到表尾了,指向空
printf("链表输入结束(END)\n"); getchar(); return 0; }



这段程序执行完毕后,我们得到了链表表头head,但是其余空间都是系统分配的,我们并不能直接找到对应的变量。但是这就是单向链表的神奇之处,只要知道表头,就可以一步一步摸到表尾。不过在此之前,我们要先理清思路。






首先,head->next代表什么?

它既是首个结构的一个成员,也是第二个结构的地址。

那么,head->next->next又是什么呢?

它既是第二个结构的一个成员,也是第三个结构的地址。

 


所以,我们可以在代表结束的getchar();语句之前插入printf(“%d”,head->next->next->num);试一试,你会发现,如果你的节点达到了三个或更多的话,这条语句能够精准地输出第三个结构里num的值。

 

现在想一想,怎么将刚刚创建的单向链表所有的节点反向?

反向也就是将所有结构中的指针成员从指向下一个结构改为指向上一个结构。



想好了吗?我们开始了哦。

 

我们首先从表头开始操作,创建三个struct
node型指针x1,x2,temp作为暂存器(为什么是三个呢?想想我们在学习交换a,b两个变量的值时,是c=a;a=b;b=c;这个样子的)。

先保存好head->next->next指向的地址 x1=head->next->next;

然后把x1放一边儿凉快去。

再保存第二个结构的地址 x2=head->next;

之后让第二个结构里的成员next指向首个结构 head->next=head;

再然后令表头指向空 head=NULL;

 

第一步反向就完成了,那么接下来再完成第二步。

还记得我们之前使用的x1和x2吗?马上就能派上用场了。

因为head指向了NULL,故head已经不复存在,但我们还有temp。

先把x1的值留住 temp=x1;

而x1再往后移动一次x1=x1->next;    //这里将x1->next看作下一结构

此时x1就又可以放在一边儿凉快了。(x1:”嘤嘤嘤”)

我们的目的是让第三个结构里的指针成员指向第二个结构,找找我们在第一步里做了什么。

 

第二个结构的地址被保存在x2中,第三个结构的地址被保存在了temp中

temp->next=x2;   //这里将temp->next看作成员

这样就又完成了一次逆向,不过还没结束这一步,因为这是循环操作,要保持语句一致性。

所以我们还要将x2向后移动一次x2=temp;

 

后面每一步的操作,都和第二步类似,但是,循环结束是什么时候呢?

由于x1每次只是单纯后移,几乎没有操作,那么,后移之后的x1里的next是不是空指针(NULL)就成了关键。
if(x1->next==NULL) { temp->next=x2; x1->next=temp; head=x1; break; }

此时,表头地址再次存入了head,不过单向链表已经反向(这个教程是有陷阱的,如果链表比较短,在x1=head->next->next;时就会崩溃,想想怎么解决吧)。

 

现在,您已经可以去阅读其他的教程,更加详细地研究链表。

 


如果您在这篇文章中发现问题,欢迎随时提出宝贵的意见,我将不甚感激,作为一名初学者,对于很多专业的知识不了解,也因此避免了使用难以理解的专业词汇进行讲解,如有错误,请以标准文档为准。