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：分割鏈表
1.1 移除鏈表元素
沒要求在原地完成移除元素操作。
新鏈表不創建新的空間，只需要創建兩個頭尾指針，輔助完成鏈表內部結點指向的更改。
1.2 反轉鏈表
思路1：遍歷+頭插
思路2：三指針
傳遞給head的實參在函數調用結束后，依然指向Node1——傳值調用。
需要用在主調函數內使用主調函數內的head，接收函數調用的返回值。
1.3 合并兩個有序鏈表
思路1：將L2插入到L1中，過程中的控制比較復雜。
思路2：創建新鏈表L3，誰小誰尾插。
1.4 鏈表的中間結點
雙指針法：源宿指針、快慢指針、……
1.5 環形鏈表的約瑟夫問題
圖解分析。
1.5.1 新建結點
typedef struct ListNode ListNode;
ListNode* BuyNode(int x){ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));//可寫可不寫，一般不會申請失敗//if(newNode == NULL){// exit(1);//}newNode->val = x;newNode->next = NULL;return newNode;
}
1.5.2 新建環形鏈表
ListNode* createList(int n){ListNode* phead = BuyNode(1);ListNode* ptail = phead;for (int i = 2; i <= n; i++){ptail->next = BuyNode(i);ptail = ptail->next;}//鏈表要首尾相連，使其循環起來ptail->next = phead;return phead;
}
1.5.3 約瑟夫問題
int ysf(int n, int m ) {//創建不帶頭單向循環鏈表ListNode* head = createList(n);ListNode* pcur = head;ListNode* prev = NULL;//count==m就刪除當前結點，并重置count，繼續遍歷遞增int count = 1; //一開始pcur指向head，count就應該數了1//逢m刪除節點while (pcur->next != pcur) { //循環條件：不止一個結點if(count == m){//刪除當前節點pcur,prev->next = pcur->next;free(pcur);//刪除pcur節點之后，要讓pcur走到新的位置，count置為初始值pcur = prev->next;count = 1;}else{//pcur往后走prev = pcur;pcur = pcur->next;count++;}}//此時pcur結點就是幸存下來的唯一的一個節點return pcur->val;
}
提交代碼。
但是自測運行。
問題：若m = 1時，第一次進循環就要刪除pcur，而此時prev還是為空？
解決辦法: createList方法不返回頭結點，而是返回尾結點。既能知道第一個節點的前驅節點，也能夠通過尾結點找到第一個節點。
1.6 分割鏈表
思路1：創建一個新鏈表，將原鏈表中小于x的結點頭插，大于等于x的結點尾插。
思路2：創建兩個新鏈表，一個大鏈表，一個小鏈表，遍歷插入完后，小鏈表尾插大鏈表。
數組的分割可以從兩邊向中間遍歷，左下標遇到大于等于x的就停下，右下標遇到小于x的就停下，然后交換數據，繼續往中間走，while(left <?right)。
2. 基于單鏈表再實現通訊錄項目
2.1 單鏈表頭文件
//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;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);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
#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);SListDesTroy(con);
}完
