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

上海应用技术学院课程设计报告 课程名称 《数据结构课程设计》 设计题目 猴子选大王+ joseph环+纸牌游戏 院系 计算机科学与信息工程学院 专业 计算机科学与技术 班级 姓名 学号 指导教师 日期 7/7/2013 目的与要求 巩固和加深对常见数据结构的理解和掌握 掌握基于数据结构进行算法设计的基本方法 掌握用高级语言实现算法的基本技能 掌握书写程序设计说明文档的能力 提高运用数据结构知识及高级语言解决非数值实际问题的能力 课程设计内容说明 猴子选大王 对设计任务内容的概述 任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 需求分析或功能描述 首先要定义数据类型，定义一个结构体， 包含猴子的编号和指向下一个猴子的指针。 然后，根据猴子的数量m创建一个循环链表，相当于所有的猴子围成一圈。 最后根据N的值，将猴子依次离开此循环链表，输出猴子离开的顺序，将最后一个输出的猴子为猴王。 概要设计或程序流程图 详细设计或源代码说明 文件“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=n) //判断输入数值是否符合要求 { goto S1; } printf(\n); MNode *monkey; //定义结点指针 monkey=NULL; monkey=Creat_clist1(monkey,m); //建立猴群的循环链表 Kingmonkey(monkey,m,n); //选出猴王并输出 system(pause); return 0; } //创建循环链表函数 struct Mnode* Creat_clist1(MNode *clist1,int a) { MNode *p,*q; //定义两个 MNode型指针 int i; clist1=NULL; //结点置空 for(i=a;i=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;ib-1;i++) { p=p-next; } 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(猴王的编号是：%d\n,p-data);