《猴子选大王课程设计说明书》由会员分享，可在线阅读，更多相关《猴子选大王课程设计说明书（22页珍藏版）》请在金锄头文库上搜索。
1、数学与计算机学院 课程设计说明书课 程 名 称: 数据结构课程设计 课 程 代 码: 6014389 题 目: 猴子选大王 年级/专业/班: 2010 级软件工程 2 班 学 生 姓 名: 蒋 童 学 号: 312010080611229 开 始 时 间: 2011 年 11 月 9 日完 成 时 间: 2011 年 12 月 30 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名： 年 月 日猴子选大王1数 据 结 构 课 程 设 计 任 务 书学院名称： 数学与计算机学院 课程代码：_
2、 6014389_专 业： 软件工程 年 级： 2 班 一、设计题目猴子选大王二、 主要内容一堆猴子都有编号，编号是 1，2，3 .m ,这群猴子（m 个）按照 1-m 的顺序围坐一圈，从第 1 开始数，每数到第 N 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。三、具体要求及应提交的材料要求：使用数组和循环链表等两种以上的存储方式来做输入数据：输入 m,n m,n 为整数，n|ai-1,aiD，i=2,3,m基本操作：创建数组，链表输入编号猴子信息，进入存储于数组，链表中报数开始，报到出局数的猴子出局输出选出的猴子大王信息等等ADT Node2.2 程序模
3、块结构 猴子选举大王系统数组存储选举单链表存储选举循环链表存储选举创 建 并 输 入 编 号 猴 子 信 息输 出 获 选 猴 子 编 号 及 信 息报 数 选 举创 建 并 输 入 编 号 猴 子 信 息输 出 获 选 猴 子 编 号 及 信 息报 数 选 举创 建 并 输 入 编 号 猴 子 信 息输 出 获 选 猴 子 编 号 及 信 息报 数 选 举图 2.1 猴子选大王系统模块结构图2.21 结构体定义如下是三种不同存储方式的存储结构概要设计a).数组定义：如下是对数组方式的定义，包含数组的大小，元素的定义，并用类对其进行封装。#include /命名空间猴子选大王8const ma
4、x=100; /宏定义数组的大小typedef int ElemType; /定义一个元素类型为整型class seq /创建一个类将其进行封装private:ElemType elemmax; /存储数组为私有int front,rear; /在此建立私有的队列头、尾public:;b).单向链表定义：如下是单向链式的结构体包含一个数域和一个指下的指针域，数值域。并也对其用类进行封装，使其更佳。struct Node /单向链表中每个结点包含一个数域和一个指下的指针域 int data; /数值域Node *next; /指针域，指向链表的下一个结点class danx /建类进行封装pri
5、vate: Node *top; /创建头指针 public:; c).循环链表定义：如下是单向链式的结构体包含一个数域和一个指下的指针域，数值域。并也对其用类进行封装，使其更佳。其中含有一个头指针，用于对其中初始结点的指向。struct NodeType /链表结点的结构体 int num; /数值域，存储猴子编号NodeType *next; ; /指针域，指向下一个猴子结点class xunh private: NodeType *Head; / 将头指针设为私有public:;猴子选大王92.3 各功能模块1、数组方式包含有构造函数，析构函数，还有进行创建（即录入操作） ，与报数输出操
6、作。各功能模块如下：class seq /数组存储的类private:public:seq() / 数组存储的构造函数seq(); /析构函数void jin(); /输入存储操作void chu(); /报数输出操作;2、单向链表方式包含有构造函数，析构函数，还有进行创建（即录入操作），与报数输出操作。各功能模块如下：class danx / 单向链表的类 private: public:danx( ) ; /单向链表操作的构造函数danx() ; /析构函数void creat(); /创建链表，输入猴子信息void outs(); /报数输出操作;3、循环链表方式包含有构造函数，析构函数
7、，还有进行创建（即录入操作），与报数输出操作。各功能模块如下：class xunh /循环链表的类 private: public:xunh( ) ; /循环链表的构造函数猴子选大王10xunh() ; /析构函数void creat(); /创建循环链表，输入信息void outs(); /报数输出大王信息3 详细设计3.1 结构体定义1、数组结构体定义如下：对数组的大小进行限制在 100，并定义一个整型元素。const max=100; /宏定义数组上线大小为 100typedef int ElemType; /定义整型元素类型 ElemType2、单向链表结构体定义如下：单向链表中每个结
8、点包含一个数域和一个指下的指针域，定义值域，存储猴子编号，还定义一个指针域用与连接操作。struct Node /单向链表中每个结点包含一个数域和一个指下的指针域 int data; / 定义值域，存储猴子编号Node *next; ; /定义指针域指向下一个结点 3、循环链表结构体定义如下：struct NodeType /也包含数值域和一个指针域 int num; /值域，存储猴子编号 NodeType *next; ; /指针域指向下一个结点3.2 初始化其数组中表示头与尾的指针进行初始化：只要在数组类的构造函数中将定义的头与尾初始化到第一个数。class seqprivate:publ
9、ic:seq()front=0;rear=0; /将数组中头尾指针初始化指向第一个猴子选大王11数;3.3 插入操作1、如下是对数组方式功能的操作：创建，录入数组： void seq:jin() /创建操作 coutm; if(m100|m100|m=2)：“; cinn; /输入报数的值 coutm; for(i=0;inext=NULL; newp-data=i+1; if(i=0) /如果链表中还没有数据存入，将存入第一个数据 top=newp; /及将其在头结点 pre= top; else pre-next=newp; /如果头结点有元素，就存在为结点的下一 个 pre=newp;
10、/将尾结点指向下一个 void danx:outs( ) /单向链表的输出操作 int n,i; /n 为报数值,i 为局部循环数值 Node *q=top; while(q-next!=NULL) /将 p 指针指向连尾 q=q-next; /如果 q 还不是尾结点，就下移 猴子选大王13cout=2)：“; cinn; coutnext!=NULL) /当头结点的下一个为空时，表示报数结 束 Node *p; /创建一个指针，进行报数操作 for(i=1;inext; /报数时将头指针下移 p-next=NULL; /令 p 的指针域指空 q-next=p; /将 p 连接到连表尾 q=p
11、; /q 下移 p=top; top=top-next; /top 头指针下移 delete p; /删除报到指定数的结点 coutdatam; /输入猴子总数 for(i=0;inext=NULL; newp-num=i+1; if(i=0) /如果链表中还没有数据存入，将存入第一个数据 Head=newp; pre= Head; else /如果头结点有元素，就存在为结点的下一个 newp-next=Head; /将尾与头连接构成循环猴子选大王14pre-next=newp; pre=newp; void xunh:outs( ) /循环链表的输出操作 int n,i; /猴子总数 m，局
12、部数值 i NodeType *q=Head, *p; /新建结点 q 并指向头 cout=2)：“; cinn; /输入要报的数 coutnext!=q) /判断：当 qd 的下一个为空时，则报数结束 for(i=1;inext; /在循环中将不对未报到出局数的结点操 作，进行下一个报数 p-next=q-next; /将报到出局数的结点取出 delete q; /删除报到数的结点 q=p-next; /将断点连接 coutnumk; /用户输入选择 switch(k) case 1: /选择 1 就调用数组类的方式 s.jin(); /创建 s.chu(); /报数，输出 cout=1co
13、ut“n 再见!“;cout“n 按任意键，返回。“endl;return 0;4 调试分析由于此次的课程设计题目所需要的相关知识大多数可在数据结构书中找到，或借鉴。所以在完成代码后运行时，没出现严重错误和问题。只是有点小问题，即局部变量用错：没定义的也用了。调试并找出错误，进行修改。最后猴子选大王16获得成功。5 用户使用说明该系统具有简单、明了、使用等特点，能够方便、准确的计算出众多猴子编号选举大王的结果。当使用该系统时，系统会给出相关的提示信息，用户只需根据提示信息，即可完成系统提供的所有功能。6 测试结果6.1 界面运行结果系统运行主界面如图 6.1 所示：图 6.1 主界面6.2 子功能测试运行结果： A)数组方式选取大王, 如图 6.21 所示:猴子选大王17图 6.2 数组方式选举大王B) 单向链表方式选取大王，如图 6.22:图 6.3 单向选举大王C) 循环方式选举，如图 6.23 所示：猴子选大王18图 6.4 循环方式选举大王6.3 结束界面（如下图）图 6.5 结束界面猴子选大王19结 论在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程设计构思中选算法是一个很重要的概念。只有确定用什么算法后才能接下来的工作，将流程图画在纸上，再进行代码的编
