數(shù)據(jù)結(jié)構(gòu)第五章串講復(fù)習(xí)要點

1、數(shù)據(jù)結(jié)構(gòu)第五章多維數(shù)組和 xx 表第五章多維數(shù)組和 xx 表51 多維數(shù)組一般用順序存儲的方式表示數(shù)組。常用方式有：1)行優(yōu)先順序，將數(shù)組元素按行向量排列； 2)列優(yōu)先順序，將數(shù)組元素按列向量排列。計算地址的函數(shù)：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d52 矩陣的壓縮存儲為多個非零元素分配一個存儲空間；對零元素不分配存儲空間。1對稱矩陣在一個n階的方陣A中，元素滿足Aij=Aji 0<=i,j<=n-1稱為對稱矩陣。元素的總數(shù)為：n(n+1)/2;設(shè)：I=i或j中大的一個數(shù)；J=i或j中小的一個數(shù)；則：k=I*(I+1)/2+J;地

2、址計算：LOC(Aij)=LOC(sak)=LOC(sa0)+k*d= LOC(sa0)+ (I*(I+1)/2+J )*d2三角矩陣以主對角線劃分，三角矩陣有上三角和下三角；上三角的主對角線下元素 均為常數(shù)C；下三角的主對角線上元素均為常數(shù)C。元素總數(shù)為：(n(n+1)/2)+1;以行優(yōu)先順序存放的Aij與SAk的關(guān)系：上三角陣：k=i*(2n-i+1)/2+j-i;下三角陣：k=i*(i+1)/2+j;3.對角矩陣所有的非零元素集中在以主對角線為中心的帶狀區(qū)域，相鄰兩側(cè)元素均為J | A零。|i-j|>(k-1)/2以行優(yōu)先順序存放的Aij與SAk的關(guān)系：k=2i+j522 稀疏矩陣

3、當(dāng)矩陣A中有非零元素S個，且S遠(yuǎn)小于元素總數(shù)時，稱為稀疏矩陣。對 其壓縮的方法有順序存儲和鏈?zhǔn)酱鎯Α?三元組表將表示稀疏矩陣的非零元素的三元組(行號、列號、值)按行或列優(yōu)先的 順序排列得到的一個結(jié)點均是三元組的線性表，將該表的線性存儲結(jié)構(gòu)稱為三 元組表。其類型定義：#define maxsize 100 typedef int datype;typedef structint i,j;datype v; trituplenode;typedef struct trituplenode datamaxsize;int m,n,t;tritupletable;2.帶行表的三元組表 在按行優(yōu)先存儲的

4、三元組表中加入一個行表記錄每行的非零元素在三元組 表中的起始位置。類型定義：#define maxrow 100 typedef struct tritulpenode datamaxsize;int rowtabmaxrow;int m, n, t; rtritulpetable;5.3xx 表的概念 廣義表是線性表的推廣。廣義表是 n 個元素的有限序列，元素可以是原子 或一個廣義表，記為 LS。若元素是廣義表稱它為LS的子表。若廣義表非空，則第一個元素稱表頭, 其余元素稱表尾。表的xx是指表展開后所含括號的層數(shù)。把與樹對應(yīng)的廣義表稱為純表，它限制了表中成分的共享和遞歸； 允許結(jié)點共享的表稱

5、為再入表；允許遞歸的表稱為遞歸表；相互關(guān)系：線性表純表再入表遞歸表；廣義表的特殊運(yùn)算： 1)取表頭 head(LS；) 2)取表尾 tail(LS); 附二:第五章多維數(shù)組和xx表*數(shù)組一般用順序存儲的方式表示。存儲的方式有：行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL C列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN*地址的計算方法：按行優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+(i-1)*n+(j-1)*d 。按列優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+(j-1)*n+(i-1)*d 。*矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間；對零元素

6、不分配空間。 特殊矩陣的概念： 所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。 稀疏矩陣的概念： 一個矩陣中若其非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個數(shù)，則該矩陣稱為稀 疏矩陣。*特殊矩陣的類型：對稱矩陣：滿足 a(ij)二a(ji)。元素總數(shù) n(n+1)/2。匸max(i,j), J=min(i,j),LOCa(ij)二LOC(sa0)+(l*(l+1)/2+J)*。三角矩陣：上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)二LOC(sa0)+k*d下三角陣：k二i*(i+1)/2+j, LOCa(ij)二LOC(sa0)+k*。對角矩陣：k=2i+j, LOCa(ij)

7、二LOC(sa0)+k*d*稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號 做為一個結(jié)點存放在一起，用這些結(jié)點組成的一個線性表來表示。但這種壓縮 存儲方式將失去隨機(jī)存儲功能。加入行表記錄每行的非零元素在三元組表中的 起始位置，即帶行表的三元組表。*廣義表是n(n >(個元素的有限序列，其中的元素是原子或者是一個廣義 表。xx 表表頭和表尾的概念：若廣義表LS非空(n > 1則這個廣義表的第一個元素就是表頭。其余的元素組成的表稱為LS的表尾，所以表尾必是一個子表。 廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。 廣義表與樹 (形結(jié)構(gòu) )相對應(yīng)，這個廣義表就

8、是純表。 如果一個廣義表的結(jié)點又可以被其他結(jié)點所共享，則這個表稱為再入表。 允許遞歸的表稱為遞歸表。線性表純表(樹)再入表遞歸表。可見，廣義表是對線性表和樹的推 廣。xx 表有兩個特殊的基本運(yùn)算：取表頭head(LS)取表中的第一個數(shù)據(jù)元素，不能對空表操作。取表尾tail(LS);取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對空表操作。前面我們學(xué)習(xí)的線性表、棧、隊列和串都是線性結(jié)構(gòu)，本章起學(xué)習(xí)的是非 線性結(jié)構(gòu)。它們的邏輯特征是：一個數(shù)據(jù)元素可能有多個直接前趨和多個直接后繼。本章重點是熟悉多維數(shù)組的存儲方式、矩陣的壓縮存儲方式、廣義表的定 義及其求表頭和表尾的運(yùn)算，難點是稀疏矩陣的壓縮存儲表示下實現(xiàn)

9、的算法。多維數(shù)組：(領(lǐng)會)多維數(shù)組的邏輯結(jié)構(gòu)特征：一個m維數(shù)組An 1 n 2 . n m的每個元素都屬于 m個向量，最多可以有 m個直接前趨和 m 個直接后繼。多維數(shù)組的順序存儲結(jié)構(gòu)及其地址計算方式 :計算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此將數(shù)組元素排成線性序列，然后將這個 線性序列存放在存儲器中。排列的方式有兩種，一是行優(yōu)先順序，也就是把數(shù) 組按一行的順序依次排列。二是列優(yōu)先順序，就是把數(shù)組按一列列的順序依次 排列。地址的計算方法：我們按行優(yōu)先順序排列的數(shù)組，是這樣計算的，假設(shè)每個元素占用 d 個存 儲單元，某個元素的地址就是它前面所有行所占的單元加上它所在行前面所有 列元素所占的單元數(shù)之和。不必

10、去死記公式。數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)的原因：因為在順序存儲的情況下，每一個元素都有與其下標(biāo)相對應(yīng)的地址，因此 可以對數(shù)組中的元素進(jìn)行隨機(jī)存儲。矩陣的壓縮存儲：（領(lǐng)會）特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。稀疏矩陣的概念：一個矩陣中若其非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個數(shù)，則該矩陣稱為稀 疏矩陣。我們在本章學(xué)習(xí)了對稱矩陣、三角矩陣、對角矩陣這三種特殊矩陣。這三 種特殊矩陣可以進(jìn)行壓縮存儲。主要要理解的是其下標(biāo)變換方法。稀疏矩陣的壓縮存儲方式三元組表就是把非零元素的值和它所在的行號列 號做為一個結(jié)點存放在一起，用這些結(jié)點組成的一個線性表（三元組表 ）來表示這個稀疏矩陣。

11、但是這種壓縮存儲方式將失去隨機(jī)存儲功能。相關(guān)算法的理解要建立在對三元組表的結(jié)構(gòu)的全面掌握的基礎(chǔ)上。但是本 章的算法考試應(yīng)不作要求。xx 表的概念 （領(lǐng)會 ）：廣義表又稱列表（Lists）是線性表的推廣。就是說，廣義表中的元素不僅可以 是數(shù)或一個結(jié)構(gòu)，而且推廣到可以是一個表（這個表又可以是廣義表 ）。所以，廣義表是n（n >0個元素a1,a2,a3.an的有限序列，其中的ai或者是原子或者是一 個廣義表。（為什么叫原子？因為原子是作為結(jié)構(gòu)上不可分割的成分。）xx 表表頭和表尾的概念：若廣義表LS非空（n > 1則這個廣義表的第一個元素就是表頭。（這個表頭可 以是原子，也可以是該廣義表

12、的子表。）而其余的元素組成的表稱為LS的表尾（要注意，不是最后一個元素，這和隊列的隊尾是不同的 ），所以表尾必是一個子 表。廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。括號表示 時，一般以大寫字母表示廣義表，以小寫字母表示原子。如：A（x,L（a,b）。用圖形表示時，圖形中的分支結(jié)點對應(yīng)廣義表，非分支結(jié)點一 般表示原子，如果一個廣義表與樹 （形結(jié)構(gòu) ）相對應(yīng)，這個廣義表就是純表。如果 一個廣義表的結(jié)點又可以被其他結(jié)點所共享，則這個表稱為再入表。允許遞歸 的表稱為遞歸表。有一個關(guān)系式：遞歸表 （包含）再入表（包含）純表（樹）（包含）線性表?？梢?，廣義表是對線性表 和樹的推廣。廣義表有兩個特殊的基本運(yùn)算，取表頭 head（LS和取表尾 tail（LS） .（我們看到 tail 這個詞就是尾巴，是一條尾巴，而不是末尾，它可能是一 個原子，但這個原子是作為子表來看待的 ）取表頭和表尾的運(yùn)算要在廣義表非空的情況下進(jìn)行。注意廣義表（）表示是空表， （）則表示有一個元素的廣義表，這個元素是一個空表。這兩個運(yùn)算很容易理解也應(yīng)該掌握。第五章多維數(shù)組和xx表復(fù)習(xí)要點本章復(fù)習(xí)要點是：多維數(shù)組和xx表的邏輯結(jié)構(gòu)特征：它們是復(fù)雜的非線性結(jié)構(gòu)。一個數(shù)據(jù)元素