C语言教学课件：13-2_2_一维数组的应用（选择）.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1,第十三部分 数组,2,复习（数值型数组）,如何定义数组？,数组如何初始化？,数组元素如何引用？,循环语句,循环三要素循环不变关系,数组元素做函数参数传递的是什么？,3,数组的概念、定义和使用,数组程序实例,数组作为函数参数,字符数组和字符串,两维和多维数组,编程实例,主要内容,一维数值型数组的重要应用,4,一维数组上的重要操作,排序,查找,插入,删除,元素交换,5,排 序,6,将计算机学院,13,级学生按平均分高低排序,将,08,的奥运会各参赛国按英文字典序排序,搜索引擎网页排序,(PageRank),learning to rank,排序问题无处不在,例,1,一维数组的应用（排序）,7,常用的排序算法,冒泡排序,选择排序,插入排序,快速排序,希尔排序,堆排序,8,用冒泡法对,10,个整数按从小到大的顺序排列。,什么是,冒泡法排序,？,排序的过程,核心程序段,完整程序,怎么做？,9,冒泡法排序的思想,假设有,n,个数,将相邻的两个数依次进行比较,使小的在前,大的在后,那么第一轮比较,n-1,次就把最大的数排到了最后。,第二轮比较,n-2,次,就把次大的数排到了倒数第二,依此类推,直到第,n-1,轮比较,1,次,将最小的数排到了第一,算法结束。,算法的整体思路是让大的数不断地往下沉,小的数不断地往上冒,所以叫,冒泡排序法,。,10,冒泡法排序的思想,假设有,n,个数,将相邻的两个数依次进行比较,使小的在前,大的在后,那么第一轮比较,n-1,次就把最大的数排到了最后。,第二轮比较,n-2,次,就把次大的数排到了倒数第二,依此类推,直到第,n-1,轮比较,1,次,将最小的数排到了第一,算法结束。,算法的整体思路是让大的数不断地往下沉,小的数不断地往上冒,所以叫,冒泡排序法,。,算法的整体思路是让大的数不断地往下沉,小的数不断地往上冒，很像气泡往上升，所以叫,“,冒泡法排序,”,。,13 21 90 32 -1,13 21 32 90 -1,13 21 32 -1,90,a0 a1 a2 a3 a4,21,13 90 32 -1,13 21 90 32 -1,第一轮,冒泡法排序,一共比较几轮？,每轮比较几次？,第一轮的结果：将最大的数移到了最后一个位置（,n-1,）。,int a5,13 21 32 -1,90,a0 a1 a2 a3 a4,13 21 32 -1,90,13 21 -1,32 90,第二轮,13 21 32 -1,90,第二轮的结果：,将第二大的数移到了,n-2,的位置。,int a5,a0 a1 a2 a3 a4,13 21 -1,32 90,第三轮,13 21 -1,32 90,13 -1,21 32 90,第三轮的结果：,将第三大的数移到了,n-3,的位置。,int a5,a0 a1 a2 a3 a4,第四轮,13 -1,21 32 90,-1,13 21 32 90,-1,13 21 32 90,结果：,最后一轮的结果：,将最小的数移到了第,0,的位置。,for(i=1;i n;i+),for(j=0;jaj+1),med=aj;,aj=aj+1;,aj+1=med;,将,aj,与,aj+1,的内容交换,冒泡法排序程序段,5,aj,2,med,5,2,5,aj+1,printf(n,排序之前：,n);,for(i=0;in;i+),printf(%6d,ai);,包含、宏定义,主程序开始,主程序区变量定义,n,个数输入到数组,a,中,将未排序的,n,个数输出,#include,#define n 5,void main(),int an,i,j,med;,printf(please input);,printf(%d integers:,n);,for(i=0;in;i+),scanf(%d,for(i=1;in;i+),开始排序！,外循环,内循环,a4,a3,a2,a1,a0,for(j=0;jaj+1),med=aj;,aj=aj+1;,aj+1=med;,printf(n,排序之后：,n);,for(i=0;in;i+),printf(%6d,ai);,排序之后的结果输出,18,问题,输入十个正整数，把这十个正整数按由,大到小,的顺序排序，如何修改程序？,n,值,如果是,可变,的,?,如果只对,部分数据,进行,排序,？,某趟循环未发生交换，后面可不再循环，,如何改进,冒泡排序,?,19,void BubbleSort(int n,int a),int flag,i,j;,for(i=1;i=n-1;i+),flag=0;,for(j=0;j aj+1),t=ai;,ai=ai+1;,ai+1=t;,flag=1;,if(!flag)break;,改进的冒泡排序（函数）：设标志,flag,，如果某趟未发生交换，,flag=0,，说明排序完成，返回。,20,将数组,a,中的前,5,个数进行排序,#include,void BubbleSort(int n,int a);,int main(),int a10,i,j,t;,printf(,请输入,10,个数,:n);,for(i=0;i 10;i+),scanf(“%d”,BubbleSort(5,a);,for(i=0;i 10;i+),printf(“%d”,ai);,return 0;,21,冒泡排序算法的复杂度分析,最坏情形下扫描数据总数,n*(n+1)/2,最坏情形下数据交换的次数,n*(n-1)/2,22,选择法排序：,把,n,个正整数按由小到大的顺序排序。,例,初始：,49 38 65 97 76 13 27,k,j,i=1,13,49,一趟：,13,38 65 97 76 49 27,i=2,27,38,二趟：,13 27,65 97 76 49 38,三趟：,13 27 38,97 76 49 65,四趟：,13 27 38 49,76 97 65,五趟：,13 27 38 49 65,97 76,六趟：,13 27 38 49 65 76,97,k,k,k,k,j,j,j,j,j,j,j,j,j,j,23,用选择法对,10,个数进行排序（,N-S,图及程序）,/*,选择法对,10,个数由小到大排序*,/,#include,#define N 10,void SelectSort(int n,int a);,void main(),int aN,i;,for(i=0;i N;i+),scanf(%d,printf(n);,SelectSort(N,a);,printf(the sorted numbers:n);,for(i=0;i N;i+),printf(%4d,ai);,printf(n);,变量、数组长度定义,k=i,for(j=i+1;jN;j+),scanf(“%d”,&ai),for(i=0;iN;i+),for(i=0;iN;i+),ajak,1,0,k=j,for(i=0;iN-1;i+),printf(“%4d”,ai),ai,与,ak,交换,24,void SelectSort(int n,int a),int i,j,k,t;,for(i=0;i n-1;i+),k=i;,for(j=i+1;j n;j+),if(aj ak)k=j;,t=ak;,ak=ai;,ai=t;,可否优化？如何优化？,25,选择排序算法的复杂度分析,最坏情形下扫描数据总数,n*(n+1)/2,最坏情形下数据交换的次数,n,1,次,26,直接插入排序,排序方法（,以排杂志为例,）,：,1.,任取一本杂志，作为排好序的一叠杂志的开始情况；,2.,从剩余杂志中任取一本，根据月份把它插入排好序的那叠杂志里的正确位置，使插入后的这叠杂志仍有序；,3.,如果还有未排好的杂志，就回到,2,，否则就结束；,27,99,8,77,66,55,44,33,22,11,1,a,99,8,77,66,55,44,33,22,11,1,t=8,8,99,77,66,55,44,33,22,11,1,8,99,77,66,55,44,33,22,11,1,t=77,8,99,99,66,55,44,33,22,11,1,8,77,99,66,55,44,33,22,11,1,8,77,99,66,55,44,33,22,11,1,t=66,8,77,99,99,55,44,33,22,11,1,8,77,77,99,55,44,33,22,11,1,8,66,77,99,55,44,33,22,11,1,8,66,77,99,55,44,33,22,11,1,t=55,28,void insertsort(int n,int a),/*,递增序直接插入排序,*,/,int i,j;,int t;/*,默认,a0,为已排好序*,/,for(i=1;i=0 -j),aj+1=aj;/*,大元素依次后移,*,/,if(j!=i-1)aj+1=t;,排序函数的定义,：,8,66,77,99,55,44,33,22,11,1,t=55,a0,ai,ai-1,将,t,插入到,a0,到,ai,之间,29,插入排序的复杂度分析,最坏情形下数据移动的次数,n*(n-1)/2,30,查,找,31,关于查找：,首先，待查找的数据放在一个一维数组中；,问题：到这样一个一维数组中去寻找一个满足某种特征的数组元素，如果找到，返回一个整数值，标志这个数在数组中的位序；如果找不到，返回整数,0,。,查找的方法：计算机中有许多的查找方法，在这里，我们只介绍两个方法：顺序查找和折半查找。,32,一、顺序查找,顺序查找方法适用于无序存放的一组数据。查找从一维数组的最后一个数组元素开始比较，直到找到指定的数组元素或已到达数组的头部依然没找到。,说明：,如果待查找的数据有,n,个，那么，我们定义一个拥有,n+1,个数组元素的一维数组；其中，下标为,0,的数组元素留作他用，待查找的数据从下标为,1,的位置开始存放。,查找时，首先将指定的数据放入下标为,0,的位置。然后开始查找。,33,顺序查找过程：,顺序查找时的内存状态：,10,9,8,7,6,5,4,3,2,1,0,0,号单元空置,数据元素从,1,号单元开始存放,34,顺序查找过程：,10,9,8,7,6,5,4,3,2,1,0,21,37,88,19,92,05,64,56,80,75,ST,假设给定值,key=64,，,要求,n,k,k,64,k,k,K=7,STk=key,，问,:k =?,35,顺序查找过程：,10,9,8,7,6,5,4,3,2,1,0,21,37,88,19,92,05,64,56,80,75,ST,假设给定值,e=,60,，,要求,STk=e,，问,:k =?,n,k,k,60,k,k,K=0,k,36,查找的结果：,如果在查找表中存在要查找的元素，则返回该元素所在的位置的下标；,如果在查找表中不存在要查找的元素，则返回整数,0,；,程序描述如下：,37,程序：,a0=Key;,i=N-1;,while,(ai!=Key),-i;,if,(i),printf(,数据找到了,是第,%d,个,n,i);,else,printf(,数据没有找到,n);,#include,#define,N 4,void,main(),int,aN,i,Key;,printf(,输入要查找的序列,:n);,for,(i=1;iN;i+),scanf(%d,printf(“,输出要查找的序列：,n);,for,(i=1;iN;i+),printf(%6d,ai);,printf(n,输入要查找的数据,:n);,scanf(%d,38,例,2,一维数组的应用（查找）,int search(int b,int key,int n),int j;,for(j=0;j n;j+),if(bj=key),return j;,return(-1);,线性查找：,从头到尾逐个查找，也称为顺序查找。,效率底！,最坏情形下的时间复杂度是,O(n),#include,#define N 10,int search(int b,int,int);,void main(),int aN,i,searchkey,element;,for(i=0;i,中间位置,的数组元素值,则在后半部继续进行折半查找。,否则,在前半部进行折半查找。,41,折半查找算法,设待查元素所在区域的下界为,low,，上界为,high,，则中间位置,mid=(low +high)/2,若,mid,元素值等于给定值，则查找成功,;,若,mid,元素值大于给定值，则在区域,mid+1,，,high,进行折半查找；,若,mid,元素值小于给定值，则在区域,low,，,mid-1,内进行折半查找；,42,例如,:,key=64,的查找过程如下：,low,指示查找区间的下界,high,指示查找区间的上界,mid,=(low+high)/2,05,13,19,21,37,56,64,75,80,88,92,0 1 2 3 4 5 6 7 8 9 10 11,low,high,mid,low,mid,high,mid,折半查找最坏情形下的复杂度是,O(lgn),#include,#define N 15,void main(),int a100,key,i,low,high,mid,find=0;,printf(,请输入数据,:n);,for(i=1;i N;i+)scanf(“%d”,printf(,输入要查找的数据,key:n);scanf(%d,low=1;high=N-1;,while(low=high),mid=(low+high)/2;,if(key=amid)find=1;break;,else if(keyamid)high=mid-1;,else low=mid+1;,if(find)printf(%dn,mid);,else printf(%dn,mid=0);,44,折半查找程序,#include,#define N 100,void f(int,int,int);,void main(),int aN,j,n,x;,scanf(“%d”,for(j=0;j n;j+),scanf(“%d”,printf(“n”);,printf(“,输入要查找的数：,n”);,scanf(“%d”,f(a,n,x);,void f(int a,int n,int x),int b=0,t,find=0,m;,t=n-1;,do,m=(t+b)/2;,if,(am=x),printf(,找到了,%3d,是,a%dn,x,m);,find=1;,else,if(x am)t=m-1;,else b=m+1;,while(b ,大），,nm,算法：需插入,x,3,）插入,x,1,）找插入位置,P,将,ap,到,am,依次后移一个位置,1,3,4,6,9,11,15,17,20,x=16,p,p=0;,while(x ap)&(p=p;j-),aj+1=aj;,ap =x;,如何用,for,改写,if(x am-1)am=x;,else,for(i=0;i=x),for(j=m-1;j=i;j-),aj+1=aj;,ai=x;,break;,47,元素交换,48,例,4,一维数组的应用（元素交换）,将,a,数组中从,第,m,个元素,起一直到最后的元素平移到数组的开头，把,a0,到,am-2,中的元素向后顺移。,a0,am-1,an-1,算法：,1,、输入数组,a,m,2,、,for(j=1;jn-m+1;j+),将,an-1,放临时单元,t,；,an-2,a0,依次后移一个位置；,a0=t;,3,、输出数组,a,49,Q&A!,