第二章 阵列与矩阵.docx
- 文档编号:4692300
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:45
- 大小:123.23KB
第二章 阵列与矩阵.docx
《第二章 阵列与矩阵.docx》由会员分享,可在线阅读,更多相关《第二章 阵列与矩阵.docx(45页珍藏版)》请在冰点文库上搜索。
第二章阵列与矩阵
第二章陣列與矩陣
2.1有序串列(orderedlist)
(1)定義
Definition:
串列中元素的資料型態為數字,並符合下列特性
(1)可以是空集合{},或是(A1,A2,A3,…,An)
(2)存在唯一的第一個元素A1及最後一個元素An
(3)除A1外,每一元素均有precessor
(4)除An外,每一元素均有successor
(2)StorageTypeofOrderedList
可以分成以下兩種方式
a.staticdatastructure
b.dynamicdatastructure(Linkedlist)
2.2Array
陣列包含一個索引和名稱,電腦只要根據陣列名稱所代表的起始位置與索引所計算出來之相對位移,就可以找到此陣列元素之實際位置並存取資料。
(1)陣列宣告
陣列宣告時需載明事項:
a.起始位置
b.維度
c.陣列名稱
d.索引起始與終止
e.陣列元素個數
f.陣列型態
Ex1.以c++宣告如下
inttest[10];
表示宣告了一個一維陣列、名稱為test,索引起始為test[0],終點為test[9],陣列共有10個數,陣列型態為int。
至於陣列起始位置則由程式決定。
(2)一維陣列
EX.
intA[n];格式如A[0],A[1],A[2],…,A[n]
記憶體位置計算:
假設起始位置為α,每一筆資料所佔空間為d,則A[i]之記憶體位置為
addressofA[i]=α+d*I
實例計算:
假設有一個陣列A[1000],求陣列中任何位置之Address
程式執行方式說明:
包括直接計算及由起始點計算
#include
usingstd:
:
cout;
usingstd:
:
cin;
usingstd:
:
endl;
intmain()
{
inti;
intA[1000]={0};
cout<<"Pleaseinputanumbersmallerthan1000"< cin>>i; cout<<"Bydirectionaloperation,theaddressofA[" < cout<<"ByindirectionaloperationtocounttheaddressfromA[0],theaddressofA["< return0; } (1)二維陣列 ex.intA[m][n];//mrowandncolumn 格式如 A[0][0]A[0][1]…A[0][j]…A[0][n-1] A[1][0]A[1][1]…A[1][j]…A[1][n-1] ……………………………………………………… A[i][0]A[i][1]…A[i][j]…A[i][n-1] A[m-1][0]A[m-1][1]…A[m-1][j]…A[m-1][n-1] 記憶體位置計算: 假設起始位置為α,每一筆資料所佔空間為d,則A[i][j]之記憶體位置為 (1)以列為主(rowmajor): 如c++ A[i][j]=α+(n*i+j)*d (2)以行為主(columnmajor): 如Fortran ㄖA[i][j]=α+(m*j+i)*d 實例計算: 假設有一個陣列A[100][100],求陣列中任何位置之Address #include usingstd: : cout; usingstd: : cin; usingstd: : endl; intmain() { constintm=100;//m=rownumber constintn=100;//n=columnnumber intA[m][n]={0}; inti,j; cout<<"Pleaseinputtherownumber"< cin>>i; cout<<"Pleaseinputthecolnumber"< cin>>j; cout<<"Bydirectionaloperation,theaddressofA[" < cout<<"ByindirectionaloperationtocounttheaddressfromA[0][0],theaddressofA["< return0; } (4)三維陣列 陣列宣告為A[u1][u2][u3],可將陣列想成一個立方體,一樣區分成兩種形式 A.Row-major 將陣列看成具有u1個u2*u3之二維陣列,則A[i][j][k]之位置為 A[i][j][k]=α+i*u2*u3*d+j*u3*d+k*d B.Column-major A[I][j][k]=α+k*u2*u1*d+j*u1*d+i*d 假設有一個陣列A[30][40][50],求陣列中任何位置之Address #include usingstd: : cout; usingstd: : cin; usingstd: : endl; intmain() { constintu1=30;//m=xdirection constintu2=40;//n=ynumber constintu3=50;//k=znumber intA[u1][u2][u3]={0}; inti,j,k; cout<<"Pleaseinputtheinumbersmallerthan30"< cin>>i; cout<<"Pleaseinputthejnumbersmallerthan40"< cin>>j; cout<<"Pleaseinputtheknumbersmaller50"< cin>>k; cout<<"Bydirectionaloperation,theaddressofA[" < cout<<"ByindirectionaloperationtocounttheaddressfromA[0][0],theaddressofA["< return0; } 推廣至多維陣列: 已知A[u1][u2]…[un],求A[i0][i1]…[in]在記憶體中之位置,則 2.3Array基礎(Optional) 2.3.1一維陣列 1.宣告 1.必須說明組成元件之資料型態、陣列名稱及元件數目 Example: floattemp[600];─代表float型態、陣列名稱為temp、元件數目為600 2.有可能陣列數目會有變動,因此通常陣列長度以整數常數(constint)宣告 Example constintsize=5; floattemp[5]={48.4,39.8,40.5,42.6,41.2}; orfloattemp[]={48.4,39.8,40.5,42.6,41.2}; (有初始值則陣列長度可以不指明,由括號內元件的數目自動決定) 2.陣列之記憶體配置說明 constintsize=5; floatPressure[size]; 配置了連續的五個大小為32bits的單元 p[0]p[1]p[2]p[3]p[4] 3.2 6.4 ↑-----------------------------------------------------------↑ p[0]的起始位置3個單元每單元32bitsp[3]的起始位置 3.陣列的下標之使用(subscript) Ex: P[]=3.2;→令3.2為P[0]之值 P[3]=P[0]*2.0;→令P[3]為P[0]之值乘以2.0 4.推廣 (a)配合for迴圈,讓程式撰寫更有效率 Ex: constintsize=5; doubleAverage,sum=0; for(inti=0;i sum+=P[i]; Average=sum/(double)(size); (b)計算最大值 doubleMax; Max=P[0]; for(inti=0;i if(Max Max=P[i] 範例程式1.Array.cpp 程式碼 #include usingstd: : cin; usingstd: : cout; usingstd: : endl; intmain() { constintsize=5; floataverage,max,sum=0; floatP[size]={48.4,39.8,40.5,42.6,41.2}; P[0]=3.2; P[3]=P[0]*2.0; cout<<"OnedimensionalmatrixPis: \n"; for(inti=0;i cout< cout< //CalculationofSumandAveragevalue for(intj=0;j sum+=P[j]; average=sum/(float)(size); cout<<"ThesumofmatrixPis: "< <<",andtheaverageofmatrixPis: "< //CalculationofMatrixvalue max=P[0]; for(intk=0;k if(max max=P[k]; } cout<<"ThemaximumvalueofmatrixPis: "< cout<<"TheaddressofmatrixPis: "<<&P< return0; } 範例程式2.A-5A-1.cpp Useasingle-subscriptedarraytosolvethefollowingproblem.Readin20numbers,eachofwhichisbetween10and100,inclusive.Aseachnumberisread,printitonlyifitisnotaduplicateofanumberalreadyread.Provideforthe“worstcase”inwhichall20numbersaredifferent.Usethesmallestpossiblearraytosolvethisproblem. 程式碼: //A-5A-1 #include usingstd: : cin; usingstd: : cout; usingstd: : endl; intmain() { constintsize=20; doublenumber; boolrepeat; doublematrix[size]={0}; for(inti=0;i { cout<<"Pleaseinputanumberbetween10and100.Thisisthe"< cin>>number; if(i==0) matrix[0]=number; for(intj=0;j { repeat=false; if(number==matrix[j]) { repeat=true; break; } } if(repeat==false) matrix[i]=number; } for(intk=0;k { if(matrix[k]! =0) cout< } return0; } 範例程式3: 寫一程式,將兩個各有5個整數的陣列,合併成一個由大至小排列的陣列。 程式碼: #include usingstd: : cin; usingstd: : cout; usingstd: : endl; #include usingstd: : setw; intmain() { constintm=3; constintn=3; constinto=2; inta[m][n]={{3,2,1},{5,6,7},{2,4,6}}; intb[n][o]={{2,3},{3,4},{6,2}}; intc[m][o]={0}; for(inti=0;i for(intj=0;j for(intk=0;k c[i][k]+=a[i][j]*b[j][k]; cout<<"ThematrixCisasfollow: \n"< for(ints=0;s { for(intt=0;t cout< cout< } return0; } 練習題 1.撰寫程式找出一維陣列元素之最大與最小值,並計算最大值與最小值的差與和 2.設計程式計算兩陣列之sum,其a[]={4,-5,3,5,0,9,-3,2,8,9}, b[]={8,3,-3,4,3,0,9,2,3,9},sum之公式為 sum= 2.3.2陣列當成函數的參數 1.如何將陣列當成函數的參數 (a)宣告時,加[] Ex: floatAverage(float[],int); 代表Average函數傳遞兩個參數,一個是float[],代表以浮點數組成的陣列,一個是整數 1.呼叫: 與一般參數相同 Ex: cout< 代表印出Average(P,size)之回傳值,其中對應宣告範例,可知P為陣列名稱,size為參數 2.定義: 如下範例 floatAverage(floatx[],intM) { … } 代表x[]為具float之陣列 範例 將Array.cpp以函數方式分別撰寫Average(P,size)及Max(P,size)兩個函數 //ArrayFnc.cpp #include usingstd: : cin; usingstd: : cout; usingstd: : endl; //DeclarationofAverage()Function doubleAverage(double[],int); //DeclarationofMax()Function doubleMax(double[],int); //Mainprogram intmain() { constintsize=5; doubleP[size]={48.4,39.8,40.5,42.6,41.2}; P[0]=3.2; P[3]=P[0]*2.0; cout<<"TheaveragevalueofmatrixPis: \n"< cout<<"ThemaximumvalueofmatrixPis: \n"< return0; } //DeclarationofmatrixAverage()function doubleAverage(doublex[],intM) { doublesum=0; for(inti=0;i sum+=x[i]; returnsum/(double)(M); } //DeclarationofmatrixMaximum()function doubleMax(doubley[],intN) { doublemaximum; maximum=y[0]; for(intj=1;j if(maximum maximum=y[j]; } returnmaximum; } C.內含static陣列的函數 Static局部變數不隨函數呼叫結束而消失,每一次函數被呼叫時,static變數的值是上一次呼叫時結束的值 →可應用來避免重複計算相同的陣列元素 範例: Fibonacci數列 程式碼 //Fibo.cpp #include usingstd: : cin; usingstd: : cerr;//standarderrorunbuffered,usedfordisplayingerrormessage usingstd: : cout; usingstd: : endl; constintMaxsize=100;//globalvariable intFibonacci(intn); intmain() { intInputN; cout<<"PleaseinputthelengthofFibonacciSeries"; cin>>InputN; if(InputN>Maxsize) { cerr<<"Maximumsizeexceeded! "; return0; } cout<<"ThedatasofFibonacciSeriesare: "< for(inti=0;i cout< } return0; } intFibonacci(intn) { staticintFib[Maxsize];//Maxsizeisaglobalvariables Fib[0]=Fib[1]=1; for(intj=0;j { if(Fib[j]==0) break; } while(j<=n) { Fib[j]=Fib[j-1]+Fib[j-2]; j++; } returnFib[n]; } 說明: 1.Maxsize為globalvariable,故於Fibonacci函數不需要再定義 2.static陣列Fib的長度預先以Maxsize定義,此陣列不隨函數Fibonacci(i)執行結束而消失 3.函數Fibonacci(i)中,先以 for(inti=0;i { if(Fib[i]==0) break; } 找出到目前為止,已經計算過的元素下標,以避免重複計算 2.3.3二維陣列 二維陣列亦稱為矩陣(matrix)或是表格(table) M= 為兩列(tworow)三行(threecolumn)的矩陣,數學上寫成 在C++中則宣告成floatM[2][3]; 初始化寫法 1.floatM[2][3]={{1.8,4.9,6.8},{6.2,2.1,3.4}}; 2.floatM[2][3]={1.8,4.9,6.8,6.2,2.1,3.4}; 3.floatM[][3]={1.8,4.9,6.8,6.2,2.1,3.4}; 以矩陣M為例,電腦內部以「列」的次序儲存 M[0][0]M[0][1]M[0][2]M[1][0]M[1][1]M[1][2] 1.8 4.9 6.8 6.2 2.1 3.4 ↑---------------------------------------------------------------------------------------↑ M[0][0]起始點+偏移量=M[1][2]的開始位置 →對於一個m n大小的矩陣M而言,M[i][j]所在的位址,相對於從M[0][0]算起,偏移量為i n+j個單位,n為column數 本例中,m=2,n=3,故M[1][2]的(offset)為 →1*3+2=5,若單位為float,每單位有4bytes,則M[1][2]離M[0][0]有20bytes 應用方法 結合巢狀for迴圈進行演算 constintRow=2; constintCol=3; doubleA[Row][Col]; doubleA[Row][Col]={1,2,3,4,5,6};//給定初始值 //平均值計算 doubleSum=0; doubleAverage; for(inti=0;i for(intj=0;j Sum+=A[i][j]; Average=Sum/(double)(Row*Col); 範例程式1. 某汽車公司有兩位業務員,2003年紀銷售量如下 業務員 一 二 三 四 1 30 35 26 32 2 33 34 30 29 利用二維陣列儲存資料,先宣告陣列為intsale[2][4], 佔用4*8=32bytes(int為4bytes) 宣告: introw=2; intcol=4; intsale[row][col]={30,35,26,32,33,34,30,29}; 計算該年度此兩位業務員個別銷售量及總銷售量,平均每季銷售量 程式碼: #in
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二章 阵列与矩阵 第二 阵列 矩阵