网站设计广州,在手机上如何制作网站,哪个平台免费招人最快,0735郴州新网招聘目录 1.循环链表的定义 2.约瑟夫环问题 3.创建循环链表 4.删除节点操作 5.打印所有节点 6.实现约瑟夫环问题的完整程序代码 #x1f308;嗨#xff01;我是Filotimo__#x1f308;。很高兴与大家相识#xff0c;希望我的博客能对你有所帮助。 #x1f4a1;本文由Filotimo_… 目录 1.循环链表的定义 2.约瑟夫环问题 3.创建循环链表 4.删除节点操作 5.打印所有节点 6.实现约瑟夫环问题的完整程序代码 嗨我是Filotimo__。很高兴与大家相识希望我的博客能对你有所帮助。 本文由Filotimo__✍️原创首发于CSDN。 如需转载请事先与我联系以获得授权⚠️。 欢迎大家给我点赞、收藏⭐️并在留言区与我互动这些都是我前进的动力 我的格言森林草木都有自己认为对的角度。 1.循环链表的定义
循环链表与常规链表的区别在于其尾节点指向头节点形成一个环形结构。循环链表可以分为单向循环链表和双向循环链表两种类型。
单向循环链表的定义为每个节点包含一个数据元素和指向下一个节点的指针而最后一个节点的指针会指向第一个节点形成一个环形结构。
双向循环链表的定义为每个节点包含一个数据元素以及两个指针一个指向前一个节点一个指向后一个节点而第一个节点的前驱指针指向最后一个节点最后一个节点的后继指针指向第一个节点也形成了一个环形结构。
这种结构使得循环链表可以从任意节点开始遍历并且可以方便地在链表中插入或删除节点。它可以通过不断重复遍历整个链表来实现循环的效果。
2.约瑟夫环问题
约瑟夫环问题是一个经典的数学问题假设 n 个人站成一个环状从第一个人开始报数每次报到 m 的人出列再从下一个人开始重新报数直到所有人都出列。最后剩下的人的编号即为最后的获胜者。
解决约瑟夫环问题的步骤设定问题的输入为n个人和要出局的报数m
1. 将n个人编号为1到n。 2. 从第一个人开始报数报到m的人出局。 3. 从出局的人的下一个人开始重新报数继续报到m的人出局。 4. 重复第3步直到只剩下一个人为止。
3.创建单向循环链表
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;// 创建 n-1 个节点并连接成循环链表for (int 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;
}
定义一个名为person的结构体由整型变量number和指向下一节点的指针next构成。
函数initlink用于初始化一个循环链表表示圆桌上的人。函数首先创建一个头节点然后使用for循环创建其他的节点并连接成循环链表。最后返回头节点。
这段代码用于创建一个循环链表其中头节点的number字段表示第一个人在圆桌上的位置后续节点的number字段按顺序递增最后一个节点的next字段指向头节点形成一个循环链表结构。
4.约瑟夫环求解过程
// 找到第 k 个人并开始报数数到第 m 个人出列
void findandkillk(person* head, int k, int m) {person* tail head;while (tail-next ! head) {tail tail-next;}person* p head;while (p-number ! k) {tail p;p p-next;}// 从第 k 个人开始报数直到只剩下一个人while (p-next ! p) {for (int i 1; i m; i) {tail p;p p-next;}// 删除第 m 个人出列并释放内存tail-next p-next;printf(出列人的编号为: %d\n, p-number);person* temp p;p p-next;free(temp);}printf(出列人的编号为: %d\n, p-number);free(p);
}从第k个人开始报数每次报到第m个人就将其出列。
先用循环找到链表中的尾节点即满足tail-next head的节点。
再用循环找到链表中编号为k的节点并在找到之前更新尾节点的位置。
再用循环进行报数和出列操作直到链表中只剩下最后一个人。循环中的内层循环每次进行m-1次迭代找到第m个人之前的节点并更新尾节点的位置。随后删除第m个人并释放其内存。外层循环在每次迭代之后更新当前节点的位置并继续进行报数和出列操作。
最后输出剩下的最后一个人的编号并释放其内存。
5.实现约瑟夫环问题的完整程序代码
#include stdio.h
#include stdlib.htypedef 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;// 创建 n-1 个节点并连接成循环链表for (int 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;
}// 找到第 k 个人并开始报数数到第 m 个人出列
void findandkillk(person* head, int k, int m) {person* tail head;while (tail-next ! head) {tail tail-next;}person* p head;while (p-number ! k) {tail p;p p-next;}// 从第 k 个人开始报数直到只剩下一个人while (p-next ! p) {for (int i 1; i m; i) {tail p;p p-next;}// 删除第 m 个人出列并释放内存tail-next p-next;printf(出列人的编号为: %d\n, p-number);person* temp p;p p-next;free(temp);}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;
}
代码中的主要函数有initlink和findandkillk。
initlink函数根据输入的人数 n初始化一个循环链表。循环链表中的每个节点都存储一个人的编号编号从 1 到 n。该函数返回链表的头节点指针。
findandkillk函数用于解决约瑟夫环问题。它接收初始化好的循环链表的头节点指针起始编号 k 和报数间隔 m 作为参数。首先它找到从第 k 个人开始报数的位置并且记录该位置的上一个节点即tail。接着通过迭代法每次报数到第 m 个人时将其从链表中删除并释放相应的内存空间。直到链表中只剩一个节点时停止迭代并输出最后剩下的那个人的编号。
在main函数中用户输入要解决的约瑟夫环问题的相关参数然后调用findandkillk函数进行求解。
程序截图如下
