【咖喱味的数据结构系列】——单链表尾插法（深入浅出从内存四区详细解读）

前言：大家好，我是北豼不太皮，话不多说上干货，我们先把链表的先展开讲，后面的再慢慢补充

不知道看完的你有没有想和我一起学的冲动呢，这就是咖喱味的数据结构系列的所有内容，看上的话赶紧加入学习吧，先三连收藏起来，不然下次就找不到了
最近刚写完C语言系列，现在也在学数据结构，接下来给大家带来咖喱味的数据结构系列，为什么叫咖喱味的数据结构系列呢，因为这个系列是跟着b站的一个带着印度口音英语的视频来学习的，声音很搞笑，讲的思路也很清晰。

传送门：b站视频印度顶级程序员
视频虽然好，但配合博文的讲解学习更佳哦
如果对动态内存那方面不太懂，也没关系，传送门：b站视频印度顶级程序员C指针
如果C语言基础比较薄弱可以看一下我的C语言专栏
最后给大家推荐几本比较好的学习C语言的书
《大话C语言》这一本书适合新手看，讲的非常简单易懂
看完《大话C语言》就可以看C语言三剑客
《C与指针》《C陷阱于缺陷》《C专家编程》
学过的内容不在于多而在于精，下面就让我们来详细理解一下怎样从链表的尾部插入一个新节点,只要理解了一种方法，后面的单链表就会触类旁通了
大家学完之后最好自己动动手敲一下代码，自己画一下图，这样印象就会更深刻

单链表尾插法

• 
  

  一、当头指针在主函数里是局部变量

• • 1.尾部插入一个节点
  • • （1）尾部插入一个节点逻辑视图
    • （2）尾部插入一个节点代码实现
    • （3）在内存里面的变化
  • 2.遍历单链表
  • • （1）遍历单链表逻辑视图
    • （2）遍历单链表代码实现
    • （3）在内存里面的变化
  • 3.总体代码
• 
  

  二、当头指针是全局变量

• • 1.尾部插入一个节点
  • • （1）尾部插入一个节点代码实现
    • （2）在内存里面的变化
  • 2.遍历单链表
  • • （1）遍历单链表代码实现
    • （2）在内存里面的变化
  • 3.总体代码

一、当头指针在主函数里是局部变量 1.尾部插入一个节点 （1）尾部插入一个节点逻辑视图

先来简单看一下尾插法的逻辑视图，先简单了解一下新节点是怎样尾插到链表上的
当链表为空时，就让temp插到head后面，一个新节点就插到链表尾部了
当链表不为空时，我们用一个局部变量的临时指针temp1指向head指向的地址，然后对temp1->next进行判断是否为空，如果不为空temp1 = temp1->next，让temp1移到下一个节点，直到temp1->next为空，temp1移到了链表尾部，让temp1->next = temp，把新节点temp插入到链表的尾部

插入第一二个节点

插入第三个节点

最后的链表

（2）尾部插入一个节点代码实现

尾部插入一个节点，需要把主函数头指针head的地址传过来，这样Inser函数可以通过*head改变main函数的head

（3）在内存里面的变化

首先main函数执行在栈上有一个新的栈帧，在这个栈帧上定义头指针head赋值为空（NULL），定义n，i，x，然后Insert函数执行，又在栈上有一个新的栈帧，定义了（二级指针）head，x，temp，temp1，main函数把head指针的地址传递给了Insert函数head（二级指针），通过解引用Insert函数的head指针，就可以访问并修改main函数的head,temp在堆开辟了新的空间，里面有data和next两个成员，data放着x的值，next赋值为空（NULL），然后判断*head的值（即访问到了main函数的head）是否为空（判断链表是否为空），这时 *head的值为空，就让*head = temp让main函数的head指向在堆新开辟节点的内存地址，然后Insert函数就完成了一次新节点的插入

Insert函数结束，Insert函数的栈帧就释放了

在刚才的基础上我们在新加第二个节点，首先Insert函数执行，又在栈上有一个新的栈帧，定义了（二级指针）head，x，temp，temp1，main函数把head指针的地址传递给了Insert函数head（二级指针），通过解引用Insert函数的head指针，就可以访问并修改main函数的head,temp在堆开辟了新的空间，里面有data和next两个成员，data放着x的值，next赋值为空（NULL），然后判断*head的值（即访问到了main函数的head）是否为空（判断链表是否为空），这时*head的值不为空，则执行temp1 = *head，让temp1指向*head指向的堆地址，然后判断temp1->next是否为空，这时temp1->next为空，则执行temp1->next = temp，让新的节点插入到链表尾部，然后Insert函数就完成了一次新节点的插入

Insert函数结束，Insert函数的栈帧就释放了

在这个基础上我们再新加上第三个节点,首先Insert函数执行，又在栈上有一个新的栈帧，定义了（二级指针）head，x，temp，temp1，main函数把head指针的地址传递给了Insert函数head（二级指针），通过解引用Insert函数的head指针，就可以访问并修改main函数的head,temp在堆开辟了新的空间，里面有data和next两个成员，data放着x的值，next赋值为空（NULL），然后判断*head的值（即访问到了main函数的head）是否为空（判断链表是否为空），这时*head的值不为空，则执行temp1 = *head，让temp1指向*head指向的堆地址，然后判断temp1->next是否为空，这时temp1->next不为空，temp1 = temp1->next，让temp1移到下一个节点，直到temp1->next为空，temp1移到了链表尾部，让temp1->next = temp，把新节点temp插入到链表的尾部

Insert函数结束，Insert函数的栈帧就释放了

2.遍历单链表 （1）遍历单链表逻辑视图

（2）遍历单链表代码实现

遍历的话，只需要把指针传递过来，并不会影响主函数的头指针

（3）在内存里面的变化

这里就不详细讲了，只接上图，下面会有详细的讲解

遍历一个节点

Print函数结束，Print函数的栈帧就释放了

遍历两个节点

Print函数结束，Print函数的栈帧就释放了

遍历三个节点

Print函数结束，Print函数的栈帧就释放了

3.总体代码

#include 
#include 

struct Node
{
	int data;
	struct Node *next;
};

void Insert(struct Node **head,int x);
void Print(struct Node *head);

int main()
{
	struct Node * head = NULL;
	printf("How many numbers?\n");
	int n,i,x;
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		printf("Enter the number\n");
		scanf("%d",&x);
		Insert(&head,x);
		Print(head);
	}
}

void Insert(struct Node **head,int x)
{
	struct Node *temp1;
	struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = x;
	temp->next = NULL;
	if(*head == NULL)
		*head = temp;
	else
	{
		temp1 = *head;
		while(temp1->next != NULL)
		{
			temp1 = temp1->next;
		}
		temp1->next = temp;
	}
}

void Print(struct Node *head)
{
	printf("List is:");
	while(head != NULL)
	{
		printf(" %d",head->data);
		head = head->next;
	}
	printf("\n");
}

二、当头指针是全局变量

当头指针是全局变量与当头指针在主函数里是局部变量这两种情况有什么区别呢
逻辑视图的思路是一样的没有改变
只是代码有所改变，还有在内存的动态变化也有所区别

1.尾部插入一个节点

下面以n为3举例，输入三个数，创建三个节点

（1）尾部插入一个节点代码实现

（2）在内存里面的变化

首先我们要知道一些知识点，这些对下面的理解非常重要
全局变量所占的内存是在静态区，在程序结束后才会释放，可以在所有函数的任何地方访问
而局部非静态变量所占的内存在函数结束后就会释放，局部非静态变量无法在任何地方访问，除非通过指针访问
而由内存分配函数在堆内存开辟的空间要程序员释放才能释放，否则就会一直存在，直到程序结束

从尾部插入一个新节点，我们来看一下内存是怎么变化的
首先定义全局变量head(头指针)，然后再主函数将其赋值（NULL）为空这是在静态区完成的
然后在主函数定义n,i,x在栈上开辟空间
然后从键盘输入一个值（x的值），把主函数x的值传递给Insert函数
Insert函数又在栈开辟了一个新的空间，定义了x,temp1,temp,这里的x与主函数的值是一样的，但是内存地址却不一样，然后temp又在堆里开辟了一个新空间，里面有data和next两个成员，data放着x的值，next赋值（NULL）为空
然后判断head是否为空，刚开始head是空的，让head = temp,让head指向temp指向的堆内存地址（即指向新节点）
然后Insert函数就完成了一次新节点的插入
Insert函数结束，Insert函数里面的局部变量的内存就释放了

Insert函数运行结束后

在刚才的基础上我们再新加上第二个节点
首先Insert函数重新在栈上开辟了空间，定义了x,temp1,temp
然后在主函数定义n,i,x在栈上开辟空间
然后从键盘输入一个值（x的值），把主函数x的值传递给Insert函数
Insert函数又在栈开辟了一个新的空间，定义了x,temp1,temp,这里的x与主函数的值是一样的，但是内存地址却不一样，然后temp又在堆里开辟了一个新空间，里面有data和next两个成员，data放着x的值，next赋值（NULL）为空
判断头指针是否为空，这时头指针是不为空的，就让temp1指向了头指针指向的地址，为了确定temp1是否指向链表的尾部，我们判断temp1->next是否为空（NULL）来判断temp1是否在链表的尾部，经过判断这时temp1正好在链表的尾部，就让temp1->next = temp把新节点接到链表尾部
然后Insert函数就完成了第二次新节点的插入
Insert函数结束，Insert函数里面的局部变量的内存就释放了

Insert函数运行结束后

在之前的基础上我们再加第三个新的节点
首先Insert函数重新在栈上开辟了空间，定义了x,temp1,temp
然后在主函数定义n,i,x在栈上开辟空间
然后从键盘输入一个值（x的值），把主函数x的值传递给Insert函数
Insert函数又在栈开辟了一个新的空间，定义了x,temp1,temp,这里的x与主函数的值是一样的，但是内存地址却不一样，然后temp又在堆里开辟了一个新空间，里面有data和next两个成员，data放着x的值，next赋值（NULL）为空
然后让temp1指向了头指针指向的地址，为了确定temp1是否指向链表的尾部，我们判断temp1->next是否为空（NULL）来判断temp1是否在链表的尾部
如果temp1->next不为空，就让temp1 = temp1->next,让temp1指向下一个节点直到temp1->next为空时，就到了链表的尾节点，然后把temp1->next = temp，把新节点接到链表尾部
然后Insert函数就完成了第二次新节点的插入
Insert函数结束，Insert函数里面的局部变量的内存就释放了

Insert函数运行结束后

2.遍历单链表 （1）遍历单链表代码实现

（2）在内存里面的变化

遍历一个节点的时候，temp = head让temp指向头指针的内存地址，然后判断temp是否为空，如果不为空输出data，temp = temp->next，让temp指向下一个节点，直到temp为空就到链表尾部了，Print函数就结束了

Print函数就结束后

遍历两个节点的时候，temp = head让temp指向头指针的内存地址，然后判断temp是否为空，如果不为空输出data，temp = temp->next，让temp指向下一个节点，直到temp为空就到链表尾部了，Print函数就结束了

Print函数就结束后

遍历三个节点的时候，temp = head让temp指向头指针的内存地址，然后判断temp是否为空，如果不为空输出data，temp = temp->next，让temp指向下一个节点，直到temp为空就到链表尾部了，Print函数就结束了

Print函数就结束后

3.总体代码

#include 
#include 

struct Node
{
	int data;
	struct Node *next;
};

struct Node * head;
void Insert(int x);
void Print();

int main()
{
	head = NULL;
	printf("How many numbers?\n");
	int n,i,x;
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		printf("Enter the number\n");
		scanf("%d",&x);
		Insert(x);
		Print();
	}
}

void Insert(int x)
{
	struct Node *temp1;
	struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = x;
	temp->next = NULL;
	if(head == NULL)
		head = temp;
	else
	{
		temp1 = head;
		while(temp1->next != NULL)
		{
			temp1 = temp1->next;
		}
		temp1->next = temp;
	}
}

void Print()
{
	struct Node *temp = head;
	printf("List is:");
	while(temp != NULL)
	{
		printf(" %d",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

最后再提一个问题，这也是我还有疑惑的地方，这是头指针是全局变量的情况

将上面的代码改成下面的就运行不成功这是为什么呢

下期预告：【咖喱味的数据结构系列】——单链表头插法（深入浅出从内存四区详细解读）