本文執行個體講述了C語言基于循環連結清單解決約瑟夫環問題的方法。分享給大家供大家參考，具體如下：
概述：
約瑟夫環問題，是一個經典的循環連結清單問題，題意是：已知 n 個人(以編号1，2，3，…，n分别表示)圍坐在一張圓桌周圍，從編号為 k 的人開始順時針報數，數到 m 的那個人出列；他的下一個人又從 1 還是順時針開始報數，數到 m 的那個人又出列；依次重複下去，要求找到最後出列的那個人。
例如有 5 個人，要求從編号為 3 的人開始，數到 2 的那個人出列：
出列順序依次為：
編号為 3 的人開始數 1，然後 4 數 2，是以 4 先出列；
4 出列後，從 5 開始數 1，1 數 2，是以 1 出列；
1 出列後，從 2 開始數 1，3 數 2，是以 3 出列；
3 出列後，從 5 開始數 1，2 數 2，是以 2 出列；
最後隻剩下 5 自己，是以 5 出列。
代碼實作:
#include
#include
typedef struct node{
int number;
struct node * next;
}person;
person * initLink(int n){
person * head=(person*)malloc(sizeof(person));
head->number=1;
head->next=NULL;
person * cyclic=head;
for (int i=2; i<=n; i++) {
person * body=(person*)malloc(sizeof(person));
body->number=i;
body->next=NULL;
cyclic->next=body;
cyclic=cyclic->next;
}
cyclic->next=head;//首尾相連
return head;
}
void findAndKillK(person * head,int k,int m){
person * tail=head;
//找到連結清單第一個結點的上一個結點，為删除操作做準備
while (tail->next!=head) {
tail=tail->next;
}
person * p=head;
//找到編号為k的人
while (p->number!=k) {
tail=p;
p=p->next;
}
//從編号為k的人開始，隻有符合p->next==p時，說明連結清單中除了p結點，所有編号都出列了，
while (p->next!=p) {
//找到從p報數1開始，報m的人，并且還要知道數m-1de人的位置tail，友善做删除操作。
for (int i=1; i
tail=p;
p=p->next;
}
tail->next=p->next;//從連結清單上将p結點摘下來
printf("出列人的編号為:%d\n",p->number);
free(p);
p=tail->next;//繼續使用p指針指向出列編号的下一個編号，遊戲繼續
}
printf("出列人的編号為:%d\n",p->number);
free(p);
}
int main() {
printf("輸入圓桌上的人數n:");
int n;
scanf("%d",&n);
person * head=initLink(n);
printf("從第k人開始報數(k>1且k
int k;
scanf("%d",&k);
printf("數到m的人出列：");
int m;
scanf("%d",&m);
findAndKillK(head, k, m);
return 0;
}
輸出:
輸入圓桌上的人數n:5
從第k人開始報數(k>1且k<5)：3
數到m的人出列：2
出列人的編号為:4
出列人的編号為:1
出列人的編号為:3
出列人的編号為:2
出列人的編号為:5
希望本文所述對大家C語言程式設計有所幫助。