第八讲(1) 数组进阶

1、1第八讲 数组及基本数据集合处理2数组的重要意义n例，对一批数据做相同的处理nint b100, a1100, a2100;for (i = 0; i 100; +i) bi += a1i * a2i;n实现以统一的方式描述一组数据n为方便地对一组同类型数据实现统一的数据处理奠定基础。该程序代码包含:1.数组变量定义2.数组元素的赋值3.数组元素的使用3一、一维数组41. 数组概念n数组(array),如int a10, b10等n多个同类型数据对象的组合。n一个数组代表一组类型相同的、顺序在内存排列的数据集合。n定义一个数组变量，如int a10，意味着：n定义了一个数组变量a,能够存储10

2、个整型数据n这10个整型数据在内存中连续存储n使用数组a中元素的访问方式是ai (0=i10)a0 a1a2 a8 a9 第一个元素第10个元素5数组定义相关说明n数组变量定义，如int a216, n, a325, m;n需要指出数组元素的类型n需要给出每一维的大小n定义数组变量时，方括号内的整型表达式说明元素个数，表达式应能静态确定值，可用文字量或枚举常量n如下数组定义不合法void f(int m, int n) int bn; .为什么不合法？因为编译时无法确定n的值。6其它说明n数组与其他变量一样可以定义在函数的内部或外部，也可以定义静态数组变量(static)。n数组变量作用域与存

3、在期规则与简单变量相同。n数组的存在(引用)声明可以不必描述数组大小。n例，设Exam1.cpp中有外部数组定义nint a100;ndouble a150;n若在Exam. cpp中要使用，则可按如下方式给出存在声明nextern int a;nextern double a1;nC规定，数组的名称代表数组的起始地址值。n若有定义: int narr10;n则，narr代表整个数组的起始地址。n取各数组元素地址采用&narri的形式进行7数组名就是指针n数组名与指针的异同点n数组名只不过是指向第一个数组元素的指针。n数组名不是一般的指针变量，是一个指针常量。valsvals的值不能修

4、改！即不能出现1.vals=&b;2.char str10; str=BJTU;void reverseInput()int ch10;int chRev10;const int ciLen=10;int i=0;while (iciLen)&(chi=getchar()!=EOF) /注意该条件。if (isupper(chi) /大写转换成小写。chi=tolower(chi);else if (islower(chi)chi=toupper(chi);chRevciLen-i-1=chi; /逆序存储。i+;fprintf(stdout,The reversed stri

5、ng is:n);for (int j=0;jciLen;j+) /注意结束条件。putchar(chRevj);printf(nThe end.n);功能：对从标准输入获得的10个字符进行大小写转换并逆序输出。要形成如下习惯：数组元素的赋值与取值一般通过循环结构进行。建立包含前30个Fibonacci数的数组，然后从大到小打印数组中的数#include enum NUM=30;int main()long fibNUM;int i;fib0=1;fib1=1;for(i=2;i=0;-i) printf(“%d”,fibi); putchar(i%6=5?n: );两个for循环和数组结合非

6、常方便的完成大部分任务！102. 数组元素操作及越界问题n对数组的多个或全部元素操作(赋值与取值)，常用for语句n令变量遍历数组下标nfor (n = 0; n 数组长度; +n) .n在循环体内对数组元素逐个访问n对前例程序， ch是10个元素的数组，若假设程序里写： for(i = 1; i = 10; +i) chRevciLen-i-1 =chi;n当i为10时，循环中试图完成如下计算nchRev-1 =ch10;数组越界！11越界n用超出范围0, n - 1的下标访问数组称为数组的越界访问，是数组使用中最常见的错误。n下标值超范围是运行过程中才会出现的问题，不属语法问题。nC不检查

7、数组元素访问的合法性，即编译时对运行中可能会出现访问越界不会报语法错。超范围访问是严重错误，后果无法预料。n在数组使用中，编程者要保证不使用比所定义的更多的元素，从而保证不越界。123. 数组的初始化n定义数组时可直接初始化。外部、内部静态或自动数组都可在定义时进行初始化。n定义时初始化的例子nint b4 = 1, 1, 2, 3;ndouble ax6 = 1.3, 2.24, 5.11, 8.37, 6.5; n注意：这种写法只能用于数组初始化，不能用在其他语句里。n初始化规则n初值表达式必须是常量表达式。对自动数组也一样。n若定义时未初始化，外部和局部静态数组的元素自动初始化为0；n自

8、动数组不自动初始化。13其它初始化方式n可只为部分元素提供初值，其余元素将自动置0。n初始化元素个数不得超过数组元素个数。n例nint b14 = 1, 2;nb12、b13将给初值0。n若给了所有元素的初值，可以不写数组大小而只写方括号，元素个数由初值个数确定。n例nint fib = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55;相当于定义了int fib10,并进行了初始化。4.数组的赋值与取值原则n使用数组的最基本方式是访问其元素，使用下标运算符(优先级最高)，如ai, bj等。n两种典型错误赋值方法14(1)给一个数组元素赋一组值 如 int a5; a5=1,2

9、,3,4,5;(2)一个数组给另一个数组初始化或者赋值 如 int a5=1,2,3,4,5; int b5=a;必须掌握的数组使用原则：逐个元素进行访问或赋值！155. 数组的存储实现n数组占据一片连续存储区，元素顺序排列，0号元素在最前面，各元素占相同大小的空间。如有：nint a8;na的存储空间恰好能存放8个整型数据a相当于8个int变量，a0 a7可以看作变量名。保证元素排在一起，能以统一方式使用。a0 a1a2 a3 a4 a5 a6 a7 16二、数组处理程序实例17例1 从字符到下标n写程序统计文件中各个数字字符出现的个数。n解决方法1n不用数组，定义10个计数变量，用if或s

10、witch区分情况，遇数字字符（isdigit）时对应计数器加1。n解决方法2n将字符看作整数nASCII字符集里0到9的编码是48到57。n利用这个事实，定义一个数组保存计数结果。n对于每一个数字字符c，用c 0计算该字符对应计数结果的下标。n如：5 0 等价于 53 48518#include #include int main () int cs10=0, 0, 0, 0, 0, 0, 0, 0, 0, 0; int c, i; while (c = getchar() != EOF) if (isdigit(c) +csc - 0; for (i = 0; i 10; +i) prin

11、tf(Digit %d: %dn, i, csi); return 0;计数数组，对应于09共10个字符，记录该10个字符的计数结果。注意计算下标的方法19例2 筛法求素数n有求素数的著名方法，具体算法如下取2开始的整数序列；1. 令n等于2，它是素数；2. 划掉序列中所有n的倍数；3. 令n等于下一未划元素(肯定是素数)，回到步骤2。n用数组表示整数序列中的各个整数是否为素数，以元素下标表示对应整数。n定义数组an，ani代表整数i的状态, 用0/1表示表示划掉或未划掉。n筛选过程n开始时所有元素置1，而后不断将元素置0，直到确定了给定范围里的所有素数。20算法伪代码假设NUM是给定范围的最

12、大数建立数组an，所有元素初始化1将an0和an1置0(表明它们不是素数，划去)for (int i = 2; i值不大于某个数; +i) if (ani = 1) / i是素数 for (int j = i * 2; j NUM; j += i) anj = 0; /*i的倍数都不是素数，划去*/ 外层循环何时结束？1. 可用NUM作为界限。2. 仔细分析不难发现，只要i超过NUM的平方根，就可以确定既定范围内的所有合数。#include enum NUM = 200 ; /设定问题规模设定问题规模int main (void) int anNUM+1; int i, j; an0 = an

13、1 = 0; /* 划去划去 0，1*/ for (i = 2; i = NUM; +i) ani = 1;/初始化其余元素初始化其余元素 for (i = 2; i * i = NUM; +i) if (ani = 1) /跳过所有合数，找到下一个素数跳过所有合数，找到下一个素数 for (j = i * 2; j = NUM; j += i) anj = 0; /划去当前素数的倍数划去当前素数的倍数 for (i = 2, j = 0; i = NUM; +i)/输出输出 if (ani != 0) printf(%d ,i); putchar(n); return 0;22例3 成绩分类

14、n写程序实现如下功能n输入一批学生成绩（200）。n输出所有不及格成绩n再输出所有及格成绩n最后输出不及格和及格的人数。n经分析发现，不及格与及格成绩分类输出功能无法在输入过程中同时完成(除非输入两遍)，因此需要用数组保存输入数据，用于两次处理。23解决方案n用数组记录所录入的学生成绩，而后再输出，可避免重复输入。n数据装入数组后有许多可能处理方法。n最简单的是两次扫描数组，第一次输出不及格成绩，第二次输出及格的成绩。n统计人数的工作可在某次扫描中完成(也可在输入中完成)，两部分人数之和就是总人数，统计一部分就够了。enum NUM = 200 ;const double PASS = 60.

15、0;double scoresNUM;int main () int i, n = 0, fail; while(n NUM & scanf(%lf,&scoresn) = 1) +n; /*输入输入n个数，输入时需要判断不越界个数，输入时需要判断不越界*/ for (fail = 0, i = 0; i n; +i) if (scoresi PASS)/输出不及格成绩及统计不及格人数输出不及格成绩及统计不及格人数 printf(%fn, scoresi); +fail; for (i = 0; i = PASS) printf(%fn, scoresi); /输出统计结果输出

16、统计结果 printf(Fail:%dnPass:%dn,fail, n-fail); return 0;记住这个循环条件25定义数组的常见策略n使用数组的情况一般为：n需要多次处理同一批同类型数据n多次处理一批文件中的数据，重复读文件影响效率。n如果数组中存储的是全局数据集合，需要在多个函数里使用，那么可考虑定义为外部数组。n大的数组应定义为外部数组，以免占用大量运行栈空间。一般系统不允许在函数内定义特别大的数组。 n递归函数的局部数组，一般应定义为自动数组。因为递归调用时需要数组的多份拷贝。 26三、数组与函数参数C语言函数参数表中的数组参数其实是指针参数，写成数组只是为了提示调用者:传给

17、函数的应该是一段给定长度的元素类型相同的连续存储空间的首地址。27例，求若干个数的平均值n求平均值，而且有多个不同数组都需要求平均值。n解决方法n定义以数组为参数的函数。n以数组为参数，处理整个数组不再是问题。n不同的实参与调用可以完成对不同数组的计算n定义以double数组为参数，求元素平均值的函数，就可解决所有double数组的平均值问题28代码设常量LEN是被处理数组的长度。 double avg0(double a) double x = 0.0; int i; for (i = 0; i LEN; +i) x += ai; return x / LEN; 注意：数组形参的内不需要写数

18、组大小，写了也没用，为什么？因为仅是一个地址，相当于double avg0(double *a)29函数复用及长度参数的引入n该函数具有一定的通用性，能求所有长度为LEN的double型数组的平均值，如n若数组int a1LEN，int a2LEN长都为LEN，以下调用都可行nx = avg0(a1);ny = avg0(a2);n缺点：不够通用n只能处理长度为LEN的double型数组，若数组长度不是LEN，元素数据类型不是double，都不能用avg0处理。n参数是使函数能处理一类问题的基本机制。n为提高数组处理函数的通用性，定义时可以引进长度参数，使函数能处理任何给定长度的double型

19、数组。30改造后的函数double avg (double a, int nLen) double x = 0.0; int i; for (i = 0; i nLen; +i) x += ai; return x / nLen;n对调用提出的新要求：必须正确提供数组长度。n将缓冲区长度提供给处理缓冲区中的数据的函数一般情况是必须要做的工作。31上述函数的调用实例int main () double b1 = 1.2, 2.43, 1.74, b2 = 6.5, 9.2, 8.6, 4.5, 0.3; printf(“%f, %fn”, avg(b1, 3), avg(b2, 5); retu

20、rn 0;n长度参数提高了函数的通用性。但使用时必须关注越界问题。n调用avg(b1, 5)会带来什么问题？n长度实参可小于数组大小，可将数组前段当作数组使用，如navg(b2, 3)，求b2前3个元素的平均值。32函数与数组数据修改n回忆参数机制n函数参数都是值参数n形参是函数体的内部变量。n调用时将实参的值拷贝送给形参。n数组作为函数的参数时，在调用的过程同样完全遵循这个机制。n以数组形式定义函数的某个参数等于定义一个指针参数，这个参数将存放某段空间的起始地址，如数组的首地址。n如果传来的参数是某个数组的首地址，在函数内就可以通过这个首地址修改数组每个元素的值33例设有函数定义void f

21、unc(int narr,int nLen) for (i = 0; i nLen; i+)narri+;return;设有调用代码 int b5 = 1, 2, 3, 4, 5;func(b, 5);实际效果: 将数组b中的每个元素都加了1真正的原因：C并不把narr这个参数看成是一个真正的数组，narr实际上被作为一个指针参数。指针参数中能存放的是某种类型存储空间的地址。0 x0012ff58narr5nLen该操作实际为narr指针指向的变量进行加1处理。例，将数组的内容按颠倒的次序重放，在操作时，只能借助一个临时存储单元而不能另外开辟数组。 互换偶数个元素不动奇数个元素互换01n-2n

22、-1in-i-135程序代码(两种方式)void rev1(int n, int a) int x, i, m = n / 2; for (i = 0; i m; +i) x = ai; ai = an - i - 1; an - i - 1 = x; void rev2(int n, int a) int i, j, x; for (i = 0, j = n-1; i j; +i, -j) x = ai; ai = aj; aj = x; 36四、字符数组与字符串C语言常用于写文字处理程序，文字信息以字符形式存在字符数组里。对字符数组有一些特殊机制。371. 字符数组n字符数组定义方式(与其

23、他数组一样)nchar szLine1000;n使用方式与其他数组一样n例，录入一行字符存入该数组i=0; /* 注意越界控制 */while (i1000 & (linei=getchar()!=n) +i;n定义时的初始化方法：nchar city15=B,e,i,j,i,n,g;n未指定初值的元素自动设0，编码0的字符称为0字符或空字符，用0表示，在C中有特殊用途。382. 字符串n用双引号括起来的任意字符序列，也叫“字符串字面量”。n注意内容n一对双引号内的字符串不能跨行n如果顺序写出的两个字符串仅由空白字符分隔，编译程序就会把它们连成一个长字符串。n因此，需要写跨行的长字符串

24、时，每行的字符串都需要写一对双引号。n在字符串中不能直接写出的字符可以采用换意序列表示，如n ” t n r nHe said: Im ok!39例子如下int main()char chWrong=GoodBad; /It is wrong!char chArr=you are right!This is a kind of c string permitted format!;printf(Hello World! He said: Im ok!n);printf(%sn,chArr);return 0;40字符串的内部表示n字符串以字符数组形式保存，存储形式是在所有字符后放0作为串结束标

25、志。例 Beijing B e i j i n g 0 字符串Beijing的内部表示 注意最后的0413. 字符数组与字符串n问题n能在定义的字符数组变量里存放字符串吗？n当然可以！n若字符数组里存了一些字符后放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;都可以作字符串使用printf(“%sn%sn%sn%sn%sn”, a,b, c,d,x);执行结果goodisaokokisnot烫蘯k42关于 0n由于字符

26、串长短不同，C将0作为字符串结束标志，以便于程序识别字符串的结束。n以空字符(不是空白字符)作为结束标志，程序可以通过其内部表示确定串结束。n0不是串内容，却是字符串表示不可缺的部分。n0作为字符串的结束标志是C的标准n字符数组并不要求它的最后一个字符必定为0，因此只是要以字符串来处理字符数组时，要求字符数组必须包含0.434. 采用字符串进行字符数组初始化n可用字符串指定字符数组的初值nchar a15 = BJTU;n未标元素个数时，数组大小确定为字符串长加1。例：nchar a2 = BJTU;n数组a2有5个字符元素，因为除了四个字母之外，还有末尾的0需要存储。445. 字符数组用作字

27、符串n字符数组变量中保存字符串后，可作字符串用。n例，若多个输出语句都用同样输出格式描述，则可以进行如下类似处理。nchar outform = point: (%f, %f)n;n.nprintf(outform, x, y);n.nprintf(outform, s, t);1.定义字符数组，存储格式描述串2. 把字符数组当字符串使用456.字符串处理程序实例n例，写函数将一个字符串复制到字符数组中。假定目标数组足以存放被复制串及空字符。void str_copy (char s, char t) int i = 0; while (ti != 0) /结束条件为碰到结束符为止 si =

28、ti; /复制 +i; si = 0; /最后加一个结束标志把t复制到s46另外一个写法另外一个写法void str_copy (char s, char t) int i = 0; while (si = ti) != 0) +i;/当ti为0时，赋值完成后，循环结束n字符串处理函数的典型循环：for (i = 0; si != 0; +i) n一般通过判断当前字符是否为空字符来判断对整个字符串的处理是否已完成。47五、 标准库的字符串处理函数要求的头文件:gets, puts(214230页): stdio.h其他函数(第11章295-299页): string.h48常见函数n求字符串长

29、度nsize_t strlen( const char *string );n获得字符串string的长度，不包括0n字符串复制函数nchar *strcpy( char *strDestination, const char *strSource );nstrSource应为字符串，const说明参数值不能修改。字符数组strDestination应足够大，以保证复制不越界。例：n限界复制函数strncpy，限制复制长度：nstrncpy(char s,const char t,int n);49字符串比较函数nint strcmp( const char *string1, const c

30、har *string2 );n返回值返回值n返回两个字符串间的字典序大小关系n返回值与返回值与string1, string2之间的关系之间的关系n 0 string1 大于 string2n如如 strcmp(“abc”,”bcd”) 返回值是返回值是-1.50其它常见函数nint puts( const char *string ); n输出字符串string到标准输出。nchar *gets( char *buffer ); n读字符串，从标准输入读一行字符到buffer,并返回指针。nchar *strcat( char *strDestination, const char *st

31、rSource );n字符串连接，把strSource连接到strDestination末尾。nchar *strlwr( char *string );n把指定字符串全部转换成小写nchar *strupr( char *string );n把指定字符串全部转换成大写51六、二维与多维数组521. 两维和多维数组n一维数组有一个下标，元素线性排列。n表示成组的数据n实际中需要更复杂的结构，如矩阵，因此也需要有一定的机制来表示这些结构。n可以定义两维、多维数组。两维数组也可以看作是一维数组，其中每个元素是一个一维数组，元素的成员类型、成员个数都相同。n多维数组的定义形式ndouble a32;

32、nint b44;nint a1324; /* 三维数组 */532. 二维数组的初始化nint a32 = 1, 2, 3, 4, 5, 6;n内嵌括号初始化成员数组，其元素个数不能超过成员数组长度，组数不超过成员数组个数。不足时自动置0。n也可不写内嵌括号(前一方式更清晰)：nint a32 = 1, 2, 3, 4, 5, 6;n初始值按顺序赋给基本成分，不够时置0。n若初始化给出了全部元素值，第一下标的元素个数可以不写(可根据初始化表示算出)。nint a2 = 1,2,3,4,5,6;nint b2 = 1, 2, 3, 4, 5, 6;nchar color16=RED,GREEN

33、,BLUE;543. 二维数组的表示和使用n设有数组定义 double a32; int b44;na表示整个数组，a0、a1和a2表示数组a的三个成员数组。它们可以被当成普通一维数组一样使用。n因此，a01表示a的下标为0的成员数组a0中下标为1的元素。n例 二维数组的元素访问方式a21 = a01 + a11;for (i = 0; i 4; +i) for (j = 0; j 4; +j) bij = i + j;554. 二维数组在内存中的排列方式nC在内存中排放数组的原则n一维数组元素连续存放n多维数组同样依次存放成员数组。n成员数组按同样方式表示。nC的数组存放方式，一行(成员数组

34、)元素连续存，这种形式又称按行方式或行优先方式。56行优先顺序与内存中的排列a00a01a02a03a10a11a12a13a20a21a22a23int a34;a00a01a02a03a10a11a12a13a20a21a22a23 0 1 2 3 4 5 6 7 11按照行优先顺序在内存中存储a的开始位置也是其首成员a0的开始位置，也是a0首成员a00的位置。57例，矩阵乘enum N = 5;double ANN, BNN, CNN;for(i = 0; i N; +i) for(j = 0; j N; +j) x = 0.0; for(k = 0; k N; +k) x += Aik

35、 * Bkj; Cij = x; 写程序段求出由二维数组A、B表示的55矩阵的乘积，存入二维数组C(设A，B已有值)并输出。nkkjikijbac1585. 多维数组作为函数的参数n如果需要定义能够处理多维数组的函数，则需要将多维数组作为函数的参数；n作为函数参数时不必给出最左一维长度，但要求给出除最左一维外其他各维的长度。n一般情况下，用多维数组作为函数的参数并不是一个好的做法。59例，二维数组参数n求出n5数组中数据均值(n是参数，表示最左维长度)double aavg (int n, double a5) int i, j; double sum = 0.0; for (i = 0; i

36、 n; +i) for (j = 0; j 5; +j) sum += aij; return sum / (5 * n);n可用于任何n5的数组，但不能用于其它尺寸的数组，如47的数组60七、数组编程实例61成绩直方图n文件里保存着一批学生成绩，写程序读入这些成绩，产生其平均值M和标准差S，并做直方图。有定义：MNxiiN11SNxMiiN21211()62问题分析n程序中需要反复使用这批数据，应存入数组。n程序工作比较多，考虑将主要工作划分为若干函数。n用一个双精度数组保存所有成绩，作为基本数据。n在最高层可将程序工作分为三步（第一层分解）1) 输入2) 计算并输出统计量3) 计算并输出直

37、方图63基本数据说明与函数原型1.常量与变量enum NUM = 200, HISTOHIGH = 60 ;double scoresNUM; /存放成绩的缓冲区2.函数int readscores(int lim, double tb); /读入成绩void statistics(int num, double tb); /统计void histogram(int num, double tb, int high); /输出64主程序int main(void) /读入成绩 int n = readscores(NUM, scores); /统计 statistics(n, scores);

38、 /输出直方图 histogram(n, scores, HISTOHIGH); return 0;65基本输入功能实现/limit，要求读入的数据项数/tb，存放数据用的缓冲区的地址/返回值：实际成功读入的数据项数int readscores(int limit, double tb) int i = 0; while(i limit & scanf(%lf, &tbi) = 1) +i; return i;66void statistics(int n, double tb) int i; double s, sum, avr; if (n 2) printf(Data t

39、oo few.n); return; for (sum = 0.0, i = 0; i n; +i) /求和求和 sum += tbi; avr = sum / n; /求平均求平均 for (sum = 0.0, i = 0; i n; +i) sum += (tbi - avr) * (tbi - avr); s = sqrt(sum / (n - 1); /求标准差求标准差 printf(Total students: %dn, n); printf(Average score: %fn, avr); printf(Std deviation: %fnn, s);项数小于2时会出现问题求

40、统计量i=1.n(xi - M)267直方图生成n每个成绩段输出一组字符，选H作为基本字符。为描述方便，定义一个字符序列输出函数： void prtHH(int n) /n为期望输出的字符个数 int i; for(i = 0; i n; +i) putchar(H);n分段长度可用符号常量表示，根据它可算出分段数。定义两个常量，利用它们之间的关系：enum SEGLEN = 5, /5分一段 HISTONUM = (100 / SEGLEN) + 1 /分数段数目;68分段成绩数统计：用数组保存各分段成绩人数，将数组命名为segs，其中应有HISTONUM个计数器。处理的是等长分段，存在从成

41、绩得到计数器下标的简便方法。对scores的元素正确更新相应计数器：segs(int)scoresi) / SEGLEN+;将成绩强制转到int后除以分段长度得到计数器下标。 下面考虑用如下形式输出直方图行： 80: 23|HHHHHHHHHHHHHH 为使直方图规范化(最长行HISTOHIGH个字符)，还要求出最长行的长度。69void histogram(int n, double tb, int high) int i, mx, int segsHISTONUM; if (n = 0) return; for (i = 0; i HISTONUM; +i) /初始化 segsi = 0;

42、 for (i = 0; i n; +i) / 统计分段人数 segs(int)tbi / SEGLEN+; for (mx = 1, i = 0; i mx) mx = segsi; for (i = 0; i HISTONUM; +i) / 输出 printf(%3d: %4d|, (i + 1) * SEGLEN, segsi); prtHH(segsi * high / mx); putchar(n); 70存在的问题和改进n若文件中都是0到100的数值，程序能得到正确结果。出现不法数据呢？如混入一个178，程序会怎么样？n实际软件应对用户的输入数据进行合法性判断，确保不让脏数据进入到程序中。这是一项非常烦琐却又是保证软件健康的基本手段。n程序抵御不