数据的组织结构一

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第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,#defineNUM10/*,候,候,选,选,人,人,人,人,数,数*/,main(),intvoteNUM=0;,intcode,i,winner;,/*,职,职,工,工,投,投,票,票*/,printf(nEnteryourselection:n);,do,scanf(%d,if(codeNUM),/*,检,检,验,验输,入,入的,编,编码,是,是否,有,有效*/,printf(nInvalidvote.);,else,if(code!=0),votecode-1=votecode-1+1;,/*,累,累加票,数,数*/,while(code!=0);,程序代,码,码,/*,输,输出选,票,票*/,printf(n Theamountofvotesis:);,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,#define NUM26,main(),intletterNUM=0;,char ch;,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(nFinalscore is%6.2f,sum);,查找问题,所谓查找是,指,指根据某个,给,给定的条件,，,，在一组数,据,据中搜索是,否,否存在满足,该,该条件的数,据,据的过程。,如,如果存在，,则,则表示查找,成,成功，给出,成,成功的标志,；,；否则表示,查,查找不成功,，,，给出失败,的,的标志。在,程,程序中，查,找,找操作的结,果,果经常被用,来,来作为是否,执,执行某项后,续,续操作的决,策,策依据。,例4：已知,某,某个班级35名学生的,某,某门课程的,考,考试成绩。,请,请编写一个,程,程序，查看,在,在这个班级,中,中是否存在,不,不及格的学,生,生。,问题分析,用一维数组,记,记录每位学,生,生的考试成,绩,绩，下标表,示,示每个学生,的,的编号，元,素,素内容表示,考,考试成绩。,查找可以通,过,过从前往后,依,依次查看每,个,个元素内容,的,的过程实现,。,。,算法描述,#include,#include,#define NUM 35/*学,生,生人数*/,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(nNotallpass.);,else,printf(Allpass.);,例5：已知,一,一个按非递,减,减有序排列,的,的整型数列,（,（12,23,30,45,48,50,67,82,91,103）。请编,写,写一个程序,，,，查找其中,是,是否存在与,给,给定key,相,相等的数值,。,。,问题分析,二分查找是,指,指每次用,key,与位于查找,区,区间中央位,置,置的元素进,行,行比较，比,较,较结果将会,产,产生下面三,种,种情形之一,：,：,如果相等，,说,说明查找成,功,功。,如果,key,小于中央位,置,置的元素，,说,说明如果存,在,在这样的元,素,素，应该位,于,于查找区间,的,的前半部分,。,。此时可以,将,将查找区间,缩,缩减为原来,的,的一半，并,在,在这一半的,区,区间中继续,用,用相同的方,式,式查找。,如果,key,大于中央位,置,置的元素，,说,说明如果存,在,在这样的元,素,素，应该位,于,于查找区间,的,的后半部分,。,。同样可以,将,将查找区间,缩,缩减为原来,的,的一半，并,在,在这一半的,区,区间中继续,用,用相同的方,式,式查找。,可以看出，,用,用,key,与当前查找,区,区间中央位,置,置的元素比,较,较后，不是,找,找到了，就,是,是将查找区,间,间缩小了一,半,半。直到查,找,找区间不存,在,在了，说明,没