资源描述
C程序设计快速进阶大学教程,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,15,章 数组进阶,C程序设计快速进阶大学教程,第,15,章 数组进阶,本章要点,数据模型,查找与排序,9/15/2024,2,C程序设计快速进阶大学教程,15,数组进阶,知识点,数据模型,查找与排序,9/15/2024,3,C程序设计快速进阶大学教程,15.1,数据模型,数据（,data,）：描述事物的符号记录。,模型（,Model),：现实世界的抽象。现实世界的事务以及关联关系可以抽象成为一个具体的模型，模型通过某种数据结构映射到计算机世界中，进而，计算机通过软件处理数据来达到模拟、管理现实世界事务的目的。,数组：管理大量数据的一个有效载体，通过数组可以管理学生的花名册、模拟一个棋盘等等。,9/15/2024,4,C程序设计快速进阶大学教程,15.1,数据模型,问题,1:,贪吃蛇,游戏简介：,玩家通过方向键（或指定时间内未按键按原方向）控制“蛇”四向移动，目的是吃掉画面中的小点（米），每吃掉一个小点（米），“蛇”的尾巴会相应地“长”上一截，吃得越多，尾巴也就拖得越长。游戏中，“蛇”头碰上四周的边框（墙），或者碰上了自己的身体都算失败。,9/15/2024,5,C程序设计快速进阶大学教程,15.1,数据模型,简单游戏模型,9/15/2024,6,C程序设计快速进阶大学教程,15.1,数据模型,贪吃蛇算法,给出描述棋盘以及蛇的数据模型。,2.,把数据模型数据用视图表达出来。,3.,获取玩家按键或者超时的控制信息。,4.,利用控制信息修改数据模型变为新的数据模型，若新的数据模型为正确模型这返回第,2,步，否则，结束游戏。,9/15/2024,7,C程序设计快速进阶大学教程,15.1,数据模型,1.,模型设计,（,1,）贪吃蛇的棋盘，约定为一个,2020,的小方格棋盘，再加上四周的墙壁，可以用一个,2222,的二维字符数组描述：第,0,行和第,21,行每个数组元素中存放一个,-,字符（上下墙壁），第,0,列（除去,0,行和,21,行）和第,21,列（除去,0,行和,21,行）每个数组元素中存放一个,|,字符（左右墙壁），其余所有元素存放一个空格字符。这样当把该二维数组按照二维方式显示出来时，将会出现一个带边框的空棋盘界面。,9/15/2024,8,C程序设计快速进阶大学教程,15.1,数据模型,1.,模型设计,char tcsQipan2222;,/*,贪吃蛇棋盘是一个二维数组,(,如,22*,22,，包括墙壁,) */,int,i,j,;,/*,初始化贪吃蛇棋盘中间空白部分*,/,for(i,=1;i=20;i+),for(j,=1;j=20;j+),tcsQipanij,= ;,/*,初始化贪吃蛇棋盘上下墙壁*,/,for(i,=0;i=21;i+) tcsQipan0i=-; tcsQipan21i=-;,/*,初始化贪吃蛇棋盘左右墙壁*,/,for(i,=1;i=20;i+) tcsQipani0=|; tcsQipani21=|;,system(cls,);,/*,清屏*,/,/*,输出贪吃蛇棋盘*,/,for(i,=0;i=21;i+),for(j,=0;j=21;j+),printf(%c,tcsQipanij,);,printf(n,);,9/15/2024,9,C程序设计快速进阶大学教程,15.1,数据模型,1.,模型设计,空的贪吃蛇棋盘,9/15/2024,10,C程序设计快速进阶大学教程,15.1,数据模型,1.,模型设计,（,2,）蛇的模型，描述蛇头与蛇身在棋盘中的坐标。用一个,2,行,20,列的二维整型数组,tcsZuobiao,存放蛇头与蛇身中每一个节点的坐标。第,i,列,tcsZuobiao0i,和,tcsZuobiao1i,表示蛇的一个节点横坐标和纵坐标。若蛇在棋盘中的初始坐标为：,1,1,，,1,2,，,1,3,，,1,4,。约定蛇头用“,#”,表示，蛇身用“*”表示。,9/15/2024,11,C程序设计快速进阶大学教程,15.1,数据模型,1.,模型设计,int,tcsZuobiao220;,/*,蛇的坐标数组*,/,/*,初始蛇坐标位置：*,/,在数组,tcsZuobiao,中,0,列,tcsZuobiao00=1,，,tcsZuobiao10=1,对应,1,1,；,在数组,tcsZuobiao,中,1,列,tcsZuobiao01=1,，,tcsZuobiao11=2,对应,1,2,；,在数组,tcsZuobiao,中,2,列,tcsZuobiao02=1,，,tcsZuobiao12=3,对应,1,3,；,在数组,tcsZuobiao,中,3,列,tcsZuobiao03=1,，,tcsZuobiao13=4,对应,1,4,；,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,1,1,1,1,1,2,3,4,9/15/2024,12,C程序设计快速进阶大学教程,15.1,数据模型,1.,模型设计,还需要确定哪边是蛇头，哪边是蛇尾，用整型变量,head,和,tail,来表示。,int,head,tail,;,head=3;tail=0;,表示,tcsZuobiao,中第,3,列为蛇头的横纵坐标。第,0,列到第,2,列为蛇身节点的坐标，第,0,列为蛇尾的横纵坐标。,下一步工作是更改蛇位置对应棋盘坐标的棋盘数组字符，把空格字符改为蛇身字符（*）和蛇头字符（,#,）。,for(i,=1;i=3;i+) tcsQipan1i=*;,/*,蛇身*,/,tcsQipan14=#;,/,蛇头*,/,9/15/2024,13,C程序设计快速进阶大学教程,15.1,数据模型,2.,视图表达,把模型按照指定的方式显示出来。但是，显示一个新的视图时，需要把原来的视图清掉，否则会影响新视图的界面。这里用到了函数,system(cls,),，用来把显示器上所有内容清除掉，并且把光标位置定位到最左上角。,system(cls,),需要用到头文件,windows.h,，它并不是标准,C,的头文件，,VC,提供的函数库。,/*,输出贪吃蛇棋盘*,/,system(cls,);,/*,清屏*,/,for(i,=0;i=21;i+),for(j,=0;j=21;j+),printf(%c,tcsQipanij,);,printf(n,);,9/15/2024,14,C程序设计快速进阶大学教程,15.1,数据模型,3.,获取控制信息,获取控制信息可以分为,3,类：,（,1,）玩家按上下左右键；,（,2,）玩家按上下左右键之外的其他键退出游戏键；,（,3,）玩家在指定时间内未按键。,对于上述的第,1,种和第,3,种情况获取信息，然后交给更改数据模型模块去更改模型数据，对于第,2,种情况，直接终止游戏即可。,9/15/2024,15,C程序设计快速进阶大学教程,15.1,数据模型,3.,获取控制信息,（,1,）玩家按上下左右键,对于获取按键，若用,getchar,函数，采用的是缓冲的输入方式，需要按键后再按回车键，并且输入字符回显到标准输出设备上，这对玩游戏来说显然是不合适的，这时需要按键后直接获取其键值。为此采用函数,getch,函数获取键值，,getch,函数直接从控制台上获取一个字符，并且不回显到标准输出设备上方向。使用,getch,时要引入头文件,conio.h,。,由于上下左右键对应键值（,16,进制）如下：,方向键,(),：,0xe048,方向键,(),：,0xe050,方向键,(),：,0xe04b,方向键,(),：,0xe04d,按一次键，可以连续读取两个。,direction=,getch();direction,=,getch,();,/*direction,为字符型代表方向 *,/,direction,读到的第一字符个总是,e0,（,16,进制），第二个字符才能够区分出上下左右键，“上”为,72,（,16,进制,48,），“下”为,80,（,16,进制,50,），“左”为,75,（,16,进制,4b,），“右”为,77,（,16,进制,4d,）。,这样，就可以把获取的键值信息（上下左右）交给更给模型模块来更改模型。,9/15/2024,16,C程序设计快速进阶大学教程,15.1,数据模型,3.,获取控制信息,（,2,）玩家按上下左右键之外的其他键退出游戏键,按的键不为上下左右键时,(!(direction=72|direction=80|direction=75 |direction=77),退出程序。,9/15/2024,17,C程序设计快速进阶大学教程,15.1,数据模型,3.,获取控制信息,（,3,）玩家在指定时间内未按键,在这里约定,500,毫秒不按键，将维持原方向前进，等价于方向还取原来的方向值。判读,500,毫秒内是否按键，首先要设定一个当前时间（,start,），然后不断检测是否按键，在,500,毫秒内一直不按键，将取原来的方向值。,long start;,int,gamespeed,=500;,/*,游戏速度*,/,int,timeover,;,timeover,=1; start = clock();,while(!kbhit,() & (,timeover,=clock()-start=,gamespeed,) ;,if(timeover,),/*500,毫秒内按下键的情形*,/,getch,();,/*,按一次键，可以连取两个*,/,direction=,getch,();,else,/*500,毫秒内未按下键的情形*,/,direction=,direction,;,/*,维持原方向，可以不写，此处为便于理解*,/,9/15/2024,18,C程序设计快速进阶大学教程,15.1,数据模型,3.,获取控制信息,（,3,）玩家在指定时间内未按键,clock,函数是自进程启动后此进程运行到此处使用,cpu,的毫秒数，需要头文件,time.h,。,kbhit,函数是只检测是否有键按下，返回的是一个整型数，未按键时返回非,0,，需要头文件,conio.h,。,上一段代码中，语句：,start = clock();,用,start,存储程序运行到此处所用的时间（毫秒数）。,语句：,while(!kbhit,() & (,timeover,=clock()-start=,gamespeed,) ;,循环条件有两个：是否按键和新的运行时间与,start,的差是否小于,500,毫秒。所以，此循环退出有两种情况：一是按键了,!,kbhit,(),为假退出；二是，当前运行时间,clock(),与,start,的差大于,500,毫秒,timeover,=clock()-start=,gamespeed,),假退出（,500,毫秒内未按键），,timeover,得到的值为,0,（循环前,timeover,的值为,1,）。然后，利用,if(timeover,),就可以判断出，,500,毫秒内是否按键。,9/15/2024,19,C程序设计快速进阶大学教程,15.1,数据模型,4.,利用控制信息修改数据模型变为新的数据模型,利用控制模块获取的方向更新数据模型，具体算法如下：,说明：当前蛇各节点的坐标存储于二维数组,tcsZuobiao,的从,tail,列到,head,列。每一列代表一个蛇节点，其中,0,行为横坐标，,1,行为纵坐标。,head,列存储的是蛇头坐标，,tail,列存储的是蛇尾坐标。,direction,为获取的新方向。,9/15/2024,20,C程序设计快速进阶大学教程,15.1,数据模型,4.,利用控制信息修改数据模型变为新的数据模型,（,1,）利用原蛇头坐标位置（,tcsZuobiao0head,，,tcsZuobiao1head,）和新获取的方向确定新的蛇头坐标位置（,x,，,y,），分以下几种情况：, 如果,direction,为,72,（向上），则新蛇头坐标在原蛇头基础上，横坐标减,1,，纵坐标不变。,x= tcsZuobiao0head-1;y= tcsZuobiao1head;,如果,direction,为,80,（向下），则新蛇头坐标在原蛇头基础上，横坐标加,1,，纵坐标不变。,x= tcsZuobiao0head+1;y= tcsZuobiao1head;,如果,direction,为,75,（向左），则新蛇头坐标在原蛇头基础上，横坐标不变，纵坐标减,1,。,x= tcsZuobiao0head;y= tcsZuobiao1head-1;,如果,direction,为,77,（向右），则新蛇头坐标在原蛇头基础上，横坐标不变，纵坐标加,1,。,x= tcsZuobiao0head;y= tcsZuobiao1head+1;,9/15/2024,21,C程序设计快速进阶大学教程,15.1,数据模型,4.,利用控制信息修改数据模型变为新的数据模型,（,2,）判读新蛇头坐标是否合法，分两步：, 新蛇头坐标是否碰到墙壁。,if(x,=0 | x=21 |y=0 | y=21),return 0;,新蛇头坐标是否碰到蛇自身。,if(tcsQipanxy,!= ) /*,若棋盘中不为空格，则为蛇自身，程序中未实现“米”*,/,return 0;,9/15/2024,22,C程序设计快速进阶大学教程,15.1,数据模型,4.,利用控制信息修改数据模型变为新的数据模型,（,3,）蛇尾处理。, 贪吃蛇棋盘上原蛇尾清除，因为蛇前进了一步。,tcsQipan,tcsZuobiao0tailtcsZuobiao1tail= ;/*,原为蛇尾的“*”*,/,确定新蛇尾坐标对应的列，因为蛇前进了一步，原蛇尾被清除，原蛇坐标倒数第,2,个变成新蛇尾坐标，如图,15.4,所示。描述蛇坐标的二维数组，长度共,20,，可以利用取余形成环。,tail=(tail+1)%20;,9/15/2024,23,C程序设计快速进阶大学教程,15.1,数据模型,4.,利用控制信息修改数据模型变为新的数据模型,（,4,）蛇头处理。, 贪吃蛇棋盘上原蛇头变成蛇身，因为蛇前进了一步。,tcsQipan,tcsZuobiao0headtcsZuobiao1head=*;/*,原为蛇头的“,#”*/,确定新蛇头坐标对应列，因为蛇前进了一步，原蛇头坐标变成蛇身坐标，新蛇头坐标向前一列。描述蛇坐标的二维数组，长度共,20,，可以利用取余形成环。,head=(head+1)%20;,在新蛇头坐标列中写入新蛇头的坐标。,tcsZuobiao0head=x;,tcsZuobiao1head=y;,在贪吃蛇棋盘中新蛇头坐标位置写入“,#”,。,tcsQipantcsZuobiao0headtcsZuobiao1head=#;,这部分较为复杂，且功能相对独立，所以把它用一个单独的函数,changeModel,完成。,9/15/2024,24,C程序设计快速进阶大学教程,15.1,数据模型,9/15/2024,25,C程序设计快速进阶大学教程,15.2,查找与排序,查找和排序运算的使用频率很高，几乎在任何一个计算机系统软件和应用软件中都会涉及到,评奖学金,查词典,9/15/2024,26,C程序设计快速进阶大学教程,15.2.1,查找,顺序查找是一种简单的查找方法，查找时用待查的数据和给定的数据集中的数据逐个比较，直到找到相等的则查找成功；或找遍所有数据都不相等则查找失败。顺序查找算法非常简单，查找对数据集中的数据并没有顺序要求。,1.,顺序查找,9/15/2024,27,C程序设计快速进阶大学教程,15.2.1,查找,int,orderSearch(int,array,int,n,int,key),int,i;,/*,查找结果下标*,/,int,index=-1;,for(i,=0;i,n;i,+),if(key,=,arrayi,),index=i;,return index;,1.,顺序查找,int,main(),int,aN,=6,3,8,4,7,5;,int,resualt,;,int,key=4;,/*,查找的值*,/,resualt,=orderSearch(a,6,key);,if(resualt,!=-1),printf(found,index is %,d,resualt,);,else,printf(not,found!);,9/15/2024,28,C程序设计快速进阶大学教程,15.2.1,查找,二分法查找是一种效率较高的查找方法，要求数据集中的数据必须,按顺序,存储。不失一般性，假定下述描述时数据都是从小到大排序。,2.,二分法查找,9/15/2024,29,C程序设计快速进阶大学教程,15.2.1,查找,2.,二分法查找,二分法查找算法：,假定待查数据集为,arrayN,，第一个数据下标为,low,（,0,），最后一个数据下标为,high,（,N-1,），待查数据为,key,。,当,lowkey,，则由数据集的有序性可知,arrrymiddle,.,arrryhigh,均大于,key,，因此若数据集中存在等于,key,的数据，则该数据必定是在位置,middle,左边的子集,arrrylow,. arrrymiddle-1,中，故新的查找区间是左子集,arrrylow,. arrrymiddle-1,。, 类似地，若,arrrymiddle,key,，所以下一次查找区间为当前区间（,0,，,6,）的左半集,（,0,，,2,）,：,low,不变，,high=middle-1,为,2,。,9/15/2024,32,C程序设计快速进阶大学教程,15.2.1,查找,2.,二分法查找,第,2,次查找：,low=0,，,high=2,middle=(low+high)/2=1,array1,为,4,，不等于,key,的,7,array1key,，所以下一次查找区间为当前区间（,0,，,2,）的右半集,（,2,，,2,）,：,low=middle+1,为,2,，,high,不变。,9/15/2024,33,C程序设计快速进阶大学教程,15.2.1,查找,2.,二分法查找,第,3,次查找：,low=2,，,high=2,middle=(low+high)/2=2,array2,为,7,，等于,key,的,7,，找到，返回下标,2,。,9/15/2024,34,C程序设计快速进阶大学教程,15.2.1,查找,2.,二分法查找,int,binarySearch(int,array,int,n,int,key),int,middle,low,=0,high=n-1;,int,index=-1;,/*,查找结果下标*,/,while(low,key),/*,下一次在左半区间*,/,high=middle-1;,else,/*,下一次在右半区间*,/,low=middle+1;,return index;,9/15/2024,35,C程序设计快速进阶大学教程,15.2.1,查找,3.,插值查找,在一本英汉字典中寻找单词“,worst”,，我们决不会仿照对半查找那样，先查找字典中间的元素，然后查找字典四分之三处的元素等等,.,事实上，我们是在所期望的地址（在字典的很靠后的地方）附近开始查找的，我们称这样的查找为插值查找。可见，插值查找不同于前面讨论的二分法查找算法，前面介绍的二分法查找算法是基于严格比较的，即假定我们对线性表中元素的分布一无所知（或称没有启发式信息）。然而实际中，很多查找问题所涉及的表满足某些统计的特点。,9/15/2024,36,C程序设计快速进阶大学教程,15.2.1,查找,3.,插值查找,插值查找要满足两个假设条件：,（,1,）数据集是有序的。,（,2,）数据量大，并且数据呈现均匀分布特征。,插值插值与二分法查找的区别在于确定每次比较的位置不同，计算比较位置公式为：,pos=(key-,arraylow)/(arrayhigh-arraylow,)*(high-low+1)+low,其中,(key-,arraylow)/(arrayhigh-arraylow,),为,key,与查找区间内最小值的差和查找区间内最大值与最小值差的比例，然后乘上元素个数,(high-low+1),，最后再加上区间起始位置（,low,）。,9/15/2024,37,C程序设计快速进阶大学教程,15.2.1,查找,3.,插值查找,插值查找算法：,假定待查数据集为,arrayN,，第一个数据下标为,low,（,0,），最后一个数据下标为,high,（,N,），待查数据为,key,。,当,lowkey,，则由数据集的有序性可知,arrrypos,.,arrryhigh,均大于,key,，因此若数据集中存在等于,key,的数据，则该数据必定是在位置,middle,左边的子集,arrrylow,. arrrypos-1,中，故新的查找区间是左子集,arrrylow,. arrrypos-1,。, 类似地，若,arrrypos,key,，则要查找的,key,若存在必在,pos,的右子集,arrrypos+1.,arrryhigh,中，即新的查找区间是右子集,arrrypos+1.,arrryhigh,。,9/15/2024,38,C程序设计快速进阶大学教程,15.2.1,查找,3.,插值查找,9/15/2024,39,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,选择排序法算法的基本思想：首先找到数据集中的最小的数据，然后将这个数据同第一个数据交换位置（约定从小到大排序）；接下来在剩下的数据（不包含前面最小的）中找最小的数据，再将其同第二个数据交换位置；以此类推，每次在剩下的数据中找最小的数据，然后和剩下的数据中最前面的数据交换。若共,n,个数据，共需要做,n-1,趟，最后一个为最大的数据。,9/15/2024,40,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,对以下数据,array6,，,minFlag,（最小元素下标）：,8 4 3 9 6 2,0 1 2 3 4 5,下标,排序过程如下：,：代表比较两个数据，,minFlag,记载小元素下标。,9/15/2024,41,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,9/15/2024,42,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,9/15/2024,43,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,9/15/2024,44,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,9/15/2024,45,C程序设计快速进阶大学教程,15.2.2,排序,选择排序,9/15/2024,46,C程序设计快速进阶大学教程,15.2.2,排序,void,selectSort(int,array,int,n),int,i,j,;,int,minFlag,;,/*,记载最小元素下标 *,/,int,temp;,/*,交换数据的临时空间 *,/,for(i,=0;in-1;i+),/* i,从,0,到,n-2,，共,n-1,趟 *,/,minFlag,=i;,for(j,=i+1;j,n;j,+),/* j,从,i+1,到,n-1,，共,n-i-1,次*,/,if(arrayj,arrayminFlag,),minFlag,=j;,if(i,!=,minFlag,),/*,如果最小元素不是最前面的元素则交换*,/,temp=,arrayminFlag,;,arrayminFlag,=,arrayi,;,arrayi,=temp;,9/15/2024,47,C程序设计快速进阶大学教程,15.2.2,排序,int,main(),int,i,aN,=8,4,3,9,6,2;,selectSort(a,6);,for(i,=0;i6;i+),printf(%d,ai,);,9/15/2024,48,C程序设计快速进阶大学教程,
展开阅读全文