第3單元線性數(shù)據(jù)結(jié)構(gòu)二主講：劉志強(qiáng)-資料下載頁

【導(dǎo)讀】它們的特點(diǎn)與一般線性表有哪些異同？算法中體現(xiàn)出處理的差異來。物理結(jié)構(gòu)及有關(guān)操作。棧、隊(duì)列、數(shù)組、串的:. ；棧底固定，而棧頂浮動(dòng)；–棧中元素個(gè)數(shù)為零時(shí)稱為空棧。入棧操作時(shí)，就要產(chǎn)生上溢。Empty判定棧是否為空；棧的順序存儲(chǔ)結(jié)構(gòu)稱為順序棧。置隨進(jìn)棧和出棧而變化。有三個(gè)元素的進(jìn)棧序列是1，2，3。棧頂指針top上移(加1)；在top所指的位置插入元素x。棧下溢信息，并停止執(zhí)行；否則，–step3棧頂指針top下移(減1)。多棧共享是充分利用棧空間的一種策略。置動(dòng)態(tài)移動(dòng)，兩個(gè)棧之間的分界線是不定的。于更多的棧就難于表達(dá)了。況，就不能使用順序棧了。就需要采用鏈棧。鏈棧存儲(chǔ)結(jié)構(gòu)的C語言描述：。則表示鏈滿;否則,執(zhí)行step2;并將top指向新申請(qǐng)的結(jié)點(diǎn)t。

　　

【正文】 下一頁 上一頁 停止放映 第 77/89 頁 數(shù)組的定義 數(shù)組是相同類型數(shù)據(jù)元素的有限集合； 數(shù)組中的各個(gè)分量稱為數(shù)組元素； 每個(gè)數(shù)組元素值可以用數(shù)組名和一個(gè)下標(biāo)值唯一的確定； 下一頁 上一頁 停止放映 第 78/89 頁 數(shù)組的邏輯結(jié)構(gòu)的形式定義 二維數(shù)組 2_Array=(D,R) D 是某種數(shù)據(jù)類型的有限元素集合 ,且 D={ aij|i=c1,d1,j=c2,d2,aij ?D0 } R是行、列關(guān)系的有限集合，且 R={ ROW ， COL }，又 ROW={aij,aij+1|c1?i?d1,c2?j?d21,aij,aij+1?D0} COL={aij,ai+1j|c1?i?d11,c2?j?d2,aij,ai+1j?D0} ci 是第 i維的下界 dj 是第 j維的上界 兩維數(shù)組的元素個(gè)數(shù)為 : (d1c1+1)*(d2c2+1) 下一頁 上一頁 停止放映 第 79/89 頁 N維數(shù)組的邏輯結(jié)構(gòu)的形式定義 N維數(shù)組 n_Array=( D , R ) ji=ci， di， i=1， 2， … n D = aj1j2… jn| aj1… jn ? D0 R={ R1 ,R2， … Rn }，又 ck?jk?dk 1 ? k ?n , ik Ri= aj1… jn,aj1,… ji+1… jn| ci?ji?di1 aj1… ji… jn ? D0 N維數(shù)組的元素個(gè)數(shù)為 : (d1c1+1)*(d2c2+1)*… .(dn+1) = ? (dici+1) n i =1 下一頁 上一頁 停止放映 第 80/89 頁 數(shù)組元素之間的關(guān)系 二維數(shù)組 m行 n列可以看作是 m個(gè)或 n個(gè)一維數(shù)組 : Amxn = ((a11a12… a1n),(a21a22… a2n),.. (am1am2… amn)) 或 : a11 a12 a1n a21 a22 a2n Amxn = am1 am2 amn ... ... ... ... 下一頁 上一頁 停止放映 第 81/89 頁 數(shù)組的操作 數(shù)組有兩種基本的操作： – 給定下標(biāo)，存取相應(yīng)的數(shù)組元素； – 給定下標(biāo)，修改相應(yīng)數(shù)組元素的值。 下一頁 上一頁 停止放映 第 82/89 頁 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) ? 數(shù)組元素是連續(xù)存放的，因此只能采用順序存儲(chǔ)結(jié)構(gòu)。 ? 無論幾維數(shù)組 ,在計(jì)算機(jī)中都是按一維數(shù)組來存放。數(shù)組存放通常采用兩種方式： –按行優(yōu)先順序 –按列優(yōu)先順序 下一頁 上一頁 停止放映 第 83/89 頁 按行優(yōu)先順序存儲(chǔ)結(jié)構(gòu) 按行優(yōu)先順序存放是將數(shù)組看作若干個(gè)行向量。例如， 二維數(shù)組 Am n，可以看作 m個(gè)行向量，每個(gè)行向量 n個(gè)元素。數(shù)組中的每個(gè)元素由元素的兩個(gè)下標(biāo)表達(dá)式唯一的確定。 地址計(jì)算公式： LOC（ aij） =LOC（ a11） +((i1)*n+(j1))*L 其中， L 是每個(gè)元素所占的存儲(chǔ)單元。 下一頁 上一頁 停止放映 第 84/89 頁 二維數(shù)組按行優(yōu)先存儲(chǔ)舉例 有二維數(shù)組如下： a11 a12 a13 a14 A3x4 = a21 a22 a23 a24 = a31 a32 a33 a34 1 2 3 4 5 6 7 8 9 10 11 12 (（ a11， a12， a13， a14），（ a21， a22， a23， a24），（ a31， a32， a33， a34）） LOC（ a23） = LOC（ a11） +（ 21） x4+（ 31） = 7 LOC（ a34） = 1 + （ 31） x 4 + （ 41） = 12 LOC（ a14） = 1 + （ 11） x 4 + （ 41） = 4 下一頁 上一頁 停止放映 第 85/89 頁 按列優(yōu)先順序存儲(chǔ)結(jié)構(gòu) 按列優(yōu)先順序存放是將數(shù)組看作若干個(gè)列向量。例如， 二維數(shù)組 Am n，可以看作 n個(gè)列向量，每個(gè)列向量 m個(gè)元素。數(shù)組中的每個(gè)元素由元素的兩個(gè)下標(biāo)表達(dá)式唯一的確定。 地址計(jì)算公式： LOC（ aij） =LOC（ a11） +((j1)*m+(i1)) * L 其中， L 是每個(gè)元素所占的存儲(chǔ)單元。 下一頁 上一頁 停止放映 第 86/89 頁 二維數(shù)組按列優(yōu)先存儲(chǔ)舉例 有二維數(shù)組如下： a11 a12 a13 a14 A3x4 = a21 a22 a23 a24 = a31 a32 a33 a34 1 2 3 4 5 6 7 8 9 10 11 12 （（ a11， a21， a31），（ a12， a22， a32），（ a13， a23， a33），（ a14， a24， a34）） LOC（ a23） = LOC（ a11） +（ 31） 3 +（ 21） = 8 LOC（ a34） = 1 + （ 41） 3 + （ 31） = 12 LOC（ a14） = 1 + （ 41） 3 + （ 11） = 10 下一頁 上一頁 停止放映 第 87/89 頁 數(shù)組的壓縮存儲(chǔ) 實(shí)際工程問題中推導(dǎo)出的數(shù)組常常是高階、含大量零元素的矩陣，或者是些有規(guī)律排列的元素。為了節(jié)省存儲(chǔ)空間，通常是對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。 壓縮的含義是： – 相同值的多個(gè)元素占用一個(gè)存儲(chǔ)單元； – 零元素不分配存儲(chǔ)單元。 下一頁 上一頁 停止放映 第 88/89 頁 能夠采用壓縮存儲(chǔ)的矩陣 對(duì)稱矩陣 存儲(chǔ)主對(duì)角線以上（下）的元素； 上（下）三角矩陣 只存儲(chǔ)三角陣元素； 帶狀矩陣 只存儲(chǔ)帶狀元素； 稀疏矩陣 只存儲(chǔ)非零元素； 大量相同元素矩陣 存儲(chǔ)某元素和重復(fù)個(gè)數(shù)。 下一頁 上一頁 停止放映 第 89/89 頁 對(duì)稱矩陣的壓縮存儲(chǔ) 對(duì)稱矩陣的元素滿足： aij = aji 1 ? i ， j ? n 因此將 n*n 個(gè)元素壓縮存放到 n（ n+1） /2 個(gè)單元的一維數(shù)組 S（（ n+1） *n/2）中。 aij的地址為： i（ i1） /2+j 當(dāng) i?j LOC（ aij） = j（ j1） /2+i 當(dāng) ij 下一頁 上一頁 停止放映 第 90/89 頁 對(duì)稱矩陣的壓縮存儲(chǔ)舉例 設(shè)有 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(22)/2+2= 3 LOC(a21)=2(21)/2+1= 2 下一頁 上一頁 停止放映 第 91/89 頁 作業(yè)、思考題 1. 思考題：第 2題； 1) 試寫出?在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中求表長的算法?。 2) 假設(shè)一單循環(huán)鏈表的長度大于 1，且表中即無頭結(jié)點(diǎn)也無頭指針。已知 S為指向鏈表中某結(jié)點(diǎn)的指針。試寫出刪除表中結(jié)點(diǎn) S 的算法。 3) 假設(shè)以數(shù)組 sequ[m1]存放循環(huán)隊(duì)列的元素，設(shè)變量 rear和 quelen分別為指示隊(duì)尾元素位置和隊(duì)中元素個(gè)數(shù)，試寫出入隊(duì)和出隊(duì)算法。 1章作業(yè)： 1 1 17 3. 作業(yè) (數(shù)字化 )要求： – 按要求提交到指定路徑下 : – /軟件基礎(chǔ) /劉志強(qiáng) /班級(jí)編號(hào) – 用 C（或其它語言）語言描述算法 – 作業(yè)命名方式為： 學(xué)號(hào) .章數(shù) _序號(hào) ( 例如 , ) 下一頁 上一頁 停止放映 第 92/89 頁 結(jié)束語 ? 計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心網(wǎng)址： ： \\ctec . ? 作業(yè)提交路徑 : ： \\202 . \moodle ? 數(shù)字化作業(yè)的路徑 : :\\\軟件基礎(chǔ) ? 答疑安排： 每星期四下午： 4： 00～ 6： 00 地點(diǎn)： 計(jì)教中心 102房間（ 1300大教室對(duì)面） 謝謝，再見！