C語言程序設(shè)計(jì) 課件 第4章數(shù)組

《程序設(shè)計(jì)》1第4章數(shù)組算法+數(shù)據(jù)結(jié)構(gòu)=程序（1）算法編程解決問題的方法數(shù)據(jù)結(jié)構(gòu)現(xiàn)實(shí)世界中要被處理的信息在程序中的表示形式《程序設(shè)計(jì)》2算法+數(shù)據(jù)結(jié)構(gòu)=程序（2）程序設(shè)計(jì)語言數(shù)據(jù)結(jié)構(gòu)基本的數(shù)據(jù)類型：整數(shù)、實(shí)數(shù)、字符復(fù)雜數(shù)據(jù)：數(shù)組、指針、結(jié)構(gòu)算法通過順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和函數(shù)來實(shí)現(xiàn)；選擇結(jié)構(gòu)：if選擇結(jié)構(gòu)和switch選擇結(jié)構(gòu)；循環(huán)結(jié)構(gòu)：while循環(huán)結(jié)構(gòu)，do-while循環(huán)結(jié)構(gòu)和for循環(huán)結(jié)構(gòu)?！冻绦蛟O(shè)計(jì)》3《程序設(shè)計(jì)》4C語言中的復(fù)雜數(shù)據(jù)說明復(fù)雜數(shù)據(jù)是由若干基本數(shù)據(jù)或其它復(fù)雜數(shù)據(jù)按一定的方法(規(guī)則)構(gòu)造而成的(也稱“導(dǎo)出類型”)C語言包含的構(gòu)造復(fù)雜數(shù)據(jù)類型的構(gòu)造機(jī)制有數(shù)組、結(jié)構(gòu)和指針。利用這幾種構(gòu)造手段，能在基本數(shù)據(jù)類型、指針等類型基礎(chǔ)上，通過反復(fù)應(yīng)用C語言提供的構(gòu)造手段，使程序能描述各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)說明或定義復(fù)雜數(shù)據(jù)必須指出它的成分元素的類型、成分個(gè)數(shù)和構(gòu)造方法。對(duì)于復(fù)雜類型的變量來說，重點(diǎn)是訪問它的元素的方法《程序設(shè)計(jì)》54.1數(shù)組的基本概念4.2一維數(shù)組4.3多維數(shù)組4.4字符串處理技術(shù)基礎(chǔ)目錄4.1數(shù)組的基本概念為什么需要數(shù)組？問題：向計(jì)算機(jī)輸入全班50個(gè)學(xué)生一門課程的成績(jī)。解決：用50個(gè)float型變量表示學(xué)生的成績(jī)？煩瑣，如果有1000名學(xué)生怎么辦呢？沒有反映出這些數(shù)據(jù)間的內(nèi)在聯(lián)系，這些數(shù)據(jù)是同一個(gè)班級(jí)、同一門課程的成績(jī)，具有相同的屬性利用數(shù)組處理批量數(shù)據(jù)《程序設(shè)計(jì)》6《程序設(shè)計(jì)》74.1數(shù)組的基本概念數(shù)組是由若干同類元素組成的對(duì)象數(shù)組的每個(gè)元素的數(shù)據(jù)類型相同，元素個(gè)數(shù)固定，其元素按順序存放，每個(gè)元素對(duì)應(yīng)一個(gè)序號(hào)（稱為下標(biāo)），各元素按下標(biāo)存取（引用）數(shù)組元素的存儲(chǔ)順序與其下標(biāo)相對(duì)應(yīng)，數(shù)組元素的下標(biāo)從0開始順序編號(hào)《程序設(shè)計(jì)》-2008年秋8數(shù)組概念說明數(shù)組元素在數(shù)組中的下標(biāo)是固定不變的，而數(shù)組元素是變量，其值是可以變化的。數(shù)組元素變量與相同類型的獨(dú)立的變量一樣使用程序引用數(shù)組元素變量借助于數(shù)組定義時(shí)為元素變量隱含設(shè)定的下標(biāo)引用數(shù)組元素變量所需的下標(biāo)個(gè)數(shù)由數(shù)組的維數(shù)決定，數(shù)組有一維數(shù)組、二維數(shù)組或多維數(shù)組之分《程序設(shè)計(jì)》-2008年秋9數(shù)組舉例一行正文可以表示成由字符組成的數(shù)組

chars[120];/*字符數(shù)組*/一個(gè)整數(shù)向量可以表示成由整數(shù)組成的數(shù)組

intintVector[80];/*由80個(gè)整數(shù)組成的數(shù)組*/一個(gè)矩陣就可以表示成由向量構(gòu)成的數(shù)組

doublematrix[40][50];/*40行X50列實(shí)數(shù)矩陣*/學(xué)生成績(jī)表可表示成由學(xué)生成績(jī)單組成的數(shù)組

intscore[40][7];/*40名學(xué)生課程成績(jī)，每個(gè)學(xué)生學(xué)7門課程*/4.2一維數(shù)組一維數(shù)組定義一維數(shù)組元素的引用數(shù)組初始化一維數(shù)組程序?qū)嵗芭菖判颉冻绦蛟O(shè)計(jì)》10《程序設(shè)計(jì)》114.2.1

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

類型說明符數(shù)組名[常量表達(dá)式];類型說明符用來指明數(shù)組元素的類型，同一數(shù)組元素的類型相同數(shù)組是一個(gè)變量，用標(biāo)識(shí)符命名，數(shù)組名遵守標(biāo)識(shí)符的命名規(guī)則方括號(hào)“[]”是數(shù)組的標(biāo)志，其中的常量表達(dá)式的值表示數(shù)組的元素個(gè)數(shù)，即數(shù)組的長(zhǎng)度常量表達(dá)式通常是整型常量、符號(hào)常量或sizeof(類型名)，以及由它們組成的常量表達(dá)式C語言約定，當(dāng)數(shù)組名單獨(dú)在程序中使用時(shí)，數(shù)組名可以代表為它分配的內(nèi)存區(qū)域的開始地址，即數(shù)組中下標(biāo)為0的元素的地址【例4.2.1.1】一維數(shù)組示例：inta[10];《程序設(shè)計(jì)》12類型說明符用來指明數(shù)組元素的類型，同一數(shù)組元素的類型相同，如上例“int”；數(shù)組是一個(gè)變量，用標(biāo)識(shí)符命名，數(shù)組名遵守標(biāo)識(shí)符的命名規(guī)則，如上例“a”；方括號(hào)“[]”是數(shù)組的標(biāo)志，其中的常量表達(dá)式的值表示數(shù)組的元素個(gè)數(shù)，即數(shù)組的長(zhǎng)度。常量表達(dá)式通常是整型常量、符號(hào)常量或sizeof(類型名)，以及由它們組成的常量表達(dá)式，如上例，方括號(hào)“[]”內(nèi)的“10”。數(shù)組元素的下標(biāo)從0開始，直至數(shù)組元素的個(gè)數(shù)減一，如上例，下標(biāo)最后到9（10-1）?！冻绦蛟O(shè)計(jì)》13【例4.2.1.1】一維數(shù)組示例inta[10]={35,27,49,18,60,54,77,83,41,2};《程序設(shè)計(jì)》144.2.2一維數(shù)組元素的引用只能引用數(shù)組中的元素，而不能一次整體調(diào)用整個(gè)數(shù)組全部元素的值引用形式:數(shù)組名[下標(biāo)]

例如，inta[5];數(shù)組a的5個(gè)元素可分別用a[0]，a[1]，a[2]，a[3]，a[4]來引用如

a[4]=a[0]+a[1]+a[2]+a[3]；

a[0]=a[i+z];/*如果0<=i+z<5*/《程序設(shè)計(jì)》15一維數(shù)組元素的引用示例設(shè)有定義：intx[20],i;順序輸入數(shù)組x的全部元素

printf("Enterdataforarrayx[].\n");for(i=0;i<20;i++)scanf("%d",&x[i]);

順序輸出x的全部元素

for(i=0;i<20;i++)printf("%d\t",x[i]);《程序設(shè)計(jì)》16【例4.2.2.2】一維數(shù)組元素的引用示例設(shè)仍有定義：intx[20],i;分別統(tǒng)計(jì)數(shù)組x中大于、等于和小于0的元素個(gè)數(shù)

great=equal=less=0;for(i=0;i<20;i++)if(x[i]>0)great++;elseif(x[i]==0)equal++;elseless++;《程序設(shè)計(jì)》17【例4.2.2.3】一維數(shù)組定義及元素引用程序樣例#include<stdio.h>voidmain(){inti,digits[10];for(i=0;i<10;++i)digits[i]=i;for(i=0;i<5;++i)printf("%3d",digits[2*i]);printf("\n");for(i=0;i<5;++i)printf("%3d",digits[2*i+1]);printf("\n\n\n");}程序運(yùn)行結(jié)果

0246813579

【例4.2.2.4】EcologicalPremium試題來源：TheJointEffortContest(WeandRodrigoMalta)，2002在線測(cè)試：UVA10300農(nóng)場(chǎng)主要根據(jù)他們農(nóng)場(chǎng)的條件支付費(fèi)用。支付費(fèi)用的簡(jiǎn)化規(guī)定如下：已知每個(gè)農(nóng)場(chǎng)主的農(nóng)場(chǎng)的面積（平方米）；在農(nóng)場(chǎng)里的動(dòng)物的數(shù)量，這里對(duì)不同的動(dòng)物不做區(qū)分；以及環(huán)境友好系數(shù)，用一個(gè)大于零的整數(shù)表示。農(nóng)場(chǎng)主支付的費(fèi)用基于對(duì)這些參數(shù)進(jìn)行計(jì)算：首先，計(jì)算每頭動(dòng)物平均占據(jù)的平均面積；然后，這個(gè)平均面積（以平方米為單位）乘以環(huán)境友好系數(shù)，得出農(nóng)場(chǎng)主為每頭動(dòng)物支付的費(fèi)用。這樣，農(nóng)場(chǎng)主支付的費(fèi)用，是將農(nóng)場(chǎng)主為每頭動(dòng)物支付的費(fèi)用乘以動(dòng)物的數(shù)量。輸入輸入的第一行給出一個(gè)正整數(shù)n（<20），表示測(cè)試用例的數(shù)量。每個(gè)測(cè)試用例的第一行給出一個(gè)整數(shù)f（0<f<20），表示測(cè)試用例中農(nóng)場(chǎng)主的數(shù)量。在這一行之后，每位農(nóng)場(chǎng)主一行，每行包含三個(gè)正整數(shù)：以平方米為單位的農(nóng)場(chǎng)的面積，在農(nóng)場(chǎng)里的動(dòng)物的數(shù)量，以及表示環(huán)境友好系數(shù)的整數(shù)值。輸入在文件結(jié)束時(shí)終止。輸入中沒有大于100000或小于0的整數(shù)。輸出對(duì)于每個(gè)測(cè)試用例，輸出一行，給出一個(gè)整數(shù)，表示在該測(cè)試用例中農(nóng)場(chǎng)主們的要支付的費(fèi)用的總數(shù)。不要輸出任何空行。試題解析根據(jù)題目描述，可以推導(dǎo)出，每個(gè)農(nóng)場(chǎng)主支付的費(fèi)用是農(nóng)場(chǎng)的面積乘以環(huán)境友好系數(shù)；而農(nóng)場(chǎng)主們的要支付的費(fèi)用的總數(shù)，就是每個(gè)農(nóng)場(chǎng)主支付的費(fèi)用的總和。也就是說，在輸入中給出的農(nóng)場(chǎng)里的動(dòng)物的數(shù)量沒有用處。對(duì)于每個(gè)測(cè)試用例，用3個(gè)一維整型數(shù)組a,b,c，分別表示農(nóng)場(chǎng)的面積，農(nóng)場(chǎng)里的動(dòng)物的數(shù)量，環(huán)境友好系數(shù)這3組批量數(shù)據(jù)。由于輸入說明中已經(jīng)給出了每個(gè)測(cè)試用例的農(nóng)場(chǎng)主數(shù)量f的上限（0<f<20），所以，數(shù)組元素個(gè)數(shù)定為20。外層循環(huán)，每次循環(huán)處理一個(gè)測(cè)試用例。對(duì)于每個(gè)測(cè)試用例，首先，農(nóng)場(chǎng)主們的要支付的費(fèi)用的總數(shù)sum初始化為0，并輸入當(dāng)前測(cè)試用例的農(nóng)場(chǎng)主數(shù)量f；然后，進(jìn)入內(nèi)層循環(huán)，每次循環(huán)，輸入一位農(nóng)場(chǎng)主的數(shù)據(jù)：農(nóng)場(chǎng)的面積，在農(nóng)場(chǎng)里的動(dòng)物的數(shù)量，以及環(huán)境友好系數(shù)；并把農(nóng)場(chǎng)的面積和環(huán)境友好系數(shù)相乘后，累加到sum中?！冻绦蛟O(shè)計(jì)》244.2.3數(shù)組初始化數(shù)組定義的初始化或數(shù)組初始化指的是數(shù)組定義同時(shí)給出元素初值的表述形式數(shù)組初始化形式有數(shù)組定義時(shí)，順序列出數(shù)組全部元素的初值只給數(shù)組的前面一部分元素設(shè)定初值當(dāng)對(duì)數(shù)組的全部元素都明確設(shè)定初值時(shí)，可以不指定數(shù)組元素的個(gè)數(shù)《程序設(shè)計(jì)》25數(shù)組初始化示例-1數(shù)組定義時(shí)，順序列出數(shù)組全部元素初值例如：intd[5]={0,1,2,3,4};將數(shù)組元素的初值依次寫在一對(duì)花括弧內(nèi)，等價(jià)于：

d[0]=0；d[1]=1；d[2]=2；d[3]=3；d[4]=4《程序設(shè)計(jì)》26數(shù)組初始化示例-2只給數(shù)組的前面一部分元素設(shè)定初值例如：inte[5]={0,1,2};定義數(shù)組e有5個(gè)整型元素，其中前3個(gè)元素設(shè)定了初值，而后2個(gè)元素未明確地設(shè)定初值系統(tǒng)約定，當(dāng)一個(gè)數(shù)組的部分元素被設(shè)定初值后，對(duì)于元素為數(shù)值型的數(shù)組，那些未設(shè)定初值的元素自動(dòng)被設(shè)定0值。所以數(shù)組e的后2個(gè)元素的初值為0但是，當(dāng)定義數(shù)組時(shí)，如未對(duì)它的元素指定過初值，對(duì)于內(nèi)部的局部數(shù)組，則它的元素的值是不確定的《程序設(shè)計(jì)》27數(shù)組初始化示例-3當(dāng)對(duì)數(shù)組的全部元素都明確設(shè)定初值時(shí)，可以不指定數(shù)組元素的個(gè)數(shù)例如：intg[]={5,6,7,8,9};由花括號(hào)內(nèi)的初值個(gè)數(shù)確定數(shù)組的元素個(gè)數(shù)若提供的初值個(gè)數(shù)小于數(shù)組希望的元素個(gè)數(shù)時(shí)，則方括號(hào)中的數(shù)組元素個(gè)數(shù)不能省略例如:intb[10]={1,2,3,4,5}數(shù)組b有10個(gè)元素,前5個(gè)如設(shè)定所示，后5個(gè)都為0注意：初值個(gè)數(shù)不允許超過數(shù)組元素個(gè)數(shù)例如：intc[5]={0,1,2,3,4,5}；是錯(cuò)誤的代碼《程序設(shè)計(jì)》28【例4.2.3.1】Fibonacci數(shù)列Fibonacci數(shù)列是一個(gè)自然數(shù)的序列，定義如下：F1=1；F2=1；Fn=Fn-1+Fn-2，其中n>2。編寫程序，用數(shù)組計(jì)算Fibonacci數(shù)列的前30項(xiàng)值。利用數(shù)組存儲(chǔ)Fibonacci數(shù)列的各項(xiàng)值，其中，數(shù)列的前2項(xiàng)可用初值為它設(shè)定?！冻绦蛟O(shè)計(jì)》29Fibonacci數(shù)列（續(xù)）#include<stdio.h>#defineMAXN30#defineAline10voidmain(){longf[MAXN]={1L,1L};intk;

for(k=2;k<MAXN;k++)f[k]=f[k-2]+f[k-1];for(k=0;k<MAXN;k++){if(k%Aline==0)/*每行輸出Aline個(gè)數(shù)*/printf(“\n”);printf(“%8ld”,f[k]);}printf(“\n”);}【例4.2.3.2】FibonacciBase在線測(cè)試：UVA948眾所周知，F(xiàn)ibonacci數(shù)列是從0和1開始，然后，將最后兩個(gè)數(shù)字相加得到下一個(gè)數(shù)字；即f(n)=f(n-1)+f(n-2)，n

2。例如，數(shù)列中的第2個(gè)數(shù)字是1（1＝1+0），第3個(gè)數(shù)字是2（2＝1+1），第4個(gè)數(shù)字是3（3＝2+1），依此類推。下圖給出Fibonacci數(shù)列n

9的情形。Fibonacci數(shù)列在我們生活中出現(xiàn)在許多事情上，有著重要的意義。所有的正整數(shù)都可以表示為Fibonacci數(shù)列中的數(shù)字的和；而且，對(duì)于每個(gè)正整數(shù)，存在若干個(gè)不同的集合，每個(gè)集合由Fibonacci數(shù)列中的數(shù)字組成，集合中的數(shù)字的和等于該正整數(shù)。例如：13可以表示為集合{13}，{5,8}或{2,3,8}中數(shù)字的和，17可以表示為集合{1,3,13}或{1,3,5,8}中的數(shù)字的和。一個(gè)正整數(shù)可以表示成Fibonacci二進(jìn)制數(shù)anan-1…a2，其數(shù)值為an

f(n)+an-1

f(n-1)+……+a2

f(2)，其中，an=1，而{an-1,……,a2}取值0或1。例如，正整數(shù)10可以表示為Fibonacci二進(jìn)制數(shù)10010(fib)，其數(shù)值計(jì)算方式如下：1

f(6)+0

f(5)+0

f(4)+1

f(3)+0

f(2)=1

8+0

5+0

3+1

2+0

1=10。一個(gè)正整數(shù)可以有多個(gè)Fibonacci二進(jìn)制數(shù)表達(dá)，例如，6=5+1=1001(fib)，而6又可以表示成6=3+2+1=111(fib)。因?yàn)槿魏蝺蓚€(gè)連續(xù)的Fibonacci數(shù)的和就是下一個(gè)的Fibonacci數(shù)。為此，本題設(shè)定在集合中不能有兩個(gè)連續(xù)的Fibonacci數(shù)，即Fibonacci二進(jìn)制數(shù)中沒有連續(xù)的1；這樣，每個(gè)正整數(shù)就有一個(gè)唯一的Fibonacci二進(jìn)制數(shù)表示。如上例，6被唯一地被表示為1001(fib)。再例如，17=100101(fib)，如圖所示。給出一個(gè)正整數(shù)的集合，請(qǐng)您將這些數(shù)表示成Fibonacci二進(jìn)制數(shù)。輸入輸入的第一行給出一個(gè)數(shù)字n，表示后面給出多少個(gè)正整數(shù)（1

n

500）。然后給出n行，每行給出一個(gè)小于100000000的正整數(shù)。輸出請(qǐng)您對(duì)輸入中的n個(gè)整數(shù)中的每一個(gè)數(shù)輸出一行，格式為“DECBASE=FIBBASE(fib)”，其中，DECBASE是給出的十進(jìn)制的數(shù)，F(xiàn)IBBASE是以Fibonacci二進(jìn)制數(shù)表示的數(shù)字。請(qǐng)參見樣例輸出。試題解析本題的理論基礎(chǔ)是Zeckendorf（齊肯多夫）定理及其證明。定理4.2.1（Zeckendorf定理）.

任何正整數(shù)都可以表示成若干個(gè)不連續(xù)的Fibonacci數(shù)（不包括第一個(gè)Fibonacci數(shù)）的和。證明：設(shè)f(n)是第n個(gè)Fibonacci數(shù)。采用數(shù)學(xué)歸納法證明。當(dāng)m=1,2,3時(shí)，因?yàn)?=f(2)，2=f(3)，3=f(4)，所以命題成立。假設(shè)對(duì)任何小于正整數(shù)m，命題成立。如果m是Fibonacci數(shù)，則命題對(duì)m也成立。如果m不是Fibonacci數(shù)，則存在n1，滿足f(n1)<m<f(n1+1)。設(shè)m'=m-f(n1)，則m'=m-f(n1)<f(n1+1)-f(n1)=f(n1-1)，即m'<f(n1-1)。因?yàn)閙'<m，所以由歸納假設(shè)，m'可以表示成若干個(gè)不連續(xù)的Fibonacci數(shù)的和，即m'=f(n2)+f(n3)+...+f(nt)，其中n2>n3>...>nt，且n2,n3,...,nt是不連續(xù)的整數(shù)。又因?yàn)閙'<f(n1-1)，所以n2<n1-1，即n2與n1也是不連續(xù)的整數(shù)。所以，m=f(n1)+m'，m=f(n1)+f(n2)+f(n3)+...+f(nt)，其中n1>n2>n3>...>nt，且n1,n2,n3,...,nt是不連續(xù)的整數(shù)。因此，命題成立?！龆鴮?duì)于正整數(shù)m，這樣的和的表達(dá)式m=f(n1)+f(n2)+f(n3)+...+f(nt)也被稱為m的齊肯多夫表示法，由定理4.2.1的證明，可以由貪心算法，即通過每次選取小于等于m的最大的Fibonacci數(shù)，得到m的齊肯多夫表示法。例如，本題中給出的17，小于等于17的最大的Fibonacci數(shù)是第7個(gè)Fibonacci數(shù)13，17-13=4；小于等于4的最大的Fibonacci數(shù)是第4個(gè)Fibonacci數(shù)3，4-3=1；小于等于1的最大的Fibonacci數(shù)是第2個(gè)Fibonacci數(shù)1，1-1=0；所以，17的齊肯多夫表示法是17=13+3+1；采用相應(yīng)的Fibonacci二進(jìn)制數(shù)表示，17=100101(fib)。由于每個(gè)測(cè)試用例都是小于100000000的正整數(shù)，而f(39)<100000000<f(40)，而每個(gè)測(cè)試用例的計(jì)算都要基于Fibonacci數(shù)列；所以，在參考程序中，首先，計(jì)算Fibonacci數(shù)列，并存在數(shù)組f中；數(shù)組初始化intf[40]={0,1}；然后，通過循環(huán)“for(i=2;i<40;++i)f[i]=f[i-1]+f[i-2];”計(jì)算在測(cè)試數(shù)據(jù)范圍內(nèi)Fibonacci數(shù)列。顯然，數(shù)組f的下標(biāo)就是相應(yīng)的Fibonacci數(shù)的序號(hào)。然后，輸入測(cè)試用例數(shù)n，每次循環(huán)處理一個(gè)測(cè)試用例正整數(shù)m：在Fibonacci數(shù)列中，從高到低，找到第一個(gè)不大于自己的Fibonacci數(shù)f[i]，得到新的m=m-f[i]，并且相應(yīng)的Fibonacci二進(jìn)制數(shù)位賦值1（如果當(dāng)前的Fibonacci數(shù)大于m，則相應(yīng)的Fibonacci二進(jìn)制數(shù)位賦值0）；然后重復(fù)這一步驟。【例4.2.3.2】FibonacciBase的參考程序，預(yù)先計(jì)算在測(cè)試數(shù)據(jù)范圍內(nèi)Fibonacci數(shù)列，這樣的做法，被稱為離線計(jì)算方法。離線計(jì)算方法在處理多個(gè)測(cè)試用例的過程中，預(yù)先計(jì)算出指定范圍內(nèi)的所有解，存入某個(gè)常量數(shù)組；以后每測(cè)試一個(gè)測(cè)試用例，直接從常量數(shù)組中引用相關(guān)數(shù)據(jù)就可以了。4.2.4一維數(shù)組程序?qū)嵗邢抟痪S數(shù)組中元素是有限的有序一維數(shù)組中元素一個(gè)接一個(gè)存儲(chǔ)同質(zhì)一維數(shù)組中元素的類型相同//循環(huán)順序處理，每次處理一個(gè)元素，下一次循環(huán)處理下一個(gè)元素《程序設(shè)計(jì)》43《程序設(shè)計(jì)》44【例4.2.4.1】在數(shù)組中找值等于變量key值元素的下標(biāo)在數(shù)組中找值為key的元素，有多種解法直觀解法設(shè)置哨兵法若已順序存放，則用二分法《程序設(shè)計(jì)》45在數(shù)組中找值等于變量key值元素的下標(biāo)-直觀解法從數(shù)組的第一個(gè)元素開始，順序查找至數(shù)組的末尾，若存在值為key的元素，程序就終止查找過程；若不存在值為key的元素，程序?qū)⒄冶檎麄€(gè)數(shù)組。程序段代碼如下

for(i=0;i<n;i++)if(key==a[i])break;/*找到終止循環(huán),若找到則i<n;否則i=n*/查找過程也可用以下代碼來描述

for(i=0;i<n&&key!=a[i];i++);/*找到結(jié)束循環(huán),若找到i<n;否則i=n*/假定每個(gè)元素的查找機(jī)會(huì)均等，則采用上述查找方法，查找的平均次數(shù)v為：v=(1+2+3+…+n)/n=(n+1)/2若在數(shù)組中沒有指定值的元素，則需查找n次《程序設(shè)計(jì)》46在數(shù)組中找值等于變量key值元素下標(biāo)-設(shè)置哨兵先在數(shù)組第n個(gè)元素的后面（如數(shù)組定義時(shí)已預(yù)留了空閑的元素），第n+1元素位置放入要尋找的值（設(shè)置了一個(gè)哨兵），然后再?gòu)牡谝粋€(gè)元素開始順序?qū)ふ?，這能簡(jiǎn)化尋找循環(huán)的控制條件

a[n]=key;for(i=0;key!=a[i];i++);/*若找到i<n；否則i=n*/這種寫法，數(shù)組需多用一個(gè)元素，但程序比前一種更簡(jiǎn)單《程序設(shè)計(jì)》47在數(shù)組中找值等于變量key值元素下標(biāo)-二分法假定數(shù)組a的元素已按它們的值從小到大的順序存放，則二分法是更好的查找方法算法基本思想是對(duì)任意a[i]到a[j](i<=j)的連續(xù)一段元素，根據(jù)它們值的有序性，試探位置m=(i+j)/2上的元素，a[m]與key比較有三種可能結(jié)果，分別采取三種對(duì)策key=a[m]；找到，結(jié)束查找key>a[m]；下一輪的查找區(qū)間為[m+1，j]key<a[m]；下一輪的查找區(qū)間為[i，m-1]當(dāng)j<i時(shí)，區(qū)間[i,j]變?yōu)橐粋€(gè)空區(qū)間，即表示在數(shù)組a中沒有值為key的元素。由于每輪查找后，使查找區(qū)間減半，因此稱為二分法查找。初始查找區(qū)間為i=0，j=n-1《程序設(shè)計(jì)》48在數(shù)組中找值等于變量key值元素下標(biāo)-二分法(續(xù))i=0;j=n-1;/*設(shè)定初始查找區(qū)間*/while(i<=j){m=(i+j)/2;if(key==a[m])break;elseif(key>a[m])i=m+1;elsej=m-1;}

/*找到時(shí)，i<=j，a[m]==key；否則i>j*/【例4.2.4.2】FinancialManagement試題來源：ACMMid-Atlantic2001在線測(cè)試地址：POJ1004，ZOJ1048，UVA2362Larry今年畢業(yè)，找到了工作，并賺了很多錢。但不知為何，Larry總感覺錢不夠用。因此，Larry要用財(cái)務(wù)報(bào)表來解決他的財(cái)務(wù)問題：他要計(jì)算他能用多少錢?，F(xiàn)在可以通過Larry的銀行帳號(hào)看到他的財(cái)務(wù)狀況。請(qǐng)您幫Larry寫一個(gè)程序，根據(jù)過去12個(gè)月他每個(gè)月的收入，計(jì)算要達(dá)到收支平衡，每個(gè)月他平均能用多少錢。輸入輸入12行，每一行是一個(gè)月的收入，收入的數(shù)字是正數(shù)，精確到分，沒有美元的符號(hào)。輸出輸出一個(gè)數(shù)字，是這12個(gè)月收入的平均值。精確到分，前面加美元的符號(hào)，后面加行結(jié)束符。在輸出中沒有空格或其他字符。試題解析【例4.2.4.3】Sub-prime試題來源：BrazilianNationalContest2009在線測(cè)試：UVA11679造成最近的經(jīng)濟(jì)危機(jī)的部分原因，是銀行向無力償還的人發(fā)放貸款，并將這些貸款作為債券轉(zhuǎn)售給其他銀行。顯然，當(dāng)人們無法償還貸款時(shí)，整個(gè)系統(tǒng)就崩潰了。這場(chǎng)危機(jī)非常嚴(yán)重，影響了世界各國(guó)，包括Nlogonia。Nlogonia的ManDashuva總理要求中央銀行主席拿出解決方案。中央銀行主席想出了一個(gè)絕妙的主意：如果所有銀行都只能用自己的貨幣儲(chǔ)備來清算債券，那么所有銀行都會(huì)生存下來，危機(jī)也就會(huì)避免。然而，涉及的債券和銀行的數(shù)量很多，這是一項(xiàng)極其復(fù)雜的任務(wù)，因此中央銀行主席請(qǐng)求您編寫一個(gè)程序，根據(jù)銀行及其印制的債券，確定是否所有銀行都可以僅使用其貨幣儲(chǔ)備和信貸償還債務(wù)。輸入輸入由若干測(cè)試用例組成。每個(gè)測(cè)試用例的第一行給出兩個(gè)整數(shù)b和n，分別表示銀行的數(shù)量（1≤b≤20）和銀行發(fā)行的債券的數(shù)量（1≤n≤20）。銀行用從1到b的整數(shù)來標(biāo)識(shí)。第二行給出用空格分隔的b個(gè)整數(shù)ri，表示b家銀行中每家銀行的貨幣儲(chǔ)備（0≤bi≤104，1≤i≤b）。接下來的n行每行給出三個(gè)用空格分隔的整數(shù)：d，表示債務(wù)人銀行（1≤D≤B）；c，表示債權(quán)人銀行（1≤c≤b并且d

c）；v，表示債券價(jià)值（1≤v≤104）。輸入的最后一行，只包含兩個(gè)用空格分隔的零。輸出對(duì)于每個(gè)測(cè)試用例，程序輸出一行，包含一個(gè)字符：如果可以在沒有Nlogonia中央銀行救助的情況下清算所有債券，輸出“S”；如果需要救助，則輸出“N”。試題解析在借貸關(guān)系中，將錢借給他人的人；稱為債權(quán)人；而向別人借錢，欠別人錢的人稱為債務(wù)人。在輸入中的b家銀行的貨幣儲(chǔ)備用數(shù)組r表示，由于1≤b≤20，銀行用從1到b的整數(shù)來標(biāo)識(shí)，且銀行的貨幣儲(chǔ)備是整數(shù)，所以b家銀行的貨幣儲(chǔ)備說明為“intr[21];”，且r[i]表示第i家銀行的貨幣儲(chǔ)備，1≤i≤20。對(duì)于每個(gè)測(cè)試用例，輸入b家銀行的貨幣儲(chǔ)備；對(duì)于每個(gè)d，c，v，d是債務(wù)人，欠了c的錢v，所以r[d]-=v；相應(yīng)地，c是債權(quán)人，d要還c錢v，r[c]+=v；在b家銀行中，只要有一家銀行的貨幣儲(chǔ)備小于0，輸出“N”；否則輸出“S”。“輸入的最后一行，只包含兩個(gè)用空格分隔的零”，所以，參考程序，每次處理一個(gè)測(cè)試用例的外層循環(huán)以“while(~scanf("%d%d",&b,&n)&&(b||n))”來實(shí)現(xiàn)?！冻绦蛟O(shè)計(jì)》60【例4.2.4.4】輸入n個(gè)整數(shù)存于數(shù)組,對(duì)數(shù)組作整理,使其中小于0的元素移到前面,等于0的元素留在中間,大于0的元素移到后面程序?qū)嵗治鲆胱兞縦、h，設(shè)在整理過程中，a[0]~a[k-1]都小于0，a[h+1]~a[n-1]都大于0。從a[0]開始順序考察，設(shè)當(dāng)前正要考察a[j]。則有a[k]至a[j-1]=0,a[j]至a[h]還未考察過。對(duì)元素a[j]有下列情況a[j]<0:a[j]與a[k]交換，并且j++和k++；a[j]=0:j++；a[j]>0:a[j]與a[h]交換，并且h--；初始時(shí)，j=0,k=0,h=n-1；整理結(jié)束后滿足:j>h《程序設(shè)計(jì)》61初始狀態(tài)：k=j=0;h=n-1《程序設(shè)計(jì)》62（續(xù)）數(shù)組整理程序#include<stdio.h>#defineMAXN1000voidmain(){intj,n,k,temp,h,m;inta[MAXN];printf(“Entern\n”);scanf(“%d”,&n);/*輸入數(shù)組中實(shí)際數(shù)據(jù)*/printf("Entera[0]--a[%d]\n",n-1);for(j=0;j<n;j++)scanf("%d",&a[j]);《程序設(shè)計(jì)》63（續(xù)）數(shù)組整理程序j=k=0;h=n-1;while(j<=h)if(a[j]<0){temp=a[j];a[j]=a[k];a[k]=temp;j++;k++;}elseif(a[j]==0)j++;else{temp=a[j];a[j]=a[h];a[h]=temp;h--;}for(j=0;j<n;j++)printf(“%4d”,a[j]);/*輸出結(jié)果*/printf("\n\n\n");}

《程序設(shè)計(jì)》64【例4.2.4.5】編一個(gè)程序，輸入n個(gè)互不相等的整數(shù)存于數(shù)組，并輸出。程序如發(fā)現(xiàn)輸入的數(shù)據(jù)已輸入過，則要求重新輸入

#include<stdio.h>#defineMAXN1000voidmain(){inti,n,k;inta[MAXN];printf("Entern");scanf("%d",&n);《程序設(shè)計(jì)》65（續(xù)）輸入n個(gè)互不相等的整數(shù)存于數(shù)組，并輸出i=0;while(i<n){printf("Entera[%d]",i);scanf("%d",&a[i]);for(k=0;a[k]!=a[i];k++);/*查是否有重復(fù)*/if(k<i)/*如果重復(fù)*/printf("Error,inputagain!\n");elsei++;/*對(duì)于不重復(fù)情況*/}for(i=0;i<n;i++)printf("%4d",a[i]);printf("\n\n\n");}《程序設(shè)計(jì)》66【例4.2.4.6】按遞增順序生成集合M的前n個(gè)元素。集合M定義如下整數(shù)1屬于M如果整數(shù)X屬于M，則整數(shù)2x+1和3x+1也屬于M再?zèng)]有別的整數(shù)屬于M程序?qū)嵗治龈鶕?jù)集合M的定義，前幾個(gè)元素為M={1，3，4，7，9，…}為存儲(chǔ)M的元素設(shè)計(jì)一個(gè)足夠大的整數(shù)組m，用j表示集合M中已生成的元素個(gè)數(shù)。按題意，首先將1放入集合M中，然后按遞增順序用M中的現(xiàn)有元素枚舉出M的新元素《程序設(shè)計(jì)》68《程序設(shè)計(jì)》69程序?qū)嵗治觯ɡm(xù)）每個(gè)元素可以施行兩種枚舉方法。在按遞增順序枚舉出M的新元素過程中，把M的元素分成以下四部分已執(zhí)行過2x+1枚舉操作的元素已執(zhí)行過3x+1枚舉操作的元素已被枚舉生成，但還未執(zhí)行過任何枚舉操作因還未被枚舉出來，其值還未定義引進(jìn)輔助變量e2和e3，分別用于指出m中下一個(gè)要執(zhí)行2x+1枚舉的元素的下標(biāo)和要執(zhí)行3x+1枚舉的元素的下標(biāo)。為了按遞增順序生成m的元素，下一個(gè)可能執(zhí)行枚舉操作的元素是m[e2]和m[e3]，選擇哪一個(gè)由它們枚舉出來的值更小來確定另設(shè)j為m中已有元素個(gè)數(shù)《程序設(shè)計(jì)》70以下代碼能描述m在第一次枚舉之前的狀態(tài)

m[0]=j=1;e2=e3=0;而一系列的枚舉生成m的n個(gè)元素的C代碼描述如下

while(j<n){if(m[e3]*3+1>=m[e2]*2+1){/*對(duì)m[e2]執(zhí)行2x+1枚舉*/m[j]=m[e2++]*2+1;if(m[e3]*3+1==m[j])e3++;/*當(dāng)兩個(gè)元素枚舉值相同時(shí)，同時(shí)枚舉*/}elsem[j]=m[e3++]*3+1;j++;}4.2.5冒泡排序排序（sorting）將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字遞增或遞減的有序序列。冒泡排序重復(fù)地對(duì)于要排序的元素序列進(jìn)行遍歷，依次比較兩個(gè)相鄰的元素，如果順序錯(cuò)誤，就互換這兩個(gè)元素。這樣的遍歷重復(fù)進(jìn)行，直到?jīng)]有相鄰元素需要互換，也就是說該元素序列的排序已經(jīng)完成。原始序列：2，4，1，3，5；冒泡排序的過程如下：第一輪，對(duì)于相鄰元素，順序錯(cuò)誤則互換，得序列：2，1，3，4，5；第二輪，得序列：1，2，3，4，5。此時(shí)，已經(jīng)沒有相鄰元素需要互換，排序完成。用Ｃ語言描述上述排序過程for(i=0;i<n-1;i++)/*控制n-1次比較調(diào)整遍歷*/for(j=0;j<n-1-i;j++)/*第i次遍歷需比較n-1-i

次*/if(a[j]>a[j+1]){/*a[j]與a[j+1]交換*/temp=a[j];a[j]=a[j+1];a[j+1]=temp;}【例4.2.5.1】Who'sintheMiddle試題來源：USACO2004November在線測(cè)試：POJ2388FJ調(diào)查他的奶牛群，他要找到最一般的奶牛，看最一般的奶牛產(chǎn)多少牛奶：一半的奶牛產(chǎn)奶量大于或等于這頭奶牛，另一半的奶牛產(chǎn)奶量小于或等于這頭奶牛。給出奶牛的數(shù)量：奇數(shù)N(1≤N<10,000)及其產(chǎn)奶量(1..1,000,000)，找出位于產(chǎn)奶量中點(diǎn)的奶牛，要求一半的奶牛產(chǎn)奶量大于或等于這頭奶牛，另一半的奶牛產(chǎn)奶量小于或等于這頭奶牛。輸入第1行:整數(shù)N第2行到第N+1行：每行給出一個(gè)整數(shù)，表示一頭奶牛的產(chǎn)奶量。輸出一個(gè)整數(shù)，位于中點(diǎn)的產(chǎn)奶量。提示對(duì)于樣例輸入，5頭奶牛，產(chǎn)奶量為1..5；因?yàn)?和2低于3，4和5在3之上，所以輸出3。試題解析遞增排序N頭奶牛的產(chǎn)奶量，排序后的中間元素即為位于中點(diǎn)的產(chǎn)奶量。參照冒泡排序C語言程序段，對(duì)輸入的產(chǎn)奶量序列進(jìn)行排序，然后輸出中點(diǎn)的產(chǎn)奶量。參考程序#include<stdio.h>intmain(){inta[10010],N,i,j,temp;scanf("%d",&N);//輸入第1行整數(shù)N，N頭奶牛for(i=0;i<N;i++)//N頭奶牛的產(chǎn)奶量scanf("%d",&a[i]);for(i=0;i<N-1;i++)//冒泡排序N頭奶牛產(chǎn)奶量 for(j=0;j<N-i-1;j++) if(a[j]>a[j+1]) {temp=a[j];a[j]=a[j+1];a[j+1]=temp;}printf("%d\n",a[N/2]);//輸出排序后的中間元素return0; }《程序設(shè)計(jì)》81冒泡排序法的改進(jìn)在冒泡排序過程中，如果某次遍歷未發(fā)生交換調(diào)整情況，這時(shí)數(shù)組實(shí)際上已排好序。程序若發(fā)現(xiàn)這種情況后，應(yīng)提早結(jié)束排序過程為此，程序引入一個(gè)起標(biāo)志作用的變量每次遍歷前，預(yù)置該變量的值為0當(dāng)發(fā)生交換時(shí)，置該變量的值為1一次遍歷結(jié)束時(shí)，就檢查該變量的值，若其值為1，說明發(fā)生過交換，繼續(xù)下一次遍歷；如該變量的值為0，說明未發(fā)生過交換，則立即結(jié)束排序循環(huán)《程序設(shè)計(jì)》82冒泡排序法的改進(jìn)(續(xù))引入標(biāo)志變量flg后相應(yīng)的排序代碼

for(i=0;i<n-1;i++){/*控制n-1次比較調(diào)整遍歷*/for(flg=j=0;j<n-1-i;j++)/*比較n-1-i次*/if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;flg=1;}if(flg==0)break;}《程序設(shè)計(jì)》83冒泡排序法的改進(jìn)(續(xù))更好的改進(jìn)：在冒泡排序過程中，若某次遍歷在某個(gè)位置j發(fā)生最后一次交換，j以后的位置都未發(fā)生交換，則實(shí)際上j以后位置的全部元素都是已排好序的利用這個(gè)性質(zhì)，后一次遍歷的范圍可立即縮短至上一次遍歷的最后交換處程序?yàn)槔眠@個(gè)性質(zhì)，引入每次遍歷的上界變量end，另引入變量k記錄每次遍歷的最后交換位置為了考慮到可能某次遍歷時(shí)一次也不發(fā)生交換的情況，在每次遍歷前時(shí)，預(yù)置變量k為0。一次遍歷結(jié)束后，將k賦給end，作為下一次遍歷的上界。冒泡排序過程至end為0結(jié)束，end的初值為n-1，表示第一次遍歷至最后一個(gè)元素《程序設(shè)計(jì)》84冒泡排序法的改進(jìn)(續(xù))更好的改進(jìn)：按上述想法把冒泡排序代碼改進(jìn)如下

end=n-1;/*end用于記錄本次遍歷范圍的上界*/while(end>0){/*掃視范圍非空時(shí)循環(huán)*/for(k=j=0;j<end;j++)/*比較至end*/ if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;k=j;/*記錄發(fā)生交換的位置*/}end=k;}《程序設(shè)計(jì)》854.3.1多維數(shù)組定義、引用和存放特點(diǎn)4.3.2多維數(shù)組初始化4.3.3多維數(shù)組程序示例4.3多維數(shù)組《程序設(shè)計(jì)》864.3.1多維數(shù)組定義、引用和存放特點(diǎn)二維數(shù)組a[4][6]三維數(shù)組a[5][4][6]行下標(biāo)

i；列下標(biāo)

j頁下標(biāo)

i;行下標(biāo)

j;列下標(biāo)k《程序設(shè)計(jì)》87多維數(shù)組定義二維數(shù)組的定義形式為類型說明符數(shù)組名[常量表達(dá)式][常量表達(dá)式]；多維數(shù)組示例floata[2][3],b[3][4];

/*兩個(gè)二維數(shù)組*/floatc[2][2][3];

/*一個(gè)三維數(shù)組*/二維數(shù)組的元素的存放順序是按行存放，即從數(shù)組首地址開始，先順序存放第一行元素，再存放第二行元素例如，對(duì)于上面數(shù)組a[2][3]，其元素在內(nèi)存中的存放順序?yàn)椋篴[0][0]、a[0][1]、a[0][2]、a[1][0]、a[1][1]、a[1][2]《程序設(shè)計(jì)》88floata[2][3];float型二維數(shù)組，數(shù)組名為a，數(shù)組第一維有2個(gè)元素，數(shù)組第二維有3個(gè)元素；可以把二維數(shù)組a看作一個(gè)一維數(shù)組，它有2個(gè)元素：a[0]和a[1]，每個(gè)元素又是一個(gè)包含3個(gè)元素的一維數(shù)組。多維數(shù)組引用引用二維數(shù)組元素：數(shù)組名[下標(biāo)][下標(biāo)]；其中，“下標(biāo)”可以是整型常量或整型表達(dá)式。二維數(shù)組a[4][6]，引用數(shù)組元素a[2][2]=a[1][1]+2。在用下標(biāo)引用數(shù)組的元素時(shí)，應(yīng)該注意下標(biāo)值的有效性，應(yīng)在已定義的對(duì)應(yīng)維大小的范圍內(nèi)，即大于等于0，和小于對(duì)應(yīng)維的元素個(gè)數(shù)。二維數(shù)組a[4][6]，引用數(shù)組元素a[i][j]，0

i<4，0

j<6?！冻绦蛟O(shè)計(jì)》90多維數(shù)組存放特點(diǎn)一個(gè)多維數(shù)組的元素在內(nèi)存中的存放順序有這樣的特點(diǎn)：第一維的下標(biāo)變化最慢，最右邊的下標(biāo)變化最快例如，對(duì)于前面例子中的三維數(shù)組c[2][2][3]，其元素的存放順序?yàn)閏[0][0][0]、c[0][0][1]、c[0][0][2]、c[0][1][0]、c[0][1][1]、c[0][1][2]、c[1][0][0]、c[1][0][1]、c[1][0][2]、c[1][1][0]、c[1][1][1]、c[1][1][2]?！冻绦蛟O(shè)計(jì)》-2008年秋914.3.2多維數(shù)組初始化按行給二維數(shù)組的全部元素賦初值

inta1[2][3]={{1,2,3},{4,5,6}};按元素存儲(chǔ)順序給數(shù)組元素賦初值

inta2[2][3]={1,2,3,4,5,6};按行給數(shù)組的部分元素賦初值

inta3[2][3]={{1,2},{0,5}};/*其余均為0*/inta4[3][4]={{1},{0,6},{0,0,1}};inta5[3][4]={{1},{5,6}};inta6[3][4]={{1},{},{9}};《程序設(shè)計(jì)》-2008年秋92多維數(shù)組初始化（續(xù)）按元素存儲(chǔ)順序給前面部分元素賦初值

inta4[2][3]={1,2,3,4};/*其余均為0*/按元素存儲(chǔ)順序，給數(shù)組部分或全部元素賦初值，并且不指定第一維的元素個(gè)數(shù)

inta5[][3]={1,2,3,4,5};/*兩行*/用按行賦初值方法，對(duì)各行的部分或全部元素賦初值，并省略第一維的元素個(gè)數(shù)

inta6[][3]={{0,2},{}};/*兩行*/《程序設(shè)計(jì)》-2008年秋934.3.3多維數(shù)組程序示例二維數(shù)組元素按行輸入和按行輸出示意程序

#include<stdio.h>voidmain(){inta[2][3],i,j;for(i=0;i<2;i++)/*二維數(shù)組元素按行輸入*/for(j=0;j<3;j++){printf("Entera[%d][%d]",i,j);scanf("%d",&a[i][j]);}for(i=0;i<2;i++){/*二維數(shù)組元素按行輸出*/for(j=0;j<3;j++)printf("%d\t",a[i][j]);printf("\n");/*按行換行*/}}《程序設(shè)計(jì)》94【例4.3.3.1】有一個(gè)3×4的矩陣，求出其中值最大的那個(gè)元素及其所在的行號(hào)和列號(hào)《程序設(shè)計(jì)》95#include<stdio.h>voidmain(){inti，j，row=0，colum=0，max;inta［3］［4］={{1，2，3，4}，{9，8，7，6}，{-10，10，-5，2}};max=a［0］［0］;for(i=0;i<=2;i++)for(j=0;j<=3;j++)if(a［i］［j］>max){max=a［i］［j］;row=i;colum=j;}

printf("max=%d，row=%d，colum=%d＼n"，max，row，colum);}

輸出結(jié)果為：max=10，row=2，colum=1【例4.3.3.2】PascalLibrary試題來源：ACMSouthAmerica2005在線測(cè)試：POJ2864，UVA3470Pascal大學(xué)是國(guó)家最古老的大學(xué)之一。Pascal大學(xué)要翻新圖書館大樓，因?yàn)榻?jīng)歷了幾個(gè)世紀(jì)后，圖書館開始出現(xiàn)無法承受館藏的巨大數(shù)量的書籍的重量的跡象。為了幫助重建，大學(xué)校友會(huì)決定舉辦一系列的籌款晚宴，邀請(qǐng)所有的校友參加。在過去幾年舉辦了幾次籌款晚宴，這樣的做法已經(jīng)被證明是非常成功的。成功的原因之一是經(jīng)過Pascal教育體系的學(xué)生對(duì)他們的學(xué)生時(shí)代有著美好的回憶，并希望看到一個(gè)重修后的Pascal圖書館。組織者保留了電子表格，表明每一場(chǎng)晚宴有哪些校友參加了。現(xiàn)在，他們希望您幫助他們確定是否有校友參加了所有的晚宴。輸入輸入包含若干測(cè)試用例。一個(gè)測(cè)試用例的第一行給出兩個(gè)整數(shù)n和d，分別給出校友的數(shù)目和組織晚宴的場(chǎng)數(shù)(1≤n≤100，并且1≤d≤500)。校友編號(hào)從1到n。后面的d行每行表示一場(chǎng)晚宴的參加情況，給出n個(gè)整數(shù)xi，如果校友i參加了晚宴，則xi

=1，否則xi

=0。用n=d=0作為輸入結(jié)束。輸出對(duì)于輸入中的每個(gè)測(cè)試用例，你的程序產(chǎn)生一行，如果至少有一個(gè)校友參加了所有的晚宴，則輸出“yes”，否則輸出“no”。試題解析校友的出席籌款晚宴的情況用二維數(shù)組att表示：att[i][j]表示在第i-1場(chǎng)籌款晚宴上第j-1個(gè)校友是否出席，att[i][j]=1表示出席，att[i][j]=0表示沒有出席；在輸入時(shí)對(duì)att進(jìn)行賦值。對(duì)每個(gè)校友出席籌款晚宴的場(chǎng)數(shù)進(jìn)行計(jì)算，設(shè)flag為校友出席籌款晚宴的場(chǎng)數(shù)。如果有校友參加了所有的晚宴，則輸出“yes”；否則輸出“no”。【例4.3.3.3】EventPlanning試題來源：Onemorehighlevelcontest，2009在線測(cè)試：UVA11559盡管您沒有出席NordicClubofPinCollectors的年度會(huì)員大會(huì)，你還是被一致推選組織今年的PinCity觀光旅行。今年秋天，你要為大家選擇一個(gè)周末，并且要找一家合適的酒店住宿，最好盡可能便宜。您會(huì)有一些限制：旅行的總費(fèi)用必須在預(yù)算范圍內(nèi)，所有參加者都必須住在同一家酒店。輸入輸入包含若干測(cè)試用例，每個(gè)測(cè)試用例如下所述。第一行輸入給出四個(gè)整數(shù)：1≤N≤200，參與者人數(shù)；1≤B≤500000，預(yù)算；1≤H≤18，需要考慮的酒店數(shù)量；1≤W≤13，您可以選擇的周末數(shù)。接下來，然后，H家酒店，每家酒店兩行信息：第一行給出1≤p≤10000，即一個(gè)人在這家酒店住一個(gè)周末的價(jià)格；第二行給出W個(gè)整數(shù)，0≤a≤1000，表示這家酒店在每個(gè)周末可以提供的床位數(shù)量。輸出對(duì)于每個(gè)測(cè)試用例，輸出一行，給出最低的預(yù)算，如果最低預(yù)算超過給定預(yù)算值，則輸出“stayhome”。試題解析處理的數(shù)據(jù)H家酒店，用一維整數(shù)數(shù)組p[18]表示周末單價(jià)；H家酒店W個(gè)周末，用二維整數(shù)數(shù)組a[18][13]表示每個(gè)周末每家酒店的床位數(shù)。每次循環(huán)處理一個(gè)測(cè)試用例。對(duì)于每個(gè)測(cè)試用例，外層循環(huán)，每次循環(huán)處理一個(gè)周末；內(nèi)層循環(huán)，每次循環(huán)處理一家酒店，循環(huán)體內(nèi)判斷：這家酒店在這個(gè)周末是否有足夠的床位（a[i][j]>=n），并且費(fèi)用是否小于當(dāng)前的最低預(yù)算（p[i]*n<minb），如果是，則調(diào)整最低預(yù)算為當(dāng)前費(fèi)用（minb=p[i]*n）。最后，輸出結(jié)果?！冻绦蛟O(shè)計(jì)》106多維數(shù)組程序示例-2把某月的第幾天轉(zhuǎn)換成年的第幾天程序?qū)嵗治鰹榇_定一年中的第幾天，需要一張每月的天數(shù)表，該表給出每個(gè)月份的天數(shù)。由于二月份天數(shù)因閏年和非閏年有所不同，為程序處理方便，把月份天數(shù)表組織成一個(gè)二維數(shù)組《程序設(shè)計(jì)》-2008年秋107多維數(shù)組程序示例-2(續(xù))（續(xù)）把某月的第幾天轉(zhuǎn)換成年的第幾天

#include<stdio.h>intday_table[][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};voidmain(){intyear,month,day,leap,i;printf("Inputyear,month,day.\n");scanf("%d%d%d",&year,&month,&day);

leap=year%4==0&&year%100||year%400==0;for(i=0;i<month-1;i++)day+=day_table[leap][i];printf("\nThedaysinyearis%d.\n",day);}《程序設(shè)計(jì)》108多維數(shù)組程序示例-3已知年份與年中的第幾天，計(jì)算該天是這年的哪一月和哪一日

#include<stdio.h>intday_table[][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};charmonthname[][10]={"January","February","March","April","May","June","July","August","September","Octorber","November","December"};《程序設(shè)計(jì)》109多維數(shù)組程序示例-3(續(xù))（續(xù)）已知年份與年中的第幾天，計(jì)算該天是這年的哪一月和哪一日

voidmain(){intyear,day,leap,i;printf("Inputyear,dayofyear.\n");scanf("%d%d",&year,&day);leap=year%4==0&&year%100||year%400==0;for(i=0;day>day_table[leap][i];i++)day-=day_table[leap][i];printf("Themonthis%s,theDayis%d.\n",monthname[i],day);}《程序設(shè)計(jì)》110多維數(shù)組程序示例-4輸入整數(shù)n，輸出以下形式的二維數(shù)組

123...nn12...n-1n-1n1...n-2...234...1注：上面問題有多種解法《程序設(shè)計(jì)》111多維數(shù)組程序示例-4(續(xù))解法1：先給出第0行,然后利用i行與i-1行的關(guān)系,求出i行

for(j=0;j<n;j++)/*先形成第0行*/a[0][j]=j+1;for(i=1;i<n;i++){a[i][0]=a[i-1][n-1];/*生成i行的第0列*/ for(j=1;j<n;j++)/*生成i行的其余列*/ a[i][j]=a[i-1][j-1];}《程序設(shè)計(jì)》112多維數(shù)組程序示例-4(續(xù))解法2：將i行的內(nèi)容分成兩部分i行內(nèi)容:n-i+1...n1...n-ifor(i=0;i<n;i++){k=1; for(j=i;j<n;j++)/*右上部分*/ a[i][j]=k++; for(j=0;j<i;j++)/*左下部分*/ a[i][j]=k++;}《程序設(shè)計(jì)》113多維數(shù)組程序示例-4(續(xù))解法3：將方法2中的變量k去掉,直接代入算式

for(i=0;i<n;i++){for(j=i;j<n;j++)a[i][j]=j-i+1;for(j=0;j<i;j++)a[i][j]=j-i+1+n;}解法4：將方法3中的兩個(gè)j循環(huán)合并

for(i=0;i<n;i++)for(j=0;j<n;j++)a[i][j]=j<i?j-i+1+n:j-i+1;《程序設(shè)計(jì)》114多維數(shù)組程序示例-4(續(xù))解法5：將4中的條件表達(dá)式簡(jiǎn)化

for(i=0;i<n;i++)for(j=0;j<n;j++)a[i][j]=(j-i+n)%n+1；解法6：先給出第0行,再由i行與0行的關(guān)系求出i行

for(j=0;j<n;j++)a[0][j]=j+1;for(i=1;i<n;i++)for(j=0;j<n;j++)a[i][j]=a[0][(j-i+n)%n];《程序設(shè)計(jì)》115多維數(shù)組程序示例-4(續(xù))解法7：對(duì)i行，從i列開始，從順將整數(shù)填入到數(shù)組中

for(i=0;i<n;i++)for(j=i;j<i+n;j++)/*i行從j列開始填n次*/a[i][j%n]=j-i+1;還有許多填值的方法，請(qǐng)大家自已再想出方法，并寫出C實(shí)現(xiàn)代碼《程序設(shè)計(jì)》116多維數(shù)組程序示例-5形成以下形式的二維數(shù)組(以n=4為例)，并輸出

11192024251012182123491317223581416126715程序?qū)嵗治鰊*n的二維數(shù)組，共有2n-1條斜線，將它們順次編號(hào)為1至2*n-1第奇數(shù)條斜線從左上往右下;第偶數(shù)條斜線從右下往左上《程序設(shè)計(jì)》117多維數(shù)組程序示例-5(續(xù))程序?qū)嵗治?續(xù))程序按從左下角至右上角的順序逐條斜線填數(shù)。斜線的填數(shù)方向按斜線的奇偶性交替變化每條斜線的行列起始位置的變化規(guī)律與斜線位于下三角或上三角有不同對(duì)于下三角，第奇數(shù)條斜線從左上往右下，起始行號(hào)為n-d（d為斜線編號(hào)，下同），起始列號(hào)為0；第偶數(shù)條斜線從右下往左上，起始行號(hào)為n-1,起始列號(hào)為d-1對(duì)于上三角，第奇數(shù)條斜線從上往下，起始行號(hào)為0，起始列號(hào)為d-n；第偶數(shù)條斜線從下往上，起始行號(hào)為2*n-1-d,起始列號(hào)為n-1《程序設(shè)計(jì)》118多維數(shù)組程序示例-5(續(xù))按以上情況分類，寫出程序如下

#include<stdio.h>#defineMAXN10inta[MAXN][MAXN];voidmain(){inti,j,k,d,n;while(1){/*n不超過10*/printf("Entern");scanf("%d",&n);

if(n>=1&&n<=10)break;printf("Error!nmustbein[1,10]\n");}《程序設(shè)計(jì)》119多維數(shù)組程序示例-5(續(xù))程序（續(xù)）

for(k=d=1;d<=2*n-1;d++){if(d<=n-1)/*左下三角*/ if(d%2)/*奇數(shù)號(hào)斜線，從左上往右下*/for(i=n-d,j=0;i<n;i++,j++) a[i][j]=k++; else/*偶數(shù)號(hào)斜線，從右下往左上*/for(i=n-1,j=d-1;i>=n-d;i--,j--)a[i][j]=k++;《程序設(shè)計(jì)》120多維數(shù)組程序示例-5(續(xù))程序（續(xù)）

else/*d>=n，右上三角*/if(d%2)for(i=0,j=d-n;i<=2*n-1-d;i++,j++)a[i][j]=k++;elsefor(i=2*n-1-d,j=n-1;i>=0;i--,j--)a[i][j]=k++;}for(i=0;i<n;i++){for(j=0;j<n;j++)printf("%4d",a[i][j]);printf("\n");}}4.4字符串處理技術(shù)基礎(chǔ)字符和對(duì)應(yīng)的ASCII碼是等價(jià)的字符串（String）是由零個(gè)或多個(gè)字符組成的有限序列。一般記為