约瑟夫环和集合的交并运算.doc

《约瑟夫环和集合的交并运算.doc》由会员分享，可在线阅读，更多相关《约瑟夫环和集合的交并运算.doc（48页珍藏版）》请在三一办公上搜索。

1、 工 程 学 院课 程 设 计设计题目： 约瑟夫环 集合交并运算系 别 信息工程系 班级 计本091 学生姓名 学号 41 42 18 指导教师 职称 副教授、讲师 起止日期：2010年12月27日起至2010年1月7日止 工 程 学 院课程设计任务书课程设计题目： 约瑟夫环 集合交并运算系 别 信息工程系 班级 计本091 学生姓名 学号 41 42 18 指导教师 职称 副教授、讲师课程设计进行地点： 实训F座 任 务 下 达 时 间： 2010年 12月 27日起止日期：2010年12月27日起至2011年1月7日止教研室主任 2010年1月7日批准一、课程设计的原始资料及依据约瑟夫（J

2、oeph）问题的一种描述是：编号为1、2、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。随着计算机的普及、IT产业和Internet获得了飞速发展，计算机应用已渗透到了各个领域，引起信息管理的革命，实现了信息的自动化处理，提高了处理的及时性和正确性。计算机应用到数学运算中之后大大提高了运算的速度和正确性。编写集合运算的软件势在必行。查阅有关

3、程序设计的案例资料，进一步理解程序设计模块化的思想，并利用此思想，根据对程序设计学习编写一个简单的游戏软件系统。通过本设计可以加深理解利用程序设计思想开发一个系统的整个流程，提高分析问题、解决问题和实际动手的能力。二、课程设计主要内容及要求1约瑟夫环. 认真阅读资料，掌握程序设计模块化的思想。. 要求在设计的过程中，建立清晰的层次结构。. 画出主要的功能结构图和主要模块的流程图。. 建立一个具有n个链结点，无头结点的循环链表。. 确定第1个报数人的位置。. 不断地从链表中删除链结点，直到链表为空。2.集合交并运算 . 构造集合，其中构造集合的时候需要从键盘输入字符型数据。. 求并集，交集和差集

4、。. 输出结果。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计

5、组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第1天（12月27日）阅读资料2第23天（12月28日12月30日

6、）系统分析设计3第48天（12月31日1月5日）程序编制、调试及运行4第9天（1月6日）成绩评定5第10天（1月7日）撰写课程设计说明书六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.20072谭浩强.C程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华等编著. 数据结构课程设计. 北京:机械工业出版社.2005.055李春葆.数据结构（C语言版）习题与解析.北京:清华大学出版社.2002.046郭翠英.C语言课程设计案例精编.北京：中国水利水电出版社.2004.37张翔.C语言函数大全

7、.北京:清华大学出版社.2002.48浦滨.C游戏编程从入门到精通.北京: 北京希望电子出版社.2002.59陈天洲.C语言高级程序设计. 北京:人民邮电出版社.200210杨旭.C语言程序设计案例教程.北京: 人民邮电出版社.200511徐慧.C语言实例解析精粹.北京:人民邮电出版社.2006.0412王为青C语言高级编程及实例剖析北京:人民邮电出版社20080213姚大鹏 栾好利 张翼英 等编著.C语言程序设计教程习题与上机实训指导.中国水利水电出版社.2005沈 阳 工 程 学 院程序设计基础课程设计成绩评定表系（部）： 信息工程系 班级： 计本091 学生姓名： 黄开 指 导 教 师

8、评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一

9、定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。

10、0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院程序设计基础课程设计成绩评定表系（部）： 信息工程系 班级： 计本091 学生姓名： 丁金清 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，

11、文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具

12、 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院程序设计基础课程设计成绩评定表系（部）： 信息工程系 班级： 计本091 学生姓名： 岳煜璐 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能

13、制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说

14、明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月

15、 日课 程 设 计 总 评 成 绩分摘 要自1946年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至几秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使得它的应用范围迅速扩展。计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来了一些新的问题。数据结构不仅为计算机专业工作者所使用，而且为广大计算机应用人员所喜爱和使用。它适合作为系统描述语言，既可以用来编写系统软件，也可以用来编写应用软件。计算机技术已深入到人类生活的各个角落，与其他学科紧密结合，成为推动各学科飞速发展的有力的催化剂。无论学什么专业，都

16、必须具备计算机的基础知识和应用能力。计算机既是现代科学技术的结晶，又是大众化的工具。学习计算机知识，不仅能够掌握有关的知识，而且能培养人们的信息素养。许多高等学校，不仅在计算机专业开设数据结构课程，而且在非计算机专业也开设了数据结构课程。学习数据结构已经成为广大计算机应用人员和广大青年学生的迫切要求。本次课程设计过程中我们主要根据课本中的实现思想及算法编写程序，体现以课本知识的应用为主，在学习了线性表、栈、队列、二叉树、树与图等结构的基础上，并能结合一些著名算法来解决一些实际问题，从而能更深刻理解数据结构的内涵，熟悉他们各自的应用场合及方法。有些在平时课程中并没有掌握的内容在这次课程设计中都是

17、先通过看课本学懂了，然后再在课程设计中加深印象，实现算法的应用和拓展。这次课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。我们主要做了约瑟夫环、集合的交并运算两个题目。我们的课程设计的主要过程是：进行课程设计课题的资料搜集、根据搜集的资料进行程序功能与数据结构分析，并选择合适的数据结构，并在此基础上进行实现程序功能的算法设计通过这两周的学习，不仅巩固了我们的基础知识，而且使我们的实际操作能力和团队协作能力有了很大的提升。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词 串的模式匹配 数据结构 广义表 查找目 录摘 要I第一章 问题分析11.1 引言

18、11.2 背景11.3 分析11.3.1链表11.3.2 集合2第二章 原理与运行环境32.1数据理论32.1.1 约瑟夫环32.1.2 集合交并运算32.2 运行环境visualC+ 6.0材料32.2.1 基本操作3第三章 系统分析与设计53.1需要实现功能53.1.1 约瑟夫环53.1.2 集合交并运算53.2程序算法及流程图53.2.1 约瑟夫环53.2.2集合交并运算8第四章 系统功能代码114.1 函数介绍与基本操作114.1.1 函数介绍114.1.2 基本操作114.2 约瑟夫环功能实现124.2.1主函数模块代码124.2.2 创建单循环链表函数模块代码134.2.3 删除结

19、点函数代码134.3集合交并运算功能实现144.3.1集合的交函数代码144.3.2集合的并函数代码154.3.3集合的差函数代码15第五章 系统功能实现175.1 约瑟夫环175.1.1运行程序后的初界面175.1.2 输入所有人所持有的密码后的界面175.1.3 输入1之后的界面185.1.4 输入0之后的界面185.2 集合交并运算195.2.1 初始界面195.2.2运算结果19结论20致谢21参考文献22第一章 问题分析1.1 引言“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心教程，而且已经成为其他理工专业的热门选修课。“数据结构”在计算机科学中是一门综合性

20、的专业基础课。“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论，存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学，计算机硬件和计算机软件的一门核心课程。在计算机科学中，“数据结构”不仅是一般程序设计（特别是非数值计算的课程设计）的基础，而且是设计和实现编译程序，操作系统，数据库系统及其他系统程序和大型应用程序的重要基础。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面

21、的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课设主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。通过本次课程设计，相信我们一定能加强对数据结构这门课程的学习，尤其在动手实践上会有很大的进步。1.2 背景约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元6670年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱

22、者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 随着计算机的普及、IT产业和Internet获得了飞速发展，计算机应用已渗透到了各个领域，引起信息管理的革命，实现了信息的自动化处理，提高了处理的及时性和正确性。计算机应用到数学运算中之后大大提高了运算的速度和正确性。编写集合运算的软件势在必行。1.3 分析1.3.1链表链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个

23、节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个

24、用来指向明上一个或下一个节点的位置的链接（links）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点。线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部

25、分信息组成一个结点（如概述旁的图所示），表示线性表中一个数据元素。循环链表是一种链式的存储结构，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。1.3.2 集合某些指定的对象集在一起就是集合。 集合，简称集，其中各事物叫做集合的元素或简称元。如（1）阿Q正传中出现的不

26、同汉字（2）全体英文大写字母。任何集合是它自身的子集.一般的，把一些能够确定的不同的对象看成一个整体，就说这个整体是由这些对象的全体构成的集合（或集）.构成集合的每个对象叫做这个集合的元素（或成员）。集合的运算有求交，求并，求差。第二章 原理与运行环境2.1数据理论2.1.1 约瑟夫环为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先

27、定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。n个人（编号0(n-1)，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 . n-2, n-1, 0, 1, 2

28、, . k-2并且从k开始报0。现在我们把他们的编号做一下转换： k - 0 k+1 - 1 k+2 - 2 . . k-2 - n-2 k-1 - n-1 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x 变回去不刚好就是n个人情况的解吗？！变回去的公式很简单，相信大家都可以推出来：x=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 - 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最

29、后胜利者的编号，最后的结果自然是fn 递推公式 f1=0; f=(fi-1+m)%i; (i1) 有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是fn。因为实际生活中编号总是从1开始，我们输出fn+1由于是逐级递推，不需要保存每个f，程序也是异常简单。为实现上述程序功能，程序应以线性表示环，该表以单向循环链表实现。为此，定义如下线性表ADT LinkList 数据对象：D=a | a LNode, i=1,2,.,n, n0 数据关系：R=| a ,a D, a a , i=2,.,n, n0 基本操作： InitList(&L) 初始条件：L为空 操作结果：构造一个空的线性表

30、L Destroy(&L, &p) 初始条件：线性表L已经存在，p指示L中的某个元素 操作结果：删除线性表L的元素p Next_m(&L,&p,m) 初始条件：线性表L已经存在，p指示L中的某个元素 操作结果：使得p指示其之后的第m个元素 Empty（L） 初始条件：线性表L已经存在 操作结果：若线性表L为空则返回True，否则返回False Get_Num(L,p,&Num) 初始条件：线性表L已经存在，p指示L中的某个元素 操作结果：用Num返回p指示的元素的Num部分Get_Num(L,p,&pwd) 初始条件：线性表L已经存在，p指示L中的某个元素 操作结果：用pwd返回p指示的元素的

31、pwd部分 Insert (&L,&p,password,Num) 初始条件：线性表L已经存在，p指示L中的某个元素操作结果：将一个Num部分的值为Num，pwd部分的值为password的元素插入 到p元素的后面，并将p指向新元素 ADT LinkList2.1.2 集合交并运算本程序中，集合的元素限定为小写字母符a.z ，集合的大小n27。集合输入的形式为一个以回车符为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。复数定义 ADT Complex 数据对象：D= | e1,e2R (R为实数集合) 数据关

32、系：R= ，e1是复数的实部，e2是复数的虚部，即：e1+j e2 基本操作： InitComplex(&T,v1,v2) 操作结果：构造复数T，元素e1,e2分别被赋以参数v1,v2的值 DestroyComplex(&T) 初始条件：复数T已存在 操作结果：复数T被销毁 GetComplex(T,i,&e) 初始条件：复数T已存在， i1,2 操作结果：用e返回复数T的实部或虚部，i=1返回实部, i=2返回虚部 PutComplex(T,i,e) 初始条件：复数T已存在， i1,2 操作结果：改变复数T实部或虚部为e，i=1改变实部, i=2改变虚部 AddComplex(T1,T2,&

33、T3) 初始条件：复数T1,T2已存在 操作结果：复数T1,T2相加，结果存入复数T3 SubComplex(&T1,T2,&T3) 初始条件：复数T1,T2已存在 操作结果：复数T1,T2相减，结果存入复数T3 MulComplex(&T1,T2,&T3) 初始条件：复数T1,T2已存在 操作结果：复数T1,T2相乘，结果存入复数T3 DivComplex(&T1,T2,&T3) 初始条件：复数T1,T2已存在 操作结果：复数T1,T2相除，结果存入复数T3 ADT Complex 有理数ADT定义： ADT Rational_Num 数据对象：D= | e1,e2I (I为整数集合) 数据

34、关系：R= ，e1是有理数的分子，e2是有理数的分母，且e20 基本操作： InitRational_Num(&T,v1,v2) 操作结果：构造有理数T，元素e1,e2分别被赋以参数v1,v2的值 DestroyRational_Num(&T) 初始条件：有理数T已存在 操作结果：有理数T被销毁 GetRational_Num(T,i,&e) 初始条件：有理数T已存在， i1,2 操作结果：用e返回有理数T的分子或分母，i=1返回分子, i=2返回分母 PutRational_Num(T,i,e) 初始条件：有理数T已存在， i1,2 操作结果：改变有理数T的分子或分母为e，i=1改变分子,

35、i=2改变分母 AddRational_Num(T1,T2,&T3) 初始条件：有理数T1,T2已存在 操作结果：有理数T1,T2相加，结果存入有理数T3 SubRational_Num(&T1,T2,&T3) 初始条件：有理数T1,T2已存在 操作结果：有理数T1,T2相减，结果存入有理数T3 MulRational_Num(&T1,T2,&T3) 初始条件：有理数T1,T2已存在 操作结果：有理数T1,T2相乘，结果存入有理数T3 DivRational_Num(&T1,T2,&T3) 初始条件：有理数T1,T2已存在 操作结果：有理数T1,T2相除，结果存入有理数T3 ADT Ratio

36、nal_Num2.2 运行环境visualC+ 6.0材料VisualC+60是Microsoft公司开发的基于CC+的集成开发工具，它是VisualStudio中功能最为强大、代码效率最高的开发工具。打开 Visual C+，其工作环境如图2-1所示。图 2-1 Visual C+ 6.0 的工作环境2.2.1 基本操作建立C源程序文件建立方法：选择菜单命令“新建”弹出如图2-2所示的对话框，选择“文件”选项下的C/C+ source file输入文件名确定即可。图2-2 新建命令对话框然后会出现如图2-3所示的界面：VisualC+6.0的工作环境可以划分为三块区域。最左边的区域是工作区，

37、最下面的区域是输入区，最右边的区域是编辑区。编辑区用来对原文件进行编辑，现在的编辑区是灰色的，表示还没有源文件在进行编辑。输出区的作用是对程序进行编译和链接后，如果程序有错误或警告，则显示在输出区。工作区的作用是用来管理各种源程序文件，在它的管理下，可以有条不紊的进行各种源文件的编辑。图2-3 编辑区域程序的编辑与编译当代码编辑完成之后，选择菜单命令“组建”“编译”对源程序进行编译，当输出区显示“0 errors， 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，当然有时提示位置不一定很准确。程序的执行单击工具

38、栏上的“红色感叹号”按钮，或选择“组建”中选择“执行”命令（ctrl+F5）即可执行刚编译完的程序，如图2-4所示。图2-4 对源程序进行编译并执行第三章 系统分析与设计3.1需要实现功能3.1.1 约瑟夫环编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。3.1.2 集合交并运算本课题主要

39、的目的是为了实现集合的合并，求交集、差操作。通过编写软件实现大量准确处理集合运算的要求。该课题的实现是基于C语言的编程过程，利用链表实现集合的求并、求交和差运算。三种运算编写三个独立的函数，在主函数中调用实现其功能。3.2程序算法及流程图3.2.1 约瑟夫环(1) 主程序流程图，如图3-1所示：开始输入参与人数构造单链表初始化单链表开始进行约瑟夫环的操作输出出列顺序结束图3-1主程序流程图(2) 创建单循环链表函数流程图, 如图3-2所示开始密码=人数？输入每人所持有的密码创建结点结束是否图3.2创建单循环链表(3) 删除结点函数（出列函数）程序流程图，如图3-3所示开始从1开始报数,报m结束

40、真是否为最后一个节点？假报m的人出列结束图3-3删除节点3.2.2集合交并运算(1) 集合的交流程图，以属于A且属于B的元素为元素的集合称为A与B的交（集），记作AB（或BA），读作“A交B”（或“B交A”），即AB=x|xA,且xB.用流程图表示这个过程如图3-4所示.开始输入集合P1输入集合P2从集合P2第一个数起取数判断P1中是否有与之相等的数将数存入P3Y取P2中下一个数判断P2中是否还有数据输出P3中数据结束N YN图3-4集合的交(2) 集合的并流程图，以属于A或属于B的元素为元素的集合称为A与B的并（集），记作AB（或BA），读作“A并B”（或“B并A”），即AB=x|xA,或x

41、B.用程序语言求并集,其流程图如图3-5所示开始输入集合P1输入集合P2从集合P2第一个数起取数判断P1中是否有与之相等的数将数存入P3N取P2中下一个数判断P2中是否还有数据输出P3中数据结束N YY将P1数据存入P3图3-5集合的并(3) 集合的差流程图，以属于A且不属于B的元素为元素的集合称为A与B的差（集），记作A-B（或B-A），读作“A减B”（或“B减A”），即A-B=x|xA,且x不B.用流程图表示这个过程如图3-6所示。开始输入集合P1输入集合P2从集合P2第一个数起取数判断P1中是否有与之相等的数将数存入P3N取P2中下一个数判断P2中是否还有数据输出P3中数据结束N YY将P1未比较数据存入P3