一看就懂-c语言单向链表【初阶】

一看就懂-c语言单向链表【初阶】

目录

0.引言

1.为什么需要链表？

2.链表概念的渗透

3.开始制作链表

3.1定义大结构

3.2定义出我们的head（第一个大结构）

3.3开始制作节点

3.4节点的传递

4.链表的打印

 5.总结

---

0.引言

相信很多人在初学c语言时，第一次接触链表会感到像博主一样的茫然失措。在一次又一次的debug，调试记录链表地址的变化后，发现了链表的实质！此文就来分享一下我对于单向链表的理解与感悟。

1.为什么需要链表？

链表作为数据结构的一种类型，它的好处是非常多的。博主就先分享一些简单的例子：当我们想去记录一组数据的时候，我们自然而然的会想到用数组去记录。但是数组在用于记录之前要进行数组大小的初始化，当数组大小不足以满足你想要储存的数据数量时，自然就会存在越界的问题。那么这个时候用一个链表的结构，就能够满足我们想用多少就能同时创造多少空间的需求，更加灵活方便。  

注：处理这个问题我们当然还可以选择使用可变数组，但是可变数组相对于链表还是有一定的局限性，二者的对比我将在后续的博文中与大家分享我的理解与想法。【期待您的关注与点赞】

2.链表概念的渗透

我们知道数组是一个连续的内存空间，那么既然我在前面说了链表可以比数组更加优化，不用当心越界的问题，那么这期博文我们就来制作一个具有数组功能的链表。既然我们要做一个类似于数组的东西，就至少要知道数组计数的大概模型。见下图：

 我们看到数组的内存空间是连续的，那么知道上一个地址的元素就能调出下一个地址的元素，知道下一个地址的元素就能调出上一个地址的元素，这是连续连锁的关系。那么本文先来考虑单向链表，就只让它往一个方向连续就行【双向链表见后续博文，期待您的关注与点赞】，由图见链表的初始模型，我们从一个元素到另一个元素，是拥有一个箭头的指向，而不是地址的紧挨着的连续，这样便更加灵活！我们知道数组从某种意义上而言就如同指针，那么指针的一个关键作用就在于地址的可移动性【了解指针可以点击我的主页看《浅入c语言指针剖析》，用房子和住户的例子来理解指针概念】，这么说来我们制作链表就自然而然需要指针！ok，那我们做链表的方向就很清楚了，我们对于每一个空间【房子】，需要两个东西：1.写入的值 2.指向下一个空间的箭头。那么如何让一个整体包含两种类型变量？--->当然是结构了！定义一个结构包含一个被写入的值，同时包含指向下一个结构的箭头【也就是后面用的指针了】   

完整的链表原理图如下：

3.开始制作链表 3.1定义大结构

 从上图我们可以看出，一个结构里面被分为两块，一个存入数据，一个指向下一个结构，那么首先我们就要先来创建结构。

#include
#include
typedef struct node_{
	int value;
	struct node_ *next;	
}node;

这里我们定义的结构类型成为node，其中包含了int value（存入的值）一个是struct node_ *next 这个指针就是箭头，用于指向下一个大结构（或者称它本身就是下一个大结构，后面会详细叙述） 其中有一个细节就是，为什么里面要用struct node_ 而不直接用node呢？因为编译器在此处还没有获取让node代替struct node_的信息，后面我们在主函数中会用node代替所有的struct node_ 

3.2定义出我们的head（第一个大结构）

在前面的链表结构原理图中，我们看到整个链表又是由head（头），节点，tail（尾巴）三大部分组成，我们先来说一说我们为什么需要这个head（头）。我们在实现链表的过程中，一开始都是随便定义一个大结构：node *p。然后让p->value=number（将你写入的值储存进入这个节点中！！），头和尾巴其实也是一个节点，但是它为什么特殊叫做head（头），是因为它要作为整个链表的起点，一旦第一个节点成为了头，那么这个头就永远不能改变，因为之后我们需要通过这个头去调用后面一个又一个的节点！他就是我们链表的源头，可以把它当作数组中的a[0]来看待，当你知道了这个头，后面的元素就全部都知道了。因为头的结构中有一个指针箭头，指针箭头的指向的结构里面又有一个指针箭头去指向下一个结构，这样一直会持续到尾巴。

int main()
{
	node *head=NULL;
	int number;
	printf("please input the numbers!n");

定义了head 并且把整个结构初始化为NULL

int number；number用来作为每一次你想储存的那个数字！

3.3开始制作节点

do{
		scanf("%d",&number);
		if(number!=-1)
		{
			node *p;
			p=(node*)malloc(sizeof(node));
			p->value=number;
			p->next=NULL;

接下来的所有事情我们都在一个do-while循环中进行，每一次输入一个不是-1的值来进行记录储存，输入-1代表退出储存数据，只要内存够用就不会越界！这里的node *p就是随机定义的一个节点，同时我们需要给这个结构动态内存分配一个位置出来所以用malloc（），前面头文件也用了#include .从此也可以看出，每次do循环过后就会重新分配一个随机的空间，而不是像数组一样紧紧挨着的连续空间。所以一定要在定义node *p后面给他分配内存，不然每一次都在同一个node *p结构中不断覆盖赋值！【为了更好的了解，你可以在最后整个代码中试着把malloc除去看看运行后的区别！】同时我们要让p->next=NULL，因为如果接下来不继续赋值了，这个p节点将成为tail（尾巴）。尾巴是最后在打印时判断是否结束的标志！

3.4节点的传递

node *list=head;
			if(list！=NULL)
			{
				while(list->next！=NULL)
				{
					list=list->next;
				}
				list->next=p;
			}else{
				head=p;
			}	
		}
	}while(number!=-1);

这个怎么又出来个node *list，这个定义出来的名为list的结构有什么作用呢？我们来一行一行的解释：我们之前说了，head一旦初始化是不能随便乱改变的，所以这里我们就需要一个head的“替身”来做后面的事情。所以每一次循环定义出来的node *list=head。这样list就成为了假的head，但是却又能够帮head完成节点的传递，也就是指针箭头的不断往后面指向！但是我们之前说了head也是一个节点，还是要有一个初始值的，也就是说第一次循环的node *p要给head，head是第一个节点！所以这里用了一个if-else语句，如果list（此时也就是head

）为NULL，那么就进入else语句，让head=p；head就被赋予了第一个节点的结构。被赋值后的head就不可能为0了，那么就会进入if里面的语句。然后我们会发现马上又紧接着一个while循环，这个循环是拿来干什么的呢？我们发现循环的条件是list->next不等于NULL，我们什么时候一个结构的->next会是NULL呢？tail（尾巴）！ 当我们已经每一次循环的结束，我们都会存在一个尾巴，因为每一个节点都让p->next=NULL；所以当我们进行到这一步的时候，说明我们不会让前面的那个节点作为尾巴，而是继续让这个尾巴的NULL 指针去指向新的结构，所以当list->next=NULL，找到了上一个节点的尾巴时，让这个尾巴去指向这次循环定义的新的节点node *p； 所以就有了list->next=p；所以这里list是在时刻发生改变的，而head是在第一次赋值之后就一直保持不变，但是head后面的内容（这里的内容就是被创造出来的一个又一个节点）却又因为list而逐渐充实！  

注：这里有一个细节就是，node *head在循环的外面，也是为了保证head的绝对安全，而不会在每一次循环过后因为某种因素而发生改变【链表的核心就是保证head的安全，后续博文所补充的链表的打印，删除，清空，查找都是在head的基础上进行的】

为了更好的理解list 和 p的关系，看下图：

图中只展现了两次过程，后面的过程以此类推，原理就是每次都要从头开始一直找到上一次的那个尾巴中的空指针，让空指针指向本轮循环创造的那个节点p。最后输入-1退出循环后，这就是一个完整的链表了 （有head（头），中间节点，tail（尾巴））

4.链表的打印

node *d;
	for(d=head;d;d=d->next)
	{
		printf("%d ",d->value);
	}
	return 0;
}

这里就是随意定义一个结构node *d，在for循环中让d从头开始打印，d=head；然后每一次循环过后让d=d->next，目的就是进入下一个节点，一直到tail（尾巴），也就是d->nex=NULL,d也就等于NULL，就退出for循环了！

效果展示图：

本文代码整合：

#include
#include
typedef struct node_{
	int value;
	struct node_ *next;	
}node;
int main()
{
	node *head=NULL;
	int number;
	printf("please input the numbers!n");
	do{
		scanf("%d",&number);
		if(number!=-1)
		{
			node *p;
			p=(node*)malloc(sizeof(node));
			p->value=number;
			p->next=NULL;
			
			node *list=head;
			if(list)
			{
				while(list->next)
				{
					list=list->next;
				}
				list->next=p;
			}else{
				head=p;
			}	
		}
	}while(number!=-1);
	node *d;
	for(d=head;d;d=d->next)
	{
		printf("%d ",d->value);
	}
	return 0;
}

 5.总结

本次文章制作了一个最简单的，能够代替数组的链表的实现，后续博文我会在本篇文章的基础上，分享如何进行链表的查找，删除，替换，清空，以及双向链表，循环链表的分享。如果看到这里的你觉得这篇文章对您有帮助的话，不妨高抬贵手点个关注点个赞。同时也期待大佬的批评指正！