[工學(xué)]西北大學(xué)：數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組和廣義表-在線瀏覽
2024-11-30 19:55本頁(yè)面
【正文】 i={ aj1 … ji…jn ， aj1 … ji+1…jn | 1≤jk≤bk， 1≤k≤n 且k≠i， 1≤ji≤bi1， aj1 … ji…jn ， aj1 … ji+1…jn ∈ D，i=1， … ， n} 返回主目錄 基本操作： （ 1） InitArray(A,n,bound1,…,bound n)： 若維數(shù) n和各維的長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組 A，并返回 TRUE； （ 2） DestroyArray（ A）： 銷毀數(shù)組 A； （ 3） GetValue（ A， e, index1, …,index n）： 若下標(biāo)合法，用 e返回?cái)?shù)組 A中由 index1, …,index n所指定的元素的值。由于這個(gè)性質(zhì)，使得對(duì)數(shù)組的操作不象對(duì)線性表的操作那樣，可以在表中任意一個(gè)合法的位置插入或刪除一個(gè)元素。 矩陣 Am n看成 n個(gè)列向量的線性表 ,即 ?j=(a1j,a2j, …,a mj) 返回主目錄 Am n= a12 a12 … a 1j … a 1n a21 a22 … a 2j … a 2n ┇ ┇ ai1 ai2 … a ij … a in ┇ ┇ am1 am2 … a mj … a mn B ‖ ?1 ?2 ┇ ?i ┇ ?m 我們還可以將數(shù)組 Am n看成另外一個(gè)線性表 : B=(?1， ,?2,， … ， ?m)，其中 ?i（ 1≤i ≤m）本身也是一個(gè)線性表，稱為行向量，即： ?I= （ ai1， ai2， … ， aij ， … ， ain）。二維數(shù)組可以看成是線性表的線性表。第 5章 數(shù)組和廣義表 數(shù)組的定義和運(yùn)算 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 特殊矩陣的壓縮存儲(chǔ) 三角矩陣 帶狀矩陣 稀疏矩陣 廣義表 返回主目錄 數(shù)組的定義和運(yùn)算 數(shù)組是一種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴(kuò)充。例如： Am n= a12 a12 ┅ a1j ┅ a1n a21 a22 ┅ a2j ┅ a2n ┇ ┇ ai1 ai2 ┅ aij ┅ ain ┇ ┇ am1 am2 ┅ amj ┅ amn 返回主目錄 Am n= a12 a12 ┅ a1j ┅ a1n a21 a22 ┅ a2j ┅ a2n ┇ ┇ ai1 ai2 ┅ aij ┅ ain ┇ ┇ am1 am2 ┅ amj ┅ amn A=（ ? 1 ? 2 ┅ ?j ┅ ?n) 我們可以把二維數(shù)組看成一個(gè)線性表： A=(? 1 ? 2 … ?j … ?n)，其中 ?j（ 1≤j ≤n）本身也是一個(gè)線性表，稱為 列向量 。 返回主目錄 上面二維數(shù)組的例子，介紹了數(shù)組的結(jié)構(gòu)特性，實(shí)際上數(shù)組是一組有固定個(gè)數(shù)的元素的集合。 對(duì)于數(shù)組的操作一般只有兩類： （ 1）獲得特定位置的元素值； （ 2）修改特定位置的元素值。 （ 4） SetValue（ A， e， index1, …,index n）： 若下標(biāo)合法，則將數(shù)組 A中由 index1, …,index n所指定的元素的值置為 e。 返回主目錄 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 對(duì)于數(shù)組 A，一旦給定其維數(shù) n及各維長(zhǎng)度 bi（ 1≤i≤n），則該數(shù)組中元素的個(gè)數(shù)是固定的，不可以對(duì)數(shù)組做插入和刪除操作，不涉及移動(dòng)元素操作，因此對(duì)于數(shù)組而言，采用順序存儲(chǔ)法比較合適。另一種是 按列序 存儲(chǔ)，如高級(jí)語(yǔ)言中的 FORTRAN語(yǔ)言就是以列序?yàn)橹鳌? 返回主目錄 如果將三維數(shù)組推廣到一般情況 ， 即：用 j1， j2，j3代替數(shù)組下標(biāo) i， j， k；并且 j1， j2， j3的下限為 c1，c2， c3， 上限分別為 d1， d2， d3， 每個(gè)元素占一個(gè)存儲(chǔ)單元 。 返回主目錄 令 α1=1*(d2c2+1)*(d3c3+1), α2=1*(d3c3+1), α3=1， 則： Loc[j1,j2,j3]=Loc[c1,c2,c3]+ α1*(j1c1)+ α2*(j2c2)+ α3(j3c3) =Loc[c1,c2,c3]+ Σαi*(jici) （ 1≤i≤3） 由公式可知 Loc[j1,j2,j3]與 j1,j2,j3呈線性關(guān)系。 Loc[j1， j2， …j n]=Loc[c1， c2， … ， ]+? αi (jici) i=1 n 其中 αi =l ? (dkck+1) （ 1≤i≤n） k=i+1 n 返回主目錄 特殊矩陣的壓縮存儲(chǔ) 特殊矩陣壓縮存儲(chǔ)的壓縮原則是：對(duì)有規(guī)律的元素和值相同的元素只分配一個(gè)存儲(chǔ)單元，對(duì)于零元素不分配空間。對(duì)于一個(gè) n階矩陣 A來(lái)說(shuō)：若當(dāng) ij時(shí)，有aij=0，則稱此矩陣為下三角矩陣；若當(dāng) ij時(shí)，有aij=0，則此矩陣稱為上三角矩陣；若矩陣中的所有元素均滿足 aij=aji，則稱此矩陣為對(duì)稱矩陣。由于下三角矩陣的元素個(gè)數(shù)為 n(n+1)/2，所以可壓縮存儲(chǔ)到一個(gè)大小為 n(n+1)/2的一維數(shù)組中。 其中元素 aij(ij)在數(shù)組 C中的存儲(chǔ)位置為： Loc[i,j]= Loc[1,1]+j(j 1)/2+ i1 對(duì)于對(duì)稱矩陣，因其元素滿足 aij=aji，我們可以為每一對(duì)相等的元素分配一個(gè)存儲(chǔ)空間，即只存下三角（或上三角）矩陣，從而將 n2個(gè)元素壓縮到n(n+1)/2個(gè)空間中。最常見(jiàn)的是三對(duì)角帶狀矩陣。 當(dāng) 1in， j=i1, i, i+1 i=n, j=n1, n。 返回主目錄 三對(duì)角帶狀矩陣的壓縮存儲(chǔ)，以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，并且只存儲(chǔ)非零元素。由此可得到一維向量所需的空間大小為： 3n2。一般地，當(dāng)非零元素個(gè)數(shù)只占矩陣元素總數(shù)的 25%—30%,或低于這個(gè)百分?jǐn)?shù)時(shí)，我們稱這樣的矩陣為稀疏矩陣。我們將這種存儲(chǔ)方法叫做稀疏矩陣的三元組表示法。 /*該非零元素的行下標(biāo)和列下標(biāo) */ ElementType e； /*該非零元素的值 */ }Triple。 /* 非零元素的三元組表 。 /*矩陣的行數(shù) 、 列數(shù)和非零元素的個(gè)數(shù) */ }TSMatrix； 返回主目錄 1）用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算 矩陣轉(zhuǎn)置：指變換元素的位置，把位于（ row， col）位置上的元素?fù)Q到（ col ， row）位置上，也就是說(shuō)，把元素的行列互換。 for(i=0。i++) for (j=0。j++) dest[i][ j]=source[j] [i] 。 B （ i， j， x） ———— （ j， i， x） A 兩種處理轉(zhuǎn)置算法如下： 返回主目錄 算法一、 void TransposeTSMatrix(TSMatrix A, TSMatrix * B) { /*把矩陣 A轉(zhuǎn)置到 B所指向的矩陣中去 。 Bm= 。 Blen= 。 for(k=1。 k++) for(i=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1