c語言程序設計11數(shù)組

ProgramminginC

c程序設計

ProgramminginC

西安電子科技大學計算機學院張淑平

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China1

ProgramminginC

這次課的主要內(nèi)容

?數(shù)組

?一維數(shù)組

?查找

?排序

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China2

ProgramminginC

什么是數(shù)組

類型相同的一組數(shù)據(jù)，集中存儲

一維數(shù)組的定義形式

A類型說明符數(shù)組名[常量表達式];

>例如：

>intnum[10];/*由10個整數(shù)組成的數(shù)組num*/

>doublea[100];/*由100個浮點數(shù)組成的數(shù)組a*/

>charname[20];/*由20個字符組成的數(shù)組name*/

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China3

ProgramminginC

數(shù)組的元素

如何區(qū)分一個數(shù)組中的每個元素

>hU_(num)[10];/*由10個整數(shù)組成的數(shù)組num*/

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

數(shù)組名Adoi也以列100];/*由100個浮點數(shù)組成的數(shù)組a*/

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

>char^name)[20];/*由20個字符組成的數(shù)組name*/

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

數(shù)組元素的下標

同一個數(shù)組中的元素通過下標相互區(qū)

分

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China4

ProgramminginC

；同一婁儂中的元素是集中存放的

?intnum[5];

num[O]79

num[l]11

num[2]27

num[3]26

num[4]43

數(shù)組元素按照下標順序依次存放在內(nèi)

存的一段空間中

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China5

ProgramminginC

查找

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China6

ProgramminginC

0順序查找

?若數(shù)組num是由8個整數(shù)組成的，請查找指

定的整數(shù)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

圖順序查找(續(xù))

?也可以按照下標從大到小的次序進行順序

查找

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

⑨順序查找（續(xù)）

?順序查找的方法是：按照下標次序從大到

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

?當數(shù)組中元素的值無序排列時，采用順序

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

呢？

num[O]11

num[l]26

num[2]27

num[3]43

num[4]79

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China9

ProgramminginC

好二分查找（折半查找）

?若數(shù)組中元素的值是有序排列的，則可采用二分

查找法查找元素，方法如下：用一對下標（稱為高

端下標high和低端下標low）指示出一個查找范圍,

由這對下標計算出中間元素的下標mid,若待查找

的元素k等于中間元素的值，則查找成功；否則，

根據(jù)k與之間元素值的大小關系，修改高端下標

high或者低端下標low,將查找范圍縮小一半。

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China10

ProgramminginC

二分查找（續(xù)）

?若數(shù)組中元素的值是有序排列的，則可采用二分查找法查

找元素，方法如下：用一對下標（稱為高端下標high和低

端下標low）指示出一個查找范圍，由這對下標計算出中間

元素的下標mid,若待查找的元素k等于中間元素的值，則

查找成功；否則，根據(jù)k與之間元素值的大小關系，修改

高端下標high或者低端下標low,將查找范圍縮小一半。

下標01234567

612232831455199

lowhigh

mid=[(low+high)/2]

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China11

ProgramminginC

二分查找（實例）

?假設需要在8個元素的數(shù)組num中查找45是否在其

中，即k=45。

下標01234567

612232831455199

lowhigh

mid

k>num

II

4528

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China12

ProgramminginC

<^二分查找（實例續(xù)）

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

一步應當在后半部查找，即確定新的low和high。

下標01234567

612232831455199

lowhigh

?high值不變，low=mid+1

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China13

ProgramminginC

簿二分查找（實例續(xù)）

?待查找的45等于中間位置上的元素45,查找結(jié)束。

下標01234567

612232831455199

lowhigh

mid

k==num[midi

IIII

4545

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China14

鴛二分查找ProgramminginC

?假設需要在8個元下標01234567

素的數(shù)組num中查612232831455199

找45是否在其中，

即k=45。

lowhigh

mid

scanf(n%dn,&k);

low=0;high=7;

while(low<=high){/*查找整數(shù)k是否在數(shù)組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

一維數(shù)組小結(jié)

?數(shù)組是具有相同類型的數(shù)據(jù)元素的序列，其元

素連續(xù)地存儲，可以通過下標訪問數(shù)組的元素。

?數(shù)組的定義（聲明）格式：

元素類型說明符數(shù)組名［常量表達式］;

其中，常量表達式的值是個整數(shù)，它指定了該

數(shù)組中元素的數(shù)目，即數(shù)組的尺寸。

?一般情況下，定義（聲明）數(shù)組時應明確數(shù)組的

尺寸。

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China16

ProgramminginC

一維數(shù)組小結(jié)（續(xù)）

?定義（聲明）數(shù)組時可以給其元素指定值，即初始

化。

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

?數(shù)組的尺寸可以由初始化時值的數(shù)目確定，即

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

＞由于用作數(shù)組元素初始化的值的個數(shù)是4個，所以編譯

系統(tǒng)由此確定該數(shù)組的尺寸（大?。?。

?若給定的初始值的數(shù)目小于指定的尺寸，則按下

標序初始化數(shù)組元素，其余的元素初始化為0。

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

西安電子科技大學計算機學院-SchoolofComputerScience&Engineering,XidianUniversity,China17

ProgramminginC

一維數(shù)組小結(jié)（續(xù)）

?對數(shù)組中的元素只能逐個進行運算，不能整體運

算

>例如: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){/*查找整數(shù)k是否在數(shù)組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,