数据结构项目——使用循环链表实现约瑟夫环(循环和双向链表实现)

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
EMR Serverless StarRocks,5000CU*H 48000GB*H
简介: 数据结构项目——使用循环链表实现约瑟夫环(循环和双向链表实现)

已知有5个人围坐在一张圆桌的周围,从编号为3的人开始顺时针数数,数到2的那个人出列淘汰,然后从出列的下个一人继续数,依次循环,直到只剩下最后一个人。(使用循环链表实现约瑟夫环)



代码如下:


#include "pch.h"
#include<string>
#include<fstream>
#include<Windows.h>
#include <iostream>
using namespace std;
//循环链表基本实现
//typedef struct LNode
//{
//  int date;
//  LNode* next;
//}*LinkList;
//
新建单链表
//void InitList(LinkList &L)
//{
//  L = new LNode;
//  L->next = NULL;
//}
//
给链表增加节点
//void GetLinkList(LinkList &L, int n)
//{
//  LNode *p;
//  LNode *r;
//  r = L;
//  char filename[20] = { 0 };
//
//  cout << "请输入单向有序链表"
//    <<"数据文件名字(文件名+“.txt”),例如List.txt"
//    << ".txt" << endl;
//
//  gets_s(filename);
//  fstream file;
//  file.open(filename);
//  if (!file)
//  {
//    cout << "文件数据打开失败!" << endl;
//    Sleep(5000);
//    exit(0);
//  }
//  
//  while (!file.eof())
//  {
//    p = new LNode;
//    file >> p->date;
//    p->next = NULL;     //前插插
//    r->next = p;
//    r = p;
//    n++;
//
//  }
//
//  file.close();
//}
//
//void OutPutList(LinkList L)
//{
//  LNode *p;
//  p = L->next;
//  while (p)
//  {
//    cout << p->date << "  ";
//    p = p->next;
//  }
//}
//
链表合并函数
//void MergeLinkList(LinkList &la, LinkList &lb, LinkList &lc)
//{
//  LinkList pa, pb, pc;
//  pa = la->next;
//  pb = lb->next;
//  
//  lc = la;
//  pc = lc;
//    
//  //两段链表都有节点
//  while (pa&&pb)
//  {
//    if (pa->date<=pb->date)
//    {
//      pc->next = pa;
//      pc = pa;
//      pa = pa->next;
//    }
//    else
//    {
//      pc->next = pb;
//      pc = pb;  
//      pb=pb->next;
//    }
//
//    pc->next = pa ? pa : pb;
//
//  }
//}
//
//int main()
//{
//  LinkList la,lb, lc;
//
//  InitList(la);
//  GetLinkList(la, 1);
//  OutPutList(la);
//  cout << endl;
//
//  InitList(lb);
//  GetLinkList(lb, 1);
//  OutPutList(lb);
//  cout << endl;
//
//  InitList(lc);
//  MergeLinkList(la, lb, lc);
//  OutPutList(lc);
//
//  return 0;
//}
//
//约瑟夫环实现
typedef struct Person
{
  int numberdate;
  Person *next;
}*LinkPerson;
LinkPerson initList(int n)
{
  LinkPerson L = new Person;
  L->numberdate = 1;
  L->next = NULL;
  Person*p = L;
  for (int i = 2; i <= n; i++)
  {
    Person*body = new Person;
    body->numberdate = i;
    body->next = NULL;
    p->next = body;
    p = p->next;
  }
  p->next = L;    //首尾相接
  return L;
}
void KillPerson(LinkPerson L, int a, int b)
{ //a是编号,b是数几淘汰
  LinkPerson tail = L;
  while (tail->next != L)
  {
    tail = tail->next;
  }
  LinkPerson p = L;
  //把链表的开头给开始的那个人
  while (p->numberdate != a)
  {
    tail = p;
    p = p->next;
  }
  //当p->next=p时说明只剩下一个人,游戏结束
  while (p->next != p)
  {
    //重新写入剩下的游戏玩家
    for (int i = 1; i < b; i++)
    {
      tail = p;
      p = p->next;
    }
    //从链表上将p结点就删除了
    tail->next = p->next;
    cout << "被杀的人是" << p->numberdate << "号" << endl;
    delete p;
    p = tail->next;
  }
  cout << "最后胜出的是:" << p->numberdate << endl;
  delete p;
}
int main()
{
  int n, a, b;
  cout << "请输入玩家数:";
  cin >> n;
  cout << "请输入从几号玩家开始:";
  cin >> a;
  cout << "请输入每次步数:";
  cin >> b;
  Person *L= initList(n);
  KillPerson(L, a, b);
  return 0;
}

结果为:


相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
|
13天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
1天前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1天前
|
存储
【初阶数据结构】深入解析带头双向循环链表:探索底层逻辑
【初阶数据结构】深入解析带头双向循环链表:探索底层逻辑
|
1天前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
5月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
33 2
|
5月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
46 1
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表