第28讲：单链表的应用-育师

单链表经典算法OJ题目
1. 单链表相关经典算法OJ题1：移除链表元素
2. 单链表相关经典算法OJ题2：反转链表
3. 单链表相关经典算法OJ题3：合并两个有序链表
4. 单链表相关经典算法OJ题4：链表的中间结点
5. 循环链表经典应用-环形链表的约瑟夫问题
6. 单链表相关经典算法OJ题5：分割链表
基于单链表再实现通讯录项目

单链表经典算法

1. 链表经典算法OJ题目

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

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

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

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

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

著名的Josephus问题

据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而 Josephus 和他的朋友并不想遵从，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

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

基于单链表再实现通讯录项目

`SList.h`

//SList.h//// Created by mm on 2023/6/13.//#include<stdio.h>#include<stdlib.h>#include<assert.h>#include"contact.h"typedefstructPersonInfoSLTDataType;//typedef int SLTDataType;structSListNode{structSListNode*next;SLTDataType data;}voidSLTPrint(SLTNode*phead);//头部插入删除/尾部插入删除voidSLTPushBack(SLTNode**pphead,SLTDataType x);voidSLTPushFront(SLTNode**pphead,SLTDataType x);voidSLTPopBack(SLTNode**pphead);voidSLTPopFront(SLTNode**pphead);//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x);//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x);//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos);//在指定位置之后插入数据voidSLTInsertAfter(SLTNode*pos,SLTDataType x);//删除pos之后的节点voidSLTEraseAfter(SLTNode*pos);//销毁链表voidSListDesTroy(SLTNode**pphead);

`contact.h`

//contact.h#pragmaonce#defineNAME_MAX100#defineSEX_MAX4#defineTEL_MAX11#defineADDR_MAX100//前置声明typedefstructSListNodecontact;//用户数据typedefstructPersonInfo{charname[NAME_MAX];charsex[SEX_MAX];intage;chartel[TEL_MAX];charaddr[ADDR_MAX];}PeoInfo;//初始化通讯录voidInitContact(contact**con);//实际调用的是链表的初始化接口（可以简单做一个头结点的初始化）//添加通讯录数据voidAddContact(contact**con);// 链表尾插/头插//删除通讯录数据voidDelContact(contact**con);//链表的删除指定位置的数据//展示通讯录数据voidShowContact(contact*con);//链表的打印//查找通讯录数据voidFindContact(contact*con);//修改通讯录数据voidModifyContact(contact**con);//销毁通讯录数据voidDestroyContact(contact**con);

`contact.c`

#define_CRT_SECURE_NO_WARNINGS#include"contact.h"#include"SList.h"voidLoadContact(contact**con){FILE*pf=fopen("contact.txt","rb");if(pf==NULL){perror("fopen error!\n");return;}//循环读取文件数据PeoInfo info;while(fread(&info,sizeof(info),1,pf)){SLTPushBack(con,info);}printf("历史数据导入通讯录成功！\n");}voidInitContact(contact**con){LoadContact(con);//把本地的通讯录数据导入到链表结构}voidAddContact(contact**con){PeoInfo info;printf("请输入姓名：\n");scanf("%s",&info.name);printf("请输入性别：\n");scanf("%s",&info.sex);printf("请输入年龄：\n");scanf("%d",&info.age);printf("请输入联系电话：\n");scanf("%s",&info.tel);printf("请输入地址：\n");scanf("%s",&info.addr);SLTPushBack(con,info);printf("插入成功！\n");}contact*FindByName(contact*con,charname[]){contact*cur=con;while(cur){if(strcmp(cur->data.name,name)==0){returncur;}cur=cur->next;}returnNULL;}voidDelContact(contact**con){charname[NAME_MAX];printf("请输入要删除的用户姓名：\n");scanf("%s",name);contact*pos=FindByName(*con,name);if(pos==NULL){printf("要删除的用户不存在，删除失败！\n");return;}SLTErase(con,pos);printf("删除成功！\n");}voidShowContact(contact*con){printf("%-10s %-4s %-4s %15s %-20s\n","姓名","性别","年龄","联系电话","地址");contact*cur=con;while(cur){printf("%-10s %-4s %-4d %15s %-20s\n",cur->data.name,cur->data.sex,cur->data.age,cur->data.tel,cur->data.addr);cur=cur->next;}}voidFindContact(contact*con){charname[NAME_MAX];printf("请输入要查找的用户姓名：\n");scanf("%s",name);contact*pos=FindByName(con,name);if(pos==NULL){printf("要查找的用户不存在，查找失败！\n");return;}printf("查找成功！\n");printf("%-10s %-4s %-4d %15s %-20s\n",pos->data.name,pos->data.sex,pos->data.age,pos->data.tel,pos->data.addr);}voidModifyContact(contact**con){charname[NAME_MAX];printf("请输入要修改的用户名称:\n");scanf("%s",&name);contact*pos=FindByName(*con,name);if(pos==NULL){printf("要查找的用户不存在，修改失败！\n");return;}printf("请输入要修改的姓名：\n");scanf("%s",pos->data.name);printf("请输入要修改的性别：\n");scanf("%s",pos->data.sex);printf("请输入要修改的年龄：\n");scanf("%d",&pos->data.age);printf("请输入要修改的联系电话：\n");scanf("%s",pos->data.tel);printf("请输入要修改的地址：\n");scanf("%s",pos->data.addr);printf("修改成功！\n");}voidSaveContact(contact*con){FILE*pf=fopen("contact.txt","wb");if(pf==NULL){perror("fopen error!\n");return;}//将通讯录数据写入文件contact*cur=con;while(cur){fwrite(&(cur->data),sizeof(cur->data),1,pf);cur=cur->next;}printf("通讯录数据保存成功！\n");}voidDestroyContact(contact**con){SaveContact(*con);//在通讯录销毁之前，先把历史数据保存到本地文件中contact.txtSListDesTroy(con);}