数据结构学习-循环链表:处理约瑟夫环问题

这篇具有很好参考价值的文章主要介绍了数据结构学习-循环链表:处理约瑟夫环问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

问题描述

一、基本概念

 1.普通链表

2.单向循环链表 

二、问题处理

1.创建链表

2.查找

3.删除

 4.其他

 三.实验环节

四.总结

问题描述

约瑟夫环问题的一种描述是:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。

基本要求:利用链表模拟此过程,按照出列的顺序印出各人的编号。

一、基本概念

链表是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个结点(节点)。单向循环链表与普通链表的区别在于:普通链表的最后一个链表的next指向NULL,而单向循环链表的最后一个节点的next指向头结点

 1.普通链表

循环链表约瑟夫环,链表,学习,数据结构

2.单向循环链表 

 循环链表约瑟夫环,链表,学习,数据结构

二、问题处理

1.创建链表

首先因为处理问题时,链表元素的访问并不是从头开始的,而是采用“接力棒”的方式进行访问。所以应该使用不带有头结点的单向循环链表。

代码如下: 

typedef struct Data
{
    int number; // 编号
    int code;   // 密码
    /*
        存放数据
    */
} Data;
typedef struct SqList
{
    Data data;    // 数据域
    SqList *next; // 指针域
} SqList;

SqList *CreateList(int n) // 生成一个不带头节点的n个元素的循环链表
{
    if (n < 1) // 输入的n不合法
    {
        printf("输入不合法!");
        system("pause");
        return NULL;
    }
    SqList *end = new SqList; // 尾指针
    for (int i = 1; i < n + 1; i++)
    {
        SqList *newNode = (SqList *)malloc(sizeof(SqList *));
        if (i == 1) // 链表为空时输入首元节点的密码
        {
            newNode->next = newNode;
            cout << "请输入成员" << i << "的密码:";
            cin >> newNode->data.code;
            newNode->data.number = 1;
            end = newNode;
            continue;
        }
        // 链表不为空时输入newNode数据的密码
        cout << "请输入成员" << i << "的密码:";
        cin >> newNode->data.code;
        newNode->data.number = i;
        // 尾插法构建链表
        newNode->next = end->next;
        end->next = newNode;
        end = newNode;
    }
    return end->next;
}

这里需要注意的是因为编号是有序的——按顺时针方向,所以采用尾插法

2.查找

代码如下:

SqList *ListSearch(SqList *L, int k) // 返回链表中的第k个元素
{
    if (!L || k < 1 || k > ListLength(L)) // 链表为空或输入的k值不合法
    {
        cout << "Error3!" << endl;
        system("pause");
        exit(0);
    }
    for (int i = 0; i < k - 1; i++)
    {
        L = L->next;
    }
    return L;
}

3.删除

代码如下:

SqList *ListDelete(SqList *L, int n) // 删除链表L中指定的第n个元素
{
    if (!L || n < 1) // 链表为空或删除位置不合法
    {
        cout << "Error2!" << endl;
        system("pause");
        exit(0);
    }
    SqList *front = L;
    SqList *temp = nullptr;         // 暂时储存要删除的元素
    for (int i = 0; i < n - 1; i++) // 移动指针到要删除的位置上
    {
        L = L->next;
    }
    while (front->next != L) // 寻找要删除的元素前面的一个元素
    {
        front = front->next;
    }
    front->next = L->next; // 将要删除的元素移出链表
    temp = L;
    L = L->next;
    free(temp); // 释放内存
    return L;
}

因为采用“接力棒”的方式访问元素,需要记住被删除元素的后一个元素。所以返回指针类型。

 4.其他

代码如下:

int ListLength(SqList *L) // 返回链表长度
{
    if (!L) // 输入空链表时报错并退出函数
    {
        cout << "Error1!";
        system("pause");
        exit(0);
    }
    SqList *F_Node = L;
    int count = 1; // 因为不带头节点的链表,所以非空时链表节点个数至少为1
    while (L->next != F_Node)
    {
        count++;
        L = L->next;
    }
    return count;
}

void ListPrint(SqList *L) // 打印链表L中的元素
{
    if (!L)
    {
        return;
    }
    SqList *Node = L;
    do
    {
        if (Node->next == L)
        {
            cout << "成员" << Node->data.number << "的密码:" << Node->data.code << "\t";
            return;
        }
        cout << "成员" << Node->data.number << "的密码:" << Node->data.code << "\t";
        Node = Node->next;
    } while (1);
    return;
}


 三.实验环节

整体代码:

/*
    整个实验重要的步骤就是创建、查找、删除
*/
#include <iostream>
using namespace std;

typedef struct Data
{
    int number; // 编号
    int code;   // 密码
    /*
        存放数据
    */
} Data;
typedef struct SqList
{
    Data data;    // 数据域
    SqList *next; // 指针域
} SqList;

SqList *CreateList(int n) // 生成一个不带头节点的n个元素的循环链表
{
    if (n < 1) // 输入的n不合法
    {
        printf("输入不合法!");
        system("pause");
        return NULL;
    }
    SqList *end = new SqList; // 尾指针
    for (int i = 1; i < n + 1; i++)
    {
        SqList *newNode = (SqList *)malloc(sizeof(SqList *));
        if (i == 1) // 链表为空时输入首元节点的密码
        {
            newNode->next = newNode;
            cout << "请输入成员" << i << "的密码:";
            cin >> newNode->data.code;
            newNode->data.number = 1;
            end = newNode;
            continue;
        }
        // 链表不为空时输入newNode数据的密码
        cout << "请输入成员" << i << "的密码:";
        cin >> newNode->data.code;
        newNode->data.number = i;
        // 尾插法构建链表
        newNode->next = end->next;
        end->next = newNode;
        end = newNode;
    }
    return end->next;
}
int ListLength(SqList *L) // 返回链表长度
{
    if (!L) // 输入空链表时报错并退出函数
    {
        cout << "Error1!";
        system("pause");
        exit(0);
    }
    SqList *F_Node = L;
    int count = 1; // 因为不带头节点的链表,所以非空时链表节点个数至少为1
    while (L->next != F_Node)
    {
        count++;
        L = L->next;
    }
    return count;
}
void ListPrint(SqList *L) // 打印链表L中的元素
{
    if (!L)
    {
        return;
    }
    SqList *Node = L;
    do
    {
        if (Node->next == L)
        {
            cout << "成员" << Node->data.number << "的密码:" << Node->data.code << "\t";
            return;
        }
        cout << "成员" << Node->data.number << "的密码:" << Node->data.code << "\t";
        Node = Node->next;
    } while (1);
}

void ListInsert(SqList *L, Data elem, int a) // 向链表L中第a个位置后面插入数据elem
{
    for (int i = 0; i < a - 1; i++)
    {
        L = L->next;
    }
    if (!L)
    {
        return;
    }
    SqList *newNode = new SqList;
    newNode->data = elem;
    newNode->next = L->next;
    L->next = newNode;
}

SqList *ListDelete(SqList *L, int n) // 删除链表L中指定的第n个元素
{
    if (!L || n < 1) // 链表为空或删除位置不合法
    {
        cout << "Error2!" << endl;
        system("pause");
        exit(0);
    }
    SqList *front = L;
    SqList *temp = nullptr;         // 暂时储存要删除的元素
    for (int i = 0; i < n - 1; i++) // 移动指针到要删除的位置上
    {
        L = L->next;
    }
    while (front->next != L) // 寻找要删除的元素前面的一个元素
    {
        front = front->next;
    }
    front->next = L->next; // 将要删除的元素移出链表
    temp = L;
    L = L->next;
    free(temp); // 释放内存
    return L;
}

SqList *ListSearch(SqList *L, int k) // 返回链表中的第k个元素
{
    if (!L || k < 1 || k > ListLength(L)) // 链表为空或输入的k值不合法
    {
        cout << "Error3!" << endl;
        system("pause");
        exit(0);
    }
    for (int i = 0; i < k - 1; i++)
    {
        L = L->next;
    }
    return L;
}

测试数据:m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4

(正确的出列顺序应为6,1,4,7,2,3,5)。 

测试如下:

#define N 7 // 约瑟问题中的人数

int main(void)
{
    SqList *List = CreateList(N);
    int res[N]; // 存放出列顺序
    int m, i = 0, code = 0;
    cout << "请输入初始的正整数密码m" << endl;
    cin >> m;
    while (ListLength(List) != 1)
    {
        int k = 0;
        m = m % (N - i);
        // cout << "当前m的值是:" << m << endl;
        /*
            注意在这里m的取值是[0,N-i-1],
            而实际上m应该属于[1,N-i]。
            所以需要对求模后的m进行条件判断
        */
        if (m == 0)        
        {
            k = N - i;
        }
        else
            k = m;
        code = ListSearch(List, k)->data.code;
        res[i] = ListSearch(List, k)->data.number;
        List = ListDelete(List, k); // 返回新的起始访问位置
        m = code;
        i++;
    }
    res[i] = ListSearch(List, 1)->data.number; //此时链表中仅有一个元素
    cout << "出列顺序为:";
    for (int i = 0; i < N; i++)
        cout << res[i] << "\t";
    free(List); // 释放内存
    return 0;
}

 循环链表约瑟夫环,链表,学习,数据结构

四.总结

该问题的难点就在于元素的访问是采取“接力棒”的方式进行访问,需要对循环链表有足够的的理解,同时对密码的处理上也需要小心。对于本次实验来说,还有许多能改进的地方,比如非法输入的检测,可以把它包装成一个函数,这样处理的话,代码会更简洁并且更容易阅读。

如有错误,欢迎在评论区指正。以上内容若涉及侵权请联系作者进行删改。 文章来源地址https://www.toymoban.com/news/detail-725042.html

到了这里,关于数据结构学习-循环链表:处理约瑟夫环问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】【约瑟夫问题】还在用递归?教你用链表秒杀约瑟夫

     🎉🎉欢迎光临🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏 《数据结构与算法:初学者入门指南》📘📘 本专栏纯属为爱发电永久免费!!! 这是苏泽的个人主页可以看到我其他的内容哦👇👇 努力的苏泽 http://su

    2024年02月19日
    浏览(39)
  • 数据结构—约瑟夫环问题(C语言版)

    目录 首先什么是约瑟夫环 约瑟夫环实现方式 一、创建结构体变量 二、初始化链表 三、构建循环链表 四、删除链表  五、完整代码及注释讲解 约瑟夫环 是 循环链表 中的一个经典问题;题目描述:n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新

    2024年02月11日
    浏览(44)
  • 【数据结构与算法】约瑟夫环(C/C++)

    约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始。按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上

    2024年02月12日
    浏览(30)
  • C语言数据结构篇——约瑟夫环的实现

    作者名:Demo不是emo  主页面链接 : 主页传送门 创作初心: 对于计算机的学习者来说,初期的学习无疑是最迷茫和难以坚持的,中后期主要是经验和能力的提高,我也刚接触计算机1年,也在不断的探索,在CSDN写博客主要是为了分享自己的学习历程,学习方法,总结的经验等

    2023年04月08日
    浏览(36)
  • C语言数据结构-用链表解决约瑟夫环问题

    只是普通的大学生一枚,不会很牛的技巧和算法,只是在做数据结构作业中的一点感悟和思考。也不知道自己写得对不对,有什么意见和建议都可以直接指出来哦,我虚心接受(低头鞠躬.jpg)...... 试用线性表的链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下:设有

    2024年02月06日
    浏览(47)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(62)
  • 数据结构上机实验——栈和队列的实现、栈和队列的应用、进制转换、约瑟夫环问题

      1.利用栈的基本操作实现将任意一个十进制整数转化为R进制整数。   2.利用循环队列实现.约瑟夫环问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到k的那个人出圈;他的下一个人又从1开始报数,数到k的那个人出圈;依

    2024年02月08日
    浏览(42)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(70)
  • 循环链表解决约瑟夫环问题

    n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新从 1开始报数,数到 m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 n个人围成一圈,很容易可以想到用循环链表解决问题,用结点代表每个人,节点的数据域存储人的编号

    2024年02月07日
    浏览(41)
  • 约瑟夫死者游戏-C语言实现-双向循环链表

    设计题目 1 : 约瑟夫生者死者游戏 [问题描述]: 约瑟夫生者死者游戏的大意是: 30 个旅客同乘一条船,因为严重超载,加上风高浪大, 危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无 奈,大家只得同意这种办法,并议定 30 个人围

    2024年02月03日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包