数据的组织结构ppt课件.ppt

第4章数据的组织结构 一 4 3字符串的组织 4 2利用一维数组组织数据的应用实例 4 1数组类型 4 4常用的字符串标准函数及应用实例 4 5二维数组 1 4 1数组类型 数组类型的应用背景 1 同时存在若干个用来描述同一性质且不同个体的数据 同质数据 2 只有将这些数据组织在一起形成批量数据 共同参与处理 很多操作才具有实际意义 例如 在某个部门中 需要由全体职工推选一名办公室主任 假设有10名候选人准备参与竞选 希望编写一个程序 统计每个候选人的得票数量及选举结果 2 一维数组类型的定义定义格式 例如 intvote 10 C语言规定 数组的下标从0开始 因此 表示这10个数据的下标为0 9变量一经定义 系统就要为它分配相应的存储空间 在C程序中 系统将会为每个数组型变量分配一片连续的存储空间 所需要分配的存储空间总数将取决于包含的元素个数和每个元素需要的存储空间 3 一维数组的初始化基本格式为 例如 floatscore 5 9 2 9 1 8 7 9 1 8 5 4 说明 1 为数组型变量中的每一个元素都提供了一个初始值 此时 可以省略方括号内的数组元素数量 系统将根据花括号中包含的初值数目推测出数组含有的元素数量 floatscore 9 2 9 1 8 7 9 1 8 5 2 对数组型变量的前面若干个元素赋予初值 此时可以使用下面这种书写形式 intletter 26 10 9 8 7 它的执行结果是 将10 9 8 7分别赋予letter数组中下标为0 1 2 3的元素 后面的所有元素赋予初值0 3 将数组型变量中的每一个元素赋予初值0 此时 可以使用下面这种简化的书写形式 intvote 10 0 5 一维数组元素的引用及基本操作数组元素的引用 数组的赋值利用赋值语句为数组赋值for i 0 i 10 i vote i 0 调用标准输入函数为数组赋值for i 0 i 13 i scanf f 6 按照条件对数据进行筛选在遇到的许多问题中 经常需要从众多的数据中挑选出来满足一定条件的数据 这就是数据的筛选操作 在C程序中 参与筛选操作的批量数据可以采用一个一维数组型变量组织 筛选的条件用逻辑表达式表示 4 2利用一维数组组织数据的应用实例 7 例1 在某个公司中 计划由职工们推选一名办公室主任 假设有10名候选人准备参与竞选 希望编写一个程序 输入一组选举人的投票信息 统计每个候选人的得票数目及选举结果 问题分析用一维数组记录每位候选人的得票数量 投票通过循环输入介于1 10之间的整型数值来模拟的 例如 输入3代表某个职工选举编码为3的候选人 找出最多的得票数量之后 从所有的候选人中筛选出得票数量与最高得票数量相同的人 8 算法描述 9 include defineNUM10 候选人人数 main intvote NUM 0 intcode i winner 职工投票 printf nEnteryourselection n do scanf d 程序代码 10 输出选票 printf nTheamountofvotesis for i 0 ivote winner winner i 输出得票最高的所有候选人 printf nThewinner for i winner i NUM i if vote i vote winner printf 3d i 1 11 根据需求对数据进行统计为了满足特定的需要 对一组数据的某些特征进行统计是一项经常遇到的基本操作 例如 统计一段文本中某个字符出现的频率 统计学生考试的平均成绩等等都属于统计操作 统计操作的结果往往是通过对所有数据进行扫描 判断或综合加工得到的 在C程序中 参与统计操作的批量数据可以用一维数组来组织 具体统计过程可以通过逻辑判断 累计 算术运算等基本操作手段实现 12 例2 在一段文本中 可能会出现各式各样的字符 编写一个程序 从键盘读入一行文本 完成统计每个英文字母出现频率的操作 问题分析用一维数组构造26个用于记录每个字母出现次数的累加器 对于输入的文本字符 可以在读取时检查一下是否为英文字母 而不需要将其存储起来 13 算法描述 14 include defineNUM26main intletter NUM 0 charch inti printf nEntertextline n while ch getchar n if A ch 程序代码 15 例3 每年中央电视台都要举办青年歌手大奖赛 假设有13位评委参与评分工作 计算每位歌手最终得分的方法是 首先去掉一个最高分和一个最低分 然后计算剩余11个分数的平均值 所得结果就是选手的最终得分 希望编写一个程序 帮助工作人员计算每个歌手的分数 问题分析用一维数组存储13位评委给出的分数寻找最高分和最低分计算剩余11个分数的平均分 16 算法描述 17 include defineNUM13main floatscore NUM inti minValue maxValue floatsum 输入13位评委给出的分数 printf nEnter13score for i 0 i NUM i scanf f 程序代码 18 找出最高分 最低分 并同时累加13个分数的总和 minValue score 0 maxValue score 0 sum score 0 for i 1 imaxValue maxValue score i sum sum score i 计算并输出歌手的最终得分 sum sum minValue maxValue NUM 2 printf nFinalscoreis 6 2f sum 19 查找问题所谓查找是指根据某个给定的条件 在一组数据中搜索是否存在满足该条件的数据的过程 如果存在 则表示查找成功 给出成功的标志 否则表示查找不成功 给出失败的标志 在程序中 查找操作的结果经常被用来作为是否执行某项后续操作的决策依据 20 例4 已知某个班级35名学生的某门课程的考试成绩 请编写一个程序 查看在这个班级中是否存在不及格的学生 问题分析用一维数组记录每位学生的考试成绩 下标表示每个学生的编号 元素内容表示考试成绩 查找可以通过从前往后依次查看每个元素内容的过程实现 21 算法描述 22 include include defineNUM35 学生人数 main intscore NUM inti 随机产生35个考试成绩 randomize for i 0 i NUM i score i random 100 显示35名学生的考试成绩 for i 0 i NUM i printf nNo d d i 1 score i 程序代码 23 顺序查找是否存在不及格的学生 for i 0 i NUM i if score i 60 break 输出查找结果 if i NUM printf nNotallpass elseprintf Allpass 24 例5 已知一个按非递减有序排列的整型数列 12 23 30 45 48 50 67 82 91 103 请编写一个程序 查找其中是否存在与给定key相等的数值 问题分析二分查找是指每次用key与位于查找区间中央位置的元素进行比较 比较结果将会产生下面三种情形之一 如果相等 说明查找成功 如果key小于中央位置的元素 说明如果存在这样的元素 应该位于查找区间的前半部分 此时可以将查找区间缩减为原来的一半 并在这一半的区间中继续用相同的方式查找 如果key大于中央位置的元素 说明如果存在这样的元素 应该位于查找区间的后半部分 同样可以将查找区间缩减为原来的一半 并在这一半的区间中继续用相同的方式查找 可以看出 用key与当前查找区间中央位置的元素比较后 不是找到了 就是将查找区间缩小了一半 直到查找区间不存在了 说明没有要找的key 25 算法描述 26 27 include defineNUM10main intvalue NUM 12 23 30 45 48 50 67 82 91 103 非递减整型数列 intlow high mid key printf nEnterakey 输入查找的数值 scanf d 确认循环正常出口 程序代码 28 用递归函数实现二分查找 intsearch intvalue intkey intlow inthigh 二分查找的递归函数 intmid if low high return 1 查找区间为空 mid low high 2 求中间位置 if value mid key returnmid 得到查找的数据位置 if key value mid returnsearch value key low mid 1 在下半区查找 elsereturnsearch value key mid 1 high 在上半区查找 29 排序问题将一组无序的数列重新排列成非递减或非递增的顺序是一种经常需要的操作 例如 在管理学生成绩的应用程序中 可以用一个数列表示一个班级的学生成绩 并按照从高到低的顺序重新排列 以便确定获得奖学金的学生 30 例6 假设用户通过键盘输入一个整型数列 请编写一个程序 将其按照从小到大的顺序重新排列 问题分析首先从n个数据中选择一个最小的数据 并将它交换到第1个位置 然后再从后面n 1个数据中选择一个最小的数据 并将它交换到第2个位置 以此类推 直至最后从两个数据中选择一个最小的数据 并将它交换到第n 1个位置为止 整个排序操作结束 31 算法描述 32 include defineNUM10 参与排序的数据个数 main intdata NUM 存放参与排序的所有整数 inti j minValue temp 通过键盘输入待排序的整型数列 printf nEnter dintegers NUM for i 0 i NUM i scanf d 程序代码 33 for i 0 i NUM 1 i minValue i for j i 1 j NUM j if data j data minValue minValue j if minValue i 交换 temp data i data i data minValue data minValue temp 输出排序后的结果 printf nOrderinglistis n for i 0 i NUM i printf 5d data i 34 字符串的组织形式字符串是指一个有限长度的字符序列 字符串常量用一对双引号 括起来 字符串中所包含的字符个数被称为字符串长度 4 3字符串的组织 35 字符串的初始化charstr Cprogram charstr C p r o g r a m 0 对于这种初始化形式 系统将其视为字符操作 而不是字符串操作 因此不会在尾部添加结束符 0 Cprogram 的存储状态 36 字符串的输入输出1 gets str 2 scanf s str gets 函数以换行符或文件结束符EOF作为输入的结束标志 因此在输入的字符串中允许包含空格和制表符 而scanf 函数则以空格 制表符 换行符和文件结束符EOF作为输入的结束标志 因此 在输入的字符串中不允许包含这些字符 如果包含了它们 将作为字符串输入的结束标志处理 37 字符串的输出1 puts str 2 printf s str puts将字符串的内容显示到标准输出设备 屏幕上 并换行 38 字符串标准函数在C语言的标准函数库中 提供了30余种与字符串处理有关的标准函数 从而大大地提高了字符串处理的能力 降低了字符串处理的复杂程度 4 4常用的字符串标准函数及应用实例 39 字符串转换成数值类型atof str atoi str atol str 其中str是一个字符串 atof 的返回类型是double 它可以将字符串str转换成一个双精度数值 atoi 的返回类型是int 它可以将字符串str转换成普通整型 atol 的返回类型是long 它可以将字符串str转换成长整型 long 例7 将用户以字符串形式输入的两个实型数值转换成double类型 并显示输出这两个实型数值及它们相加的结果 40 include includemain charnum1 20 num2 20 doubled1 d2 sum printf nEnterthefirstnumber gets num1 输入第1个用字符串表示的实型数值 printf Enterthssecondnumber gets num2 输入第2个用字符串表示的实型数值 d1 atof num1 将第1个字符串转换成double类型 d2 atof num2 将第2个字符串转换成double类型 sum d1 d2 将2个double类型数值相加 printf n s s 3lf num1 num2 sum 显示结果 程序代码 41 数值类型转换成字符串itoa num str radix ltoa num str radix 其中str用于存放结果的字符串 radix是用户指定的进制数 它的取值必须介于2 36之间 在itoa 函数中的num是一个int类型的数值 在ltoa 函数中的num是一个long类型的数值 例8 将用户输入的长整型 long类型 数值转换成以字符串形式表示的十六进制 八进制和二进制数值 并显示输出 42 include includemain charstr 33 longvalue printf nEnteralongnumber scanf ld 程序代码 43 大小写转换strlwr str strupr str str是一个字符串 标准函数strlwr 可以将字符串str中出现的所有大写字母转换成小写字母 标准函数strupr 可以将字符串str中出现的所有小写字母转换成大写字母 例9 统计一段文本中每个英文字母出现的次数 44 include include include defineNUM26main intletter NUM 0 用于存放统计结果的一维数组 charstr 80 存放以字符串形式输入的文本 inti printf nEnteratextline gets str 输入文本 strupr str 将文本中的所有小写字母转换成大写字母 for i 0 str i 0 i 统计每个字母出现的次数 if isalpha str i isalpha函数判断是否英文字母 letter str i A letter str i A 1 for i 0 i NUM i 输出统计结果 printf n c d A i letter i 程序代码 45 计算字符串长度strlen str 这个函数的功能是返回字符串中所包含的字符个数 即字符串长度 字符串结束标志 0 不计算在内 字符串比较strcmp str1 str2 两个字符串进行比较时将依据每个字符对应的ASCII编码决定其大小 例10 假设用户的密码是 administrators 下面这个程序将用于检测用户输入的密码是否正确 如果不正确 给出相应的提示信息 并请求用户重新输入 46 include includemain charpassword 20 存放用户输入的密码 printf nEnterpassword gets password 输入密码 检测用户输入的密码 如果不正确 给出提示 并请求重新输入 while strcmp password administrators 0 printf nInvalidpassword n n printf Enterpassword again gets password printf OK 输入正确 显示 OK 程序代码 47 字符串拷贝strcpy str1 str2 其中str2是将要被拷贝的字符串 str1是用于存放拷贝结果的存储区域 字符串连接strcat str1 str2 其中str1和str2是两个字符串 这个函数的功能是 将str2连接在str1之后 并在结束处添加一个字符串结束符 0 例11 根据用户的选择输出相应的字符串 48 include includemain charstr1 80 Thisisa charstr2 program charstr3 Java charstr4 Pascal charstr5 C charstr6 C intchoice printf n MENU n 菜单 printf nJava 1 printf nPascal 2 printf nC 3 printf nC 4 printf nchoice scanf d 用户做出选择 程序代码 49 switch choice 根据用户的选择拼接字符串 case1 strcat str1 str3 strcat str1 str2 break case2 strcat str1 str4 strcat str1 str2 break case3 strcat str1 str5 strcat str1 str2 break case4 strcat str1 str6 strcat str1 str2 break default strcpy str1 Error break printf n s str1 显示字符串 50 求子串strstr str1 str2 其中str1是主串 str2是子串 如果在主串str1中存在子串str2 函数将返回子串str2在主串中第一次出现的 第一个字符的存储位置 否则返回空 确定某个字符在字符串中出现的位置strchr str1 ch 其中str1是一个给定的字符串 ch是所要查找的字符 如果在str1中存在字符ch 函数返回ch在字符串str1中第一次出现的存储位置 否则返回空 例12 文本变换 51 include include includemain inti chartext 1000 gets text 输入文本内容 for i 0 text i 0 i if isalnum text i text i text i 5 变换 puts text for i 0 text i 0 i if isalnum text i text i text i 5 还原 puts text 程序代码 52 4 5二维数组 二维数组的定义定义格式 例如 intvalue 5 4 value数组的每个元素类型为int 包含5行4列共20个元素一旦定义了一个二维数组型变量 系统就会立即为其分配相应的存储空间用于存放数组中的每个元素 存储空间的数量取决于数组元素的类型和所