国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C > 正文

C語言基于循環鏈表解決約瑟夫環問題的方法示例

2020-01-26 13:49:30
字體:
來源:轉載
供稿:網友

本文實例講述了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 <stdio.h>#include <stdlib.h>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<m; 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<%d):",n);  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語言程序設計有所幫助。

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表

圖片精選

主站蜘蛛池模板: 平乐县| 乌拉特中旗| 屏东县| 利辛县| 长泰县| 景洪市| 克山县| 龙山县| 南阳市| 桂东县| 江津市| 恭城| 隆尧县| 潍坊市| 贺州市| 新田县| 连南| 年辖:市辖区| 启东市| 新丰县| 博客| 攀枝花市| 安徽省| 元阳县| 八宿县| 清水县| 太原市| 莲花县| 迁西县| 长丰县| 南投县| 义乌市| 石门县| 都安| 巫溪县| 昌乐县| 广元市| 青海省| 西乌珠穆沁旗| 唐河县| 桐城市|