一、实验目的
1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。
2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。
二、实验原理
约瑟夫问题的一种描述：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。
方法1．报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。
方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。
#include<stdio.h>
#include <stdlib.h>
typedef struct Lnode /* 结点的结构定义 */
{ int num; /* 编号子域 */
int sm; /* 密码子域 */
struct Lnode *next; /* 指针域 */
}Lnode,*LinkList;
LinkList creat(LinkList &L)// 创建链表
{
LinkList p,head;
L=(LinkList)malloc(sizeof(Lnode));//开辟空间1个空间
head=L;//把节点给head
L->next=L;//让l->next指向l构造循环链表
int i=0,end=0;//i是序号给num赋值，end是为了给sm赋值
printf("是否结束输入-111：");
while(true){
scanf("%d",&end);//输入密码
if(end==-111) //如果输入-111，跳出循环
{
break;
}
p=(LinkList)malloc(sizeof(Lnode));//开辟空间
p->num=i;//序号
p->sm=end;//给密码赋值
i++;
p->next=head;//尾插法
L->next=p;
L=p;
}
return head;//返回链表的头地址
}
void print1(LinkList &L){//输出带头节点的链表
LinkList q;
q=L->next;//由于带头指针，所以指向头节点的下一个节点
while(q!=L){
printf("序号：%d 密码：%d
",q->num,q->sm);//输出序号跟密码
q=q->next; //指向下一个节点，如果下一个节点等于头结点就跳出循环
}
printf("
------------
");
}
LinkList print2(LinkList &L){//删除头节点，在输出
LinkList q,p,head,z;
q=L->next;//q指向头结点的下一个节点，跳过空的头节点
while(q!=L){//寻找最后一个结点
printf("序号：%d 密码：%d
",q->num,q->sm);
p=q;
q=q->next;
}
z=p->next;//z指向空的头结点
p->next=z->next;//去除头结点
free(z);//释放空间
head=p;// 把该节点当作头节点
printf("
------------
");
return head;
}
void out1(LinkList &L,int m){
LinkList p,q;
q=L;//把链表头结点给 q
int i=0;//为了选出要出局的人
while(true){
if(m==i){
printf("序号：%d 密码：%d
",q->num,q->sm);
m=q->sm;//下一次需要数几个人出局
if(q->next==q)//如果只剩下他自己游戏结束
{
printf("game over!!!");
break;
}
p->next=q->next;//删除输出的节点
q=p->next;//让q指向输出节点的下一个节点
i=1;
}
i++;
p=q;//记录要输出的节点的上一个节点
q=q->next;
}
}
int main()
{
LinkList head1,L,head2;//head1是为了往里输入数据，head2是经过约瑟夫算法以后存到的地方
int t=5;//第一次要出局的人的位置
head1=creat(L);//初始化一个链表，并把地址给head1
print1(head1);//输出带头结点链表
head2=print2(head1);//输出不带头节点的链表
out1(head2,t);//按约瑟夫环输出链表
return 0;
}