信息学奥赛课课通-第8单元电子课件.ppt

《信息学奥赛课课通-第8单元电子课件.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛课课通-第8单元电子课件.ppt（78页珍藏版）》请在三一办公上搜索。

1、第 8 单元 指针,作者：林厚从,信息学奥赛课课通（C+）,第 1 课 指针的概念,学习目标1.理解指针的概念。2.学会定义和使用指针。,指针,指针是 C+语言的一个重要概念，也是 C+语言的重要特色。C+语言的高度灵活性及极强的表达能力，在很大程度上表现在巧妙而灵活的运用指针。通过指针可以有效地表示复杂的数据结构；能够方便地处理数组和字符串；能够动态地分配内存，直接对内存地址进行操作；利用指针作为函数参数，能够实现“一次函数调用，有多个返回值”的目的。因此，必须深入学习和理解指针的概念，体会和掌握指针的各种操作，熟练应用指针去实践编程。,1.指针的概念,对于“int a=3;”，系统会在内存

2、的某个区域开辟连续4个字节的单元存储。对 a 的操作就是对该内存区域进行操作，至于是具体的哪4个单元，我们并不关心。内存单元的位置（编号）叫作“地址”，可以通过取地址操作符“&”获得一个变量 a 的起始地址（首个存储单元的地址）：&a。指针也是一个变量。和普通变量不同的是，指针变量里存储的数据是一个内存地址，就好像一个指示器，指引着你去该内存地址开始的一块内存区域存取数据。,2.指针的定义和使用,指针变量的定义格式为：数据类型*指针变量;可以通过赋值语句给指针变量赋值，例如“p=&a；”表示把变量 a 的内存地址赋值给 p，如图 8.1-1 所示。指针变量初始化：int*p=NULL；,例1、

3、数字变化,【问题描述】输入两个不同的整数，把较小的那个数翻倍并输出。【输入格式】一行两个整数（int 范围以内），之间用一个空格隔开。【输出格式】一行一个整数，较小数翻倍后的结果。【输入样例】2 3【输出样例】4,/p8-1-1#includeusing namespace std;int main()int a,b;int*p;cin a b;if(a b)p=,【程序说明】,1）变量 a 和 b 一旦定义，系统就会给它们分配内存空间，而且在程序运行过程中，其内存地址是固定不变的，这种存储方式称为“静态存储”。2）指针变量 p 定义后，其地址空间是不确定的，默认是 NULL。当执行到 p=&

4、a 或者 p=&b 时，p 才指向 a 或者 b 的地址，才能确定 p 的值。这种储存方式称为“动态存储”。3）指针的动态性，还体现在可以根据需要，通过函数 new（）随时申请。看以下例2：,例2、阅读程序，写出程序的运行结果。,/p8-1-2#includeusing namespace std;int main()int*p;char*q;p=new(int);q=new(char);*p=65;*q=*p;cout*p“*q endl;return 0;,【程序说明】,1）运行程序，输出结果为“65 A”。2）程序中声明了两个指针类型：一个指向整数类型的指针 p 和一个指向字符类型的指针

5、 q，分别通过 new(int)和 new(char)为 p 和 q 向内存申请空间。3）“*p=65；”把 65 这个整数存放到 p 所指向的内存单元。4）“*q=*p；”把 p 所指向的内存单元里的值赋值给 q 所指向的内存单元，由于 q 指向的是一个字符类型，而 p 指向的是一个整数类型，在赋值的时候执行了类型的强制转换，最终 q 所指向的内存单元里存储的是 65 号字符即为 A。,3.指针的理解,（1）指针的类型,从语法角度看，把指针定义语句里的指针名字去掉，剩下的部分就是这个指针的类型，也就是指针本身所具有的类型。int*ptr;/指针的类型是 int*char*ptr;/指针的类型

6、是 char*int*ptr;/指针的类型是 int*int(*ptr)3;/指针的类型是 int(*)3int*(*ptr)4;/指针的类型是 int*(*)4,（2）指针所指向的类型,当通过指针来访问指针所指向的内存区域时，指针所指向的类型决定了编译器将把那片内存区域里的内容当作什么来看待。从语法上看，把指针定义语句中的指针名字和名字左边的指针声明符“*”去掉，剩下的就是指针所指向的类型。int*ptr;/指针所指向的类型是 intchar*ptr;/指针所指向的类型是 charint*ptr;/指针所指向的类型是 int*int(*ptr)3;/指针所指向的类型是 int()3int*(

7、*ptr)4;/指针所指向的类型是 int*()4在指针的算术运算中，指针所指向的类型有很大的作用。指针的类型和指针所指向的类型是两个不同的概念。,（3）指针的值,指针的值是指针本身存储的数值，这个值将被编译器当作一个地址，而不是一般的数值。在位长 32 位的系统中，内存地址都是 32 位的，所以所有类型的指针的值都是一个 32 位整数。指针所指向的内存区域就是从指针的值所代表的那个内存地址开始，长度为sizeof（指针所指向的类型）的一片内存区域。我们说一个指针的值是 X，就相当于说该指针指向了以 X 为首地址的一片内存区域。指针所指向的内存区域和指针所指向的类型是两个完全不同的概念。,（4

8、）指针本身所占据的内存区,用函数 sizeof（指针的类型）测一下就知道了。在 32 位的系统中，指针本身占据了 4 字节的长度。,例3、阅读程序，写出程序的运行结果。,/p8-1-3#includeusing namespace std;int main()int*p,*q;p=(int*)malloc(40);/动态申请 40 字节用来存放 int 类型，并返回首地址给 p q=p;*p=1;p+;*p=2;free(q);/释放刚才申请的 40 字节的空间 return 0;,【程序说明】,（1）单步跟踪程序，发现执行完“*p=1;”，q和p为同一个地址，*p和*q的值也都是1。,（2）

9、继续跟踪程序，执行完“*p=2;”，p 指向了下一个整数空间，在原来的地址上加4，因为一个整型占4个字节。*p 的值也变成了2。,（3）程序中的“free(q);”是释放一开始申请的40个字节的内存空间，是配合malloc()使用。注意释放的是内存，q和p的地址还在，指针并没有被释放，指针仍然指向原来的存储空间。指针是一个变量，只有程序结束时才被销毁。释放了内存空间后，原来指向这块空间的指针还是存在，只不过现在指针指向的内容是未定义的，里面可能会有一些垃圾内容。继续跟踪看看p、q、*p、*q的值。,动态申请内存,（1）malloc()void*malloc(unsigned size);在内存

10、的动态存储区中分配一块长度为size字节的连续区域，参数size为需要内存空间的长度，返回该区域的首地址。（2）calloc()void*calloc(size_t numelements,size_t sizeofelement);与malloc相似，参数sizeofelement为申请地址的单位元素长度，numelements为元素个数，即在内存中申请numelements*sizeofelement字节大小的连续地址空间。（3）realloc()void*realloc(void*ptr,unsigned newsize);给一个已经分配了地址的指针重新分配空间，参数ptr为原有的空间地

11、址，newsize是重新申请的地址长度。,实践巩固,第 2 课 指针的引用与运算,学习目标1.理解并学会引用指针。2.掌握指针的常用运算。,1.指针的引用,首先理解指针变量与普通变量的区别和对应关系。例如，定义一个指针变量“int*p；”和一个普通变量“int a；”，关于两者之间的各种引用方式对应关系如下：1）“p”等同于“&a”，表示的是内存地址。2）“*p”等同于“a”，表示变量里存储的实际数据。3）“*p=3；”等同于“a=3；”，表示变量的赋值方法。,2.指针的运算,如果定义的是局部指针变量，其地址就是随机的，直接操作会引发不可预测的错误。所以，指针变量一定要初始化后才能引用。由于指

12、针变量存储的是内存地址，所以也可以执行加法、减法运算，一般用来配合数组进行寻址操作。例如：,例1、阅读并上机调试以下程序，体会指针变量的加法运算。,/p8-2-1#includeusing namespace std;int main()int a100,n;cin n;for(int i=0;i ai;int*p=,【问题分析】,1）程序的作用是输入 n 及 n 个整数，使用指针变量依次遍历输出。2）程序中的“p+”是广义的“p=p+1”，本质上是“p+sizeof(int)”。3）注意，“*p+3”和“*（p+3）”是不同的。对于本题，前者是指 a0+3，而后者是指 a3。,例2、求和,【

13、问题描述】输入 n 个正整数，要求对这 n 个数中的奇数和偶数分别求和。【输入格式】第 1 行 1 个正整数 n，1n5000。以下 n 行，每行一个正整数（120000 之间）。【输出格式】2 行 2 个整数。第 1 行为所有奇数之和，第 2 行为所有偶数之和。,【输入样例】5310758【输出样例】1518,/p8-2-2#includeusing namespace std;int main()int n,a5011;int*p,*s1,*s2;/s1 和 s2 指向的单元分别存放偶数和、奇数和 cin n;for(int i=0;i ai;p=,例3、阅读并上机调试以下程序，体会无类型

14、指针的使用。,/p8-2-3#includeusing namespace std;int main()int a=10;double b=3.5;void*p;p=,例4、阅读并上机调试以下程序，体会多重指针的使用。,/p8-2-4#include using namespace std;int main()int a=10;int*p;int*pp;p=,实践巩固,第 3 课 指针与数组,学习目标1.理解数组指针。2.学会使用指针实现数组操作。3.学会使用指针实现字符串操作。,指针与数组,在 C+中，数组名在一定意义上可以被看成指针。“数组的指针”是指整个数组在内存中的起始地址，“数组元素

15、的指针”是指数组中某个元素所占存储单元的地址。一般可以使用“下标法”访问数组元素，如 a5；也可以使用“地址法”访问数组元素，因为数组名就代表数组在内存中的起始地址，也就是 a 0 的地址，如 a+4 就表示 a 4 的地址；也可以通过“指针法”访问数组元素，通过数组的指针或者数组元素的指针访问数组元素，能使目标程序质量更高，占用内存更少，运行速度更快。,例1、阅读并上机调试以下程序，体会数组的指针和数组元素的指针。,/p8-3-1#includeusing namespace std;int main()int a=10,11,12,13,14,15;int*p=a+4;cout*a;cou

16、t“*(a+3);cout“*(+p)endl;return 0;,【问题分析】,1）运行程序，输出“10 13 15”。2）程序中直接拿数组名 a 当指针用。但是 a 始终是静态的，是不可变的，不能做“a=a+4；”运算，而指针可以做“+p”或“p=p+4；”运算。3）语句“scanf（“%d“，&n）；”其实就是指针的意思。如果是数组，就不需要加取地址符“&”。,例2、阅读并上机调试以下程序，体会动态数组的定义和使用。,/p8-3-2#includeusing namespace std;int main()int n,*a;cin n;a=new int n;/申请 n 个连续的 int

17、 类型内存空间（动态数组），并返回首地址给 a for(int i=0;i ai;for(int i=1;i n;i+)ai+=ai-1;for(int i=0;i n-1;i+)cout ai“;cout an-1 endl;return 0;,【问题分析】,1）运行程序，输入 10 及如下 10 个数“1 2 3 4 5 6 7 8 9 10”，输出“1 3 6 10 15 21 28 36 45 55”。2）因为指针可以动态申请空间。那一次申请 100 个变量空间，系统给的地址是连续的，就可以当成数组使用，这就是“动态数组”的一种。3）在信息学竞赛中遇到大批量数据的情况下，数组开小只能拿

18、部分分，开大又可能爆空间，此时就可以定义和使用动态数组。,例3、行列转换,【问题描述】对于一个 nm 的稀疏矩阵，按照行、列、值的格式读入 k 个元素（其他位置的值为 0），再输出这些数。【输入格式】第 1 行 3 个整数，表示 n、m 和 k，每两个数之间用一个空格隔开。以下 k 行，按照“行优先（从上到下、从左到右）”的方式读入 k 个非 0 元素。每行 3 个数，依次为行号、列号、元素值，每两个数之间用一个空格隔开。【输出格式】输出k个数，按照“列优先（从左到右、从上到下）”的方式输出，每两个数之间用一个空格隔开。,【输入样例】4 5 31 2 121 4 234 3 45【输出样例】1

19、2 45 23,例4、阅读并上机调试以下程序，体会使用指针实现字符串的输入输出及存储。,/p8-3-4#include#includeusing namespace std;int main()char*s;s=new char;/给 s 申请一个地址 cin s;/输入字符串以空格或者回车结束 cout s endl;cout strlen(s);return 0;,【程序说明】,运行程序，输入“hello world!”。输出：hello5使用指针实现字符串的输入、输出及存储，与普通数组类似。只是在使用前一定要给字符串变量指定一个地址。,例5、阅读并上机调试以下程序，体会使用指针实现字符串

20、的复制。,/p8-3-5#includeusing namespace std;void copy_string(char*from,char*to)/用字符指针作为函数参数 while(*from!=0)*to=*from;*to+;*from+;*to=0;/在结束位置强制加结束符int main()char a20=“c language”;char b20=“very good”;copy_string(a,b);cout a endl;cout b endl;return 0;,实践巩固,第 4 课 函数指针及扩展,学习目标1.理解并学会使用函数指针。2.了解函数指针数组。3.了解引

21、用与指针的区别。4.了解指向结构体的指针。,函数指针及扩展,程序中需要处理的数据都保存在内存空间，而程序以及函数同样也保存在内存空间，C+支持通过函数的入口地址（指针）访问函数。另一方面，有些函数在编写时要调用其他的辅助函数，但是尚未确定，在具体执行时，再为其传递辅助函数的地址。比如排序函数 sort（a，a+n，cmp），其中的比较函数 cmp 是根据需要传递给 sort 的，就是传递了一个函数指针。函数指针就是指向函数的指针变量，定义格式如下：类型名（*函数名）（参数）;,例1、阅读并上机调试以下程序，体会函数指针的使用。,/p8-4-1a#includeusing namespace s

22、td;int test(int a)return a*a;int main()cout test endl;/或者,使用函数指针需要注意的几点：,1）定义函数指针要与函数原型一致。例如，函数为“int test(int)；”，则函数指针声明为“int(*fp)(int)；”。2）获取函数的地址有两种方式：一种是直接使用函数名，如 test 或者 fp=test；另一种是使用取地址符，如&test 或者 fp=&test。3）调用函数有两种方式：一种是直接使用函数名，如 fp(5)；另一种是使用函数指针调用函数，如(*fp)(5)。4）函数指针还支持一种结合 typedef 的定义方式。参见下一

23、页例1的另一个程序：5）可以定义一个数组存放多个函数指针。参见例2：,/p8-4-1b#includeusing namespace std;int add(int a,int b)return a+b;typedef int(*addp)(int,int);/声明一个函数指针变量 addpint main()addp fp=add;/定义 addp 类型的函数指针 fp,并赋值为 add cout fp(2,3)endl;/程序输出 5 return 0;,例2、模拟计算器,【问题描述】输入两个正整数 m 和 n，再输入一个代表运算方案的数字 k：1 代表求 m+n 的值；2 代表求m-n

24、的值；3 代表求 mn 的值；4 代表求 m/n 的值（整除）。请函数指针数组编程模拟计算器，输出相应的运算结果。【输入格式】第 1 行为 2 个正整数 m 和 n；第 2 行为 1 个正整数 k，1k4。【输出格式】一行一个整数，表示相应的运算结果。【输入样例】6 81【输出样例】14,/p8-4-2#include#includeusing namespace std;int cal1(int a,int b)return a+b;int cal2(int a,int b)return a-b;int cal3(int a,int b)return a*b;int cal4(int a,i

25、nt b)return a/b;typedef int(*f)(int a,int b);/自定义一个函数指针变量类型 fint main()freopen(“cal.in”,”r”,stdin);freopen(“cal.out”,”w”,stdout);int m,n,k;f a4=cal1,cal2,cal3,cal4;/定义函数指针数组 a,4 个元素,每个元素为 f 类型,并且分别赋初值 cin m n k;cout ak-1(m,n)endl;/用 ak-1()来调用相应的函数 return 0;,例3、阅读并上机调试以下程序，体会引用变量的使用。,/p8-4-3#includeu

26、sing namespace std;int main()int a=10,b=20;int*f;int,【问题分析】,1）运行程序，输出：a=10a=152）“引用变量”是 C+中的一种复合类型，它的本质就是给原变量起了一个别名，就像生活中有个人叫“张三”，大家给他取了一个别名叫“乐乐”，那么这两个名字指的是同一个人。引用就相当于给原变量取了一个别名，对引用变量的操作就是对原变量的操作。3）注意区分引用变量与指针变量，引用也不是取地址。另外，引用在定义的同时必须进行初始化，不能通过赋值语句，把对一个变量的引用改成对另一个变量的引用。4）程序中的 a、*f 和 ra 都是指向同一个内存地址。,

27、5）使用引用会使程序代码更加简洁，一般用在多重数组中。例如递推式“faij=(faij-1+faij-2)*aij”，可以先定义引用变量“int&k=aij”，然后简化写成“fk=(fk-1+fk-2)*k”。6）函数参数一般都是使用普通变量实现“传值”方式，也可以使用指针参数实现“传址”方式，比如数组。有了引用，就可以使用“引用参数”，使得函数中的变量名成为调用函数中的变量的别名。这种传递参数的方式叫“按引用传递”。,例4、阅读并上机调试以下程序，体会引用参数。,/p8-4-4,交换两个变量的值#includeusing namespace std;void change1(int,void

28、 change3(int m,int n)/普通变量参数 int t=m;m=n;n=t;return;int main()int x=7,y=160;change1(x,y);cout x“y endl;change2(,例5、阅读并上机调试以下程序，体会指向结构体变量的指针。,/p8-4-5#include using namespace std;struct tstudent int num;char name20;char sex;int age;tstudent x=13,”lihao”,m,35;tstudent*p;int main()p=,【程序说明】,1）运行程序，输出：13

29、Lihao352）一个指向结构体变量的指针就是该变量占据的内存空间的起始地址，如图 8.4-1 所示（下一页）。3）访问结构体成员的方法为：结构体名.成员名。使用指针访问结构体成员有两种方式：结构体名-成员名，或者（*指针变量名）.成员名。例如p-name，或者（*p）.name，但不能写成*p.name。4）如果函数的参数是一个结构体变量（按值传递），那么函数调用时就要复制整个结构体，效率不高。这种情况下，一般使用指针参数或者引用参数。,实践巩固,第 5 课 指针应用举例,学习目标学会使用指针建立链表，并熟练应用链表结构解决一些实际问题。,线性表是一种常用的数据结构，其中的每一个元素（结点）

30、都有唯一的前驱和唯一的后续。当然，第一个元素只有后续，最后一个元素只有前驱。线性表一般分为“顺序表”和“链表”。顺序表可以简单理解成前面学过的数组。它是一种逻辑上和物理上都是有序的、连续存储的静态结构。链表是一种物理上不连续存储的动态结构，数据之间的逻辑顺序是通过链表中的指针链接关系实现的。,线性表,链表,链表由一系列“结点”组成，结点可以在需要时动态生成。每个结点的数据域至少包括两部分：一是存储数据元素的“数据域”；二是存储下一个结点内存地址的“指针域”。图 8.5-1 就是一个链表的示意图，其中，head 表示头结点，数据域的值为 5 的结点为尾结点，其指针域为NULL。,链表中每个结点的

31、数据结构定义如下：struct node int num;node*next;,（1）链表的建立,建立链表有“头插法”和“尾插法”两种方法，前者是把新结点插在头结点之后，后者是把新结点插在尾结点之后。本课以尾插法为例建立链表，就是不断地在链表尾部链接一个新结点。如图 8.5-2 所示，r 为链表的尾部结点，p 为要增加的新结点，只需要把 r-next 指向 p 即可，然后把 r 再指向新的尾部。,（1）链表的建立尾插法,（2）链表的遍历,链表的遍历就是从链表的头结点 head 开始，依次访问每一个元素，直到链表尾部，包括查找、输出等操作。如果已经创建了一个链表，如何查找其中是否有给定的元素 x

32、 呢？只需要从头结点开始扫描，如果当前结点数据域的值等于 x，那么就表示找到了 x，如果到达链表尾部还没有找到，则链表中没有 x 这个元素。同样，链表的输出也是从头结点开始一个一个输出，直到链表尾部结束。,（3）链表的插入,链表的插入就是在链表给定位置插入一个新结点。如图 8.5-3 所示，就是在链表数据域值为 4 和 9 的两个结点中间插入一个数据域值为 7 的结点。如果在表头表尾插入结点要特殊处理。,（4）链表的删除,链表的删除就是删除链表中的某一个元素，如图 8.5-4 所示，就是要删除链表中数据域值为7 的结点。如果删除头结点要特殊处理。,例1、陶陶摘苹果,【问题描述】陶陶家的院子里有

33、一棵苹果树，秋天树上会结 10 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 30 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知 10 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。【输入格式】第 1 行包含 10 个 100200 之间（包括 100 和 200）的正整数（以厘米为单位）分别表示 10个苹果到地面的高度，两个相邻的正整数之间用一个空格隔开。第 2 行只包括一个 100120 之间（包含 100 和 120）的正整数（以厘米为单位），表示陶陶把手伸直的时

34、候能够达到的最大高度。,【输出格式】一行一个整数，表示陶陶能够摘到的苹果的数目。【输入样例】100 200 150 140 129 134 167 198 200 111110【输出样例】5,【问题分析】定义一个一维数组记录 10 个苹果的高度，如果陶陶手伸直能够到的高度加上 30 大于或等于苹果的高度，那么这个苹果就会掉下来，则能摘到的苹果数就加一。可以用动态存储实现本题。,/p8-5-1#include#includeusing namespace std;int a11;int main()freopen(“apple.in”,”r”,stdin);freopen(“apple.out”

35、,”w”,stdout);int*p;int s=0;p=a;for(int i=0;i*p;p+;p=new(int);cin*p;for(int i=0;i 10;i+)if(ai=*p+30)s+;cout s endl;return 0;,建议跟踪程序，体会过程。,例2、插入排序,【问题描述】给出一个整数 x 和一个数列，这个数列保证从小到大排列。现在要求将这个整数 x 插入到数列中，使新的数列仍然从小到大排列。【输入格式】第 1 行 1 个整数 n，表示数列中数的个数。第 2 行 n 个整数，之间用一个空格隔开，保证从小到大。第 3 行 1 个整数 x，表示等待插入的整数。【输出格式

36、】一行整数，表示新的数列。每两个数之间用一个空格隔开。【输入样例】41 3 4 52【输出样例】1 2 3 4 5,【问题分析】由于题目中并没有明确 n 的范围，所以定义一个动态链表。从头结点开始扫描链表，找到第一个大于或等于要插入数字的位置，就把要插入的数字插在这个位置的前面。如果没有找到比插入数大或者与其相等的，则插在链表的尾部。具体程序和说明参见教材311页-312页。,例3、夏令营旗手,【问题描述】一年一度的省“信息与未来”小学生夏令营活动又开始了。同往年一样，组织者又设计安排了许多有趣的活动，其中第一项依然是挑选本次夏令营的旗手。由于这是一个非常具有荣誉感的角色，所以报名参加夏令营旗

37、手角逐的营员仍然非常多，营委会于是规定：将 N 个人排成一排，编号 1N。从第 1 人开始进行 1M 正向报数，报到 M 的人出列，再从下一个人开始继续1M 报数、出列。（注意：按某个方向报数报到尾部时，再反方向继续报数）。如此进行下去，直到剩下一人为止，这个人就是本次夏令营的旗手。小明非常渴望能成为旗手，请编一个程序帮助他实现愿望，并输出小明的编号。,【输入格式】一行两个正整数 N 和 M，2N，M300，MN，两个数之间用一个空格分隔。【输出格式】一行一个正整数，表示小明在队列中的编号。【输入样例 1】9 3【输出样例 1】8【输入样例 2】8 3【输出样例 3】8,【问题分析】,双向链表

38、是单链表的改进。当对单链表进行操作时，有时要对某个结点的“前驱结点”进行操作，则必须从表头开始重新查找。在双向链表中，每个结点除了数据域外，还有两个指针域。一个存储后继结点地址，一般称之为后继指针域；一个存储前驱结点地址，一般称之为前驱指针域。,双向链表是单链表的改进，它的遍历、删除、插入等操作都类似于单链表，只是在操作时需要考虑每个结点还要维护一个前驱指针域。,具体程序和说明参见教材315页-316页。,例4、猴子选大王,【问题描述】有 n 只猴子围成一圈，编号为 1n，打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一只猴子开始循环报数，数到 k 的猴子出圈，然后从下一只猴子继续

39、报数出圈最后剩下来的那只猴子就是大王。【输入格式】一行两个正整数 n 和 k，之间用一个空格分开，2n1000，2k109。【输出格式】一行 n 个正整数，表示 n 只猴子依次出圈的编号，中间用一个空格隔开。【输入样例】6 4【输出样例】4 2 1 3 6 5,【问题分析】定义一个“循环链表”把猴子围成一圈。然后从当前猴子开始报数，不断扫描这个链表，数到 k 的猴子就出圈，输出这只猴子的编号，然后链表中就删除这只猴子直到剩下最后一只猴子，最后单独输出这只猴子的编号。循环链表与单链表一样，是一种链式存储结构。所不同的是，循环链表的最后一个结点的指针是指向头结点（而不是 NULL），从而构成一个环形的链。,具体程序参见教材317页-318页。由于指针的操作比较复杂，一般利用数组来模拟循环链表。具体程序参见教材318页-319页。,实践巩固,