【php精品源码栏目提醒】:网学会员为需要php精品源码的朋友们搜集整理了约瑟夫环实验报告 - 大学课件相关资料,希望对各位网友有所帮助!
《数据结构》 实验
报告实验题目: 约瑟夫环班 级:学 号:求分析 1、利用单向循环链表存储结构模拟 Josephus
问题,按照出列的顺序输出出列序号。
建立一个不带头结点的循环单链表,结点数据域值分别为 1-n;根据输入的第一个报数位置,找到单向循环链表中相应结点;根据输入的要报数值,反复进行以下操作:计数到 m,输出对应结点的数据元素值并删除该结点,直到所有结点全部删除。
2、输出形式 从屏幕显示出列顺序 3、程序功能
演示程序以用户与
计算机的对话方式执行,用户输入相应的数据,输出结果显示在其后。
测试数据: 1 n8 s1 m4 出列顺序为:48521376 2 n9 s4 m5 出列顺序为:739658241 3 n7 s6 m2 出列顺序为:6135274 4 n10 s3 m2 出列顺序为:35791482106 5 n6 s3 m5 出列顺序为:6513422.概要设计 为实现上述程序功能,应利用单向循环链表存储结构模拟此过程。
1. 单向循环链表的抽象数据类型定义为: ADT CircularList 数据对象:Daiai∈LNodei12…nn≥0 数据关系:R1ai-1∈Di2…n 基本操作: LinkList InitListElemType n 操作结果:构造一个空的循环表 L,为线性表分配存储空间用于存放 数据元素。
void JosephusLinkList pElemType numberElemType n 操作结果:根据输入的要报数值,反复进行以下操作:计数到 n,输 出对应结点的数据元素值并删除该结点,直到所有结点number全部删除。
2. 本
程序中包括的两个基本模块: 1 主程序模块: Intmain 初始化; 接受命令; 处理命令;Return02、单向循环列表模块——实现循环列表抽象数据类型;3、各模块之间的调用关系如下: 主程序模块 单向循环
列表模块3.详细
设计1、1结点类型 typedef struct Lnode int value//编号 struct Lnode next //指向直接后继结点 LNodeLinkList 2 用循环链表存储约瑟夫环,没有头结点,基本操作函数如下: LinkList InitListElemType n //构造一个空的循环列表结构的约瑟夫环,结点个数为 n LinkList headNULLpNULLqNULL int i1 headLinkList mallocsizeofLNode //头指针 head-valuei phead fori2inextq pq //尾指针指向当前结点 p-valuei p-nexthead //尾指针指向头结点 return head void JosephusLinkList pElemType numberElemType n //删除一个结点 int i1jg0 LinkList qNULL forj1jnext //指向下一个结点 qp-next //记录被删除结点 p-nextq-next //删除该结点 printf第3d 个出圈号是:3dniq-value //输出该删除结点的 编号 freeq //释放被删除结点的空间 fori2inext p-nextq-next //下一次循环的开始 printf第3d 个出圈号是:3dniq-value freeq printfn 2 主函数: int main int m0n0s0i LinkList head0 printf请输入总人数:n scanfdm printf请输入第一个报名的人编号n scanfds printf请输入出圈编号:n scanfdn ifsms