c语言程序设计14第十三讲(第六章中).ppt

1,C语言编程是一项技艺，需要多年的历练才能达到较为完善的境界！ -摘自Expert C Programming,2,第六章 数组,3,复习（数值型数组）,如何定义数组？ 数组如何初始化？ 数组元素如何引用？ 循环语句 循环三要素循环不变关系 数组元素做函数参数传递的是什么？,4,作业提示,7.写一个函数，它判断一个整数（或浮点数）是否在一个数组中出现。如果出现，给出第一次出现的位置下标；没出现时给出-1。 15.1 请写一个程序，它输入一个学生成绩文件，输出按照每10分一个成绩段的学生人数。,5,数组的概念、定义和使用 数组程序实例 数组作为函数参数 字符数组和字符串 两维和多维数组 编程实例,主要内容,一维数值型数组的重要应用,6,一维数组上的重要操作,排序 查找 插入 删除 元素交换,7,将计算机学院08级学生按平均分高低排序 将08的奥运会各参赛国按英文字典序排序 搜索引擎网页排序(PageRank)learning to rank 排序问题无处不在,例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,a0 a1 a2 a3 a4 a5 a6 a7,10,用冒泡法对10个数进行排序（N-S图及程序）,变量、数组长度定义,for(j=0;j=N-i-1;j+),scanf ( “%d” , &ai ),for(i=0;iN;i+),for(i=0;iN;i+),ajaj+1,1,0,aj与aj+1交换,for(i=1;i=N-1;i+),printf ( “%6d”, ai ),/*冒泡法对10个数由小到大排序*/ #include #define N 10 void main() int aN , i , j , t; printf(“请输入10个数:n“); for ( i = 0 ; i aj+1) t = aj; aj = aj+1; aj+1 = t; printf(“n排序后的数据为:n“); for (i = 0; i N; i+) printf(“%6d“, ai); printf(“n“); ,11,问题,输入十个正整数，把这十个正整数按由大到小的顺序排序，如何修改程序？课后作业 n值如果是可变的? 如果只对部分数据进行排序？ 某趟循环未发生交换，后面可不再循环， 如何改进冒泡排序?,12,void BubbleSort(int n, int a ) int flag, i, j; for (i = 1; i aj+1) t = ai; ai = ai+1; ai+1 = t; flag = 1; if ( !flag ) return; ,改进的冒泡排序（函数）：设标志flag，如果某趟未发生交换，flag=0，说明排序完成，返回。,13,将数组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”, ,14,冒泡排序算法的复杂度分析,最坏情形下扫描数据总数 n*(n+1)/2 最坏情形下数据交换的次数 n*(n-1)/2,15,选择法排序：把n个正整数按由小到大的顺序排序。,例,初始： 49 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,16,用选择法对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“, ,变量、数组长度定义,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交换,17,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; ,可否优化？如何优化？,18,选择排序算法的复杂度分析,最坏情形下扫描数据总数 n*(n+1)/2 最坏情形下数据交换的次数 n1次,19,直接插入排序,排序方法（以排杂志为例）： 1. 任取一本杂志，作为排好序的一叠杂志的开始情况； 2. 从剩余杂志中任取一本，根据月份把它插入排好序的那叠杂志里的正确位置，使插入后的这叠杂志仍有序； 3.如果还有未排好的杂志，就回到2，否则就结束；,20,a,t=8,t=77,t=66,t=55,21,void insertsort(int n, int a) /* 递增序直接插入排序 */ int i, j; int t; /*默认a0为已排好序*/ for( i = 1; i = 0 ,排序函数的定义：,t=55,a0,ai,ai-1,将t插入到a0到ai之间,22,插入排序的复杂度分析,最坏情形下数据移动的次数 n*(n-1)/2,23,例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 N; i+) scanf(“%d “, ,24,先检索中间的一个数据，如果不是所需的数据，则判断这要找的数在那一边，在所在的一边中再看中间的数是否为所需的数，依次下去。 只适用于已排好序的数列。,折半查找,10 17 20 22 31 44 51 55 68 73 89 95 120 133 137 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,折半查找最坏情形下的复杂度是O(lgn),25,折半查找程序,#include #define N 100 void f(int , int, int); void main() int aN, j, n, x; scanf(“%d”, ,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 = t ,26,例3 一维数组的应用（插入/删除） 将一个数插入一个有序的数列中，插入后数列仍然有序。an，有m个有序数(小-大），nm,算法：需插入x,3）插入x,1）找插入位置P,将ap到am依次后移一个位置,x=16,p,p = 0; while (x ap) /*小于或等于时插入*/,for (j = m-1; j = 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; ,27,例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-2a0依次后移一个位置； a0 =t; 3、输出数组a,28,字符数组预备知识,字符常量与字符串常量有什么区别？ 如何定义一个字符变量？,29,规定： 一个字符串书写时不能跨行 多个字符串之间仅由空白分隔，系统会将它们连成一个长字 符串。双引号需用转义符：“He said: “Im ok!“。,字符串以字符数组形式保存，存储形式是在所有字符后放0作为串结束标志。例 “Beijing“,0不是串内容，却是字符串表示不可缺的部分。 标准库的字符串处理函数都按这种表示设计，写字符串处理程序时也应该遵守这一规则。,30,6.4 字符数组与字符串,字符数组定义方式（与其他数组一样）： char line1000; 字符数组使用方式(与其他数组一样)： i=0; /* 注意越界控制 */ while(i1000 ,字符数组初始化方式一：逐个字符赋值 char city15=B,e,i,j,i,n,g; 未指定初值的元素自动设0，编码0的字符称为0字符/空字符，用0表示，在C中有特殊用途（字符串结束标志）。,31,若字符数组里存了一些字符后放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; 注意：字符数组的有效长度指第一个0前的字符个数+1,32,初始化方式二：用字符串常量 char a120 = “Peking University“; 未标元素个数时，数组大小确定为串长加1。例： char a3 = “Peking University“; 数组a3有18个字符元素。,字符数组变量中保存字符串后，可作字符串用。 例，若多个输出语句都用同样输出格式描述： char outform1 = ”point: (%f, %f)n“; . printf(outform1, x, y); . printf(outform1, s, t);,33,字符数组的赋值,将一个字符串赋值给一个字符数组,只能用在初始化的情况下,不能用在赋值语句中 例如: char str11; str = “I am happy”;是错误的.,34,字符串的输入输出,逐个字符I/O： %c 数组名下标 整个字符串I/O： %s 数组名,例 用%c main() char str5; int i; for (i = 0; i 5; i+) scanf(“%c”, ,例 用%s main() char str5; scanf(“%s”, str); printf(“%s”, str); ,输入用字符数组名,不要加& 输入串长度数组维数 遇空格或回车结束 自动加0,输出用字符数组名, 遇0结束,35,int main() int i; char a5; scanf(“%s“, a); for (i = 0; i 5; i+) printf(“%c“, ai); return 0; ,运行情况： （1）若输入 hel , 正常 （2）若输入 hell , 正常 （3）若输入 hello , 用%s 输出，会出现问题？,输入字符串长度数组维数,例子,36,#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); ,运行情况： 输入：How are you? 输出：a=How b=are c=you? 输入：How are you? 输出：a=How,scanf中%s输入时,遇空格或回车结束,运行情况： 输入：How are you?,字符串输入举例,37,void str_copy (char s, const char t) int i = 0; while (ti != 0) si = ti; +i; si = 0; ,循环结束时ti的空字符正好赋给si。 void str_copy (char s, const char t) int i = 0; while (si = ti) != 0) +i; ,字符串处理程序实例,例1，写函数将一字符串复制到一字符数组。假定数组足以存放被 复制串及空字符。,38,字符串处理函数的典型循环： for (i = 0; si != 0; +i) 用是否空字符确定对字符串的处理是否已完成。,例2，（二进制转换）写函数，给它一个表示二进制数的0/1字符串，它算出这个串表示的整数值。,二进制数bnbn-1.b2b1b0的值可以用下面公式计算： (.(bn2) +bn-1)2 +.)2 + b2)2 + b1)2 + b0 据此可写出循环，循环条件判断二进制数是否结束。 二进制数位只能是0/1，只需要在遇到1时加1。,39,int bin2int(const char s) int i = 0, n = 0; while(si!=0 ,由于数字字符的编码连续排列.函数改为： int bin2int(const char s) int i = 0, n = 0; while(si!=0 /* 这种写法可以推广到八进制和其他进制 */,40,例3 计算字符数组的有效长度,#include int strLen(const char s); int main() int len; char str10; scanf(“%s“, str); len = strLen(str); printf(“%dn“, len); printf(“%sn“, str); return 0; ,int strLen(const char s) int i=0; while(si!=0) i+; return (i+1); ,有问题吗？,41,包含在头文件 string.h,字符串输出函数puts 格式：puts(字符数组) 功能：向显示器输出字符串（输出完，换行） 说明：字符数组必须以0结束,字符串输入函数gets 格式：gets(字符数组) 功能：从键盘输入一以回车结束的字符串放入字符数组中， 并自动加0 说明：输入串长度应小于字符数组维数,标准库中常用的字符串处理函数,42,例 #include main( ) char string80; printf(“Input a string:”); gets(string); puts(string); 输入: How are you? 输出: How are you ?,scanf(“%s”,str); gets(str); 区别是scanf取不到空格,gets()函数是个过时的函数,43,标准库中常用的字符串处理函数,包含在头文件 string.h 字符串（实际）长度函数 strlen(const char s);,#include #include int main() char str10 = “China“; int n; printf(“Length=%dn“, strlen(str); n = strlen(str); printf(“n=%dn“, n); return 0; ,44,标准库中常用字符串处理函数,复制函数： strcpy(char s,const char t); t应为字符串，const说明参数值不修改。字符数组s应足够大，以保证复制不越界。例： char a116, a216; strcpy(a1, “programming“); strcpy(a2, a1);,限界复制函数strncpy，限制复制长度： strncpy(char s,const char t,int n); 将t中前n个字符复制到s中。,a1,45,#include #include int 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=%sn“, a); a = “Study“; printf(“a=%sn“, a); a = b; printf(“a=%sn“, a); return 0; ,程序查错,46,#include #include int 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; ,改正错误后,47,int strcmp(const char s1, const char s2) 两字符串相同时返回值0; s1大于s2的情况下返回大于0的值; 否则返回小于0的值。 判断字符串大小的标准是字符串的字