带密码的约瑟夫环的解题思路
题目:
编号为1,2,…,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。
学完链表后面的题目,最后一题就是要求用链表实现约瑟夫环带密码的问题。
很明显建立一个循环链表可以实现我们想要的结果。
单循环链表的建立与单链表的建立一样,只是将尾结点的指针域指向头指针所在的地址。
声明一个人的结构体,每个人有自己的编号和所携带的密码,所以:
struct node
{
int position; //位置
int m; //所持密码
struct node *next;
};
建立单循环链表:
void CreateList(node **head, int n) //数据录入与单循环链表的建立
{
node *p1, *p2;
int i = 1;
p1 = p2 = (node *)malloc(sizeof(node));
(*head)->next = p1; //头指针的指针域指向第一个结点
while(n--)
{
scanf("%d",&p1->m);
p1->position = i;
p2->next = p1; //指向新的
p2 = p1;
p1 = (node *)malloc(sizeof(node)); //新的节点
i++; //人数
}
p2->next = *head; //尾结点指向头结点
}
录入数据后,建立好了一个单循环链表。
接下来是主函数:
int main()
{
int n, M;
int i, k = 1;
node *head;
node *p1, *p2, *pf = NULL;
if( (head = (node *)malloc(sizeof(node))) == NULL)
exit(1);
printf("n = ");
scanf("%d", &n);
CreateList(&head, n); //循环链表数据录入
printf("第一次报数上限 m = ");
scanf("%d",&M);
printf("出列顺序为: ");
p1 = head;
while(n != 0)
{
for(i = 1; i <= M; i++) //经过这一步,p1指向了即将要被踢出的那个人
{
p1 = p1->next; //结点移动
if(p1 == head)
p1 = p1->next; //循环了一遍之后,下个人从1开始数
if(i == M - 1) //记录被踢出的结点左边结点
p2 = p1;
}
free(pf); //释放被踢出的那个人所在的位置
M = p1->m; //密码值的更换
printf("%d ",p1->position); //输出被提出的那个人的位置
p2->next = p1->next; //重新连接链表
n--;
}puts("");
system("pause");
return 0;
}
实现的过程:
通过for循环,使得链表指针指到将要被踢出人所在的位置,踢出可以理解为释放掉那个人在的位置,并且把被释放的结点左右结点接合起来,再次形成链式结构。
测试情况:
编译环境:vs2010
如有错误,欢迎指出。