数据结构课程设计论文【报数出列】.doc

湖南科技学院课程设计报告课程名称：数据结构课程设计课程设计题目：报数出列游戏系：数学与计算科学系专 业：信息与计算科学年级、班：信计0701姓 名：陈爱明学 号：200705002031指导教师：牛志毅职 称：讲师2009年12月目录1 课程设计的教学目的和任务 -12 课程设计的主要内容 -12.1 问题分析和任务定义 -12.2逻辑设计 -22.3物理设计 -32.4 程序调试与测试 -32.5 初步测试结果分析 -33 课程设计报告的要求 -44 课程设计的题目 -45 课程设计的源代码 -45.1 头文件 -45.2 可执行文件 -55.3 主函数 -126 课程设计的最终测试结果 -146.1 整个操作过程与运行结果 -146.2 最终结果分析 -157 课程设计总结 -168 参考资料 -161 课程设计的教学目的和任务 使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 使学生能用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2 课程设计的主要内容2.1 问题分析和任务定义在编号为1,2,n（n0）个人按顺时针方向围坐一圈，每人持有一个正整数密码。则这个圈我们可以用循环链表来表示，即用循环链表的数据结构来保存着n个人的信息，其中每个人作为链表中的n个结点。而每个人都有“序列号”与“密码”的信息，所以我采用一个结构体来保存这两项信息。为了能够使得n个结点能连成一个环，即一个“圈”，则在建立链表的每个结点时要有保存下一个结点地址的指针域，所以链表的结点有一个数据域与一个指针域。其中，数据域是一个结构体类型，用来保存每个人的“序列号”与“密码”；指针域是链表结点类型，用来保存下一个结点的地址。因此，链表的每个结点类型也是一个结构体类型。创建链表时，由于是要创建循环链表，则新开辟进来链表中的结点的指针域都要指向链表的头结点，即要保证链表的头尾结点连接起来。第一次报数是从第一个人开始，停止报数的上限是一个随机的数，在此，可以人工控制，即从键盘输入一个数。当停止报数时，要把出队结点的密码记下，作为下一次的报数上限，所以每次结点出队前，要先保存他的密码。而最后要输出报数的出队序列，所以也要记下出队结点的序列，在此，我用一个数组来保存，最后直接输出数组中保存的元素就是出队的序列。每次出队一个结点，都要从1开始重新报数，所以要定义一个计数器，当有人出队时，计数器要重新初始化为1。这是一个循环链表的数据结构操作，所以，没访问一个结点，指针域都要及时地向后移动。此游戏要使得所有结点都出队才结束，所以要使用循环结构来控制：有n个人就要循环n次出队操作，每出队一个结点，人数要减1，而且及时地初始化计数器。由于删除循环链表的结点操作难以实现，所以我可以采用“每个结点出队后，数据域赋值为0”的方法来控制。由于链式结构的链表在建立时就带有一个头结点，而头结点又不能用来保存消息，所以要给与特殊的标志以区分头结点和其他结点。在此，我用赋0值的方法来解决，即头结点的数据域中的“序列号”与“密码”都赋值为0。所以，当遇到数据域为0的结点，就表示此节点为头结点与已经出队的节点，此时，要跳过不报数。在整个过程中，涉及到的要实现的功能比较多，所以我采用“分模块”的方法，把整个过程划分为不同的功能函数来实现。为了让使用者了解本程序有哪些基本功能，我可以采用一个人机交流的接口，即展示界面的函数void jiekoumian()。首先，定义链表结点数据域的结构体类型，包含两个数据成员，一个保存结点序列号，一个保存结点的密码。在此，由于密码也是不知道的，所以我引入随机函数，用来产生随机密码。接着，要定义链表的节点类型，同样是一个结构体类型，也有两个成员，一个是数据域，一个是指针域。第二步，定义单循环链表。此时要对链表进行初始化，所以要建立初始化链表函数void initList(LinkList& L)。第三步，创建单循环链表。根据要参加进入链表的人数n，创建有n个节点的链表，同时把创建链表结点的数据域。因此要编写创建单循环链表函数void createList(LinkList& L, int n,int *codes)。第四步，输出与清理工作。要得到游戏的结果，就要建立输出报数出列函数void chulie(LinkList& L,int n,int m)。为了保护系统，节省内存空间，则要进行清理工作，所以要建立清空单循环链表函数void clearList(LinkList& L)。第五步，测试。在此，有两项测试工作：一，测试操作是否成功，最主要是测试清理工作是否成功，所以建立测试被清空的单循环链表是否为空的函数void print3(LinkList& L)；二，测试结果，为了操作的方便，我可以建立一个规模很小的链表（输入人数较少）进行测试，再与我们自己人工进行游戏的结果比较。2.2逻辑设计本问题涉及的操作对象，最主要就是单循环链表。对于单循环链表，基本操作的对象就是链表结点，结点是一个结构体类型。其中有数据域：data，保存结点的消息，即每个人的“序列号”与“密码”；指针域：next，保存下一个结点的地址。本程序的数据结构最主要就是单循环链表、数组、指针等。基本功能的函数实现说明如下：函数名称函数主要原型实现功能的简单描述界面展示函数Void jiekoumian ()为了使用者清楚本程序的功能，在界面展示本程序中涉及到的主要实现功能。初始化单循环链表链表函数VoidinitList()定义了链表后，要对链表进行操作，先初始化链表，即建立一个空链表。创建单循环链表函数void createList()把要进入链表的节点串联起来，建立头尾相连的循环链表。输出初始单循环链表函数void print1()第一次创建了链表，还没进行报数出列游戏，先输出初始链表的基本信息。报数出列函数void chulie ()实现游戏的规则，而且输出游戏结果，即输出报数出队的序列。清空单循环链表函数void clearList ()为了保护系统，进行清理工作，释放单循环链表占有的内存空间。输出报数出队后单循环链表Void print2 ()为了了解报数出列后链表中的信息，输出各个节点的数据域以验证游戏过程。测试循环链表是否为空函数Void print3()游戏后，清空了链表，要进行测试链表是否为空，输出测试结果。每个功能函数作为一个小模块，首先调用界面展示函数void jiekoumian()。再根据实现的需要，从列出的清单中输入相应的操作：第一：请输入 1 确认要进入游戏！确认后，首先调用清屏函数system(cls)，即可进入人机交流界面，让使用者了解本程序涉及到的基本功能。第二：确认进入游戏，请按：1 否则结束请按：0在第一种情况下，游戏开始，调用随机函数产生密码。接着要输入参加游戏的人数，进入游戏中。在第二种情况下，结束整个游戏。 第三：请问是否要展示初始密码？（1：要，0：不要）在第一种情况下，则进行输出流操作，输入初始密码。在第二种情况下，跳过输出流操作。第四：请问是否要输出原始链表？（1：要，0：不要）在第一种情况下，调用输出开始创建的链表函数print1()，此时可以输出创建的初始链表。在第二种情况下，跳过输出函数print1()。无论第一、第二种情况，使用者都会得到提醒请输入开始游戏时的报数上限：。输入后，接着调用报数出列函数chulie()。此时输出游戏的结果，即出队序列。第五：请问是否要输出报数出列游戏后的链表？（1：要，0：不要）在第一种情况下，调用报数出队后的单循环链表输出函数print2()，此时将得到报数数列游戏后的链表信息。在第二种情况下，跳过输出函数print2()。无论第一、第二种情况，系统都将进行清理工作，即调用清空单循环链表函数clearList()，进行系统内存清理工作。第六：请问是否要测试链表是否为空？（1：要，0：不要）在第一种情况下，调用测试链表是否被清空函数print3()。此时假如整个过程的操作有误，则聊表不空，接着将输出链表中的信息；操作无误的话，用样给出测试结果：“ *链表已经空啦！*”。在第二种情况下，跳过测试链表是否被清空函数print3()，直接结束整个过程。以上的每一步操作都会有不同的结果展现在人机交流界面上，而且 每一步操作后都有一个提醒下一步操作的信息。这样，每一步操作的逻辑性很清晰，即可达到本程序逻辑设计的目的。2.3物理设计对于程序源代码部分，见5 课程设计的源代码。以下列出本程序算法中函数的调用框架：jiekoumian()system(cls)createList()initList()print1()chulie ()print2 ()print3 ()clearList () 2.4 程序调试与测试在测试本程序之前，为了操作的方便，我不采用随机函数产生密码的方式，而是同过自己从键盘上输入一些较小的数据，进行一下测试。测试创建链表函数与报数出列函数的结果为：输入 参加本游戏的人数：5开始时报数的上限：3 原始密码：7 2 4 8 6创建链表函数得到结果为：序列号 密码1 72 23 44 85 6 出列函数得到结果为：出队序列为：3 2 5 4 12.5 初步测试结果分析本测试得到的结果刚好和我在实践中进行真正游戏时得到的结果是一致的，出队序列刚好符合设置游戏规则，而且输出的格式很清晰。但是，这只是一个小规模情况下得到的结果，而且，随机密码要自己输入，很麻烦。因此，为了测试大规模情况下各个功能函数是否也能得到正确的结果，为了避免输入密码数据的麻烦，我转向为采用了随机函数产生密码的方法来操作，所得到的结果在最终的测试结果中。3 课程设计报告的要求课程设计报告要求规范书写。应当包括如下内容： 问题描述：描述要求编程解决的问题。 基本要求：给出程序要达到的具体的要求。 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。 算法思想：描述解决相应问题算法的设计思想。 模块划分：描述所设计程序的各个模块（即函数）功能。 数据结构：给出所使用的基本抽象数据类型，所定义的具体问题的数据类型，以及新定义的抽象数据类型。 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。 测试情况：给出程序的测试情况，并分析运行结果。 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。 参考文献：列出参考的相关资料和书籍。4 课程设计的题目设编号为1,2,n（n0）个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。（要求使用单循环链表）5 课程设计的源代码5.1 头文件#ifndef KCSJ_H_INCLUDED#define KCSJ_H_INCLUDED#include#define N 100 /N值用来限定人数using namespace std;/定义链表结点的数据域的类型struct Elemint id; /保存结点的序列号，为1、2、3int code; /保存每个结点的密码，由随机函数产生;typedef Elem ElemType; /重新定义类型，提高通用性/链表的结点类型struct LNodeElemType data; /保存本结点的数据域，有序列和密码LNode* next; /指向下一个结点指针;typedef LNode* LinkList;/展示界面函数void jiekoumian();/初始化单循环链表void initList(LinkList& L);/创建单循环链表函数，n是链表中的人数，codes保存密码数组void createList(LinkList& L, int n,int *codes);/输出初始单循环链表函数void print1(LinkList& L);/报数出列函数，n是人数，m是初始输入的报数上限值void chulie(LinkList& L,int n,int m);/清空单循环链表函数void clearList(LinkList& L);/输出报数出队后的单循环链表void print2(LinkList& L);/测试被清空的单循环链表是否为空函数void print3(LinkList& L);#endif / KCSJ_H_INCLUDED5.2 可执行文件#includekcsj.h/初始化单循环链表函数void initList(LinkList& L) L=new LNode; if (!L) exit(1); /存储空间分配失败 L-next=NULL;/创建单循环链表函数，n是链表中的人数，codes保存密码数组void createList(LinkList& L,int n,int *codes) LinkList p; LinkList r=L; /为了保存头指针L而设置变量r /*循环单链表有头结点，为了区别其他结点， 给头结点的数据域都赋0值*/ L-data.id=0; L-data.code=0; for (int i=0;idata).code=codesi; /传进来的密码保存到数据域中 (p-data).id=i+1; /序列从1开始 p-next=L; /建立循环链表，则新节点的指针域链接到链表的头指针 r-next=p; /连接新结点 r=r-next; /指针后移 /输出初始单循环链表void print1(LinkList& L) LinkList r=L; coutendl创建的原始链表为：endl; cout序列号 密码next; /链表带有头结点，则要从头结点的下一个结点开始输出 while(r!=L) /循环链表，当头尾指针相等时就是遍历一圈了 cout data).id data).code; r=r-next; coutendl; /报数出列函数，n是人数，m是初始输入的报数上限值void chulie(LinkList& L,int n,int m) coutendl 报数出列游戏开始！data).code; /m保存结点的密码 idsj+=r-data.id; /出队序列保存到数组ids中 r-data.id=0; /每个结点出队后，数据域赋值为0 r-data.code=0; size-; /每出队一个，链表中的人数要减1 r=r-next; /结点出队后，本节点的指针要后移 i=1; /每一个节点出队后，计数器又从1开始 else i+; /计数器的值与m值不等时计数器加1 r=r-next; /计数器加1后指针要后移 if(r-data.id=0) /数据域为0的表示头结点与已经出队的节点 i-; /遇到头结点与已经出队的节点要跳过去，所以计数器减1 coutendl出队序列：endl; for(int k=0;kn;k+) /输出报数出队的序列 coutidsk ; coutnext,p; L-next=NULL; /头结点的下一个结点赋为空 while (r!=NULL) /每个结点都要清空 p=r; r=r-next; delete p; /释放结点空间 /输出报数出队后的单循环链表void print2(LinkList& L) LinkList r=L; coutendl报数出队后的链表为：endl; cout序列号 密码next; /链表带有头结点，要从头结点的下一个开始输出 while(r!=L) /这是循环链表，只要头尾指针不相等就还没遍历完 cout data).id data).code; r=r-next; /每输出一个节点指针要后移 coutendl; coutendl; cout O(_)O 链表结点都已经出队，所以数据域都是0！next; /链表带头结点，都是要从头结点的下一个结点开始 if(r=NULL) coutendl *链表已经空啦！*endl; else coutendl没有被清空的链表为：endl; cout序列号 密码endl; while(r) /链表没有被清空时，只要指针不空就循环 cout data).id data).code; r=r-next; coutendl; cout链表没有清空，而且结点都已经出队，所以数据域都是0！endl; /展示界面函数void jiekoumian() int t; cout游戏开始()/啦啦啦endl; coutendlt; system(cls); /先清屏再说明各功能 cout $ 创建本游戏要实现如下功能 $ endl; cout-*- -*-endl; cout-*- -*-endl; cout-*- 一、定义单循环链表 -*-endl; cout-*- -*-endl; cout-*- 二、初始化循环链表 -*-endl; cout-*- -*-endl; cout-*- 三、创建单循环链表 -*-endl; cout-*- -*-endl; cout-*- 四、确定要出列规则 -*-endl; cout-*- -*-endl; cout-*- 五、打印出列的序列 -*-endl; cout-*- -*-endl; cout-*- 六、清空单循环链表 -*-endl; cout-*- -*-endl; cout-*- 七、测试链表是否空 -*-endl; cout-*- -*-endl; cout-*- -*-endl; cout $ 所有功能用单循环链表实现 $ endl;5.3 主函数#include #includekcsj.husing namespace std;int main() int num; /num用来保存要进入链表中的人数 int codesN; /codes数组用来保存随机函数产生的密码 cout $ 欢迎各位朋友来参加报数出列游戏 $ endl; jiekoumian(); /界面接口展示 cout确认进入游戏，请按：1 否则结束请按：0t; if(t=1) coutendl请输入参加本游戏的人数(不超过：Nnum; for(int i=0;inum;i+) codesi=rand(); /随机函数产生密码 coutendlk; if(k=1) coutendl由随机函数产生的原始密码为:endl; for(int j=0;jnum;j+) coutcodesj ; /输出原始密码 coutendl; if(t=0) return 0; /结束游戏 LinkList L; initList(L); /初始化链表 createList(L,num,codes); /创建单循环链表 coutendli; if(i=1) print1(L); /输出开始创建的链表 int m; /开始时的报数上限 coutendlm; chulie(L,num,m); /游戏开始后报数出列函数 coutendlj; if(j=1) print2(L); /报数出列后的链表 clearList(L); /清空链表 coutendlk; if(k=1) print3(L); /测试链表是否被清空函数，不空则输出链表数据域 coutendl O(_)O 游戏已经结束 ()/ endl; coutendl *-谢谢大家的参与-*endl; return 0;6 课程设计的最终测试结果6.1 整个操作过程与运行结果 $ 欢迎各位朋友来参加报数出列游戏 $ 游戏开始()/啦啦啦请输入 1 确认要进入游戏！ 1 $ 创建本游戏要实现如下功能 $ -*- -*- -*- -*- -*- 一、定义单循环链表 -*- -*- -*- -*- 二、初始化循环链表 -*- -*- -*- -*- 三、创建单循环链表 -*- -*- -*- -*- 四、确定要出列规则 -*- -*- -*- -*- 五、打印出列的序列 -*- -*- -*- -*- 六、清空单循环链表 -*- -*- -*- -*- 七、测试链表是否空 -*- -*- -*- -*- -*- $ 所有功能用单循环链表实现 $ 确认进入游戏，请按：1 否则结束请按：0 1请输入参加本游戏的人数(不超过：100): 18请问是否要展示初始密码？（1：要，0：不要） 1由随机函数产生的原始密码为:41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942请问是否要输出原始链表？（1：要，0：不要） 1创建的原始链表为：序列号 密码1 412 184673 63344 265005 191696 157247 114788 293589 2696210 2446411 570512 2814513 2328114 1682715 996116 49117 299518 11942请输入开始游戏时的报数上限：500 报数出列游戏开始！出队序列：14 10 9 18 17 5 12 4 3 16 6 8 7 15 1 11 13 2请问是否要输出报数出列游戏后的链表？（1：要，0：不要） 1报数出队后的链表为：序列号 密码0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0 O(_)O 链表结点都已经出队，所以数据域都是0！请问是否要测试链表是否为空？（1：要，0：不要）