课设报告 数据结构.doc

沈 阳 工 程 学 院课 程 设 计设计题目：约瑟夫问题、线索二叉树的创建与遍历院 系 信息学院 班级 计本131 学生姓名 王志鹏 李振 吕雪峰 刘瀚超 陈知予 学 号 08 11 14 22 30 指导教师 姜柳 、吕海华 职称 副教授、讲师 起止日期：2013年6月15日起至2013年6月27日止沈 阳 工 程 学 院课程设计任务书课程设计题目：约瑟夫问题院 系 信息学院 班级 计本131 学生姓名 王志鹏 李振 吕雪峰 刘瀚超 陈知予 学 号 08 11 14 22 30 指导教师 姜柳 、吕海华 职称 副教授、讲师 课程设计进行地点： 实训F座 任 务 下 达 时 间： 2013年 6月 15日起止日期：2013年6月16日起至2013年6月27日止教研室主任 张欣 年 月 日批准4一、课程设计的原始资料及依据约瑟夫（Joeph）问题的一种描述是：编号为1、2、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。二、课程设计主要内容及要求1约瑟夫环 . 认真阅读资料，掌握程序设计模块化的思想。 . 要求在设计的过程中，建立清晰的层次结构。 . 画出主要的功能结构图和主要模块的流程图。 . 建立一个具有n个链结点，无头结点的循环链表。 . 确定第1个报数人的位置。 . 不断地从链表中删除链结点，直到链表为空三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第1天阅读资料2第23天系统分析设计3第47天程序编制、调试及运行4第89天成绩评定5第10天撰写课程设计说明书六、主要参考资料（文献）1郭翠英.C语言课程设计案例精编.北京：中国水利水电出版社.2004.3 2谭浩强.C语言程序设计.北京:清华大学出版社.1999.123张翔.C语言函数大全.北京:清华大学出版社.2002.44浦滨.C游戏编程从入门到精通.北京: 北京希望电子出版社.2002.55陈天洲.C语言高级程序设计. 北京:人民邮电出版社.2002 6杨旭.C语言程序设计案例教程.北京: 人民邮电出版社.20057 王为青C语言高级编程及实例剖析北京:人民邮电出版社2008028徐慧.C语言实例解析精粹.北京:人民邮电出版社.2006.04 9 姚大鹏 栾好利 张翼英 等编著.C语言程序设计教程习题与上机实训指导.中国水利水电出版社.200510 王为青C语言实例解析北京:人民邮电出版社200802沈阳工程学院课程设计报告 diyizhng沈 阳 工 程 学 院课程设计任务书课程设计题目：线索二叉树的创建与遍历院 系 信息学院 班级 计本131 学生姓名 王志鹏 李振 吕雪峰 刘瀚超 陈知予 学 号 08 11 14 22 30 指导教师 姜柳 、吕海华 职称 副教授、讲师 课程设计进行地点： 实训F座 任 务 下 达 时 间： 2013年 6月 15日起止日期：2013年6月16日起至2013年6月27日止教研室主任 张欣 年 月 日批准4一、 课程设计的原始资料及依据当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能得到结点在任意序列中的前驱和后继信息，这种信息只有在遍历的动态工程中才能得到。如何保存在这种遍历过程中得到的信息呢？一个最简单的办法就是在每个结点上增加两个指针域fwd和bkwd，分别指示结点在任一次序遍历时得到的前驱和后继信息。显然这样做使得结构的存储密度大大降低。另一方面，在有n个结点二叉链表中必定存在n+1个空链域。如此设想能否利用这些空链域存放结点的前驱和后继的信息。结点结构构成的二叉链表作为二叉树的存储结构称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种遍历使其变为线索二叉树的过程为线索化。在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找到结点后继直至其后继为空为止。二、课程设计主要内容及要求 根据二叉树的先序遍历序列建立一颗中序线索二叉树，并以中序遍历序列输出。1. 按先序遍历序列输入每个结点的值。2. 建立中序线索二叉树。3. 中序遍历序列遍历线索二叉树，并输出结果。本课程设计使用的数据结构是二叉树，二叉树采用线索链表存储结构来实现。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第1天阅读资料2第23天系统分析设计3第47天程序编制、调试及运行4第89天成绩评定5第10天撰写课程设计说明书六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.20072谭浩强.C程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.055李春葆.数据结构（C语言版）习题与解析.北京:清华大学出版社.2002.04沈 阳 工 程 学 院数据结构与算法课程设计成绩评定表院系： 信息学院 班级： 计本131 学生姓名： 李振 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院数据结构与算法课程设计成绩评定表院系： 信息学院 班级： 计本131 学生姓名： 陈知予 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院数据结构与算法课程设计成绩评定表院系： 信息学院 班级： 计本131 学生姓名： 王志鹏 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院数据结构与算法课程设计成绩评定表院系： 信息学院 班级： 计本131 学生姓名： 吕雪峰 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院数据结构与算法课程设计成绩评定表院系： 信息学院 班级： 计本131 学生姓名： 刘瀚超 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分目录摘 要1第一章 问题分析21.1 引言21.2 背景31.3 分析31.3.1 约瑟夫问题31.3.2线索二叉树的创建与遍历3第二章 运行原理和环境52.1 数据结构理论52.1.1 约瑟夫问题52.1.2 线索二叉树的创建与遍历52.2 运行环境6第三章 系统分析与设计113.1 约瑟夫问题分析与设计113.1.1 系统功能113.1.2系统分析模块分析及流程图113.2 线索二叉树的创建与遍历分析与设计133.2.1 系统功能133.2.2 系统分析模块分析及流程图14第四章 系统功能实现174.1 约瑟夫问题功能实现174.1.1 算法思想174.1.2 程序代码184.2 线索二叉树的创建与遍历功能实现214.2.1 定义主函数214.2.2 输入功能244.2.3 中序遍历将二叉树线索化254.2.4 寻找的p结点前驱结点和后继结点26总 结30致 谢31参考文献3230沈阳工程学院课程设计报告 第一章 问题分析 摘 要时代在进步，科技在发展，这改变了整个世界和人类的生活方式。同时，这也要求我们新世纪的大学生掌握现代科学技术知识，调整自己的知识结构和能力结构，以适应社会发展的要求，跟上时代的脚步。新世纪需要具有丰富的现代科学知识，能够独立解决面临的任务，充满活力，又有创新意识的新型人才。随着各个领域的突飞猛进，计算机也有它卓越的进步。数据结构不仅为计算机专业工作者所使用，而且为广大计算机应用人员所喜爱和使用。数据结构是国际上广泛流行的计算机高级语言。它适合作为系统描述语言，既可以用来编写系统软件，也可以用来编写应用软件。许多高等学校，不仅在计算机专业开设数据结构课程，而且在非计算机专业也开设了数据结构课程。学习数据结构已经成为广大计算机应用人员和广大青年学生的迫切要求。约瑟夫环是由约瑟夫生死游戏而来的，他通过一块控制入队、出队，找到死亡位置，从而确定生者位置。主要包括确定死亡。为了能够方便的找到二叉树单个结点的前驱和后继，就需要将二叉树线索化。本次的另一程序就是为了实现这一目的而编译的，在线索二叉树中，课程设计使用的是数据结构式二叉树，二叉树采用线索链表存储结构来实现。二叉树线索化递归算法基本思想：先线索化左子树，然后处理根结点，最后线索化右子树。在为期两周的数据结构课程设计学习中，先要学习数据结构课程的目的掌握数据结构存储的方法，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法结构存储是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上和运用何种存储的方法，通过思考和大量的阅读，来构造一个完整的程序。数据结构存储的设计直接关系到程序的好坏。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词 队，链表，约瑟夫环 二叉树，线索，排序第一章 问题分析1.1 引言数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S），其中，K是数据元素的有限集，R是K上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。数据结构它既是理论性较强的基础课，又是实践性很强的专业课，在计算机科学领域的主干课程中具有承上启下的作用。它的先行课程有计算机基础、程序设计语言、离散数学和数学等；后继课程有操作系统、数据库原理、编译原理和软件开发技术等。综上所述我们应该，在实践中理解它学好它。学习数据结构也有技巧学习数据结构的概念后对于抽象数据类型的设计参考C+ STL标准库中容器的设计，这样对于无论是数据结构的学习还有程序设计接口能力上都会有很大的提高。数据结构学习一定要自己独立完成代码实现，虽然有时候你理解内容了，但是实现上面还是会愈要很多困难的，解决这些困难会帮助你提高程序设计的能力的。数据结构是计算机专业最重要最基础的一门课，对于有过编程经验的人，结合自己的编程体会去悟它的思想；对于初学者，捡一种自己最熟悉的语言去分析它总之千万不要陷在语言的细节上要高屋建瓴的去领会数据结构的思想。而且我觉得随着编程经历的丰富对它的体会越深入，最初接触是对一些思想可能只是生硬的记忆，随着学习的深入逐渐领悟了很多。1.2 背景约瑟夫环是来源于著名著名犹太历史学家 Josephus：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。约瑟夫问题并不难，但求解的方法很多。言而总之，约瑟夫游戏在数学界有很高的研究价值，而且至今还在被一些数学家们所研究也是我们所喜欢玩的一种益智游戏，它可以帮助开发智力，激发我们的思维。对约瑟夫还可以有进一步的研究。线索二叉树的创建与遍历：当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能得到结点在任意序列中的前驱和后继信息。所以为了方便检索信息应将二叉树线索化。这样做使得结构的存储密度大大降低。1.3 分析1.3.1 约瑟夫问题约瑟夫（Joeph）问题的一种描述是：编号为1、2、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。1.3.2线索二叉树的创建与遍历在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找到结点后继直至其后继为空为止。按先序遍历序列输入线索二叉树中每个结点的值，构造线索二叉树。基本思想:依次输入各结点信息，若输入的结点不是空结点，则建立一个新结点。然后建立左孩子，如果结点有左孩子，则左标志为0；然后建立右孩子，若结点有右孩子，则右标志为0。如此重复下去，直到输入结点的信息 为“#”为止。按中序遍历将二叉树线索化。二叉树线索化的递归算法基本思想：首先令全局指针变量current始终指向刚访问过的结点，t指向当前正在访问的结点。结点current是结点t的前驱，t是current的后继。该算法与中序遍历二叉树的算法类似，采用递归的方法，先线索化左子树，然后处理根结点，最后线索化右子树。对根结点的处理分为以下几步：第一步，判断结点t的左和右指针域，若为空，则将其相应的标志置1。第二步，判断结点t的前驱结点current，若不为空，则判断结点current的右标志，如果右标志为1，则current-rchild指向它的后继结点t，同样判断结点t的左标志，如果左标志为1，则t-lchild指向前驱结点current。第三步，current指向刚访问过的结点t。线索二叉树中序遍历的非递归算法基本思想：先查找中序遍历的开始结点，沿左指针往下查找，直到找到无左孩子的结点即二叉树中最左下的结点，将其输出。继续查找结点的中序后继结点，直到终端结点。结点的中序后继结点分两种情况：若结点t的右子树为空，则t-rchild直接指向t的中序后继结点；若结点t的右子树不为空，则从其右子树开始，沿左指针往下查找，直到找到结点t的右子树中最左下结点，就是它的中序后继结点。沈阳工程学院课程设计报告 第二章 运行原理和环境 第二章 运行原理和环境2.1 数据结构理论2.1.1 约瑟夫问题队列是只允许在一段进行插入，而在另一端进行删除的的运算受限制的线性表。队列是一种特殊的线性表。其特殊性在于只允许在一段进行插入，而在另一端进行删除。插入元素又称为入队，删除元素又称为出队。允许进行插入操作的一端称为队头（front），另一端称为队尾（rear）。处于队头的数据元素称为队头元素，处于队尾位置的数据元素称为队尾元素。不含任何数据元素的队称为空队。由于队是操作受限制的线性表，因此与线性表类似，队也有两种存储结构，即顺序存储结构和链式存储结构。队除了有入队和出队外，还有初始化、判空等操作，常用的基本操作有：（1）初始化队InitQueue(Q)；其作用是构造一个空队列Q。（2）判断栈空EmptyQueue（Q）；其作用是判断是否是空队，若栈Q为空，则返回真值；否则返回0假值。（3）入队EnQueue；其作用是队列不满时，则将x插入Q的队尾。（4）出队DeQueue；其作用是队列不空是，则删除Q的队头元素。（5）返回队头元素QueueFront（Q）；其作用是当队列Q不为空时，将队头元素赋给x并返回，操作结果只是读取队头元素，队列Q不发生变化。2.1.2 线索二叉树的创建与遍历本课程设计使用的是数据结构式二叉树，二叉树采用线索链表存储结构来实现。二叉树线索化递归算法基本思想：先线索化左子树，然后处理根结点，最后线索化右子树。树是n（n0）个结点的有限集合。当n=0时称为空树。当n0时，是非空树，它满足以下两个条件：（1）有且仅有一个称为根的结点；（2）其余结点分为m（m0）个互不相交的非空集合T1，T2，Tm，其中每个集合本身又是一棵树，称为根的子树。二叉树的定义：二叉树（Binary Tree）是有n（n0）个结点的有限集合。（1）该集合或者为空（n=0）；（2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；（3）左子树和右子树同样又都是二叉树。二叉树的遍历：一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分组成。一般限定先左后右的次序，那么只有三种遍历：DLR（根左右）、LDR（左根右）、LRD（左右根）。我们将这三种遍历方法称作前（根）序遍历，中（根）遍历和后（根）序遍历。也可以对二叉树的每个层次的各结点按从左至右进行遍历（按层次遍历），下面我们分别介绍这几种遍历方法。先序遍历的递归算法：先（根）序遍历。若二叉树为空，遍历结束。否则依次执行以下操作：（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。中序遍历的递归算法：若二叉树为空，遍历结束。否则依次执行以下操作：（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。后序遍历的递归算法：若二叉树为空，遍历结束。否则依次执行以下操作：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。2.2 运行环境本次课设采用Microsoft Visual C+ 6.0运行环境。VC+6.0是Microsoft公司推出的一个基于Windows系统平台、可视化的集成开发环境，它的源程序按C+语言的要求编写，并加入了微软提供的功能强大的MFC(Microsoft Foundation Class)类库。MFC中封装了大部分Windows API函数和Windows控件，它包含的功能涉及到整个Windows操作系统。MFC不仅给用户提供了Windows图形环境下应用程序的框架，而且还提供了创建应用程序的组件，这样，开发人员不必从头设计创建和管理一个标准Windows应用程序所需的程序，而是从一个比较高的起点编程，故节省了大量的时间。另外，它提供了大量的代码，指导用户编程时实现某些技术和功能。因此，使用VC+提供的高度可视化的应用程序开发工具和MFC类库，可使应用程序开发变得简单。 单击“开始”选择“所有程序”，双击点开Microsoft Visual C+ 6.0。如图2-1所示。图2-1 打开Microsoft Visual C+ 6.0运行环境 打开界面如图2-2所示。图2-2 打开VC+6.0 操作界面 建立新的工程：new-选择标签projects-在project name中填写你的工程名（例如myproject）-双击win32 console Application-选择一个空的工程-finish-ok。如图2-3、图2-4所示和图2-5所示。图2-3 单击“File”打开“New”图2-4 建立新工程命名为“my project”图2-5 选择空的工程 在所建立完成的工程下建立新的文件：new-files-add to project选中在file 中输入文件名（注意：用C语言写文件明后要加.c例如文件名myfile.c,C+写就不需要直接就myfile或者myfile.cpp）-单击OK。如图2-6所示。图2-6 建立C+文件 进入编辑界面，开始进行程序编辑。如图2-7所示。图2-7 编辑界面沈阳工程学院课程设计报告 第三章 系统分析与设计 第三章 系统分析与设计3.1 约瑟夫问题分析与设计3.1.1 系统功能约瑟夫问题要求用户输入总人数n和上限数m，还有每个人的密码pwd（password）。然后系统将根据输入的数值找出下一个人，直至所有人全部出列为止。3.1.2系统分析模块分析及流程图1.主函数在主函数中需要完成的任务是传递总人数n和上限数m。其系统总体的流程图，如图3-1所示。开始输入总人数n输入开始上限m构建约瑟夫环输出每个人的出列顺序和密码结束图3-1 程序总体流程图2. 链表的创建在主函数中输入完总人数n和开始上限数m后，就进入循环链表的创建函数中。在创建循环链表函数中，要输入每个玩家的密码password，最后返回到主函数，其流程图如图3-2所示。开始输入i=1从主函数中获取玩家人数n 否i=i+1irchild直接指向t的中序后继结点；若结点t的右子树不为空，则从其右子树开始，沿左指针往下查找，直到找到结点t的右子树中最左下结点，就是它的中序后继结点。流程图如图3-6所示。开始 是否为空树 否 是结点是否有左子树 否 是访问下一个结点访问该节点的前驱是否有右子树 否 是访问下一个结点访问该结点后继返回函数值结束图3-6 中序遍历非递归流程图沈阳工程学