约瑟夫循环的顺序表实现和循环单链表实现
约瑟夫循环问题想必知道,我直接在代码中说如何实现:
1.顺序表:
# include <iostream>
using namespace std;
int main() {
int m, n,sum,count=0,i=0;
cout << "请输入总人数和第几个人要离开:" << endl;
cin >> n >> m;
sum = n; //sum为剩余人数
int *a = new int[n];
int *flag = new int[n];
for (int j= 0; j < n; j++) { //给每一个人赋值1、2、3、4.....
a[j] = j+1; flag[j] = 1; //设计离开标记,初始值全是1,谁离开更改其值为0,以避免重复计数
}
cout << "离开的顺序如下:" << endl;
while (sum) { //当剩余人数为零时结束循环
if (flag[i]) {
count++; //当离开标记为真,此人未离开,计数器加一
if (count == 3) {
flag[i] = 0; //当计数器到3时,标记此人离开
cout << a[i] << endl;
count = 0; //令count=0,清空计数器,重新计数
sum--; //当有人离开时,求剩余人数
}
}
if (i == n - 1) { //当每次到最后一位元素时,令i=0实现新的一圈的开始
i = 0; continue;
}
i++; //下标后移,无论每次的操作如何,事实上,都会把每一人遍历到,
}
system("pause");
return 0;
}
2.循环单链表:
# include <iostream>
using namespace std;
struct circle
{
int number;
struct circle *next;
};
int main()
{
int m, n, flag = 1, sum = 10;
cout << "输入第几个人退出和总人数:" << endl;
cin >> m >> n;
struct circle *p = new circle;
struct circle *head, *q;
head = p; //记录头指针的位置
p->number = 1;
for (int i = 2; i <= n; i++) { //给创建链表并初始化
q = new circle;
q->number = i;
p->next = q;
p = q;
}
p->next = head; //令尾指针等于头指针,其实头指针事实上就是尾指针,下图(1)
p = p->next; //继续将工作指针传到下一个节点即尾指针,下图(2)
while (p->next != p) { //如果工作指针的next指向自己即该循环链表中只有一个节点了,下图(3)
if (flag == m - 1) { //***************当需要执行删除操作时(找到指向将删节点的前一个节点的指针)
flag = 1; //清零计数器重新计数
cout << p->next->number << endl; //打印被删除的成员
p->next = p->next->next; //删除该节点
p = p->next; //工作指针继续移动
}
else {
p = p->next; //**************当不需要执行删除操作时:计数器加一,工作指针后移
++flag;
}
}
cout << p->number << endl; //打印最后一个人
system("pause");
return 0;
}