单链表（含循环单链表）——数据结构预习
C++链表难倒了不少小萌新，今天我来写一下心得，以后忘了还能复习,先讲用malloc和free这一对cp版的单链表吧。
拓展一：
补充c的free和c++的delete的区别：
delete 用于释放new分配的内存，和new成对调用
free 用于释放malloc分配的内存，和malloc成对调用
使用free释放时需要判断指针是否为NULL👀，delete不用
free 释放内存，但不调用对象的析构函数
delete 不仅释放内存，还调用对象的析构函数
delete 和new是对对象的操作，是运算符👀
free 和malloc是对内存空间的操作👀
（这一段参考https://blog.csdn.net/amf12345/article/details/99656492）
拓展二：
SqList *L和SqList * &L的区别（这的Sqlist相当于我的Node）https://www.cnblogs.com/xiang-little/p/5840809.html
不过我一般用结构体指针Link，应该没有上面顾虑那么多
image.png
头指针一定要有，头节点不一定。但是带上头节点好处很多，比如
image.png
头指针数据域没有东西，头节点数据域一般没有东西。链表的有效长度从首元节点算起。
拓展四：
前一节点的next可以看成是下一节点（但在创建节点时不要犯Link s->next=head这样的错误！！！还有偶尔会把next看成一条线）。
拓展五：
头指针是以确定线性表中第一个元素对应的存储位置，一般用于处理数组，链表，队列等数据结构。单链表可以用头指针的名字来命名。单链表中头指针指向头节点。头指针指向上述数据结构的起始数据的指针，如指向数组首地址的指针，指向链表表头节点的指针。
头指针也就是表头指针
在单链表的第一个结点之前附设一个结点（是个结构体），称之为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。头结点的作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。
第一节点，不太清楚，应该是链表有效数据存储的第一个节点吧，就是去除了头结点的第一个节点。（来自https://zhidao.baidu.com/question/1173824466773596459.html）
第一步，弄一个结构体
typedef struct node
{
int data;
struct node* next;
}Node, * Link;//结构体别名，Node等价于 struct node; Link等价于struct node*
第二步，写一个创建链表的函数
Link create()
{
Link head = (Link)malloc(sizeof(Node));//创建头节点,Node不可以改成Link，免得以后操作出错，head是头指针
head->next = NULL;//空表
return head;
}
AQ1E2TR88F(LT[F97P]TB0L.png
当时没做删除操作时，因为Link head = (Link)malloc(sizeof(Node));最后那个Node改为Link发现链表的创建、插入、打印正常，所以觉得三个Link行得通，然后删除操作的free老报错，最后发现是Node改为Link的错误（被某同学嘲讽了QAQ）
插入分两种讲，第三步讲头插法
先补充个东西：假如单链表有相邻三点，从左往右顺序为a，b，c，那么a->next是b，a->next->next是c。
void headadd(Link head, int newdata)
{
Link s = (Link)malloc(sizeof(Node));//创建空节点s
s->data = newdata;
s->next = head->next;//这句和下一句不能弄反,此时s->next=NULL
head->next = s;
}
头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。
简单来说，就是把新加进的元素放在表头后的第一个位置:先让新节点的next指向头点之后（s->next = head->next），然后让表头的next指向新节点（head->next = s，或者说s点放在head后面）。
嗯，用现实环境模拟的话就是插队的方法，始终让新结点插在第一的位置。因此插入的东西打印出来为倒序
image.png
尾插法
void tailadd(Link head, int newdata)
{
Link s = (Link)malloc(sizeof(Node));//创建空节点s
s->data = newdata;
Link r = head;//创建运动节点r，指向head
while (r->next)//要找到NULL前面那点r
{
r = r->next;
}
r->next = s;//从尾部插入
s->next = NULL;
}
嗯，用现实环境模拟的话就是插队的方法，始终让新结点插在最后的位置。尾插法插入的东西打印出来是顺眼的正序。感觉这r尾指针是工具人，但是最后又不能释放掉，释放就报错，为什么😪
image.png
初始化赋值后插入数据
详情见整个代码
按照数值修改数据
详情见整个代码
按照位置修改数据
详情见整个代码
image.png
详情见整个代码
打印链表
void print(Link head)
{
Link temp = head->next;//从第二个节点开始打印
while (temp)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
单链表的销毁
void destroy(Link head)
{
Link p = head;
Link q ;
while (p)
{
q = p->next;//先保留下一点的地址
free(p);
p = q;//此时p已经移动到q的位置，有点像继承遗产
}
head->next = NULL;
}
这里没有头节点，所以只有销毁单链表，没有清空单链表的情况。如果有头节点，销毁（参数是头指针）和清空（参数是头节点）的区别是头指针的保留与否。
……………………………………………………………………………………………………………
整个代码示例（多了头节点略微有点不同，上面都基于没有头节点的情况）
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node
{
int data;
struct node* next;
}Node, * Link;//结构体别名，Node等价于 struct node; Link等价于struct node*
Link create()
{
Link head = (Link)malloc(sizeof(Node));//创建头指针,Node不可以改成Link，免得以后操作出错
Link L = (Link)malloc(sizeof(Node));//创建头节点
head->next = L;
L->next = NULL;//空表
return head;
}
void headadd(Link L, int data)
{
Link s = (Link)malloc(sizeof(Node));//创建空节点s
s->data = data;
s->next = L->next;//和下一句不能弄反,此时s->next=NULL
L->next = s;
}
void tailadd(Link L, int data)
{
Link s = (Link)malloc(sizeof(Node));//创建空节点s
s->data = data;
Link r = L;//创建运动节点r，指向L
while (r->next)
{
r = r->next;
}
r->next = s;//从尾部插入
s->next = NULL;
}
void insert(Link L, int i, int data2)//一般人家插入都是按位置插入的，按值插其前后少见
{ //i从L开始，i>=1
Link p = L;
Link s = (Link)malloc(sizeof(Node));
s->data = data2;
for (int j = 1; j < i; j++)//找到插入位置i的前一个位置，找的方法for循环比while循环更易懂
{
p = p->next;
}
s->next = p->next;
p->next = s;
}
void change1(Link L, int data, int data2)//按值查找
{
Link p = L;
while (p && p->data != data)//直接找到修改点，想修改数据为data的点
{
p = p->next;
}
p->data = data2;//修改data为data2
}
void change2(Link L, int i, int data2)//按位查找
//修改第i个有值点，i>=1
{
Link p = L;
int j = 1;
while (p && j < i)//这个while和上面的while少了一个移动，一般删除和这个一样都是找相应点的前一点
{
p = p->next;
j++;
}
p->next->data = data2;
}
void del1(Link L, int data)//按值查找删除
{
Link p = L;
while (p->next && p->next->data != data)//找到删除点的前一点
{
p = p->next;
}
if (p->next->next == NULL)//如果要删除的是最后一个点
{
free(p->next);//与下面两句不要弄错顺序，因为弄错顺序的意思不一样，如果先指空的话，程序还是没有释放掉该节点空间
p->next = NULL;
}
else
{
Link q = p->next;
p->next = q->next;
free(q);//q为临时节点，用完就释放，不要弄错成释放p
}
}
void del2(Link L, int i)
{
Link p = L;
int j = 1;
while (p && j < i)//找到删除点的前一点
{
p = p->next;
j++;
}
if (p->next->next == NULL)//如果要删除的是最后一个点
{
free(p->next);//与下面两句不要弄错顺序，因为弄错顺序的意思不一样，如果先指空的话，程序还是没有释放掉该节点空间
p->next = NULL;
}
else
{
Link q = p->next;
p->next = q->next;
free(q);//q为临时节点，用完就释放，不要弄错成释放p
}
}
void print(Link L)
{
Link temp = L->next;//从第二个节点开始打印
while (temp)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
void destroy(Link head)
{
Link p = head;
Link q;
while (p)
{
q = p->next;
free(p);
p = q;//此时p已经移动到q的位置，有点像继承遗产
}
}
int main()
{
Link head1 = create();
for (int i = 0; i < 5; i++)
{
int data = i;
headadd(head1->next, data);
}
cout << "链表1创建并赋值后为：";
print(head1->next);
cout << endl << "分别输入链表1插入的位置和插入的值：";
int a, b;
scanf("%d %d", &a, &b);
insert(head1->next, a, b);
print(head1->next);
printf("\n分别输入你要修改的值和修改后的值：");
int n0, n1;
scanf("%d %d", &n0, &n1);
change1(head1->next, n0, n1);
cout << endl << "链表1修改值后为：";
print(head1->next);
cout << endl << "输入你要删去的值：";
int n2;
scanf("%d", &n2);
del1(head1->next, n2);
cout << endl << "链表1删除值后为：";
print(head1->next);
destroy(head1);
cout << "——————————————————————————————————————————————————————" << endl;
Link head2 = create();
for (int i = 5; i < 10; i++)
{
int data = i;
headadd(head2->next, data);
}
cout << "链表2创建并赋值后为：";
print(head2->next);
printf("\n分别输入你要修改的值的位置和修改后的值：");
int j, m1;
scanf("%d %d", &j, &m1);
change2(head2->next, j, m1);
cout << endl << "链表2修改值后为：";
print(head2->next);
cout << endl << "输入你要删去的值的位置：";
int k;
scanf("%d", &k);
del2(head2->next, k);
cout << endl << "链表2删除值后为：";
print(head2->next);
destroy(head2);
return 0;
}
new和delete版的，在原基础上，把
Link head = (Link)malloc(sizeof(Node));
和相应的free
改为
Link head = new Node;
和相应的delete
就行了
题目思考：单链表反转、求未知长度单链表的中间节点
多编程自己才会掌握知识！
循环单链表👀👀👀
循环单链表，与普通单链表的区别就是，单链表的最后一个元素s的next指向空，而循环链表的末尾元素s的next指向头节点（注意，不是指向头指针）
#include "iostream"
using namespace std;
constexpr auto TRUE = 1;
constexpr auto FALSE = 0;
constexpr auto OK = 1;
constexpr auto ERROR = 0;
typedef int Elemtype;
typedef int Status;
typedef struct Node
{
Elemtype data;
struct Node* next;
} Node;
typedef struct Node* Link;
/*
功能：初始化一个循环空链表
*/
Link create()
{
Link head;
head = (Link)malloc(sizeof(Node));
head->next = head;//循环无数据表
return head;
}
/*
功能：创建循环链表
*/
void tailadd(Link head)
{
Link p = head;
int flag = 1;
double c;
while (flag)
{
cin >> c;
if (c != -99999)
{
Link s = (Link)malloc(sizeof(Node));
s->data = c;
s->next = head; // 因为是尾插法，所以申请结点的next指向链表头，构成循环
p->next = s;
p = s;
}
else
{
flag = 0;
}
}
}
/*
功能：循环链表中元素的个数
*/
int getlength(Link head)
{
Link p = head;
int count = 0;
while (p->next != head)
{
count++;
p = p->next;
}
return count;
}
/*
功能：在第 i 个位置插入一个元素
*/
Status insert(Link head, int i, Elemtype e)
{
Link pre = head;
int k = 1;
while (pre && k < i) // 找到第 i-1 个元素
{
pre = pre->next;
k++;
}
if (!pre || k > i || i > getlength(head) + 1)
{
cout << "插入位置错误！" << endl;
return ERROR;
}
else
{
Link s = (Link)malloc(sizeof(Node));
s->data = e;
s->next = pre->next;
pre->next = s;
}
return OK;
}
/*
功能：删除第 i 个元素，并将其值赋给*e
*/
Status del(Link head, int i, Elemtype* e)
{
Link pre = head;
int k = 1;
while (pre && k < i) // 找到第 i-1 个元素
{
pre = pre->next;
k++;
}
if (!pre || k > i || i > getlength(head))
{
cout << "删除位置错误！" << endl;
return ERROR;
}
else
{
Link r = pre->next;
pre->next = pre->next->next;
*e = r->data;
free(r);
}
return OK;
}
/*
功能：查找第 i 个元素，并将查找到的元素放入 *e 中
*/
Status find(Link head, int i, Elemtype* e)
{
Link p = head;
int k = 0;
while (p && k < i) // 找到第 i 个元素
{
p = p->next;
k++;
}
if (!p || k > i || i > getlength(head) || i <= 0)
{
cout << "查找位置错误！" << endl;
return ERROR;
}
else
{
*e = p->data;
}
return OK;
}
/*
功能：打印整个链表
*/
Status print(Link head)
{
Link p;
p = (head)->next;
if (p != NULL)
{
while (p != head)
{
cout << p->data << " ";
p = p->next;
}
}
else
{
cout << "没有元素！" << endl;
return ERROR;
}
cout << endl;
return OK;
}
void main()
{
Link head;
Elemtype e;
cout << "开始初始化..............................................." << endl;
head = create();
cout << "初始化操作完毕！" << endl;
cout << "开始建表，请输入元素：(这里是尾插法建表，输入-99999结束建表)..........." << endl;
tailadd(head);
cout << "建表操作完毕！" << endl;
cout << "打印线性表中的所有数据：";
print(head);
cout << "打印线性表的长度：";
int count = getlength(head);
cout << count << endl;
cout << "-------------------------------------------------" << endl;
cout << "开始插入（在第6个位置插入81）............................" << endl;
insert(head, 6, 81);
cout << "插入操作完毕！" << endl;
cout << "打印线性表中的所有数据：";
print(head);
cout << "打印线性表的长度：";
int count2 = getlength(head);
cout << count2 << endl;
cout << "-------------------------------------------------" << endl;
cout << "开始删除（这里删除第2个元素）............................" << endl;
del(head, 2, &e);
cout << "删除操作完毕!" << endl;
cout << "删除后打印线性表中的所有数据：";
print(head);
cout << "-------------------------------------------------" << endl;
cout << "开始查找（这里查找第5个元素）............................." << endl;
if (find(head, 5, &e))
{
cout << "查找操作完毕!" << endl;
cout << "打印查找到的数据：";
cout << e << endl;
}
else
{
cout << "查找位置错误！" << endl;
}
system("pause");
}
void headadd(Link head)
{
int flag = 1;
double c;
while (flag)
{
cin >> c;
if (c != -99999)
{
Link s = (Link)malloc(sizeof(Node));
s->data = c;
s->next = head->next;
head->next = s;
}
else
{
flag = 0;
}
}
}
实际应用：约瑟夫环问题
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（以编号1，2，3，…，n分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。
例如有 5 个人，要求从编号为 3 的人开始，数到 2 的那个人出列：
image
出列顺序依次为：
编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
最后只剩下 5 自己，所以 5 出列。
作者：小Q_wang
链接：https://www.jianshu.com/p/24734b20c81b
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int number;
struct node* next;
}person;
person* initLink(int n) {
person* head = (person*)malloc(sizeof(person));
head->number = 1;
head->next = NULL;
person* cyclic = head;
int i;
for (i = 2; i <= n; i++) {
person* body = (person*)malloc(sizeof(person));
body->number = i;
body->next = NULL;
cyclic->next = body;
cyclic = cyclic->next;
}
cyclic->next = head;//首尾相连
return head;
}
void findAndKillK(person* head, int k, int m) {
person* tail=NULL;//一般指针定义都要初始化，免得有未知错误，这里不初始化就有错
person* p = head;
//找到编号为k的人
while (p->number != k) {
tail = p;//tail为删除点前一点
p = p->next;
}
//从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
while (p->next != p) {
int i;
//找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。
for (i = 1; i < m; i++) {
tail = p;
p = p->next;
}
tail->next = p->next;//从链表上将p结点摘下来，过了这一句此时是tail->next是原来的p->next
printf("出列人的编号为:%d\n", p->number);
free(p);
p = tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
}
printf("出列人的编号为:%d\n", p->number);
free(p);
}
int main() {
printf("输入圆桌上的人数n:");
int n;
scanf("%d", &n);
person* head = initLink(n);
printf("从第k人开始报数(k>1且k<%d)：", n);
int k;
scanf("%d", &k);
printf("数到m的人出列：");
int m;
scanf("%d", &m);
findAndKillK(head, k, m);
return 0;
}
代码略改动
单链表逆转https://blog.csdn.net/LMengi000/article/details/79130114
