C第四章數(shù)組與指針

第4章數(shù)組與指針第第4章數(shù)組與指針4.2指針及其簡(jiǎn)單應(yīng)用4.4字符串某些程序在運(yùn)行過(guò)程中要處理大批量的數(shù)據(jù)，而且這批數(shù)如成績(jī)分析程序，要對(duì)一個(gè)班級(jí)全體學(xué)生的若干門課程成績(jī)進(jìn)行多種處理(輸入成績(jī)、計(jì)算每位學(xué)生的總分、按總分從高計(jì)人數(shù)等等),顯然，要對(duì)成績(jī)表中數(shù)據(jù)進(jìn)行多次訪問(wèn)，所以100個(gè)未知數(shù))的一次方程組，程序運(yùn)行時(shí)要一直保存方程組據(jù)稱為數(shù)組元素(或數(shù)組分量),數(shù)組元素可以用下標(biāo)(順未知數(shù)x的系數(shù)可以用數(shù)組a表示，其元素為：在這里，區(qū)分g數(shù)組的元素需要一個(gè)順序號(hào)，故稱為一維數(shù)組；而區(qū)分a數(shù)組的元素需要兩個(gè)順序號(hào)，故稱為二維數(shù)我們可以用循環(huán)語(yǔ)句控制下標(biāo)的變化，從而實(shí)現(xiàn)對(duì)數(shù)組元素有規(guī)律的訪問(wèn)。例如，輸入60名學(xué)生的成績(jī)，可描述數(shù)組在使用之前也要定義，即確定數(shù)組的名字、類型、類型符數(shù)組名[常量表達(dá)式];其中，方括號(hào)中的常量表達(dá)式的值表示數(shù)組元素的個(gè)數(shù)，即數(shù)組的大小或長(zhǎng)度。常量表達(dá)式可以包括字面常量和符號(hào)常量以及由它們組成的常量表達(dá)式，但必須是整型。方括號(hào)之前的數(shù)組名是一個(gè)標(biāo)識(shí)符。類型符指出數(shù)組(數(shù)組元素)C++程序設(shè)計(jì)---中南大學(xué)要注意的是方括號(hào)中不能含有變量，下面的定義錯(cuò)誤的：度//企圖根據(jù)N的臨時(shí)輸入值定義數(shù)組的長(zhǎng)如果N是已經(jīng)定義的符號(hào)常量則合法，例如：2.一維數(shù)組元素的引用一維數(shù)組元素的引用形式為：數(shù)組名[下標(biāo)]一個(gè)數(shù)組元素的引用就代表一個(gè)數(shù)據(jù)，它和簡(jiǎn)單變量等同使用。C++規(guī)定，數(shù)組元素的下標(biāo)從0開(kāi)始。在引用數(shù)組元素時(shí)要注意下標(biāo)的取值范圍。當(dāng)所定義數(shù)組的數(shù)組元素的個(gè)數(shù)為M時(shí)，下標(biāo)值取0到M-1之間的整數(shù)。例如上面定義的數(shù)組a有10個(gè)元素，即a[0],a[1],…a[9],如程序引用數(shù)組元素a[i],就要保證程序運(yùn)行時(shí)i不越出0到9的范圍。下標(biāo)可以是整型常量、整型變量或整型表達(dá)式。要給上面的數(shù)組a中數(shù)組元素輸入數(shù)據(jù)可表示如下(假設(shè)i是已定義的整型變量):cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[53.一維數(shù)組的存儲(chǔ)結(jié)構(gòu)C++編譯系統(tǒng)為所定義的一維數(shù)組在內(nèi)存中分配一片連續(xù)的存儲(chǔ)單元，數(shù)組元素按下標(biāo)從小到大連續(xù)排列，每個(gè)元素占用相同的例如，定義數(shù)組a如下：則數(shù)組a的存儲(chǔ)結(jié)構(gòu)如圖4.1所示。數(shù)組名代表數(shù)組在內(nèi)存的起始地址，即第一個(gè)元素的地址(該元素首字節(jié)的地址),圖中數(shù)字1000表示內(nèi)存地址。而每個(gè)數(shù)組元素所占字節(jié)數(shù)相同，因此，根據(jù)數(shù)組元素序號(hào)可以求得數(shù)組各元素在內(nèi)存中的地址，由此地址也可訪問(wèn)數(shù)組元素。后面指針與數(shù)組一節(jié)會(huì)進(jìn)一步解釋。C++程序設(shè)計(jì)--中南大學(xué)4.一維數(shù)組的初始化可在定義數(shù)組的同時(shí)，給出數(shù)組元素的初值。這種表達(dá)形式稱為數(shù)組的初始化。數(shù)組的初始化可用以下幾種方法實(shí)現(xiàn)。(1)順序列出數(shù)組全部元素的初值數(shù)組初始化時(shí)，將數(shù)組元素的初值依次寫在一對(duì)花括號(hào)內(nèi)。例如：經(jīng)上面定義和初始化之后，使得x1[0]、x1[1]、x1[2]、x1[3]的初值分別為0、1、2、3和4。注意，如提供的初值個(gè)數(shù)超過(guò)了數(shù)組元素個(gè)數(shù)，編譯源程序時(shí)會(huì)出現(xiàn)語(yǔ)法錯(cuò)誤。C++程序設(shè)計(jì)---中南大學(xué)(2)僅對(duì)數(shù)組的前面一部分元素設(shè)定初值對(duì)x2前四個(gè)元素設(shè)定了初值，依次為0,1,2,3。編譯系(3)對(duì)全部數(shù)組元素賦初值時(shí)，可以不指定數(shù)組元素的個(gè)數(shù)x3[]={0,1,2,3,4,5,6,7編譯系統(tǒng)根據(jù)花括號(hào)中數(shù)據(jù)的個(gè)數(shù)確定數(shù)組的元素個(gè)數(shù)。所以數(shù)組x3有10個(gè)元素。但若提供的初值個(gè)數(shù)小于數(shù)組應(yīng)有的元素個(gè)數(shù)時(shí)，則方括號(hào)中的數(shù)組元素個(gè)數(shù)值不能省略。C++程序設(shè)計(jì)---中南大學(xué)【例4.1】用數(shù)組求費(fèi)氏(Fibonacci)數(shù)列前20項(xiàng)。分析問(wèn)題：數(shù)列即有次序的一系列數(shù)，在程序中正好可以程序如下：}請(qǐng)思考還可用哪些方法解答業(yè)題序設(shè)計(jì)---中南大學(xué)【例4.2】找出一維數(shù)組中最大、最小元素及它們的下標(biāo)。數(shù)組元素值從鍵盤上輸入。分析：此處定義數(shù)組a,用變量max、min用來(lái)分別保存數(shù)組中的最大、最小值，首先假定第一個(gè)元素既是最大的，也是最小的，即用語(yǔ)句max=min=a[0]對(duì)有元素(a[i])一一比較，把比當(dāng)前max更大的元素值賦給max,比當(dāng)前min更小的賦給min,同時(shí)用變量j,k分別記錄目前最大、最小元素的下標(biāo)。這種有規(guī)律的比較過(guò)程正好可用for語(yǔ)句控制，控制i從0或1遞 C++程序設(shè)計(jì)---中南大學(xué)formax=min=a[0];//假定第一個(gè)元素既是最大的，也是最小的cout<<"\nmax:a["<<j<<”]="<maxminmin}C++程序設(shè)計(jì)---中南大學(xué)【例4.3】將n個(gè)數(shù)按從小到大順序排列后輸出。解答此題分為三個(gè)步驟：第一步：將需要排序的n個(gè)數(shù)存放到一個(gè)數(shù)組中(設(shè)x數(shù)組);第二步：將x數(shù)組中的元素從小到大排序，即x[0]最小、x[1]次之、…、x[n-1]最大。第三步：將排序后的x數(shù)組輸出。其中第二步是關(guān)鍵，實(shí)現(xiàn)這一步的排序算法非常多，如選擇法、冒泡法、插入法、歸并法等。此處采用選擇排序法。選擇排序法的基本思路是：設(shè)有n個(gè)元素(數(shù))要排序，則從中選擇最小的元素與第一個(gè)元素交換，然后從剩余的n-1個(gè)元素中，找一個(gè)最小的數(shù)，將它與第二個(gè)元素互換，這樣重復(fù)n-1次后即可將n個(gè)數(shù)按由小到大排序。若要由大到小只須每次選擇最大的元素。具體過(guò)程是：先把第一個(gè)元素作為最小者，將它與后面的n-1個(gè)元素依次逐個(gè)比較，如第一個(gè)元素大，則與其交換(保證第一個(gè)元素總是最小的),這樣，第一遍就找出了最小數(shù)，并保存在第一個(gè)元素位置。再以第二個(gè)元素(剩余數(shù)據(jù)中的第一個(gè)元素)作為剩余元素中的最小者也將它與后面元素一一比較，若發(fā)現(xiàn)后面元素較小，則與第二個(gè)元素交換。這樣，第二小的數(shù)就找到了，并保存在數(shù)組的第二個(gè)元素中。依此類推，總共經(jīng)過(guò)n-1遍處理后就完成了將n個(gè)數(shù)由小到大排序。該過(guò)程的流程圖如圖4.2(a)。X-1Yj-i+1wjOHYMYj+C++程序設(shè)計(jì)--中南大學(xué)cin>>a[i];//從鍵盤上輸入10個(gè)元素for(j=i+1;j<N;j++)//每遍進(jìn)行10-(i+1)次比較if(a[i]>a[j])準(zhǔn)備排序M準(zhǔn)備排序MrNj<IYNY排序結(jié)束此例中，使用兩重循環(huán)來(lái)實(shí)現(xiàn)排序。外層循環(huán)控制選擇遍數(shù)，若數(shù)組有N個(gè)元素，則共進(jìn)行N-1遍，每一遍選出一個(gè)當(dāng)前范圍最小數(shù)排到合適的位置。內(nèi)層循環(huán)控制每遍選擇的具體操作過(guò)程。循環(huán)控制變量j的初值上交換。值得注意的是以上程序執(zhí)行時(shí)元素的交換并不都是必須的。事實(shí)上，只要記住比較時(shí)小元素的位置，即序號(hào)(用k表示),在內(nèi)循環(huán)結(jié)束后做一次交換即可，Xrj(NrH望計(jì)NY數(shù)組的維數(shù)是指數(shù)組元素的下標(biāo)個(gè)數(shù)，一維數(shù)組的元素只有一個(gè)下標(biāo)，二維數(shù)組的元素則有兩個(gè)下標(biāo)?；蛘哒f(shuō)數(shù)組中的元素需要兩個(gè)下標(biāo)才能區(qū)分。1.二維數(shù)組的定義二維數(shù)組的定義形式為：類型符數(shù)組名[常量表達(dá)式1][常量表達(dá)式2];定義二維數(shù)組a,它有3行4列，邏輯上對(duì)應(yīng)于下面二維陣列：C++把二維數(shù)組看作是一種特殊的一維數(shù)組，而它的成分又是一個(gè)數(shù)組。對(duì)于上述定義的數(shù)組a,把它看作是具有3個(gè)元二維陣列的第一、第二、第三行，每個(gè)元素又是一個(gè)包含4個(gè)元素的一維數(shù)組，如a[0]包含上面二維陣列的第一行4個(gè)元素可看作是一個(gè)一維數(shù)組，而它的元素是一個(gè)n-1維的數(shù)組。由二維數(shù)組可以推廣到多維數(shù)組。多維數(shù)組的定義形式有連續(xù)多個(gè)“[常量表達(dá)式]”。例如：定義了三維數(shù)組b。二維數(shù)組元素的引用形式為：數(shù)組名[下標(biāo)1][下標(biāo)2]下標(biāo)1稱第一維下標(biāo)，下標(biāo)2稱第二維下標(biāo)。因二維數(shù)組邏輯上對(duì)應(yīng)一張表格，故下標(biāo)1又稱行標(biāo)，下標(biāo)2又稱列標(biāo)。如同一維數(shù)組一樣，下標(biāo)可以是整型常量、變量或表達(dá)式。各n維數(shù)組元素的引用形式為數(shù)組名之后緊接連續(xù)n個(gè)“[下3.二維數(shù)組的初始化第一個(gè)花括號(hào)內(nèi)的數(shù)據(jù)給第一行的元素賦初值，第二個(gè)花括號(hào)內(nèi)的數(shù)據(jù)給第二行的元素賦初值，依次類推。這種賦初(2)按元素的排列順序賦初值其效果與上一方式相同，但這種賦初值方法結(jié)構(gòu)性差，容易遺漏。(3)對(duì)部分元素賦初值例如：y3各元素為顯然，其效果是使y3[0][0]=1,y3[0][1]=2,y3[1][0]=0,y3[1][1]=5,y3[2][0]=4,其余元素均為0。也可對(duì)部分行賦初值，例如：y3各元素為中間的行不賦初值則對(duì)應(yīng)的一對(duì)括號(hào)不能省，例如y3各元素為C++程序設(shè)計(jì)---中南大學(xué)(4)如果對(duì)數(shù)組的全部元素都賦初值，定義數(shù)組時(shí)，第一維的元素個(gè)數(shù)可以不指定編譯系統(tǒng)會(huì)根據(jù)給出的初始數(shù)據(jù)個(gè)數(shù)和其它維的元素個(gè)數(shù)確定第一維的元素個(gè)數(shù)。所以數(shù)組y4有2行。在程序中可以用表達(dá)式sizeof(y4)/sizeof(y4[0])自動(dòng)求出數(shù)組的行數(shù)。也可以用分行賦初值方法，只對(duì)部分元素賦初值而省略第一維的元素個(gè)數(shù)，例如也能確定數(shù)組y5共有2行。C++程序設(shè)計(jì)---中南大學(xué) C++編譯系統(tǒng)為一個(gè)數(shù)組分配一片連續(xù)的內(nèi)存單元，每個(gè)存儲(chǔ)單元存放一個(gè)數(shù)組元素。在C++中，二維數(shù)組元素在內(nèi)存中是按行的順序存放的，即從數(shù)組的首地址開(kāi)始，先順序存放第一行的各元素，再存放第二行的各元素，依次類推。例如定義了二維數(shù)組x,它的元素在內(nèi)存中的排列順序如圖4.3所示。5.二維數(shù)組應(yīng)用舉例C++程序設(shè)計(jì)---中南大學(xué)for(j=0;j<3;j++)cin>>a[i][j];for(j=0;j<2;j++)b[i][j]=a[j][i];}}}【例4.5】找出矩陣A?x4中第一個(gè)最大元素以及它的分析：可以將A?x4存于二維數(shù)組a中，然后在a中找第一個(gè)最大元素以及它的行號(hào)和列號(hào)，此題與【例4.2】類似，此處要用變量max保存數(shù)組中的最大值，首先假定第0行(最前面一行)的第0列元素是最大的，即用語(yǔ)句max=a[0][0]對(duì)max進(jìn)行初始化。然后用max與后面所有元素(a[i][j])一一比較，把比max更大的元素值賦給max,同時(shí)用變量row、colum分別記錄其行下標(biāo)和列下標(biāo)；這種有規(guī)律的比較過(guò)程正好可用二重循環(huán)控制，控制i和j變化。比較完后，輸出max、row、 intmain(){inti,j,row,colum,max;inta[M][N];for(i=0;i<M:i++)//輸入a數(shù)組for(j=0;j<N;j++)max=a[0][0];//假定第一行第一列元素是最大的colum=j;}//把當(dāng)前最大值送max,其行下標(biāo)列下標(biāo)送變量row、columcoutnmaxmaxrowrowcolum}C++程序設(shè)計(jì)---中南大學(xué)【例4.6】矩陣乘法。已知m×n矩陣A和n×p矩陣B,試求它們乘積：C=A×B。分析：求兩個(gè)矩陣A和B的乘積分三步：(1)輸入矩陣A和B;(2)求A和B的乘積并用C表示；(3)輸出矩陣C。其中第(2)步是關(guān)鍵。依照矩陣乘法規(guī)則，乘積C必為m×p矩陣，且C的各元素的為了計(jì)算C,需要采用三重循環(huán)。其中，外層循環(huán)(設(shè)循環(huán)變量為i)控制矩陣待求矩陣C的行(i從1到m);中層循環(huán)(設(shè)循環(huán)變量為j)控制矩陣C的列(j從1到p);內(nèi)層循環(huán)(設(shè)循環(huán)變量為k)控制計(jì)算C,的值，顯然，求C的各元素屬于累加問(wèn)題。A、B和C用數(shù)組a、b和c存儲(chǔ)，注意，A存于a[i-1][j-1]中。程序如下：C++程序設(shè)計(jì)--中南大學(xué)N2b[N][P]={{3,2,1,4},{0,7,2,6}2313069315±27124946C++程序設(shè)計(jì)--中南大學(xué)4.1.4數(shù)組作為函數(shù)的參數(shù)數(shù)組元素和含有數(shù)組元素的表達(dá)式同樣可以作為函數(shù)的實(shí)參。數(shù)組元素作為函數(shù)的實(shí)參，與普通變量作實(shí)參一樣，是將數(shù)組元素的值傳給形參，形參的變化不會(huì)影響實(shí)參數(shù)組元素，前面章節(jié)介紹的函數(shù)只對(duì)少數(shù)幾個(gè)參數(shù)進(jìn)行處理，當(dāng)函數(shù)要對(duì)一批數(shù)據(jù)進(jìn)行處理時(shí)，定義函數(shù)時(shí)可以采用數(shù)組作為函數(shù)即數(shù)組第一個(gè)元素的地址，因此，調(diào)用函數(shù)時(shí)實(shí)參應(yīng)該用數(shù)實(shí)參數(shù)組的起始地址傳給形參數(shù)組名，從而形參數(shù)組與實(shí)參數(shù)組對(duì)應(yīng)同一存儲(chǔ)區(qū)域，形參數(shù)組的改變就是對(duì)實(shí)參數(shù)組的改變。地址是一種特別數(shù)據(jù)值，后面指針部分會(huì)詳細(xì)介紹。實(shí)參數(shù)組與形參數(shù)組的類型要相同，維數(shù)要相同。C++C++程序設(shè)計(jì)--中南大學(xué)分析：函數(shù)要對(duì)n個(gè)數(shù)據(jù)求和，故可采用一維數(shù)組作函數(shù)形參，}445213圖4.4數(shù)組名作函數(shù)形參時(shí)參數(shù)結(jié)合單元。由于數(shù)組占用一片連續(xù)的存儲(chǔ)單元，故以后的元素同一存儲(chǔ)單元.以后的元素按存儲(chǔ)順序一一對(duì)而用另一整型形參指出與形參數(shù)組對(duì)應(yīng)的實(shí)參數(shù)組的元素個(gè)數(shù)。如上面sum(intx[],intn)中沒(méi)指出a的長(zhǎng)度，而用n個(gè)形參數(shù)組元素總與某個(gè)實(shí)參數(shù)組元素共用同一存儲(chǔ)單元，所以，函數(shù)運(yùn)行時(shí)對(duì)形參數(shù)組元素的訪問(wèn)就是對(duì)實(shí)參數(shù)組元素的訪問(wèn)，對(duì)形參數(shù)組元素的操作就是對(duì)實(shí)參數(shù)組元素的操作，形參數(shù)組元素的改變會(huì)引起相應(yīng)實(shí)參數(shù)組元素的改變?！纠?.8】編寫函數(shù)對(duì)其形參數(shù)組中的n個(gè)數(shù)用冒泡法按由小冒泡法的基本思想是：相鄰兩數(shù)比較，若前面數(shù)大，則兩數(shù)交換位置，直至最后一個(gè)元素被處理，最大的元素就“沉”到最下面，即在最后一個(gè)元素位置上。這樣，如有n個(gè)元素，共進(jìn)行n-1輪處理，每輪讓剩余元素中最大的元素“沉”到下面，從而完成排序。n-1輪是最多的排序輪數(shù)，而事實(shí)上，只要在某一輪排序中沒(méi)有進(jìn)行元素交換，說(shuō)明已排好序，可以提前退出外循環(huán)，結(jié)束排序。例中通過(guò)設(shè)置標(biāo)志變量flag來(lái)實(shí)現(xiàn)，其初值為0,有交換，flag=1,否則flag=0不變，用break提前結(jié)C++程序設(shè)計(jì)--中南大學(xué)N#include<iostream>for(i=0;i<k-j-1;i++)//控制每一輪處理if(b[i]>b[ib[i+1]=b[i];//相鄰元素交換位置b[i+1]=t;flag=1;//有元素交換位置，標(biāo)志}//沒(méi)有交換元素，結(jié)束循環(huán)a[N];//輸入N個(gè)數(shù)據(jù)到數(shù)組a中//輸入N個(gè)數(shù)據(jù)到數(shù)組a中N4<iomanip>voidprint(intb[],intk)//輸出數(shù)組b的元素//輸入從上例可發(fā)現(xiàn)二維形參數(shù)組的第一維大小可以省，但第二維大小必須指定。用多維數(shù)組作函數(shù)參數(shù)時(shí)，形參的第一維可以不指定大小，但其它維必須指定。另外可發(fā)現(xiàn)函數(shù)調(diào)用用數(shù)組作為參數(shù)可以將函數(shù)處理中得到的多個(gè)結(jié)果值帶回主調(diào)函數(shù)，這也是從被調(diào)函數(shù)獲得多個(gè)結(jié)果的一種方法。4.2指針及其應(yīng)用指針是C++的一種重要數(shù)據(jù)類型，借助指針，用戶可用靈活多變的方式來(lái)訪問(wèn)內(nèi)存中的變量、數(shù)組、字符串、類對(duì)象和調(diào)用函數(shù)；而且用指針可以構(gòu)造非常行過(guò)程中動(dòng)態(tài)地申請(qǐng)的內(nèi)存空間或創(chuàng)建的變量，用指針建立變量之間的邏輯指向關(guān)系；利用指針做函數(shù)參數(shù)，在主調(diào)函數(shù)和被調(diào)函數(shù)間傳遞數(shù)據(jù)更方便。占用內(nèi)存空間。計(jì)算機(jī)如何找到指令，執(zhí)行的指令又如何找到它要處理的變量呢?這得從內(nèi)存地址說(shuō)起。內(nèi)存是以字節(jié)為單位的一片連續(xù)存儲(chǔ)空間，為了便于訪問(wèn)，計(jì)算機(jī)系統(tǒng)給每個(gè)字節(jié)單元一個(gè)唯一的編號(hào)，編號(hào)從0開(kāi)始，第一字節(jié)單元編號(hào)為0,以后各單元按順序連續(xù)編號(hào)，這些編號(hào)稱為內(nèi)存單元的地址，利用地址來(lái)使用具體的內(nèi)存單元，就象用房間編號(hào)來(lái)管理一棟大樓的各個(gè)房間一樣。地址的具體編號(hào)方式與計(jì)算機(jī)體系結(jié)構(gòu)有關(guān)，如同大樓房間編號(hào)方式與大樓結(jié)構(gòu)和管理方式有關(guān)一樣。在C++程序中定義一個(gè)變量，根據(jù)變量類型的不同，編譯系統(tǒng)會(huì)為其分配一定字節(jié)數(shù)的存儲(chǔ)單元。如有下列定義：如有下列定義：則給整型變量a分配4個(gè)字節(jié)的存儲(chǔ)a空間，給字符變量b和c各分配1字節(jié)， 給變量x分配4字節(jié)的存儲(chǔ)空間。內(nèi)存2004b空間分配如圖4.5所示。C我們把系統(tǒng)給變量所分配存儲(chǔ)空間的首字節(jié)地址稱為該變量的地址。如aX的地址為2000,b的地址為2004,x的地址為2006?？梢?jiàn)，地址就象是要訪