猴子选大王数据结构课程设计

用C++编写程序猴子选大王(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--湖南人文科技学院计算机系课程设计说明书课程名称: 数据结构课程代码:题目: 猴子选大王年级/专业/班: 06级计算机科学与技术专业一班学生姓名:学号:06408109 06408102 06408107 06408122 06408103指导教师: 刘刚常开题时间: 2008 年 6 月 16 日完成时间: 2008 年 6 月 29 日目录摘要..................................................................................................................... 错误!未定义书签。

一、引言............................................................................................................. 错误!未定义书签。

二、设计目的与任务......................................................................................... 错误!未定义书签。

三、设计方案....................................................................................................... 错误!未定义书签。

1、总体设计......................................................................................................... 错误!未定义书签。

[题目]第1.1猴子选大王问题一：实验内容：M只猴子要选大王，选举办法如下：所有猴子按1，2……n编号围成一圈，从第一号开始顺序1,2……m,凡是报m号的退出圈外，如此循环报数直到圈内只剩一只猴子时这只猴子就是大王。

二：实验要求：利用单向循环链表模拟此过程，输出选出的大王编号。

三：程序的设计思想：（1）问题分析：“猴子选大王”问题是约瑟夫环问题的一个特例。

由于本题目的数据元素个数不可知，所以可使用链表来动态的分配内存空间。

而该问题又是一个不断的循环问题所以用循环链表来实现。

（2）总体设计：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。

再给每只猴子建立顺序的编号。

现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过q->next=p->next删除该结点后继续运行否则让q成为p的前驱指针。

最后当p->next==p时停止运行，得到p所指向的结点即为猴子选出大王的编号。

四：提供测试结果：定义 n=8, m=3,测试结果如下：对猴子进行编号！1号猴子：12号猴子：23号猴子：34号猴子：45号猴子：56号猴子：67号猴子：78号猴子：82号猴子报：2 3号猴子报：3 3号猴被淘汰4号猴子报：1 5号猴子报：2 6号猴子报：3 6号猴被淘汰7号猴子报：1 8号猴子报：2 1号猴子报：3 1号猴被淘汰2号猴子报：1 4号猴子报：2 5号猴子报：3 5号猴被淘汰7号猴子报：1 8号猴子报：2 2号猴子报：3 2号猴被淘汰4号猴子报：1 7号猴子报：2 8号猴子报：3 8号猴被淘汰7号猴子报：24号猴子报：34号猴被淘汰7号猴子报：1胜出:7号猴子Press any key to continue五：程序源代码#include <stdio.h>#include <stdlib.h>#define n 8#define m 3typedef struct monkey{int num;struct monkey *next;} Monkey;int main(){Monkey *p,*head,*q;int i;head=p=q=malloc(sizeof(Monkey));//建立头指针 for(i=1;i<n;i++) //给n个结点分配空间{p=malloc(sizeof(Monkey));q=p;}q->next=head; //建立循环链表p=head;printf("对猴子进行编号！\n");for(i=1;i<=n;i++) //给n只猴子分别建立顺序编号{p->num=i;printf("%d号猴子：%d\n",p->num,p->num);p=p->next;}i=0; //初始化p=head;while(1){i++;printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; //判断还剩下最后一个结点时停止运行 if(i==m) //报道m的猴子淘汰{i=0;printf("%d号猴被淘汰\n",p->num);q->next=p->next;continue;}else{if(i==m-1) q=p;p=p->next;}}printf("胜出:%d号猴子",p->num); }。

重庆交通大学信息科学与工程学院综合性设计性实验报告专业：课程名称：《C语言程序设计》题目：数组和链表的操作班级：设计者：学号：指导教师：完成时间：2014年6月16日重庆交通大学信息科学与工程学院综合性设计性实验任务书重庆交通大学信息学院综合性设计性实验评分表数组和链表的操作——猴子选大王程序设计报告一、系统的功能需求及分析功能：一群猴子共有m只，编号为1，2，……m，围坐一圈，从第1号猴子开始依次报数，数到n的猴子退出，然后从退出的下一只猴子继续从1开始报数，依次循环，直到圈内剩下一只猴子为止，该编号的猴子就是所选出的大王。

分析：用数组实现：先对数组进行初始化，然后将报到要删除的那个数字的猴子编号赋值为-1，每赋值一次，猴子数减一，再重新报数。

当猴子数只有一只的时候，输出猴子编号不为-1的那个编号。

用链表实现：先建立一个无头节点的单向循环的链表，然后将报到要删除的那个数字的猴子编号删除，以此循环，直到一个节点的下一个指向自己，最后输出猴子编号。

二、设计说明(一) 用数组实现1、数组的初始化for(i=0;i<m;i++)a[i]=i+1;2、算法流程图及说明(二) 用链表实现1、节点的定义struct monkey{int a;struct monkey *next;}*p,*q,*p1,*q1,*p2;2、链表的建立for (int i=0;i<m;i++){p=(struct monkey *)malloc(sizeof(struct monkey));p->a=i+1;p->next=NULL;if (i==0){head=p;q=head;}else{q->next=p;q=q->next;}}q->next=head;p2=head;p1=head;3、算法流程图及说明三、主要代码(一) 用数组实现#include<stdio.h>void main(){int a[10000];int m,n,x,b,i;printf("请输入猴子的只数:");scanf("%d",&m);printf("请输入要删除的猴子编号:");scanf("%d",&n);for(i=0;i<m;i++)a[i]=i+1;b=m;x=0;for(i=0;b!=1;i++){if(a[i%m+1]!=-1){x++;}if(x==n && a[i%m+1]!=-1){a[i%m+1]=-1;b--;x=0;}}for(i=1;i<=m;i++)if(a[i]!=-1)printf("猴子大王编号为:%d\n",i);}(二) 用链表实现#include <stdio.h>#include <stdlib.h>struct monkey{int a;struct monkey *next;}*p,*q,*p1,*q1,*p2;void main(){struct monkey *head;int m,n;printf("请输入猴子的只数:");scanf("%d",&m);printf("请输入想删除猴子的编号:");scanf("%d",&n);for (int i=0;i<m;i++){p=(struct monkey *)malloc(sizeof(struct monkey));p->a=i+1;p->next=NULL;if (i==0){head=p;q=head;}else{q->next=p;q=q->next;}}q->next=head;p2=head;p1=head;for (i=1;;i++){if (i==n-1){q1=p1->next;p1->next=q1->next;free(q1);i=0;}p1=p1->next;if (p1->next==p1) break;}printf("猴子大王的编号为%d\n",p1->a);}四、系统功能测试功能：一群猴子共有m只，编号为1，2，……m，围坐一圈，从第1号猴子开始依次报数，数到n的猴子退出，然后从退出的下一只猴子继续从1开始报数，依次循环，直到圈内剩下一只猴子为止，该编号的猴子就是所选出的大王。

#include<stdio.h>#include<stdlib.h>struct Monkeyking{int data;struct Monkeyking *next;};void main(){struct Monkeyking *head, *s, *q, *t,*p,*h;int n, k, count=0, i,j;printf("输入猴子总数:");scanf("%d",&k);printf("\n");printf("输入报号起始猴子编号:");scanf("%d",&j);printf("\n");printf("输入报号间隔数:");scanf("%d",&n);printf("\n");for(i=0; i<k; i++){s=(struct Monkeyking *)malloc(sizeof(struct Monkeyking)); s->data=i+1;s->next=NULL;if(i==0){head=s;q=head;}else{q->next=s;q=q->next;}}//建立一个单链表q->next=head;//将单链表组成环状printf("输出猴子原始的编号:");q=head;while(q->next!=head){printf("%d ",q->data);q=q->next;}//依次输出节点的值printf("%d ",q->data);printf("\n");printf("\n");q=head;for (i=0;i<j;i++){p=q;q=q->next;}q=p;printf("输出被淘汰的猴子编号:");if (n==1){for (i=1;i<=k;i++){t=q;q=q->next;t->next=h;h=t;}for (i=1;i<=k;i++){printf("%d ",h->data);//倒序输出淘汰猴子的编号，第一个编号为大王h=h->next;}printf("\n");}else{do{count++;if(count==n-1){t=q->next;q->next=t->next;t->next=h;h=t;count=0;}q=q->next;}while(q->next!=q);q->next=h;h=q;}for(i=1;i<=k;i++){printf("%d ",h->data);//倒序输出淘汰猴子的编号，第一个编号为大王h=h->next;}}。

5.4.8 实验项目5-14：猴子选大王1、实验名称：猴子选大王2、实验目的：（1）熟练使用循环控制。

（2）熟练理解和掌握二维数组存储结构的使用技巧。

3、实验任务（1）实验内容：一群猴子要选新猴王。

新猴王的选择方法是：让n只候选猴子围成一圈，从某位置起顺序编号为1~n号。

从第1号开始报数（从1到3），凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。

如此不断循环，最后剩下的一只猴子就选为猴王。

请问是原来第几号猴子当选猴王？（2）实验要求：输入一个正整数n（n<=100），写一个程序来模拟这个过程，输出猴王的序号。

测试用例：4、实验要点分析（1）问题分析：用循环的方法模拟选猴王的过程。

一种简单的方法是对n只猴子用1~n 编号，编号存放在大小为n的一维整数数组中，若某编号的猴子要退出圈子，则把其编号改为-1。

若数组中只剩一个非-1的编号时，该编号的猴子就是大王。

开始时数组中的元素是从1到n的整数，表示都在“圈子”中，凡报到3的猴子退出圈子，即置为-1。

再依次查找下一只在“圈子”中的猴子，并重新开始报数。

这个过程进行n-1次，就只剩下一只编号不是-1的猴子了。

这种方法在寻找“下一个在圈子中的猴子”时可能会遇到很多“-1”而浪费时间。

另一种改进的方法是把n只猴子用0~n-1编号，数组的下标表示猴子的编号，数组元素的值表示相邻下一只在圈子中的猴子编号。

比如，n=5时，初始的数组M的内容如下表: 下标：0 1 2 3 4当2号猴子（报数轮到3）退出圈子时，1号猴子的下一只相邻猴子就是3号猴子了，实现时只需一个赋值M[1]=M[2]（即原来2号猴子的下一只相邻猴子成了1号猴子的下一只相邻猴子）。

数组M的内容变成了下表:下标：0 1 2 3 4这样做的好处有两个，一是第i号猴子的下一只相邻猴子就是M[i]，不需要用一个循环去找了；二是不用当心数组M下标的访问会越界。

（2）实现要点：1）循环控制结构。

《数据结构》课程设计题目(程序实现采用C语言)题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。

题目2：字符逆转（学时：3）从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。

题目3：工资核算（学时：3）设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。

现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。

题目4：满足条件的有序表生成（学时：3）已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。

另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。

题目5：一元多项式的减法（学时：6）设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。

另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。

题目6：床位分配（学时：6）某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。

要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。

题目7：文本文件单词的检索及计数（学时：6）要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。

课程设计报告课程设计题目：1：学生成绩管理系统2：joseph环3：猴子选大王姓名洪军学号201420180706班级1421807指导教师邹国华2015年12月17日1：学生成绩管理系统1, 问题分析；定义一个学生管理系统实现对学生基本数据的管理，录入：输入每位学生的信息；输出：输出每位学生的信息；查询：可以按3学号和4姓名查询某个学生的信息；修改：可以修改学生（按1学号修改，按2成绩修改）的信息；插入：可以插入一个学生的信息；删除：可以删除（按1学号删除，按2成绩删除）满足条件的学生信息；排序：可以按学生的总成绩排序。

2 结构分析首先分析结果我采用的是单链表的存储结构通过此系统可以实现如下功能：定义一个学生类型student（学号，姓名，四门课程成绩），学生链表student，含有学生数组和学生数。

3 实现流程分析定义数据类型typedef struct student⇩初始化结构体并输入学生的数据inputstu(stu &s,int n)⇩重载运算符便于输入输出学生的成绩⇩输出函数输出全部学生的信息output(stu s)⇩查找学生3按学号查找getstu1(stu s,char i[]) 4按姓名查找getstu2(stu s,char c[])⇩插入学生insetstu(stu &s,int i,char nu[],char na[],char se[],int sc[])⇩1按学号删除学生deletestu1(stu &s)，2按姓名删除学生deletestu2(stu &s)⇩1按学号修改学生的信息update1(stu &s) 2按姓名修改学生的信息update2(stu &s)⇩对总成绩排序sort(stu &s,struct shu shuzu[])⇩CPP文件实现所有功能4 算法实现头文件status.htypedef int status;#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define N 10typedef struct student{ //学生结构体（链表）char num[9];char name[15];char sex[2];int score[4];student *next;}student,*stu;struct shu{ //辅助结构体数组存储学生总成绩和学号便于排序float allscore;char num[9];}shuzu[10];ostream &operator<<(ostream &os,stu &s); //运算符的重载istream &operator>>(istream &is,stu &s); //运算符的重载void inputstu(stu &s,int n) //初始化并且输入函数{student *p,*r;int i;s=(stu)malloc(sizeof(student)); //申请头节点r=s;for(i=0;i<n;i++){p=(student *)malloc(sizeof(student)); //申请链表空间}status insetstu(stu &s,int i,char nu[],char na[],char se[],int sc[]) //插入学生{student *p=s,*q;int j=0,m;while(j<i-1&&p->next) //找到学生的位置{p=p->next;j++;}if(j==i-1){q=(student*)malloc(sizeof(student)); //申请新结点if(!q)return OVERFLOW; //申请失败返回错误{strcpy(q->name,na); //赋值strcpy(q->num,nu);for(m=0;m<4;m++)q->score[m]=sc[m];strcpy(q->sex,se);q->next=p->next;p->next=q;return OK;}}elsereturn ERROR;}status deletestu1(stu &s) //按学号删除学生{char i[10];cout<<"请输入你要删除学生的学号"<<endl;cin>>i;student *p=s,*r;while(strcmp(p->next->num,i)!=0) //找到修改学生{p=p->next;}if(p) //存在就删除不存在就返回错误{r=p->next;p->next=r->next;free(r);return 0;}elsereturn ERROR;}status deletestu2(stu &s) //按姓名删除学生{char i[10];cout<<"请输入你要删除学生的姓名"<<endl;cin>>i;student *p=s,*r;while(strcmp(p->next->name,i)!=0) //找到修改学生{p=p->next;}if(p){r=p->next;p->next=r->next;free(r);return 0;}elsereturn ERROR;}status update1(stu &s) //按学号修改学生的信息{char i[10];cout<<"请输入你要修改学生的学号"<<endl;cin>>i;student *p=s;while(strcmp(p->num,i)!=0) //找到修改学生{p=p->next;}if(p){cin>>p;return 0;}elsereturn ERROR;}status update2(stu &s) //按姓名修改学生的信息{char i[10];cout<<"请输入你要修改学生的姓名"<<endl;cin>>i;student *p=s;while(strcmp(p->name,i)!=0) //找到修改学生{p=p->next;}if(p){cin>>p;return 0;}elsereturn ERROR;}void sort(stu &s,struct shu shuzu[]) //对总成绩排序{int n=0,i,j,k;student *p=s->next;while(p){ //获取多少个人数n++;p=p->next;};p=s->next;for(i=1;i<=n;i++) //对结构体进行赋值{ shuzu[i].allscore=0;for(j=0;j<4;j++)shuzu[i].allscore=shuzu[i].allscore+p->score[j];strcpy(shuzu[i].num,p->num);p=p->next;}for(i=1;i<n;i++){ //对结构体进行排序k=i;for(j=i+1;j<=n;j++)if(shuzu[j].allscore>shuzu[k].allscore)k=j;if(k!=j){shuzu[0].allscore=shuzu[i].allscore;strcpy(shuzu[0].num,shuzu[i].num);shuzu[i].allscore=shuzu[k].allscore;strcpy(shuzu[i].num,shuzu[k].num);shuzu[k].allscore=shuzu[0].allscore;strcpy(shuzu[k].num,shuzu[0].num);}}for(i=1;i<=n;i++){ //对总成绩从大到小输出p=s->next;while(strcmp(p->num,shuzu[i].num)!=0) //按学号查找相对应的学生信息{p=p->next;}cout<<p<<" 总成绩为:"<<shuzu[i].allscore<<endl;}}ostream &operator<<(ostream &os,stu &s) //输出函数的重载{os<<"学号:"<<s->num<<" 姓名:"<<s->name<<" 性别:"<<s->sex<<"科目 1 "<<s->score[0]<<"科目 2 "<<s->score[1]<<"科目3 "<<s->score[2]<<"科目4 "<<s->score[3]<<endl;return os;}istream &operator>>(istream &is,stu &s) //输入函数的重载{ cout<<""<<"学号"<<"姓名"<<"性别"<<"科目1 "<<"科目2 "<<"科目3 "<<"科目4 "<<endl; is>>s->num>>s->name>>s->sex>>s->score[0]>>s->score[1]>>s->score[2]>>s->score[3];return is;}CPP文件#include<iostream.h>#include<stdio.h>#include<string.h>#include<stdlib.h>#include"Status.h"void menu(){cout<<"* * * * * * * *学生管理系统* * * * * * *"<<endl;cout<<"* * * 1：添加学生* * *"<<endl;cout<<"* * * 2：显示信息* * *"<<endl;cout<<"* * * 3：按学号查找* * *"<<endl;cout<<"* * * 4：按姓名查找* * *"<<endl;cout<<"* * * 5: 插入学生* * *"<<endl;cout<<"* * * 6: 删除学生* * *"<<endl;cout<<"* * * 7: 修改学生* * *"<<endl;cout<<"* * * 8: 学生总成绩排序* * *"<<endl;cout<<"* 其他：返回主菜单"<<endl;cout<<"请选择";}int main(){ stu s;struct shu shuzu[10];int i,k[4],j;char c[9],p[9];char x[20],o[20];char l[3];menu();while(1){static int n;scanf("%d",&n);switch(n){case 1:cout<<"输入多少个学生"<<endl;cin>>n;inputstu(s,n);break;case 2:output(s);break;case 3:cout<<"请输入你要找的学生学号:";cin>>c;getstu1(s,c);break;case 4:cout<<"请输入你要找的学生姓名:";cin>>x;getstu2(s,x);break;case 5:cout<<"需要插入位置，学号，姓名，性别,科目１，科目２，科目３，科目４"<<endl;cin>>i>>p>>o>>l;for(j=0;j<4;j++)cin>>k[j]; insetstu(s,i,p,o,l,k);break;case 6:cout<<"1:按学号删除学生的信息;2:按姓名删除学生的信息"<<endl;cin>>j;switch(j){case 1:deletestu1(s);break;case 2:deletestu2(s);break;};break;case 7:cout<<"1:按学号修改学生的信息;2:按姓名修改学生的信息"<<endl;cin>>j;switch(j){case 1:update1(s);break;case 2:update2(s);break;};break;case 8:sort(s,shuzu);break;default:return 0;}}调试结果5 课程小结我采用的是链表来存储学生的信息，最大的难点就是总成绩的排序，其他的功能实现还是比较简单，总成绩排序我用啦一个辅助结构体struct shu 来存储每个学生的学号char num来记录学生以及便于排序的时候查找，还有总成绩float allscore，且用结构体数组来存储首先对每个学生的学号及总成绩赋值给结构体数组shuzu[]，然后对结构体数组进行从大到小排序（选择排序）然后对结构体一一查找相应的信息。

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。

问怎样排法，才能使每次投入大海的都是非教徒。

*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。

这里给出一种实现方法。

题目中30个人围成一圈，因而启发我们用一个循环的链来表示。

可以使用结构数组来构成一个循环链。

结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。

从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。

这样循环计数直到有15个人被扔下海为止。

[编辑本段]约瑟夫问题的一般形式：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

C++代码示例:#include<iostream>usingnamespacestd;voidmain(){intn,m,a[101],k,i,j,num;.n-2,n-1,0,1,2,...k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k-->0k+1-->1k+2-->2......k-2-->n-2k-1-->n-1变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n 个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)modn 如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。