C語(yǔ)言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)

C語(yǔ)言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)第1頁(yè)/共39頁(yè)主要內(nèi)容7.1一維數(shù)組7.2二維數(shù)組7.3字符數(shù)組7.4數(shù)組在函數(shù)中的應(yīng)用7.5折半查找7.6數(shù)組元素排序7.7典型習(xí)題分析解答第2頁(yè)/共39頁(yè)

7.1一維數(shù)組

7.1.1一維數(shù)組的定義與初始化一維數(shù)組的定義

一維數(shù)組的定義格式為：類(lèi)型說(shuō)明符數(shù)組名[常量表達(dá)式]；

說(shuō)明：

(1)數(shù)組的類(lèi)型指數(shù)組元素的取值類(lèi)型。對(duì)于上例，即說(shuō)明該數(shù)組a中的10個(gè)元素都是整型。(2)數(shù)組名必須是合法標(biāo)識(shí)符，也就是說(shuō)必須符合標(biāo)識(shí)符的命名規(guī)則；(3)數(shù)組名不能與同一程序中的其它變量同名；(4)若用方括號(hào)中的整數(shù)n來(lái)表示數(shù)組元素的總數(shù)，則數(shù)組的第一個(gè)元素的下標(biāo)為0（稱(chēng)為數(shù)組下標(biāo)的下界），最后一個(gè)為n-1（稱(chēng)為數(shù)組下標(biāo)的上界）。對(duì)于上例，數(shù)組中含有10個(gè)元素，分別是：a[0],a[1],a[2],……,a[9]。(5)不能在方括號(hào)中用變量來(lái)表示元素的個(gè)數(shù)。

(6)允許在同一個(gè)說(shuō)明中，說(shuō)明相同類(lèi)型的多個(gè)數(shù)組和多個(gè)變量。(7)可以使用在編譯預(yù)處理#define中定義的符號(hào)常量。第3頁(yè)/共39頁(yè)

一維數(shù)組的初始化

初始化賦值的一般形式為：

類(lèi)型說(shuō)明符數(shù)組名[常量表達(dá)式]={值，值……值}；其中在{}中的各數(shù)據(jù)值即為各元素的初值，各值之間用逗號(hào)間隔。例如：inta[10]={0,1,2,3,4,5,6,7,8,9};說(shuō)明：（1）可以只給部分元素賦初值。當(dāng){}中值的個(gè)數(shù)少于元素個(gè)數(shù)時(shí)，只給前面部分元素賦值。例如：inta[10]={0,1,2,3,4};表示只給a[0]～a[4]這5個(gè)元素賦值，而后5個(gè)元素自動(dòng)賦0值。（2）能給元素逐個(gè)賦值，但不能給數(shù)組整體賦值。例如給十個(gè)元素全部賦1值，只能寫(xiě)為：inta[10]={1,1,1,1,1,1,1,1,1,1};而不能寫(xiě)為：inta[10]=1;（3）如給全部元素賦值，則在數(shù)組說(shuō)明中，可以不給出數(shù)組元素的個(gè)數(shù)。例如：inta[5]={1,2,3,4,5};可寫(xiě)為：inta[]={1,2,3,4,5};第4頁(yè)/共39頁(yè)7.1.2一維數(shù)組元素的引用數(shù)組元素引用的一般形式為：

數(shù)組名[下標(biāo)]其中的下標(biāo)只能為整型常量或整型表達(dá)式。如果為小數(shù)時(shí)，C編譯將自動(dòng)取整。例如，a[6],b[i+j],b[i++]都是合法的數(shù)組元素。數(shù)組元素通常也稱(chēng)為下標(biāo)變量。必須先定義數(shù)組，才能使用下標(biāo)變量。在Ｃ語(yǔ)言中只能逐個(gè)地使用下標(biāo)變量，而不能一次引用整個(gè)數(shù)組。例如，單獨(dú)使用一個(gè)下標(biāo)變量：

inta[10];a[7]=6;第5頁(yè)/共39頁(yè)7.1.3一維數(shù)組元素的賦值數(shù)組定義之后，如果不對(duì)其進(jìn)行初始化，則其值可通過(guò)賦值語(yǔ)句獲或者可從鍵盤(pán)、文件等讀取獲得。現(xiàn)以從鍵盤(pán)接收數(shù)據(jù)為例：【例7.1】從鍵盤(pán)輸入十個(gè)數(shù)據(jù)給數(shù)組a賦值，然后把數(shù)組a的值復(fù)制到數(shù)組b中。

main(){inta[10],b[10],i;for(i=0;i<10;i++)scanf("%d",&a[i]);for(i=0;i<10;i++)b[i]=a[i];for(i=0;i<10;i++)printf("%d",b[i]);}第6頁(yè)/共39頁(yè)7.1.4順序查找

順序查找即為從數(shù)組的一端開(kāi)始，逐個(gè)進(jìn)行數(shù)組元素的值和給定值x的比較，若某個(gè)元素的值和給定值x相等，則查找成功；反之，若直至最后一個(gè)數(shù)組元素，其值和給定值x都不相等，則表明數(shù)組中沒(méi)有所查的數(shù)據(jù)，查找不成功?！纠?.2】已知存放在a數(shù)組中的數(shù)據(jù)兩兩不相同，在a數(shù)組中查找和x值相同的元素的位置。若找到，輸出該值和其在a數(shù)組中的位置；若沒(méi)找到，輸出相應(yīng)的提示信息。#defineN100main(){inta[N],x,n,i,flag=-1;printf("Inputn:\n");scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);printf("Inputx:\n");scanf("%d",&x);第7頁(yè)/共39頁(yè)for(i=0;i<n;i++)if(a[i]==x){flag=i;break;}if(flag!=-1)printf("%dindexis%d",x,flag+1);elseprintf("%ddonntbefounded!\n",x);對(duì)于上例，也可以通過(guò)設(shè)監(jiān)視哨的方法對(duì)數(shù)組倒著查找，代碼見(jiàn)課本。第8頁(yè)/共39頁(yè)

7.2二維數(shù)組

二維數(shù)組：數(shù)組元素是雙下標(biāo)變量的數(shù)組。二維數(shù)組的數(shù)組素可以看作是排列為行列的形式（矩陣）。二維數(shù)組也用統(tǒng)一的數(shù)組名標(biāo)識(shí)，第一個(gè)下標(biāo)表示行，第二個(gè)下標(biāo)表示列。下標(biāo)從0開(kāi)始。7.2.1二維數(shù)組的定義與初始化二維數(shù)組的定義二維數(shù)組定義的一般形式是：

類(lèi)型說(shuō)明符數(shù)組名[常量表達(dá)式1][常量表達(dá)式2]；其中常量表達(dá)式1表示第一維下標(biāo)的長(zhǎng)度，常量表達(dá)式2表示第二維下標(biāo)的長(zhǎng)度。例如：inta[3][4];說(shuō)明了一個(gè)三行四列的數(shù)組，數(shù)組名為a，其下標(biāo)變量的類(lèi)型為整型。該數(shù)組的下標(biāo)變量共有3×4個(gè)，即：a[0][0],a[0][1],a[0][2],a[0][3]a[1][0],a[1][1],a[1][2],a[1][3]a[2][0],a[2][1],a[2][2],a[2][3]如何在一維存儲(chǔ)器中存放二維數(shù)組，可有兩種方式：一種是按行排列，即放完一行之后順次放入第二行。另一種是按列排列，即放完一列之后順次放入第二列。在Ｃ語(yǔ)言中，二維數(shù)組是按行排列的。第9頁(yè)/共39頁(yè)二維數(shù)組的初始化二維數(shù)組可按行分段賦值，也可按行連續(xù)賦值。二維數(shù)組的初始化的幾種常見(jiàn)形式：（1）分行給二維數(shù)組所有元素賦初值例如：inta[2][4]={{1,2,3,4},{5,6,7,8}};（2）不分行給二維數(shù)組所有元素賦初值例如：inta[2][4]={1,2,3,4,5,6,7,8};（3）給二維數(shù)組所有元素賦初值，二維數(shù)組第一維的長(zhǎng)度可以省略（編譯程序可計(jì)算出長(zhǎng)度）例如：inta[][4]={1,2,3,4,5,6,7,8};或：inta[][4]={{1,2,3,4},{5,6,7,8}};（4）對(duì)部分元素賦初值例如：inta[2][4]={{1,2},{5}};

第10頁(yè)/共39頁(yè)7.2.2二維數(shù)組元素的引用定義了二維數(shù)組后，就可以引用該數(shù)組的所有元素。引用形式：數(shù)組名[下標(biāo)1][下標(biāo)2]例如：a[1][2]表示a數(shù)組第二行第三列的元素。下標(biāo)變量和數(shù)組說(shuō)明在形式中有些相似，但這兩者具有完全不同的含義。數(shù)組說(shuō)明的方括號(hào)中給出的是某一維的長(zhǎng)度，即可取下標(biāo)的最大值；而數(shù)組元素中的下標(biāo)是該元素在數(shù)組中的位置標(biāo)識(shí)。第11頁(yè)/共39頁(yè)7.2.3二維數(shù)組元素的賦值同一維數(shù)組一樣，若二維數(shù)組定義之后，不對(duì)其進(jìn)行初始化，則其值可通過(guò)賦值語(yǔ)句獲得，或者可從鍵盤(pán)、文件等讀取獲得?，F(xiàn)以從鍵盤(pán)接收數(shù)據(jù)為例：【例7.3】通過(guò)鍵盤(pán)給3×3的二維數(shù)組輸入數(shù)據(jù)，第一行賦1，2，3，第二行賦10，20，30，第三行輸入100，200，300，然后輸出此二維數(shù)組。main(){inta[3][3],i,j;for(i=0;i<3;i++)for(j=0;j<3;j++)scanf("%d",&a[i][j]);for(i=0;i<3;i++){for(j=0;j<3;j++) printf("%4d",a[i][j]);printf("\n");}}第12頁(yè)/共39頁(yè)7.3字符數(shù)組用來(lái)存放字符型數(shù)據(jù)的數(shù)組稱(chēng)為字符數(shù)組。字符數(shù)組中的一個(gè)元素存放一個(gè)字符。

7.3.1字符數(shù)組的定義、初始化字符數(shù)組的定義與前面介紹的數(shù)值數(shù)組定義相同。其定義格式為：

char數(shù)組名[下標(biāo)總數(shù)];例如：charc[10]={‘c’,‘’,‘p’,‘r’,‘o’,‘g’,‘r’,‘a(chǎn)’,’m’};賦值后各元素的值為：c[0]的值為‘c’，c[1]的值為‘’，c[2]的值為‘p’，……，c[8]的值為‘m’，其中c[9]未賦值，系統(tǒng)自動(dòng)賦予’\0’值。當(dāng)對(duì)全體元素賦初值時(shí)也可以省去長(zhǎng)度說(shuō)明。例如：charc[]={‘c’,‘’,‘p’,‘r’,‘o’,‘g’,‘r’,‘a(chǎn)’,’m’};這時(shí)C數(shù)組的長(zhǎng)度自動(dòng)定為9。另外，我們還可以將一個(gè)字符串賦給一個(gè)字符數(shù)組。字符串，是指若干有效字符的序列。如：”a”,”abc”。注意：由于系統(tǒng)在存儲(chǔ)字符串常量時(shí)，會(huì)在串尾自動(dòng)加上1個(gè)結(jié)束標(biāo)志，所以無(wú)需人為地再加1個(gè)。第13頁(yè)/共39頁(yè)7.3.2字符串處理函數(shù)

字符串標(biāo)準(zhǔn)函數(shù)的原型在頭文件string.h中。1.輸出字符串──puts()函數(shù)（1）調(diào)用方式：puts(字符數(shù)組)（2）函數(shù)功能：把字符數(shù)組中所存放的字符串，輸出到標(biāo)準(zhǔn)輸出設(shè)備中去，并用‘\n’取代字符串的結(jié)束標(biāo)志‘\0’。所以用puts()函數(shù)輸出字符串時(shí)，不要求另加換行符。（3）使用說(shuō)明:①字符串中允許包含轉(zhuǎn)義字符，輸出時(shí)產(chǎn)生一個(gè)控制操作。②該函數(shù)一次只能輸出一個(gè)字符串，而printf()函數(shù)也能用來(lái)輸出字符串，且一次能輸出多個(gè)?！纠?.5】下列程序的輸出結(jié)果是:#include<stdio.h>main(){charc[]="BASIC\ndBASE";puts(c);}運(yùn)行結(jié)果為：BASICdBASE第14頁(yè)/共39頁(yè)2．輸入字符串──gets()函數(shù)（1）調(diào)用方式：gets(字符數(shù)組)（2）函數(shù)功能：從標(biāo)準(zhǔn)輸入設(shè)備(stdin)──鍵盤(pán)上，讀取1個(gè)字符串（可以包含空格），并將其存儲(chǔ)到字符數(shù)組中去。（3）使用說(shuō)明

1）gets()讀取的字符串，其長(zhǎng)度沒(méi)有限制，編程者要保證字符數(shù)組有足夠大的空間，存放輸入的字符串。

2）該函數(shù)輸入的字符串中允許包含空格，而在scanf()函數(shù)中使用%s接收字符串時(shí)，空格做為字符串的結(jié)束標(biāo)志。【例7.6】#include<stdio.h>main(){charst[15];printf("inputstring:\n");gets(st);puts(st);}輸入：cprogram顯示：cprogram第15頁(yè)/共39頁(yè)3．字符串比較──strcmp()函數(shù)（1）調(diào)用方式：strcmp(字符串1,字符串2)其中“字符串”可以是串常量，也可以是1維字符數(shù)組。（2）函數(shù)功能：比較兩個(gè)字符串的大小。如果：字符串1=字符串2，函數(shù)返回值等于0；字符串1<字符串2，函數(shù)返回值負(fù)整數(shù)；字符串1>字符串2，函數(shù)返回值正整數(shù)。（3）使用說(shuō)明①如果一個(gè)字符串是另一個(gè)字符串從頭開(kāi)始的子串，則母串為大。②不能使用關(guān)系運(yùn)算符“＝＝”來(lái)比較兩個(gè)字符串，只能用strcmp()函數(shù)來(lái)處理?！纠?.7】#include<string.h>main(){intk;charst1[15],st2[]="CLanguage";printf("inputastring:\n");gets(st1);k=strcmp(st1,st2);if(k==0)printf("st1=st2\n");if(k>0)printf("st1>st2\n");if(k<0)printf("st1<st2\n");}第16頁(yè)/共39頁(yè)4.拷貝字符串──strcpy()函數(shù)（1）調(diào)用方式：strcpy(字符數(shù)組1,字符數(shù)組2)（2）函數(shù)功能：將“字符數(shù)組2”完整地復(fù)制到“字符數(shù)組1”中，字符數(shù)組中原有內(nèi)容被覆蓋。（3）使用說(shuō)明:①字符數(shù)組必須定義得足夠大，以便容納復(fù)制過(guò)來(lái)的字符串。復(fù)制時(shí)，連同結(jié)束標(biāo)志'\0'一起復(fù)制。②不能用賦值運(yùn)算符“＝”將一個(gè)字符串直接賦值給一個(gè)字符數(shù)組，只能用strcpy()函數(shù)來(lái)處理?！纠?.8】#include<string.h>main(){charst1[15],st2[]="CLanguage";strcpy(st1,st2);puts(st1);printf("\n");}運(yùn)行結(jié)果為：CLanguage第17頁(yè)/共39頁(yè)5．連接字符串──strcat()函數(shù)（1）調(diào)用方式：strcat(字符數(shù)組,字符串)（2）函數(shù)功能：把“字符串”連接到“字符數(shù)組”中的字符串尾端，并存儲(chǔ)于“字符數(shù)組”中?！白址麛?shù)組”中原來(lái)的結(jié)束標(biāo)志，被“字符串”的第一個(gè)字符覆蓋，而“字符串”在操作中未被修改。（3）使用說(shuō)明①由于沒(méi)有邊界檢查，編程者要注意保證“字符數(shù)組”定義得足夠大，以便容納連接后的目標(biāo)字符串；否則，會(huì)因長(zhǎng)度不夠而產(chǎn)生問(wèn)題。②連接前兩個(gè)字符串都有結(jié)束標(biāo)志'\0'，連接后“字符數(shù)組”中存儲(chǔ)的字符串的結(jié)束標(biāo)志'\0'被舍棄，只在目標(biāo)串的最后保留一個(gè)'\0'?！纠?.9】把初始化賦值的字符數(shù)組與動(dòng)態(tài)賦值的字符串連接起來(lái)。#include<string.h>main(){charst1[30]="Mynameis";/*注意長(zhǎng)度為30*/charst2[10];printf("Inputyourname:");gets(st2);strcat(st1,st2);puts(st1);}第18頁(yè)/共39頁(yè)6．求字符串長(zhǎng)度──strlen()函數(shù)（len是length的縮寫(xiě)）（1）調(diào)用方式：strlen(字符串)（2）函數(shù)功能：求字符串（常量或字符數(shù)組）的實(shí)際長(zhǎng)度（不包含結(jié)束標(biāo)志）?！纠?.10】#include<string.h>main(){intk;charst[]="Clanguage";k=strlen(st);printf("Thelenthofthestringis%d\n",k);}運(yùn)行結(jié)果為：Thelenthofthestringis10第19頁(yè)/共39頁(yè)7.4數(shù)組在函數(shù)中的應(yīng)用

數(shù)組可以作為函數(shù)的參數(shù)使用，進(jìn)行數(shù)據(jù)傳送。數(shù)組用作函數(shù)參數(shù)有兩種形式:一種是把數(shù)組元素(下標(biāo)變量)作為實(shí)參使用；另一種是把數(shù)組名作為函數(shù)的形參和實(shí)參使用。數(shù)組元素作函數(shù)實(shí)參數(shù)組元素就是下標(biāo)變量，它與普通變量并無(wú)區(qū)別。因此它作為函數(shù)實(shí)參使用與普通變量是完全相同的，在發(fā)生函數(shù)調(diào)用時(shí)，把作為實(shí)參的數(shù)組元素的值傳送給形參，實(shí)現(xiàn)單向的值傳送?！纠?.11】編程實(shí)現(xiàn)對(duì)一數(shù)組中所有元素取絕對(duì)值.#include<math.h>main(){inta[5]={1,-5,4,-7,-4},i;for(i=0;i<5;i++)a[i]=f(a[i]);for(i=0;i<5;i++)printf("%4d",a[i]);}intf(intx){ if(x<0)return-x; elsereturnx;}第20頁(yè)/共39頁(yè)2、數(shù)組名作為函數(shù)參數(shù)

數(shù)組名就是數(shù)組的首地址，因此在數(shù)組名作函數(shù)參數(shù)時(shí)所進(jìn)行的傳送是地址的傳送，所以要求形參必須是和實(shí)參類(lèi)型相同的數(shù)組名，對(duì)于形參必須有明確的數(shù)組說(shuō)明。在實(shí)參與形參進(jìn)行“值傳遞”時(shí)，是把實(shí)參數(shù)組的首地址賦予形參數(shù)組名。形參數(shù)組名取得該首地址之后，也就等于有了實(shí)在的數(shù)組。實(shí)際上是形參數(shù)組和實(shí)參數(shù)組為同一數(shù)組，共同擁有一段內(nèi)存空間?！纠?.12】數(shù)組a中存放了一個(gè)學(xué)生5門(mén)課程的成績(jī)，求平均成績(jī)。floataver(floata[5]){inti;floatav,s=a[0];for(i=1;i<5;i++)s=s+a[i];av=s/5;returnav;}voidmain(){floatsco[5],av;inti;printf("\ninput5scores:\n");for(i=0;i<5;i++)scanf("%f",&sco[i]);av=aver(sco);printf("averagescoreis%5.2f",av);}第21頁(yè)/共39頁(yè)7.5折半查找折半查找又稱(chēng)二分查找，是針對(duì)有序表進(jìn)行查找的簡(jiǎn)單、有效而又較常用的方法。所謂有序表，即要求表中的各元素按關(guān)鍵字的值有序（升序或降序）存放。折半查找不像順序查找那樣，從第一個(gè)記錄開(kāi)始逐個(gè)順序搜索，其基本思想是：首先選取表中間位置的記錄，將其關(guān)鍵字與給定關(guān)鍵字k進(jìn)行比較，若相等，則查找成功；否則，若k值比該關(guān)鍵字值大，則要找的元素一定在表的后半部分（或稱(chēng)右子表），則繼續(xù)對(duì)右子表進(jìn)行折半查找；若k值比該關(guān)鍵字值小，則要找的元素一定在表的前半部分（左子表），同樣應(yīng)繼續(xù)對(duì)左子表進(jìn)行折半查找。每進(jìn)行一次比較，要么找到要查找的元素，要么將查找的范圍縮小一半。如此遞推，直到查找成功或把要查找的范圍縮小為空（查找失?。ＴO(shè)表的長(zhǎng)度為n，表的被查找部分的頭為low，尾為high，初始時(shí)，low=1,high=n,k為關(guān)鍵字的值。

第22頁(yè)/共39頁(yè)【例7.16】已知如下11個(gè)數(shù)據(jù)元素的有序表(關(guān)鍵字即為數(shù)據(jù)元素的值)：

現(xiàn)要查找關(guān)鍵字為21和85的數(shù)據(jù)元素。

假設(shè)指針low和high分別指示待查元素所在范圍的下界和上界，指針mid指示區(qū)間的中間位置，即mid=(low+high)／2。在此例中，low和high的初值分別為1和11，即[1，11]為待查范圍。

第23頁(yè)/共39頁(yè)先看給定值key=21的查找過(guò)程：

a[mid]與給定值key相比較，因?yàn)閍[mid]>key，說(shuō)明待查元素若存在，必在區(qū)間[low，mid-1]的范圍內(nèi)，則令指針high指向第mid-1個(gè)元素，重新求得mid=(1+5)／2=3

仍以a[mid]和key相比，因?yàn)閍[mid]<key，說(shuō)明待查元素若存在，必在[mid+1，high]范圍內(nèi)，則令指針low指向第mid+1個(gè)元素，求得mid的新值為4，比較a[mid]和key，因?yàn)橄嗟龋瑒t查找成功，所查元素在表中序號(hào)等于指針mid的值。

第24頁(yè)/共39頁(yè)源程序：#defineN50intbinsrch(intr[],intn,intk){intmid,low,high,find;low=1;high=n;find=0;/*置區(qū)間初值*/while((low<=high)&&(!find)){mid=(low+high)/2;/*求中點(diǎn)*/if(k==r[mid])find=1;/*已查到*/elseif(k>r[mid])low=mid+1;/*在后半?yún)^(qū)間查找*/elsehigh=mid-1;/*在前半?yún)^(qū)間查找*/}if(find)return(mid);/*查找成功，返回找到元素的位置*/elsereturn(0);/*查找不成功，返回0標(biāo)記*/}第25頁(yè)/共39頁(yè)main(){inta[N],n,i,k,f;printf("請(qǐng)輸入數(shù)據(jù)元素的個(gè)數(shù):\n");scanf("%d",&n);printf("請(qǐng)輸入數(shù)據(jù)元素:\n");for(i=1;i<=n;i++)scanf("%d",&a[i]);printf("請(qǐng)輸入要查找的數(shù)據(jù):\n");scanf("%d",&k);f=binsrch(a,n,k);if(f==0)printf("值為%d的元素不存在。\n",k);elseprintf("%d在數(shù)組中的位置為%d",k,f);}第26頁(yè)/共39頁(yè)7.6數(shù)組元素排序排序(Sorting)是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列.7.6.1插入排序線性插入排序的基本思想是：第1遍，將初始文件中的第1個(gè)記錄看作有序的序列，然后從第2個(gè)記錄開(kāi)始逐個(gè)插入前邊的有序序列，并使插入后，前邊仍有序。第i趟直接插入排序的操作為：在含有i-1個(gè)記錄的有序子序列r[1..i-1]中插入一個(gè)記錄r[i]后，變成含有i個(gè)記錄有序子序列r[1..i]。為了在查找插入位置的過(guò)程中避免數(shù)組下標(biāo)出界，在r[0]處設(shè)置監(jiān)視哨，將r[i]拷貝到r[0]處，當(dāng)從i-1起往前搜索的過(guò)程中，可以同時(shí)后移記錄。直至整個(gè)數(shù)組變成有序?yàn)橹?。整個(gè)排序過(guò)程共進(jìn)行n-1趟插入。第27頁(yè)/共39頁(yè)【例7.17】將數(shù)組（43，21，89，15，43，28）中的元素進(jìn)行升序排列。第28頁(yè)/共39頁(yè)其源程序?yàn)椋?defineN50voidinsertsort(intr[],intn){inti,j; for(i=2;i<=n;i++)/*共進(jìn)行n-1趟*/{r[0]=r[i];/*r[0]為監(jiān)視哨，也可做下邊循環(huán)結(jié)束標(biāo)志*/j=i-1;while(r[j]>r[0]){ r[j+1]=r[j];j--;}r[j+1]=r[0];}}第29頁(yè)/共39頁(yè)main(){inta[N],n,i;printf("請(qǐng)輸入數(shù)據(jù)元素的個(gè)數(shù):\n");scanf("%d",&n);printf("請(qǐng)輸入數(shù)據(jù)元素:\n");for(i=1;i<=n;i++)scanf("%d",&a[i]);insertsort(a,n);printf("升序排列的結(jié)果為:\n");for(i=1;i<=n;i++)printf("%5d",a[i]);}第30頁(yè)/共39頁(yè)7.6.2折半插入排序

在線性插入排序中，我們采用順序查找法來(lái)確定記錄的插入位置。如果（R1，R2，…，Ri-1）是有序子文件，我們可以采用折半查找法來(lái)確定R1的插入位置，這種排序稱(chēng)為折半插入排序?！纠?.18】將數(shù)組（43，21，89，15，43，28）中的元素進(jìn)行升序排列。#defineN50voidbinarysort(intr[],intn)/*按關(guān)鍵字遞增次序?qū)[1],r[2],……,r[n]進(jìn)行折半插入排序*/{inti,j,l,h,mid; for(i=2;i<=n;i++){r[0]=r[i]; l=1; h=i-1;while(l<=h){mid=(l+h)/2;if(r[0]<r[mid])h=mid-1;elsel=mid+1;}for(j=i-1;j>=l;j--)r[j+1]=r[j];r[l]=r[0];}}第31頁(yè)/共39頁(yè)main(){inta[N],n,i;printf("請(qǐng)輸入數(shù)據(jù)元素的個(gè)數(shù):\n");scanf("%d",&n);printf("請(qǐng)輸入數(shù)據(jù)元素:\n");for(i=1;i<=n;i++)scanf("%d",&a[i]);binarysort(a,n);printf("升序排列的結(jié)果為:\n");for(i=1;i<=n;i++)printf("%5d",a[i]);}第32頁(yè)/共39頁(yè)7.7典型習(xí)題分析解答

【例7.19】若有說(shuō)明：inta[3][4]，則對(duì)數(shù)組a元素非法引用的是。A）a［0］［2*1］B）a［1］［3］C）a［4-2］［0］D）a［0］［4］分析：本題考察對(duì)于二維數(shù)組元素引用的原則。對(duì)以上述定義的二維數(shù)組，其最大下標(biāo)的元素對(duì)應(yīng)：a[2][3].答案：D【例7.20】若二維數(shù)組有m列，則在a[i][j]之前的元素的個(gè)數(shù)為A.j*m+iB.i*m+jC.i*m+j-1D.j*m+i-1分析：在C語(yǔ)言中，由于二維數(shù)組在內(nèi)存中是按照行優(yōu)先的順序存儲(chǔ)的，且下標(biāo)的起始值為0，因此在a[i][j]之前有i*m+j個(gè)。答案：B【例7.21】以下選項(xiàng)中合法的數(shù)組說(shuō)明語(yǔ)句是A.ina[]=”string”B.inta[5]={0,1,2,3,4,5}C.chara=”string”D.chara[5]={0,1,2,3,4,5}分析：在C語(yǔ)言中，字符變量中存放的是與字符對(duì)應(yīng)的ASCII碼值，數(shù)值0，1，2，3，4，5對(duì)應(yīng)的字符雖然是不可顯示的字符，但是這些都可以作為控制字符。此時(shí)，數(shù)組的大小有后面的初始化數(shù)據(jù)的數(shù)量決定。答案：D第33頁(yè)/共39頁(yè)【例7.22】以下程序的輸出結(jié)果是：

voidreverse（inta［］,intn）

{inti,t;for（i=0;i<n/2;i++）

{t=a［i］;a［i］=a［n-1-i］;a［n-1-i］=t;}}main（）

{intb［10］={1,2,3,4,5,6,7,8,9,10};inti,s=0;reverse（b,8）;for（i=6;i<10;i++）s+=b［i］;printf（"%d＼n",s）;}A）22B）10C）34D)分析：在main函數(shù)中，調(diào)用reverse函數(shù)將b數(shù)組中的前8個(gè)成員進(jìn)行互置，執(zhí)行完畢后，b數(shù)組中的成員為{8,7,6,5,4,3,2,1,9,10}，然后再執(zhí)行for循環(huán)結(jié)構(gòu)，將b［6］，b［7］...b［9］的值相加，結(jié)果為22。答案：A第34頁(yè)/共39頁(yè)【例7.23】當(dāng)運(yùn)行以下程序時(shí)，從鍵盤(pán)輸入；AhaMA(空格)Aha<CR>，則下面程序的運(yùn)行結(jié)果是#include<stdio.h>main(){chars［80］,c=′a′;inti=0;scanf("%s",s);while(s［i］!=′＼n′){if