下载文档原格式
重庆交通大学信息科学与工程学院综合性设计性实验报告专业：课程名称：《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开始报数，依次循环，直到圈内剩下一只猴子为止，该编号的猴子就是所选出的大王。
一、猴子选大王课题描述一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
猴子选大王系统设计1、猴子选大王总体设计结构图2、系统数据的数据结构设计猴子的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的.(1)、变量说明程序中使用的存储结构:ListNode结构体Struct ListNode{Int data; //数据域Struct ListNode *nextPtr; //指向后继结点的指针域};Int monkeys,count //分别为猴子的个数和猴子的报数HeadPtr,tailPtr，currentPtr //分别为链表的头结点，尾结点和结点HeadPtr1,headPtr2 //分别为选大王的单循环链表和由淘汰的猴子所构成的链表(2)、函数说明DestroyList (LISTNODEPTR headPtr) //用destroylist函数来释放选大王链表的各个结点CreateList (int n) //创建循环链表，容纳n个猴子Printf(“input the amount of monkeys:”) //用printf函数来提示输入的内容Scanf(“%d”,&monkeys) //用scanf函数来输入猴子的个数Printf(“input the count number:”) //用printf函数来提示报数的数Scanf(“%d”,&count) //用scanf函数来输入每次数到的猴子就出局(3)、while循环说明while(currentPtr1!=currentPtr1->nextPtr){/*往后数一个猴子*/prePtr1=currentPtr1;currentPtr1=currentPtr1->nextPtr;count++;/*若数到n，则淘汰currentPtr指向的猴子*/if(count%n==0){/*从headPtr1指向链表中拆下currentPtr指向的结点*/prePtr1->nextPtr=currentPtr1->nextPtr;currentPtr1->nextPtr=NULL;/*将currentPtr1指向的结点插入到headPtr2指向链表中*/if(headPtr2==NULL){/*若headPtr2指向的为空链表*/headPtr2=currentPtr1;tailPtr2=currentPtr1;}else{ /*将拆下来的结点组装到headPtr2指向的链表上*/ tailPtr2->nextPtr=currentPtr1;tailPtr2=tailPtr2->nextPtr;}currentPtr1=prePtr1; /*currentPtr1指向上一个结点，为下一次数数做准备*/}}二、猴子选大王重点及关键技术分析程序通过循环链表较好的实现了猴子选大王的功能，但是还是有许多值得思考的地方。
#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）循环控制结构。
蓝桥杯-猴⼦选⼤王（约瑟夫问题）标题：猴⼦选⼤王⼀群猴⼦要选新猴王。
新猴王的选择⽅法是：让N只候选猴⼦围成⼀圈，从某位置起顺序编号为1~N号。
从第1号开始报数，每轮从1报到3，凡报到3的猴⼦即退出圈⼦，接着⼜从紧邻的下⼀只猴⼦开始同样的报数。
如此不断循环，最后剩下的⼀只猴⼦就选为猴王。
请问是原来第⼏号猴⼦当选猴王？输⼊格式：输⼊在⼀⾏中给⼀个正整数N（≤1000）。
输出格式：在⼀⾏中输出当选猴王的编号。
输⼊样例：11输出样例：7思路⼀：⽤数组模拟⼀个环，存储第下标+1位猴⼦是否退出(因为下标从0开始)，数组初始化为0，每次轮到数3的猴⼦就将他的下标置为-1，最后⼀个下标不为-1的猴⼦就是选中的王。
1 #include<bits/stdc++.h>2using namespace std;34const int N = 1000; //共有N个猴⼦56int a[N]; //⽤数组和%操作模拟圈78int index = 0; //下标index9int i = 1; //⽤来对3计数10int counter; //记录每次剩下的猴⼦个数1112int main()13 {14int num; //num是猴⼦的数量15 cin >> num;16 counter = num;1718while(counter > 1)19 {20if(a[index] != -1) //当下标为index的猴⼦还在圈内时21 {22if(i == 3)23 {24 a[index] = -1; //将数到3的猴⼦退出圈⼦，将下标置为-125 counter--; //剩下的猴⼦总个数-126 }2728 i++;2930if(i > 3) //i=4时候，i要回到131 {32 i = i % 3;33 }34 }3536 index++;3738if(index >= num) //当下标达到了猴⼦总数时，要回到开头39 {40 index = index % num;41 }4243 }4445for(int i = 0; i < num; i++)46 {47if(a[i] != -1)48 {49 cout << i + 1; //数组下标是从0开始的，要+150 }51 }5253return0;54 }思路2：使⽤递归思想1 #include<bits/stdc++.h>2using namespace std;34int fun(int n)5 {6if(1 == n)7 {8return0;9 }1011return (fun(n - 1) + 3) % n;12 }1314int main()15 {16int n;17 cin >> n;18 cout << fun(n) + 1;19return0;20 }。
-- Array《数据结构》课程设计报告题目猴子选大王学生姓名学号专业班级指导老师方霞设计日期 2010.03.04指导老师评阅意见：一设计目的数据结构课程设计是学习计算机程序设计的一个重要环节。
它不仅能加强和加深数据结构所学内容，提高学生实际运用实践能力，培养实际作风，为学习计算机类后续课程和今后的计算机类系统开发奠定坚实而又牢固的基础。
通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。
二设计内容2.1 任务描述1）任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
2）要求：输入数据：输入m,n,m,n 为整数，n<m3）输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。
2.2 存储结构采用了建立单循环链表和monkey结构体相结合的存储方式。
以下是monkey结构体的存储结构形式，其中包括了记录了猴子号码的int 型的number数据元素，和Link List型的指针next。
typedef struct monkey{int number;struct monkey *next;}Monkey,*LinkList;2.3 基本算法这个算法的主要流程为：首先通过设置一个monkey得结构体来建立单循环链表所需要参数number，next，利用主函数main来完成链表，编号，选择猴子王的算法来完成整个程序设计，这个过程中还不断的调用for循环来求得猴子王。
2.4 算法或程序模块在程序中以下代码是用来给猴子编号和数数选择是留下还是离开的：for(i=1;i<m;i++){p=(LinkList)malloc(sizeof(Monkey));q->next=p;q=p;}q->next=head;//建立单循环链表p=head;//p指向了链表头结点printf("对%d只猴子进行编号如下:\n",m);for(i=1;i<=m;i++){p->count=i;//依顺序对15只猴子进行编号printf("%d号猴子编号为：%d\n",p->count,p->count);p=p->next;}i=0;p=head;printf("\n");while(1){i++;printf("%d号猴子报数:%d\n",p->count,i);if(p->next==p)break;if(i==n){i=0;printf("%d号猴出局离开\n",p->count);printf("\n");q->next=p->next;p=q->next;}下面的代码是用主函数main来完成的，其中这个过程汇总，设计了一个单循环链表LinkList，使用了几个for循环来编号，数数出局离开来选择猴子王的。
猴子选大王一、设计目的1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。
学生通过上机实习，验证自己设计的算法的正确性。
学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。
4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。
二、设计内容1、系统名称：猴子选大王按照规定的要求，选出最后的一只猴子，为大王。
2、要求：一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。
三、程序设计步骤1）采用主要的数据结构类型。
采用了链表的存储方式，属于链接存储结构。
for(i=1;i<n;i++) //建立链表的存储结构{p=(LINK)malloc(sizeof(Monkey));p2->next=p;p2=p;}以下是用于存储结点的结构体的定义:typedef struct monkey{int num;struct monkey *next;} Monkey,*LINK;基本算法：这个算法的主要流程为：从控制台读取猴子的数量和报数的最大数——>对猴子进行编号，并用链表来存储——>让链表中的猴子进行报数，对于报数为m的猴子则从链表中删除——>当链表中只剩下一个报数后则停止这个过程，这最后一个猴子即选出来的大王。
以下为为猴子建立链表：for(i=1;i<n;i++) //建立链表的存储结构{p=(LINK)malloc(sizeof(Monkey));p2->next=p;p2=p;}以下为猴子进行编号：for(i=1;i<=n;i++) //对猴子进行编号{p->num=i;//printf("%d号猴子：%d\n",p->num,p->num);p=p->next;}以下为最主要的算法过程，是通过一个While循环来控制的，是让猴子报数的过程，并删除报数为m的猴子：while(1){i++;//当链表只剩最后一个元素了则跳出循环，此时报数已完成printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break;if(i==m){i=0;printf("%d号猴被淘汰\n",p->num);printf("\n");p2->next=p->next;p=p2->next;continue;}else{if(i==m-1) p2=p;p=p->next;}}2）详细设计：#include <stdio.h>#include <stdlib.h>int n=2;int m=1;typedef struct monkey{int num;struct monkey *next;} Monkey,*LINK;void main(){printf("请输入一个整数（猴子数量）：");scanf("%d",&n);printf("请输入一个小于猴子数量的整数（报数的最大数）：");scanf("%d",&m);LINK p,head,p2;int i;head=p=p2=(LINK)malloc(sizeof(Monkey));for(i=1;i<n;i++) //建立链表的存储结构{p=(LINK)malloc(sizeof(Monkey));p2->next=p;p2=p;}p2->next=head;p=head;//printf("对猴子进行编号！\n");for(i=1;i<=n;i++) //对猴子进行编号{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){i=0;printf("%d号猴被淘汰\n",p->num);printf("\n");p2->next=p->next;p=p2->next;continue;}else{if(i==m-1) p2=p;p=p->next;}}printf("胜出:%d",p->num);}四、调试分析调试的过程中，对程序做了几点改进，增加了程序的容错能力，不论用户输入什么内容，程序都能安全检查。
数据结构课程设计报告题目：猴子选大王——采用循环链表及动态存储的实现班级：计算机082班姓名：指导教师：成绩：信息工程学院2010年01 月20 日目录课程设计摘要(题目) (03)1.引言 (03)2.需求分析 (04)2.1问题分析 (04)2.2总体设计 (05)3.概要设计 (07)3.1模块分析 (07)3.1.1链表循环输入删除输出 (07)3.1.2各个函数之间的调用关系 (09)3.2函数的流程分析 (10)4.详细设计 (12)4.1函数设计 (12)4.2程序源代码 (13)5.测试结果 (16)6.设计体会 (18)7.结束语 (19)参考文献 (20)摘要(题目):猴子选大王任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m 个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：输入数据：输入m,n ；m,n 为整数（n<m）输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能1.引言随着计算机科学的迅速发展，计算机已深入到揉合社会的各个领域，它的应用已不再局限于科学计算，以解决一些数学问题，而且可以解决一些抽象化的具体问题，更多地用于控制，管理及数据处理等非数值计算的处理工作，这便为我们的日常生活提供了很多的方便，譬如说火车、飞机售票系统，学生成绩管理，商品管理系统，医院选址等实际问题。
如今程序设计的语言很多，有发展比较完善高级语言，也有最基本的低级语言，然而再好的程序设计也要有一个比较清晰的思路——算法。
为了编写好一个好程序，必须分析待处理对象的特性以及各处理对象之间的关系，于是数据结构便成为我们绝佳的选择。
数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。
计科专业数据结构A课程设计选猴王作者姓名：王显衡专业、班级：计科123学号： 12422003指导教师：赵晶完成日期： 2013年11月17日大连大学Dalian University目录题目描述 (1)1、算法思想 (2)2、详细设计 (2)4 调试分析 (4)5 用户使用说明 (5)6课程设计总结 (6)参考文献 (7)题目描述任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m 的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：输入数据：输入m,n m,n 为整数，n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能1、算法思想将表中最后一个结点的指针域指向头结点，整个链表形成一个环，构造循环链表‘*L’。
由此，从表中任意一个结点开始，都可以遍历全表。
再用一个for循环来实现从第1开始数，第数到第N个，该猴子就要离开此圈。
如果链表不空的话，用’a’指向开始结点，往后数到第N个结点，就把第N-1个结点与第N+1个结点链在一起，即实现了删除第N个结点。
如此反复，直到L的后继结点是它自己，即圈中只剩最后一只猴子，那么这只猴子就是大王。
2、详细设计1）、猴子的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的：typedef struct Mnode{ int data;struct Mnode *next;}Mnode;根据题目要求，要让这M只猴子顺序围坐一圈，那就得用循环链表，只须将单循环链表的尾指针的NEXT域指向头指针。
它的判空条件是L=L->next =NULL；（非空表）（空表）单循环链表2）、函数void hzxdw(M，N)读取数据M、N后,然后就根据N的值，用for循环数猴子结点用’a’指向开始结点，往后数到第N个结点，就把第N-1个结点与第N+1个结点链在一起，即实现了删除第N个结点。
湖南人文科技学院计算机系课程设计说明书课程名称: 数据结构课程代码:题目: 猴子选大王年级/专业/班: 06级计算机科学与技术专业一班学生姓名:学号:06408109 06408102 06408107 0640812206408103指导教师: 刘刚常开题时间: 2008 年 6 月16 日完成时间: 2008 年 6 月29 日目录摘要 (3)一、引言 (4)二、设计目的与任务 (4)三、设计方案 (5)1、总体设计 (5)2、详细设计 (8)3、程序清单 (14)4、程序调试与体会 (22)5、运行结果 (23)四、结论 (24)五、致谢 (24)六、参考文献 (25)摘要本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了C语言编写,有很少一部分函数是用C++编写的，有比较详细的中文注释并在VC++下调试运行通过。
整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。
关键词：循环队列；循环链表；存储结构AbstractThis paper details the difference of sequence list and linklist.We respectively use queue and circular queue and circular linked list to solve the seek elected king of the monkey problem . The procedure write with C language ，a very small part function is used by the C + +,and has chinese explanatory note.What’s more,it was debugged in VC++ debugger and run very well.The whole procedure,with Chinese interface and thecorresponding hints,is convenient to run and easy to be operated.Keywords : circular queue；circular linked list ；storage structure《数据结构》课程设计——猴子选大王一、引言数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。
题目：猴子选王一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。
#include <stdio.h>struct monkey{int num;monkey *next;};monkey *head,*tail;void creat(int n){int i;monkey *p,*q;p=new monkey; //为p分配内存空间p->num=1; //初始化p结点num域为1p->next=NULL; //初始化p结点next域为空head=p; //链表头指针head赋值为pq=p;for(i=2;i<=n;i=i+1) //循环存入猴子{p=new monkey; //为p配内存空间p->num=i; //初始化p结点num域为i，表示猴子号q->next=p; //将p点加到链表尾部q=p; //让指向链表尾部结点p->next=NULL; //链表尾部指向空}tail=q; //链表尾tail->next=head; //链表尾部指向链表头，形成循环链表}void select(int n){int x=0;monkey *p,*q;q=tail; //q赋值给tail，指向循环链表尾部do //直到型循环，用于循环删除指定间隔的结点{p=q->next; //p赋值给相邻的下一个结点x=x+1; //x加1if(x%n==0) //x是否整除m{printf("%d号猴子淘汰\n",p->num);q->next=p->next; //删除此结点delete p; //释放空间p=NULL;}else q=p; //q指向相邻的下一个结点p }while(q!=q->next); //剩余结点数不为1，则继续循环head=q; //head指向结点q,q为链表中剩余的一个结点}void main(){int n,m;head=NULL; //初始化head为空printf("请输入猴子的个数\n");scanf("%d",&m);printf("请输入n\n");scanf("%d",&n);creat(m); //调用函数creat建立循环链表select(n); //调用函数select，找出剩下的猴子printf("猴王是%d号\n",head->num); //输出猴王delete head; //删除循环中最后一个结点}#include<stdio.h>int main(){int a[1000];//定义一个较大的数组存储数据int m,n,x,count,i;//定义猴子数m、输入n、所需变量x、cout、iprintf("请输入猴子个数:\n");//提示输入mscanf("%d",&m);printf("请输入n:\n");//提示输入nscanf("%d",&n);for(i=1;i<=m;i++) //令数组与猴子编号对应a[i]=i;count=m;//令cout等于猴子个数x=0;//令x初始值为零for(i=0;count>1;i++)// 执行循环，淘汰的猴子值为-1，直到只剩一只猴子，即为猴王{if(a[i%m+1]!=-1) {x++;}if(x==n&&a[i%m+1]!=-1){a[i%m+1]=-1;count--;x=0;printf("%d号猴子淘汰\n",i%m+1);} }for(i=1;i<=m;i++) //输出值不为-1的猴子，即猴王if(a[i]!=-1) printf("猴王是%d号\n",i);}。
《数据结构》课程设计题目(程序实现采用C语言)题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第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中出现的元素。
另外该先判断b和c。
在从头开始找a。
for(i=0;i<10;i++)for(j=0;j<10;j++){if(b[i]=c[j]){for(k=0;k<10;k++)if(a[k]=b[i])a[k]=0;}}题目5：一元多项式的减法（学时：6）摄有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。
另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。
题目6：床位分配（学时：6）某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。
bbb://wenku.baiduaaa/view/7202b929b4daa58da0114a2d.html1要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；2分配不成功时，允许更改房间等级，3若不更改等级，印出“满客”提示。
