數(shù)據(jù)結(jié)構(gòu)第五章 數(shù)組和廣義表

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組和廣義表一、課程內(nèi)容

5.1多維數(shù)組（1課時）數(shù)組的定義

數(shù)組（Arrays）是由一組類型一致的數(shù)據(jù)元素構(gòu)造而成的。它的每個元素由一個值和一組下標確定。

二維數(shù)組An1n2?nm的每個元素ai1i2?im都屬于m個向量，最多可以有m個直接前趨和m個直接后繼。數(shù)組的順序存儲結(jié)構(gòu)

數(shù)組的順序存儲結(jié)構(gòu)指的是用一組連續(xù)的存儲單元依次存放數(shù)組元素。行優(yōu)先順序

行優(yōu)先順序：將數(shù)組元素按行向量排列，第i+1個行向量緊接在第i個行向量后面。

行優(yōu)先順序規(guī)定為先排最右的下標，從右向左，最終排最左下標。列優(yōu)先順序

列優(yōu)先順序：將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后。

列優(yōu)先順序規(guī)定為先排最左下標，從左向右，最終排最右下標。

二維數(shù)組Amn按“行優(yōu)先順序〞存儲在內(nèi)存中，假設(shè)每個元素占d個存儲單元，則aij的地址計算函數(shù)為：LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d對應(yīng)C語言的二維數(shù)組：DataTypeA[m][n];

數(shù)組A[m][n]的兩個下標的下界均為0，上界分別為m-1、n-1，每個數(shù)據(jù)元素占k個存儲單元，二維數(shù)組中任一元素a[i,j]的存儲位置可由以下公式確定。loc[i,j]=loc[0,0]+(n*i+j)*k

其中，loc[0,0]是A[0][0]的存儲位置，它是該二維數(shù)組的起始地址。loc[i,j]是A[i][j]的存儲位置。這個式子確定了C語言的二維數(shù)組元素的位置和下標的關(guān)系。

5.2矩陣的壓縮存儲（1課時）

壓縮存儲：即為多個一致的非零元素只分派一個存儲空間，對零元素不分派空間。所謂特別矩陣（SpecialMatrices）是指非零元素或零元素的分布有一定規(guī)律的矩陣。

幾種特別矩陣的壓縮存儲：對稱矩陣

在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≤i，j≤n-1則稱A為對稱矩陣。如下圖：

存儲元素為：{1,5,0,1,8,9,3,0,2,5,7,0,6,1,3}，共15個。令I(lǐng)=max(i,j)，J=min(i,j)，則k和i，j的對應(yīng)關(guān)系為：k=I×(I+1)/2+J0≤k＜n(n+1)/2aij的地址計算公式：

LOC(aij)=LOC(sa[0])+[I×(I+1)/2+J]×d三角矩陣

以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣的下三角（不

包括主角線）中的元素均為常數(shù)c。下三角矩陣正好相反，它的主對角線上方均為常數(shù)c。在多數(shù)狀況下，三角矩陣的常數(shù)c為零。上三角矩陣中，sa[k]和aij的對應(yīng)關(guān)系是：

下三角矩陣中，sa[k]和aij的對應(yīng)關(guān)系是：

對角矩陣

對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。如下圖：

對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應(yīng)關(guān)系。5.3廣義表的概念（1課時）

廣義表的定義

廣義表（Lists）又稱列表，是線性表的推廣。廣義表是n(n≥0)個元素的有限序列，尋常記作LS=（a1,a2,?an）。其中LS是廣義表的名字，n為它的長度，ai或者是一個廣義表。若ai是廣義表，則稱它為LS的子表。為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。

若廣義表LS非空（n≥1），則a1是LS的表頭，其余元素組成的表（a2,a3,?an）稱為LS的表尾。

廣義表是遞歸定義的，廣義表中可以包含廣義表。一個表的“深度（Depth）〞是指表展開后所含括號的層數(shù)。

尋常把與樹對應(yīng)的廣義表稱為純表，它限制了表中成分的共享和遞歸；把允許結(jié)點共享的表稱為再入表；而把允許遞歸的表稱為遞歸表。它們之間的關(guān)系滿足：遞歸表再入表純表線性表。

廣義表三個特別的基本運算：取表頭GetHead(LS)、取表尾GetTail(LS)和表長Length(LS)。根據(jù)表頭、表尾的定義可知：任何一個非空廣義表的表頭是表中第一個元素，它可以是原子，也可以是子表，而其表尾必定是子表。廣義表的舉例E=()

GetHead(E)=空GetTail(E)=()Length(E)=0L=(a,b)

GetHead(L)=aGetTail(L)=(b)Length(L)=2

A=(x,L)=(x,(a,b))

GetHead(A)=xGetTail(A)=(L)=((a,b))Length(A)=2

B=(A,y)=((x,(a,b)),y)

GetHead(B)=A=(x,(a,b))GetTail(B)=(y)Length(B)=2

C=(A,B)=((x,(a,b)),((x,(a,b)),y))

GetHead(C)=A=(x,(a,b))GetTail(C)=(B)=(((x,(a,b)),y))Length(C)=2

D=(a,D)=(a,(a,(a,(…))))

GetHead(D)=aGetTail(D)=(D)Length(D)=2

二、學(xué)習(xí)目的與要求

本章的目的是介紹多維數(shù)組的規(guī)律結(jié)構(gòu)特征及

其存儲方式，特別矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，要求考生熟悉這些內(nèi)容。本章重點是熟悉多維數(shù)組的存儲方式、矩陣的壓縮存儲方式、廣義表的定義及其求表頭和表尾的運算，難點是稀疏矩陣的壓縮存儲表示下實現(xiàn)的算法。

三、考核知識點與考核要求

1.多維數(shù)組，要求達到“領(lǐng)會〞層次1.1多維數(shù)組的規(guī)律結(jié)構(gòu)特征

1.2多維數(shù)組的順序存儲結(jié)構(gòu)及地址計算方式1.3數(shù)組是一種隨機存取結(jié)構(gòu)的原因2.矩陣的壓縮存儲，要求達到“領(lǐng)會〞層次2.1特別矩陣和稀疏矩陣的概念

2.2特別矩陣和壓縮存儲時的下標變換方法2.3稀疏矩陣的三元組表表示方法及有關(guān)算法2.4稀疏矩陣的十字鏈表表示方法3.廣義表的概念，要求達到“領(lǐng)會〞層次

3.1廣義表的有關(guān)概念及其與線性表的關(guān)系3.2廣義表的括號表示和圖形表示之間的轉(zhuǎn)換3.3求給定的廣義表的表頭、表尾和長度運算5.1多維數(shù)組

數(shù)組的定義

數(shù)組（Arrays）是由一組類型一致的數(shù)據(jù)元素構(gòu)造而成的。它的每個元素由一個值和一組下標確定。

二維數(shù)組An1n2?nm的每個元素ai1i2?im都屬于m個向量，最多可以有m個直接前趨和m個直接后繼。數(shù)組的順序存儲結(jié)構(gòu)

數(shù)組的順序存儲結(jié)構(gòu)指的是用一組連續(xù)的存儲單元依次存放數(shù)組元素。行優(yōu)先順序

行優(yōu)先順序：將數(shù)組元素按行向量排列，第i+1個行向量緊接在第i個行向量后面。行優(yōu)先順序規(guī)定為先排最右的下標，從右向左，最終排最左下標。列優(yōu)先順序

列優(yōu)先順序：將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后。列優(yōu)先順序規(guī)定為先排最左下標，從左向右，最終排最右下標。

二維數(shù)組Amn按“行優(yōu)先順序〞存儲在內(nèi)存中，假設(shè)每個元素占d個存儲單元，則aij的地址計算函數(shù)為：LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d對應(yīng)C語言的二維數(shù)組：DataTypeA[m][n];

數(shù)組A[m][n]的兩個下標的下界均為0，上界分別為m-1、n-1，每個數(shù)據(jù)元素占k個存儲單元，二維數(shù)組中任一元素a[i,j]的存儲位置可由以下公式確定。loc[i,j]=loc[0,0]+(n*i+j)*k

其中，loc[0,0]是A[0][0]的存儲位置，它是該二維數(shù)組的起始地址。loc[i,j]是A[i][j]的存儲位置。這個式子確定了C語言的二維數(shù)組元素的位置和下標的關(guān)系。5.2矩陣的壓縮存儲

壓縮存儲：即為多個一致的非零元素只分派一個存儲空間，對零元素不分派空間。所謂特別矩陣（SpecialMatrices）是指非零元素或零元素的分布有一定規(guī)律的矩陣。幾種特別矩陣的壓縮存儲：對稱矩陣

在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≤i，j≤n-1則稱A為對稱矩陣。如下圖：

存儲元素為：{1,5,0,1,8,9,3,0,2,5,7,0,6,1,3}，共15個。令I(lǐng)=max(i,j)，J=min(i,j)，則k和i，j的對應(yīng)關(guān)系為：k=I×(I+1)/2+J0≤k＜n(n+1)/2aij的地址計算公式：

LOC(aij)=LOC(sa[0])+[I×(I+1)/2+J]×d三角矩陣

以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣的下三角（不包括主角線）中的元素均為常數(shù)c。下三角矩陣正好相反，它的主對角線上方均為常數(shù)c。在多數(shù)狀況下，三角矩陣的常數(shù)c為零。

上三角矩陣中，sa[k]和aij的對應(yīng)關(guān)系是：

下三角矩陣中，sa[k]和aij的對應(yīng)關(guān)系是：

對角矩陣

對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。如下圖：對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應(yīng)關(guān)系。5.2.1特別矩陣

壓縮存儲：即為多個一致的非零元素只分派一個存儲空間，對零元素不分派空間。所謂特別矩陣（SpecialMatrices）是指非零元素或零元素的分布有一定規(guī)律的矩陣。幾種特別矩陣的壓縮存儲：對稱矩陣

在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≤i，j≤n-1則稱A為對稱矩陣。如下圖：

存儲元素為：{1,5,0,1,8,9,3,0,2,5,7,0,6,1,3}，共15個。令I(lǐng)=max(i,j)，J=min(i,j)，則k和i，j的對應(yīng)關(guān)系為：k=I×(I+1)/2+J0≤k＜n(n+1)/2aij的地址計算公式：

LOC(aij)=LOC(sa[0])+[I×(I+1)/2+J]×d

三角矩陣

以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣的下三角（不包括主角線）中的元素均為常數(shù)c。下三角矩陣正好相反，它的主對角線上方均為常數(shù)c。在多數(shù)狀況下，三角矩陣的常數(shù)c為零。

上三角矩陣中，sa[k]和aij的對應(yīng)關(guān)系是：

下三角矩陣中，sa[k]和aij的對應(yīng)關(guān)系是：

對角矩陣

對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。如下圖：對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應(yīng)關(guān)系。

5.2.2稀疏矩陣

設(shè)矩陣Amn中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s＜＜m×n），則稱A為稀疏矩陣（SparseMatrix）。當用三元組來表示非零元時，對稀疏矩陣進行壓縮存儲尋常有兩類方法：順序存儲和鏈式存儲。

三元組表

若

將表示稀疏矩陣的非零元素的三元組按行優(yōu)先（或列優(yōu)先）的順序排列（跳過零元素），則得到一個其結(jié)點均是三元組的線性表，我們將該線性表的順序存儲結(jié)構(gòu)稱為三元組表（Listof3-tuples）。三元組表類型描述：

矩陣轉(zhuǎn)置運算的算法：

這個算法的時間繁雜度為O(n×t)，即與矩陣A的列數(shù)和非零元素的乘積成正比。而尋常用二維數(shù)組表示矩陣時，其轉(zhuǎn)置算法的執(zhí)行時間是O(m×n)，它正比于行數(shù)和列數(shù)的乘積。由于非零元素個數(shù)一般遠遠大于行數(shù)，因此上述稀疏矩陣轉(zhuǎn)置算法的時間大于尋常的轉(zhuǎn)置算法的時間。

帶行表的三元組表

當將行表作為三元組表的一個新增屬性加以描

述時，就得到了稀疏矩陣的另一種順序存儲結(jié)構(gòu)：帶行表的三元組表。其類型描述為：

十字鏈表

稀疏矩陣的鏈接存儲是一種既帶行指針又帶列指針的

5.3廣義表的概念

廣義表的定義廣義表（Lists）又稱列表，是線性表的推廣。廣義表是n(n≥0)個元素的有限序列，尋常記作LS=（a1,a2,…an）。其中LS是廣義表的名字，n為它的長度，ai或者是一個廣義表。若ai是廣義表，則稱它為LS的子表。為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS非空（n≥1），則a1是LS的表頭，其余元素組成的表（a2,a3,…an）稱為LS的表尾。廣義表是遞歸定義的，廣義表中可以包含廣義表。一個表的“深度（Depth）〞是指表展開后所含括號的層數(shù)。尋常把與樹對應(yīng)的廣義表稱為純表，它限制了表中成分的共享和遞歸；把允許結(jié)點共享的表稱為再入表；而把允許遞歸的表稱為遞歸表。它們之間的關(guān)系滿足