数据结构课程设计报告-猴子选大王+ joseph环+纸牌游戏.doc

上海应用技术学院课程设计报告课程名称 数据结构课程设计 设计题目 猴子选大王+ joseph环+纸牌游戏 院系 计算机科学与信息工程学院 专业 计算机科学与技术 班级 姓名 学号 指导教师 日期 11/15/2019 一. 目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力二. 课程设计内容说明1. 猴子选大王(1) 对设计任务内容的概述任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。(2) 需求分析或功能描述首先要定义数据类型，定义一个结构体， 包含猴子的编号和指向下一个猴子的指针。然后，根据猴子的数量m创建一个循环链表，相当于所有的猴子围成一圈。最后根据N的值，将猴子依次离开此循环链表，输出猴子离开的顺序，将最后一个输出的猴子为猴王。(3) 概要设计或程序流程图开始定义结构体存储猴子创建循环链表m=nYesYesfor(i=1;inext; 结束输入m,nm,n输出猴王编号: p-data输出p-next-dataq=p-nextfree(q)p!=p-nextNo猴子选大王流程图(4) 详细设计或源代码说明文件“list1.cpp”typedef int Elemtype;typedef struct Mnode/创建结构体 Elemtype data;/猴子编号 struct Mnode *next;/指向下一个猴子的指针 MNode;/函数声明 struct Mnode* Creat_clist1(MNode *clist1,int a);int Kingmonkey(MNode*clist1,int a,int b);int list1()/主函数直接调用函数 int m,n;/用来存储猴群的数量， S1:printf(请输入猴群的数量m：);scanf(%d,&m);/猴群数量 printf(请输入每数到第N个n：);scanf(%d,&n);/每次数N个 if(m=1;i-)p=(MNode*)malloc(sizeof(MNode); /开辟内存空间 p-data=i;/猴子编号 p-next=clist1;clist1=p;if(i=a)q=p; /用q指向链表最后一个结点 q-next=clist1; /构成循环链表 return clist1; /clist1即为指向第一个结点的指针/运算并输出猴王函数 int Kingmonkey(MNode*clist1,int a,int b)MNode *p,*q;p=clist1;int i;printf(猴子依次离开此圈的编号顺序为：);do/依次让猴子离开 ，只留最后一只猴子 for(i=1;inext; printf(%d ,p-next-data); q=p-next; /q结点为要删除的结点 p-next=p-next-next;/将q借点忽略 p=p-next;free(q);/删除q while(p!=p-next);/是否只剩下最后一个结点 printf(n);printf(猴王的编号是：%dn,p-data); /输出猴王编号 printf(n);return 0;(5) 程序模块及其接口描述1、函数名：list1()调用参数：无调用方式：main()调用返回值：02、函数名：Creat_clist1(MNode *clist1,int a)调用参数：monkey,m/ monkey：指向第一个结点的指针；m:猴子个数调用方式：list1()调用返回值：monkey /monkey：指向第一个结点的指针3、函数名：Kingmonkey(MNode*clist1,int a,int b)调用参数：monkey,m,n / monkey：指向第一个结点的指针；m：猴子个数调用方式：list1()调用返回值：0(6) 程序的输入与输出描述输入：猴群的数量m每数到N个n输出：猴子依次离开此圈的编号顺序猴王的编号(7) 调试分析或程序测试 (8) 尚未解决的问题或改进方向无(9) 对软件的使用说明在主菜单输入1，可进入猴子选大王模块。根据提示输入要输入的数值，敲回车后，输出结果。2. joseph环(1) 对设计任务内容的概述任务：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。(2) 需求分析或功能描述首先要定义数据类型，定义一个结构体， 包含人的编号、人的密码和指向下一个人的指针。然后，根据人的数量n创建一个循环链表，相当于所有的人围成一圈。最后根据任意给定的正整数m的值，将人依次离开此循环链表，输出人离开的顺序。(3) 概要设计或程序流程图开始创建循环链表输入n.mm,n定义结构体存储人定义数组p100存密码Yesfor(i=1;inext; 结束输出最后一个人的编号: p-data输出p-next-dataq=p-nextfree(q)p!=p-nextNob=p-numjoseph环流程图(4) 详细设计或源代码说明文件“list2.cpp”typedef int Elemtype;typedef struct Pnode/创建结构体Elemtype data;/人的编号int num;/人的密码 struct Pnode *next;PNode;/函数声明struct Pnode* Creat_clist(PNode*clist,int a,int b);int Goout(PNode*clist2,int a,int b);int list2()int m,n,i;printf(请输入人的数量n：);scanf(%d,&n);/存储人的数量 printf(请输入初始密码值m：);scanf(%d,&m);/存储给定任意正整数 /存储密码的数组 int p100=3,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,4,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,3,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,1,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,2,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2;PNode *people; /定义结点指针people=NULL;/指针指向为空 people=Creat_clist(people,n,p); /建立人的循环链表printf(n);printf(从1-%d的人对应密码为:,n);for(i=0;i=1;i-)p=(PNode*)malloc(sizeof(PNode);/开辟内存空间p-data=i;/人的编号p-num=bj;/人对应的密码j-; p-next=clist2;clist2=p;if(i=a)q=p; /用q指向链表最后一个结点,头插法 q-next=clist2;/构成循环链表 return clist2; /clist即为指向第一个结点的指针/运算并输出人的出列顺序函数 int Goout(PNode*clist2,int a,int b)PNode *p,*q;/定义两个 PNode型指针 p=clist2;int i;printf(人依次出列的编号顺序为：);dofor(i=1;inext; printf(%d ,p-next-data);b=p-next-num; q=p-next; /q节点为要删除的结点 p-next=p-next-next;/P指向下下个结点 p=p-next;free(q);/删除qi=1;while(p!=p-next);/是否只剩下最后一个结点printf(%dn,p-data);/输出最后一个人的编号 return 0;。(5) 程序模块及其接口描述1、函数名：list2()调用参数：无调用方式：main()调用返回值：02、函数名：Creat_clist(PNode *clist2,int a,int b)调用参数：people,n,p/people:指向第一个结点的指针;n:人的个数；p: 密码数组首地址调用方式：list2()调用返回值：people /people:指向第一个结点的指针3、函数名：Goout(PNode*clist2,int a,int b)调用参数：people,n,m / people:指向第一个结点的指针; n:人的个数；m:第一个任意给定的密码值调用方式：list2()调用返回值：0(6) 程序的输入与输出描述输入：人的数量n初始密码值m输出：从1n的人对应密码人依次出列的编号顺序(7) 调试分析或程序测试 。(8) 尚未解决的问题或改进方向无(9) 对软件的使用说明在主菜单输入2，可进入joseph环模块。根据提示输入要输入的数值，敲回车后，输出结果。3. 纸牌游戏(1) 对设计任务内容的概述任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？(2) 需求分析或功能描述首先要定义数据类型，定义一个结构体， 包含扑克牌的编号，标记和指向下一张扑克牌的指针。然后，根据猴子的数量k=52创建一个单链表，再调用Turn()函数，从2-52，按操作要求反转。最后根据count的值是否为0，输出此时标号为o的扑克牌编号。(3) 概要设计或程序流程图开始创建结构体创建单链表如p-count=0则p-count=1 如p-count=1则p-count=0结束2=idata)%i=0Yesp=p-nextYesNoNoq=head-nextq!=NULLNoYesq-count=0输出：q-dataq=q-nextYesNo纸牌游戏流程图(4) 详细设计或源代码说明typedef struct node/创建结构体int data; /扑克牌的编号 int count; /扑克牌标记 struct node *next;/指向下一张扑克牌的指针 LinkList; /函数声明LinkList *creat(int k);LinkList *Turn(LinkList *head,int k);void Display(LinkList *head) ;int list3() int i,k=52; LinkList *head,*p;/定义结点指针 p=creat(k); /创建单链表 p=Turn(p,k);/从2-52，按操作要求反转 printf(n); Display(p);/输出最后正面向上的牌 printf(n); system(pause); return 0;LinkList *creat(int k) /创建单链表 LinkList *head,*p,*q;/定义结点指针 int i=0; head=(LinkList *)malloc(sizeof(LinkList);/分配内存空间 p=head; /p指向头结点 q=(LinkList *)malloc(sizeof(LinkList);/分配内存空间 while(idata=i+1; q-count=0; p-next=q; p=q; q=q-next; q=(LinkList *)malloc(sizeof(LinkList);/分配内存空间 i+; p-next=NULL;/尾结点的next置空 return(head);/从2-52，按操作要求反转 LinkList *Turn(LinkList *head,int k)LinkList *p; for(int i=2;inext; while(p!=NULL) if(p-data)%i=0)/判断是否为i的倍数 if(p-count=0)/count是1则变为0 ，count是0则变为1 p-count=1; else p-count=0; p=p-next; return(head);/输出最后正面向上的牌的函数 void Display(LinkList *head) LinkList *q; q=head-next; printf(正面向上的牌编号为：); while(q!=NULL) if(q-count=0) /若标号为0则输出 printf(%d ,q-data); q=q-next; printf(n);(5) 程序模块及其接口描述1、函数名：list3()调用参数：无调用方式：main()调用返回值：02、函数名：creat(int k);调用参数：k /k=52,52张牌的编号调用方式：list3()调用返回值：p /p:指向第一个结点的指针;3、函数名：Turn(LinkList *head,int k)调用参数：p,k /p:指向第一个结点的指针;k:52张牌编号调用方式：list3()调用返回值：p /p:指向第一个结点的指针;4、函数名：Display(LinkList *head);调用参数：p /p:指向第一个结点的指针调用方式：list3()调用返回值：0(6) 程序的输入与输出描述输入：无输出：输出最后正面向上的牌(7) 调试分析或程序测试(8) 尚未解决的问题或改进方向无(9) 对软件的使用说明在主菜单输入3，回车，可进入纸牌游戏模块，输出最后正面向上的牌。4. 帮助(1) 对设计任务内容的概述对项目的内容进行说明。(2) 需求分析或功能描述帮助中还有对3个项目的说明：1、猴子选大王2、joseph环3、纸牌游戏(3) 概要设计或程序流程图开始输入ijoseph环1=i=1& i=3)break;elseprintf(输入错误，);printf(请选择1-3:);switch (i)case 1:Display1();break;case 2:Display2();break;case 3:Display3();break;int Display1()printf( 猴子选大王 nn);printf( *nn);printf( *任务：一堆猴子都有编号，编号是1，2，3 ，.m ,*nn); printf( * 这群猴子（m个）按照1-m的顺序围坐一圈，从*nn); printf( * 第1开始数，每数到第N个，该猴子就要离开此*nn); printf( * 圈，这样依次下来，直到圈中只剩下最后一只*nn);printf( * 猴子，则该猴子为大王. *nn);printf( *要求：输入数据：输入m,n m,n 为整数，nm。 *nn);printf( *输出形式：中文提示按照m个猴子，数n 个数的方法,*nn);printf( * 输出为大王的猴子是几号 ，建立一个函数来 *nn);printf( * 实现此功能 . *nn);printf( *nn);system(pause);return 0;int Display2()printf( joseph环 nn);printf( *nn);printf( *任务：编号是1，2，,n的n个人按照顺时针方向 *nn); printf( * 围坐一圈，每个人只有一个密码(正整数)。一*nn); printf( * 开始任选一个正整数作为报数上限值m,从第一*nn); printf( * 个人开始顺时针方向自1开始顺序报数，报到 *nn);printf( * m时停止报数。报m的人出列，将他的密码作 *nn);printf( * 为新的m值，从他在顺时针方向的下一个人开 *nn);printf( * 始重新从1报数，如此下去，直到所有人全部 *nn);printf( * 出列为止。设计一个程序来求出出列顺序。 *nn);printf( * 实现此功能. *nn);printf( *要求：利用单向循环链表存储结构模拟此过程，按照*nn); printf( * 出列的顺序输出各个人的编号。 *nn); printf( *测试数据：m的初值为20，n=7 ,7个人的密码依次为 *nn); printf( * 3，1，7，2，4，7，4，首先m=6,则正确的输 *nn);printf( * 出是什么？ *nn);printf( * 要求：输入数据：建立输入处理输入数据，输入m *nn);printf( * 的初值，n ，输入每个人的密码，建立单循 *nn);printf( * 环链表。 *nn);printf( *输出形式：建立一个输出函数，将正确的输出序列 *nn);printf( *nn);system(pause);return 0;int Display3()printf( 纸牌游戏 nn);printf( *nn);printf( *任务：编号为1-52张牌，正面向上，从第2张开始， *nn); printf( * 以2为基数，是2的倍数的牌翻一次，直 到最 *nn); printf( * 后一张牌；然后，从第3张开始，以3为基数，*nn); printf( * 是3的倍数的牌翻一次，直到最后一张牌；然 *nn);printf( * 后，从第4张开始，以4为基数，是4的倍数的 *nn);printf( * 牌翻一次， 直到最后一张牌；.再依次5的 *nn);printf( * 倍数的牌翻一次，6的，7的直到以52为基数的*nn);printf( * 翻过，输出：这时正面向上的牌有哪些？ *nn);printf( *nn);system(pause);return 0;(5) 程序模块及其接口描述1、函数名：list4()调用参数：无调用方式：main()调用返回值：02、函数名：Display1()调用参数：无调用方式：list4()调用返回值：03、函数名：Display2()调用参数：people,n,m调用方式：list4()调用返回值：04、函数名：Display3()调用参数：无调用方式：list4()调用返回值：0(6) 程序的输入与输出描述输入：输入对应数字（1/2/3）输出：输出对应的项目的文字说明(7) 调试分析或程序测试 (8) 尚未解决的问题或改进方向无(9) 对软件的使用说明在帮助菜单输入1/2/3，回车，会输出对应项目的说明。二. 结论及体会经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。在此期间我失落过，也曾一度热情高涨。点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。 这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。 这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也时用错了方法，总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。主函数流程图开始输入040=i=4YesNoList1()List2()List3()List4()i=1i=2i=3i=4退出i=0主函数流程图附录1：参考文献1 数据结构教程（第3版），李春葆，清华大学出版社，20102数据结构，杨剑，清华大学出版社，20113数据结构(C语言版)，严蔚敏 吴伟民，清华大学出版社，19974Data Structures Using C数据结构（C语言版），R Krishnamoorthy、G Indirani Kumaravel，清华大学出版社，2009-95C+数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译， 清华大学出版社，2004 6计算机算法设计与分析（第2版），王晓东， 电子工业出版社， 2004附录2：部分源代码清单本课程设计共有5份代码：“main.cpp”“list1.cpp”“list2.cpp”“list3.cpp”“list4.cpp”1. “main.cpp”#include #include #include list1.cpp#include list2.cpp#include list3.cpp#include list4.cppint main()int i,flag=1;while (flag)L1:printf( 主菜单 n);printf( *nn);printf( * 1.猴子选大王 *nn); printf( * 2.joseph环 *nn); printf( * 3.纸牌游戏 *nn); printf( * 4.帮助 *nn);printf( * 0.退出 *nn);printf( *nn);printf( 请选择:);while (true)scanf(%d,&i);if (i=0 & i=4)break;elseprintf(输入错误，);printf(请选择0-4:n);switch (i)case 1:list1();break;case 2:list2();break;case 3:list3();break;case 4:list4();break;case 0: flag=0;break;2. “list1.cpp”typedef int Elemtype;typedef struct MnodeElemtype data;struct Mnode *next;MNode;struct Mnode* Creat_clist1(MNode *clist1,int a);int Kingmonkey(MNode*clist1,int a,int b);int list1()int m,n;S1:printf(请输入猴群的数量m：);scanf(%d,&m);printf(请输入每数到第N个n：);scanf(%d,&n);if(m=1;i-)p=(MNode*)malloc(sizeof(MNode);p-data=i;p-next=clist1;clist1=p;if(i=a)q=p; /用q指向链表最后一个节点 q-next=clist1; /构成循环链表 return clist1; /clist即为指向第一个节点的指针int Kingmonkey(MNode*clist1,int a,int b)MNode *p,*q;p=clist1;int i;printf(猴子依次离开此圈的编号顺序为：);dofor(i=1;inext; printf(%d ,p-next-data); q=p-next; /q节点为要删除的节点 p-next=p-next-next;p=p-next;free(q);while(p!=p-next);printf(n);printf(猴王的编号是：%dn,p-data);printf(n);return 0;3. “list2.cpp”typedef int Elemtype;typedef struct PnodeElemtype data;int num;struct Pnode *next;PNode;struct Pnode* Creat_clist(PNode*clist,int a,int b);int Goout(PNode*clist2,int a,int b);int list2()int m,n,i;printf(请输入人的数量n：);scanf(%d,&n);printf(请输入初始密码值m：);scanf(%d,&m);int p100=3,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,4,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,3,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,1,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2,2,1,7,2,4,7,4,6,3,6,8,3,5,4,2,1,6,3,4,2;PNode *people; people=NULL;people=Creat_clist(people,n,p); printf(n);printf(从1-%d的人对应密码为:,n);for(i=0;i=1;i-)p=(PNode*)malloc(sizeof(PNode);p-data=i;p-num=bj;j-; p-next=clist2;clist2=p;if(i=a)q=p; /用q指向链表最后一个节点,头插法 q-next=clist2; /构成循环链表 return clist2; /clist即为指向第一个节点的指针int Goout(PNode*clist2,int a,int b)PNode *p,*q;p=clist2;int i;printf(人依次出列的编号顺序为：);dofor(i=1;inext; printf(%d ,p-next-data);b=p-next-num; q=p-next; /q节点为要删除的节点 p-next=p-next-next;p=p-next;free(q);i=1;while(p!=p-next);printf(%dn,p-data);return 0;4. “list3.cpp”typedef struct nodeint data; int count; struct node *next;LinkList;LinkList *creat(int k);LinkList *Turn(LinkList *head,int k);void Display(LinkList *head) ;int list3() int i,k=52; LinkList *head,*p; p=creat(k); p=Turn(p,k); printf(n); Display(p); printf(n); system