约瑟夫环---链表法

上机题目：约瑟夫环

解题思路：生成单项循环链表当给定 n 值和密码后，首先应当生成单项循环链表，第一个结点的插入和其它结点的插入方法有所不同。某人的出列操作即为结点的删除操作：注意删除最后一个结点和删除其余结点的情况不同。并且设置一个计数器来存放链表中结点个数。

源代码： #include #include #include

#define NULL 0

#define LEN sizeof(struct josephus)

struct josephus{//结构体 };

int n; int key;

struct josephus * creat(void){//创建函数 struct josephus * p1, * p2; struct josephus * head; printf(\"请输入参与游戏的人数：\");

scanf(\"%d\

p1=p2=(struct josephus *)malloc(LEN);//开辟新单元 head=NULL; int i;

for(i=1;i<=n;++i){ if(i == 1){

p1->number=i; head=p1;

printf(\"请输入第一个人的密码：\");

int number; int code;

struct josephus * next;

scanf(\"%d\

}//头指针进行特殊操作并使p1指向head else{

p2->next=p1;

p1->number=i;

printf(\"请输入下一个人的密码：\"); scanf(\"%d\

}

}//依次赋值

p2=p1; p1=(struct josephus * )malloc(LEN); }

p2->next=head; return (head);

int m;

void main(){ struct josephus *p,*q;

struct josephus *head; int count; head=creat(); //调用创建链表函数 }

输出效果：

p=head;

printf(\"输入第一个报数上限值：\");

scanf(\"%d\

for(int i=1;ip=p->next; key=p->code;

printf(\"\\n\");

printf(\"依次退出比赛的编号是：\"); count=1; while(n!=1){ }

printf(\"\\n\");

printf(\"最后一个退出游戏的编号为：\"); printf(\"%d\\n\

while(count+1 != key){ p=p->next;//依次往后指 count++; }

q=p->next; //删除操作

p->next=q->next;

printf(\"%4d\输出编号 key=q->code; free(q); n--;

count=0;