数据结构-约瑟夫环实验报告-C语言

一．需求分析 1.设有编号为1,2，…，n的n（n）0）个人按顺时针方向围坐成一圈。从第一个人开始顺时针报数，报到m的人（m为正整数），令其出列。然后再从下一个开始，重新从1 顺时针报数，如此下去，直至所有人全部出列为止。程序依次输出列人的编号顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和在运算结果显示在其后。 3.测试数据 M的初值为20； N=7,7个人的密码依次为：3,1,7，2，4,8,4 出列顺序为 6,1,4,7,2,3,5 【约瑟夫环问题】是数据结构中的一种经典问题，主要涉及到链表操作和循环算法。该问题描述了一个场景：n个人围成一个圈，从第一个人开始顺时针报数，每数到m的人出列，然后从下一个人继续报数，直到所有人都出列。在这个过程中，程序需要记录并输出出列的顺序。 在C语言中实现约瑟夫环问题，通常使用链表作为数据结构。链表中的每个节点代表一个人，包含两个属性：编号(num)和密码(pwd)。在这个实验报告中，程序包含了四个模块： 1. **主函数** (`main()`)：负责获取用户输入的m（报数上限）和n（人数），并对输入进行错误检查。如果输入合法，则创建链表，输入密码，并调用输出函数。 2. **链表创建函数** (`Createlinklist()`)：初始化链表，创建一个循环链表，包含n个节点，每个节点的编号从1到n。 3. **密码输入函数** (`enterpwd()`)：根据用户输入的密码序列，将密码分配给链表中的相应节点。 4. **输出函数** (`outlist()`)：根据m值进行报数，每次数到m就删除当前节点，直到链表为空。输出的顺序就是出列的顺序。 在调试过程中，遇到了几个问题： - **错误处理**：最初没有检查m和n是否在有效范围内，导致错误输入后程序仍能运行。后来添加了if语句进行判断。 - **循环初始值**：在输出函数中的for循环，初始值应为1，而不是其他值。 - **密码处理**：最初的程序忽略了题目中关于密码的要求，后来添加了密码函数并调用。 用户手册中指出，这个程序在DOS操作系统环境下运行，用户需要输入M和N的值，以及对应的密码序列，程序会显示出列顺序。 测试结果显示，当M=20，N=7，且密码序列为3,1,7,2,4,8,4时，出列顺序为6,1,4,7,2,3,5。 约瑟夫环问题的C语言实现涉及到了链表的创建、遍历、节点删除等基本操作，同时还需要考虑错误处理和用户交互。这个问题是数据结构和算法课程中的典型练习，有助于理解链表结构和循环算法的应用。