C++数组及其应用.ppt

数组及其应用 数组的概念 数组的应用 数组的定义 授课内容 字符串 常见错误 例 某班有50名学生 求该班成绩的平均分 includevoidmain intj sum s floatave sum 0 for j 1 j s sum sum s ave sum 50 0 cout ave ave 假设现在不仅要求平均分 还要求高于平均分的人数 那就不能只使用一个变量s了 而需要50个变量 但这样一来输入 输出 计算都会变得繁琐 在这种情况下 我们可以使用数组类型 说明一个含有50个元素的数组 每个数组元素存放一个成绩 成绩的输入 输出 计算都可通过循环来实现 引入 includevoidmain inti overn 0 mark 50 floatave 0 for i 0 i mark i ave ave mark i ave ave 50 for i 0 i ave overn cout 平均分 ave 高于平均分的人数有 overn 1数组的概念 数组是一组有序数据的集合 数组中的每一个元素都属于同一个数据类型 用一个统一的数组名和下标来唯一的确定数组中的元素 在科学计算和数据处理中 要用到成批数据 这些数据类型相同 且彼此间存在一定的顺序关系 为了便于处理 引入了数组类型 1 数组 由具有相同类型的固定数量的元素组成的结构 2 数组元素 每一个数组元素都是一个变量 为了与一般的变量相区别 我们称数组元素为下标变量 3 下标变量在数组中的位置序号称下标下标变量的数据类型称为下标类型 或元素类型 数组的概念 一维数组 一维数组的定义 一维数组的存储结构 数组元素的引用形式 一维数组的初始化 一维数组程序设计举例 算法 一维数组的输入和输出 数组 是一组具有相同数据类型的变量的有序集合 例如 inta 10 数组名 常量表达式 类型说明 一维数组的定义 格式 类型标识符数组名 常量表达式 inta 10 数组名 用户定义的标识符 数组名表示了一个存储区的首地址 即第一个数组元素的地址 intn cin n inta n 常量表达式中不能有变量常量表达式的值不能是实数 下标从0开始 a 0 a 1 a 9 没有a 10 常量表达式的值为元素的个数 一维数组的存储结构 a 一个数组的所有元素都是连续存储的 数组元素为 a 0 a 1 a 2 a 9 inta 10 所占空间为 类型长度 元素个数 数组首地址 数组元素的引用形式 数组元素的引用 数组名 下标 a 0 a 2 a 4 2 2 4 0 inta 10 a 0 2 说明 1 下标可以是整型常量或整型表达式如 a 1 a 2 3 2 数组定义为inta 5 数组长度为5而下标在0 4之内 即a 0 a 4 注意 如果出现a 5 72 编译时不会指出错误 系统会将a 4 后下一个存储单元赋值为72 但这样可能会破坏数组以外其他变量的值 一维数组的初始化 概念 在定义一维数组时对各元素指定初始值称为数组的初始化 如 inta 5 1 3 5 7 9 2 说明初值用 括起来 数据之间用逗号分开 对数组的全体元素指定初值 可以不指明数组的长度 系统会根据 内数据的个数确定数组的长度 如 inta 1 3 5 7 9 3 对数组中部分元素指定初值 这时不能省略数组长度 如 inta 5 1 3 5 4 使数组中的全部元素初始值都为0如 inta 5 0 0 0 0 0 更简单的写法 inta 5 0 例 输入50个成绩 求平均分 输出高于平均分的个数 includevoidmain inti overn 0 mark 50 floatave 0 for i 0 i mark i ave ave mark i ave ave 50 for i 0 i ave overn cout 平均分 ave 高于平均分的人数有 overn 一维数组的输入和输出 数组的输入和输出只能逐个对数组元素进行操作 字符数组例外 输入方法 定义 inta 10 i 输入第i个数组元素 cin a i 输入整个数组元素 for i 0 i a i 输出方法 输出第i个数组元素 cout a i 输出整个数组元素 for i 0 i 10 i cout a i 例 用一维数组求Fibonacci数列 includevoidmain inti intf 20 1 1 for i 2 i 20 i f i f i 2 f i 1 for i 0 i 20 i if i 5 0 cout n cout t f i f 0 f 1 f 2 f 3 f 4 f 5 f 19 i 2f 2 f 0 f 1 i 3f 3 f 1 f 2 i 4f 4 f 2 f 3 2 3 5 8 6765 例 输入一个数据 在已知数组中查找是否有该数据 9 a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 includevoidmain inti x inta 10 5 8 0 1 9 2 6 3 7 4 cin x for i 0 i 10 i if x a i cout find endl break if i 10 cout nofind endl includeVoidmain intf 20 1 1 j for j 2 j 0 j 逆序显示cout f j cout endl 练习 把F数列倒序输出 2二维数组 二维数组的定义 二维数组的存储结构 二维数组的初始化 二维数组元素的引用形式 二维数组的输入和输出 二维数组程序设计举例 二维数组的定义 格式 类型标识符数组名 常量表达式 常量表达式 intb 2 3 b为2 3 2行3列 的数组 b 0 b 1 b b 0 0 b 0 1 b 0 2 b 1 0 b 1 1 b 1 2 b 0 b 1 b 0 0 b 0 1 b 0 2 二维数组的存储结构 intb 2 3 b 1 0 b 1 1 b 1 2 b 0 0 b 0 1 b 0 2 存放顺序 按行存放 先顺序存放第一行的元素 再存放第二行的元素 b 0 b 1 可以作为数组名 a 1 0 a 1 1 a 1 2 a 2 0 a 2 1 a 2 2 a 0 0 a 0 1 a 0 2 a 0 0 a 0 1 a 0 2 a 1 0 a 1 1 a 1 2 a 2 0 a 2 1 a 2 2 101010141018102210261030103410381042 数组的元素在内存中是连续存放的inta 3 3 的存放形式如下 a 0 a 1 a 2 C 将二维数组看作一维数组 其每个数组元素又是一个一维数组 二维数组的初始化 intb 2 3 1 2 3 4 5 6 intb 2 3 1 2 3 4 5 6 分行赋值 按数组排列的顺序赋值 注意 此方法数据没有明显的界限 当数据较多时容易出错 将数据依次赋给元素b 0 0 b 0 1 b 1 2 intb 3 1 2 3 4 5 6 intb intb 1 2 3 4 5 6 intb n m 错 若全部都赋初值 第一维长度可省略 二维数组元素的引用形式 数组名 下标1 下标2 b 0 2 b 1 0 b 0 0 b 0 2 数组元素可以出现在表达式中 也可以被赋值 引用形式 inta 3 4 a 3 4 4 错 注意 1 每个下标都要用 括起来如a 2 1 不能写成a 2 1 2 下标不要超过定义的范围 intb 3 1 2 3 4 5 6 二维数组的输入和输出 数组的输入和输出只能逐个对数组元素进行操 字符数组例外 定义 inta 2 3 i j 例 有一个3 4的矩阵 编程求出其中的最大值及其所在的行号和列号 max row col 12 1 2 includevoidmain inti j row 0 col 0 max inta 3 4 5 2 0 9 3 7 12 6 10 4 1 8 max a 0 0 for i 0 imax max a i j row i col j cout max max cout max a row col 输出 max 12max a 1 2 例 将一个矩阵进行转置 即原来的行变为列 includevoidmain inta 3 4 b 4 3 i j for i 0 i a i j for i 0 i 3 i for j 0 j 4 j b j i a i j for i 0 i 4 i for j 0 j 3 j cout b i j cout endl 输入数组a 进行矩阵转置 输出数组b a 0 2 b 2 0 a 2 1 b 1 2 练习 输出杨辉三角 111121133114641 include includevoidmain inti j a 10 10 0 for i 0 i 10 i a i 0 1 a i i 1 for i 2 i 10 i for j 1 j i j a i j a i 1 j a i 1 j 1 for i 0 i 10 i for j 0 j 10 i j cout for j 0 j i j cout setw 4 a i j cout endl 课堂练习 1 数组元素a i 是该数组中的第 个元素 2 元素类型为int的数组a 10 共占用 字节的存储空间 其中元素a 5 的字节地址为 3 元素类型为double的数组a 4 6 共占用 字节的存储空间 其中元素a 2 5 的字节地址为 4 元素类型为char的数组a 10 30 共占用 字节的存储空间 其中元素a 3 4 的字节地址为 答案 1 i 12 40a 203 192a 1364 300a 94 利用数组进行数值计算 3数组的应用 利用数组进行统计 数据排序冒泡法选择法 查找数据顺序查找 不要求数组元素有序排列 二分查找 要求数组元素有序排列 基本算法举例 1 排序 1 冒泡法排序例 输入5个数 进行由小到大排序 98542 算法 两两比较 大数向后移 找到最大数放在最后 再在剩余的的4个数中进行两两比较 找到最大数 以此类推 总是小数往前放 大数往后放 相当于气泡上升 故称之为 冒泡法 85429 5428 425 24 比较4次第一轮 比较3次第二轮 比较2次第三轮 比较1次第四轮 98542 89542 85942 85492 8542 5842 5482 542 42 452 对n个数 则要进行n 1趟扫描 在第i趟扫描中要进行n i次比较 可以推知 排序 for i 0 ia j 1 t a j a j a j 1 a j 1 t include defineN10voidmain inti j a N t for i 0 i a i for i 0 i N i 输出cout a i 排序 for i 0 ia j 1 t a j a j a j 1 a j 1 t for i 0 i N i 输出cout a i 2 选择法排序特点 比较后不立即互换元素 而是记下其位置并在每一轮比较完毕后和 互换 排序过程 1 首先通过9次比较 从10个数中找出最小的 将它与第1个数交换 第一趟选择排序 结果最小的数被安置在第1个元素位置上 2 再通过8次比较 从剩余的9个数中找出次小的数 将它与第2个数交换 第二趟选择排序 3 重复上述过程 共经过9趟排序后 排序结束 49386597761327 第1趟 i 0 13 49 13 386597764927 27 38 132738496576 97 第2趟 i 1 第3趟 i 2 第4趟 i 3 第5趟 i 4 第6趟 i 5 includeconstintN 10 voidmain inta N i j k t for i 0 i a i 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 for i 0 i N i cout a i 例 在有序数组中插入一个数后使原数组仍然有序 例如 3571218 m 5 将b 10插入步骤 1 要找到b在数组中的位置 2 给b让位置 3 将b放到该位置上 4 数组元素的个数m加1 b 10 for i 0 ib break for j m 1 j i j a j 1 a j a i b 12 18 10 m m 1 4 357101218 m 6 将b 10删除步骤 1 要找到b在数组中的位置 2 后面的数组元素依次前移 覆盖该位置上的数组元素即可实现删除 3 数组元素的个数m减1 例 在有序数组中删除一个数 例如 for i 0 i m i if a i b break 10 12 18 for j i j m 1 j a j a j 1 3 m m 1 是对有序数列进行查找的一种高效查找办法 其基本思想是逐步缩小查找范围 采取半分作为分割范围可使比较次数最少 比较过程 设数列已做升序排序处理 设置三个变量 分别代表数组序列s的low high和mid位置 其中mid low high 2 进行下列判断 134681012151820 X 15 查找 1 顺序查找 2 折半查找法 对有序数组 4字符串 字符串及字符串结束标志 字符数组的输入和输出 字符串处理函数 字符数组程序应用 字符数组的定义 字符数组的初始化 字符数组 用来存放字符数据的数组为字符数组 charc 10 charc 10 I a m h a p p y 若初值个数小于数组长度 剩余元素自动定为空字符 charc 12 c p r o g r a m intc 10 定义 初始化 二者互相通用 但存储空间不同 字符串和字符串结束标志 C 中没有专门的字符串变量 因此字符串存放在字符数组中 字符串以 0 作为结束标志 字符串 由若干个有效字符组成的序列有效字符包括字母 数字 专用字符 转义字符如 bfer a45 7 m tk n 例 charc 5 c 0 O c 1 K c 2 c 0 O c 1 K c 2 c 3 0 注意 字符数组与字符串并不相同 字符数组的初始化 如果对数组全部元素指定初值 则可以省略数组的长度charc H e l l o 1 为数组中的元素指定初值charc 8 H e l l o 2 对字符数组指定字符串初值 charc 8 Hello charc 8 Hello charc 8 H e l l o 0 charc Hello charc 6 Hello charc 5 Hello 错误的初始化 注意 初始化时数组的长度应足够大 确保可以容纳所有字符和结束标志 0 1 输入单个字符charc 8 inti cin c 0 c 1 c 2 for i 0 i c i 2 整个数组的输入输出 即按数组名输入输出 仅用于字符数组 因数组名本身代表数组的首地址 字符数组的输入和输出 注意 1 输入 输出字符串时不包括 2 cin输入时系统一直读取字符 直到遇到 空白符 为止 例如 输入数据helloworldC数组中内容为hello 补充get 函数 包含在 iostream h 如想输入含空格的字符串 如 helloworld 只能使用get 函数 使用格式如下 cin get 字符数组名 字符串长度 规定的结束符 其中 规定的结束符省略时 默认为回车键 如 charstr 20 cin get str 20 字符串处理函数 字符串函数的原型保存在中字符串连接函数 strcat s1 s2 char strcat char s1 constchar s2 连接s1和s2两个字符串赋给s1 返回s1的值字符串拷贝函数 strcpy s1 s2 char strcpy char s1 constchar s2 将s2中的字符串赋给s1 返回s1的值字符串比较函数 strcmp s1 s2 求字符串长度函数 strlen s 函数值为整数 返回字符个数 参数为字符数组名 5字符数组程序应用 字符串的长度 逆序 字符串函数 例 求字符串长度 扫描数组 只要不是 0 计数器就加1 源程序 includevoidmain inti chars 50 cin s for i 0 i 50 i for i 0 i 50 i i 0 字符串连接函数 例 STRCAT includevoidmain inti j chars1 40 s2 20 cin s1 s2 for i 0 i 40 s1 s2 s1 i strlen s1 例 STRCPY includevoidmain charp1 80 p2 80 inti cin p2 for i 0 p2 i 0 i p1 i p2 i p1 i 0 cout p1 p1 np2 p2 n 字符串复习 字符数组 用来存放字符数据的数组是字符数组 字符数组中的一个元素存放一个字符 一 字符数组的定义 char数组名 常量表达式 charc 4 每个元素占一个字节 c 0 I c 1 m c 2 类型 数组名 数组大小 二 字符数组的初始化 与数值数组的初始化相同 取其相应字符的ASCII值 charc 10 I a m a b o y 如果字符个数大于数组长度 做错误处理 如果数值个数小于数组长度 后面的字节全部为 0 如果省略数组长度 则字符数即为数组长度 staticcharc I a m a g i r l 同理 也可定义和初始化一个二维或多维的字符数组 分层或省略最后一维 charst1 65 66 68 三 字符数组的引用 voidmain void charc 10 I a m a b o y inti for i 0 i 10 i cout c i cout n 定义 输出 四 字符串和字符串结束标志 C 语言将字符串作为字符数组来处理 字符串常量 CHINA 在机内被处理成一个无名的字符型一维数组 C 语言中约定用 0 作为字符串的结束标志 它占内存空间 但不计入串长度 有了结束标志 0 后 程序往往依据它判断字符串是否结束 而不是根据定义时设定的长度 字符串与字符数组的区别 chara C H I N A charc CHINA 字符数组 字符串 可以用字符串的形式为字符数组赋初值 charc Iamaboy 长度11字节 以 0 结尾 chara I a m a b o y 长度10字节 如果数组定义的长度大于字符串的长度 后面均为 0 charc 10 CHINA 0 的ASCII为0 而 空格 的ASCII为32 charw T u r b o 0 charw Turbo 0 charw Turbo 0 charw Turbo 0 非法 chara 2 5 abcd ABCD str为字符数组在内存中存储的地址 一经定义 便成为常量 不可再赋值 charstr 12 TheString 非法 在语句中赋值 定义数组 开辟空间时赋初值 字符数组的输入输出 逐个字符的输入输出 这种输入输出的方法 通常是使用循环语句来实现的 如 charstr 10 cout str i A A行将输入的十个字符依次送给数组str中的各个元素 定义 赋值 把字符数组作为字符串输入输出 对于一维字符数组的输入 在cin中仅给出数组名 输出时 在cout中也只给出数组名 voidmain void chars1 50 s2 60 cout s1 cin s2 cout ns1 s1 cout ns2 s2 n 输入 abcdstring cin只能输入一个单词 不能输入一行单词 数组名 数组名 输出到 0 为止 当要把输入的一行作为一个字符串送到字符数组中时 则要使用函数cin getline 这个函数的第一个参数为字符数组名 第二个参数为允许输入的最大字符个数 cin getline 数组名 数组空间数 chars1 80 cin getline s1 80 首先开辟空间 参数是数组名 voidmain void chars3 81 cout 输入一行字符串 cin getline s3 80 Acout s3 s3 n B 当输入行中的字符个数小于80时 将实际输入的字符串 不包括换行符 全部送给s3 当输入行中的字符个数大于80时 只取前面的80个字符送给字符串 定义 从键盘接收一行字符 输出到 0 为止 六 字符串处理函数 C 中没有对字符串变量进行赋值 合并 比较的运算符 但提供了许多字符串处理函数 用户可以调用 include string h 所有字符串处理函数的实参都是字符数组名 1 合并两个字符串的函数strcat str1 str2 staticcharstr1 20 Iama staticcharstr2 boy strcat str1 str2 将第二个字符串str2接到第一个字符串str1后 注意 第一个字符串要有足够的空间 空间足够大 2 复制两个字符串的函数strcpy str1 str2 staticcharstr1 20 Iama staticcharstr2 boy strcpy str1 str2 strcpy str1 CHINA strcpy CHINA str1 str1 str2 str1 CHINA 字符串正确赋值 均为非法 3 比较两个字符串的函数strcmp str1 str2 此函数用来比较str1和str2中字符串的内容 函数对字符串中的ASCII字符逐个两两比较 直到遇到不同字符或 0 为止 函数值由两个对应字符相减而得 该函数具有返回值 返回值是两字符串对应的第一个不同的ASCII码的差值 若两个字符串完全相同 函数值为0 if strcmp str1 str2 0 用来判断两字符串是否相等 staticcharstr1 20 CHINA staticcharstr2 CHINB cout strcmp str1 str2 endl 输出 1 staticcharstr1 20 CHINA staticcharstr2 AHINB cout strcmp str1 str2 endl 输出 2 if str1 str2 cout yes n if strcmp str1 str2 0 cout yes n 非法 正确 4 求字符串长度的函数strlen str1 长度不包括 0 函数参数为数组名 返回值为数组首字母到 0 的长度 并非数组在内存中空间的大小 chars 80 strcpy s abcd cout strlen s endl 输出 4 输出 3 cout strlen str1 endl cout siziof s endl 输出 80 charstr1 20 CHINA cout strlen str1 endl 输出 5 charsp x69 082 cout strlen sp endl 输出 6 charsp t v 0will n cout strlen sp endl 输出 3 charstr1 20 abook cout strlen str1 endl 输出 1 5 strlwr str1 将str1中的大写字母转换成小写字母 6 strupr str1 将str1中的小写字母转换成大写字母 7 函数strncmp 字符串1 字符串2 maxlen 函数原型为 intstrncmp charstr1 charstr2 intm 第三个参数为正整数 它限定了至多比较的字符个数 若字符串1或字符串2的长度小于maxlen的值时 函数的功能与strcmp 相同 当二个字符串的长度均大于maxlen的值时 maxlen为至多要比较