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