數(shù)據(jù)結(jié)構(gòu)實例教程（C語言版）：第5章 二維數(shù)組及廣義表的結(jié)構(gòu)分析

1、第5章二維數(shù)組及廣義表的結(jié)構(gòu)分析 學(xué)習(xí)目標(biāo) 掌握二維數(shù)組的行優(yōu)先和列優(yōu)先兩種存儲結(jié)構(gòu)及 求址方法。 了解特殊矩陣的特點，并掌握特殊矩陣存儲形式 及基本運算。 了解廣義表的概念及相關(guān)術(shù)語。 掌握廣義表的取表頭和取表尾的基本運算。5.1二維數(shù)組的存儲結(jié)構(gòu)及求址方法 一、二維數(shù)組的存儲結(jié)構(gòu) 二維數(shù)組Amn可視為由m個行向量組成的向量，或由n個列向量組成的向量。 行優(yōu)先存儲：二維數(shù)組Amn的按行優(yōu)先存儲的線性序列為：a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn 列優(yōu)先存儲：二維數(shù)組Amn的按列優(yōu)先存儲的線性序列為：a11,a21,am1,a12,a22,am2,，a1n,

2、a2n,，amn5.1二維數(shù)組的存儲結(jié)構(gòu)及求址方法 二、二維數(shù)組的求址方法 1、按照行優(yōu)先求址公式 LOC(aij)=LOC(a11)+(i-1)n+j-1d LOC(a11)是開始結(jié)點的存放地址 d為每個元素所占的存儲單元數(shù) 2、按照列優(yōu)先求址公式 LOC(aij)=LOC(a11)+(j-1)m+i-1d5.2矩陣的壓縮存儲 一、特殊矩陣 1、對稱矩陣 對稱矩陣滿足下述性質(zhì)：aij=aji 按照行優(yōu)先存儲aij和sak之間的對應(yīng)關(guān)系： k=i(i+1)/2+j4階對稱矩陣 行優(yōu)先存放示意圖 5.2矩陣的壓縮存儲 一、特殊矩陣 2、三角矩陣 aij和sak之間的對應(yīng)關(guān)系：上三角矩陣 下三角矩

3、陣 aij和sak之間的對應(yīng)關(guān)系：5.2矩陣的壓縮存儲 二、稀疏矩陣 1、稀疏矩陣定義：設(shè)矩陣Amn中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)(即smn)。2、三元組表只存儲非零元素及非零元素所在的行號、列號，并由此三元組唯一確定 。 5.3廣義表的概念 一、廣義表定義 1、廣義表定義：n(n0)個元素a1，a2，ai，an的有限序列。ai或者是原子或者是一個廣義表。廣義表通常記作：Ls=(a1，a2，ai，an)。Ls是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為Ls的子表。5.3廣義表的概念 二、廣義表表示 1、廣義表常用表示 E=() /E是一個空表，其長度為0。 L=(a，b

4、) /L是長度為2的廣義表 A=(x，L)=(x，(a，b) /A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。 B=(A，y)=(x，(a，b)，y) /B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。 C=(A，B)=(x，(a，b)，(x，(a，b)，y) /C的長度為2，兩個元素都是子表。 D=(a，D)=(a，(a，(a，() /D的長度為2，第一個元素是原子，第二個元素是D自身。5.3廣義表的概念 二、廣義表表示 2、廣義表的深度 廣義表的深度定義：是指表展開后所含括號的層數(shù)。 例如：表L、A、B、C的深度為分別為1、2、3、4，表D的深度為。 3、廣義表的圖形表示5.3廣義表的概念 三、廣義表運算 1、取表頭head(Ls) 表頭的定義：是表中第一個元素，它可以是原子，也可以是子表。 2、取表尾tail(Ls) 表尾的定義：是表中除了第一個元素外其他元素的集合， 而其表尾必定是子表。 3、舉例 head(L