【C语言】约瑟夫环(用单向循环链表解决)

时间:2021-10-04 20:30:46

约瑟夫环:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。这里我用单向循环链表来解决这个问题。

我们先考虑几种情况:

当m=1和k=1的时候,要挨个删除链表中的结点。

在k!=1和m=1的情况下,指针必须先向后移动到k的位置,并且记住k的前驱结点,以便删除结点不断链。

在k!=1和m!=1的情况下,此处我只让指针移动到了要删除结点的前驱结点处进行删除。

注意这里的每一种情况都没有完全的把链表删除,链表中还剩下一个 结点,即没有出列的那个人,我在这里依然将它输了出来。

代码如下:

#define _CRT_SECURE_NO_WARNINGS 1 
#ifndef _JOSEPH_H__
#define _JOSEPH_H__

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef struct Joseph_ring
{
int num;
struct Joseph_ring* next;
}Joseph,*pJoseph;

pJoseph CreateJoseph(int n);
void joseph_r(pJoseph head, int k, int m);

#endif
函数实现:

#include"Joseph ring.h"

pJoseph CreateJoseph(int n)
{
int i = 0;
pJoseph head = NULL;
pJoseph tail = NULL;
head = (pJoseph)malloc(sizeof(Joseph));
head->next = head; //先让第一个结点head指向自己形成一个环
head->num = 1;
tail = head;
for (i = 2; i <= n; i++) //循环向环中插入结点
{
pJoseph New = (pJoseph)malloc(sizeof(Joseph));
New->num = i;
New->next = tail->next;
tail->next = New;
tail = New;
}
return head;
}

void joseph_r(pJoseph head, int k, int m)
{
assert(head);
pJoseph cur = NULL;
pJoseph prev = NULL;
pJoseph del = NULL;
cur = head;
if (k == 1 && m == 1) //如果从第一个人开始,数到1就出列。
{
while (cur->next != head)
{
printf("%d ", cur->num);
del = cur;
cur = cur->next;
free(del);
}
printf("%d\n", cur->num);
}

else if (k != 1 && m == 1) //从第k个人开始报数,报到1的人出列。
{
while (cur->num != k)//找到第k个人的前一个
{
prev = cur;
cur = cur->next;
}
while (head->next != head)
{
del = cur;
prev->next = cur->next;
cur = cur->next;
printf("%d ", del->num);
if (cur == head)
{
head = cur->next;
}
free(del);
}
printf("%d\n", head->num);
}
else
{
int i = 0;
while (cur->num != k)//找到第k个人,从他开始报数
{
cur = cur->next;
}
while (head->next != head)
{
for (i = 1; i < m - 1; i++) //找到要出列的人的前一个
{
cur = cur->next;
} //cur当前表示要出列的人的前一个
del = cur->next;
cur->next = del->next;
printf("%d ", del->num);
if (del == head)
{
head = del->next;
}
free(del);
cur = cur->next;
}
printf("%d\n", head->num);
}
}
测试部分:

#include"Joseph ring.h"

void test1()
{
pJoseph head;
head = CreateJoseph(10);
joseph_r(head, 1, 1);
}

void test2()
{
pJoseph head;
head = CreateJoseph(10);
joseph_r(head, 2, 1);
}
int main()
{
pJoseph head;
test1();
test2();
head=CreateJoseph(10);
joseph_r(head, 2, 2);
getchar();
return 0;
}
那么测试的结果是什么呢?

【C语言】约瑟夫环(用单向循环链表解决)