数据结构课程设计-约瑟夫环.doc

课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 约瑟夫环约瑟夫环 数据结构课程设计报告 I 目目 录录 1 1 课程设计介绍课程设计介绍 1 1 1 课程设计内容 1 1 2 课程设计要求 1 2 2 课程设计原理课程设计原理 2 2 1 课设题目粗略分析 2 2 2 原理图介绍 2 2 2 1 功能模块图 2 2 2 2 流程图分析 3 3 数据结构分析数据结构分析 6 3 1 存储结构 6 3 2 算法描述 6 4 4 调试与分析调试与分析 8 4 1 调试过程 8 4 2 程序执行过程 8 4 3 运行时的界面显示 9 参考文献参考文献 10 附附 录 关键部分程序清单 录 关键部分程序清单 11 数据结构课程设计报告 1 1 1 课程设计介绍课程设计介绍 1 11 1 课程设计内容课程设计内容 编号为 1 2 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密 码 正整数 一开始任选一个正整数作为报数的上限值 m 从第一个人开始 按顺时针方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将他 的密码作为新的 m 值 从他的顺时针方向的下一个开始重新从 1 报数 如此 下去 直至所有的人全部出列为止 设计一个程序求出出列顺序 1 21 2 课程设计要求课程设计要求 1 使用单循环链表作为储存结构 并模拟该过程 2 从键盘输入开始时的总人数 初始报数上限值 m 及每个人的密码 3 按照出列顺序输出各人的编号 数据结构课程设计报告 2 2 2 课程设计原理课程设计原理 2 12 1 课设题目粗略分析课设题目粗略分析 演示程序以用户和计算机的对话的方式执行 即在计算机终端上显示 提示 信息 之后 由用户在键盘上输入相应的数据 即每个人都所持的密码 每个 人的序号由程序自动分配 程序执行的命令包括 1 构造链表 2 输入数据 3 执行报数 储存出列人的序号 删除出列人的信息以及把出列人的密码 赋给 m 4 结束 本程序包括三个模块 1 信息录入 构造链表 模块 此模块将对数据进行初始化 构造链表 并录入数据以便后续程序的使用 2 结果输出模块 此模块将根据前面所输入的数据对数据进行处理 输出 报数号码 删除报数节点 并继续进行处理 3 主程序模块 此模块实现整个程序的进入和退出 及各种初始化处理 2 2 原理图介绍原理图介绍 2 2 12 2 1 功能模块图功能模块图 约约瑟瑟夫夫环环 主函数模块 信息录入模块 结果输出模块 图 2 1 功能模块图 功能模块如图 2 1 所示 数据结构课程设计报告 3 2 2 22 2 2 流程图分析流程图分析 1 此部分为 createlist 函数 首先初始化变量 再输出提示性语句 等待用 户输入数据 将总人数和初始上限值分别存入 num 和 m 以 num 为上限值建立 单循环链表 最后返回 L b be eg gi in n 声声明明变变量量t t和和指指针针p p q q 输输出出提提示示语语句句并并录录入入总总人人数数和和 初初始始上上限限值值n nu um m和和m m t t 1 1 t t n ne ex xt t L L p p n no od de e m ma al ll lo oc c s si iz ze eo of f n n o od de e L L N NU UL LL L q q n ne ex xt t p p L L q q p p N N Y Y Y Y N N R Re et tu ur rn n 图 2 2 createlist 函数流程图 2 此部分为 printlist 函数部分 定义变量 temp m 从第一个人开始进行 报数 指针 q 和 p 指向第一个人 L 当 q next p 时 q q next 否则当 q 数据结构课程设计报告 4 next q 时 temp 直到 temp 0 时输出 p 所指向的节点的 num 重复以上处 理直到 q next q 为假时结束该函数 b be eg gi in n i in nt t t te em mp p m m q q n ne ex xt t q q F Fr re ee e p p p p q q n ne ex xt t t te em mp p 0 0 p pr ri in nt tf f d d p p n nu um m T Te em mp p p p m mm m q q n ne ex xt t p p n ne ex xt t q q p p p p p p n ne ex xt t L Li in nk kl li is st t q q p p q q p p L L p pr ri in nt tf f d d n n q q n nu um m N N Y Y N N Y Y R Re et tu ur rn n q q n ne ex xt t p p q q q q n ne ex xt t Y Y N N 图 2 3 printlist 函数流程图 3 此部分为主程序部分 分别调用函数 createlist 和 printlist 所有人 输出 程序结束 并通过 while 循环对程序进行重复使用 数据结构课程设计报告 5 开开始始 i in nt ts s 1 1 s s 0 0 p pr ri in nt tf f 谢谢谢谢使使用用 n n L Li in nk kl li is st t L L N NU UL LL L l li is st t L L p pr ri in nt tf f 继继续续 1 1 y ye es s o or r 0 0 n no o 输输入入s s的的值值 结结束束 图 2 4 主程序流程图 数据结构课程设计报告 6 3 数据结构分析数据结构分析 3 13 1 存储结构存储结构 根据要求首先应该建立一个单循环链表 实现链式存储 设置结构体存储节 点 用结构体存储全体人数整型变量 num 和每个人的密码整型变量 mm 用以指 示下一结点的指针 next 结构体指针 Linklist struct node int mark int num struct node next typedef struct node Linklist 设置结构体指针 p 和 q 及表头指针 L 3 23 2 算法描述算法描述 1 将人数的编号和相应的密码输入到单循环链表中 应用 creatlist 函数 输 入总人数和初始上限值 然后依次输入每个人的密码 循环 n 1 次 设置指针 p Linklist malloc sizeof node 如果头结点为空 将指针 p L q 每人的号码 编号赋值给指针 p 所指的人数 p num i q next p 然后将 p 所指的节点赋给 q q p 依次循环 直到所有的节点都赋值完成 赋值完成后 p next L 构成单 循环链表的要求 2 进行出圈的过程 所用的函数为 Print 函数 因为上限值为全局变量值 所以在 Print 函数中用一个变量 temp 代替 令 temp m q next L 进行循环 条 件为 q next q 因为为循环链表 所以判断最后指针是否指向自己 while q next q 在这循环体中 令变量 temp 逐步减 1 判断是否为一 while temp 1 循环体为 q p p p next 当为 1 时 选中第一个出圈的人 并输出他的 数据结构课程设计报告 7 编号 printf d p num 此时将他的编号赋值为新的上限值 temp p mark q 指向的下一结点为 p 所指向的下一节点 并进行删除节点操作 free p 将 q 的下一节点再次赋值给 p p q next 重复以上的操作 知道所有的人都输 出 3 主程序模块部分 全局变量总人数 n 和初始上限值 m 设置单循环链表 的表头 L 分别引用函数 createlist 和 printlist 本程序结束 并通过 while 循环 对程序进行重复使用 数据结构课程设计报告 8 4 4 调试与分析调试与分析 4 14 1 调试过程调试过程 在调试程序是主要遇到一下几类问题 1 当输入此函数时出现了与 struct node int mm int num struct node next typedef struct node Linklist Linklist createlist Linklist L 根据人数创建链表 int t Linklist p q printf 请输入总人数 scanf d printf 请输入初始上限值 scanf d for t 1 tmm p num t if L NULL L q p else q next p q p p next L return L void printlist Linklist L 输出链表 数据结构课程设计报告 12 int temp m Linklist p q printf 出列顺序是 n p q L while q next p q q next while q next q while temp q p p p next printf d p num temp p mm q next p next free p p q next printf d n q num 输出最后一个结点 return void main int s 1 while s 0 Linklist L NULL L createlist L printlist L printf 继续 1 yes or 0 no scanf d printf n printf 谢谢使用 n 数据结构课程设计报告 13 课程设计总结 课程设计总结 通过本次课程设计使我更加清楚了自己的水平以及以后要努力的方向 本 次课程设计涉及到的范围很广 让本人能够比较系统的对 C 语言和数据结构进 行一次整理和复习 同时有了很多的体会和经验 我的课设的题目是约瑟夫环 根据题目的内容与要求 首先得到的是用单 链表作为全体人数与每个人的密码的存储结构 设置结构体指针 并定义了两 个指针类型的指针 p 与 q 并编写了两个函数 链表构造函数和输出函数 对数据结构的理解有待加强 算法的知识面也有待于提高 不同的人会选 择不同的算法 所以即使同样的程序 不同的人必然会设计出不同的方案 所 以以后的学习生活中 一定要广泛涉猎 掌握更多更好的解决问题的方法 在编写程序的过程中要明白程序的好坏是运行的效率如何 所以在编写程 序时尽量用简洁的数据结构方法与算法 同时使程序格式清晰与美观 通过这次课程设计 我知道要想成为一个合格的程序员