《数据的组织结构-一维数组》由会员分享，可在线阅读，更多相关《数据的组织结构-一维数组（48页珍藏版）》请在金锄头文库上搜索。
1、数据的组织结构数据的组织结构数组数组第四章第四章一、一维数组二、一维数组的编程实例三、字符数组与字符串四、二维数组1n数组类型的应用背景数组类型的应用背景同时存在若干个用来描述同一性质同时存在若干个用来描述同一性质且不同个体的数据且不同个体的数据将这些数据组织在一起形成批量数将这些数据组织在一起形成批量数据，共同参与处理，很多操作才具据，共同参与处理，很多操作才具有实际意义有实际意义2例如：例如：输入输入100名学生的成绩，要求输出高于名学生的成绩，要求输出高于平均分的所有成绩。平均分的所有成绩。单一数据考虑：单一数据考虑：用用100个变量个变量(a1,a2,a100)存放学生成绩，与平均成绩
2、存放学生成绩，与平均成绩(ave)进进行判断，行判断，if(a1ave)printf(“%fn”,a1);if(a2ave)printf(“%fn”,a2);用数组用数组：for（i=1；iave)printf(“%fn”,ai);数组是一种用来组织数组是一种用来组织批量数据批量数据的数据类型。的数据类型。3一、一维数组一、一维数组n一维数组：一维数组：由若干具有由若干具有相同类型相同类型的数据元素组成。每个元的数据元素组成。每个元素仅使用素仅使用一个序号（下标）一个序号（下标）唯一标识。唯一标识。n一维数组定义一维数组定义 长度长度 ； intint a10 a10；元素序号（下标）从元素序
3、号（下标）从0 0开始，即开始，即a0 a1 a9a0 a1 a9长度长度即为元素的数量，必须给定即为元素的数量，必须给定数组名的命名与通常变量命名方式相同数组名的命名与通常变量命名方式相同系统为它分配一片系统为它分配一片连续连续的存储空间的存储空间n数组元素的引用形式数组元素的引用形式 数组名数组名 下标下标 下标为整型表达式下标为整型表达式4u 说明：说明：若数组长度为若数组长度为 n n，下标的下限从下标的下限从0 0开始，开始，上限到上限到 n-1n-1。注意下标不要越界，否则将产生不可注意下标不要越界，否则将产生不可预料的运行结果，预料的运行结果， C C语言并不检验下语言并不检验下
4、标是否越界标是否越界C C语言规定语言规定，数组名数组名是一个地址常量，是一个地址常量，代表所分配的内存区域的代表所分配的内存区域的起始地址起始地址5数组的存储实现数组的存储实现例如：例如：intint a8; a8;为为a a分配的存储空间如图：分配的存储空间如图：所占字节数所占字节数：sizeofsizeof( (元素类型元素类型)元素个数元素个数6n一维数组初始化一维数组初始化在在定义数组定义数组时对数组元素赋以初值时对数组元素赋以初值inta10=0,1,2,3,4,5,6,7,8,9;在对在对全部全部数组元素赋初值时，数组长度可数组元素赋初值时，数组长度可以省略以省略inta=0,1
5、,2,3,4,5,6,7,8,9;只给只给一部分一部分赋值，未设定初值的自动被设赋值，未设定初值的自动被设定为定为0 0，数组长度不能省略数组长度不能省略inta10=0,1,2,3,4;intdigit10=0;有几个初值，数组默认大小就是多大有几个初值，数组默认大小就是多大7n一维数组的引用一维数组的引用利用赋值语句为数组元素利用赋值语句为数组元素赋值赋值for(i=0;i10;i+)ai=0;数组的数组的输入输入for(i=0;i10;i+)scanf(“%f”,&scorei);数组的数组的输出输出for(i=0;i10;i+)printf(“%6.2f”,scorei);8 某个公司
6、计划由职工推选一名办公室主某个公司计划由职工推选一名办公室主任。假设有任。假设有1010名候选人名候选人准备参与竞选。编写准备参与竞选。编写一个程序，输入一组选举人的投票信息，统一个程序，输入一组选举人的投票信息，统计每个候选人的得票数目及选举结果。计每个候选人的得票数目及选举结果。 实例实例1根据条件对数据进行筛选根据条件对数据进行筛选二、二、一维数组的编程实例一维数组的编程实例P81，例，例4-19问题分析问题分析记录每位候选人的记录每位候选人的得票数量得票数量（一维数组）（一维数组）投投票票可可通通过过循循环环输输入入110之之间间的的整整型型数数值值来来模模拟拟，需需对对候候选选人人进
7、进行行编编号号。例例如如，输输入入3 3代代表表某某个职工选举编码为个职工选举编码为3 3的候选人的候选人找出找出最多的得票数量最多的得票数量再再从从所所有有的的候候选选人人中中筛筛选选出出得得票票数数量量与与最最高高得得票数量相同的人票数量相同的人（可能有多人）（可能有多人）10数据对象数据对象每位候选人的每位候选人的得票数量得票数量 intint vote10 vote10投票时投票时输入的编码输入的编码 intint code code最高最高得票数量得票数量 intint winner winner约束条件约束条件假设投票时以假设投票时以 0 0 作为作为输入的结束标志输入的结束标志输
8、入输入无效编码无效编码的检验的检验11算法描述算法描述 输入选票输入选票code选票合法？选票合法？code0？code-1计数器加计数器加1输出错误信息输出错误信息code0？YNNYYN职工投票职工投票12#include #define NUM 10 /* 候候选人人数人人数 */main( ) int voteNUM = 0; int code, i, winner; /* 职工投票工投票 */ printf(nEnter your selection:n); do scanf(%d, &code); if (codeNUM) /* 检验输入的入的编码是否有效是否有效 */ print
9、f(nInvalid vote.); else if (code!=0) votecode-1 = votecode-1+1; /* 累加票数累加票数 */ while (code!=0);程程序序代代码码13 /* 输出出选票票 */ printf(n The amount of votes is :); for (i=0; iNUM; i+) printf(%4d, votei); /* 计算最高得票数量算最高得票数量 */ winner = 0; for (i=1; ivotewinner) winner = i; /* 输出得票最高的所有候出得票最高的所有候选人人 */ printf(
10、nThe winner :); for (i=winner; iNUM; i+) if (votei=votewinner) printf(%3d, i+1); 问题：问题：改为改为winner = 0;for (i=1; i=votewinner) winner = i;后面是否修改，如何修改后面是否修改，如何修改14为了满足特定的需要，对一组数据的某些特征为了满足特定的需要，对一组数据的某些特征进行统计是一项经常遇到的基本操作进行统计是一项经常遇到的基本操作例如例如统计一段文本中某个字符出现的频率统计一段文本中某个字符出现的频率统计学生考试的平均成绩统计学生考试的平均成绩在在C程序中，参与
11、统计操作的批量数据可以用程序中，参与统计操作的批量数据可以用一一维数组维数组来组织，具体统计过程可以通过来组织，具体统计过程可以通过逻辑判断逻辑判断、累计累计、算术运算算术运算等基本操作手段实现等基本操作手段实现根据需求对数据进行统计根据需求对数据进行统计15教材教材P84例例4-2：编写一个程序，从键盘：编写一个程序，从键盘读入一行文本，统计每个英文字母出现的读入一行文本，统计每个英文字母出现的频率频率该题与上一章的该题与上一章的3.5例例5的方法类似的方法类似基本方法基本方法用一维数组构造用一维数组构造26个用于记录每个字母出现次个用于记录每个字母出现次数的计数器数的计数器用数组下标来区分
12、不同字母，且顺序一致用数组下标来区分不同字母，且顺序一致输入的字符如果是字母，则按其在字母表中的输入的字符如果是字母，则按其在字母表中的顺序找到相应的计数器顺序找到相应的计数器16算法描述算法描述 开始开始ch=getchar() 输出统计结果输出统计结果 相应计数器加相应计数器加1结束结束是大写是大写是小写是小写相应计数器加相应计数器加1ch!= nYNYNNY17#include#defineNUM26main()intletterNUM=0;charch;inti;printf(nEntertextlinen);while(ch=getchar()!=n)if(A=ch&ch=Z) /*
13、检测是否是否为大写字母大写字母*/letterch-A=letterch-A+1;elseif(a=ch&ch=z)/*检测是否是否为小写字母小写字母*/letterch-a=letterch-a+1;/*输出每个英文字母出现的次数输出每个英文字母出现的次数*/for(i=0;iNUM;i+)printf(n%c:%d,A+i,letteri);问题：问题：若只输出计数次数若只输出计数次数大于大于0的结果，应的结果，应如何修改？如何修改？18实例实例2 2： 大奖赛大奖赛 每年中央电视台都要举办青年歌手大奖赛。每年中央电视台都要举办青年歌手大奖赛。假设有假设有1313位评委参与评分工作。计算每
14、位歌位评委参与评分工作。计算每位歌手手最终得分的方法最终得分的方法是：首先去掉一个最高分是：首先去掉一个最高分和一个最低分，然后计算剩余和一个最低分，然后计算剩余1111个分数的平个分数的平均值，所得结果就是选手的最终得分。希望均值，所得结果就是选手的最终得分。希望编写一个程序，帮助工作人员计算每个歌手编写一个程序，帮助工作人员计算每个歌手的分数。的分数。19数据对象分析数据对象分析用一维数组存储用一维数组存储 1313位评委给出的分数位评委给出的分数 float score13float score13寻找最高分和最低分寻找最高分和最低分 float float maxValuemaxVal
15、ue，minValueminValue 计算剩余计算剩余1111个分数的平均分个分数的平均分 float sumfloat sum 20算法描述算法描述 21#include #define NUM 13 /*评委人数评委人数*/main( ) float scoreNUM; int i; float minValue, maxValue, sum; /* 输入输入13位评委给出的分数位评委给出的分数 */ printf(nEnter 13 score:); for (i=0; iNUM; i+) scanf(%f, &scorei); 程序代码程序代码 22/* 找出最高分、最低分，并同时累
16、加找出最高分、最低分，并同时累加13个分数的总和个分数的总和 */ minValue = score0; maxValue = score0; sum = score0; for (i=1; iNUM; i+) if (scoreimaxValue) maxValue = scorei; sum = sum+scorei; /* 计算并输出歌手的最终得分计算并输出歌手的最终得分 */ sum = (sum- minValue-maxValue)/(NUM-2); printf(nFinal score is %6.2f, sum);23排序问题排序问题将一组将一组无序的数列无序的数列重新排列成
17、非递重新排列成非递减或非递增的顺序是一种经常需要减或非递增的顺序是一种经常需要的操作。例如，在管理学生成绩的的操作。例如，在管理学生成绩的应用程序中，可以用一个数列表示应用程序中，可以用一个数列表示一个班级的学生成绩，并按照从高一个班级的学生成绩，并按照从高到低的顺序重新排列，以便确定获到低的顺序重新排列，以便确定获得奖学金的学生得奖学金的学生24 题目题目用简单选择法对从键盘输入的用简单选择法对从键盘输入的1010个整数由个整数由小到大排序（升序）。小到大排序（升序）。实例实例3选择排序选择排序P93例例4-6n数据对象考虑数据对象考虑n应保存应保存1010个整数个整数, ,设置数组设置数组
18、 a a1010n每个元素存一个数每个元素存一个数n第一个数保存在第一个数保存在 a0 a0 中中25n算法思想：算法思想：利用数组存放利用数组存放n个数据，并在此数组中进个数据，并在此数组中进行排序行排序针对一组针对一组n个数据个数据a0、a1、an-1选出最小的数据，与第一个数据进行交换选出最小的数据，与第一个数据进行交换从剩余的从剩余的n-1个数据中选出最小的数据，个数据中选出最小的数据，与剩余的与剩余的n-1个数据的第一个数据进行交换个数据的第一个数据进行交换进行进行n-1遍处理后，数组形成升序排列遍处理后，数组形成升序排列26选择排序过程：选择排序过程：P93原始数据：原始数据：23
19、163295667863minimini第一趟后：第一趟后：61632956237863minmin第二趟后：第二趟后：69321656237863imin27算法：算法：、从键盘输入、从键盘输入N个整数（即个整数（即10个）。个）。、for(i=0;iN-1;i+)2.1设第设第i个值为最小值个值为最小值(min)。2.2for(j=i+1;jN;j+)如果第如果第j个值比第个值比第min个值小个值小,则则minj2.3if(i!=min)aiamin、输出。输出。流程图流程图P94图图4-928最小值下标最小值下标minValue0 i iN-1minValue!=i交换交换YYNN开始开
20、始输入待排序整数数列输入待排序整数数列i+1 iiminValue显示排序后的结果显示排序后的结果 结束结束n算法描述算法描述显示整数数列显示整数数列29#include#defineN10/*参与排序的数据个数参与排序的数据个数*/main()intaN;/*存放参与排序的所有整数存放参与排序的所有整数*/inti,j,min,t;/*通过键盘输入待排序的整型数列通过键盘输入待排序的整型数列*/printf(Input10numbers:n);for(i=0;iN;i+)scanf(%d,&ai);（接下一页）接下一页）arrsort.c程序实现程序实现30for(i=0;iN-1;i+)/
21、*排序排序*/min=i;for(j=i+1;jN;j+)if(ajamin)min=j;if(i!=min)t=ai;ai=amin;amin=t;printf(Thesortednumbers:n);for(i=0;iN;i+)/*显示排序后结果显示排序后结果*/printf(%d,ai);31for(i=0;i10;i+)/*产生随机数产生随机数*/ai=1+rand()%10;printf(“Therandnumbers:n”);/*显示显示*/for(i=0;i10;i+)printf(%d,ai);由随机函数产生由随机函数产生10个数，放入数组中个数，放入数组中,需需要要#incl
22、ude数据产生数据产生 待排序的数值通过随机数产生，以便模拟待排序的数值通过随机数产生，以便模拟键盘输入。键盘输入。32|随机数的产生随机数的产生C语言的标准库提供了函数语言的标准库提供了函数rand()和和srand()。可实现如模拟和游戏等方面的应用。可实现如模拟和游戏等方面的应用。u函数函数rand和和srand的函数原型在的函数原型在stdlib.h中中u函数函数rand()产生一个在产生一个在0到到RAND_MAX之之间的整数值（间的整数值（随机数随机数）。）。RAND_MAX是符是符号常量，其值为号常量，其值为32767。u调用形式调用形式：n=rand（）；（）；33u可缩放和移
23、动函数可缩放和移动函数rand所产生的值，所产生的值，确定指定范围确定指定范围。一般方法：一般方法：n=a+rand()%b;其中：其中：a为移动值为移动值，所需的连续整数值范围内的第一个数；，所需的连续整数值范围内的第一个数；b是比例因子是比例因子，等于所需的连续整数值范围的宽度。，等于所需的连续整数值范围的宽度。u函数函数srand使程序随机化。需要设置使程序随机化。需要设置随机种子随机种子。srand（time（NULL）函数函数time的函数原型的函数原型time.h中。中。34nintrandom(intnum)返回一个返回一个0num-1之间的数之间的数k=random(10);n
24、voidrandomize()初始化随机数发生器初始化随机数发生器使用例：使用例：randomize();for(i=0;i10;i+)/*产生随机数产生随机数*/ai=1+random(10);另一组随机函数：另一组随机函数：35查找问题查找问题查找是指根据某个给定的条件，在一组数据查找是指根据某个给定的条件，在一组数据中搜索是否存在满足该条件的数据的过程中搜索是否存在满足该条件的数据的过程查找有查找有2种结果种结果满足给定的条件的数据存在，即查找成功，给满足给定的条件的数据存在，即查找成功，给出成功的标志出成功的标志该数据不存在，即查找不成功，应给出失败的该数据不存在，即查找不成功，应给出
25、失败的标志标志在程序中，查找操作的结果经常被用来作为在程序中，查找操作的结果经常被用来作为是否执行某项后续操作的决策依据是否执行某项后续操作的决策依据36实例实例4：请编写一个程序，查看在某班：请编写一个程序，查看在某班35名学生的某门课程的考试成绩中，是否存名学生的某门课程的考试成绩中，是否存在不及格的学生在不及格的学生问题分析问题分析用一维数组记录每位学生的考试成绩，下标表用一维数组记录每位学生的考试成绩，下标表示每个学生的编号，元素内容表示考试成绩示每个学生的编号，元素内容表示考试成绩通过从前往后依次查看每个元素内容的过程实通过从前往后依次查看每个元素内容的过程实现查找现查找37算法描述
26、算法描述开始开始结束结束顺序查找不及格的学生顺序查找不及格的学生 显示显示35名学生的成绩名学生的成绩存在不及格学生存在不及格学生输出输出Notallpass输出输出Allpass随机产生随机产生35名学生的成绩名学生的成绩YN38#include #include #define NUM 35 /*学生人数学生人数*/main( ) int scoreNUM, i; randomize( ); for (i=0; iNUM; i+) /* 随机随机产生生35个考个考试成成绩 */ scorei = random(100); for (i=0; iNUM; i+) /* /* 输出输出3535
27、个考试成绩个考试成绩 * */ / printf(nNo.%d: %d, i+1, scorei); for (i=0; iNUM; i+) if (scorei60) break; if (i highhighmidlow43开始开始结束结束low=0；high=NUM-1；mid=中央位置中央位置low=highNvaluemid=keyvaluemidkeylow=mid+1high=mid-1YYNNY44#include #define NUM 10main () int valueNUM=05,13,19,21,37,56,64,75,80,88; int low,high,mid
28、,key; printf(nEnter a key:); scanf(%d, &key);/ 二分查找 ; / 输出查找结果 if( low=high ) printf(n%d is found at %d, key, mid); else printf(n%d is not found., key); 45/有序表二分查找 low = 0; high = NUM-1; / 置区间初值 while (low = high) mid = (low + high) / 2; if(valuemid=key ) break; / 找到待查元素 if ( valuemidkey ) low = mid
29、 + 1; / 继续在后半区间进行查找 else high = mid - 1; / 继续在前半区间进行查找 46顺序查找的特点顺序查找的特点优点是在查找前没有先决条件，在任何情况下都优点是在查找前没有先决条件，在任何情况下都可以使用可以使用缺点是效率低缺点是效率低若待查找的数据是有序的，则可以使用二分若待查找的数据是有序的，则可以使用二分查找查找47第第4 4章章 第一部分作业第一部分作业阅读教科书第四章（一维数组）阅读教科书第四章（一维数组）一、阅读练习一、阅读练习P1181，2二、编程练习二、编程练习P1194，5，6P1231三、上机题（事先准备好）三、上机题（事先准备好） P1201 P1196， P123编程题编程题148
