《c语言程序设计第十三讲第六章中实用教案》由会员分享，可在线阅读，更多相关《c语言程序设计第十三讲第六章中实用教案（51页珍藏版）》请在金锄头文库上搜索。
1、1复习(fx)（数值型数组）如何定义数组？数组如何初始化？数组元素如何引用(ynyng)？循环语句循环三要素循环不变关系数组元素做函数参数传递的是什么？第1页/共50页第一页，共51页。2作业(zuy)提示7.写一个函数，它判断(pndun)一个整数（或浮点数）是否在一个数组中出现。如果出现，给出第一次出现的位置下标；没出现时给出-1。15.1请写一个程序，它输入一个学生成绩文件，输出按照每10分一个成绩段的学生人数。第2页/共50页第二页，共51页。3数组的概念、定义和使用数组程序(chngx)实例数组作为函数参数字符数组和字符串两维和多维数组编程实例主要(zhyo)内容n一维数值型数组的重
2、要(zhngyo)应用第3页/共50页第三页，共51页。4一维数组上的重要(zhngyo)操作排序查找插入删除元素(yuns)交换第4页/共50页第四页，共51页。5将计算机学院08级学生(xusheng)按平均分高低排序将08的奥运会各参赛国按英文字典序排序搜索引擎网页排序(PageRank)learningtorank排序问题无处不在例1一维数组的应用(yngyng)（排序）第5页/共50页第五页，共51页。6常用(chnyn)的排序算法冒泡排序(pix)选择排序(pix)插入排序(pix)快速排序(pix)希尔排序(pix)堆排序(pix)第6页/共50页第六页，共51页。7冒泡排序法
3、输入(shr)n(shr)n个正整数存在数组中，按由小到大的顺序排序（最大的数下沉）例38 49 65 76 13 27 30 97 第一趟38 49 65 13 27 30 76 第二趟38 49 13 27 30 65 第三趟38 13 27 30 49 第四趟13 27 30 38 第五趟13 27 30 第六趟49 38 65 97 76 13 27 30 初始关键字n=838497697139797273097137676762730136527653065131349493049273827383038 13 27 第七趟a0a1a2a3a4a5a6a7第7页/共50页第七页，共5
4、1页。8用冒泡法对1010个数进行(jnxng)(jnxng)排序（N-SN-S图及程序）变量、数组长度(chngd)定义 for(j=0;j=N-i-1;j+) scanf ( “%d” , &ai ) for(i=0;iN;i+) for(i=0;iaj+110 aj与aj+1交换(jiohun) for(i=1;i=N-1;i+) printf ( “%6d”, ai )/*冒泡法对10个数由小到大排序*/#include #define N 10void main() int aN , i , j , t; printf(请输入10个数:n); for ( i = 0 ; i N ;
5、i+) scanf(%d,&ai); printf(n); for (i = 1; i = N-1; i+) for (j = 0; j aj+1) t = aj; aj = aj+1; aj+1 = t; printf(n排序后的数据为:n); for (i = 0; i 课后作业n值如果是可变的?如果只对部分数据进行排序？某趟循环未发生交换，后面可不再循环，如何改进冒泡排序?第9页/共50页第九页，共51页。10void BubbleSort(int n, int a )int flag, i, j;for (i = 1; i = n-1; i+) flag = 0; for (j = 0
6、; j aj+1) t = ai;ai = ai+1; ai+1 = t;flag = 1;if ( !flag ) return; 改进的冒泡排序（函数(hnsh)）：设标志flag，如果某趟未发生交换，flag=0，说明排序完成，返回。第10页/共50页第十页，共51页。11将数组a中的前5个数进行(jnxng)排序#include void BubbleSort(int n, int a );int main()int a10 , i , j , t; printf(请输入(shr)10个数:n); for( i = 0 ; i 10 ; i+) scanf(“%d”, &ai); Bu
7、bbleSort(5, a); for( i = 0 ; i 10 ; i+) printf(“%d”, ai); return 0;第11页/共50页第十一页，共51页。12冒泡排序算法(sunf)的复杂度分析最坏情形(qngxing)下扫描数据总数n*(n+1)/2最坏情形(qngxing)下数据交换的次数n*(n-1)/2第12页/共50页第十二页，共51页。13选择法排序(pi x)：把n个正整数按由小到大的顺序排序(pi x)。例初始(ch sh)： 49 38 65 97 76 13 27 kji=11349一趟： 13 38 65 97 76 49 27 i=22738二趟： 1
8、3 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 kkkkjjjjjjjjjj第13页/共50页第十三页，共51页。14用选择(xunz)法对10个数进行排序（N-S图及程序）/*选择(xunz)法对10个数由小到大排序*/#include #define N 10void SelectSort(int n, int a);void main()int aN, i;for (i = 0; i N; i+)
9、scanf(%d, &ai);printf(n);SelectSort(N, a);printf(the sorted numbers:n);for (i = 0; i N; i+) printf(%4d, ai);printf(n);变量、数组长度(chngd)定义k=ifor(j=i+1;jN;j+) scanf ( “%d” , &ai ) for(i=0;iN;i+) for(i=0;iN;i+) ajak10k=j for(i=0;iN-1;i+) printf ( “%4d”, ai ) ai与ak交换第14页/共50页第十四页，共51页。15void SelectSort(int
10、 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; 可否(k fu)优化？如何优化？第15页/共50页第十五页，共51页。16选择排序算法(sunf)的复杂度分析最坏情形下扫描数据总数(zngsh)n*(n+1)/2最坏情形下数据交换的次数n1次第16页/共50页第十六页，共51页。17直接(zhji)插入排序排序方法（以排杂志为例）：1. 任取一本(y bn)杂志，作为排好序的一叠杂志的开始情况；2.
11、 从剩余杂志中任取一本(y bn)，根据月份把它插入排好序的那叠杂志里的正确位置，使插入后的这叠杂志仍有序；3.如果还有未排好的杂志，就回到2，否则就结束；第17页/共50页第十七页，共51页。18998776655443322111a998776655443322111t=8899776655443322111899776655443322111t=77899996655443322111877996655443322111877996655443322111t=66877999955443322111877779955443322111866779955443322111866779955
12、443322111t=55第18页/共50页第十八页，共51页。19voidinsertsort(intn,inta)/*递增序直接插入排序*/inti,j;intt;/*默认a0为已排好序*/for(i=1;i=0&taj;-j)aj+1=aj;/*大元素(yuns)依次后移*/if(j!=i-1)aj+1=t;排序函数(hnsh)的定义：866779955443322111t=55a0aiai-1将t插入(ch r)到a0到ai之间第19页/共50页第十九页，共51页。20插入排序的复杂度分析(fnx)最坏情形下数据移动(ydng)的次数n*(n-1)/2第20页/共50页第二十页，共51
13、页。21例2 2一维数组的应用(yngyng)(yngyng)（查找）int search(int b, int key, int n)int j;for(j = 0; j n; j+)if (bj = key) return j;return (-1);线性查找： 从头到尾逐个查找，也称为(chn wi)顺序查找。效率(xio l)底！最坏情形下的时间复杂度是O(n)#include #define N 10int search(int b,int,int);void main()int aN, i, searchkey, element;for (i = 0; i N; i+)scanf(
14、%d , &ai);printf(Input searchkey:n);scanf(%d, &searchkey);element = search(a, searchkey, N);if (element != -1)printf(Find, its %dth emement.n, element+1);elseprintf(Not find.n);第21页/共50页第二十一页，共51页。22先检索中间的一个数据，如果不是所需的数据，则判断这要找的数在那一边，在所在的一边中再看中间的数是否为所需的数，依次下去。只适用(shyng)于已排好序的数列。折半(zhbn)查找101720223144
15、515568738995120133137 0 1 2 3 4 5 6 7 8 9 1011 12 13 14bot0mid0top0top1mid1bot1bot2top2mid2xtop3bot3 mid3折半查找(ch zho)最坏情形下的复杂度是O(lgn)第22页/共50页第二十二页，共51页。23折半查找(chzho)程序#include#define N 100void f(int , int, int);void main() int aN, j, n, x; scanf(“%d”, &n); for (j = 0; j n; j+) scanf(“%d”, &aj); pri
16、ntf(“n”); printf(“输入(shr)要查找的数：n”); scanf(“%d”, &x); 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 -大），nmnm算法(sun f)：需插入x3）插入(ch r)x1）找插入位置P2)将ap到am
17、依次后移一个位置1346911151720x=16pp = 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; 第24页/共50页第二十四页，共51页。25例4 4一维数组的应用（元素交换）将a a数组中从第m m个元素起一直到最后(zuhu)(zuhu)的元素平移到数组的开头，把a0a0到am-2am-2中的元素向后顺移。a0am-1an-1算法：1、
18、输入数组a ,m 2、for(j=1;jn-m+1 ;j+) 将an-1放临时单元t； an-2a0依次后移一个(y )位置； a0 =t; 3、输出数组a 第25页/共50页第二十五页，共51页。26字符(zf)数组预备知识字符常量(chngling)与字符串常量(chngling)有什么区别？如何定义一个字符变量？第26页/共50页第二十六页，共51页。27规定：一个字符串书写(shxi)时不能跨行多个字符串之间仅由空白分隔，系统会将它们连成一个长字 符串。双引号需用转义符：He said: Im ok!。字符串以字符数组形式(xngsh)保存，存储形式(xngsh)是在所有字符后放0作为
19、串结束标志。例 Beijing0不是串内容，却是字符串表示不可缺的部分。标准库的字符串处理函数都按这种表示设计(shj)，写字符串处理程序时也应该遵守这一规则。第27页/共50页第二十七页，共51页。286.4 字符(z f)数组与字符(z f)串字符数组定义方式（与其他数组一样）：char line1000;字符数组使用方式(与其他数组一样)：i=0; /* 注意(zh y)越界控制 */while(i1000 & (linei=getchar()!=n) +i;字符数组初始化方式一：逐个字符赋值char city15=B,e,i,j,i,n,g;未指定初值的元素(yun s)自动设0，编码
20、0的字符称为0字符/空字符，用0表示，在C中有特殊用途（字符串结束标志）。第28页/共50页第二十八页，共51页。29若字符数组里存了一些字符后放0 ，就符合字符串形式，可当作字符串使用（数组里存着字符串）：char a5 = g, o, o, d, b5 = i, s, a, c5 = o, k, 0, d5 = o, k, 0, x, x5 = i,s,n,o,t;注意(zh y)：字符数组的有效长度指第一个0前的字符个数+1第29页/共50页第二十九页，共51页。30初始化方式二：用字符串常量char a120 = Peking University;未标元素(yun s)个数时，数组大
21、小确定为串长加1。例：char a3 = Peking University;数组a3有18个字符元素(yun s)。字符数组变量中保存(bocn)字符串后，可作字符串用。例，若多个输出语句都用同样输出格式描述：charoutform1=”point:(%f,%f)n;.printf(outform1,x,y);.printf(outform1,s,t);第30页/共50页第三十页，共51页。31字符(z f)(z f)数组的赋值将一个字符串赋值给一个字符数组, ,只能用在初始化的情况下, ,不能用在赋值语句(yj)(yj)中例如: :char str11;char str11;str = “
22、I am happy”;str = “I am happy”;是错误的. .第31页/共50页第三十一页，共51页。32字符串的输入输出l逐个字符I/O： %c数组名下标(xi bio)l整个字符串I/O： %s数组名例 用%c main() char str5; int i; for (i = 0; i 5; i+) scanf(“%c”, &stri); for(i = 0; i 5; i+) printf(“%c”, stri);例 用%s main() char str5; scanf(“%s”, str); printf(“%s”, str);输入用字符数组名,不要加&输入串长度(c
23、hngd)数组维数遇空格或回车结束自动加0输出(shch)用字符数组名,遇0结束第32页/共50页第三十二页，共51页。33int main() int i; char a5; scanf(%s, a); for (i = 0; i 5; i+) printf(%c, ai); return 0;运行情况：（1）若输入(shr) hel , 正常（2）若输入(shr) hell , 正常（3）若输入(shr) hello , 用%s 输出，会出现问题？ h e l 0 h e l l 0 h e l l o输入(shr)字符串长度数组维数例子(lzi)第33页/共50页第三十三页，共51页。3
24、4 H o w 0 a r e 0 y o u ? 0 #include main() char a15, b5, c5; scanf(%s%s%s, a, b, c); printf(a=%snb=%snc=%sn, a, b, c); scanf(%s, a); printf(a=%sn, a);运行(ynxng)情况：输入：How are you?输出：a=How b=are c=you?输入：How are you?输出：a=Howscanf中%s输入时,遇空格(kn )或回车结束运行(ynxng)情况：输入：How are you?字符串输入举例第34页/共50页第三十四页，共51页
25、。35voidstr_copy(chars,constchart)inti=0;while(ti!=0)si=ti;+i;si=0;循环(xnhun)结束时ti的空字符正好赋给si。voidstr_copy(chars,constchart)inti=0;while(si=ti)!=0)+i;字符串处理程序实例(shl)例1，写函数将一字符(z f)串复制到一字符(z f)数组。假定数组足以存放被复制串及空字符(z f)。第35页/共50页第三十五页，共51页。36字符串处理函数的典型(dinxng)循环：for(i=0;si!=0;+i)用是否空字符确定对字符串的处理是否已完成。例2，（二进
26、制转换）写函数，给它一个表示二进制数的0/1字符串，它算出这个(zh ge)串表示的整数值。 二进制数bnbn-1.b2b1b0的值可以用下面(xi mian)公式计算：(.(bn2) +bn-1)2 +.)2 + b2)2 + b1)2 + b0据此可写出循环，循环条件判断二进制数是否结束。二进制数位只能是0/1，只需要在遇到1时加1。 第36页/共50页第三十六页，共51页。37intbin2int(constchars)inti=0,n=0;while(si!=0&(si=0|si=1)n=n*2;if(si=1)+n;+i;returnn;由于数字字符的编码连续排列.函数改为：int
27、bin2int(const char s) int i = 0, n = 0; while(si!=0&(si=0|si=1) n = n * 2 + (si - 0); +i; return n; /* 这种写法(xif)可以推广到八进制和其他进制 */第37页/共50页第三十七页，共51页。38例3计算字符(zf)数组的有效长度#include int strLen(const char s);int main() int len; char str10; scanf(%s, str); len = strLen(str); printf(%dn, len); printf(%sn, st
28、r); return 0;int strLen(const char s) int i=0; while(si!=0)i+; return (i+1);有问题(wnt)吗？第38页/共50页第三十八页，共51页。39包含(bohn)在头文件 string.hu字符串输出(shch)函数putsu格式：puts(字符数组)u功能：向显示器输出(shch)字符串（输出(shch)完，换行）u说明：字符数组必须以0结束u字符串输入(shr)函数getsu格式：gets(字符数组)u功能：从键盘输入(shr)一以回车结束的字符串放入字符数组中，u 并自动加0u说明：输入(shr)串长度应小于字符数组维
29、数标准库中常用的字符串处理函数第39页/共50页第三十九页，共51页。40例 #include main( ) char string80; printf(“Input a string:”); gets(string); puts(string); 输入(shr): How are you?输出: How are you ? scanf(“%s”,str);gets(str);区别(qbi)是scanf取不到空格gets()函数(hnsh)是个过时的函数(hnsh)第40页/共50页第四十页，共51页。41标准(biozhn)库中常用的字符串处理函数包含在头文件 string.h字符串（实际
30、）长度(chngd)函数strlen(const char s);#include#includeint main() char str10 = China; int n; printf(Length=%dn, strlen(str); n = strlen(str); printf(n=%dn, n); return 0;第41页/共50页第四十一页，共51页。42标准(biozhn)库中常用字符串处理函数复制函数：strcpy(chars,constchart);t应为字符串，const说明参数值不修改。字符数组s应足够大，以保证(bozhng)复制不越界。例：chara116,a216;
31、strcpy(a1,programming);strcpy(a2,a1);限界复制(fzh)函数strncpy，限制复制(fzh)长度：strncpy(chars,constchart,intn);将t中前n个字符复制(fzh)到s中。program m ing0 0 0 0 0a1第42页/共50页第四十二页，共51页。43#include#includeint main()char a5 , b5 = Power, c1, c2;c1 = A; c2 = B;printf(b=%sn, b);a0 = C; a1 = h; a2 = i; a3 = n; a4 = a;printf(a=%
32、sn, a);a = Study; printf(a=%sn, a);a = b; printf(a=%sn, a);return 0;程序(chngx)查错第43页/共50页第四十三页，共51页。44#include#includeint main()char a6 ,b6= Power,c1,c2;c1=A;c2=B;printf(b=%sn,b);a0=C;a1=h; a2=i; a3=n; a4=a;a5=0;printf(a=%sn,a);strcpy(a, Study ); printf(a=%sn,a);strcpy(a,b); printf(a=%sn,a);return 0;
33、改正错误后第44页/共50页第四十四页，共51页。45intstrcmp(constchars1,constchars2)两字符串相同时返回值0;s1大于s2的情况下返回大于0的值;否则返回小于0的值。判断字符串大小的标准是字符串的字典(zdin)序。（字典(zdin)序就是普通英语词典里单词排列的顺序,按ASCII码值大小比较）“DOG”A”“computer”compare”字 符 串 比 较 (bjio)函数限界(xinji)比较函数：intstrncmp(constchars1,constchars2,intn);第45页/共50页第四十五页，共51页。46#include#inclu
34、deint main()char str16 = China, str26 = Korea;int yes;yes = strcmp(str1, str2);printf(%dn, yes);yes=strcmp(China, Korea);printf(%dn, yes);if (str1 str2)printf(yes1n);if (strcmp(str1,str2) 0)printf(yes2n);return 0;第46页/共50页第四十六页，共51页。47strcat(chars,constchart);t是字符串，s是保存(bocn)字符串的数组。把t复制到s已有的字符之后，形成连
35、起的串。数组s必须足够大。charb140=Programming,b210;strcat(b1,language);strcpy(b2,C);strcat(b1,b2);字 符 串 连 接 (linji)函数另有限界连接(linji)函数strncat：strncat(chars,constchart,intn);string.h还包含许多函数，参看有关标准库的一章第47页/共50页第四十七页，共51页。48作业(zuy)分别写函数(hnsh)用冒泡和选择两种排序方法实现n(如n=10)个数从大到小排序根据排好序的N个正整数，用折半查找法完成某个数的查找（要求先调用排序函数(hnsh)再调用
36、查找函数(hnsh)）。写程序实现例4：将a数组中从第m个元素起一直到最后的元素平移到数组的开头（写函数(hnsh)并调用）P2155(1),6,11(设所有空格分隔的连续字符构成词),13第48页/共50页第四十八页，共51页。49Q & A!第49页/共50页第四十九页，共51页。50感谢您的欣赏(xnshng)！第50页/共50页第五十页，共51页。内容(nirng)总结1。循环三要素循环不变关系。7.写一个函数，它判断一个整数（或浮点数）是否在一个数组中出现。如果出现，给出第一次出现的位置下标。j=N-i-1。scanf(%d, &ai)。101720223144515568738995120133137。p=p+1。字符(z f)常量与字符(z f)串常量有什么区别。例，若多个输出语句都用同样输出格式描述：。例1，写函数将一字符(z f)串复制到一字符(z f)数组。感谢您的欣赏第五十一页，共51页。
