C语言链表之单链表

C语言链表之单链表

目录

1.什么是链表

 2.结点的组成

3.结点是如何连接成链表的

4.结点

 5.静态链表实现:

1）.创建结点：

 2）.链接结点：

3）.看一下连接前和连接后的效果：

4）.用调试让大家更容易理解一下：

 6.动态链表实现

1）.创建结点

2）.头插法 

3）.遍历链表

 4).尾插法

5）.查找结点

6）.中间插入

7）.删除结点

a.删除头结点

b. 结点在中间

c.删除的结点在链表之外

 PS

---

---

1.什么是链表

链表是由一个个结点链接而成的，它和数组有一点相似，但和数组又有不同数组的内存段是连续的，而链表的内存段是一段一段的，不连续的

 

 2.结点的组成

结点分为两个部分：数据域和指针域

 数据域用来存放数据，指针域用来指向下一个数据域的地址

3.结点是如何连接成链表的

我们先来创建四个结点，如图

 这是四个结点，下面来看一下它们是如何连接的：

原本这四个结点的指针域都是指向NULL的，这是为了防止指针成为野指针，如图：

 当它们连接成链表的时候，除了最后一个结点的指针继续指向NULL外，前面的三个的指针将不在指向NULL，而是指向下一个结点的数据域的地址，如图：

最后就变成了这样：

4.结点

上面提到了静态链表，除了静态链表还有动态链表，然而不论是静态链表还是动态链表，都需要结点，代码如下：

 5.静态链表实现: 1）.创建结点：

 2）.链接结点：

 这三个图可以和  “3.结点是如何连接成链表的” 一起看

3）.看一下连接前和连接后的效果：

4）.用调试让大家更容易理解一下：

第一次：（箭头到哪，程序运行到哪一行，但还未运行此行）此时N1的指针域和N2的数据域还没有连接到一起

 第二次：此时可以从图中看出N1的指针域和N2的数据域已经连接到一起了，下同

 第三次：

第四次：

 本人嫌静态链表太麻烦，所以静态链表到此结束，下面讲一下动态链表

 6.动态链表实现 1）.创建结点

声明：

 定义：

main函数里：

 创建结点的时候需要数据，所以需要往函数里传一个date（数据）

2）.头插法 

声明：

 定义：

 

 在画图理解一下：

原链表:

现在我们需要插入一个新的结点，让它成为表头，也就是第一个结点，现在我们需要县创建一个新的结点，让新的结点指向老链表，在让我们创建的list成为新的结点

main（）函数：

3）.遍历链表

 为了看一下功能是否实现，先实现一下遍历功能

声明：

 定义：

 看一下头插法是否实现:

 4).尾插法

最后在实现中间插入，先实现一下尾插

声明：

定义：

画图理解一下：

老链表：

 现在我们需要找到最后一个结点，因为只有最后一个结点的指针域指向NULL，所以只需找到当NewNode->next == NULL的情况

过程如下：

现在看一下效果：

5）.查找结点

在我们实现插入第N个点的时候，我们需要先找的到第N-1个结点

先画图看一下为什么插入第N个结点，我们需要找到第N-1个 结点

下面是四个结点：

接下来我们需要做的是先创建一个结点，假如我们需要这个新建的结点成为第3个结点，那我们是不是要把它插入的第二个的后面

那么第二步我们需要做的是让这个新结点的指针域指向原链表的第三个结点

  

 然后让第二个结点的指针域指向新结点，如此，目标完成。但是这里有一个前提，我们需要先找到第二个结点，所以先实现一下查找功能

声明：

定义：

6）.中间插入

中间插入已经在“5）.查找结点” 里讲过了，这里不再过多叙述

声明：

定义：

 接下来看一下效果：

7）.删除结点

 先画图看一下怎么实现删除功能

假如我们要删除第三个结点，我们需要这样做：

删除结点有四种情况

a.删除头结点

原本的表头在这个位置

如果我们想删除第一个结点，让表头指向第二个结点就行，直接让表头等于DNord->next（代码里有）就行 

代码如下：

 main函数里：

 效果：

b. 结点在中间

直接NewNode->next = NewNode->next->next

代码如下：

main函数里：

效果：

c.删除的结点在链表之外

代码：

 main函数：

 效果：

 删除节点这段代码有点调整，但不大

声明：

定义：

 main函数：

效果：

 

 PS

笔者也是才学会，若有不足，请各位大佬指教，第一次正式的写博客，有点啰嗦，见谅

静态代码

#include

//结点
struct Node
{
	int date;				//数据域
	struct Node* next;		//指针域   创造一个指向struct Node*类型的指针
};
int main()
{
	//第一种方法：静态链表
	struct Node N1 = { 1,NULL };//让指针域指向NULL，防止struct Node* next成为野指针
	struct Node N2 = { 2,NULL };
	struct Node N3 = { 3,NULL };
	struct Node N4 = { 4,NULL };
	//把上面这些结点链接起来就是一个静态链表
	//链接方式：
	struct Node* FrontNode = &N1;
	printf("链接前：n");
	while (FrontNode)
	{
		printf("%dn", FrontNode->date);
		FrontNode = FrontNode->next;
	}
	N1.next = &N2.date;
	N2.next = &N3.date;
	N3.next = &N4.date;
	struct Node* AfterNode = &N1;
	printf("链接后：n");
	while (AfterNode)
	{
		printf("%dn", AfterNode->date);
		AfterNode = AfterNode->next;
	}
	return 0;
}

动态代码：

#include
#include

//结点
struct Node
{
	int date;				//数据域
	struct Node* next;		//指针域   创造一个指向struct Node*类型的指针
};
//创建结点
struct Node* CreateNode(int);//创建一个struct Node*类型的函数
//头插法
void HeardNode(int, struct Node**);//因为我们会对头指针进行 *** 作，所以我们需要用二级指针
//遍历链表
void Traver(struct Node*);
//尾插法
void TrailNode(int, struct Node**);
//查找
struct Node* FindNode(int, struct Node*);//int是我们需要告诉这个函数我们想找到第几个节点
//这里为什么使用struct Node*类型，是因为我们需要返回struct Node*类型的值
//中间插入
void MiddleNord(int, struct Node**, int);//这里的两个int，一个用来传递数据，一个用来传递n
//删除结点
void DelNord(int, struct Nord**, int);//这里的两个int，一个用来传递数据，一个用来传递n
int main()
{
	struct Node* list = NULL;//链表
	Traver(list);
	for (int i = 9; i >= 0; i--)
	{
		HeardNode(i, &list);
	}
	Traver(list);
	for (int i = 10; 9 < i && i < 20; i++)
	{
		TrailNode(i, &list);
	}
	Traver(list);
	for (int i = 9; i >= 0; i--)
	{
		MiddleNord(1, &list, 3);
	}
	Traver(list);
	for (int i = 9; i >= 0; i--)
	{
		DelNord(1, &list, 3);
	}
	Traver(list);
	DelNord(1, &list, 1);
	Traver(list);
	DelNord(1, &list, 20);
	Traver(list);
	return 0;
}
//创建结点
struct Node* CreateNode(date)
{
	struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));
	//使用malloc函数分配内存，用sizeof获得struct Node所需要的内存
	//malloc函数的返回值是void*类型，所以用(struct Node*)将其转换
	//成struct Node*类型
	if (NewNode == NULL)
	{
		printf("申请内存失败n");
		return NULL;
	}
	else
	{
		//成员赋值
		NewNode->date = date;
		NewNode->next = NULL;//让NewNode->next指向NULL，防止它成为野指针
		return NewNode;
	}
}
//头插法
void HeardNode(int date, struct Node** list)
{
	if (*list == NULL)//若链表为空
	{
		*list = CreateNode(date);
	}
	else//若链表不为空
	{
		//创建一个新结点，让新结点的下一个指向老链表，在让*list成为表头
		struct Node* NewNode = CreateNode(date);
		NewNode->next = *list;
		*list = NewNode;
	}
}
//遍历链表
void Traver(struct Node* list)
{
	printf("list:(链表)n");
	while (list)
	{
		printf("%d   ", list->date);
		list = list->next;
	}
	printf("n");
}
//尾插法
void TrailNode(int date, struct Node** list)
{
	if (*list == NULL)//链表为空
	{
		HeardNode(date, *list);
	}
	else//链表不为空
	{
		//拷贝一下链表
		struct Node* NewNode = *list;
		//寻找最后一个结点，因为只有最后一个结点的指针域指向空，所以找NewNode->next是否为空，若为空，则找到
		while (NewNode->next)
		{
			NewNode = NewNode->next;
		}
		NewNode->next = CreateNode(date);//最后一个NewNode->next指向新建的结点，成功
	}
}
//查找
struct Node* FindNode(int n, struct Node* list)
{
	int count = 1;
	while (1)
	{
		if (list == NULL) return NULL;
		if (count == n - 1) return list;
		list = list->next;
		count++;
	}
}
//中间插入
void MiddleNord(int date, struct Node** list, int n)
{
	if (list == NULL || *list == NULL) return;//防止是空链表
	if (n == 1)
	{
		HeardNode(date, list);
		return;
	}
	struct Node* Find = FindNode(n, *list);//接收一下找到的结点
	if (Find == NULL)//如果是NULL，直接尾插法
	{
		TrailNode(date, list);
	}
	else
	{
		struct Node* NewNord = CreateNode(date);//创建一个新结点
		NewNord->next = Find->next;//新结点指向我们找到的结点的下一个
		Find->next = NewNord;//找到的那一个结点在指向新创建的结点
	}
}
//删除结点
void DelNord(int date, struct Node** list, int n)
{
	if (list == 0 || *list == 0) return;
	struct Node* NewNode = FindNode(n, *list);
	if (n == 1)
	{
		struct Node* DNord = *list;
		*list = DNord->next;
	}
	else if (NewNode->next == NULL)
	{
		return;
	}
	else
	{
		
		NewNode->next = NewNode->next->next;
	}
}