[数据结构与算法]单链表的操作（基本操作和一些复杂操作）

💦单链表的操作

头文件

#include<stdio.h>
#include<stdlib.h>

提前说明 lenth是表长，不包括头节点。

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

💧头插入和删除

在这篇博客 头插入和删除 中有详细介绍这里我就不再赘述。

介绍另一种创建

💧尾插法创建单链表

尾插法：每次在链表的末尾新添一个节点。既然要在末尾添加，是不是得找到这个末尾呢？肯定需要的。

所以在调用函数的时候，我们需要进行传址调用，改变尾指针的指向，即记录节点

这里涉及到函数调用的问题，我们需要知道形参是实参的一份临时拷贝，如果不传址调用的话，形参写成Node* pend
退出这个函数的时候，主函数中end指针的指向是没有改变的，仍然指向的是头节点。

还有一点要提醒，要把节点连起来，一开始的尾指针是要指向头节点的。

void TailCreatList(Node_t** pend,int x)
{
	Node_t* p = AollocNode(x);
	(*pend)->next = p;
	*pend = p;
}

💦完整代码

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

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

void TailCreatList(Node_t** pend,int x)
{
	Node_t* p = AollocNode(x);
	(*pend)->next = p;
	*pend = p;
}
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;
	int i = 0;
	//尾插入创建
	//int data = 0;
	for (i = 1; i < 10; i++)
	{
		//scanf("%d", &data);
		TailCreatList(&end, i);
		//TailCreatList(&end, data);
		head->lenth++;
	}
	ShowList(head);
	
	free(head);
	head = NULL;
	return 0;
}

也可以这样写，看你使用场景去选择

void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}

💦完整代码

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

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	printf("初始化链表:");
	for (i = 0; i < 10; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;
	int i = 0;
	//尾插入创建
	TailCreatList(&end);
	ShowList(head);

	free(head);
	head = NULL;
	return 0;
}

🌊尾插法 VS 头插法

头插入

void HeadCreatList(Node_t* head,int x)
{
	Node_t* p = AollocNode(x);
	p->next = head->next;
	head->next = p;
}

局部代码

	for (i = 1; i < 10; i++)
	{
		TailCreatList(&end, i);
	}
	for (i = 1; i < 10; i++)
	{
		HeadCreatList(head1, i);
	}

通过运行结果我们可以看出两者的差别。
一个是尾部添加产生的是顺序效果，一个是头部添加产生的是逆序效果
使用哪种方法创建链表具体情况具体分析使用哪种会更简单

比如在这篇博客中单链表实战项目贪吃蛇 蛇的创建，移动过程中的添加身体，用尾插法会省事许多

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

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
void TailCreatList(Node_t** pend ,int x)
{
	Node_t* p = AollocNode(x);
	(*pend)->next = p;
	*pend = p;
}
void HeadCreatList(Node_t* head,int x)
{
	Node_t* p = AollocNode(x);
	p->next = head->next;
	head->next = p;
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* head1 = AollocNode(0);
	Node_t* end = head;
	int i = 0;
	//尾插入创建
	for (i = 1; i < 10; i++)
	{
		TailCreatList(&end, i);
	}
	for (i = 1; i < 10; i++)
	{
		HeadCreatList(head1, i);
	}
	ShowList(head);
	printf("\n");
	ShowList(head1);

	free(head);
	free(head1);
	head1 = NULL;
	head = NULL;
	return 0;
}

💧插入操作

🌊插入 一 在x位置处插入一个数y

先判断这个x是否合法

//插入1 从特定位置插入
void Insert1Node(Node_t* head ,int x,int y)
{
	if (x<1 || x>head->lenth)
	{
		printf("位置错误\n");
		exit(0);//结束程序
	}
	int i = 0;
	Node_t* t = AollocNode(y);//创建节点并给data赋值为y
	Node_t* p = head;
	while (i < x - 1)
	{
		p = p->next;
		i++;
	}
	t->next = p->next;
	p->next = t;
	head->lenth++;
}

x需要减1为啥呢？因为链表中访问节点只能能过一个节点一个节点访问。

所以，只能通过循环遍历的方式查找
又因为在x位置处插入新的数据，得找到原来x处节点的前一个节点，才能插入并且连接起来。

综上所述， x-1即循环的次数，在查找x-1次后，p恰好指向x位置处的前一个节点。

改变指针指向的先后顺序要注意。如果先p->next = t;，那t就找不到原来的第三个节点了，因为p->next 的指向已经改变了

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;
//尾插入创建
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印函数
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

//插入1 从特定位置插入
void Insert1Node(Node_t* head ,int x,int y)
{
	if (x<1 || x>head->lenth)
	{
		printf("位置错误\n");
		exit(0);//结束程序
	}
	int i = 0;
	Node_t* t = AollocNode(y);//创建节点并给data赋值为y
	Node_t* p = head;
	//x = 3
	while (i < x - 1)
	{
		p = p->next;
		i++;
	}
	t->next = p->next;
	p->next = t;
	head->lenth++;
}

int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;
	int i = 0;
	//尾插入创建
	TailCreatList(&end);
	
	int x = 0;
	int y = 0;
	printf("请输入：在x位置处，插入y数\n");
	scanf("%d %d", &x,&y);
	Insert1Node(head,x,y);
	ShowList(head);
	free(head);
	head = NULL;
	return 0;
}

🌊插入 二 插入一个数，使原有链表任然有序(原链表有序）

这种情况下的插入，我们仍然需要去找合适位置处的前一个节点，才能保证我们插入且连接。

在通过循环查找的时候，不能忘记指针可能指向NULL的情况，比如说，原有的链表是升序，插入的这个数是最大的，那插入位置只能在最后。

void Insert2Node(Node_t* head, int x)
{
	Node_t* p1 = head->next;//p1->data与x做比较
	Node_t* p2 = head;//找p1指向节点的前驱(即前一个节点)
	Node_t* t = AollocNode(x);
	while (p1->data < x && p1)//原链表为升序
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	t->next = p2->next;
	p2->next = t;
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
//插入 2 保证原来有序的情况下插入
void Insert2Node(Node_t* head, int x)
{
	Node_t* p1 = head->next;//p1->data与x做比较
	Node_t* p2 = head;//找p1指向节点的前驱(即前一个节点)
	Node_t* t = AollocNode(x);
	while (p1->data < x && p1)//p1->data < x 根据你原有表的顺序
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	t->next = p2->next;
	p2->next = t;
}

int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;
	
	//尾插入创建
	TailCreatList(&end);
	int y = 0;
	printf("请输入:插入y数\n");
	scanf("%d", &y);
	Insert2Node(head, y);
	ShowList(head);

	free(head);
	head = NULL;
	return 0;
}

💧删除

🌊删除 一 删除链表中第x处的数据

和上述操作插入一样，同样需要找到x处的前一个节点。
为啥呢？删除数据后你还要将断开的链表连接起来，所以你必须找到x处的前一个节点。

删除的本质是释放空间。 原因也很简单：节点都是在堆区上开辟的，要将其删除只要释放所开辟的空间即可

不能忘记对删除位置的判断，判断其是否合法

//删除一 从指定位置删除
void Dele1Node(Node_t* head, int x)
{
	Node_t* p = head;//要注意p开始的指向
	Node_t* t = NULL;//指向要被删除的节点
	if (x<1 || x>head->lenth)
	{
		printf("删除位置错误\n");
		exit(0);//退出程序
	}
	while (x - 1  > 0)
	{
		p = p->next;
		x--;
	}
	t = p->next;//指向要删除的数据
	p->next = p->next->next;//链接，把删除节点的前一个节点和后一个节点连起来
	free(t);//删除操作
	t = NULL;
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
//删除一 从指定位置删除
void Dele1Node(Node_t* head, int x)
{
	Node_t* p = head;//要注意p开始的指向
	Node_t* t = NULL;//指向要被删除的节点
	if (x<1 || x>head->lenth)
	{
		printf("删除位置错误\n");
		exit(0);//退出程序
	}
	while (x - 1  > 0)
	{
		p = p->next;
		x--;
	}
	t = p->next;//指向要删除的数据
	p->next = p->next->next;//链接，把删除节点的前一个节点和后一个节点连起来
	free(t);//删除操作
	t = NULL;
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;

	//尾插入创建
	TailCreatList(&end);
	int x = 0;

	printf("请输入：要被删除的位置\n");
	scanf("%d", &x);
	Dele1Node(head, x);
	ShowList(head);

	free(head);
	head = NULL;
	return 0;
}

🌊删除 二 删除链表中所有的数据y

和上面一样，还是得找删除节点的前驱(即前一个节点)，在和删除节点的后面一个节点链接起来。

这种情况下，需要考虑数据不存在的情况，需要设一个标记去判断。

要注意的是，删除数据的时候，前驱是不能指向下一个的，因为删除之后，p指针需要指向删除节点的下一个一个节点。
还需要另外增加一个指针去指向删除的节点，不能使用p去释放。如果free(p)，该节点删除的同时，p已经找不到下一个节点了，内部数据会被清空。

void Dele2Node(Node_t* head, int y)
{
	Node_t* p = head->next;//指向第一个节点
	Node_t* t = head;//同样也要找到删除数据的前一个节点
	int flag1 = 1;//下面if的标记
	while ( p )
	{
		int flag = 1;//标记是否有释放
		if (p->data == y)
		{
			Node_t* p1 = p;
			t->next = p->next;//链接,p指向的是删除节点，t指向的是删除节点的前一个节点

			p = p->next;//指向下个节点

			free(p1);//删除
			flag = 0;
			flag1 = 0;
		}
		if (flag)
		{
			p = p->next;
			t = t->next;
		}
	}
	if (flag1)
	{
		printf("链表中无此数据\n");
		exit(0);//退出程序
	}
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
void Dele2Node(Node_t* head, int y)
{
	Node_t* p = head->next;//指向第一个节点
	Node_t* t = head;//同样也要找到删除数据的前一个节点
	int flag1 = 1;//下面if的标记
	while ( p )
	{
		int flag = 1;//标记是否有释放
		if (p->data == y)
		{
			Node_t* p1 = p;
			t->next = p->next;//链接,p指向的是删除节点，t指向的是删除节点的前一个节点

			p = p->next;//指向下个节点

			free(p1);//删除
			flag = 0;
			flag1 = 0;
		}
		if (flag)
		{
			p = p->next;
			t = t->next;
		}
	}
	if (flag1)
	{
		printf("链表中无此数据\n");
		exit(0);//退出程序
	}
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;

	//尾插入创建
	TailCreatList(&end);
	int x = 0;

	printf("请输入：要被删除的位置\n");
	scanf("%d", &x);
	Dele1Node(head, x);
	ShowList(head);

	free(head);
	head = NULL;
	return 0;
}

🌊删除 三 删除链表中所有重复的数（2022.10.8）

这个操作的难点是把所有的重复的元素进行删除，在删除的时候，能两个两个一起删吗？答案是不能，比如这组数1 1 1 2两个两个一起删后只剩下1 2它就结束了。不符合要求。
所以删除只能一个一个的删除，那删除哪个呢？当然是前一个，删除后再去偏移，要是相等再次删除。这样就不会遗漏了。

仅仅这样还是不能做到完全删除，仍然是这个数据1 1 1 2删除到最后还会剩下1 2。
思路肯定是没错的，只是在过程中还需要添加标记，去记录前一次的删除的值，这样才能正确匹配，并且全部删除。

还要考虑特殊情况，①没有节点的时候，②相同数据出现在最后的情况1 1 1 2 2，仅仅在循环内部完成的话最后还会剩下2，我们在出循环后仍然需要在来一次比较，和之前删除的数的比较。

void DeReList(Node_t* head)
{
	if (head->next == NULL)//对第一个节点进行判断
	{
		return;
	}
	Node_t* p = head->next->next;//指向第二个节点
	Node_t* p1 = head->next;//p的前驱
	Node_t* p2 = head;//p1的前驱

	int flag = 1;
	int bedata = 0;//记录重复的数据
	while (p) 
	{
		flag = 1;
		if (p->data == p1->data || bedata == p1->data)
		{
			//用p4,p5来释放节点，p1,p指向后面的节点
			Node_t* p4 = p1;
			bedata = p1->data;
			//1 1 1 2
			p1 = p1->next;
			p = p1->next;
			p2->next = p1;
			free(p4);
			flag = 0;

		}
		if (flag)
		{
			p = p->next;
			p1 = p1->next;
			p2 = p2->next;
		}
	}
	//判断最后一个节点是否是重复的
	if (p1->data == bedata)
	{
		p2->next = p1->next;
		free(p1);
	}
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
void DeReList(Node_t* head)
{
	if (head->next == NULL)//对第一个节点进行判断
	{
		return;
	}
	Node_t* p = head->next->next;//指向第二个节点
	Node_t* p1 = head->next;//p的前驱
	Node_t* p2 = head;//p1的前驱

	int flag = 1;
	int bedata = 0;//记录重复的数据
	while (p) 
	{
		flag = 1;
		if (p->data == p1->data || bedata == p1->data)
		{
			//用p4,p5来释放节点，p1,p指向后面的节点
			Node_t* p4 = p1;
			bedata = p1->data;
			//1 1 1 2
			p1 = p1->next;
			p = p1->next;
			p2->next = p1;
			free(p4);
			flag = 0;

		}
		if (flag)
		{
			p = p->next;
			p1 = p1->next;
			p2 = p2->next;
		}
	}
	//判断最后一个节点是否是重复的
	if (p1->data == bedata)
	{
		p2->next = p1->next;
		free(p1);
	}
}
int main()
{
	
	Node_t* head = AollocNode(0);
	Node_t* end = head;
	TailCreatList(&end);
	
	DeReList(head);
	ShowList(head);

	free(head);
	head = NULL;
	return 0;
}

💧查改

这两个放在一起也是有原因的，要进行修改的操作，是在查的基础上进修改的。
查和改比较简单，不需要对节点增或减，此处就略讲。

🌊查 一 查找具体的数据是否存在

	
void Search1Data(Node_t* head,int y)
{
	Node_t* p = head->next;//指向第一个节点
	int i = 1;
	while (p)
	{
		if (p->data == y)
		{
			printf("%d在第%d个节点处\n", y, i);
			break;
		}
		i++;
		p = p->next;
	}
	if (NULL == p)
		printf("无此数据\n");
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
//查找1
void Search1Data(Node_t* head,int y)
{
	Node_t* p = head->next;//指向第一个节点
	int i = 1;
	while (p)
	{
		if (p->data == y)
		{
			printf("%d在第%d个节点处\n", y, i);
			break;
		}
		i++;
		p = p->next;
	}
	if (NULL == p)
		printf("无此数据\n");
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;

	//尾插入创建
	TailCreatList(&end);
	int y = 0;

	printf("请输入：要查找的数据\n");
	scanf("%d", &y);
	Search1Data(head,y);

	free(head);
	head = NULL;
	return 0;
}

🌊查 二 查找某个节点的数据并展示

void Search2Data(Node_t* head, int x)
{
	Node_t* p = head;//指向头节点
	if (x < 1 || x > head->lenth)
	{
		printf("位置错误");
		exit(0);
	}
	while (x)
	{
		p = p->next;
		x--;
	}
	printf("%d", p->data);
}

💦完整代码

🌊改

改的操作基于查 二就可以完成了，也是很容易的。

void MoidfyData(Node_t* head,int x,int y)
{
	Node_t* p = head;//指向头节点
	if (x < 1 || x > head->lenth)
	{
		printf("位置错误");
		exit(0);
	}
	while (x)
	{
		p = p->next;
		x--;
	}
	p->data = y;
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}
//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}
//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
//修改
void MoidfyData(Node_t* head,int x,int y)
{
	Node_t* p = head;//指向头节点
	if (x < 1 || x > head->lenth)
	{
		printf("位置错误");
		exit(0);
	}
	while (x)
	{
		p = p->next;
		x--;
	}
	p->data = y;
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* end = head;

	//尾插入创建
	TailCreatList(&end);
	int x = 0;
	int y = 0;

	printf("请输入：要修改的位置,以及修改后的值\n");
	scanf("%d%d", &x, &y);
	MoidfyData(head, x, y);
	ShowList(head);

	free(head);
	head = NULL;
	return 0;
}

💧排序

如果你了解过插入排序，那么单链表的排序也会非常的容易理解。

单链表中每个节点存储的时候，地址并不是连续的，所以冒泡排序，选择排序就不适用了，插入排序可不在乎数据存储时的地址是否连续。
这里介绍以插入排序的思想去实现单链表的排序。

🌊插入排序

看下面这张动图。
插入排序，从第二个元素开始。
先把第二个元素拿出来，和前面元素比较，如果是比前面元素小的话就进行插入，否则就不动。（升序）

比较比的是当前下标前面的元素。
在对第三个元素进行插入的时候，前面的元素已经是有序的了！在对第n个元素进行插入的时候，前面n-1个元素已经有序了。

代码实现

int main()
{
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	for (i = 1; i < sz; i++)
	{
		int t = arr[i];//插入元素拿出来--拷贝
		int j = i - 1;//从插入元素前面开始比较
		while (j >= 0 && t < arr[j])
		{
			arr[j + 1] = arr[j];//往后覆盖--移动
			j--;
		}
		arr[j + 1] = t;//有个减减的效果，因此要+1
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

简单了解了一下插入排序，那就开始单链表的排序吧
也是靠这个图来理解。

首先需要明确一点，单链表的访问，只能一个节点一个节点的去访问。
插入思想是什么呢？从第二个节点开始， 要插入的节点 需要拿出来，和之前的节点比较。

单链表和顺序存储(数组)不一样，节点拿出来了，还需要与后面的节点连起来。
还记得上面的插入操作吗？插入需要记录前驱。

不管是哪种方法，都要有下列这四种功能的。

第一个指针指向插入节点
第二个指针指向插入节点的前驱，起连接作用
第三个指针找插入位置
第四个指针指向插入位置的前驱
第三第四作用是 进行插入，连接。

下列代码为排成升序

🌊方法一

根据节点查找的特点，进行插入排序。
每次只能从第一个节点开始往后找插入位置，在进行插入。

void OrderList(Node_t* head)
{
	Node_t* p1 = head->next;//插入节点的前驱，起到连接作用
	Node_t* p2 = NULL;//找插入的位置
	Node_t* p3 = NULL;//记录插入位置前一个节点
	Node_t* t = p1->next;//开始先指向第二个节点，指向要插入的节点
	while (t)
	{
		p2 = head->next;//遍历要从第一个节点开始
		p3 = head;//记录 p2指向节点的前驱
		int flag = 1;//标记是否为升序
		while (p2 != t && flag)
		{
			if (t->data <= p2->data)
			{
				Node_t* t1 = t;
				t = t1->next;//指向下一个插入的节点
				p1->next = t1->next;//连接

				t1->next = p2;//插入
				p3->next = t1;
				flag = 0;
			}
			p2 = p2->next;
			p3 = p3->next;
		}
		if (flag)
		{
			t = t->next;
			p1 = p1->next;
		}
	}

}

🌊方法二

根据插入排序的特点。因为从第二个开始进行插入，那每次插入完成后或者没插入，不管哪种情况，下一个插入节点的前面所有节点都是有序的。

因此在比较的时候只要比较相邻的两个节点是否是升序，如果不是升序那么则进行插入，从第一个节点开始找位置。

void OrderList(Node_t* head)
{
	Node_t* p = head->next;//指向前一个节点 (第一个节点)，插入节点的前驱
	Node_t* p1 = p->next;//指向后一个节点(第二个节点) 指向插入节点

	while (p1)
	{
		int flag = 0;//检测p1、p2节点是否是升序
		Node_t* p3 = head;
		Node_t* p4 = head->next;
		if (p->data > p1->data)
		{
			//拷贝,链接
			Node_t* tmp = p1;//拷贝
			flag = 1;
			//链接
			p1 = p1->next;
			p->next = p1;

			//开始插入
			//因为链表的特点只能从头开始遍历，找到特定的位置插入
			while (p4->data < tmp->data)
			{
				p4 = p4->next;
				p3 = p3->next;
			}
			tmp->next = p3->next;
			p3->next = tmp;
		}
		if (!flag)
		{
			p1 = p1->next;
			p = p->next;
		}
	}
}

如果，你想把你的排序功能写的更强大一些，那就看这篇博客qsort的介绍以及模拟实现怎么个强大法呢？OrderList函数可以对任意类型进行排序。

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}

//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

//方法一
//void OrderList(Node_t* head)
//{
//	Node_t* p1 = head->next;//插入节点的前驱，起到连接作用
//	Node_t* p2 = NULL;//遍历 插入节点前的所有节点
//	Node_t* p3 = NULL;//记录前驱，要记录前一个节点，才能插入
//	Node_t* t = p1->next;//开始先指向第二个节点，指向要插入的节点
//	while (t)
//	{
//		p2 = head->next;//遍历要从第一个节点开始
//		p3 = head;//记录 p2指向节点的前驱
//		int flag = 1;//标记是否为升序
//		while (p2 != t && flag)
//		{
//			if (t->data <= p2->data)//升序
//			{
//				Node_t* t1 = t;
//				t = t1->next;//指向下一个插入的节点
//				p1->next = t1->next;//连接
//		
//				t1->next = p2;//t->next = p3->next;//插入
//				p3->next = t1;
//				flag = 0;
//			}
//			p2 = p2->next;
//			p3 = p3->next;
//		}
//		if (flag)
//		{
//			t = t->next;
//			p1 = p1->next;
//		}
//	}
//
//}

//方法二
void OrderList(Node_t* head)
{
	Node_t* p = head->next;//指向前一个节点 (第一个节点)
	Node_t* p1 = p->next;//指向后一个节点(第二个节点) 指向插入元素

	//p1遍历所有的链表元素
	while (p1)
	{
		int flag = 0;//检测p1、p2节点是否是升序
		Node_t* p3 = head;
		Node_t* p4 = head->next;
		if (p->data > p1->data)//升序
		{
			//拷贝,链接
			Node_t* tmp = p1;//拷贝
			flag = 1;
			//链接
			p1 = p1->next;
			p->next = p1;

			//开始插入
			//因为链表的特点只能从头开始遍历，找到特定的位置插入
			while (p4->data < tmp->data)
			{
				p4 = p4->next;
				p3 = p3->next;
			}
			tmp->next = p3->next;
			p3->next = tmp;
		}
		if (!flag)
		{
			p1 = p1->next;
			p = p->next;
		}
	}
}
int main()
{

	Node_t* head = AollocNode(0);
	Node_t* end = head;

	//尾插入创建
	TailCreatList(&end);
	
	OrderList(head);
	ShowList(head);
	
	free(head);
	head = NULL;
	return 0;
}

🌊排序 二 对单链表中的结构体的任意类型的成员排序（2022.10.8）

提前说明：基于这篇博客进行讲解qsort的应用以及模拟

我们需要知道顺序表和单链表是不同的，在存储地址上有很大差异，单链表存储地址是任意的，而顺序表在存储的时候是连续的。

这也是为什么qsort在使用的时候，需要传一个长度，和一个元素的大小。就可以用char*的指针，结合元素的大小和长度，将所有元素遍历一遍。

那单链表需要传一个长度和一个元素的大小吗？答案是不要的。因为单链表只需要知道一个头节点，就可以遍历完所有的节点

在传参的设计上，我们还需要用void*吗？不需要了，为什么呢？我们的要求是对节点中结构体的任意成员排序。节点的类型是固定死了的。

那还需要什么？需要比较的方法。根据你想比较的成员去写比较函数。和qsort中一样的设计。

事先说明，对于下图这段代码仅在.cpp的文件中有效，在.c的文件中会报错。
因为结构体的初始化操作只能在定义变量的时候进行。

在InsertSort函数中，比较那里注意要传地址。

typedef struct Student
{
	int age;
	char name[10];
}stu;

typedef struct Node
{
	int data;
	int lenth;
	stu student;
	struct Node* next;
}Node_t;

int stint_cmp(const void* e1, const void* e2)
{
	return ((stu*)e1)->age - ((stu*)e2)->age;
}
int stchar_cmp(const void* e1, const void* e2)
{
	return strcmp(((stu*)e1)->name, ((stu*)e2)->name);
}

//对指定结构体中任意类型排序
void InsertSort(Node_t* head, int(*cmp)(const void*, const void*))
{
	
	Node_t* t1 = head->next;//插入节点的前驱
	Node_t* t = t1->next;//插入节点
	Node_t* p = NULL;//p1的前驱
	Node_t* p1 = NULL; //遍历插入节点前面所有的节点

	int flag = 1;
	while (t)
	{
		flag = 1;
		Node_t* p = (Node_t*)head;//p1的前驱
		Node_t* p1 = head->next; //遍历插入节点前面所有的节点
		while (p1 != t && flag)
		{
			if (cmp(&(p1->student), &(t->student)) > 0)
			{
				Node_t* t3 = t;
				t = t->next;//指向下个节点
				t1->next = t;//连接

				p->next = t3;
				t3->next = p1;
				flag = 0;
			}
			p = p->next;
			p1 = p1->next;
		}
		if (flag)
		{
			t = t->next;
			t1 = t1->next;
		}

	}
	
}

💦完整代码

typedef struct Student
{
	int age;
	char name[10];
}stu;

typedef struct Node
{
	int data;
	int lenth;
	stu student;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}

//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}
int stint_cmp(const void* e1, const void* e2)
{
	return ((stu*)e1)->age - ((stu*)e2)->age;
}
int stchar_cmp(const void* e1, const void* e2)
{
	return strcmp(((stu*)e1)->name, ((stu*)e2)->name);
}

//对指定结构体中任意类型排序
void InsertSort(Node_t* head, int(*cmp)(const void*, const void*))
{
	
	Node_t* t1 = head->next;//插入节点的前驱
	Node_t* t = t1->next;//插入节点
	Node_t* p = NULL;//p1的前驱
	Node_t* p1 = NULL; //遍历插入节点前面所有的节点

	int flag = 1;
	while (t)
	{
		flag = 1;
		Node_t* p = (Node_t*)head;//p1的前驱
		Node_t* p1 = head->next; //遍历插入节点前面所有的节点
		while (p1 != t && flag)
		{
			if (cmp(&(p1->student), &(t->student)) > 0)
			{
				Node_t* t3 = t;
				t = t->next;//指向下个节点
				t1->next = t;//连接

				p->next = t3;
				t3->next = p1;
				flag = 0;
			}
			p = p->next;
			p1 = p1->next;
		}
		if (flag)
		{
			t = t->next;
			t1 = t1->next;
		}

	}
	
}
int main()
{
	
	Node_t* head = AollocNode(0);

	//测试对任意节点中的结构体排序
	Node_t* p= AollocNode(1);
	head->next = p;
	Node_t* p1 = AollocNode(2);
	p->next = p1;
	Node_t* p2 = AollocNode(3);
	p1->next = p2;
	p->student = { 12 ,"za" };//1
	p1->student = { 16,"ba" };//2
	p2->student = { 13,"fa" };//3

	//对特定结构体中任意成员排序
	InsertSort(head, stint_cmp);
	ShowList(head);
	InsertSort(head, stchar_cmp);
	ShowList(head);
	
	free(head);
	head = NULL;
	return 0;
}

💧逆置

还记得 尾插法 vs 头插法中说到它们俩的特点吗？
尾插法产生的是顺序的结果，头插法产生的是逆序的结果。说到这你是否有思路了呢。

只要拿出链表最后一个节点进行头插入不就完成了逆置吗？当第一个节点变为最后一个节点，逆置结束。换句话说就是原来第一个节点的下一个节点指向的是NULL，逆置结束。

这里需要注意的是头插入位置是在移动的，因此也是需要记录的

void ReverseList(Node_t* head)
{
	Node_t* t = head->next;
	Node_t* t1 = head;//指向插入位置的前驱
	while (t->next)//原有的第一个节点下一个为NULL时结束
	{
		Node_t* p1 = head->next;//遍历找最后一个节点进行头插
		Node_t* p = head;//p指向的节点是p1指向节点的前驱。
		//起连接的作用，即让p指向的节点变为最后一个指向NULL
		while (p1->next)
		{
			p1 = p1->next;
			p = p->next;
		}
		//出循环后p1指向最后一个节点
		p->next = p1->next;//起连接的作用，最后一个节点也就被拿出来了在进行头插入

		//头插入
		p1->next = t1->next;
		t1->next = p1;
		t1 = t1->next;
	}
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}

//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

void ReverseList(Node_t* head)
{
	Node_t* t = head->next;
	Node_t* t1 = head;//指向插入位置的前驱
	while (t->next)//原有的第一个节点下一个为NULL时结束
	{
		Node_t* p1 = head->next;//遍历找最后一个节点进行头插
		Node_t* p = head;//p指向的节点是p1指向节点的前驱。
		//起连接的作用，即让p指向的节点变为最后一个指向NULL
		while (p1->next)
		{
			p1 = p1->next;
			p = p->next;
		}
		//出循环后p1指向最后一个节点
		p->next = p1->next;//起连接的作用，最后一个节点也就被拿出来了在进行头插入

		//头插入
		p1->next = t1->next;
		t1->next = p1;
		t1 = t1->next;
	}
}
int main()
{
	Node_t* head = AollocNode(0);
	Node_t* head1 = AollocNode(0);
	Node_t* end = head;

	//尾插入创建
	TailCreatList(&end);
	
	ReverseList(head);
	ShowList(head);
	
	free(head);
	head = NULL;
	return 0;
}

💧合并

提前说明，这里的合并后的链表并没有新增额外的空间，用的是已有链表的空间。这就会导致原来链表可能会发生改变。

🌊合并 一 无序合并

这个比较简单，合并成无序的链表

void Merge1List(Node_t* head, Node_t* head1, Node_t* head2)
{
	Node_t* p2 = head2;//head2是合并后的链表
	p2->next = head->next;
	while (p2->next)
	{
		p2 = p2->next;
	}
	p2->next = head1->next;
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}

//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

void Merge1List(Node_t* head, Node_t* head1, Node_t* head2)
{
	Node_t* p2 = head2;//head2是合并后的链表
	p2->next = head->next;
	while (p2->next)
	{
		p2 = p2->next;
	}
	p2->next = head1->next;
}
int main()
{

	Node_t* head = AollocNode(0);
	Node_t* head1 = AollocNode(0);
	Node_t* head2 = AollocNode(0);
	Node_t* end = head;
	Node_t* end1 = head1;

	//尾插入创建
	TailCreatList(&end);
	TailCreatList(&end1);

	Merge2List(head, head1, head2);
	ShowList(head2);

	free(head);
	free(head1);
	free(head2);
	head2 = NULL;
	head1 = NULL;
	head = NULL;
	return 0;
}

🌊合并 二 有序合并

原来有序，合并成有序。
这里讲两个升序的序合并为一个升序

其它有序链表通过上面的逆置，排序操作，都可以转化变为两个升序的合并

void Merge2List(Node_t* head, Node_t* head1, Node_t* head2)
{
	Node_t* p = head->next;//指向第一个节点
	Node_t* p1 = head1->next;//指向第一个节点
	Node_t* p2 = head2;//合并后的链表
	while (p && p1)
	{
		if (p->data < p1->data)
		{
			p2->next = p;
			p = p->next;
		}
		else
		{
			p2->next = p1;
			p1 = p1->next;
		}
		p2 = p2->next;
	}
	//p1指向NULL,表明p指向的链表还有数据
	if (p1 == NULL)
	{
		p2->next = p;
	}
	//p指向NULL,表明p1指向的链表还有数据
	if (p == NULL)
	{
		p2->next = p1;
	}
}

💦完整代码

typedef struct Node
{
	int data;
	int lenth;
	struct Node* next;
}Node_t;

//开辟空间+初始化 
Node_t* AollocNode(int x)
{
	Node_t* p = (Node_t*)malloc(sizeof(Node_t));
	if (p == NULL)//检测是否开辟成功
	{
		perror("molloc");
	}
	p->data = x;
	p->next = NULL;
	return p;
}

//尾插法创建链表 2
void TailCreatList(Node_t** pend)
{
	int i = 0;
	int x = 0;
	int n = 0;
	printf("请输入初始化链表的个数");
	scanf("%d", &n);
	(*pend)->lenth = n;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Node_t* p = AollocNode(x);
		(*pend)->next = p;
		*pend = p;
	}
}

//打印链表
void ShowList(Node_t* head)
{
	Node_t* p = head->next;
	while (p)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

void Merge2List(Node_t* head, Node_t* head1, Node_t* head2)
{
	Node_t* p = head->next;//指向第一个节点
	Node_t* p1 = head1->next;//指向第一个节点
	Node_t* p2 = head2;//合并后的链表
	while (p && p1)
	{
		if (p->data < p1->data)
		{
			p2->next = p;
			p = p->next;
		}
		else
		{
			p2->next = p1;
			p1 = p1->next;
		}
		p2 = p2->next;
	}
	//p1指向NULL,表明p指向的链表还有数据
	if (p1 == NULL)
	{
		p2->next = p;
	}
	//p指向NULL,表明p1指向的链表还有数据
	if (p == NULL)
	{
		p2->next = p1;
	}
}

int main()
{

	Node_t* head = AollocNode(0);
	Node_t* head1 = AollocNode(0);
	Node_t* head2 = AollocNode(0);
	Node_t* end = head;
	Node_t* end1 = head1;
	
	//尾插入创建
	TailCreatList(&end);
	TailCreatList(&end1);

	Merge2List(head, head1, head2);
	ShowList(head2);

	free(head);
	free(head1);
	free(head2);
	head2 = NULL;
	head1 = NULL;
	head = NULL;
	return 0;
}

🔥结束语

可以使用单链表基本操作，去创建一个通讯录。大家可以尝试下。后续更新哦~

也可以去看 C语言实现的贪吃蛇，这里涉及到了大量的单链表的操作。