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

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

已知有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)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
68 0
|
2月前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
142 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
2月前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
29 0
|
2月前
数据结构的带头,双向,循环链表来咯
数据结构的带头,双向,循环链表来咯
24 0
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
210 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
37 1

热门文章

最新文章