第3單元線性數(shù)據(jù)結構二-資料下載頁
2025-07-20 10:04本頁面
【正文】 0 9 d 8 9 B E I J I N G S H A N G H A I 43/53 三 .數(shù)組 ? 數(shù)組的定義 ? 數(shù)組是有限個數(shù)組元素的集合 ? 數(shù)組中所有元素有相同的數(shù)據(jù)類型 ? 每個數(shù)組元素值可以用數(shù)組名和一組下標值唯一的確定； 44/53 ? m行 n列二維數(shù)組可以看作是 m個或 n個一維數(shù)組 : – Amxn = ((a11a12…a1n),(a21a22…a2n),.. – (am1am2…amn)) – 或 : a11 a12 a1n – a21 a22 a2n ? Amxn = – am1 am2 amn ... ... ... ... 45/53 ? 兩種基本的操作： –給定下標，存取相應的數(shù)組元素； –給定下標，修改相應數(shù)組元素的值。 46/53 ? 無論幾維數(shù)組 ,在計算機中都是按一維數(shù)組來存放。 ? 二維數(shù)組存放通常采用兩種方式： –按行優(yōu)先順序 –按列優(yōu)先順序 47/53 1) 按行優(yōu)先順序存儲 ? 按行優(yōu)先將數(shù)組看作若干個行向量 ? 數(shù)組中的每個元素由元素的兩個下標表達式唯一的確定。 ? 地址計算公式： – LOC(aij)=LOC(a11)+(i1)*n+(j1))*L ? L: 每個元素所占的存儲單元 48/53 2)按列優(yōu)先順序存儲 ? 將數(shù)組看作若干個列向量。 ? 數(shù)組中的每個元素由元素的兩個下標表達式唯一的確定。 ? 地址計算公式： – LOC(aij)=LOC(a11)+((j1)*m+(i1))*L ? L: 每個元素所占的存儲單元。 49/53 ? 壓縮的含義： –相同值的多個元素占用一個存儲單元； –零元素不分配存儲單元。 ? (1)特殊矩陣的壓縮存儲 –特殊矩陣 :值相同的元素或非零元素分布有一定規(guī)律的矩陣 –壓縮 :將二維數(shù)組的元素壓縮到一維數(shù)組 –關鍵 :兩個數(shù)組的下標之間建立映象關系 50/53 例 : 對稱矩陣的壓縮存儲 ? 對稱矩陣的元素滿足： – aij = aji 1 ? i ， j ? n ? n*n 個元素壓縮存放到 n（ n+1） /2 個單元的一維數(shù)組中。 ? Aij在一維數(shù)組中的地址為： ? i（ i1） /2+j 當 i?j ? LOC(aij) = ? j（ j1） /2+i 當 ij 51/53 對稱矩陣的壓縮存儲 ? 設有 A3x3矩陣 , ? a11 ? A3x3 = a21 a22 ? a31 a32 a33 ? 存于一維數(shù)組 S[6] ? S[6]=(a11, a21,a22, a31,a32,a33) ? 1 2 3 4 5 6 – LOC(a31)=3(31)/2+1= 4 – LOC(a22)=2(21)/2+2= 3 – LOC(a21)=2(21)/2+1= 2 52/53 ? 常見的特殊矩陣 : –對稱矩陣 存儲主對角線以上 (下 )的元素 –上 (下 )三角矩陣 只存儲三角陣元素； –帶狀矩陣 只存儲帶狀元素； ? (2) 稀疏矩陣的壓縮存儲 – 利用三元組只存儲非零元素； – 三元組 : (i,j,aij) 53/53 作業(yè)、思考題 ? 思考題： – 試寫出“在帶頭結點的單循環(huán)鏈表中求表長的算法”。 – 假設一單循環(huán)鏈表的長度大于 1，且表中即無頭結點也無頭指針。已知 S為指向鏈表中某結點的指針。試寫出刪除表中結點 S 的算法。 – 假設以數(shù)組 sequ[m1]存放循環(huán)隊列的元素，設變量 rear和 quelen分別為指示隊尾元素位置和隊中元素個數(shù)，試寫出入隊和出隊算法。 ? 第 1章作業(yè)： ? 11
職業(yè)教育相關推薦
鄂ICP備17016276號-1