数据的组织结构

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 数据的组织结构（一）,4.3,字符串的组织,4.2,利用一维数组组织数据的应用实例,4.1,数组类型,4.4,常用的字符串标准函数及应用实例,4.5,二维数组,1,课前复习,前三章,数据类型,-,数据结构的一种方式,学习新的数据的组织形式,-,数据结构的另一种方式,2,4.1,数组类型,数组类型的应用背景,（,1,）同时存在若干个用来描述同一性质且不同个体的数据。,（,2,）只有将这些数据组织在一起形成批量数据，共同参与处理，很多操作才具有实际意义。,例如：在某个部门中，需要由全体职工推选一名办公室主任。假设有,10,名候选人准备参与竞选。希望编写一个程序，统计每个候选人的得票数量及选举结果。,3,一维数组类型的定义,定义格式：, ,；,例如：,int vote10;,C,语言规定：数组的下标从,0,开始，因此，表示这,10,个数据的下标为,09,变量一经定义，系统就要为它分配相应的存储空间。在,C,程序中，系统将会为每个数组型变量分配一片连续的存储空间，所需要分配的存储空间总数将取决于包含的元素个数和每个元素需要的存储空间。,4,一维数组的初始化,基本格式为：, =,，,，,.,，,；,例如：,float score5 = 9.2, 9.1, 8.7, 9.1, 8.5;,5,说明：,1,）为数组型变量中的每一个元素都提供了一个初始值。此时，可以省略方括号内的数组元素数量。系统将根据花括号中包含的初值数目推测出数组含有的元素数量。,float score = 9.2, 9.1, 8.7, 9.1, 8.5;,2,）对数组型变量的前面若干个元素赋予初值。此时可以使用下面这种书写形式：,int letter26 = 10, 9, 8, 7;,它的执行结果是：将,10,、,9,、,8,、,7,分别赋予,letter,数组中下标为,0,、,1,、,2,、,3,的元素，后面的所有元素赋予初值,0,。,3,）将数组型变量中的每一个元素赋予初值,0,。此时，可以使用下面这种简化的书写形式：,int vote10 = 0;,6,一维数组元素的引用及基本操作,数组元素的引用,数组的赋值,利用赋值语句为数组赋值,for (i=0; i10; i+),votei = 0;,调用标准输入函数为数组赋值,for (i=0; i13; i+) ,scanf(“%f”, ,数组的输出,for (i=0; i10; i+) ,printf(“%5d”, votei);,7,按照条件对数据进行筛选,在遇到的许多问题中，经常需要从众多的数据中挑选出来满足一定条件的数据，这就是数据的筛选操作。在,C,程序中，参与筛选操作的批量数据可以采用一个一维数组型变量组织，筛选的条件用逻辑表达式表示。,4.2,利用一维数组组织数据的应用实例,8,例,1,：在某个公司中，计划由职工们推选一名办公室主任。假设有,10,名候选人准备参与竞选。希望编写一个程序，输入一组选举人的投票信息，统计每个候选人的得票数目及选举结果。,问题分析,用一维数组记录每位候选人的得票数量。,投票,通过循环输入介于,110,之间的整型数值来模拟的。例如，输入,3,代表某个职工选举编码为,3,的候选人。,找出最多的得票数量之后，从所有的候选人中筛选出得票数量与最高得票数量相同的人。,9,算法描述,10,#include ,#define NUM 10 /*,候选人人数 *,/,main( ),int voteNUM = 0;,int code, i, winner;,/*,职工投票 *,/,printf(nEnter your selection:n);,do ,scanf(%d, ,if (codeNUM) ,/*,检验输入的编码是否有效 *,/,printf(nInvalid vote.);, else ,if (code!=0),votecode-1 = votecode-1+1;,/*,累加票数 *,/, while (code!=0);,程序代码,11,/*,输出选票 *,/,printf(n The amount of votes is :);,for (i=0; iNUM; i+) ,printf(%4d, votei);,/*,计算最高得票数量 *,/,winner = 0;,for (i=1; ivotewinner),winner = i;,/*,输出得票最高的所有候选人 *,/,printf(nThe winner :);,for (i=winner; iNUM; i+) ,if (votei=votewinner),printf(%3d,i+1);,12,根据需求对数据进行统计,为了满足特定的需要，对一组数据的某些特征进行统计是一项经常遇到的基本操作。例如，统计一段文本中某个字符出现的频率；统计学生考试的平均成绩等等都属于统计操作。统计操作的结果往往是通过对所有数据进行扫描、判断或综合加工得到的。在,C,程序中，参与统计操作的批量数据可以用一维数组来组织，具体统计过程可以通过逻辑判断、累计、算术运算等基本操作手段实现。,13,例,2,：在一段文本中，可能会出现各式各样的字符。编写一个程序，从键盘读入一行文本，完成统计每个英文字母出现频率的操作。,问题分析,用一维数组构造,26,个用于记录每个字母出现次数的累加器。,对于输入的文本字符，可以在读取时检查一下是否为英文字母，而不需要将其存储起来。,14,算法描述,15,#include ,#define NUM 26,main( ),int letterNUM = 0;,char ch;,int i;,printf(nEnter text linen);,while (ch=getchar() != n) ,if (A=ch & ch=Z) /*,检测是否为大写字母 *,/,letterch-A = letterch-A+1;, else ,if (a=ch & ch=z) /*,检测是否为小写字母 *,/,letterch-a = letterch-a+1;,/*,输出每个英文字母出现的次数,*,/,for (i=0; iNUM; i+),printf(n%c:%d, A+i, letteri);,程序代码,16,例,3,：每年中央电视台都要举办青年歌手大奖赛。假设有,13,位评委参与评分工作。计算每位歌手最终得分的方法是：首先去掉一个最高分和一个最低分，然后计算剩余,11,个分数的平均值，所得结果就是选手的最终得分。希望编写一个程序，帮助工作人员计算每个歌手的分数。,问题分析,用一维数组存储,13,位评委给出的分数,寻找最高分和最低分,计算剩余,11,个分数的平均分,17,算法描述,18,#include ,#define NUM 13,main( ),float scoreNUM; */,int i, minValue, maxValue;,float sum;,/*,输入,13,位评委给出的分数 *,/,printf(nEnter 13 score:);,for (i=0; iNUM; i+),scanf(%f, ,程序代码,19,/*,找出最高分、最低分，并同时累加,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);,20,查找问题,所谓查找是指根据某个给定的条件，在一组数据中搜索是否存在满足该条件的数据的过程。如果存在，则表示查找成功，给出成功的标志；否则表示查找不成功，给出失败的标志。在程序中，查找操作的结果经常被用来作为是否执行某项后续操作的决策依据。,21,例,4,：已知某个班级,35,名学生的某门课程的考试成绩。请编写一个程序，查看在这个班级中是否存在不及格的学生。,问题分析,用一维数组记录每位学生的考试成绩，下标表示每个学生的编号，元素内容表示考试成绩。,查找可以通过从前往后依次查看每个元素内容的过程实现。,22,算法描述,23,#include ,#include ,#define NUM 35 /*,学生人数*,/,main( ),int scoreNUM;,int i;,/*,随机产生,35,个考试成绩 *,/,randomize( );,for (i=0; iNUM; i+) ,scorei = random(100);,/*,显示,35,名学生的考试成绩*,/,for (i=0; iNUM; i+) ,printf(nNo.%d: %d, i+1, scorei);,程序代码,24,/*,顺序查找是否存在不及格的学生*,/,for (i=0; iNUM; i+) ,if (scorei60) break;,/*,输出查找结果*,/,if (iNUM),printf(nNot all pass.);,else,printf(All pass.);,25,例,5,：已知一个按非递减有序排列的整型数列（,12,23,30,45,48,50,67,82,91,103,）。请编写一个程序，查找其中是否存在与给定,key,相等的数值。,问题分析,二分查找是指每次用,key,与位于查找区间中央位置的元素进行比较，比较结果将会产生下面三种情形之一：,如果相等，说明查找成功。,如果,key,小于中央位置的元素，说明如果存在这样的元素，应该位于查找区间的前半部分。此时可以将查找区间缩减为原来的一半，并在这一半的区间中继续用相同的方式查找。,如果,key,大于中央位置的元素，说明如果存在这样的元素，应该位于查找区间的后半部分。同样可以将查找区间缩减为原来的一半，并在这一半的区间中继续用相同的方式查找。,可以看出，用,key,与当前查找区间中央位置的元素比较后，不是找到了，就是将查找区间缩小了一半。直到查找区间不存在了，说明没有要找的,key,。,26,算法描述,27,#include ,#define NUM 10,main( ),int valueNUM = 12, 23, 30, 45, 48, 50, 67, 82, 91, 103; /*,非递减整型数列 *,/,int low, high, mid, key;,printf(nEnter a key:); /*,输入查找的数值 *,/,scanf(%d, ,low = 0;high = NUM-1;,while (low=high) ,mid = (low+high)/2;,if (valuemid=key)break;,if (valuemidkey),low = mid+1;,else,high = mid-1;,if (low=high),printf(n%d is found at %d., key, mid);/*,确认,break,出口 *,/,else,printf(n%d is not found., key);/*,确认循环正常出口 *,/,程序代码,28,排序问题,将一组无序的数列重新排列成非递减或非递增的顺序是一种经常需要的操作。例如，在管理学生成绩的应用程序中，可以用一个数列表示一个班级的学生成绩，并按照从高到低的顺序重新排列，以便确定获得奖学金的学生。,29,例,6,：假设用户通过键盘输入一个整型数列。请编写一个程序，将其按照从小到大的顺序重新排列。,问题分析,首先从,n,个数据中选择一个最小的数据，并将它交换到第,1,个位置；然后再从后面,n-1,个数据中选择一个最小的数据，并将它交换到第,2,个位置；以此类推，直至最后从两个数据中选择一个最小的数据，并将它交换到第,n-1,个位置为止，整个排序操作结束。,30,算法描述,31,#include ,#define NUM 10 /*,参与排序的数据个数 *,/,main(),int dataNUM; /*,存放参与排序的所有整数 *,/,int i, j, minValue, temp;,/*,通过键盘输入待排序的整型数列 *,/,printf(nEnter %d integers., NUM);,for (i=0; iNUM; i+) ,scanf(%d, ,/*,显示原始整型数列 *,/,printf(n%d integers are:, NUM);,for (i=0; iNUM; i+) ,printf(%5d, datai);,程序代码,32,for (i=0; iNUM-1; i+) ,minValue = i;,for (j=i+1; jNUM; j+) ,if (datajdataminValue),minValue = j;,if (minValue!=i) /*,交换 *,/,temp = datai;,datai = dataminValue;,dataminValue = temp;,/*,输出排序后的结果 *,/,printf(nOrdering list is:n);,for (i=0; iNUM; i+) ,printf(%5d, datai);,33,小结与作业,一维数组的定义、初始化、赋值、引用,一维数组的应用,课后作业,34,