數(shù)據(jù)結(jié)構(gòu)第九講

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

下面我們討論一下對于任意給定的（i，j），求得在一維數(shù)組中存儲位置k的方法。注：該矩陣除第一行和最后一行外，每行有3個(gè)元素。前i-1行元素的個(gè)數(shù)：3*(i-1)-1;第i行，第j個(gè)位置在第i行的次序?yàn)椋簀-i+2故：k=3*(i-1)-1+j-i+2=3*(i-1)+j-i+1,當(dāng)i-1<=j<=i+1第20頁，共44頁，2023年，2月20日，星期六2.稀疏矩陣的壓縮存儲若一個(gè)m×n的矩陣含有t個(gè)非零元素，且t遠(yuǎn)遠(yuǎn)小于m*n，則我們將這個(gè)矩陣稱為稀疏矩陣。舉例：注：通常：t/(m*n)<=0.05時(shí)稱為稀疏矩陣第21頁，共44頁，2023年，2月20日，星期六稀疏矩陣的壓縮存儲方法——三元組表示法。矩陣中的每個(gè)元素都是由行序號和列序號唯一確定的。因此，我們需要用三項(xiàng)內(nèi)容表示稀疏矩陣中的每個(gè)非零元素，即形式為：(i,j,value)其中，i表示行序號，j表示列序號，value表示非零元素的值，通常將它稱為三元。我們將稀疏矩陣中的所有非零元素用這種三元的形式表示，并將它們按以行為主的順序存放在一個(gè)一維數(shù)組中，就形成了我們所說的三元組表示法。第22頁，共44頁，2023年，2月20日，星期六注：稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。例如（（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的另一種描述第23頁，共44頁，2023年，2月20日，星期六//---------稀疏矩陣的三元組順序表存儲表示#defineMAXSIZE125000//最大的非零元素個(gè)數(shù)typedefstruct{inti,j;//行序號、列序號

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

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

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