C语言 第6章 1、一维数组).ppt

1、1,1,构造数据类型,第六章,例题：求10个数的平均数,5,5,主要内容,数组概述 一维数组 二维数组 字符数组 结构体类型,6,6,float、int、 char等都是简单类型。 简单类型变量的特点是一个变量描述一个数据。 构造数据类型变量描述的是一组数据。 一个构造类型变量包含若干个简单数据类型或若干个构造类型的数据。,1、数组概述,7,7,数组是一种构造数据类型。 数组由若干个同类型的数据元素连续排列而成。 一个数组类型的变量值, 按数组元素的顺序存放在内存中一片连续的内存单元中。 每个数组元素占据一个独立的空间。,8,8,按数组元素的类型不同，数组又可分为： 数值数组 字符数组 指针数

2、组 结构数组等,1、数组概述,9,9,数组在内存中的存放,例：A5（A为有5个元素的数组变量）,第1个数组元素,第5个数组元素,数组名表示内存首地址， 是地址常量,下标从0开始,编译时分配连续内存,10,10,对数组的操作：,定义数组变量; 引用数组中的元素; 对数组进行初始化-为数组元素赋初值; 数组型变量的输入和输出;,11,11,格式： 基本类型 数组名数组元素的个数;,1、定义数组类型的变量：,每一个数组元素的类型,数组变量名,12,12,定义数组变量时考虑的因素：,数组元素的类型;（基本类型） 数组变量名称; 数组的维数; 每一维数组元素的个数;,13,13,定义数组变量时考虑的因素

3、：,例： int a10; char ch20; float b56;,一维数组,二维数组,14,14,对数组的操作：,定义数组变量; 引用数组中的元素; 对数组进行初始化-为数组元素赋初值; 数组型变量的输入和输出;,15,15,2、引用数组中的元素,格式：数组名下标1下标2下标n; 考虑因素： 引用哪一个数组数组名; 数组元素在数组中的位置数组下标;,16,16,2、引用数组中的元素,例： int a10; char ch20; float b56;,a3,chi,b23,定义,引用,17,17,主要内容,数组概述 一维数组 二维数组 字符数组 结构体类型,18,18,一、定义一维数组变量

4、 二、引用一维数组变量的元素 三、初始化一维数组变量 四、对数组进行输入和输出 五、应用举例,2、一维数组,定义,例：,格式： 类型说明符 数组名常量表达式;,int a5;,char c20;,float x10;,定义一个数组元素为整型的, 包含五个数组元素的一维数组,定义一个数组元素为字符型的, 包含20个数组元素的一维数组,定义一个数组元素为浮点型的, 包含10个数组元素的一维数组,决定数组元素的类型,用户为数组起的名字,决定数组元素个数,20,20,例：,int a10;,char c20;,float x9;,定义一个数组元素为实型的, 包含9 个数组元素的一维数组,定义一个数组元

5、素为字符型的, 包含 20 个数组元素的一维数组,定义一个数组元素为整型的, 包含10 个数组元素的一维数组,21,说明：,1.数组名定名规则和变量名相同，遵循标识符定名规则。 2.在定义数组时，需要指定数组中元素的个数，方括弧中的常量表达式用来表示元素的个数，即数组长度。 3.常量表达式中可以包括常量和符号常量，但不能包含变量。也就是说，C语言不允许对数组的大小作动态定义，即数组的大小不依赖于程序运行过程中变量的值。,22,22,二、引用一维数组变量的数组元素,原则： 数组型变量必须先定义, 后使用。 只能逐个引用数组元素, 不能直接引用整个数组型变量。 数组下标从 0 开始。,a0,a1,

6、a2,例如, 定义数组a: int a3, 数组元素为：,23,23,二、引用一维数组变量的数组元素,原则： 数组型变量必须先定义, 后使用。 只能逐个引用数组元素, 不能直接引用整个数组型变量。 数组下标从 0 开始。,a0,a1,a2,例如, 定义数组a: int a3, 数组元素为：,对数组变量的处理只能一个数组元素一个数组元素地处理,24,24,二、引用形式：,例如：,数组名下标,a2 = 1;,i = 1;j = 2; k = 3; ai+j = bk;,a2,25,注意： 定义数组时用到的“数组名常量表达式” 和引用数组元素时用到的“数组名下标” 是有区别的。 例如 int a10

7、; t=a6;,26,26,使用数组编程:,步骤：,定义数组; 对数组进行初始化; 引用数组, 对数组进行相应的操作; 对结果数组进行输出;,例. 使用数组编程, 计算出前10项 fibonacci 数列, 要求一行打印5个数。,怎么做？,27,27,例： 计算出 fibonacci 数列前 10 项 , 要求一行打印5个数。,目标1：使用数组存放这10个数;,目标2：输出时, 一行打印5个数,定义整型数组f：int f10,输出fi, i：09 输出5个数换一次行。,28,28,f1 ：第二项, 为1;,f0 ：第一项, 为0;,f0 = 1;,f1 = 1;,从第三项开始, 每一项为： 它

8、的前两项之和, 即： fi = fi-1+ fi-2;（i：29）,计算 fibonacci 中的项：,int f10;,f0 = 1; f1 = 1;,f,for(i = 2;i10;i+) fi = fi-1+fi-2;,for(i = 0;i10;i+) if ( i %5 = = 0 ) printf(n); printf(%4d, fi); ,1 1 2 3 5 8 13 21 34 55,8,13,21,34,55,5,3,执行过程：,1,1,30,31,32,32,一、定义一维数组变量 二、引用一维数组变量的元素 三、初始化一维数组变量 四、对数组进行输入和输出 五、应用举例,2

9、、一维数组,33,33,三、初始化一维数组变量,顺序指定全部元素的初始值: 格式：int a5 = 1, 2, 3, 4, 5; 结果： a0=1, a1=2, a2=3, a3=4, a4= 5,在定义数组的同时, 为数组元素指定值。 有4种方式：,34,34,指定部分元素的初始值: 格式：int a5 = 1, 0, 1; 结果： 数组a的前面三个元素赋了指定的初始值, 其他元素自动被赋为 0 值; a0 = 1, a1 = 0, a2 = 1, a3 = 0, a4 = 0。,35,35,指定部分元素的初始值: 格式：int a5 = 1, 0, 1; 结果： 数组a的前面三个元素赋了指

10、定的初始值, 其他元素自动被赋为 0 值; a0 = 1, a1 = 0, a2 = 1, a3 = 0, a4 = 0。,希望对数组中的第三个元素赋值为 5 , 初始化语句怎样写？,int a5= 0, 0, 5 ,36,36,初始化时不指定数组元素的个数: int b = 1, 2, 3; 结果： b数组中只包含3个元素 每个数组元素的值为： b0 = 1, b1 = 2, b2 = 3。 隐含定义数组的元素个数;,37,37,数组的静态存储: static int a5; 结果： 在编译时, 在静态存储区中数组a被分配给5个数组元素的空间, 并被自动初始化为全零。 各个数组元素的值： a

11、0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0,38,38,一、定义一维数组变量 二、引用一维数组变量的元素 三、初始化一维数组变量 四、对数组进行输入和输出 五、应用举例,2、一维数组,39,39,四、对数组进行输入和输出,C 语言规定, 对数组的使用只能逐个引用数组元素, 不能一次引用整个数组变量。 同样, 对数组的输入和输出也是依次对每个元素进行的。 即：printf和scanf语句的操作对象是每个数组元素。,例： 输入10 个数到数组a中, 然后将它们输出。,怎么做？,40,41,42,42,一、定义一维数组变量 二、引用一维数组变量的元素 三、初始化一维数

12、组变量 四、对数组进行输入和输出 五、应用举例,2、一维数组,43,43,五、应用举例,1、排序 1、冒泡法排序 2、选择法排序 2、查找 1、顺序查找 2、折半查找,44,44,用数组编程时，可以这样思考：,在存储器中有一片连续的内存区，名称为a。,将需要处理的一组数据，依次放入这片连续内存区的每一个单元中。对应的名称分别为：,a0,a1,a2,a3, ,an-2,an-1,a0,a1,a2,a3,a-2,a-1,根据问题的需要，对这组数据中的每一个数据元素进行相应的处理，处理时的访问方式为：a i ，即：数组a中下标为i的位置处的数组元素。,45,45,1. 有一个一维数组, 有 10 个

13、整数存放其中, 找出其中最大的一个数。,数组a,max,=,a0;,for( i=1;imax ) max=ai;,定义,main() int i, max, x10;,printf(enter data:n); for(i = 0;i10;i+) scanf(%d, ,max = x0; for(i = 1;imax) max = xi;,输入,处理,输出,printf(max = %dn, max); ,47,47,2. 用冒泡法对 10 个整数按从小到大的顺序排列。,什么是冒泡法排序？ 排序的过程 核心程序段 完整程序,怎么做？,48,48,冒泡法排序的思想,假设有 n 个数, 将相邻的

14、两个数依次进行比较, 使小的在前, 大的在后, 那么第一轮比较 n-1 次就把最大的数排到了最后。 第二轮比较 n-2 次, 就把次大的数排到了倒数第二, 依此类推, 直到第 n-1 轮比较1 次, 将最小的数排到了第一, 算法结束。 算法的整体思路是让大的数不断地往下沉, 小的数不断地往上冒, 所以叫冒泡排序法。,int a5,13 21 90 32 -1,13 21 32 90 -1,第一轮的结果： 将最大的数移到了最后一个位置（n-1）。,13 21 32 -1 90,a0 a1 a2 a3 a4,第一轮 21 13 90 32 -1,13 21 90 32 -1,int a5,13 2

15、1 32 -1 90,a0 a1 a2 a3 a4,13 21 32 -1 90,13 21 -1 32 90,第二轮 13 21 32 -1 90,第二轮的结果： 将第二大的数移到了 n-2 的位置。,int a5,a0 a1 a2 a3 a4,13 21 -1 32 90,第三轮 13 21 -1 32 90,13 -1 21 32 90,第三轮的结果： 将第三大的数移到了 n-3 的位置。,int a5,a0 a1 a2 a3 a4,第四轮 13 -1 21 32 90,-1 13 21 32 90,-1 13 21 32 90,结果：,最后一轮的结果： 将最小的数移到了第 0 的位置。

16、,排序程序段：,54,55,55,五、应用举例,1、排序 1、冒泡法排序 2、选择法排序 2、查找 1、顺序查找 2、折半查找,引例：从一组数中，找出其中最大的一个数。,引例：从一组数中，找出其中最大的一个数。,引例：从一组数中，找出其中最大的一个数。,59,59,3. 选择法排序,要求：将n个数按照从大到小的顺序排列。 前提：n个数放入一个一维数组中。 选择法排序的思想： 第一次, 从n个数中, 找出一个最大的, 放到第一个数组元素的位置处。 第二次, 从剩下的n-1个数中, 找出一个最大的, 放到第二个数组元素的位置处。 以此类推, 第n-1次, 从剩下的两个数中, 找出一个最大的放到第n

17、-1个数组元素的位置处。,61,62,62,写一选择法排序算法（小大） 写一冒泡法排序算法（大小）,思考题：,63,63,五、应用举例,1、排序 1、冒泡法排序 2、选择法排序 2、查找 1、顺序查找 2、折半查找,64,64,关于查找：,首先，待查找的数据放在一个一维数组中； 问题：到这样一个一维数组中去寻找一个满足某种特征的数组元素，如果找到，返回一个整数值，标志这个数在数组中的位序；如果找不到，返回整数0。 查找的方法：计算机中有许多的查找方法，在这里，我们只介绍两个方法：顺序查找和折半查找。,65,65,1、顺序查找,顺序查找方法适用于无序存放的一组数据。 查找从一维数组的最后一个数组

18、元素开始比较，直到找到指定的数组元素或已到达数组的头部依然没找到。,66,66,1、顺序查找,说明： 如果待查找的数据有n个，那么，我们定义一个拥有n+1个数组元素的一维数组； 其中，下标为0的数组元素留作他用，待查找的数据从下标为1的位置开始存放。 查找时，首先将指定的数据放入下标为0的位置，然后开始查找。,67,67,顺序查找过程：,顺序查找时的内存状态：,0号单元空置,数据元素从1号单元开始存放,68,68,顺序查找过程：,ST,假设给定值 key = 64， 要求,n,k,k,64,k,k,K=7,STk = key,， 问: k = ?,69,69,顺序查找过程：,ST,假设给定值 e = 60， 要求 STk = e， 问: k = ?,n,k,k,60,k,k,K=0,k,关键代码：,71,71,查找的结果：,如果在查找表中存在要查找的元素，则返回该元素所在的位置的下标； 如果在查找表中不存在要查找的元素，则返回整数 0； 程序描述如下：,73,73,2、折半查找,若数组中的数据已经按照从小到大的顺序排好序，则查找过程可以基于折半进行。 折半查找又称为二分查找。,74,74,折半查找基本思想,先与“中间位置”的数组元素值比较，若相等则查找成功，否则： 将给定值与中间位置的数组元素值比较，如果： 给定值中间位置的数组元素值, 则在后半部继续进行折半查找