猴子选大王课程设计说明书.doc

数学与计算机学院课程设计说明书课 程 名 称: 数据结构课程设计 课 程 代 码: 6014389 题 目: 猴子选大王 年级/专业/班: 2010级软件工程2班 学 生 姓 名: 蒋 童 学 号: 312010080611229 开 始 时 间: 2011 年 11 月 9 日完 成 时 间: 2011 年 12 月 30 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名： 年 月 日数 据 结 构 课 程 设 计 任 务 书学院名称： 数学与计算机学院 课程代码：_ 6014389_专 业： 软件工程 年 级： 2班 一、设计题目猴子选大王二、 主要内容一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。三、具体要求及应提交的材料要求：使用数组和循环链表等两种以上的存储方式来做输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能用C/C+语言编程实现上述内容，对每个问题写出一个算法实现，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书，并提交下列材料：1)课程设计说明书打印稿一份2)课程设计说明书电子稿一份；3)源程序电子文档一份。四、主要技术路线提示可采用数组、链表数据结构实现。在此基础上用C/C+实现其操作。五、进度安排按教学计划规定，数据结构课程设计为2周，其进度及时间大致分配如下：序号设计内容天数1分析问题，给出数学模型，选择数据结构22设计算法，给出算法描述13给出源程序清单24编辑、编译、调试源程序25编写课程设计报告3总 计10六、推荐参考资料1 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 2 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。3 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年9月4 朱战立.数据结构(C+语言描述)（第二版本）.高等出版社出版.2004年4月5 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月6 徐孝凯 等著.数据结构（C语言描述）.清华大学出版社.2004指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日目 录 摘 要4引 言51 需求分析51.1任务与分析51.2测试数据62 概要设计62.1 ADT描述62.2程序模块结构72.21结构体定义72.3各功能模块83详细设计93.1结构体定义93.2 初始化103.3 插入操作104 调试分析155用户使用说明156测试结果166.1 界面运行结果166.2子功能测试运行结果：166.3 结束界面（如下图）18结 论19致 谢20参考文献21摘 要 随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本课程设计主要通过使用循环链表、数组、以及单向链表，将猴子编号来数据化待选猴子坐成一个圈，并对圈内的猴子进行报数选取大王。最终输出选出的猴子大王的编号。考虑到循环链表、数组、以及单向链表要使用不同的结构体、算法等，故将不同的三种方法设计为分开的三个类。只在主函数中调用其相应的函数。程序通过调试运行，结果与预计结果一致，初步实现了设计功能。关键词：现代版；队列（循环链表）；队列（数组）；单向链表 ；数据结构 引 言 A、 课程设计任务本课程设计主要实现在循环链表、数组、单向链表三种不同存储结构下对问题（即：“一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。”）实现要求。依据猴子的编号数据化将猴子用以上方式存储。并进行报数入队，与出队操作。最终输出最后一位猴子编号，该猴子为此次当选的猴王。B、课程设计性质数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和数据结构课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于数组、链表等算法的实现，包括在存储结构中添加、删除操作，最后把结果输出。此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。C、课程设计目的其目的是让我们在学习完C+、数据结构等课程基础上，掌握数据的存储结构、掌握数据相应的存储，添加，更新等操作，并用输出结果。进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。1 需求分析1.1任务与分析猴子选大王，众多猴子纷纷想成为大王，以一统群族。更便享有最高的地位与权利，因而导致猴子间惨重的事件发生。在现代发展的社会中不管人类还是猴子都不想看到如此不幸的画面。故利用计算机软件来解决血腥的冲突。即将编号为1，2，n的一群猴子按照1-n的顺序围坐成一个圈，所以可以用数组将其以循环的方式存储，输入猴子的总数m与要报的数n，且保证nm。还用rear表示数组尾front数组头，并进行报数，将未报到指定数的猴子加到rear；用链表时可以用指针结点将一个猴子作为一个结点存储，也用front表示链表头，rear表示链表尾。将未到报数的猴子加到链表尾；循环链表就将链表的头尾连接，不用将未报到n的猴子加到尾部，只需将报到n的猴子结点删除。最后输出最后一个猴子的信息，便得出该猴子为此次选举的猴子大王。具体步骤如下：第一步 建立数组（链表），填入猴子编号及猴子出局时报的数；第二步 从第一个猴子报数；第三步 数组存储中将数m的猴子不作操作，将未数到的猴子循环存在数组中，可以将报过数的信息猴子覆盖。链表中将报到的猴子结点删除；第四步 继续报数，重复第三步。到只剩一个猴子编号；第五步 输出此猴子的信息。1.2测试数据 1）、输入猴子数与出局报数 5 2 第3个猴子是大王2）、输入猴子数与出局报数 43 13 第10个猴子是大王3）、输入猴子数与出局报数 121 31 第84个猴子是大王2 概要设计2.1 ADT描述 ADT Node数据对象：D=ai|aiElemSet,i=1,2,3,m数据关系：R|ai-1,aiD，i=2,3,m基本操作： 创建数组，链表 输入编号猴子信息，进入存储于数组，链表中 报数开始，报到出局数的猴子出局 输出选出的猴子大王信息 等等ADT Node2.2程序模块结构 图2.1 猴子选大王系统模块结构图2.21结构体定义如下是三种不同存储方式的存储结构概要设计a).数组定义： 如下是对数组方式的定义，包含数组的大小，元素的定义，并用类对其进行封装。#include /命名空间const max=100; /宏定义数组的大小typedef int ElemType; /定义一个元素类型为整型class seq /创建一个类将其进行封装private: ElemType elemmax; /存储数组为私有 int front,rear; /在此建立私有的队列头、尾public:;b).单向链表定义： 如下是单向链式的结构体包含一个数域和一个指下的指针域，数值域。并也对其用类进行封装，使其更佳。struct Node /单向链表中每个结点包含一个数域和一个指下的指针域 int data; /数值域 Node *next; /指针域，指向链表的下一个结点class danx /建类进行封装private: Node *top; /创建头指针 public:; c).循环链表定义： 如下是单向链式的结构体包含一个数域和一个指下的指针域，数值域。并也对其用类进行封装，使其更佳。其中含有一个头指针，用于对其中初始结点的指向。struct NodeType /链表结点的结构体 int num; /数值域，存储猴子编号 NodeType *next; ; /指针域，指向下一个猴子结点class xunh private: NodeType *Head; / 将头指针设为私有public:;2.3各功能模块1、数组方式包含有构造函数，析构函数，还有进行创建（即录入操作），与报数输出操作。各功能模块如下：class seq /数组存储的类private:public:seq() / 数组存储的构造函数seq(); /析构函数void jin(); /输入存储操作void chu(); /报数输出操作;2、单向链表方式包含有构造函数，析构函数，还有进行创建（即录入操作），与报数输出操作。各功能模块如下：class danx / 单向链表的类 private: public:danx( ) ; /单向链表操作的构造函数danx() ; /析构函数void creat(); /创建链表，输入猴子信息void outs(); /报数输出操作 ;3、循环链表方式包含有构造函数，析构函数，还有进行创建（即录入操作），与报数输出操作。各功能模块如下：class xunh /循环链表的类 private: public:xunh( ) ; /循环链表的构造函数xunh() ; /析构函数void creat(); /创建循环链表，输入信息void outs(); /报数输出大王信息3详细设计3.1结构体定义1、数组结构体定义如下： 对数组的大小进行限制在100，并定义一个整型元素。 const max=100; /宏定义数组上线大小为100 typedef int ElemType; /定义整型元素类型ElemType2、单向链表结构体定义如下： 单向链表中每个结点包含一个数域和一个指下的指针域，定义值域，存储猴子编号，还定义一个指针域用与连接操作。 struct Node /单向链表中每个结点包含一个数域和一个指下的指针域 int data; / 定义值域，存储猴子编号 Node *next; ; /定义指针域指向下一个结点 3、循环链表结构体定义如下： struct NodeType /也包含数值域和一个指针域 int num; /值域，存储猴子编号 NodeType *next; ; /指针域指向下一个结点3.2 初始化其数组中表示头与尾的指针进行初始化：只要在数组类的构造函数中将定义的头与尾初始化到第一个数。 class seq private: public: seq()front=0;rear=0; /将数组中头尾指针初始化指向第一个数 ;3.3 插入操作1、如下是对数组方式功能的操作： 创建，录入数组：void seq:jin() /创建操作coutn.欢迎使用数组方式选取大王.endl;int m; /猴子的总数docoutn 请输入猴子的总数(m;if(m100|m0) /判断猴子的总数是否正确，输出提示cout100|m0); /dowhile语句使得m的值输入正确for(int i=0;im;i+) /将编号存入数组elemi=i+1; rear=m-1; /将尾指针指向数组的尾报数输出结果：void seq:chu() /报数输出操作int n; /定义出局报的数cout=2)：; cinn; /输入报数的值coutn根据报数值n，开始选猴大王.endl;if(front=rear) /判断队列是否为空cout 存储错误！队列为空！endl;else /当数组存储不为空时coutn报数结束，最终成为猴子大王的是（编号）：;while(front!=rear) /头尾相等表示报数结束for(int i=1;in;i+) /对出局报数循环，使报到的猴子出局rear=(rear+1)%max; /实现在数组中循环存储，让尾指向下一个，但不出数组elemrear=elemfront; /实现让队头报数后的猴子接在队尾front=(front+1)%max; /在循环中头指针不出数组front=front+1; /正好报到数的猴子出队coutelemfront; /选择猴王结束，输出猴王编号coutendl;2、如下是对单向链表方式功能的操作：void danx:creat() /创建操作 coutn.欢迎使用单向链表方式选取大王.endl;int i=0, m; /猴子总数mNode *newp, *pre; /新声明两结点，创建时pre作为尾结点coutm;for(i=0;inext=NULL; newp-data=i+1; if(i=0) /如果链表中还没有数据存入，将存入第一个数据top=newp; /及将其在头结点pre= top; elsepre-next=newp; /如果头结点有元素，就存在为结点的下一个pre=newp; /将尾结点指向下一个 void danx:outs( ) /单向链表的输出操作 int n,i; /n为报数值,i为局部循环数值Node *q=top;while(q-next!=NULL) /将p指针指向连尾q=q-next; /如果q还不是尾结点，就下移cout=2)：; cinn;coutn根据报数值n，开始选猴大王.endl;coutnext!=NULL) /当头结点的下一个为空时，表示报数结束Node *p; /创建一个指针，进行报数操作for(i=1;inext; /报数时将头指针下移p-next=NULL; /令p的指针域指空q-next=p; /将p连接到连表尾q=p; /q下移p=top;top=top-next; /top头指针下移delete p; /删除报到指定数的结点coutdataendl; /输出当选猴大王猴子的编号 3、如下是对循环链表方式功能的操作：void xunh:creat() /创建操作 coutn.欢迎使用循环链表方式选取大王.endl;int i=0, m; /猴子总数mNodeType *newp, *pre; /新声明两结点，创建时pre作为尾结点coutm; /输入猴子总数for(i=0;inext=NULL;newp-num=i+1; if(i=0) /如果链表中还没有数据存入，将存入第一个数据Head=newp;pre= Head;else /如果头结点有元素，就存在为结点的下一个newp-next=Head; /将尾与头连接构成循环pre-next=newp;pre=newp; void xunh:outs( ) /循环链表的输出操作 int n,i; /猴子总数m，局部数值iNodeType *q=Head, *p; /新建结点q并指向头cout=2)：; cinn; /输入要报的数coutn根据报数值n，开始选猴大王.endl;coutnext!=q) /判断：当qd的下一个为空时，则报数结束for(i=1;inext; /在循环中将不对未报到出局数的结点操作，进行下一个报数 p-next=q-next; /将报到出局数的结点取出delete q; /删除报到数的结点q=p-next; /将断点连接coutnumendl; /输出最后结点信息，为当选猴王delete q; /删除结点 4、如下是主函数的实现调用操作：在主函数中使用switchcase语句将上述三个功能进行界面处理显示，并对用户人性化设计，并创建三个相应类的对象，在switchcase语句中，能根据用户的选项作出相应的函数调用。体如下：int main() int k; /在switch语句中用到的选择值seq s; /创建数组方式的对象danx f; /创建单向链表的对象xunh d; /创建循环方式的对象coutn.欢迎进入猴子选大王系统.endl;coutn* ;do /对用户界面进行美化 ，并提供相关的选项供用户选择coutnn| 1.使用数组方式选取大王 |;coutnn| 2.使用单向链表方式选取大王 |;coutnn| 3.使用循环链表方式选取大王 |;coutnn| 4.结束程序 |;coutn*;coutk; /用户输入选择switch(k)case 1: /选择1就调用数组类的方式s.jin(); /创建s.chu(); /报数，输出coutendl;coutendl;break;case 2:/选择2就调用单向链表的操作f.creat(); /创建f.outs(); /报数，输出coutendl;coutendl;break;case 3: /选择3就调用循环方式的操作 d.creat(); /创建d.outs(); /报数，输出coutendl;coutendl;break;default:break; /其他就结束 cout=1&k4); coutn 再见!; coutn 按任意键，返回。endl; return 0;4 调试分析 由于此次的课程设计题目所需要的相关知识大多数可在数据结构书中找到，或借鉴。所以在完成代码后运行时，没出现严重错误和问题。只是有点小问题，即局部变量用错：没定义的也用了。调试并找出错误，进行修改。最后获得成功。5用户使用说明该系统具有简单、明了、使用等特点，能够方便、准确的计算出众多猴子编号选举大王的结果。当使用该系统时，系统会给出相关的提示信息，用户只需根据提示信息，即可完成系统提供的所有功能。6测试结果6.1 界面运行结果 系统运行主界面如图6.1所示：图6.1 主界面6.2子功能测