1、实验原理node
约瑟夫问题描述：编号为1，2，……，n的n我的按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数做为报数的上限值m，从第一我的开始按顺时针方向自1开始顺序报数直到报m的人，将此人删除，并将他的密码做为新的m值，从他在顺时针方向上的下一我的开始从新从一报数，……，如此下去，直到全部人所有出列为止。 实现：利用单向循环链表存储结构模拟约瑟夫环，按照出列的顺序打印出各人的编号和此人对应的密码。函数
2、参考程序spa
#include <stdio.h>指针
#include <stdlib.h>code
/*--------------------------结构体------------*/io
typedef struct Lnode /* 结点的结构定义 */ 原理
{ int num; /* 编号子域 */List
int sm; /* 密码子域 */循环
struct Lnode *next; /* 指针域 */ 程序
}Lnode,*LinkList;
/* 函数声明 */
LinkList creat();
void print1(LinkList h);
void print2(LinkList h);
LinkList shanchu(LinkList h);
void outs(LinkList h, int m);
/* 主函数 */
main()
{ int m; LinkList head;
head=creat();
print1(head);//带头结点输出（实际上是跳过了头结点）
head=shanchu(head);
print2(head);//删除头结点后输出
printf("\n enter the begin secret code, m=（m>1）"); scanf("%d",&m);
outs(head, m);//按照密码输出
} /* main */
/* 建立约瑟夫环 带头结点的单链表 */
LinkList creat()
{ int i=0, mi;
LinkList h,p2,p1;
h=( LinkList)malloc(sizeof(Lnode));
p1=h;
p1->next =h;
printf("\n 我的密码为： "); scanf("%d",&mi);
while( mi != -111) // 密码为-111，结束循环
{
p2=( LinkList)malloc(sizeof(Lnode)); // 申请数据元素结点空间
i++;
p2->num=i;
p2->sm=mi;
p2->next=h;//连成环
p1->next=p2;
p1=p2;
printf("\n 我的密码为： "); scanf("%d",&mi); // 读入下一个密码
} //while
return(h);
}
/*---------------------------------------带头结点输出（跳过头结点输出）----------------*/
void print1(LinkList h)
{
LinkList q;
q=h->next;
printf("带头结点链表输出：\n");
// 与头插法建立链表对应的输出函数
while (q!=h)
{
printf("%6d %6d \n",q->num,q->sm);
q=q->next;
}
}
LinkList shanchu(LinkList h){
LinkList m,p;
m=h;
for(p=h;p->next!=h;p=p->next);
p->next=h->next;
h=h->next;
free(m);
return(h);
}
/*----------------------删除头结点后输出-------------------*/
void print2(LinkList h)
{
LinkList r;
r=h;
printf("不带头结点链表输出：\n");
while (r->next !=h )
{
printf("%6d %6d \n",r->num,r->sm);
r=r->next;
}
printf("%6d %6d \n",r->num,r->sm);// 头指针指向第一个数据元素结点
}
/*--------------------------------按照密码输出某我的------------*/
void outs(LinkList h, int m)
{ int i; LinkList q=h,p;
printf("\n ");
while (q->next!=q)
{ for(i=1;i<m;i++){ p=q; q=q->next;} // 报数到第m我的
printf("%6d %6d\n ",q->num,q->sm); // 输出第m我的的编号和密码
m=q->sm;
p->next=q->next; free(q); // 第m我的出列
q=p->next;
}
printf("%6d %6d \n",q->num,q->sm); // 输出最后一个结点的编号值
free(q);
} //outs