找回密码
 注册

QQ登录

只需一步,快速开始

搜索

C++语言循环链表(约瑟夫环)源程序

[复制链接]
Jonsa 发表于 2021-11-15 15:02:20 | 显示全部楼层 |阅读模式
1.循环链表和约瑟夫
循环链表:将单链表的首尾连接,使其成为了一个环状链表,通常称为循环链表。
约瑟夫环:是一个经典的循环链表问题,题意是:已知 n 个人(分别用编号 1,2,3,…,n 表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列;他的下一个人又从 1 开始,还是顺时针开始报数,数到 m 的那个人又出列;依次重复下去,直到圆桌上剩余一个人。
2.算法思路
1.png
3.源码
  1. #include<stdio.h>
  2. #include<stdlib.h>


  3. typedef struct node{
  4.     int number;
  5.     struct node* next;
  6. }person;

  7. person *initLink(int n)
  8. {
  9.     person *head=(person*)malloc(sizeof(person));
  10.     head->number=1;
  11.     head->next=NULL;
  12.     person *cyclic=head;
  13.     int i;
  14.     for(i=2;i<=n;i++)
  15.     {
  16.         person *temp=(person*)malloc(sizeof(person));
  17.         temp->number=i;
  18.         temp->next=NULL;

  19.         head->next=temp;
  20.         head=head->next;
  21.     }
  22.     head->next=cyclic;
  23.     return cyclic;
  24. }


  25. void linkPrint(person *temp)
  26. {
  27.     person *head=temp;
  28.     if(!temp)
  29.         printf("the link is empty\n");
  30.     else
  31.     {
  32.         while(temp)
  33.         {
  34.             printf("%d\t",temp->number);
  35.             temp=temp->next;
  36.             if(temp==head)
  37.                 break;
  38.         }
  39.     }
  40. }

  41. void findANDkill(person *head,int k,int m)
  42. {
  43.     person *tail=head;
  44.     //找到链表第一个结点的上一个结点,为删除操作做准备
  45.     while(tail->next!=head)
  46.         tail=tail->next;
  47.     person * p=head;
  48.     //找到编号为k的人
  49.     while(p->number!=k)
  50.     {
  51.         tail=p;
  52.         p=p->next;
  53.     }
  54.     //从编号为k的人开始,只有符合p->next==p时,说明链表中除了p结点,所有编号都出列了,
  55.     while(p->next!=p)
  56.     {
  57.         //找到从p报数1开始,报m的人,并且还要知道数m-1de人的位置tail,方便做删除操作。
  58.         for(int i=1;i<m;i++)
  59.         {
  60.             tail=p;
  61.             p=p->next;
  62.         }

  63.         tail->next=p->next;//从链表上将p结点摘下来
  64.         printf("出列人的编号为:%d\n",p->number);
  65.         free(p);
  66.         p=tail->next;//继续使用p指针指向出列编号的下一个编号,游戏继续
  67.     }
  68.     printf("出列人的编号为:%d\n",p->number);
  69.     free(p);
  70. }

  71. int main()
  72. {
  73.     int n,k,m;
  74.     printf("请输入圆桌上的人数:\n");
  75.     scanf("%d",&n);
  76.     person *head=initLink(n);
  77.     //linkPrint(head);
  78.     printf("从第k人开始报数(k>1且k<%d):",n);
  79.     scanf("%d",&k);
  80.     printf("数到m的人出列:");
  81.     scanf("%d",&m);

  82.     findANDkill(head,k,m);
  83.     return 0;
  84. }
复制代码


您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|手机版|小黑屋|ELEOK |网站地图

GMT+8, 2024-2-25 04:01

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表