关于约瑟夫环问题的链表实现 - 黑马程序员技术交流社区

/*
对于这个题目，大家既然都可以用数组循环的方式来解决，那么对基本的解决思想是有的，而用数组和链表的区别是：使用数组最大的障碍是下标，因为下标的连续性，导致我们无法判定活着的下一个人在什么位置，而需要遍历当前的人员后边的每一个位置，直到这个人是活的，才参与报数。而使用双向链表的优势在于，每个节点都记录的自己的前一个人的地址是什么，后一个人的地址是什么，便于直接访问。
*/
#include <stdio.h>
#include <stdlib.h>
int main(int argc, const char * argv[]) {
struct people{
int num; //当前人员的号码
struct people *top;//当前人员的前一个人员
struct people *next;//当前人员的后一个人员
};//声明一个结构体
typedef struct people Note;
int N=13,q=3;//N是总人数q是喊到q的人被杀
Note *head,*tail,*pnew,*topNote,*nextNote;
//head 链表的头
//head 链表的尾
//pnew 新添加的元素
//topNote 上一个元素
//nextNote 下一个元素
head=(Note *)malloc(sizeof(Note));//创建头指针
head->next=NULL;//头指针的下一个地址是空的，可以相当于一个人的时候
head->num=1;//当前的人的编号
tail=head;//尾指针指向头指针
for (int i=2; i<=N; i++) { //初始化链表。为了便于人员编号循环从2开始
pnew=(Note *)malloc(sizeof(Note));//创建当前人员
pnew->num=i; //人员的编号
pnew->top=tail;//新的人员进入链表之后，这个人员的前一个人就是原来链表的最后一个人
pnew->next=NULL;//新的人员的后边没有人，复制NULL
tail->next=pnew;//原链表中的后边一个人成了新添加的人员
tail=pnew;//新的人员进入链表之后，链表的尾指针指向新添加的人员，形成新的链表
}
tail->next=head; //链表尾部的下一个节点指向头指针
head->top=tail;//链表头部的上一个节点指向尾指针完成环形链表
//如果这里有疑问，可以打印出连表中每个节点Top next num 和地址，看于想象的是否相同
pnew=tail;//杀人游戏开始，当前节点指向尾指针，因为从头指针还是报数，我们认为尾指针是0
for (int i=1; i<N; i++) {//循环N-1次，循环一次杀一人
for (int j=0; j<q; j++) {//循环q次，找到被杀人员pnew
pnew=pnew->next;
}
topNote=pnew->top;//找出被杀人员的上一个人员
topNote->next=pnew->next;//上一个人员的后边一个人，变成当前人员的后一个人。用数字来表示1 2 3,假设被杀的人员是2号，那么2号的上一个人员（也就是1号）他的右边的人员变成了2号右边的人员。下边相同
nextNote=pnew->next;//找出被杀的下一个人员
nextNote->top=pnew->top;//注释同上
free(pnew);//释放当前空间
pnew=topNote;//当前人员的上一个人员变成上一个活着的人
}
printf("存活的人员编号是：%d\n",pnew->num);//最后链表中只剩一个节点，为了验证，我们做以下操作
printf("下一个活着的人员的编号是：%d\n",pnew->next->num);
printf("上一个活着的人员的编号是：%d\n",pnew->top->num);
return 0;
}

复制代码

public static void yuesefu(int totalNum, int countNum) {
18 // 初始化人数
19 List<Integer> start = new ArrayList<Integer>();
20 for (int i = 1; i <= totalNum; i++) {
21 start.add(i);
22 }
23 //从第K个开始计数
24 int k = 0;
25 while (start.size() >0) {
26 k = k + countNum;
27 //第m人的索引位置
28 k = k % (start.size()) - 1;
29 // 判断是否到队尾
30 if (k < 0) {
31 System.out.println(start.get(start.size()-1));
32 start.remove(start.size() - 1);
33 k = 0;
34 } else {
35 System.out.println(start.get(k));
36 start.remove(k);
37 }
38 }

复制代码

#include <stdio.h>
/*
程序总体思路：
用一个数组存储每个人的编号，然后按顺序报数，每数到3该人的编号变为0，并且好人的数量加1.
当到达数组尾部时再从数组头部开始报数，这个时候数组中有些人的编号为0，当到达编号为0的人时，
此人不报数，直接跳到下一个人，以此类推。当好人数量达到14时，数组就只有一个非零数了，这个编号
的人就是叛徒。
*/
int main()
{
//变量good_man用来存储好人个数
int good_man = 0;
//创建一个容量为15的数组
int arr[15];
//变量flag用来记录
int flag = 0;
//对数组中的每个人编号，
for (int i = 0; i < 15; i++) {
//由于数组是从0开始的，而此题编号从1开始，所以编号是i+1
arr[i] = i+1;
}
//定义一个遍历数组的循环变量j
int j = 0;
//当好人数量不是14的时候进行循环
while (good_man != 14)
{
//如果某人的编号不为零，则flag加1
if (arr[j] != 0) {
flag++;
}
/*如果flag的值为3，则此人是好人，将此人的编号设为0，
并且将好人加1。最后把flag重置为0.
*/
if (flag == 3) {
arr[j] = 0;
flag = 0;
good_man++;
}
//循环变量自增
j++;
//如果j到达数组尾部，则让j回到数组头部去
if (j == 15) {
j = 0;
}
}
//打印数组中唯一一个编号非零的人，这个人就是叛徒
for (int k = 0; k < 15; k++)
{
if (arr[k] != 0)
{
printf("出卖耶稣是第%d个人\n",arr[k]);
}
}
return 0;
}
/*这个程序也可以用单向循环链表实现：每数到3将相应的元素从链表中移除*/

复制代码