本周我主要学习了链表的知识，包括链表的输出与出入、链表的逆向输出、链表的插入节点、链表的删除节点、循环链表；
话不多说，直接展示：
001.创建链表与输出链表
输入：
5
1 2 3 4 5
输出：
1 2 3 4 5
#include <stdio.h>
#include <stdlib.h>//……………………可使用malloc函数
typedef struct FFF //………………typedef可用于，快速表达结构体名的声明
{
int data;
struct FFF *next;
} link;
link *head, *p, *q, *r;
//……………………head：头指针，p：代替指针，r：输入指针
int n;
void creating_lianbiao() //………………创建一个链表
{
head = (link *)malloc(sizeof(link));//…………首先分配一个内存
head->next = NULL;//…………………………在对头指针初始化
p = head;//……………………………………用p代替头指针遍历
for (int i = 0; i < n; i++)
{
r = (link *)malloc(sizeof(link));//………………步骤一致
r->next = NULL;
scanf(“%d”, &r->data);//………………借助r向data中输入元素
p->next = r;//………………………………连接节点
p = p->next;
}
}
int main()
{
scanf(“%d”, &n);
creating_lianbiao();//……………………引用函数
p = head->next;//………………………………用p指针表示头指针的移动
while (p != NULL)
{
q = p;//……………………利用q指针代替p指针，便于释放内存
printf(“%d “, p->data);
p = p->next;//……………………向后移动
free(q);//…………………………………………释放节点内存
}
free(head);//…………………………………………释放头指针内存
}
002.链表的逆置
输入：
输出后：
#include <stdio.h>
#include <stdlib.h>//……………………可使用malloc函数
typedef struct FFF// ………………typedef可用于，快速表达结构体名的声明
{
int data;
struct FFF *next;
} link;
link *head, *p, *q, *r;
//……………………head：头指针，p：代替指针，r：输入指针
int n;
void creating_lianbiao() //………………创建一个链表
{
head = (link *)malloc(sizeof(link));//…………首先分配一个内存
head->next = NULL;//…………………………在对头指针初始化
p = head;//……………………………………用p代替头指针遍历
for (int i = 0; i < n; i++)
{
r = (link *)malloc(sizeof(link));//………………步骤一致
r->next = NULL;
scanf(“%d”, &r->data);//………………借助r向data中输入元素
r->next = head->next;
head->next = r;
//…………直接连接r的下一节点连接头节点（head）的下一节点，
//不断这样做，使用每一次输入的节点连接在头节点之后，从而使得第一个输入的反而在末尾，实现逆向。
}
}
int main()
{
scanf(“%d”, &n);
creating_lianbiao();//……………………引用函数
p = head->next;//………………………………用p指针表示头指针的移动
while (p != NULL)
{
q = p;//……………………利用q指针代替p指针，便于释放内存
printf(“%d “, p->data);
p = p->next;//……………………向后移动
free(q);//…………………………………………释放节点内存
}
free(head);//…………………………………………释放头指针内存
}
003.链表的奇偶分家
2021年12月19日
19:24
1.4 编写程序，输入若干正整数，按从小到大次序建立1个带头结点单链表，设计一个实现单链表分离算法的Split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求Split算法时间复杂性达到O（n）,程序不可存在内存泄漏。
输入格式:
若干正整数。
输出格式:
每个单链表输出占一行，元素间用分隔符->分隔；初始单链表、剩余元素单链表、偶数元素单链表，共3行。
输入样例:
100 2 3 50 2 1 5 8
结尾无空行
输出样例:
1->2->2->3->5->8->50->100
1->3->5
2->2->8->50->100
来自 <PTA | 程序设计类实验辅助教学平台>
/*思路：
利用数组先存入未知个数字，之后再冒泡排序，之后用三个函数创建三个链表，分别输出。*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct sss
{
int data;
struct sss *next;
} LLL;
LLL *head, *p, *q, *r, *ohead, *jhead;
int num[1000];
//…………创建多个链表，关键在于头节点的不同，例如：head、ohead、jhead…………
void maopao(int num[], int n)//………………先对数组冒泡排序
{
int i, j;
int temp;
for (i = 0; i < n – 1; i++)
{
for (j = 0; j < n – 1 – i; j++)
{
if (num[j] > num[j + 1])
{
temp = num[j + 1];
num[j + 1] = num[j];
num[j] = temp;
}
}
}
}
void creat(int num[], int n)//………………创建普通链表
{
head = (LLL *)malloc(sizeof(LLL));
head->next = NULL;
p = head;
int i;
for (i = 0; i < n; i++)
{
r = (LLL *)malloc(sizeof(LLL));
r->next = NULL;
r->data = num[i];
p->next = r;
p = p->next;
}
}
void oocreat(int num[], int n)//………………创建偶数链表
{
ohead = (LLL *)malloc(sizeof(LLL));
ohead->next = NULL;
p = ohead;
int i;
for (i = 0; i < n; i++)
{
if (num[i] % 2 == 0)
{
r = (LLL *)malloc(sizeof(LLL));
r->next = NULL;
r->data = num[i];
p->next = r;
p = p->next;
}
}
}
void jjcreat(int num[], int n)//……………创建奇数链表
{
jhead = (LLL *)malloc(sizeof(LLL));
jhead->next = NULL;
p = jhead;
int i;
for (i = 0; i < n; i++)
{
if (num[i] % 2 != 0)
{
r = (LLL *)malloc(sizeof(LLL));
r->next = NULL;
r->data = num[i];
p->next = r;
p = p->next;
}
}
}
int main()
{
int F = 1, n = 0;
while (scanf(“%d”, &num[n]) != EOF) //…………存入一个数组
{
n++;
}
maopao(num, n);
creat(num, n);
oocreat(num, n);
jjcreat(num, n);
p = head->next;//……………分三次输出
while (p != NULL)
{
q = p;
if (F) {
printf(“%d”, p->data);
F = 0;
} else {
printf(“->%d”, p->data);
}
p = p->next;
}
printf(“\n”);
p = jhead->next;
F = 1;
while (p != NULL)
{
q = p;
if (F) {
printf(“%d”, p->data);
F = 0;
} else {
printf(“->%d”, p->data);
}
p = p->next;
}
printf(“\n”);
F = 1;
p = ohead->next;
while (p != NULL)
{
q = p;
if (F) {
printf(“%d”, p->data);
F = 0;
} else {
printf(“->%d”, p->data);
}
p = p->next;
}
return 0;
}
004.循环链表（约瑟夫问题变形）
2021年12月19日
19:34
编号为1…N的N个小朋友玩游戏，他们按编号顺时针围成一圈，按顺时针次序报数，从第1个人报到第M个人出列；然后再从下个人开始报到第M+1个人出列；再从下一个人开始报到第M+2个人出列……以此类推不断循环，直至最后一人出列。请编写程序按顺序输出出列人的编号。
输入格式:
输入为2个整数，分别表示N、M（1≤N,M,K≤10000）。
输出格式:
输出为一行整数，为出列人的编号。每个整数后一个空格。
输入样例1:
6 3
结尾无空行
输出样例1:
3 1 2 6 4 5
结尾无空行
输入样例2:
10 2
结尾无空行
输出样例2:
2 5 9 6 4 8 7 3 1 10
结尾无空行
输入样例3:
5 1
结尾无空行
输出样例3:
1 3 2 5 4
结尾无空行
来自 <PTA | 程序设计类实验辅助教学平台>
C++：
/*本题思路：
本题思路在于利用两个函数，分别控制创建循环链表、
链表输出：循环链表利用末节点连接头节点，实现循环；
链表输出：连用链表特性实现链表内部循环计数，及时淘汰
部分数字。*/
#include <iostream>//……………………C++万能头
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <bitset>
#include <cctype>
using namespace std;
typedef struct ss
{
int date;
struct ss *next;
} gg;
int i, n, m;
gg *p, *q, *head, *r;
void creating_xunhuan()//…………创建循环链表
{
head = (gg *)malloc(sizeof(gg));
head->next = NULL;
p = head;
for (i = 1; i <=n; i++)//………………先构建一个编号的链表，1~n
{
r = (gg *)malloc(sizeof(gg));
r->next = NULL;
r->date = i;
p->next = r;
p = r;
}
p->next = head->next;//………………使末节点连接头节点，实现头尾相接循环
}
void print() //………………………………执行函数
{
int sum = 0, count = 0;
q = head->next;//………………定义一个新指针代替头指针
while (count != n) //……………………控制淘汰所有人后退出
{
sum++;
if (sum == m)//……………………控制每次淘汰的编号
{
while (q->date == 0)// ………………再次控制跳过已被淘汰的编号，淘汰
sum=m后的出现已淘汰的编号
{
q = q->next;
}
cout << q->date << ” “;
q->date = 0;//………………标记已淘汰的数字为零。
q = q->next;//………………指向下一个
m++;
sum = 0;
count++;
}
else //………………控制跳过已被淘汰的编号
{
while (q->date == 0)
{
q = q->next;
}
q = q->next;
}
}
}
int main()
{
scanf(“%d %d”, &n, &m);
creating_xunhuan();
print();
return 0;
}
C语言：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct SS
{
int data;
struct SS *next;
} LINK;
LINK *p, *head, *q, *r, *pp, *temp;
int n, m;
void creat_lianbiao()
{
head = (LINK *)malloc(sizeof(LINK));
head->next = NULL;
p = head;
r = (LINK *)malloc(sizeof(LINK));
r->next = NULL;
r->data = 1;
p->next = r;
p = p->next;
for (int i = 2; i <= n; i++)
{
r = (LINK *)malloc(sizeof(LINK));
r->next = NULL;
r->data = i;
p->next = r;
p = p->next;
}
p->next = head->next;
}
void panduan()
{
int sum = 0, rr = 0;
pp = head->next;
while (rr != n)
{
sum++;
if (sum == m)
{
while (pp->data == 0)
{
pp = pp->next;
}
printf(“%d “, pp->data);
sum = 0;
rr++;
m++;
pp->data = 0;
pp = pp->next;
}
else
{
while (pp->data == 0)
{
pp = pp->next;
}
pp = pp->next;
}
}
}
int main()
{
scanf(“%d %d”, &n, &m);
creat_lianbiao();
panduan();
return 0;
}
005.单链表基本操作（插入、删除）
2021年12月19日
20:11
请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。
输入格式:
输入第1行为1个正整数n，表示当前单链表长度；第2行为n个空格间隔的整数，为该链表n个元素的数据域值。第3行为1个正整数m，表示对该链表施加的操作数量；接下来m行，每行表示一个操作，为2个或3个整数，格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点，若k=0则表示表头插入。1 k表示删除链表中第k个结点，此时k不能为0。注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。n和m不超过100000。
输出格式:
输出为一行整数，表示实施上述m个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。
输入样例:
5
1 2 3 4 5
5
0 2 8
0 9 6
0 0 7
1 0
1 6
输出样例:
7 1 2 8 3 5
来自 <PTA | 程序设计类实验辅助教学平台>
/*本题思路：
首先创建一个单链表，然后对于插入与删除分别创建一个函数，然后再讨论特殊
情况。插入函数首先找到目标数，然后在目标数后面连接一个数据。
删除函数跳过被删除的数字，实现删除。*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct FFF
{
int data;
struct FFF *next;
} link;
link *p, *q, *r, *mw, *head, *temp, *ed;
int n, nn, sc, cr, crh;
int j = 1;
void creat()//……………………创建一个链表
{
int i;
head = (link *)malloc(sizeof(link));
head->next = NULL;
p = head;
for (i = 0; i < n; i++)
{
r = (link *)malloc(sizeof(link));
r->next = NULL;
scanf(“%d”, &r->data);
p->next = r;
p = r;
}
}
void shangchu()//………………删除函数
{
temp = head->next;//………………设置一个代替头指针的指针
while (j < sc – 1) //………………找到删除位前一个节点
{
temp = temp->next;
j++;
}
mw = (link *)malloc(sizeof(link));
mw = temp->next;
temp->next = mw->next;
//…………思路：定义一个新节点，新节点代替下一个节点的位置，再由下一个节点//指向新指针的下一个节点，即利用新节点架空被删除的节点，再跳过目标点连接链表
j = 1;
}
void charu()//………………插入函数
{
if (crh == 0) //………………特殊情况，插入到第一个节点位置
{
ed = (link *)malloc(sizeof(link));
ed->data = cr;
ed->next = head->next;
head->next = ed;
//………………定义一个新节点，让新节点的下一个节点等于头指针的下一个节点，//再令头指针下一个节点等于新节点，后面节点自动退后。
j=1;
}
else
{
temp = head->next;
while (j < crh) //……………………找到被插入数
{
temp = temp->next;
j++;
}
ed = (link *)malloc(sizeof(link));
ed->data = cr;
ed->next = temp->next;
temp->next = ed;
//…………上同义。
j = 1;
}
}
int main()
{
int F;
scanf(“%d”, &n);
creat();
scanf(“%d”, &nn);
int sum = nn;//………………sum=n也行
for (int i = 0; i < nn; i++)
{
scanf(“%d”, &F);
if (F)
{
scanf(“%d”, &sc);
if (sc > 0 && sc <=sum)
{
shangchu();
sum–;
}
}
else
{
scanf(“%d %d”, &crh, &cr);
if (crh <= sum)
{
charu();
sum++;
}
}
}
p = head->next;
int gg = 1;
while (p != NULL)
{
q = p;
printf(“%d “, p->data);
p = p->next;
free(q);
}
free(head);
return 0;
}