C++课件第六章数组.ppt

第章数组 问题的引入 例 输入10个学生某门学科的成绩 求平均成绩 1 当读入下一分数时 前一分数值是否还能找到 2 如何将低于平均成绩的分数打印出来 在程序设计中存储单个数据时 需要根据数据的类型定义相应的变量来保存 如存储一个整数时需要定义一个整数变量来保存 存储一个实数时需要定义一个单精度或双精度变量来保存 存储含有多个成分的一个记录数据时 需要定义该类型的一个结构变量来保存 若在程序设计中需要存储同一数据类型的 彼此相关的多个数据时 如存储数学上使用的一个数列或一个矩阵中的全部数据时 显然采用定义简单变量的方法是不行的 这就要求定义出能够同时存储多个值的变量 这种变量在程序设计中称为数组 相同类型的若干个元素所组成的有序集合 在实际应用中 一组相关的数据之间可能存在着一维关系 也可能存在着二维关系 等等 如下表 概述 C 数据类型 基本类 简单类 字符型 整型 实型 枚举型 构造类 组合类 数组 结构体 共用体 指针类 空类型 void 基本类型 单个出现的变量 每个变量可以代表一个确定的数据 变量值 且具有一定属性 如staticintx y 但变量间不存在确定的相互关系 构造类型 由基本类型按一定规则组成 其中数组 由一组有序数据 数组元素 组成 这些数据保存在连续的内存空间 每个元素具有相同类型 因此占有相同大小的存储单元 具有统一数组名 用下标确定其顺序 但可以取各自值 如staticinta 5 其中 1 表示a是个数组 而不是一个简单变量a2 5表示该数组共有5个元素3 元素编号即下标从0开始 a 0 表示第一个元素 a 4 表示第5个元素 最后一个 一般化 假设m和n是常量 则数组a m 的第一个元素是a 0 最后一个元素是a m 1 数组a m n 的第一个元素是a 0 0 最后一个元素是a m 1 n 1 以此类推 数组的用处很多 简单例子 要读入某班全体50位同学某科学习成绩 然后进行简单处理 求平均成绩 最高分 最低分 分析 若用简单变量 需50个不同变量名 如stu1 stu2 stu50 要用很多个cin命令 而用数组 可共用一个cin命令 并利用循环结构读取 同变量一样 数组也必须先定义 后使用 定义内容 数组名 必须是合法标示符 类型 存储属性 数据类型 大小 维数 元素个数 定义的一般形式 存储属性数据类型数组名 常量表达式 常量表达式 常量表达式 常量或符号常量 其值必须为正 不能为变量 如 intn 5 inta n 这样定义是错误的 如下为正确的 inta 10 b 5 4 charname 8 ch 2 3 staticfloatx 8 2 1 table 2 3 4 defineNUM40inta NUM b NUM 2 数组定义 数组的初始化 可以在定义数组的同时赋初值 如 可以省略第一维数组大小 如 inta b 3 省略元素值 如 inta 5 0 intb 3 2 0 全部元素初始化为0 inta 3 1 2 3 4 5 6 7 思考第一维的大小 静态 外部数组未初始化 默认初值是0 数值 或 0 字符 auto数组未初始化 初值为不可预料的数 只能逐个引用数组元素 不能一次引用整个数组 引用数组元素要注意下标不要越界 编译程序不检查是否 越界 引用示例 a 2 3 a 2 1 2 3 1 a x x为整型表达式或变量 inta 5 for i 0 i 5 i 注意下标不要越界 cout a i 数组元素的引用 用一维数组来处理Fibonicci数列的前20项 f1 1n 1f2 1n 2fn fn 1 fn 2n 3 voidmain inti intf 20 1 1 f1 f2已知 for i 2 i 20 i f i f i 1 f i 2 for i 0 i 20 i if i 5 0 cout endl cout setw 12 f i include include 例 以下程序的运行结果是什么 includevoidmain inta 3 1 2 3 4 5 6 0 cout a 1 1 a 2 1 a 3 1 结果 500 123450600000 例 显示如下图形 1000021000321004321054321 a 5 5 分析 a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34a40a41a42a43a44 voidmain inta 5 5 1 2 1 3 2 1 4 3 2 1 5 4 3 2 1 i j for i 0 i 4 i for j 0 j 4 j cout a i j cout n 例 读入某班全体50位同学某科学习成绩 然后进行简单处理 求平均成绩 最高分 最低分 例 找出一个二维数组的鞍点 即该位置上的元素在该行上最大 在该列上最小 也可能没有鞍点 例 有一3 4矩阵 编程求其元素最大值并输出其行 列号 voidmain inti j x y max inta 4 3 5 8 1 6 9 7 12 6 max a 0 0 for i 0 imax max a i j x i y j cout maxisa x y max n 358169712 6000 结果 maxisa 1 3 12 用数组元素作函数实参此时可把数组元素看作普通变量 单向值传递 特点 主调函数中的实参 数组元素 带下标 被调函数中的形参 普通变量调用结果 形参值的变化对实参值无影响 二者分占不同内存 数组作为函数参数 例 voidmain inta 1 2 3 4 5 6 staticintb 6 2 3 0 4 inti sum int int int for i 0 i 6 i sum a i b i i cout a a i b b i voidsum intx inty intz x z y z 结果 a 1 b 2a 2 b 3a 3 b 0a 4 b 4a 5 b 0a 6 b 0 用数组名作函数实参若inta 6 则数组名a表示数组的起始地址 此时 是把实参数组的起始地址 传给 形参数组 本质 对应的数组元素 不是形参与实参 共享同一内存单元 所谓 双向的地址传送 特点 主调函数中的实参 数组名 不带下标 被调函数中的形参 数组名或数组定义式调用结果 两数组同下标者为同值 数组作为函数参数 例 voidmain inta 1 2 3 4 5 6 staticintb 6 2 3 0 4 inti sum int int int for i 0 i 6 i sum a b i cout a a i b b i voidsum intx inty intz x z z 2 y z z 传址 结果 a 2 b 0a 3 b 1a 4 b 2a 5 b 3a 6 b 4a 7 b 5 例 下面的程序定义了一个3x4的数组 表示3个学生 每个学生有4门成绩 求所有学生中的最好成绩 intmaximum int 4 int int voidmain intsg 3 4 68 77 73 86 87 96 78 86 90 70 81 86 coutmax max grade i j returnmax 字符数组的初始化charc 5 a b c c 3 和c 4 自动定为 0 字符串在内存中以字符数组存放 因此可以用字符串直接初始化字符数组 charc 5 abc 思考 charc abc 数组c的数组长度 字符串以字符串结束标志 0 即空字符 结束 可以思考 A 和 A 在内存中存放的区别 因此charc abc 等价于charc a b c 0 既数组c的数组长度为4 当然charc 5 abc 的数组长度仍为5 字符数组和字符串 字符数组charc 5 的输入法一 逐字符输入 inti for i 0 i c i 法二 字符串输入 cin c 注意 此法输入的字符串以空格或回车结束 即输入的字符串不可能包括空格 如输入 abcdef回车后 c对应的字符串为 abc 而不是 abcdef 另外此法输入的字符串串长有可能比数组长度要长 应引起注意 要想输入带空格的字符串 可使用函数cin get或者cin getline 此例对应cin get c 6 n 或者cin getline c 6 n 字符数组charc 5 的输出法一 inti for i 0 i 5 i cout c i 法二 cout c 输出一个字符串 直到遇到 0 为止 因此输出的字符串有可能和数组不一样 例 比较以下字符数组长度是否相同 chara ABCD charb ABCD charc A B C D 5 5 4 例 下列程序段的运行结果是 chara 5 a b 0 d 0 cout a ab 二维数组可以看成特殊的一维数组 这个特殊的一维数组的元素又是一个一维数组 即a 3 4 可看成数组长度为3的一维数组 而此一维数组的每个元素又是一个数组长度为4的一维数组 如下图所示 所以a 0 对二维数组a来说是元素名 但对一维数组 a 0 0 a 0 1 a 0 2 a 0 3 来说却是数组名 例 分析以下程序的运行结果 voidmain charword 3 10 inti for i 0 i word i cout word i 2 运行时 输入 12345 回车 abcdef 回车 ABCDEFG 回车 结果 abcdef 将一个字符串直接给一个字符数组只能够出现在初始化中 不能够出现在赋值语句中 也不能把一个字符数组直接赋值给另一个字符数组 如 charc 5 d 5 c abc d c 是错误的 要使用string h的函数strcpy to字符数组1 from字符数组2 如 strcpy c abc strcpy d c 字符串处理函数 例 以下程序的输出结果是 include string h voidmain chars 10 sp HELLO strcpy s sp s 0 h s 6 cout s hELLO strcat 字符串连接函数形式 strcat 目的字符数组 源字符串 作用 将源字符串连接到目的字符数组后面 函数返回值 目的字符数组的地址 注意 目的字符数组要定义得足够大 例 以下程序的输出结果是 include string h voidmain chara abcde charb 12345 strcat b a cout a b abcde 12345abcde 例 以下程序的输出结果是 include string h voidmain chara 80 AB b 80 LMNP inti 0 strcat a b while a i 0 b i a i cout b LBLMNP 比较两个字符串 字符数组 的大小要使用string h的函数strcmp 字符数组1 字符数组2 不能直接使用关系运算符 0时 字符串1 字符串2 strcmp函数返回值 0时 字符串1 字符串2 思考 如何判断str1是否等于str2 要写成if strcmp str1 str2 0 不可写成if str1 str2 include string h voidmain inti charstr 10 temp 10 Control for i 0 i str if strcmp temp str 0 strcpy temp str cout temp 例 运行以下程序时 从键盘输入 BOOKCUTGAMEPAGE 表示回车 则运行结果是什么 变量跟踪 tempstr比较 i 0 Control BOOK 0 i 1 Control CUT 0 i 2 Control GAME 0 GAME i 3 GAME PAGE 0 PAGE 求字符串实际长度可使用string h的函数strlen 字符数组 它不包括字符串的结束符 0 如 chara 10 abcde 则strlen a 5 sizeof a 10 例 以下程序段的运行结果是什么 chara t r 0will n cout sizeof a t strlen a 结果 103 数组元素的排序 一 输入10个数 用 冒泡法 对10个数排序 由小到大 冒泡法 算法 以六个数9 8 5 4 2 0为例 第1趟比较 第一次 8 9 5 4 2 0 第二次 8 5 9 4 2 0 第三次 8 5 4 9 2 0 第四次 8 5 4 2 9 0 第五次 8 5 4 2 0 9 第1趟比较产生第一个最大数 9 对剩下的五个数 8 5 4 2 0进行第2趟比较 第一次 5 8 4 2 0 第二次 5 4 8 2 0 第三次 5 4 2 8 0 第四次 5 4 2 0 8 第2趟比较产生第二个最大数 8依此类推 便可实现排序 第1趟比较后 剩5个数未排好序 两两比较5次第2趟比较后 剩4个数未排好序 两两比较4次第3趟比较后 剩3个数未排好序 两两比较3次第4趟比较后 剩2个数未排好序 两两比较2次第5趟比较后 全部排好序 两两比较1次 算法结论 对于n个数的排序 需进行n 1趟比较 第i趟比较需进行n i次两两比较 for i 1 ia j 1 t a j a j a j 1 a j 1 t 改进后的算法for i 1 ia j 1 t a j a j a j 1 a j 1 t flag 1 if flag 0 break 二 输入10个数 用 选择法 对10个数排序 由小到大 选择法 算法 以六个数9 8 5 4 2 0为例 第1趟比较 第一次 8 9 5 4 2 0 第二次 5 9 8 4 2 0 第三次 4 9 8 5 2 0 第四次 2 9 8 5 4 0 第五次 0 9 8 5 4 2 第1趟比较产生第一个最小数 0 对剩下的五个数 9 8 5 4 2进行第2趟比较 第一次 8 9 5 4 2 第二次 5 9 8 4 2 第三次 4 9 8 5 2 第四次 2 9 8 5 4 第2趟比较产生第二个最小数 2依此类推 便可实现排序 算法总结 对于n个数的排序 需进行n 1趟比较 第i趟比较时要将第i 1个开始的元素依次与第i个元素进行两两比较 后者小于前者就进行交换 for i 0 i n 1 i for j i 1 j n j if a j a i t a i a i a j a j t for i 0 i n 1 i k i for j i 1 j n j if a j a k k j if k i t a i a i a k a k t 改进后的选择排序算法 三 插入排序基本思想 假定从小到大排序 依次从后面拿一个数和前面已经排好序的数进行比较 比较的过程是从已经排好序的数中最后一个数开始比较 如果比这个数 继续往前面比较 直到找到比它大的数 然后就放在它的后面 如果一直没有找到 肯定这个数已经比较到了第一个数 那就放到第一个数的前面 那么一般情况下 对于采用插入排序法去排序的一组数 可以先选取第一个数做为已经排好序的一组数 然后把第二个放到正确位置 voidmain inti j t a 12 11 2 3 6 67 89 0 1 3 for i 1 i 0 j if t a j a j 1 a j elsebreak a j 1 t for i 0 i 10 i cout a i t 四 合并排序基本思想 将a b两个数组看成两个队列 比较队首的两个元素 将较小者放入c队列尾部 如果队首的两个元素相等 则先选择a队列首部元素加入c队列尾部 循环执行以上过程 直到a或b队列之一为空 然后将另一个非空队列拷贝到c队列尾部 inti 0 j 0 while i m 如果b队列非空 将b队列剩余元素拷贝至c队列尾部 数组元素的查找 二分 查找算法说明所谓 二分 查找 就是每次操作都将查找范围 已排序 一分为二 即将查找区间缩小一半 直到找到或查询了所有区间都没有找到要查找的数据为止 Find a mid key a mid key a mid intbinsearch inta intn intkey intlow 0 high n 1 mid low high 2 while lowa mid low mid 1 mid low high 2 return 1 课后练习 试卷汇编P5T23 26P15T24 25P23T24 P24T1 P25T9P27T12 涉及到指针部分 P32T24P33T1 3P41T3P42T6 7P51T22 P52T25P53T3 7