学习笔记---看完就会的单链表的应用～～

1.单链表经典算法🫵

1.1 单链表相关经典算法OJ题1：移除链表元素

1.2 单链表相关经典算法OJ题2：反转链表

1.3 单链表相关经典算法OJ题3：合并两个有序链表

1.4 单链表相关经典算法OJ题4：链表的中间结点

1.5 循环链表经典应⽤-环形链表的约瑟夫问题

1.6 单链表相关经典算法OJ题5：分割链表

2. 基于单链表再实现通讯录项⽬👑

2.0 Slist.h(底层逻辑）

2.1 SList.c(底层逻辑)

2.2 Contact.h

2.3 Contact.c

2.4 test.c

2.5 最终效果呈现

1.单链表经典算法🫵

1.1 单链表相关经典算法OJ题1：移除链表元素

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

方法1:直接在原链表上面执行删除操作

方法2:创建一个新链表，将不等于val的数据存入

我们这里使用方法2，也更推荐方法2，因为更简单

1.2 单链表相关经典算法OJ题2：反转链表

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

方法1:创建一个新链表，遍历原链表，将原链表的节点依次头插到新链表

方法2:在原链表的基础上，翻转箭头方向

我们这里更推荐方法2，因为更简单

1.3 单链表相关经典算法OJ题3：合并两个有序链表

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解法1:遍历原链表，将小的放到大的之前，会涉及到在指定位置之前插入数据

解法2:创建1个新链表，遍历2个原链表，比较之后放入新链表

我们这里更推荐方法2，因为更简单

typedef struct ListNode ListNode;
 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     //判断链表是否为空
if(list1==NULL){
   return list2; 
}
if(list2==NULL){
   return list1;
}
//创建指针遍历原链表
ListNode* cur1=list1;
ListNode* cur2=list2;
 //创建新链表---带头---不考虑是否为空
 ListNode* newhead,*newtail;
 newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
 //判断空间是否开辟成功
 if(newhead==NULL||newtail==NULL)
 {
     perror("malloc");
     exit(1);
 }
while(cur1&&cur2)
{
    if(cur1->val<cur2->val)
    {
        newtail->next=cur1;
        newtail=newtail->next;
        cur1=cur1->next;
    }
    else
    {
        newtail->next=cur2;
        newtail=newtail->next;
        cur2=cur2->next;
    }
}
//也可能list1和list2的个数不相同
if(cur1)
{
    newtail->next=cur1;
}
if(cur2)
{
    newtail->next=cur2;
}
//free
ListNode* rethead=newhead->next;
free(newhead);
return rethead;
}

1.4 单链表相关经典算法OJ题4：链表的中间结点

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

注意while的判断条件不能交换位置，&&会先判断前面的，如果前面为假，则不进去while循环

如果5个数据，fast->next放在前面，我们fast走到第四个数据的时候，fast->next已经指向NULL了，循环结束了

1.5 循环链表经典应⽤-环形链表的约瑟夫问题

环形链表的约瑟夫问题_牛客题霸_牛客网

著名的Josephus问题

据说著名犹太历史学家 Josephus有过以下的故事：在罗⻢⼈占领乔塔帕特后，39 个犹太⼈与Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被⼈抓到，于是决定了⼀个⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀个重新报数，直到所有⼈都⾃杀⾝亡为⽌。

然⽽Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 //创建带环链表
 #include <stdio.h>
#include <stdlib.h>
typedef struct ListNode ListNode;
//申请空间
ListNode* ListByNode(int x)
{
    ListNode* node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    node->val=x;
    node->next=NULL;
    return node;
}
ListNode* CreateList(int n)
{
    //创建单链表
    ListNode* phead=ListByNode(1);
    ListNode* pTail=phead;
    for(int i=2;i<=n;i++)
    {
        ListNode* node=ListByNode(i);
        pTail->next=node;
        pTail=pTail->next;
    }
    //创建带环链表
    pTail->next=phead;
    return pTail;//有尾节点就能找到头节点
}
int ysf(int n, int m ) {
    ListNode* prev=CreateList(n);//prev指代尾节点
    //进行游戏
    ListNode* cur=prev->next;
    int count=1;//cur指向头节点，报数1
    while(cur->next!=cur)//cur->next=cur时，只剩1个人了
    {
        if(count==m)
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
            count=1;//重新开始报数
        }
        else
        {
            prev=cur;
            cur=cur->next;
            count++;
        }
    }
    return cur->val;
}

1.6 单链表相关经典算法OJ题5：分割链表

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：创建2个带头（不用考虑链表是否为空）的新链表，遍历原链表，将小于x的放在小链表，大于x的放在大链表，最后将小链表的尾节点指向大链表的第一个节点（不是指向哨兵位）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head==NULL)
    return head;
//创建2个带头的新链表
ListNode* lesshead,* lesstail;
ListNode* biggerhead,* biggertail;
//申请空间
lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode));
biggerhead=biggertail=(ListNode*)malloc(sizeof(ListNode));
//创建指针遍历原链表
ListNode* cur=head;
while(cur)
{
    if(cur->val<x)
    {
        lesstail->next=cur;
        lesstail=lesstail->next;
    }
    else
    {
        biggertail->next=cur;
        biggertail=biggertail->next;
    }
    cur=cur->next;
}
//如果没有把大链表的尾节点置为NULL，那么会造成超出时间限制的问题
if(biggertail)
{
    biggertail->next=NULL;
}
//把小链表和大链表的尾节点和第一个节点相连
lesstail->next=biggerhead->next;
//free
free(biggerhead);
//大链表的哨兵位没有用到直接free就可以，但是小链表的哨兵位用到了，不能直接free--->先存储起来，然后free
ListNode* rethead=lesshead->next;
free(lesshead);
return rethead;
}

2. 基于单链表再实现通讯录项⽬👑

有了上次的顺序表实现通讯录📇，我们这次基于单链表再实现通讯录项⽬就显得比较简单了，由于思路和要实现的目标都差不多，这里我就不再赘述了，需要的请自行看之前的博客，博客链接：学习笔记---不容错过的顺序表的应⽤～～-CSDN博客文章浏览阅读148次，点赞36次，收藏22次。顺序表实现通讯录📇，经典算法OJ题https://blog.csdn.net/2301_79184587/article/details/133929298

学习笔记---0基础+干货满满的单链表专题～～-CSDN博客文章浏览阅读175次，点赞38次，收藏24次。超基础的单链表的知识！！！https://blog.csdn.net/2301_79184587/article/details/133965720

2.0 Slist.h(底层逻辑）

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#define _CRT_SECURE_NO_WARNINGS 1
#include"Contact.h"//包含头文件

//定义单链表节点的结构体(创建）
//typedef int SLDataType;

//替换
typedef struct PersonInfo SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLNode;

//尾插
void SLPushBack(SLNode** pphead, SLDataType x);//一级指针要二级指针接受才可以改变形参

//头插
void SLPushFront(SLNode** pphead, SLDataType x);//一级指针要二级指针接受才可以改变形参

//尾删
void SLPopBack(SLNode** pphead);

//头删
void SLPopFront(SLNode** pphead);

//打印---展示
void SLPrint(SLNode* phead);

//查找数据
SLNode* SLFind(SLNode** pphead, SLDataType x);

//指定位置之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);

//指定位置之后插入
void SLInsertAfter(SLNode* pos, SLDataType x);

//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos);

//删除pos节点之后的节点
void SLEraseAfter(SLNode* pos);

//销毁
void SLDesTroy(SLNode** pphead);

2.1 SList.c(底层逻辑)

#include"SList.h"
//打印
void SLPrint(SLNode* phead)
{
	//循环打印
	SLNode* pcur = phead;//pcur从头节点开始遍历链表
	//不用phead遍历--->以后需要用到指向头节点的地址时，帮助我找到地址
	while (pcur)//pcur指向NULL的时候结束遍历
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;//pcur指向下一个节点继续遍历
	}
	printf("NULL\n");
}

//插入数据都需要创建空间--->我们单独写出来，避免重复多次
SLNode* SLByNNode(SLDataType x)
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	if (node == NULL)
	{
		perror("malloc");
		return 1;
	}
	node->data = x;
	node->next = NULL;
	return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x)//一级指针要二级指针接受才可以改变
{   //传过来的指针不能为空
	assert(pphead);
	SLNode* node = SLByNNode(x);
	
	//链表为空,直接插入
	if (*pphead == NULL)
	{
		*pphead = node;
		return 1;
	}
	//到这说明不为空，遍历
	SLNode* pcur = *pphead;
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	pcur->next = node;
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)//一级指针要二级指针接受才可以改变形参
{
	//传过来的指针不能为空
	assert(pphead);
	SLNode* node = SLByNNode(x);
	//新节点和原来的头节点链接
	node->next = *pphead;
	//新节点成为新的头节点
	*pphead = node;
}

//尾删
void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//只有1个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个节点
	else
	{
		SLNode* prev = NULL;
		SLNode* ptail = *pphead;
		while (ptail->next!=NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = ptail->next;
		free(ptail);
		ptail = NULL;
	}
}

//头删
void SLPopFront(SLNode** pphead)
{
	assert(pphead&&*pphead);
	SLNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}

//查找数据
//SlNode* SLFind(SlNode** pphead, SLDataType x)
//{
//	assert(pphead);
//	SlNode* pcur = *pphead;
//	while (pcur)
//	{
//		if (pcur->data == x)
//		{
//			return pcur;
//		}
//		pcur = pcur->next;
//	}
//	return NULL;
//}

//指定位置之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead && *pphead&&pos);
	//创建空间
	SLNode* node = SLByNNode(x);
	//pos为第一个节点(只有1个节点)
	if (pos == (*pphead))
	{
		node->next = *pphead;
		*pphead = node;
		return 1;
	}
	//pos不为第一个节点
	//找pos节点的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	node->next = pos;
	prev->next = node;
}

//指定位置之后插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	//创建空间
	SLNode* node = SLByNNode(x);
	node->next = pos->next;
	pos->next = node;
}

//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead && *pphead && pos);
	//pos是第一个节点
	if (pos==(*pphead))
	{
		*pphead= (*pphead)->next;
		free(pos);
		return 1;
	}
	//pos不是第一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;//出于规范
}

//删除pos节点之后的节点
void SLEraseAfter(SLNode* pos)
{
	//尾节点不行，空指针也不行
	assert(pos&&pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

//销毁
void SLDesTroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
		//注意：如果是pcur->next，那么循环将结束于尾节点没有free的时候
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

2.2 Contact.h

#pragma once
#define NAME_MAX 100
#define SEX_MAX 4
#define TEL_MAX 11
#define ADDR_MAX 100


//前置声明---通讯录的底层逻辑是由单链表来实现的
typedef struct SListNode contact;

//用户数据
typedef struct PersonInfo
{
    char name[NAME_MAX];
    char sex[SEX_MAX];
    int age;
    char tel[TEL_MAX];
    char addr[ADDR_MAX];
}PeoInfo;

//初始化通讯录
void InitContact(contact** con);
//添加通讯录数据
void AddContact(contact** con);
//删除通讯录数据
void DelContact(contact** con);
//展示通讯录数据
void ShowContact(contact* con);
//查找通讯录数据
void FindContact(contact* con);
//修改通讯录数据
void ModifyContact(contact** con);
//销毁通讯录数据
void DestroyContact(contact** con);

2.3 Contact.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Contact.h"
#include"SList.h"
//初始化通讯录

//创建+导入通讯录
void LoadContact(contact** con)
{
	FILE* pf = fopen("contact.txt", "rb");//需要contact.txt先存在，才能打开成功，否则出错
	if (pf == NULL)
		perror("fopen error!\n");
	return 1;

	//循环读取数据
	PeoInfo info;
	while (fread(&info, sizeof(info), 1, pf))
	{
		SLPushBack(con, info);
	}
}

void InitContact(contact** con)
{
	LoadContact(con);
}

//添加通讯录数据
void AddContact(contact** con)
{
	//接下来要获取的数据都是PeoInfo结构体里我们设置的数据
	PeoInfo info;
	printf("请输入要添加的联系人的姓名：");
	scanf("%s", &info.name);//name是数组名--->本来就是地址
	printf("请输入请输入要添加的联系人的性别：");
	scanf("%s", &info.sex);
	printf("请输入要添加的联系人的年龄：");
	scanf("%d", &info.age);//age是int类型的数据--->取地址
	printf("请输入要添加的联系人的号码：");
	scanf("%s", &info.tel);
	printf("请输入要添加的联系人的地址：");
	scanf("%s", &info.addr);
	//数据获取到之后存储到info中
	//接下来，我们需要在单链表中插入数据
	SLPushBack(con, info);//直接调用单链表的尾插
}

//删除通讯录数据
//删除联系人
//由于删除/修改/查找联系人都需要判断联系人是否存在，所以我们把判断联系人是否存在单独写出来
contact* FindByName(contact* con, char name[])
{
	contact* cur = con;
	while (cur)
	{
		if (strcmp(cur->data.name, name) == 0)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void DelContact(contact** con)
{
	//我们需要使用联系人众多信息中的一项来查找联系人是否存在
	//这里直接要求输入联系人的姓名进行查找
	printf("请输入要删除的联系人的姓名：");
	//创建一个name数组存储要输入的姓名
	char name[NAME_MAX];
	scanf("%s", name);
	//调用函数判断联系人是否存在
    //1.存在--->根据返回的下标删除--->即为调用顺序表的删除指定位置的数据
    //2.不存在--->说明要删除的联系人不存在
	contact* pos=FindByName(*con, name);
	//判断是否存在
	if (pos == NULL)
	{
		printf("要删除的联系人不存在！\n");
		return 1;
	}
		SLErase(con, pos);
		printf("删除成功！\n");
}

//展示通讯录数据
void ShowContact(contact* con)
{
	//打印通讯录存储的所有数据
	//为了更加好看--->我们先输出表头
	printf("%-10s %-4s %-4s %15s %-10s\n", "姓名", "性别", "年龄", "联系电话", "地址");
	contact* cur = con;
	while(cur)
	{
		printf("%-10s %-4s %-4d %15s %-10s\n",//表头对齐--->美观
			cur->data.name,
			cur->data.sex,
			cur->data.age,
			cur->data.tel,
			cur->data.addr
		);
		cur = cur->next;
	}
}

//查找通讯录数据
void FindContact(contact* con)
{
	//我们需要使用联系人众多信息中的一项来查找联系人是否存在
    //这里直接要求输入联系人的姓名进行查找
    //创建一个name数组存储要输入的姓名
	char name[NAME_MAX];
	printf("请输入要查找的联系人的姓名：");
	scanf("%s", name);
	//调用函数判断联系人是否存在
    //1.存在--->根据返回的下标查找并打印出来
    //2.不存在--->说明要查找的联系人不存在
	contact* pos = FindByName(con, name);
	//判断是否存在
	if (pos == NULL)
	{
		printf("要查找的联系人不存在！\n");
		return 1;
	}
	else
	{
		printf("%-10s %-4s %-4s %15s %-20s\n", "姓名", "性别", "年龄", "联系电话", "地址");
		printf("%-10s %-4s %-4d %15s %-20s\n",//表头对齐--->美观
			pos->data.name,
			pos->data.sex,
			pos->data.age,
			pos->data.tel,
			pos->data.addr
		);
		printf("查找成功！\n");
	}
}
void ModifyByMenu()
{
	printf("*******************************************\n");
	printf("*******************通讯录******************\n");
	printf("***********1.修改姓名 2.修改性别***********\n");
	printf("***********3.修改年龄 4.修改号码***********\n");
	printf("***********5.修改地址 6.退出修改***********\n");
}

//修改通讯录数据
void ModifyContact(contact** con)
{
	//我们需要使用联系人众多信息中的一项来查找联系人是否存在
	//这里直接要求输入联系人的姓名进行查找
	//创建一个name数组存储要输入的姓名
	char name[NAME_MAX];
	printf("请输入要修改的联系人的姓名：");
	scanf("%s", &name);
	//调用函数判断联系人是否存在
	//1.存在--->根据返回的下标修改
	//2.不存在--->说明要修改的联系人不存在
	contact* pos = FindByName(*con, name);
	//判断是否存在
	if (pos == NULL)
	{
		printf("要修改的联系人不存在！\n");
		return 1;
	}
	else
	{
		int a = -1;
		do {
			ModifyByMenu();
			printf("请选择你的操作：");
			scanf("%d", &a);
			//底层逻辑是顺序表--->在顺序表中修改对应的下标的结构体中的各项数据
			switch (a)
			{
			case 1:
				printf("请输入新的联系人的姓名：");
				scanf("%s",pos->data.name);//name是数组名--->本来就是地址
				break;
			case 2:
				printf("请输入请输入新的联系人的性别：");
				scanf("%s", pos->data.sex);
				break;
			case 3:
				printf("请输入新的联系人的年龄：");
				scanf("%d", &pos->data.age);//age是int类型的数据--->取地址
				break;
			case 4:
				printf("请输入新的联系人的号码：");
				scanf("%s", pos->data.tel);
				break;
			case 5:
				printf("请输入新的联系人的地址：");
				scanf("%s", pos->data.addr);
				break;
			case 6:
				printf("退出修改联系人的界面！\n");
				break;
			default:
				printf("输入有误！请重新输入：");
				break;
			}
		} while (a != 6);
	}
}

//销毁通讯录数据

//先要保存文件的数据，再free
void SaveContact(contact* con)
{
	FILE* pf = fopen("contact.txt", "wb");
	if (pf == NULL)
	{
		perror("fopen error!\n");
		return 1;
	}
	//将通讯录的数据写入文件保存
	contact* cur = con;
	while (cur)
	{
		fwrite(&(cur->data), sizeof(cur->data), 1, pf);
		cur = cur->next;
	}
	
}
void DestroyContact(contact** con)
{
	SaveContact(*con);//传地址
	DestroyContact(con);
}

2.4 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
#include"Contact.h"
//为了界面更加美观--->创建菜单界面
void menu1()
{
	printf("***********************************************\n");
	printf("*********************通讯录********************\n");
	printf("***********1.添加联系人 2.删除联系人***********\n");
	printf("***********3.修改联系人 4.查找联系人***********\n");
	printf("***********5.查看通讯录 6.退出通讯录***********\n");
}
int main()
{
	int a = -1;
	//初始化+创建通讯录
	contact* con=NULL;
	InitContact(&con);
	//一系列操作
	do {
		menu1();
		printf("请选择你的操作：\n");
		scanf("%d", &a);
		switch (a)
		{
		case 1:
			AddContact(&con);
			break;
		case 2:
			DelContact(&con);
			break;
		case 3:
			ModifyContact(&con);
			break;
		case 4:
			FindContact(con);
			break;
		case 5:
			ShowContact(con);
			break;
		case 6:
			printf("退出通讯录界面！\n");
			break;
		default:
			printf("选择错误！请重新选择：\n");
			break;
		}
	} while (a != 6);
	//销毁通讯录
	DestroyContact(&con);
	return 0;
}