c语言程序设计13第十二讲(第六章上).ppt

1、1,编程就是不断编程！,2,高级语言程序设计,主讲教师：贾彩燕 计算机与信息技术学院 计算机科学与技术系 ,3,课程内容,第一章 程序设计和C语言 第二章 数据对象与计算 第三章 变量、函数和控制结构 第四章 基本程序设计技术 第五章 C程序结构（函数） 第六章 数组 第七章 指针 第八章 文件和输入输出 第九章 结构和其它数据机制 第十章 程序开发技术 第十一章 标准库,4,第六章 数组,5,语言需要提供一套数据机制，描述与数据有关的问题： 必须足够丰富，以满足需要； 不能过庞杂，臃肿难用； 也不能太低级，使描述过于烦琐。,高级语言的数据机制： 把数据分为类型，每个类型是一个数据集。 提供一

2、组基本数据类型；确定其书写方式；为各类型提供一组基本操作。 提供一组由简单数据类型或对象构造复合数据类型或对象的机制。,组合的数据对象称为复合数据对象。由所有“同类的”复合对象形成的类型称为复合数据类型，组成部分称为成分/成员/元素。,6,C 数据类型,由基本类型数据按一定规则组成的， 也称为“导出类型”,数组,7,问题:输入学生的学号,成绩, 计算平均成绩, 计算每个学生的成绩与平均成绩的差, 差=10 成绩等级 A 0=差10 成绩等级 B 其它 成绩等级 C 设:学号 double n1,n2,n3,n4, n30; 成绩 double s1,s2,s3,s4, s30;,能否:一个变量

3、名对应多个连续的存储单元:,数组,数组是程序中最常用的结构数据类型，用来描述由固定数目的同一类型的元素组成的数据结构,8,数组的概念、定义和使用 数组程序实例 数组作为函数参数 字符数组和字符串 两维和多维数组 编程实例,主要内容,9,6.1 数组的概念、定义和使用 数组（array）:是多个同类型数据对象的组合。 一个数组汇集了多个数据项，数组元素。 可从数组出发处理各元素，以统一方式处理一批/所有元素，是数组和一组独立变量的主要区别。,为此需要： 数组描述，数组变量定义，初值化 数组使用，包括通过数组变量使用其元素 数组实现，数组的存储方式,10,数组变量定义 定义数组变量（定义数组）时需

4、说明： 数组元素类型 数组（变量）名 数组（变量）的元素个数（也称数组大小或长度） 定义方式： 数据类型 数组名常量表达式；,例，定义两个数组： int a10; double a1100; 数组定义可以与其他变量定义写在一起，如： int a216, n, a325, m; 方括号内整型表达式说明元素个数，表达式应能静态确定值，可用字面量或枚举常量,11,可定义外部数组和局部数组，包括局部静态数组（用static）,作用域与存在期与简单变量相同。 数组的外部说明不必描述数组大小。例： extern int a; extern double a1;,下面函数里数组定义不合法： void f(i

5、nt m, int n) int bn; /*非法，编译时无法确定大小*/ . ,新 C99 标准支持这种定义，满足 C99 的编译器很少,12,基本操作是元素访问。元素顺序编号，首元素序号0，其余顺序编号。n元数组元素编号是0到n-1。定义： int b100; 元素编号为0、1、2、99。称为下标或指标。 元素访问通过运算符，优先级最高，运算对象是数组名和括号里表示下标的表达式。 表达式、语句里的 b3称为下标表达式或带下标的变量。,例：有上面定义后，可写： b0 = 1; b1 = 1; b2 = b0 + b1; b3 = b1 + b2;,数组的使用,13,数组的真正意义在于能以统一

6、方式描述对一组数据的处理。下标表达式可用一般的整型表达式。如： bi = bi-1 + bi-2; 访问哪个元素由i值确定。同一语句可访问不同元素，可用在循环里访问一批元素。,for (i = 0; i 100; +i) bi += a1i * a2i; /* 假设数组都有定义 */ 循环中涉及到300个基本数据对象。,14,#include int main () long fib30; int n; fib0 = 1; fib1 = 1; for (n = 2; n 30; +n) fibn = fibn-1 + fibn-2; for (n = 0; n 30; +n) printf(%

7、d, fibn); putchar(n%6 = 5 ? n : ); /* 6个数输出一行 */ return 0; ,例：写程序创建包含前30个Fibonacci数的数组，然后打印数组中所有的数。,15,对数组的多个或全部元素操作，常用for语句。 令循环变量遍历数组下标： for (n = 0; n 数组长度; +n) .,问题：fib是30个元素的数组，假设程序里写： for(n = 2; n = 30; +n) fibn = fibn-1 + fibn-2; 循环中试图访问fib30，实际无此元素。,用超范围的下标访问称为越界访问，是数组使用中最常见的错误。下标值超范围是运行中的问题。

8、,C不检查数组元素访问的合法性，运行中出现越界不会报错。超范围访问是严重错误，后果无法预料。,16,数组的实现 数组占据一片连续存储区，元素顺序排列，0号元素在最前面，各元素占相同空间。如有： int a8; a的存储恰好能存放8个整型数据，情况如图：,a至少相当于8个int变量，a0 a7可以看作“变量名”。保证元素排在一起，能以统一方式使用。,数组名表示内存首地址， 是地址常量,编译时分配连续内存 内存字节数=数组元素个数* sizeof(元素数据类型),17,在一些系统里越界访问可能导致动态错，系统强行终止出错的程序。越界可能破坏本程序的数据/程序本身/其他软件，甚至 是整个系统。 编程

9、者要保证数组下标值的合法性，保证不越界。,数组初始化 定义数组时可直接初始化。外部、局部静态或自动数组都可在定义时进行初始化。 方法一：定义时直接初始化 int b4 = 1, 1, 2, 3; double ax6 = 1.3, 2.24, 5.11, 8.37, 6.5; 初值表达式必须是常量表达式。,外部和静态数组在程序开始执行前建立并初始化，局部自动数组在程序执行进入相应函数或复合语句体时建立和初始化,18,这种写法只能用于数组初始化，不能用在语句里。 若定义时未初始化，外部和局部静态数组的元素自动初始化为0；自动数组处在不明确的状态。,方法二：只为部分元素提供初值，其余元素将自动置0

10、。初始化表元素个数不得超过数组元素个数。例： int b14 = 1, 2; b12、b13将给初值0。,方法三：若给了所有元素的初值，可以不写数组大小而只写方括号，元素个数由初值个数确定。例： int fib = 1,1,2,3,5,8,13,21,34,55; 这种写法能减少维护负担，有利于程序修改。,在语句中对数据元素赋值的方法？,19,说明： 数组必须先定义，后使用 只能逐个引用数组元素，不能一次引用整个数组 数组元素表示形式： 数组名下标 其中：下标可以是常量或整型表达式,/顺序输入输出数组元素 #include void main() int i, a10; for (i = 0;

11、 i 10; i+) ai = i; for (i = 0; i = 9; i+) printf(“%4d”, ai); ,/将数组元素逆序输出 #include void main() int i, a10; for (i = 0; i 10; i+) ai = i; for (i = 9; i = 0; i-) printf(“%4d”, ai); ,例一维数组的输入与输出。,20,数组的概念、定义和使用 数组程序实例 数组作为函数参数 字符数组和字符串 两维和多维数组 编程实例,主要内容,21,6.2 数组处理程序实例,从字符到下标（整数） 写程序统计由标准输入得到的文件中数字字符的个数

12、。,可定义10个计数变量，用if或switch区分情况，遇数字字符（isdigit）时对应计数器加1。不需要数组。,将字符看作整数可得到另一解法。常见字符集里数字顺序排列，ASCII字符集里0到9的编码是48到57。 利用这个事实，用10个元素的计数器数组可以更方便地完成对数字出现的统计。,22,int cs10; 用cs0记录0出现次数，余类推。若c是数字，对应计数器加1可以写成： +csc-0; /* c-0正是对应计数器的下标*/,#include #include int cs10 = 0,0,0,0,0,0,0,0,0,0; int main () int c, i; while (

13、c = getchar() != EOF) if (isdigit(c) +csc-0; for (i = 0; i 10; +i) printf(Digit %d: %dn, i, csi); return 0; ,23,例1 筛法求素数 筛法是求素数的著名方法：用空间换时间，1亿以内的素数只需要十几秒的时间(如不考虑输出) 具体算法：取2开始的整数序列： 令n等于2，它是素数； 划掉序列中所有n的倍数； 令n等于下一未划元素（它是素数），回到步骤2。,用数组表示整数序列，以元素下标表示对应整数。 数组an，an0代表0，ani代表i。 每个数只需表示划掉或未划掉，用0/1表示。 开始时元素

14、置1（即假设所有元素都是素数），而后不断将元素置0，直到确定了给定范围里的所有素数。,24,假设NUM是给定范围： /* 建数组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的倍数都不是素数*/,外层循环何时结束？可用NUM作为界限。,检验一个数是不是素数，只要看比它的平方根小的素数是不是能整除它 ，因此只要i超过NUM的平方根，就可以划掉到既定范围内的所有合数。,1 2 3 4 5 6

15、7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1不算 遍历一遍，划掉2的倍数：得2 3 5 7 9 11 13 15 17 19 21 23 25 遍历一遍，划掉3的倍数：得2 3 5 7 11 13 17 19 23 25 遍历一遍，划掉5的倍数：得2 3 5 7 11 13 17 19 23,25,#include enum NUM = 200 ; int anNUM+1; int main (void) int i, j; an0 = an1 = 0; /* 建立初始向量 */ for (i = 2; i = NUM; +i)

16、 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; ,26,例2：成绩分类 写程序输入一批学生成绩（200）。先输出不及格成绩，再输出及格成绩，最后输出不及格和及格的人数。,无法在输入过程中完成(除非输入两遍)。用数组记录学生成绩，输入记入数组，而后输出，可避免重复输入,数据装入数组后有许多可能处理方法。

17、 最简单的是两次扫描数组，第一次输出不及格成绩，第二次输出及格的成绩。 统计工作可在某次扫描中完成（也可在输入中完成），两部分人数之和就是总人数，统计一部分就够了。,27,enum NUM = 200 ; const double PASS = 60.0; double scoresNUM; int main() int i, n = 0, fail; while(n= PASS) printf(%fn, scoresi); printf(Fail:%dnPass:%dn,fail, n-fail); return 0; ,28,例3 多项式求值 设数组p中存放下列多项式的系数， 其中pi存放

18、 写程序求p表示的多项式在指定点的值。,方法1：求出各项值累加。假设指定点值存于x： for (sum = 0.0, n = 0; n TERMS; +n) for (t = pn, i = 1; i = n; +i) t *= x; sum += t; ,循环体内可以改写为（先算x的幂）： for (t = 1.0, i = 1; i = n; +i) t *= x; sum += t * pn; 可发现有大量重复计算。,29,通过保存前次的t值： for(sum = 0.0, t = 1.0, n = 0; n TERMS; +n) sum += t * pn; t *= x; ,方法2：

19、多项式可以变形为Horner范式：,按照这个公式，求值循环可写为： for (sum = 0.0, n = TERMS-1;n = 0; -n) sum = sum * x + pn;,从计算量上比较它们：需要多少次加法，多少次乘法。,30,定义数组的问题,如果数组表示的是全局数据集合，需要在多个函数里使用，那么可考虑定义为外部数组。 大的数组应定义为外部，以免占大量运行栈空间。一般系统不允许在函数内定义特别大的数组。 若数组保存着递归定义函数的局部数据，就必须定义为自动数组。因为递归调用时需要数组的多份拷贝。 其他情况可以根据需要自由选择。,31,数组的概念、定义和使用 数组程序实例 数组作

20、为函数参数 字符数组和字符串 两维和多维数组 编程实例,主要内容,32,6.3 数组作为函数参数,数组可以作为函数的参数，但是在向函数传递数组时通常有两种方法：即： “地址”的传递 “值”的传递,33,方法一： 用数组名作为实际参数，给函数传递数组的地址，通过这个地址就可以访问到数组的元素了双向传递。,#include #define N 20 void f(int b , int n , int m) int i; for (i = m; i = n; i-) bi+1 = bi; void main() int i, aN = 1,2,3,4,5,6,7,8,9,10; f(a, 2, 9

21、); for (i = 0; i 5; i+) printf(“%4d”, ai); ,b,10,7,6,4,12334,34,方法二： 用数组元素作为实际参数，是一种传值的方式，即：调用函数时要复制数据 单向传递。,#include int fmax(int x, int y) return (x y ? x : y ) ; ,void main() int a10, j, max ; for (j = 0; j = 9; j+) scanf(“%d”, ,35,对函数参数的小结：,“值”传递,形参和实参都是普通变量,实参是数组元素，形参是普通变量,“地址”传递：形参、实参都是数组名，完成双

22、向传递。,完成单向传递,36,假设有多个数组都需要求平均值? 解决方法：定义以数组为参数的函数。 以数组为参数，不同调用可以完成对不同数组的计算。 定义以double类型的数组为参数求元素平均值的函数，就可解决所有double数组的平均值问题,设常量LEN是被处理数组的长度。 double avg0(double a) double x = 0.0; int i; for (i=0; iLEN; +i) x+= ai; return x / LEN; /*注意：数组形参不需要写数组大小 */,37,若数组a1长LEN，可用： x = avg0(a1); avg0有一定通用性，若数组a2长度也是

23、LEN： y = avg0(a2); 用符号常量指定数组大小可解决许多问题。,缺点：若数组长度不是LEN，就不能用avg0处理。 可见：avg0不够通用，只能正确处理长为LEN的数组。,参数是使函数能处理一类问题的基本机制。 为提高数组处理函数的通用性，定义时应引进长度参数，使函数能处理任何给定长度的数组。,38,改造后的函数： double avg (int len, double a) double x = 0.0; int i; for (i = 0; i len; +i) x += ai; return x / len; 对调用提出的新要求：必须正确提供数组长度。,应用实例： int

24、main () double b1=1.2, 2.43, 1.74, b2=6.5, 9.2, 8.6, 4.5, 0.3; printf(%f, %fn,avg(3, b1),avg(5, b2); return 0; ,39,长度参数提高了函数的通用性。 但使用时必须关注越界问题。avg(5, b1)引起数组越界（b1有3个元素）。 长度实参可小于数组大小，avg(3, b2)求b2前3个元素的平均值。可将数组前段当作数组使用。,40,例4：将a数组的内容按颠倒的次序重放，在操作时，只能借助一个临时存储单元而不能另外开辟数组。,偶数个元素,奇数个元素,41,void rev(int n,

25、int a) int x, i, m = n/2; for (i = 0; i m; +i) x = ai; ai = an - i - 1; an - i - 1 = x; 自己添加主程序,另一写法： for (i = 0, j = n-1; i j; +i, -j) x = ai; ai = aj; aj = x; ,42,数组的概念、定义和使用 数组程序实例 数组作为函数参数 字符数组和字符串 两维和多维数组 编程实例,主要内容,一维数值型数组的重要应用,43,一维数组上的重要操作,排序 查找 插入 删除 元素交换,44,将计算机学院08级学生按平均分高低排序 将08的奥运会各参赛国按英

26、文字典序排序 搜索引擎网页排序(PageRank)learning to rank 排序问题无处不在,例1一维数组的应用（排序）,45,常用的排序算法,冒泡排序 选择排序 插入排序 快速排序 ,46,冒泡排序法 输入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,47,用冒泡法对10个数进行排序（N-S图及程序）,变量、数组长度定

27、义,for(j=0;j=N-i-1;j+),scanf ( “%d” , 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

28、+) printf(%6d, ai); printf(n); ,48,问题,输入十个正整数，把这十个正整数按由大到小的顺序排序，如何修改程序？课后作业 n值如果是可变的? 如果只对部分数据进行排序？ 某趟循环未发生交换，后面可不再循环， 如何改进冒泡排序?,49,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，说明排序完成，返回。,50,将数组a中的前5个数进行排序,#include void