数据结构上机实验程序--猴子选大王

课程设计说明书
2.1.4 2.1.4．创建单向基本链表基本算法
创建循环单链表函数 采用头插法创建单向循环链表 Status CreateList(elemtype m) { List head, p; head = (List)malloc(sizeof(struct Node)); //*为头指针申请两个空间*// head->next = head; //*一共有 m 个猴子，所以建立含有 m 个结点的单向循环链表*// for (i = 1; i < m; ++i) { p = (List)malloc(sizeof(struct Node)); / /*为结点申请两个空间*// p->next = head->next; head->next = p; }//*利用 for 循环实现链表的创建*// p = head; //*将指针 p 指向表头*//
No.8
沈阳大学
课程设计说明书
2.1.6 2.1.6 主函数方案设计
No.9
在主函数中首先设计程序的登陆界面信息，用户可以根据界面的提示，完成猴子选大 王的基本操作过程，为了使操作更加人性化，使输入猴子的数目 m 和决定要淘汰的猴子 编号 n，通过键盘输入，若输入错误是（m<n）,界面将用英文提示输入错误请重新输入， ，若输入正确，程序将显示运行后的结果,显示最后猴子大王的编号，并显示被淘汰猴子 的编号，程序运行完毕。 在主函数中，在用户输入结束后，分别调用创建链表函数 CreateList(elemtype m)和猴 子选大王参数 LinkedList(elemtype num_monkey, elemtype number)，经过一些列的运 算，最后得出猴子大王的编号，及其被淘汰的猴子的编号，以上即为函数的基本功能的 实现过程。

第五章数组和广义表一、选择题1. 常对数组进行的两种基本操作是（）（A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引参考答案：C2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( ) 的起始地址相同。

（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]参考答案：B3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。

（A）80（B）100（C）240（D）270参考答案：C4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（）。

（A）SA+141（B）SA+144（C）SA+222（D）SA+225参考答案：C5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。

（A）SA+141（B）SA+180（C）SA+222（D）SA+225参考答案：B6.稀疏矩阵一般的压缩存储方法有两种,即（）。

（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表参考答案：C7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（）。

（A）正确（B）错误参考答案：B8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（）。

（A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1 (D)i(i+1)/2+j参考答案：B二、填空题1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是_____________________。

实验一单链表的基本操作（必做）一、实验目的1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。

2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。

3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。

二、实验内容1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。

2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。

三、实验步骤1.定义一个链表结构体。

2.利用插入功能插入一个结点。

3.利用删除功能删除一个结点。

四、程序运行测试1.利用插入功能插入一个结点。

2.利用删除功能删除一个结点。

五、实验报告要求1.绘制链表操作实现的流程图。

2.详细给出程序运行测试结果（包括测试数据和测试结果）。

3.选试验步骤2-3中的任意一个，给出程序的详细注释。

4.参考程序中某一部分功能的改进（选做）5.实验心得与体会6.附录，实验用源程序六、参考源代码#include <iostream.h>#include <malloc.h>typedef struct LNode{int data;struct LNode *next;}Lnode, *LinkList;//假设下面的单链表均为带头结点。

void CreatLinkList(LinkList &L,int j){//建立一个单链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;L=(LinkList )malloc(sizeof(Lnode));L->next=NULL;q=L;cout<<"在单链表内输入整数："<<endl;for(int i=0;i<j;i++) p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data;p->next=q->next;q->next=p;q=p; }int PrintLinkList(LinkList &L){//输出单链表L的数据元素LinkList p;p=L->next;if(L->next==NULL){cout<<"链表没有元素!"<<endl;return 0;}cout<<"单链表的数据元素为:";while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;return 1;}void LinkListLengh(LinkList &L){//计算单链表L的数据元素个数。

}
cout<<endl;
return 0;
}
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ
，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，
这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
int main()
{
int i,j,nx[10000] = {0},n[10000] = {0},m[10000] = {1},counter[2] = {0};//数组要足够大才能不停止运行
{ j = j % nx[i]; //求余实现循环从0-n移动或用if判断实现循环
if(n[j] == 0)
{ counter[0]++; //计数器记录具有某一特点的数的次数
if(counter[0] % m[i] == 0)n[j] = 1,counter[1]+& = 0;j < nx[i];j++)
if(!n[j])cout<<j + 1<<endl;
for(j = 0;j < 10000;j++)n[j] = 0;for(j = 0;j < 2;j++)counter[j] = 0; //初始化需要重新使用的变量
for(i = 1;m[i - 1] != 0;i++) //利用m[]只有最后的值为0判定，不使用m[0]并赋值为1，其余默认为0
cin>>nx[i]>>m[i];
for(i = 1;m[i] != 0;i++)

*****数据结构课程设计题目: 赫夫曼树的建立运动会分数统计订票系统猴子选大王图的建立与输出姓名：***学号 ****专业：计算机科学与技术指导教师：****2006年9月20日目录一：绪言 (3)1.1课题设计背景 (3)1.2课题研究的目的和意义…………………………….3.1.3课题研究的内容 (4)二：主菜单设计 (4)2.1主菜单 (4)2.2主菜单源代码 (4)2.3主菜单流程图 (5)三：具体程序设计 (6)3.1赫夫曼树的建立 (6)3.2运动会设计 (8)3.3订票系统 (12)3.4猴子选大王 (15)3.5图的建立及输出 (16)四：总结与展望 (19)五：参考文献 (19).1.绪言1．1 课题背景《数据结构》作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。

从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。

从70年代中期到80年代初，各种版本的数据结构著作就相继出现。

目前在我国，《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。

《数据结构》在计算机科学中是一门综合性的专业基础课。

数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。

在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。

因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。

〈数据结构〉上机实验指导数据结构是计算机科学中的一门重要课程，它研究的是数据的组织、存储和管理方式，以及对数据进行操作和处理的算法。

上机实验是数据结构课程的重要组成部分，通过实践操作，能够更好地理解和掌握数据结构的基本概念、算法和应用。

在进行〈数据结构〉上机实验之前，首先需要准备实验环境。

通常情况下，我们会使用一种编程语言来实现数据结构的相关操作，比如C++、Java等。

根据自己的实际情况和实验要求，选择一种合适的编程语言，并确保在实验环境中已经正确安装了相应的编译器或解释器。

接下来，我们可以开始进行具体的上机实验了。

下面以链表为例，介绍一下〈数据结构〉上机实验的指导步骤和要求：1. 实验目的：掌握链表的基本概念、操作和应用，理解链表与数组的区别和联系。

2. 实验原理：链表是一种动态数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。

链表的特点是插入和删除操作的时间复杂度为O(1)，但是查找操作的时间复杂度为O(n)。

3. 实验步骤：3.1 创建链表：首先，我们需要定义一个链表的结构体，包含数据和指针两个成员变量。

然后，通过动态内存分配来创建链表的节点，并将节点之间通过指针连接起来，形成一个完整的链表。

3.2 插入节点：可以在链表的任意位置插入一个新的节点。

插入节点的操作包括：创建一个新的节点，将新节点的指针指向插入位置的下一个节点，将插入位置的前一个节点的指针指向新节点。

3.3 删除节点：可以删除链表中的任意一个节点。

删除节点的操作包括：将要删除的节点的前一个节点的指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存空间。

3.4 遍历链表：可以通过遍历链表来访问链表中的每一个节点，并对节点进行相应的操作。

遍历链表的操作包括：从链表的头节点开始，依次访问每个节点，直到链表的尾节点。

3.5 查找节点：可以根据节点的值来查找链表中的某一个节点。

查找节点的操作包括：从链表的头节点开始，依次比较每个节点的值，直到找到目标节点或者链表结束。

int n, m, count=0, i;
do//输入总个数
{
printf("请输入总个数（1－%d）：",MAXN);
scanf("%d",&m);
}while((m<1)||(m>MAXN));
do//输入出圈时要数到的个数
{
printf("要数到的个数(1--%d)：",m);
scanf("%d",&n);
}
for(i=m-1;i>=0;i--)
printf("%4d",a[i]);
printf("\n");
}
}
3.#include<stdio.h>
#include<stdlib.h>
#define MAXN 100 /*定义猴子总数*/
void main()
{
int i,j,*a,m,n,s1,w;
do//输入总个数
printf("\n");
}
}
4.#include<stdio.h>
#include<stdlib.h>
#define MAXN 100 //最大个数
struct Node
{
int data;
struct Node *next;
};
void main()
{
struct Node *head, *s, *q, *t;
for(j=s1;j<i;j++) //原来第i+1个至倒数第i个元素依次向前移动一个位置。

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）循环控制结构。

上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力表。

3、输出功能：void print(LinkList *head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。

知道不满足循环语句，程序再次回到菜单选择功能界面。

4、删除功能：LinkList *Delete(LinkList *head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。

5、插入功能：LinkList *Insert(LinkList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。

链表长度加一，重新存储。

(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList *head)函数，输出学生的记录。

(6) 程序测试主菜单：成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。

return OK;
}
int InsertSort(Form &F)
{//对顺序表F作直接插入排序
int i,j;
int comp=0;//比较次数
int move=0;//移动次数
for(i=2;i<=F.length;i++)
{
comp++;
if(F.r[i].key<F.r[i-1].key)
{
high--;
move++;
}
F.r[low]=F.r[high];
if(low<high&&F.r[low].key<=p)
{
low++;
move++;
}
F.r[high]=F.r[low];
}
F.r[low]=F.r[0];
return low;
}
void main()
{
Form F;
Init_Form(F);
{
F.r[0]=F.r[i]; //F.r[0]是监视哨
F.r[i]=F.r[i-1];
j=i-2;
comp++;
if(F.r[0].key<F.r[j].key)
{//进行元素移动，以腾出位置插入F.r[i]
F.r[j+1]=F.r[j];// 记录后移
j--;
move++;
}
F.r[j+1]=F.r[0]; //在j+1处插入F.r[i]
2.实现快速排序算法。
3.实现折半插入排序。
4.采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。

双向链表基本操作的实现
单链表的特点是任何操作都必须从表头 开始。假如要把一个链表从尾到头输出， 那效率就太低了，建立双向链表可以解决 这一问题。
循环链表基本操作的实现
利用指针实现表时，表中最后一个元素所在单元的指针 域(next)为空指针nil。如果将这个空指针改为指向表头单 元的指针就使整个链表形成一个环。．这种首尾相接的链 表称为循环链表。在循环链表中，从任意一个单元出发可 以找到表中其他单元。 (1)单向循环链表 在单链表中，将最后一个结点的指针指向头结点 (2)双向循环链表 在单向循环链表中，虽然从任一单元出发，可以找到其 前驱单元，但需要O(n)时间。如果将双链表中最后一个结 点的指针指向头结点，且头结点的前趋指向最后一个结点， 这样就构成了双向循环链表
ቤተ መጻሕፍቲ ባይዱ
线性表基本操作的实现
单链表基本操作的实现 (5)判断链表是否为空(emplkst(head)) function emplkst(head：link)：boolean； begin if head^．Next=nil then emplkst：=true else emplkst：=false end； (6)查找 ①按序号查找。 ②按值查找。 read(ch)； P：=head； while(p<>nil)and(p^．data<>ch)do P：=P^．next； if p<>nil then write(’ok’) else write(‘sorry‘)；
线性表的存储结构
链接存储结构：用指针类型来描述 单链表： Type datatype={ datatype={单链表中结点的数据类型} } link=^node; node=record data:dataty; next:link end;

一、猴子选大王：（1）M只猴子要选大王，选举办法如下：所有猴子按1-M编号围坐一圈，从1号开始按顺序1，2，，，K报数，凡报到K的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和K由输入文件提供，要求在输出文件中打印出最后剩下的猴子的编号。

数据规模（M<=1000,K<=10）【输入文件】输入文件monkey.in 的第1 行，为两个正整数，用一个空格隔开:M K【输出文件】输出文件monkey.out 只有一个正整数,输出最后一个猴子的编号【输入样例】7 3【输出样例】4这就是顶顶有名的约瑟夫问题。

这是一个据说是由古罗马著名史学家Josephus提出的问题演变而来的。

称之为约瑟夫问题。

很多资料上对这一问题解释得过于繁杂，实现起来不好理解。

在这里介绍一下本人的一些想法以供大家参考。

这个题目其实就是一种编程的经验问题。

我们可以假设猴子就位的状态用1表示，把猴子离开的状态用0表示。

那么我们就可以用一个a[M]的数组来存放M个猴子是否就位的状态。

我们可以一边报数一边遍历该数组，每遇到第K个1时，就把当前位置的1变为0，表示当前位置的猴子已经出局了。

一直循环遍历到我们的状态数组只有一个1的时候，这个存放1的数组下标再加上1（因为数组下标是由0开始的，所以要加1）即为选出的大王的编号。

想法很简单，现在关键的问题是如何解决当报数到第M个猴子的时候如何使得下一个报数重新回到第1个猴子处，也就是如何使用一维数组来解决环型问题的求解技巧。

大家想一下当我们的猴子围成圈坐的时候，问题其实由简单的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列。

假设p为当前数组某一元素的下标，对于一维数组来说，我们只要p++就可以移动到下一个元素的位置上。

那么当p=M时，如果我们直接使用p++的话，p的值就超出了a[M]数组的最大长度，我们想要的是p++之后等于0。

那么如何实现呢？解决环型数组循环遍历元素的方法：对于环型数组移动下标时，我们如果每次在p++之后再加上p=p%M的话就能解决先前遇到的越界的问题。

一维、二维数组及应用程序设计习题1、 【字符统计问题】题目描述：试统计用户键盘输入的一串英文字符中每种英文字符个数。

题目要求：⑴相同英文字符的大小写形式视为同一种统计对象；⑵遇到任意非英文字符时统计终止；⑶输出数据时每行仅输出10个数据。

输入数据：abcdeABCDElKlhmn2输出数据：A(2) B(2) C(2) D(2) E(2) F(0) G(0) H(1) I(0) J(0)K(1) L(0) M(1) N(1) O(0) P(0) Q(0) R(0) S(0) T(0) U(0) V(0) W(0) X(0) Y(0) Z(0)2、 【约瑟夫(猴子选大王)问题】题目描述：有M(1000以内)个猴子围成一圈，每个有一个编号，编号从1到M 。

打算从中选出一个大王。

经过协商，决定选大王的规则如下：从第一个开始，每隔N(任意正整数)个，数到的猴子出圈，最后剩下来的就是大王。

题目要求：从键盘输入M 、N(均为正整数)，试编程计算哪一个编号的猴子将成为大王。

输入数据：15 3 输出数据：5 200 55 93 3、 【行列互换问题】题目描述：试编程将一个二维数组行和列元素互换，存到另一个二维数组中。

例如：A =B = 4、 【矩阵初始化问题】题目描述：矩阵是线性代数中的重要概念及研究工具，在计算机算法设计中，我们常常选用二维数组之类的数据结构来描述矩阵。

下图是两个4×4的下三角方阵(即行列相等)初始化后的状态，请编程输出任意方阵(用户从键盘输入方阵的行列值)的这类初始化状态。

A 4×4 =B 4×4 =5、 【杨辉三角问题】题目描述：杨辉三角(出自其1261年所著的《详解九章算法》，也叫贾宪三角或帕斯卡三角)，它可以简单解释为由两个未知数和的幂次方运算后按某个未知数的降幂排列(或另一未知数的升幂排列)后的系数表(二项式定理)。

比如(x+y)0=1，系数为(1)；(x+y)1=x+y ，系数为(1、1)；(x+y)2=x 2+2xy+y 2，系数为(1、2、1)；(x+y)3=x 3+3x 2y+3xy 2+y 3，系数为(1、3、3、1)以及四次、五次、……等运算后所得的系数表，如下图(仅举5行)：题目要求：⑴利用一维数组试求用户给定行数的杨辉三角形；⑵利用二维数组试求用户给定行数的杨辉三角形(请尽力严格按照上图要求的输出格式)。

数据结构课程设计----个人设计报告专业：班级：姓名：学号：指导教师：日期： 2016年X月XX日至XX日目录1 课程设计目的 (3)2 课程设计内容和要求 (3)3 任务完成情况 (3)4 设计报告 (4)4.1顺序表应用 (4)4.1.1 设计目的 (4)4.1.2 设计内容及要求 (4)4.1.3 需求分析 (5)4.1.4 概要设计 (7)4.1.5 详细代码 (8)4.1.6 使用说明 (8)4.1.7 测试结果与分析 (8)4.1.8 参考文献 (10)4.2链表应用 (10)4.2.1 设计目的 (10)4.2.2 设计内容及要求 (11)4.2.3 需求分析 (12)4.2.4 概要设计 (14)4.2.5 详细代码 (16)4.2.6 使用说明 (16)4.2.7 测试结果与分析 (16)4.2.8 参考文献 (18)4.3树和二叉树 (19)4.3.1 设计目的 (19)4.3.2 设计内容及要求 (19)4.3.3 需求分析 (19)4.3.4 概要设计 (20)4.3.5 详细代码 (21)4.3.6 使用说明 (21)4.3.7 测试结果与分析 (22)4.3.8 参考文献 (22)5 体会与感想 (23)附录： (24)设计一（顺序表应用）的代码 (24)设计二（链表的应用）的代码 (35)设计三（二叉树应用）的代码 (47)1 课程设计目的1、学习获取知识的方法；2、提高发现问题、分析问题和解决实际问题的能力；3、加强创新意识和创新精神；4、加强团队的分工与合作；5、掌握面向实际背景思考问题的方法。

2 课程设计内容和要求内容：（仅供参考，请根据实际完成情况填写）第一章前言第二章顺序表与链表的应用第三章树结构的应用第四章图结构的应用第五章赫夫曼编码的应用要求：完成第2章、第3章中每章的比作必做任务。

在完成个人任务的基础上，完成第4章第5章的小组任务。

每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。

湖南人文科技学院计算机系课程设计说明书课程名称: 数据结构课程代码:题目: 猴子选大王年级/专业/班: 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);}。

第一章算法复习思考题设n为正整数，给出下列各种算法关于n的时间复杂度和空间复杂度①void fun1(int n){ j=1 ; k=100 ;while(j<n){ k=k+1 ; j=j+2 ; }}②void fun2(int b[n] , n){ for i=0 to n-1{ k=i ;for j=i+1 to n-1if(b[k]>b[j]) k=j ;x=b[i] ;b[i]=b[k] ;b[k]=x ;}}③void fun3(int n){ j=0 ; s=0 ;while(s<n){ j=j+1 ;s=s+j ;}}④ void fun4(int b[n] , n){ for i=0 to n-1if(b[i]>n) a[n]=b[i]-n ;for i=0 to n-1b[i]=a[i] ;}第二章基本数据结构及运算复习思考题教材 P152~154 2.2、2.4、2.5、2.7、2.8、2.9、2.10、2.11、2.12、2.14、2.15、2.16、2.18、2.19、2.20、2.21、2.22、2.25第三章查找与排序技术复习思考题教材 P232~233 3.1、3.2、3.4、3.9、3.11补充习题：采用本书的算法描述语言，编写链式存储结构下的简单选择排序算法。

第四章数据库技术复习思考题教材 P323~324 5.2、5.4、5.6、5.7、5.11（加“并转换为关系模式”）、5.12 补充习题：用SQL语句命令在D盘“学生成绩”目录下，建立一个叫“学生”的数据库，其数据库结构如5.7表5.36所示，并用SQL语句实现5.7的操作。

实习一、线性表（顺序存储）及其应用（分四个实验）实习目的：掌握顺序表的建立及基本操作。

问题：建立一个顺序表，表中元素为学生，每个学生信息包含姓名和学号两部分，对该表实现：①输出、②插入、③删除、④查找功能。

实习二、栈的应用（选做）实习目的：掌握栈的特点及其基本运算，用栈解决一个应用问题。