单链表的应⽤

时间：2024-10-16 09:34:50

⽬录

1. 单链表经典算法OJ题⽬

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

———————————————————————————————————————————

正文开始

单链表经典算法

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：分割链表

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

//SList.h
//
// Created by mm on 2023/6/13.
//
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"contact.h"
typedef struct PersonInfo SLTDataType;
//typedef int SLTDataType;
struct SListNode{
struct SListNode* next;
 SLTDataType data;
}
void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
//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);
//contact.c
#define _CRT_SECURE_NO_WARNINGS
#include"contact.h"
#include"SList.h"
void LoadContact(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");
}
void InitContact(contact** con) {
LoadContact(con);//把本地的通讯录数据导⼊到链表结构
}
void AddContact(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, 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) {
 char name[NAME_MAX];
 printf("请输⼊要删除的⽤⼾姓名：\n");
 scanf("%s", name);
 contact* pos = FindByName(*con, name);
 if (pos == NULL) {
 printf("要删除的⽤⼾不存在，删除失败！\n");
 return;
 }
 SLTErase(con, pos);
 printf("删除成功！\n");
}
void ShowContact(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;
 }
}
void FindContact(contact* con) {
 char name[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);
}
void ModifyContact(contact** con) {
 char name[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");
}
void SaveContact(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");
}
void DestroyContact(contact** con) {
 SaveContact(*con);//在通讯录销毁之前，先把历史数据保存到本地⽂件中contact.txt
 SListDesTroy(con);
}

———————————————————————————————————————————

完

相关文章