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

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