数据的组织结构

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第4章 数据的组织结构（一）,4.3,字符串的组织,4.2,利用一维数组组织数据的应用实例,4.1,数组类型,4.4,常用的字符串标准函数及应用实例,4.5,二维数组,课前复习,前三章,数据类型 -数据结构的一种方式,学习新的数据的组织形式-数据结构的另一种方式,4.1 数组类型,数组类型的应用背景,（,1,）同时存在若干个用来描述同一性质且不同个体的数据。,（2）只有将这些数据组织在一起形成批量数据，共同参与处理，很多操作才具有实际意义。,例如：在某个部门中，需要由全体职工推选一名办公室主任。假设有10名候选人准备参与竞选。希望编写一个程序，统计每个候选人的得票数量及选举结果。,一维数组类型的定义,定义格式：,；,例如：,int vote10;,C,语言规定：数组的下标从,0,开始，因此，表示这,10,个数据的下标为,09,变量一经定义，系统就要为它分配相应的存储空间。在,C,程序中，系统将会为每个数组型变量分配一片连续的存储空间，所需要分配的存储空间总数将取决于包含的元素个数和每个元素需要的存储空间。,一维数组的初始化,基本格式为：,=,，,，,.,，,；,例如：,float score5=9.2,9.1,8.7,9.1,8.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;,一维数组元素的引用及基本操作,数组元素的引用,数组的赋值,利用赋值语句为数组赋值,for(i=0;i10;i+),votei=0;,调用标准输入函数为数组赋值,for(i=0;i13;i+),scanf(“%f”,数组的输出,for(i=0;i10;i+),printf(“%5d”,votei);,按照条件对数据进行筛选,在遇到的许多问题中，经常需要从众多的数据中挑选出来满足一定条件的数据，这就是数据的筛选操作。在,C,程序中，参与筛选操作的批量数据可以采用一个一维数组型变量组织，筛选的条件用逻辑表达式表示。,4.2 利用一维数组组织数据的应用实例,例1：在某个公司中，计划由职工们推选一名办公室主任。假设有10名候选人准备参与竞选。希望编写一个程序，输入一组选举人的投票信息，统计每个候选人的得票数目及选举结果。,问题分析,用一维数组记录每位候选人的得票数量。,投票,通过循环输入介于,110,之间的整型数值来模拟的。例如，输入,3,代表某个职工选举编码为,3,的候选人。,找出最多的得票数量之后，从所有的候选人中筛选出得票数量与最高得票数量相同的人。,算法描述,#include,#define NUM 10/*候,选,选人人数*/,main(),int voteNUM=0;,int code,i,winner;,/*职工,投,投票*/,printf(nEnteryourselection:n);,do,scanf(%d,if(codeNUM),/*检验,输,输入的编码,是,是否有效*/,printf(nInvalid vote.);,else,if(code!=0),votecode-1=votecode-1+1;,/*累加,票,票数*/,while(code!=0);,程序代码,/*输出,选,选票*/,printf(nTheamount ofvotesis:);,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);,根据需求对,数,数据进行统,计,计,为了满足特,定,定的需要，,对,对一组数据,的,的某些特征,进,进行统计是,一,一项经常遇,到,到的基本操,作,作。例如，,统,统计一段文,本,本中某个字,符,符出现的频,率,率；统计学,生,生考试的平,均,均成绩等等,都,都属于统计,操,操作。统计,操,操作的结果,往,往往是通过,对,对所有数据,进,进行扫描、,判,判断或综合,加,加工得到的,。,。在,C,程序中，参,与,与统计操作,的,的批量数据,可,可以用一维,数,数组来组织,，,，具体统计,过,过程可以通,过,过逻辑判断,、,、累计、算,术,术运算等基,本,本操作手段,实,实现。,例2：在一,段,段文本中，,可,可能会出现,各,各式各样的,字,字符。编写,一,一个程序，,从,从键盘读入,一,一行文本，,完,完成统计每,个,个英文字母,出,出现频率的,操,操作。,问题,分,分析,用一,维,维数,组,组构,造,造26个,用,用于,记,记录,每,每个,字,字母,出,出现,次,次数,的,的累,加,加器,。,。,对于,输,输入,的,的文,本,本字,符,符，,可,可以,在,在读,取,取时,检,检查,一,一下,是,是否,为,为英,文,文字,母,母，,而,而不,需,需要,将,将其,存,存储,起,起来,。,。,算法,描,描述,#include,#defineNUM26,main(),intletterNUM=0;,charch;,inti;,printf(nEntertextlinen);,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);,程序代,码,码,例3：,每,每年中,央,央电视,台,台都要,举,举办青,年,年歌手,大,大奖赛,。,。假设,有,有13,位,位评委,参,参与评,分,分工作,。,。计算,每,每位歌,手,手最终,得,得分的,方,方法是,：,：首先,去,去掉一,个,个最高,分,分和一,个,个最低,分,分，然,后,后计算,剩,剩余11个分,数,数的平,均,均值，,所,所得结,果,果就是,选,选手的,最,最终得,分,分。希,望,望编写,一,一个程,序,序，帮,助,助工作,人,人员计,算,算每个,歌,歌手的,分,分数。,问题分,析,析,用一维,数,数组存,储,储 13位评,委,委给出,的,的分数,寻找最,高,高分和,最,最低分,计算剩,余,余11,个,个分数,的,的平均,分,分,算法描,述,述,#include,#define NUM13,main(),floatscoreNUM;*/,inti,minValue,maxValue;,floatsum;,/*,输,输入13位评,委,委给出,的,的分数*/,printf(nEnter13score:);,for(i=0;iNUM;i+),scanf(%f,程序代,码,码,/*,找,找出最,高,高分、,最,最低分,，,，并同,时,时累加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(nFinalscoreis%6.2f,sum);,查找问,题,题,所谓查,找,找是指,根,根据某,个,个给定,的,的条件,，,，在一,组,组数据,中,中搜索,是,是否存,在,在满足,该,该条件,的,的数据,的,的过程,。,。如果,存,存在，,则,则表示,查,查找成,功,功，给,出,出成功,的,的标志,；,；否则,表,表示查,找,找不成,功,功，给,出,出失败,的,的标志,。,。在程,序,序中，,查,查找操,作,作的结,果,果经常,被,被用来,作,作为是,否,否执行,某,某项后,续,续操作,的,的决策,依,依据。,例4,：,：已,知,知某,个,个班,级,级35名,学,学生,的,的某,门,门课,程,程的,考,考试,成,成绩,。,。请,编,编写,一,一个,程,程序,，,，查,看,看在,这,这个,班,班级,中,中是,否,否存,在,在不,及,及格,的,的学,生,生。,问题,分,分析,用一,维,维数,组,组记,录,录每,位,位学,生,生的,考,考试,成,成绩,，,，下,标,标表,示,示每,个,个学,生,生的,编,编号,，,，元,素,素内,容,容表,示,示考,试,试成,绩,绩。,查找,可,可以,通,通过,从,从前,往,往后,依,依次,查,查看,每,每个,元,元素,内,内容,的,的过,程,程实,现,现。,算法,描,描述,#include,#include,#defineNUM35/*学,生,生人,数,数*/,main(),intscoreNUM;,inti;,/*随,机,机产生35个考试,成,成绩*/,randomize();,for(i=0;iNUM;i+),scorei=random(100);,/*显示35名学,生,生的考试,成,成绩*/,for(i=0;iNUM;i+),printf(nNo.%d:%d,i+1,scorei);,程序代码,/*顺序,查,查找是否,存,存在不及,格,格的学生*/,for(i=0;iNUM;i+),if(scorei60)break;,/*输出,查,查找结果*/,if(iNUM),printf(nNot all pass.);,else,printf(Allpass.);,例5：已,知,知一个按,非,非递减有,序,序排列的,整,整型数列,（,（12,23,30,45,48,50,67,82,91,103）,。,。请编写,一,一个程序,，,，查找其,中,中是否存,在,在与给定key相,等,等的数值,。,。,问题分析,二分查找,是,是指每次,用,用,key,与位于查,找,找区间中,央,央位置的,元,元素进行,比,比较，比,较,较结果将,会,会产生下,面,面三种情,形,形之一：,如果相等,，,，说明查,找,找成功。,如果,key,小于中央,位,位置的元,素,素，说明,如,如果存在,这,这样的元,素,素，应该,位,位于查找,区,区间的前,半,半部分。,此,此时可以,将,将查找区,间,间缩减为,原,原来的一,半,半，并在,这,这一半的,区,区间中继,续,续用相同,的,的方式查,找,找。,如果,key,大于中央,位,位置的元,素,素，说明,如,如果存在,这,这样的元,素,素，应该,位,位于查找,区,区间的后,半,半部分。,同,同样可以,将,将查找区,间,间缩减为,原,原来的一,半,半，并在,这,这一半的,区,区间中继,续,续用相同,的,的方式查,找,找。,可以看出,，,，用,key,与当前查,找,找区间中,央,央位置的,元,元素比较,后,后，不是,找,找到了，,就,就是将查,