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

ProgramminginC

c程序設(shè)計(jì)

ProgramminginC

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院張淑平

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China1

ProgramminginC

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

?數(shù)組

?一維數(shù)組

?查找

?排序

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China2

ProgramminginC

什么是數(shù)組

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

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

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

>例如：

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

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

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

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China3

ProgramminginC

數(shù)組的元素

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

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

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

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

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

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

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

數(shù)組元素的下標(biāo)

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

分

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China4

ProgramminginC

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

?intnum[5];

num[O]79

num[l]11

num[2]27

num[3]26

num[4]43

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

存的一段空間中

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China5

ProgramminginC

查找

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China6

ProgramminginC

0順序查找

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

定的整數(shù)k是否在其中。

scanf(n%dn,&k);

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

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

elseprintf(nfound!\nn);

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China7

卞ProgramminginC

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

?也可以按照下標(biāo)從大到小的次序進(jìn)行順序

查找

scanf(n%dn,&k);

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

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

elseprintf(nfound!\nH);

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China8

ProgramminginC

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

?順序查找的方法是：按照下標(biāo)次序從大到

?。ɑ驈男〉酱螅┮来尾檎摇?/p>

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

查找是當(dāng)然的，若元素的值是有序排列的

呢？

num[O]11

num[l]26

num[2]27

num[3]43

num[4]79

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China9

ProgramminginC

好二分查找（折半查找）

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

查找法查找元素，方法如下：用一對下標(biāo)（稱為高

端下標(biāo)high和低端下標(biāo)low）指示出一個(gè)查找范圍,

由這對下標(biāo)計(jì)算出中間元素的下標(biāo)mid,若待查找

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

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

high或者低端下標(biāo)low,將查找范圍縮小一半。

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China10

ProgramminginC

二分查找（續(xù)）

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

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

端下標(biāo)low）指示出一個(gè)查找范圍，由這對下標(biāo)計(jì)算出中間

元素的下標(biāo)mid,若待查找的元素k等于中間元素的值，則

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

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

下標(biāo)01234567

612232831455199

lowhigh

mid=[(low+high)/2]

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China11

ProgramminginC

二分查找（實(shí)例）

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

中，即k=45。

下標(biāo)01234567

612232831455199

lowhigh

mid

k>num

II

4528

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China12

ProgramminginC

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

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

一步應(yīng)當(dāng)在后半部查找，即確定新的low和high。

下標(biāo)01234567

612232831455199

lowhigh

?high值不變，low=mid+1

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China13

ProgramminginC

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

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

下標(biāo)01234567

612232831455199

lowhigh

mid

k==num[midi

IIII

4545

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China14

鴛二分查找ProgramminginC

?假設(shè)需要在8個(gè)元下標(biāo)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;

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China15

ProgramminginC

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

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

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

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

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

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

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

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

尺寸。

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China16

ProgramminginC

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

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

化。

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

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

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

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

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

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

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

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

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China17

ProgramminginC

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

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

算

>例如:inti,num[8];

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

scanf&num[i]);

num=100;/*錯(cuò)誤*/

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-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);

文電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaTC2.0

ProgramminginC

簡單排序法

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-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*/

西安電子科技大學(xué)計(jì)算機(jī)學(xué)院-SchoolofComputerScience&Engineering,