第四章 数组和字符串.ppt

1 第四章数组和字符串 2 主要内容 数组的概念 数组的定义 数组的应用 字符串 3 4 1数组的概念 一个简单变量可以存放一个简单数据 怎样存放彼此相关的多个数据呢 如果是同一类型的数据 通常定义一个数组 如果是不同类型的数据 通常定义一个结构或类 数组可以用来存储彼此相关的若干数据 如 数列或矩阵等 4 1 数组 Array 是具有一定顺序关系的若干相同类型变量的集合体 是一种构造类型 2 数组机制要掌握 1 数组描述 数组变量定义 2 数组使用 使用元素 通过数组名和下标通过指针 和下标 3 数组实现 数组的存储方式 5 3 什么是数组的存储单元 数组中一个数据称作一个数组 元素 每个元素占居一个存储单元 数组元素在内存中连续存储 元素下标越小地址值越小 元素下标越大地址值越大 0123 四元素数组的存储 6 4 数组的分类 一维数组 存储数列 如 38 42 25 60 存放在长度为4的数组中 二维数组 存储矩阵 如 可存放在行长度为 列长度为 的二维数组中 多维数组 两维或两维以上 7 4 2数组的定义和使用 4 2 1一维数组 One DimensionalArrays 一 一维数组的声明类型说明符数组名 常量表达式 例如 inta 10 表示a为整型数组 有10个元素 a 0 a 9 数组元素编号规则 首元素 第一个元素 序号为0 顺序编号 n 元 数组元素的编号是0到n 1 8 二 一维数组的初始化 定义数组的同时赋给数组元素初值叫做数组的初始化 初始化可以在编译阶段使数组得到值 在声明数组时对全部数组元素赋以初值 例如 inta 10 0 1 2 3 4 5 6 7 8 9 可以只给一部分元素赋初值 例如 inta 10 0 1 2 3 4 后面值为0charb 5 a c 后面值为 0 可以不指定数组长度赋值 此时认为在对全部数组元素赋初值例如 inta 1 2 3 4 5 数组 9 eg1 数组的定义及初始化举例 inta 20 doubleb MS MS为已定义的整型常量intc 5 1 2 3 4 0 chard a b c d inte 8 1 4 7 charf 10 B A S I C boolg 2 N 1 N为已定义的整型常量floath1 5 h2 10 shortx 1 y 2 z w 4 25 x 10 x 2 y 44 10 eg2 判断正误 intarray 5 1 2 3 4 5 6 intarray 1 2 3 4 5 6 intarray 5 1 3 4 5 intarray 5 1 2 3 intarray 5 0 intarray 5 error error ok ok ok error 11 数组元素的引用 数组元素和普通变量一样必须先声明 后使用 单个数组元素和同类型的变量可进行一样的操作一般不能一次引用整个数组 字符数组例外 元素访问方式 通过 运算符及下标表达式 eg inta 10 a 0 a 5 a 7 a 2 3 ok 元素编号为 0 9数组元素为 a 0 a 9 注意 编译程序不能检查下标越界错误 eg 区别a 5 在不同情况下的意义 inta 5 a 5 0 a中元素个数至少为6个 三 一维数组元素的引用和访问 12 假定a n 为一已定义的数组 下面都是访问该数组的下标变量的合法格式 a 5 下标为一常量a i 下标为一变量a j 下标为后增一表达式a 2 x 1 下标为一般表达式a a 0 下表为数组元素 设a n 为整型且a 0 n 使用一个下标变量同使用一个简单变量一样 可对它赋值 取出它的值 或者做运算 13 四 数组元素的赋值操作 数组元素在初始化时可以整体赋值 在一般的赋值语句中需要逐个赋值 字符数组可以通过特殊函数整体赋值 14 例4 1一维数组元素的输入与输出操作 includevoidmain intA 10 B 10 inti for i 0 i 10 i A i i 2 1 B 10 i 1 A i for i 0 i 10 i cout A i A i for i 0 i 10 i cout B i B i endl 用循环逐个输出 给数组元素逐个赋值 逐个输出数组元素值 15 五 一维数组的存储 数组元素在内存中顺次存放 它们的地址是连续的 例如 具有10个元素的数组a 在内存中的存放次序如下 数组名字是数组首元素的内存地址 数组名是一个地址常量 不能被赋值 16 sizeof a 数组a的存储长度sizeof a 0 数组a元素的长度sizeof a sizeof a 0 数组a的元素个数 测试数组元素的大小 sizeof 17 includevoidmain inti intf 20 1 1 初始化第0 1个数 for i 2 i 20 i f i f i 2 f i 1 求第2 19个数 for i 0 i 20 i if i 5 0 cout endl 输出 每行5个数 cout setw 8 f i cout endl 例1 用数组来处理求Fibonacci数列问题 最前面两个元素是1 其余元素都是其前两元素之和 运行结果 11235813213455891442333776109871597258441816765 18 例 找出Fibonacci数列中比 大的最小数 是常量 intjsValue intt inta 1 b 1 while at returnb a a b if a t returna else b a if b t returnb 19 例2 评分程序 本例循环从键盘读入若干组选择题答案 计算并输出每组答案的正确率 直到输入ctrl z为止 每组连续输入5个答案 每个答案可以是 a d 20 includevoidmain charkey a c b a d charc intques 0 numques 5 numcorrect 0 cout Enterthe numques questiontests endl 21 while cin get c if c n if c key ques numcorrect cout elsecout else cout Score float numcorrect numques 100 ques 0 resetvariablesnumcorrect 0 cout endl continue ques 22 运行结果 acbba Score60 acbadScore100 abbda Score40 bdcba Score0 23 eg3 一维数组元素排序 选择法排序过程 1 首先通过n 1次比较 从n个数中找出最小的 将它与第一个数交换 第一趟选择排序 结果最小的数被安置在第一个元素位置上 2 再通过n 2次比较 从剩余的n 1个数中找出最小的记录 将它与第二个数交换 第二趟选择排序 结果次小的数被安置在第二个元素位置上 3 重复上述过程 共经过n 1趟排序后 排序结束 24 例 初始 49386597761327 i 1 13 49 一趟后 13 386597764927 i 2 27 38 六趟 132738496576 97 例用选择法排序 k是一次比较中最小元素的下标 j用来控制循环 25 选择法排序源代码 VoidSelectSort inta intn inti j k for i 1 ia j k j intx a k a k a i 1 a i 1 x 26 冒泡法排序过程 1 比较最后一个数与倒数第二个数 若为逆序a n 1 a n 2 则交换 然后比较倒数第二个数与倒数第三个数 依次类推 直至第1个数和第2个数比较为止 第一趟冒泡排序 结果最小的数被安置在最前面一个元素位置上 2 对后n 1个数进行第二趟冒泡排序 结果使次小的数被安置在第n 1个元素位置 3 重复上述过程 经过n 1趟冒泡排序后 排序结束 27 例用冒泡法排序 图解 28 冒泡法排序源代码 voidbubblesort intr intn inti j temp for i 0 ii j if r j r j 1 temp r j 1 r j 1 r j r j temp 29 eg4 统计选票eg5 查找元素 30 例 计算个人所得税 应纳税所得额的计算 工资 薪金所得 以每月收入额减除费用2000元后的余额 为应纳税收入 国家对个人月收入征收个人所得税的办法如下表所示 31 分析 由每一级的级距上界组成一个数列 最后一级的上界理论上为无穷大 但计算机无法表示一个无穷大的数 所以可用一个非常大的数 如1e9来表示 假定该数列用a表示 由每一级税率组成另一个数列 假定该数列用b表示 则a和b分别为 a 0 500 2000 5000 20000 40000 60000 80000 100000 1e9 b 0 0 05 0 10 0 15 0 20 0 25 0 30 0 35 0 40 0 45 设用x表示一个人的月收入 用i表示x所对应的级数 用y表示月收入为x应缴纳的税额 则y的计算公式为 其中1 i 8 a1 a8依次为数列a中对应的级距上界 依次为数列b中对应的税率 如当x 5500时 对应的级距为3 应缴纳税额为 程序 1 二维数组的声明类型说明符数组名 常量表达式 常量表达式 引用 双下标定位例如 inta 3 4 b 5 5 b 1 2 a 2 3 2 注意两维下标均不要越界 4 2 2二维数组的声明及引用 33 2 二维数组元素的存储方式 行顺序 例doublematrix 3 2 说明 a表示数组的首地址 也是数组首行a 0 的首地址 还是a 0 首成员a 0 0 的位置 这种存储形式又称按行方式或行优先方式 a a 0 a 1 a 2 a 0 0 a 0 1 a 1 0 a 1 1 a 2 0 a 2 1 1 分行给二维数组赋初值例如 inta 3 4 1 2 3 4 5 6 7 8 9 10 11 12 2 将所有数据写在一个 内 按顺序赋值例如 inta 3 4 1 2 3 4 5 6 7 8 9 10 11 12 3 可以对每行的部分元素赋初值例如 inta 3 4 1 0 6 0 0 11 3 二维数组的初始化 35 4 定义二维数组时第一维下标可以省略eg inta 2 1 2 3 4 5 6 inta 2 1 2 3 4 5 6 charb 4 error 36 4 二维数组的使用和表示 对二维数组元素逐个赋值 用嵌套的for循环例 doublea 3 2 for i 0 i 3 i 遍历行for j 0 j 2 j 遍历行中每个元素a i j i j 37 eg1 求的转置矩阵 includeconstintM 3 constintN 4 voidmain intaa M N 3 8 2 9 4 7 3 6 5 2 8 4 intbb N M i j for i 0 i M i for j 0 j N j bb j i aa i j for i 0 i N i for j 0 j M j cout bb i j cout endl 38 eg2 矩阵元素按行从小到大排序 includeconstintM 3 constintN 4 voidmain intaa M N 3 8 2 9 4 7 3 6 5 2 8 4 inti j k for i 0 i M i for j 0 j N j for k j k N k if aa i k aa i j aa i k aa i k aa i j aa i j aa i k aa i j aa i k aa i k aa i j 加输出语句既可以看到排序结果 39 1 用typedef语句对已有类型定义别名如 typedefintInteger Integerx 5 2 用typedef语句定义一维数组类型 1 typedefintvector 10 2 typedefcharstrings 80 可以用上述类型定义对象 1 vectorv1 v2 2 stringss1 s2 s3 definetype 5 用typedef语句定义数组类型 40 3 用typedef语句定义一维数组类型 1 typedefintmatrix 5 5 2 typedefcharnameTable 10 NN 用上述类型定义相应的二维数组 1 matixmx 0 2 nameTablent 可以用用户已定义的类型再去定义数组类型 typedefvectorvectorSet 20 vectorSetvs 41 4 4字符数组与字符串 1 字符串和字符数组字符串常量 例如 china 字符数组 定义时开辟一系列连续的存储空间将字符串存入字符数组中 顺序存入一批单元中 最后由系统自动存入一个 0 作为串结束标志 例 chararray 8 Beijing 在array中从低字节到高字节依次存储了 B e i j i n g 0 42 2 用一维字符数组存储和处理字符串 1 字符数组的声明和引用 例 2 字符数组的初始化 例4 4 43 例4 4一个一维字符数组可以存储一个字符串 includevoidmain charc 10 inti for i 0 i 10 i cin c i 44 3 字符串的输入 逐个字符输入 用循环 一维 或嵌套循环 二维 将整个字符串一次输入cin 输入不含空格的字符串getline 输入整行字符串 遇 n 结束eg 输入 Mary Smith 18 表示空格 charfirstName 10 charlastName 10 cin firstName lastname firstName Mary lastName Smith 45 charinputStr 20 getline cin inputStr 输入整个16个字符cin getline 数组名 指定长度 n 从键盘输入一个以回车为结束标志的字符串或按指定长度 含有 0 输入字符串 46 47 4 字符串的输出 逐个字符输出 用循环 一维 或嵌套循环 二维 将整个字符串一次输出注意 输出字符不包括 0 输出字符串时 cout的输出项是字符数组名 输出时遇到 0 结束 48 eg chararray 8 Beijing cout array endl array 5 0 cout array endl 结果 BeijingBeiji 49 5 二维字符数组 二维字符数组每行存储一个字符串 能够同时保存若干个字符串 最多能保存的字符串的个数等于该数组的行容量 chara 7 4 sun mon tue wed thu fri sat charb 8 well good middle pass bad charc 6 10 int double char chard 10 20 例4 5 50 例4 5输出一个钻石图形 includevoidmain chardiamond 5 inti j for i 0 i 5 i for j 0 j 5 j cout diamond i j cout endl 运行结果 51 4 4 2字符串处理函数 strcat 连接 strcpy 复制 strcmp 比较 strlen 求长度 strlwr 转换为小写 strupr 转换为大写 上述函数包含在头文件中 52 1 字符串长度函数 intstrlen constchars 实参可以是一个字符串常量 可以是一个一维字符数组名 可以是二维字符数组中的行元素 只带行下标的单下标变量 例如 53 2 字符串复制函数 char strcpy chars constchar