c语言程序设计11数组

ProgramminginC

c程序设计

ProgramminginC

西安电子科技大学计算机学院张淑平

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China1

ProgramminginC

这次课的主要内容

•数组

•一维数组

•查找

•排序

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China2

ProgramminginC

什么是数组

类型相同的一组数据，集中存储

一维数组的定义形式

A类型说明符数组名[常量表达式];

>例如：

>intnum[10];/*由10个整数组成的数组num*/

>doublea[100];/*由100个浮点数组成的数组a*/

>charname[20];/*由20个字符组成的数组name*/

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China3

ProgramminginC

数组的元素

如何区分一个数组中的每个元素

>hU_(num)[10];/*由10个整数组成的数组num*/

>num[0],num[1],num[2],...,num[8],num[9]

数组名Adoi也以列100];/*由100个浮点数组成的数组a*/

>a[0],a[l],a[2],...，a[98],a[99]

>char^name)[20];/*由20个字符组成的数组name*/

>name[0],name[1],...,name[18],name[19]

数组元素的下标

同一个数组中的元素通过下标相互区

分

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China4

ProgramminginC

；同一娄侬中的元素是集中存放的

•intnum[5];

num[O]79

num[l]11

num[2]27

num[3]26

num[4]43

数组元素按照下标顺序依次存放在内

存的一段空间中

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China5

ProgramminginC

查找

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China6

ProgramminginC

0顺序查找

・若数组num是由8个整数组成的，请查找指

定的整数k是否在其中。

scanf(n%dn,&k);

for(i=0;i<8&&num[i]!=k;++i);

if(i>=8)printf(nnotfoundin'');

elseprintf(nfound!\nn);

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China7

卞ProgramminginC

图顺序查找(续)

•也可以按照下标从大到小的次序进行顺序

查找

scanf(n%dn,&k);

for(i=7;i>=0&&num[i]!=k;i-);

if(i<0)printf(nnotfound!\nn);

elseprintf(nfound!\nH);

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China8

ProgramminginC

⑨顺序查找（续）

•顺序查找的方法是：按照下标次序从大到

小（或从小到大）依次查找。

•当数组中元素的值无序排列时，采用顺序

查找是当然的，若元素的值是有序排列的

呢？

num[O]11

num[l]26

num[2]27

num[3]43

num[4]79

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China9

ProgramminginC

好二分查找（折半查找）

•若数组中元素的值是有序排列的，则可采用二分

查找法查找元素，方法如下：用一对下标（称为高

端下标high和低端下标low）指示出一个查找范围,

由这对下标计算出中间元素的下标mid,若待查找

的元素k等于中间元素的值，则查找成功；否则，

根据k与之间元素值的大小关系，修改高端下标

high或者低端下标low,将查找范围缩小一半。

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China10

ProgramminginC

二分查找（续）

•若数组中元素的值是有序排列的，则可采用二分查找法查

找元素，方法如下：用一对下标（称为高端下标high和低

端下标low）指示出一个查找范围，由这对下标计算出中间

元素的下标mid,若待查找的元素k等于中间元素的值，则

查找成功；否则，根据k与之间元素值的大小关系，修改

高端下标high或者低端下标low,将查找范围缩小一半。

下标01234567

612232831455199

lowhigh

mid=[(low+high)/2]

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China11

ProgramminginC

二分查找（实例）

•假设需要在8个元素的数组num中查找45是否在其

中，即k=45。

下标01234567

612232831455199

lowhigh

mid

k>num

II

4528

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China12

ProgramminginC

<^二分查找（实例续）

•待查找的45大于中间位置上的元素28,因此，下

一步应当在后半部查找，即确定新的low和high。

下标01234567

612232831455199

lowhigh

•high值不变，low=mid+1

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China13

ProgramminginC

簿二分查找（实例续）

•待查找的45等于中间位置上的元素45,查找结束。

下标01234567

612232831455199

lowhigh

mid

k==num[midi

IIII

4545

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China14

鸳二分查找ProgramminginC

•假设需要在8个元下标01234567

素的数组num中查612232831455199

找45是否在其中，

即k=45。

lowhigh

mid

scanf(n%dn,&k);

low=0;high=7;

while(low<=high){/*查找整数k是否在数组num中*/

mid=(low+high)/2;

if(k==num[mid])break;

elseif(k>num[mid])low=mid+1;

elsehigh=mid-1;

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China15

ProgramminginC

一维数组小结

•数组是具有相同类型的数据元素的序列，其元

素连续地存储，可以通过下标访问数组的元素。

•数组的定义（声明）格式：

元素类型说明符数组名［常量表达式］;

其中，常量表达式的值是个整数，它指定了该

数组中元素的数目，即数组的尺寸。

•一般情况下，定义（声明）数组时应明确数组的

尺寸。

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China16

ProgramminginC

一维数组小结（续）

•定义（声明）数组时可以给其元素指定值，即初始

化。

A例如：intnum[8]={6,12,23,28,31,45,51,99);

•数组的尺寸可以由初始化时值的数目确定，即

»例如：intnum[]={6,12,23,28};

＞由于用作数组元素初始化的值的个数是4个，所以编译

系统由此确定该数组的尺寸（大小）为4。

•若给定的初始值的数目小于指定的尺寸，则按下

标序初始化数组元素，其余的元素初始化为0。

A例如：intnum[8]={6,12,23,28）;

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China17

ProgramminginC

一维数组小结（续）

•对数组中的元素只能逐个进行运算，不能整体运

算

>例如:inti,num[8];

for(i=0;i<8;i++)

scanf&num[i]);

num=100;/*错误*/

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China18

ProgramminginC

期二^查找程序

intk,num[8]={6,12,23,28,31,45,51,99};intlow,high,mid;

scanf(n%dn,&k);

low=0;high=7;

while(low<=high){/*查找整数k是否在数组num中*/

mid=(low+high)/2;

if(k==num[mid])break;

elseif(k>num[mid])low=mid+1;

elsehigh=mid-1;

)

if(low>high)

printf(n%disnotfoundinarraynum.\nn,k);

else

printf(n%disfoundinarraynum[%d].\nn,k,mid);

文电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaTC2.0

ProgramminginC

简单排序法

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China回顾

ProgramminginC

冒泡排序流程图

ProgramminginC

目冒泡排序

inti,j,temp,a[7]={43,18,9,13,55,7,43};

for(i=0;i<6;i++){

for(j=0;j<6-i;j++)

if(a[j]>a[j+l]){

temp=a[j];a[j]=a[j+l];a[j+l]=temp;

}/*endif*/

}/*endfori*/

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,