首页 > 其他 > 详细

单循环链表 解决约瑟夫环的问题

时间:2017-10-10 20:18:58      阅读:216      评论:0      收藏:0      [点我收藏+]

已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

 

#include<stdio.h>
#include<malloc.h>
typedef struct node{
int num;
struct node* next;
}Node;

Node *creat(int n){
Node *p,*q,*head;
p=(Node *)malloc(sizeof(Node));
head = p;
p->num = 1;
for(int i=2;i<=n;i++){
q=(Node *)malloc(sizeof(Node));
q->num = i;
p->next = q;
p = q;
}

p->next = head; //最后一个节点的指针指向头指针,形成循环

return head;
}

void link_process(Node *head,int k,int m){
Node *p =head,*temp;
while(p->num!=k) //使当前指针移动到k的位置
p=p->next;

while(p->next!=p) //p->next == p 时表明这个链表中只剩下一个节点了,结束循环
{
for(int i=1;i<m;i++){
temp = p;
p=p->next;
}
printf("%d",p->num);

temp->next = p->next;
free(p);
p=temp->next;
}

printf("%d",p->num);
free(p);
}

int main(){

int n,m,k;
scanf("%d%d%d",&n,&k,&m);

Node *head = creat(n);

link_process(head,k,m);


return 0;

}

单循环链表 解决约瑟夫环的问题

原文:http://www.cnblogs.com/chenbo820/p/7647104.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!