C语言程序设计重庆大学课件第章数组及其应用.ppt

程序设计技术 C语言数据描述和C程序设计初步结构化程序设计基础和C语言的控制结构数组及其应用函数与C程序结构指针与函数指针与数组字符串及其应用结构体类型和联合体类型C语言的文件处理及其应用位运算与枚举类型 数组及其应用 3 1一维数组3 1 1一维数组的定义和初始化3 1 2一维数组元素的引用方法3 2二维数组和多维数组3 2 1二维数组和多维数组的定义3 2 2二维数组和多维数组元素引用方法3 3数组的简单应用3 3 1数组元素值的随机生成3 3 2常用排序方法3 3 3常用查找方法 一维数组 数组是有序数据的集合 一维数组是一组按线性排列有序且个数有限的同类型变量构成的数据集合 每个数组有一个名称 数组名 数组中的每个数据元素有一个编号 下标 下标从0开始 是正整数 一维数组在存储时需要占用连续的内存空间 其每一个数据元素所占用的字节长度与它们的数据类型相关 3 1 1一维数组的定义和初始化 一维数组的定义存储类型数据类型数组名 常量表达式 存储类型 auto static extern数据类型 数组元素的数据类型 基本 构造 指针 常量表达式 指定数组的元素个数 也称数组长度 例如 ints 30 定义了1个整型数组s 把30个学生的成绩放在一维数组s中 数组中每个元素表示一个学生的某科成绩 如s 5 表示序号为5的学生成绩73 因序号从0开始 所以没有S 30 元素 3 1 1一维数组的定义和初始化 一维数组的初始化数据类型数组名 n 常量列表 其中 常量列表 可是逗号分隔的常量或常量表达式 n 数组长度 常量列表个数不能超过数组长度 例如 inta 10 1 2 3 4 5 6 7 8 9 10 常量 intb 3 1 3 5 4 3 2 常量表达式 intd 5 1 2 3 4 5 6 超过数组长度 注意 数组名代表数组存储区的首地址 即第一个数组元素的存储地址 即a等价于 a 0 3 1 1一维数组的定义和初始化 数组元素初始化的几种形式在数组初始化时 既可以对全部数组元素赋初始值 也可只对部分数组元素赋初始值 没有初始化的元素值为0 字符数组为 0 chars1 10 a b c d e 其余元素为 0 如果数组长度没有指定 以初始化数值个数作为数组的长度 或者说数据的个数是确定的 可以不指定数组的长度 floata1 10 20 30 9 40 50 数组长度为5 将数组全部元素初始化为0值的简写形式例如 inta 10 0 inta 5 0 10 不能给数组整体赋值例如 inta 5 1 1 1 1 1 inta 5 1 3 1 2一维数组元素的引用 C语言规定 只能逐个引用数组元素而不能一次引用整个数组 数组元素 下标变量 表示形式 数组名 下标 下标 整型常量或整型表达式 实型下标自动取整 例 intb 10 定义数组b b 10 100 下标越界 b 100 整体操作数组 常将数组和循环配合使用 通过改变数组的下标值来访问数组的各个元素 举例如下 doublea 10 for i 0 i 10 i scanf lf 将a数组第6个元素 序号5 赋值为300 3 1 2一维数组元素的引用 例3 1将一个整型数组中所有元素值在同一个数组中按逆序重新存放并输出 程序一次运行情况如下所示 InputtenvalueofArray 2123252729303234363838363432302927252321 Arr 0 Arr 9 3 1 2一维数组元素的引用 例3 4打印杨辉三角形的前10行 用一维数组处理 杨辉三角形的数列特点 即一行中某列的数是上一行该列上前两位数之和 比如第4行第2列的3等于第3行第1 2列的数1 2 每行第1列和最后1列都为1 行数 列数 解题思路 利用数组具有保存数据的特点 将第1列初始化为1 第n行从第n列开始 从后往前计算该行中各列的值 在数组中已经保留了上一行的各列数据 利用此数据 可以计算新行的各列数据 然后输出 3 1 2一维数组元素的引用 对每一行杨辉三角形值的具体处理方法为 首先用表达式yh row 1将该行最后一个元素值置1 然后从后向前循环执行表达式 yh col yh col yh col 1 即将一维数组yh上一行当前位置元素值与其前面一个位置的元素值相加作为本行当前位置上的元素值 row 1 yh 1 1 利用它可将每行的第1列置为1 row 2 yh 2 1 row 3 yh 3 1 yh 2 yh 2 yh 1 2 row 4 yh 4 1 yh 3 yh 3 yh 2 3 yh 2 yh 2 yh 1 3 row 5 yh 5 1 yh 4 yh 4 yh 3 4 yh 3 yh 3 yh 2 6 yh 2 yh 2 yh 1 4 3 1 2一维数组元素的引用 对每一行杨辉三角形值的具体处理方法为 首先用表达式yh row 1将该行最后一个元素值置1 然后从后向前循环执行表达式 yh col yh col yh col 1 即将一维数组yh上一行当前位置元素值与其前面一个位置的元素值相加作为本行当前位置上的元素值 row 1 yh 1 1 row 2 yh 2 1 row 3 yh 3 1 yh 2 yh 2 yh 1 2 row 4 yh 4 1 yh 3 yh 3 yh 2 3 yh 2 yh 2 yh 1 3 row 5 yh 5 1 yh 4 yh 4 yh 3 4 yh 3 yh 3 yh 2 6 yh 2 yh 2 yh 1 4 各行的第1列都置为1 各行的最后1列都置为1 倒数第2列开始处理 1yh 1 11yh 1 yh 2 121yh 1 yh 2 yh 3 1331yh 1 yh 2 yh 3 yh 4 数组及其应用 3 1一维数组3 1 1一维数组的定义和初始化3 1 2一维数组元素的引用方法3 2二维数组和多维数组3 2 1二维数组和多维数组的定义3 2 2二维数组和多维数组元素引用方法3 3数组的简单应用3 3 1数组元素值的随机生成3 3 2常用排序方法3 3 3常用查找方法 3 2二维数组和多维数组 在程序设计中如果需要处理诸如矩阵 平面的或立体的图形等数据信息 使用一维数组显然不够 可以使用二维 三维以至更多维的数组 一维数组存储线性关系的数据 二维数组则可以存储平面关系的数据 三维数组可以存储立体信息 依次类推可以合理地使用更高维数的数组 数组的几个实例 用二维数组做字模手机屏幕采用的字体称为 点阵 字体 如果不支持中文 则最小只需7 7点阵 程序要在屏幕上打出 A 时 则只需遍历该数组 然后在元素值为0的地方 打出空格 在元素值为1的地方 打出小点即可 对于这样一个点阵 对应的一个二维数组为 数组的几个实例 多个班级的成绩管理如 某年级有4个班 每个班最多不超过40人 则该成绩数据对应于一个二维数组 intcj 4 40 提问 2班24号的成绩是哪个数组元素 答案是 cj 1 23 注意 C语言中的数组下标从0开始 所以2班24号对应数组元素的下标是1和23 数组的几个实例 多个年级的成绩管理设有 年级总数为6 每个年级的班级数为4 每个班级的学生人数为40 利用三维数组实现多个年级的成绩管理intcj 6 4 40 将三年级 2班 20号学生的成绩赋值为78cj 2 1 19 78 二维数组和多维数组的定义一个二维数组可以分解为多个一维数组 可以推论多维数组 n维数组的每个元素由n 1维数组构成 二维数组定义的一般形式为 数据类型数组名 常量表达式 常量表达式 多维数组定义的一般形式为 数据类型数组名 常量表达式 常量表达式 例如 inta 3 4 ma 10 10 二维数组 floatb 3 3 3 三维数组 a由3行4列共12个元素组成 ma由10 10共100个元素组成 b是一个3 3 3共27个元素构成的三维数组 行数 列数 3 2 1二维数组和多维数组的定义 C语言中规定数组按 行 存储 由于计算机系统内存是一个线性排列的存储单元集合 所以当需要存储二维或多维数组到内存时 必须进行二维空间或多维空间向一维空间的投影 例如 inta1 2 2 a2 2 2 2 则数组a1和a2在内存的存放形式如图3 4和3 5所示 3 2 1二维数组和多维数组的定义 根据多维数组在存储器中按行存储规则和行列顺序 计算多维数组元素在连续内存中的单元序号 以0开头 设有m n m行n列 的二维数组a 则二维数组元素a i j 在连续存储区域的单元序号计算公式为 i n j 行号 列数 列号 例如 inta 2 2 则数组元素a 1 1 的序号为 1 2 1 3即二维空间中1行1列元素是一维空间中的3号元素 三维数组部分省略 参看第3章要点 3 2 1二维数组和多维数组的定义 3 2 1二维数组和多维数组的定义 二维和多维数组的初始化 分行赋值初始化方式例如 inta 2 3 1 1 1 2 2 2 inta 10 20 0 inta 4 1 2 3 4 5 6 7 8 9 10 11 12 系统根据12个元素 二维长度为4 自动测算出一维长度3 单行赋值初始化方式例如 inta 3 4 1 2 3 4 5 6 7 8 9 10 11 12 对部分数组元素赋初值例如 inta 3 4 1 0 6 0 0 11 二维数组元素的下标表示法数组名 下标 下标 数组元素也称为下标变量 其用法与一般变量相同 例 doublea 5 5 y a 2 3 300 将a的2行3列元素赋值300 y 500 将变量y赋值500 a 5 5 200 下标越界 在程序设计中 二维数组不能作为一个整体进行处理 通常用双重for循环来逐个访问二维数组元素 外循环控制行 内循环控制列 外循环控制列 内循环控制行 例如 inta 5 10 i j 则a数组的输入输出基本形式如图3 8所示 3 2 1二维数组和多维数组的引用 3 2 2二维数组和多维数组元素引用 例3 5在二维数组a 3 4 中依次选出各行最大元素值存入一维数组b 3 对应元素中 程序运行结果 arraya 31687654321110810251227arrayb 8710827 数组及其应用 3 1一维数组3 1 1一维数组的定义和初始化3 1 2一维数组元素的引用方法3 2二维数组和多维数组3 2 1二维数组和多维数组的定义3 2 2二维数组和多维数组元素引用方法3 3数组的简单应用3 3 1数组元素值的随机生成3 3 2常用排序方法3 3 3常用查找方法 3 3 1数组元素值的随机生成 计算机自动生成 随机数 是一种较好的模拟数据法为在程序中产生随机数 需要使用标准库函数srand rand和time 并将对应头文件包含到程序中 Srand函数是初始化随机数 即种子 发生器 种子可以当前的系统时间产生 函数原型在stdlib h中声明 voidsrand unsignedintseed rand函数是随机产生一个0到RAND MAX 0 x7fff 之间的正整数 函数原型在stdlib h中声明 intrand void time函数是获取系统时间 函数原型在time h中声明如下 time ttime time t timer 3 3 1数组元素值的随机生成 例3 7随机生成20个3位以内的整数序列存放在一维数组中 然后按每行5个数输出所有数组元素 程序一次运行结果为 659100184135876348934293587338179243523799653234657439776297例3 8编程序实现如图3 10所示的矩阵转置功能 即将N M矩阵转换为M N矩阵 要求被处理的二维数组元素值 2位数以内 随机产生 冒泡排序 从待排数据序列中第一个位置开始 依次比较相邻两个位置上的数据 若是逆序则交换 一趟扫描后 关键字值最大 或最小 的数则交换到了最右边 或最下面 不考虑已排好序的数据 将剩下的数作为待排序列 重复 两步直到排序完成 n个数据的排序最多进行n 1趟比较 在第1趟比较中要进行n 1次两两比较 在第i趟比较中要进行n i次的两两比较 例3 9编程实现冒泡排序算法 对随机生成的20个整数按升序排序并输出 3 3 2数组的常用排序方法 将6个数进行冒泡排序第一趟比较中 进行了5次比较 最大数下沉 5555556622222266669999991010101010333333101次2次3次4次5次结果 3 3 2数组的常用排序方法 余下5个数进行排序第二趟比较中 进行了4次比较 次大数下沉 52222255556666699993333391次2次3次4次结果 3 3 2数组的常用排序方法 3 3 2数组的常用排序方法 选择排序 交换排序的优化 假设具有n个元素的数组a中用a 0 存放最小 或最大 的数 将此数与后面所有的数比较并用下标变量k记录最小 或最大 数所在位置 一趟比较完成后 将a 0 与a k 交换 在剩下的N 1个数据 即a 1 到a n 1 的元素 中使用相同的方法寻找最大 或最小 的数 并将a 1 与a k 交换 以此类推 直到将整个待排数据集合处理完 例3 10编程序实现选择排序算法 对随机生成的20个整数按升序进行排序并输出 将6个数进行选择排序在a 0 到a 5 数组元素中找最小数a 0 a 1 a 2 a 3 a 4 a 5 5629103 3 3 2数组的常用排序方法 记下小数下标为2 将a 0 与a 2 交换在余下a 1 到a 5 数组元素中又找最小数a 1 a 2 a 3 a 4 a 5 659103 将a 1 与a 5 交换 小数下标为2 修改小数下标为5 3 3 3数组的常用查找方法 顺序查找 线性查找 从数组首元素或最后一个元素开始 往后或往前顺序比较每一个数组元素值是否等于查找关键字 如果找到相符合的元素值 则查找成功 否则 查找失败 顺序查找适应于被查找集合无序的场合 例3 11编程序实现顺序查找算法 在随机生成的20个整数中查找指定值 要求程序能够显示出查找进行比较的次数以及本次查找成功与否 3 3 3数组的常用查找方法 折半查找 二分查找 该算法要求在一个对查找关键字而言有序的序列上进行 其基本思想是 逐步缩小查找目标可能存在的范围 具体描述如下 选取表中中间位置的记录作为基准 将表分为两个子表 当基准位置的关键字值与查找关键字值相符合时 返回基准记录位置 算法结束 当基准位置的关键字值与查找的关键字值不符合时 在处理的两个子表中选取一个子表 重复执行 直到被处理的子表中没有记录为止 3 3 3数组的常用查找方法 图3 11是在一有序序列中实现对key 21进行折半查找 low 0 high 22 middle 11 数组下标从0开始 low 12 high 22 middle 17 数组下标从12开始 low 18 high 22 middle 20 数组下标从18开始 例3 12a编程实现折半查找 在有序数组a的23个元素中查找关键字21 并输出查找比较次数以及查找成功与否的信息