c语言程序设计14第十三讲第六章中

1,C语言编程是一项技艺，需要多年的历练才能达到较为完善的境界！-摘自ExpertCProgramming,2,第六章数组,3,复习（数值型数组）,如何定义数组？数组如何初始化？数组元素如何引用？循环语句循环三要素循环不变关系数组元素做函数参数传递的是什么？,4,作业提示,7.写一个函数，它判断一个整数（或浮点数）是否在一个数组中出现。如果出现，给出第一次出现的位置下标；没出现时给出-1。15.1请写一个程序，它输入一个学生成绩文件，输出按照每10分一个成绩段的学生人数。,5,数组的概念、定义和使用数组程序实例数组作为函数参数字符数组和字符串两维和多维数组编程实例,主要内容,一维数值型数组的重要应用,6,一维数组上的重要操作,排序查找插入删除元素交换,7,将计算机学院08级学生按平均分高低排序将08的奥运会各参赛国按英文字典序排序搜索引擎网页排序(PageRank)learningtorank排序问题无处不在,例1一维数组的应用（排序）,8,常用的排序算法,冒泡排序选择排序插入排序快速排序希尔排序堆排序,9,冒泡排序法输入n个正整数存在数组中，按由小到大的顺序排序（最大的数下沉）,例,38,49,76,97,13,97,97,27,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,a0a1a2a3a4a5a6a7,10,用冒泡法对10个数进行排序（N-S图及程序）,变量、数组长度定义,for(j=0;j=N-i-1;j+),scanf(“%d”,iN;i+),for(i=0;iaj+1,1,0,aj与aj+1交换,for(i=1;i=N-1;i+),printf(“%6d”,ai),/*冒泡法对10个数由小到大排序*/#include#defineN10voidmain()intaN,i,j,t;printf(请输入10个数:n);for(i=0;iaj+1)t=aj;aj=aj+1;aj+1=t;printf(n排序后的数据为:n);for(i=0;i课后作业n值如果是可变的?如果只对部分数据进行排序？某趟循环未发生交换，后面可不再循环，如何改进冒泡排序?,12,voidBubbleSort(intn,inta)intflag,i,j;for(i=1;iaj+1)t=ai;ai=ai+1;ai+1=t;flag=1;if(!flag)return;,改进的冒泡排序（函数）：设标志flag，如果某趟未发生交换，flag=0，说明排序完成，返回。,13,将数组a中的前5个数进行排序,#includevoidBubbleSort(intn,inta);intmain()inta10,i,j,t;printf(请输入10个数:n);for(i=0;i10;i+)scanf(“%d”,14,冒泡排序算法的复杂度分析,最坏情形下扫描数据总数n*(n+1)/2最坏情形下数据交换的次数n*(n-1)/2,15,选择法排序：把n个正整数按由小到大的顺序排序。,例,初始：49386597761327,i=1,13,49,一趟：13386597764927,i=2,27,38,六趟：13273849657697,16,用选择法对10个数进行排序（N-S图及程序）,/*选择法对10个数由小到大排序*/#include#defineN10voidSelectSort(intn,inta);voidmain()intaN,i;for(i=0;iN;i+)scanf(%d,变量、数组长度定义,k=ifor(j=i+1;jN;j+),scanf(“%d”,iN;i+),for(i=0;iN;i+),ajak,1,0,k=j,for(i=0;iN-1;i+),printf(“%4d”,ai),ai与ak交换,17,voidSelectSort(intn,inta)inti,j,k,t;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(ajak)k=j;t=ak;ak=ai;ai=t;,可否优化？如何优化？,18,选择排序算法的复杂度分析,最坏情形下扫描数据总数n*(n+1)/2最坏情形下数据交换的次数n1次,19,直接插入排序,排序方法（以排杂志为例）：1.任取一本杂志，作为排好序的一叠杂志的开始情况；2.从剩余杂志中任取一本，根据月份把它插入排好序的那叠杂志里的正确位置，使插入后的这叠杂志仍有序；3.如果还有未排好的杂志，就回到2，否则就结束；,20,a,t=8,t=77,t=66,t=55,21,voidinsertsort(intn,inta)/*递增序直接插入排序*/inti,j;intt;/*默认a0为已排好序*/for(i=1;i=0,排序函数的定义：,t=55,a0,ai,ai-1,将t插入到a0到ai之间,22,插入排序的复杂度分析,最坏情形下数据移动的次数n*(n-1)/2,23,例2一维数组的应用（查找）,intsearch(intb,intkey,intn)intj;for(j=0;jn;j+)if(bj=key)returnj;return(-1);,线性查找：从头到尾逐个查找，也称为顺序查找。,效率底！最坏情形下的时间复杂度是O(n),#include#defineN10intsearch(intb,int,int);voidmain()intaN,i,searchkey,element;for(i=0;iN;i+)scanf(%d,24,先检索中间的一个数据，如果不是所需的数据，则判断这要找的数在那一边，在所在的一边中再看中间的数是否为所需的数，依次下去。只适用于已排好序的数列。,折半查找,10172022314451556873899512013313701234567891011121314,折半查找最坏情形下的复杂度是O(lgn),25,折半查找程序,#include#defineN100voidf(int,int,int);voidmain()intaN,j,n,x;scanf(“%d”,voidf(inta,intn,intx)intb=0,t,find=0,m;t=n-1;dom=(t+b)/2;if(am=x)printf(找到了%3d,是a%dn,x,m);find=1;elseif(xm,算法：需插入x,3）插入x,1）找插入位置P,将ap到am依次后移一个位置,x=16,p,p=0;while(x=p;j-)aj+1=aj;,ap=x;,如何用for改写,if(xam-1)am=x;elsefor(i=0;i=x)for(j=m-1;j=i;j-)aj+1=aj;ai=x;break;,27,例4一维数组的应用（元素交换）将a数组中从第m个元素起一直到最后的元素平移到数组的开头，把a0到am-2中的元素向后顺移。,a0,am-1,an-1,算法：1、输入数组a,m2、for(j=1;jn-m+1;j+)将an-1放临时单元t；an-2a0依次后移一个位置；a0=t;3、输出数组a,28,字符数组预备知识,字符常量与字符串常量有什么区别？如何定义一个字符变量？,29,规定：一个字符串书写时不能跨行多个字符串之间仅由空白分隔，系统会将它们连成一个长字符串。双引号需用转义符：Hesaid:Imok!。,字符串以字符数组形式保存，存储形式是在所有字符后放0作为串结束标志。例Beijing,0不是串内容，却是字符串表示不可缺的部分。标准库的字符串处理函数都按这种表示设计，写字符串处理程序时也应该遵守这一规则。,30,6.4字符数组与字符串,字符数组定义方式（与其他数组一样）：charline1000;字符数组使用方式(与其他数组一样)：i=0;/*注意越界控制*/while(i1000,字符数组初始化方式一：逐个字符赋值charcity15=B,e,i,j,i,n,g;未指定初值的元素自动设0，编码0的字符称为0字符/空字符，用0表示，在C中有特殊用途（字符串结束标志）。,31,若字符数组里存了一些字符后放0，就符合字符串形式，可当作字符串使用（数组里存着字符串）：chara5=g,o,o,d,b5=i,s,a,c5=o,k,0,d5=o,k,0,x,x5=i,s,n,o,t;注意：字符数组的有效长度指第一个0前的字符个数+1,32,初始化方式二：用字符串常量chara120=PekingUniversity;未标元素个数时，数组大小确定为串长加1。例：chara3=PekingUniversity;数组a3有18个字符元素。,字符数组变量中保存字符串后，可作字符串用。例，若多个输出语句都用同样输出格式描述：charoutform1=”point:(%f,%f)n;.printf(outform1,x,y);.printf(outform1,s,t);,33,字符数组的赋值,将一个字符串赋值给一个字符数组,只能用在初始化的情况下,不能用在赋值语句中例如:charstr11;str=“Iamhappy”;是错误的.,34,字符串的输入输出,逐个字符I/O：%c数组名下标整个字符串I/O：%s数组名,例用%cmain()charstr5;inti;for(i=0;i5;i+)scanf(“%c”,例用%smain()charstr5;scanf(“%s”,str);printf(“%s”,str);,输入用字符数组名,不要加chara5;scanf(%s,a);for(i=0;istr2)printf(yes1n);if(strcmp(str1,str2)0)printf(yes2n);return0;,49,strcat(chars,constchart);t是字符串，s是保存字符串的数组。把t复制到s已有的字符之后，形成连起的串。数组s必须足够大。charb140=Programming,b210;strcat(b1,language);strcpy(b2,C);strcat(b1,b2);,字符串连接函数,另有限界连接函数strncat：strncat(