數據結構第九講第一頁，共四十四頁，2022年，8月28日數組1數組的定義和基本運算數組的特點是每個數據元素可以又是一個線性表結構。因此，數組結構可以簡單地定義為：若線性表中的數據元素為非結構的簡單元素，則稱為一維數組，即為向量；若一維數組中的數據元素又是一維數組結構，則稱為二維數組；依次類推，若二維數組中的元素又是一個一維數組結構，則稱作三維數組。結論：線性表結構是數組結構的一個特例，而數組結構又是線性表結構的擴展。舉例：第二頁，共四十四頁，2022年，8月28日第三頁，共四十四頁，2022年，8月28日其中，A是數組結構的名稱，整個數組元素可以看成是由m個行向量和n個列向量組成，其元素總數為m×n。在C語言中，二維數組中的數據元素可以表示成a[表達式1][表達式2]，表達式1和表達式2被稱為下標表達式，比如，a[i][j]。數組結構在創建時就確定了組成該結構的行向量數目和列向量數目，因此，在數組結構中不存在插入、刪除元素的操作。二維數組結構的基本操作：（1）給定一組下標，修改該位置元素的內容Assign(A,item,index1,index2)（2）給定一組下標，返回該位置的元素內容Value(A,item,index1,index2)第四頁，共四十四頁，2022年，8月28日2數組的存儲結構從理論上講，數組結構也可以使用兩種存儲結構，即順序存儲結構和鏈式存儲結構。然而，由于數組結構沒有插入、刪除元素的操作，所以使用順序存儲結構更為適宜。換句話說，一般的數組結構不使用鏈式存儲結構。組成數組結構的元素可以是多維的，但存儲數據元素的內存單元地址是一維的，因此，在存儲數組結構之前，需要解決將多維關系映射到一維關系的問題。舉例：第五頁，共四十四頁，2022年，8月28日假設每個元素占L個存儲單元，下面求地址公式第六頁，共四十四頁，2022年，8月28日第0行第1行第m-1行第0列第1列第m-1列LOC(i,j)=LOC(0,0)+(n*i+j)*LLOC(i,j)=LOC(0,0)+(m*j+i)*L第七頁，共四十四頁，2022年，8月28日3．矩陣的壓縮存儲矩陣是在很多科學與工程計算中遇到的數學模型。在數學上，矩陣是這樣定義的：它是一個由m×n個元素排成的m行（橫向）n列（縱向）的表。下面就是一個矩陣：第八頁，共四十四頁，2022年，8月28日m×n的矩陣第九頁，共四十四頁，2022年，8月28日4特殊矩陣所謂特殊矩陣就是元素值的排列具有一定規律的矩陣。常見的這類矩陣有：對稱矩陣、下（上）三角矩陣、對角線矩陣等等。對稱矩陣的特點是aij=aji，比如，下面就是一個對稱矩陣：第十頁，共四十四頁，2022年，8月28日第十一頁，共四十四頁，2022年，8月28日下（上）三角矩陣的特點是以主對角線為界的上（下）半部分是一個固定的值，下（上）半部分的元素值沒有任何規律。比如，下面是一個下三角矩陣：第十二頁，共四十四頁，2022年，8月28日對角矩陣的特點是所有的非零元素都集中在以主對角線為中心的帶狀區域中。比如，下面就是一個3階對角矩陣：第十三頁，共四十四頁，2022年，8月28日壓縮：為多個值相同的元只分配一個存儲空間，對零元不分配空間.對于這些特殊矩陣，應該充分利用元素值的分布規律，將其進行壓縮存儲。選擇壓縮存儲的方法應遵循兩條原則：一是盡可能地壓縮數據量，二是壓縮后仍然可以比較容易地進行各項基本操作。三種特殊矩陣的壓縮方法：（1）對稱矩陣對稱矩陣的特點是aij=aji。一個n×n的方陣，共有n2個元素，而實際上在對稱矩陣中有n(n-1)/2個元素可以通過其他元素獲得。第十四頁，共四十四頁，2022年，8月28日壓縮的方法是首先將二維關系映射成一維關系，并只存儲其中必要的n(n+1)/2個（主對角線和下三角）元素內容，這些元素的存儲順序以行為主序。舉例：假設定義一個數組型變量：intA[10];第十五頁，共四十四頁，2022年，8月28日設k是對稱矩陣位于（i，j）位置的元素在一維數組中的存放位置。注意第一元素放在a[0]。A[i,j],前i-1行元素的個數為i(i-1)/2,在第i行為第j個的次序為j，而A[1,1]放在a[0],所以k=i(i-1)/2+j-1,(i>=j),A[i,j],當i<j時，由于對稱性，A[i,j]=A[j,i],即看A[j,i]放在什么位置，所以有上面的知識得到：k=j(j-1)/2+i-1,(i<j),第十六頁，共四十四頁，2022年，8月28日(2)下（上）三角矩陣下三角矩陣的壓縮存儲與上面講述的對稱矩陣的壓縮存儲一樣，只是將上三角部分的常量值存儲在0單元，下三角和主對角上的元素從1號單元開始存放。舉例：第十七頁，共四十四頁，2022年，8月28日設k是對稱矩陣位于（i，j）位置的元素在一維數組中的存放位置。對于任意的（i，j），在一維數組中的存放位置可利用下列公式求得：第十八頁，共四十四頁，2022年，8月28日（3）對角矩陣我們以三階對角矩陣為例討論一下它的壓縮存儲方法。對于對角矩陣，壓縮存儲的主要思路是只存儲非零元素。這些非零元素按以行為主序的順序，從下標為1的位置開始依次存放在一維數組中，而0位置存放數值0。第十九頁，共四十四頁，2022年，8月28日

下面我們討論一下對于任意給定的（i，j），求得在一維數組中存儲位置k的方法。注：該矩陣除第一行和最后一行外，每行有3個元素。前i-1行元素的個數：3*(i-1)-1;第i行，第j個位置在第i行的次序為：j-i+2故：k=3*(i-1)-1+j-i+2=3*(i-1)+j-i+1,當i-1<=j<=i+1第二十頁，共四十四頁，2022年，8月28日2.稀疏矩陣的壓縮存儲若一個m×n的矩陣含有t個非零元素，且t遠遠小于m*n，則我們將這個矩陣稱為稀疏矩陣。舉例：注：通常：t/(m*n)<=0.05時稱為稀疏矩陣第二十一頁，共四十四頁，2022年，8月28日稀疏矩陣的壓縮存儲方法——三元組表示法。矩陣中的每個元素都是由行序號和列序號唯一確定的。因此，我們需要用三項內容表示稀疏矩陣中的每個非零元素，即形式為：(i,j,value)其中，i表示行序號，j表示列序號，value表示非零元素的值，通常將它稱為三元。我們將稀疏矩陣中的所有非零元素用這種三元的形式表示，并將它們按以行為主的順序存放在一個一維數組中，就形成了我們所說的三元組表示法。第二十二頁，共四十四頁，2022年，8月28日注：稀疏矩陣可由表示非零元的三元組及其行列數唯一確定。例如（（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），6，4，-7）再加上（6，7）這一對行，列值便可作為矩陣M的另一種描述第二十三頁，共四十四頁，2022年，8月28日//---------稀疏矩陣的三元組順序表存儲表示#defineMAXSIZE125000//最大的非零元素個數typedefstruct{inti,j;//行序號、列序號

ElemTypee;//非零元素值}Triple;typedefstruct{

Tripledata[MAXSIZE+1];//非零元素的三元組表，data[0]未用

intmu,nu,tu;//稀疏矩陣的行數、列數及非零元素個數}TSMatrix;第二十四頁，共四十四頁，2022年，8月28日那么求矩陣的轉置？假設a和b是TSMatrix型的變量，分別表示矩陣M和T,如何a得到b?前兩步很容易實現，關鍵是第三步，我們需要做如下三步：（1）矩陣的行列值互換；（2）將每個三元組中的i和j相互調換；（3）重排三元組之間的次序實現矩陣的轉置；有兩種處理辦法：（1）按照b.data中三元組的次序依次在a.data中找到相應的三元組進行轉置，即，按照矩陣M的列序來進行轉置。其算法如下：第二十五頁，共四十四頁，2022年，8月28日StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//算法5.1//采用三元組順序表存儲表示，求稀疏矩陣M的轉置矩陣Tintp,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;//第1，2步if(T.tu){q=1;for(col=1;col<=M.nu;++col)//第3步for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}第二十六頁，共四十四頁，2022年，8月28日}returnOK;}//TransposeSMatrix注：該算法僅適用于tu<<mu*nu的情況（2）按照a.data中的三元組的次序進行轉置，并將轉置后的三元組置入b中恰當的位置。提示：如果能預先確定矩陣M的每一列（T的每一行）的第一個非零元在b.data中的應有位置，則在對a.data中的三元組依次作轉置時，便可直接放到b.data中的恰當位置，因此在轉置前，映先求得M的每一列中非零元的個數，進而求得每一列的第一個非零元在b.data中的應有位置。第二十七頁，共四十四頁，2022年，8月28日設num和cpot兩個向量，num[col]表示矩陣M中第col列的非零元的個數，cpot[col]指示M中第col列的第一個非零元在b.data中的恰當位置，顯然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];2<=col<=a.nu;第二十八頁，共四十四頁，2022年，8月28日前面矩陣M，num和cpot的值如下所示：第二十九頁，共四十四頁，2022年，8月28日StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組順序表存儲表示，求稀疏矩陣M的轉置矩陣Tintcol,t,p,q;intnum[20],cpot[20];T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)//求M中每一列所含非零元的個數++num[M.data[t].j];cpot[1]=1;//求M中每一列的第一個非零元在b.data中的序號for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}//for}//ifreturnOK;}//FastTransposeSMatrix該轉置方法稱為快速轉置，詳細算法見課本P100第三十頁，共四十四頁，2022年，8月28日注：三元順序表又稱為有序的雙下表法，其特點是：非零元在表中按行序有序存儲，因此便于進行依行順序處理的矩陣運算。對于稀疏矩陣的表示還有：行邏輯鏈接的順序表和十字鏈表第三十一頁，共四十四頁，2022年，8月28日一、選擇題1.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。13B.33C.18D.403.設有數組A[i,j]，數組的每個元素長度為3字節，i的值為1到8，j的值為1到10，數組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為()。A.BA+141B.BA+180C.BA+222D.BA+2254.假設以行序為主序存儲二維數組A=array[1..100，1..100]，設每個數據元素占2個存儲單元，基地址為10，則LOC[5，5]=（）。A.808B.818C.1010D.1020答案：1B,3B,4B第三十二頁，共四十四頁，2022年，8月28日2.有一個二維數組A[1:6，0:7]每個數組元素用相鄰的6個字節存儲，存儲器按字節編址，那么這個數組的體積是（①）個字節。假設存儲數組元素A[1，0]的第一個字節的地址是0，則存儲數組A的最后一個元素的第一個字節的地址是（②）。若按行存儲，則A[2，4]的第一個字節的地址是（③）。若按列存儲，則A[5，7]的第一個字節的地址是（④）。就一般情況而言，當（⑤）時，按行存儲的A[I，J]地址與按列存儲的A[J，I]地址相等。供選擇的答案：①-④：A．12B.66C.72D.96E.114F.120G.156H.234I.276J.282K.283L.288⑤：A．行與列的上界相同B.行與列的下界相同C.行與列的上、下界都相同D.行的元素個數與列的元素個數相同答案：2.1L，2.2J，2.3C，2.4I，2.5C第三十三頁，共四十四頁，2022年，8月28日5.數組A[0..5,0..6]的每個元素占五個字節，將其按列優先次序存儲在起始地址為1000的內存單元中，則元素A[5，5]的地址是()。A.1175B.1180C.1205D.12106.有一個二維數組A[0:8,1:5],每個數組元素用相鄰的4個字節存儲，存儲器按字節編址，假設存儲數組元素A[0,1]的第一個字節的地址是0，存儲數組A的最后一個元素的第一個字節的地址是（①）。若按行存儲，則A[3,5]和A[5,3]的第一個字節的地址是（②）和（③）。若按列存儲，則A[7,1]和A[2,4]的第一個字節的地址是（④）和（⑤）。①-⑤:A.28B.44C.76D.92E.108F.116G.132H.176I.184J.188答案：5.A，6.1H，6.2C，6.3E，6.4A，6.5F第三十四頁，共四十四頁，2022年，8月28日7.將一個A[1..100，1..100]的三對角矩陣，按行優先存入一維數組B[1‥298]中，A中元素A6665（即該元素下標i=66，j=65），在B數組中的位置K為（）。供選擇的答案：198B.195C.1979.二維數組A的每個元素是由6個字符組成的串，其行下標i=0,1,…,8,列下標j=1,2,…,10。若A按行先存儲，元素A[8,5]的起始地址與當A按列先存儲時的元素（）的起始地址相同。設每個字符占一個字節。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]10.若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關系為()。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i答案：7.B，9.B，10.B第三十五頁，共四十四頁，2022年，8月28日8.二維數組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圈從1到10。從供選擇的答案中選出應填入下列關于數組存儲敘述中（）內的正確答案。（1）存放A至少需要（）個字節；（2）A的第8列和第5行共占（）個字節；（3）若A按行存放，元素A[8，5]的起始地址與A按列存放時的元素（）的起始地址一致。供選擇的答案：（1）A.90B.180C.240D.270E.540（2）A.108B.114C.54D.60E.150（3）A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]答案：8.1E，8.2A，8.3B第三十六頁，共四十四頁，2022年，8月28日11.設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數組B[1..n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數組T[N（N+1）/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是（）。A.i（i-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（i-1）/2+113.設二維數組A[1..m，1..n]（即m行n列）按行存儲在數組B[1..m*n]中，則二維數組元素A[i，j]在一維數組B中的下標為()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-1答案：11.B，12.B，13.A第三十七頁，共四十四頁，2022年，8月28日14.有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數占2字節，則用三元組表示該矩陣時，所需的字節數是（）。A.60B.66C.18000D.3315.數組A[0..4,-1..-3,5..7]中含有元素的個數（）。A.55B.45C.36D.1616.用數組r存儲靜態鏈表，結點的next域指向后繼，工作指針j指向鏈中結點，使j沿鏈移動的操作為()。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next17.對稀疏矩陣進行壓縮存儲目的是（）。A．便于進行矩陣運算B．便于輸入和輸出C．節省存儲空間D．降低運算的時間復雜度答案：14.B，15.B，16.A，17.C第三十八頁，共四十四頁，2022年，8月28日二、填空題1.數組的存儲結構采用_______存儲方式。2.設二維數組A[-20..30,-30..20],每個元素占有4個存儲單元,存儲起始地址為200.如按行優先順序存儲,則元素A[25,18]的存儲地址為_______；如按列優先順序存儲,則元素A[-18,-25]的存儲地址為_______。3.設數組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a[45,68]的存儲地址為_______;若以列序為主序順序存儲，則元素a[45,68]的存儲地址為_______。4.將整型數組A[1..8，1..8]按行優先次序存儲在起始地址為1000的連續的內存單元中，則元素A[7，3]的地址是：_______。5.二維數組a[4][5][6]（下標從0開始計，a有4*5*6個元素），每個元素的長度是2，則a[2][3][4]的地址是____。(設a[0][0][0]的地址是1000,數據以行為主方式存儲)第三十九頁，共四十四頁，2022年，8月28日6.設有二維數組A[0..9,0..19],其每個元素占兩個字節，第一個元素的存儲地址為100，若按列優先順序存儲，則元素A[6,6]存儲地址為_______。7.已知數組A[0..9,0..9]的每個元素占5個存儲單元，將其按行優先次序存儲在起始地址為1000的連續的內存單元中，則元素A[6，8]的地址為_______。8.已知二維數組A[1..10，0..9]中每個元素占4個單元，在按行優先方式將其存儲到起始地址為1000的連續存儲區域時，A[5，9]的地址是：_______。9.用一維數組B與列優先存放帶狀矩陣A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8個元素是A中的第_（1）_行，第_（2）_列的元素。11．設n行n列的下三角矩陣A已壓縮到一維數組B[1..n*（n+1）/2]中，若按行為主序存儲，則A[i,j]對應的B中存儲位置為_______。第四十頁，共四十四頁，2022年，8月28日10.設數組A[0..8,1..10],數組中任一元素A[i,j]均占內存48個二進制位，從首地址2000開始連續存放在主內存里，主內存字長為16位，那么（l）存放該數組至少需要的單元數是_______;（2）存放數組的第8列的所有元素至少需要的單元數是_______;（3）數組按列存儲時，元素A[5,8]的起始地址是_______。12.n階對稱矩陣a滿足a[i][j]=a[j