數(shù)據(jù)結構 第4章 廣義線性表(g)

1、數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義第四章第四章 廣義線性表廣義線性表本章的基本內(nèi)容是：本章的基本內(nèi)容是：數(shù)組的邏輯結構特征數(shù)組的邏輯結構特征數(shù)組的存儲方式及尋址方法數(shù)組的存儲方式及尋址方法特殊矩陣和稀疏矩陣的壓縮存儲方法特殊矩陣和稀疏矩陣的壓縮存儲方法廣義表的基本概念和存儲結構廣義表的基本概念和存儲結構數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義第四章第四章 廣義線性表廣義線性表線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。限制插入、刪除位置限制插入、刪除位置線性表線性表具有相同類型的數(shù)據(jù)元素的有限

2、序列。具有相同類型的數(shù)據(jù)元素的有限序列。限制元素類型為字符限制元素類型為字符棧棧僅在表尾進行插入和刪除操作的線性表。僅在表尾進行插入和刪除操作的線性表。隊列隊列在一端進行插入操作，而另一端進行在一端進行插入操作，而另一端進行刪除操作的線性表。刪除操作的線性表。串串零個或多個字符組成的有限序列零個或多個字符組成的有限序列 。特殊線性表特殊線性表數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義第四章第四章 廣義線性表廣義線性表線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。將元素的類型進行擴充將元素的類型進行擴充廣義線性表廣義線性表（多維）數(shù)組

3、（多維）數(shù)組線性表中的數(shù)據(jù)元素可以是線性表中的數(shù)據(jù)元素可以是線性表，但所有線性表，但所有元素的類型相同元素的類型相同。廣義表廣義表線性表中的數(shù)據(jù)元素可以是線性表，線性表中的數(shù)據(jù)元素可以是線性表，且且元素的類型可以不相同元素的類型可以不相同。數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義數(shù)組的定義數(shù)組的定義數(shù)組是由一組數(shù)組是由一組類型相同類型相同的數(shù)據(jù)元素構成的的數(shù)據(jù)元素構成的有序有序集集合合，每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元素），每個元素受素），每個元素受n(n1)個個線性關系線性關系的約束，的約束，每每個元素在個元素在n個線

4、性關系中的序號個線性關系中的序號i1、i2、in稱為稱為該元素的下標，并稱該數(shù)組為該元素的下標，并稱該數(shù)組為 n 維數(shù)組。維數(shù)組。 數(shù)組的特點數(shù)組的特點元素本身可以具有某種結構，屬于同一數(shù)據(jù)類型；元素本身可以具有某種結構，屬于同一數(shù)據(jù)類型；數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合。廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義廣義線性表廣義線性表多維數(shù)組多維數(shù)組 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a22受兩個線性關系的約束，在行上有受兩個線

5、性關系的約束，在行上有一個行前驅一個行前驅a21和一個行后繼和一個行后繼a23，在列上有一個列，在列上有一個列前驅前驅a12和和一個列后繼和和一個列后繼a32。數(shù)組示例數(shù)組示例數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)數(shù)組數(shù)組線性表的推廣線性表的推廣二維數(shù)組是二維數(shù)組是數(shù)據(jù)元素為線性表數(shù)據(jù)元素為線性表的的線性表線性表。廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大

6、學 謝仕義謝仕義數(shù)組的基本操作數(shù)組的基本操作廣義線性表廣義線性表多維數(shù)組多維數(shù)組在數(shù)組中插入（或刪除）一個元素有意義嗎？在數(shù)組中插入（或刪除）一個元素有意義嗎？ a11 a12 a1n a21 a22 a2n am1 am2 amnA=將元素將元素 x 插入插入到數(shù)組中第到數(shù)組中第1行第行第2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=刪除數(shù)組中刪除數(shù)組中第第1行第行第2列元素。列元素。數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義數(shù)組的基本操作數(shù)組的基本操作 存取存?。航o定一組下標，讀出對應的數(shù)組元素；：給定一組下標，讀出對應

7、的數(shù)組元素； 修改修改：給定一組下標，存儲或修改與其相對應的：給定一組下標，存儲或修改與其相對應的數(shù)組元素。數(shù)組元素。存取和修改操作本質上只對應一種操作存取和修改操作本質上只對應一種操作尋址尋址數(shù)組應該采用何種方式存儲？數(shù)組應該采用何種方式存儲？數(shù)組沒有插入和刪除操作，所以，不用預留空間，數(shù)組沒有插入和刪除操作，所以，不用預留空間，適合采用順序存儲。適合采用順序存儲。廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義數(shù)組的存儲結構與尋址數(shù)組的存儲結構與尋址一維數(shù)組一維數(shù)組設一維數(shù)組的下標的范圍為閉區(qū)間設一維數(shù)組的下標的范圍為閉區(qū)間l，h，

8、每個每個數(shù)組元素占用數(shù)組元素占用 c 個存儲單元，則個存儲單元，則其其任一元任一元素素 ai 的的存儲地址可由下式確定：存儲地址可由下式確定： Loc(ai)Loc(al)(il)c 廣義線性表廣義線性表多維數(shù)組多維數(shù)組c al ai-1 ai ah al+1 Loc(al)Loc(ai)數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義常用的映射方法有兩種：常用的映射方法有兩種：按按行行優(yōu)先：優(yōu)先：先行后列先行后列，先存儲行號較小的元素，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。行號相同者先存儲列號較小的元素。 按按列列優(yōu)先：優(yōu)先：先列后行先列后行，先存儲列號

9、較小的元素，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。列號相同者先存儲行號較小的元素。 廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)組的存儲結構與尋址數(shù)組的存儲結構與尋址二維數(shù)組二維數(shù)組二維數(shù)組二維數(shù)組內(nèi)內(nèi) 存存二維結構二維結構一維結構一維結構數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義廣義線性表廣義線性表多維數(shù)組多維數(shù)組l2h2 l1h1(a) 二維數(shù)組二維數(shù)組aij前面的元素個數(shù)前面的元素個數(shù)=陰影部分的面積陰影部分的面積=整行數(shù)每行元素個數(shù)整行數(shù)每行元素個數(shù)+本行中本行中aij前面的元素個數(shù)前面的元素個數(shù)=( (i - -l1) )( (h2 - -l21

10、) )( (j - -l2) )本行中本行中aij前面的元素個數(shù)前面的元素個數(shù)每行元素個數(shù)每行元素個數(shù)整整行行數(shù)數(shù)aij按行優(yōu)先存儲的尋址按行優(yōu)先存儲的尋址數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義廣義線性表廣義線性表多維數(shù)組多維數(shù)組第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc( (aij) )Loc( (al1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )個元素個元素Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按行優(yōu)先存

11、儲的尋址按行優(yōu)先存儲的尋址按列優(yōu)先存儲的尋址方法與此類似。按列優(yōu)先存儲的尋址方法與此類似。數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c 廣義線性表廣義線性表多維數(shù)組多維數(shù)組 n（n2）維維數(shù)組一般也采用數(shù)組一般也采用按行優(yōu)先和按列按行優(yōu)先和按列優(yōu)先兩種存儲方優(yōu)先兩種存儲方法。法。請自行推導請自行推導任一元素存儲地任一元素存儲地址的計算方法。址的計算方法。數(shù)組的存儲結構與尋址數(shù)組的存儲結構與尋址多維數(shù)組多維數(shù)組數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣

12、的壓縮存儲矩陣的壓縮存儲特殊矩陣：特殊矩陣：矩陣中很多值相同的元素并且它們的分布矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律。有一定的規(guī)律。稀疏矩陣：稀疏矩陣：矩陣中有很多零元素。矩陣中有很多零元素。壓縮存儲的基本思想是：壓縮存儲的基本思想是： 為多個值為多個值相同相同的元素只分配的元素只分配一個一個存儲空間；存儲空間； 對對零零元素元素不分配不分配存儲空間。存儲空間。 特殊矩陣和稀疏矩陣特殊矩陣和稀疏矩陣數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣對稱矩陣 3647862842481697460582957A對稱矩陣特

13、點：對稱矩陣特點：aij=aji如何壓縮存儲？如何壓縮存儲？只存儲下三角部分的元素。只存儲下三角部分的元素。矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義(a) 下三角矩陣下三角矩陣 (b) 存儲說明存儲說明 (c) 計算方法計算方法aij在一維數(shù)組中的序號在一維數(shù)組中的序號=陰影部分的面積陰影部分的面積= i( (i+1) )/2+ j+1一維數(shù)組下標從一維數(shù)組下標從0開始開始aij在一維數(shù)組中的下標在一維數(shù)組中的下標k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素個數(shù)每行元素個數(shù)12iaij在本行中

14、的序號在本行中的序號aij第第0行行第第1行行第第i-1行行對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義對于下三角中的元素對于下三角中的元素aij（ij），在數(shù)組，在數(shù)組SA中的下標中的下標k與與i、j的關系為：的關系為：ki(i1)/2j 。上三角中的元素上三角中的元素aij（ij），），因為因為aijaji，則訪問和則訪問和它對應的元素它對應的元素aji即可，即：即可，即：kj(j1)/2i 。對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 第第1行行第第n-1行行第第0行行 a00 a10 a11 a20

15、a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 k n(n+1)/2-1矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲三角矩陣三角矩陣 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩陣下三角矩陣3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩陣上三角矩陣如何壓縮存儲？如何壓縮存儲？只存儲上三角（或下三角）部分的元素。只存儲上三角（或下三角）部分的元素。矩陣的壓縮存儲

16、矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標中的下標k與與i、j的對應關系：的對應關系：i( (i1) )/2j 當當ijn( (n1) )/2 當當ijk=下三角矩陣的壓縮存儲下三角矩陣的壓縮存儲0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22矩陣的壓縮存儲矩陣的壓縮存儲存儲存儲下三角下三角元素元素對角線上方的常數(shù)對角線上方的常數(shù)只存一個只存一個數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋

17、大學 謝仕義謝仕義矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標中的下標k與與i、j的對應關系：的對應關系： i( (2ni1) )/2ji 當當ijn( (n1) ) /2 當當ijk=上三角矩陣的壓縮存儲上三角矩陣的壓縮存儲矩陣的壓縮存儲矩陣的壓縮存儲存儲存儲上三角上三角元素元素對角線上方的常數(shù)對角線上方的常數(shù)只存一個只存一個數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對角矩陣對角矩陣 對角矩陣：對角矩陣：所有非零元素都集中在以主對角線為中心所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，除了主的帶狀區(qū)域中，除了主對角

18、線和它的上下方若干條對對角線和它的上下方若干條對角線的元素外，所有其他元素都為零。角線的元素外，所有其他元素都為零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=將帶狀區(qū)將帶狀區(qū)域立起來域立起來0 a00a01a10 a11 a12a21 a22 a23a32

19、a33 a34a43 a44 0B=sj- -i+1t=i映射到二維數(shù)組映射到二維數(shù)組B中中(Aij=Bts)， 映射關系為映射關系為對角矩陣的壓縮存儲（方式一）對角矩陣的壓縮存儲（方式一）矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義按行按行存儲存儲 元素元素aij在一維數(shù)組中的序號在一維數(shù)組中的序號=2 + 3( (i1) )+( ( ji + 2) )=2i+ j+1 一維數(shù)組下標從一維數(shù)組下標從0開始開始元素元素aij在一維數(shù)組中的下標在一維數(shù)組中的下標=2i+ j(b) 尋址的計算方法尋址的計算方法(c) 壓縮到一維數(shù)組中壓縮到一維

20、數(shù)組中a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6 7 8 9 10 11 12矩陣的壓縮存儲矩陣的壓縮存儲對角矩陣的壓縮存儲（方式二）對角矩陣的壓縮存儲（方式二）(a) 三對角矩陣三對角矩陣 0 0 0 0 00 00 0 0 0 0 A=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0

21、0 0 0 0 0 0 0 9 0 0 0 0 0A=如何只存儲非零元素？如何只存儲非零元素？矩陣的壓縮存儲矩陣的壓縮存儲注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義template struct element int row, col; /行號，列號行號，列號 T item /非零元素值非零元素值;將稀疏矩陣中的每個非零元素表示為將稀疏矩陣中的每個非零元素表示為：( (行號，列號，非零元素值行號，列號，非零元素值) )三元組三元組矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩

22、陣的壓縮存儲 定義三元組定義三元組：數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義三元組表三元組表：將稀疏矩陣的非零元素對應的三元組所將稀疏矩陣的非零元素對應的三元組所構成的集合，構成的集合，按行優(yōu)先的順序排列成一個線性表。按行優(yōu)先的順序排列成一個線性表。矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 三元組表三元組表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存儲三元組表？如何存儲三元組

23、表？數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表采用順序存儲結構存儲三元組表采用順序存儲結構存儲三元組表15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表是否三元組順序表是否需要預留存儲空間？需要預留存儲空間？稀疏矩陣的修改操作稀疏矩陣的修改操作三元組順序表的插入三元組順序表的插入/ /刪除操作刪除操作數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義稀疏矩陣的壓

24、縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表采用順序存儲結構存儲三元組表采用順序存儲結構存儲三元組表 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -1矩陣的壓縮存儲矩陣的壓縮存儲15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=7（非零元個數(shù)）（非零元個數(shù)）三元組表是否對應惟一的稀三元組表是否對應惟一的稀疏矩陣？疏矩陣？5（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的

25、列數(shù)）（矩陣的列數(shù)）數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義存儲結構定義：存儲結構定義： const int MaxTerm=100; template struct SparseMatrix T dataMaxTerm; /存儲非零元素存儲非零元素 int mu, nu, tu; /行數(shù)，列數(shù)，非零元個數(shù)行數(shù)，列數(shù)，非零元個數(shù) ;矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義三元組順序表操作三元組順序表操作轉置操作轉置操作例：例： 15 0 0 0 9

26、1 0 11 0 0 0 0 3 0 0 0 22 0 6 0 0 0 0 0 0 0 - -15 0 0 0 0 B=15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩

27、陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義三元組順序表轉置算法三元組順序表轉置算法算法算法 基本思想：基本思想：直接取，順序存直接取，順序存。即。即在在A的三元組順序的三元組順序表中表中依次依次找第找第0列、第列、第1列

28、、列、直到最后一列的三元直到最后一列的三元組，并將找到的每個三元組的行、列交換后組，并將找到的每個三元組的行、列交換后順序順序存存儲到儲到B的三元組順序表中。的三元組順序表中。 矩陣的壓縮存儲矩陣的壓縮存儲數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row

29、col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）設置矩陣設置矩陣B的行數(shù)、列數(shù)、非零元個數(shù)的行數(shù)、列數(shù)、非零元個數(shù)數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row

30、 col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第0列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B中中 0 0 15 0 4 91數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（

31、矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第1列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B中中 0 0 15 0 4 91 1 1 11數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456Max

32、Term- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第2列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B中中 0 0 15 0 4 91 1 1 11 2 1 3數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空

33、空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第3列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲

34、0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第4列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2

35、6數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第5列非零元，順序存儲到矩陣列非零

36、元，順序存儲到矩陣B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（

37、矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣A中查找第中查找第6列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義1. 設置轉置后矩陣設置轉置后矩陣B的行數(shù)、列數(shù)和非零元個數(shù)；的行數(shù)、列數(shù)和非零元個數(shù)；2. 在在B中設置初始存儲位置中設置初始存儲位置pb；3. for (col=最小列號最小列號; col=最大列號最大列號; col+) 3.1 在在A中查找列號為中查找列號為col的三元組；的三元組；

38、3.2 交換其行號和列號，存入交換其行號和列號，存入B中中pb位置；位置； 3.3 pb+；矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉置算法三元組順序表轉置算法偽代碼偽代碼數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義分析分析：A中第中第0列的第一個非零元素一定存儲在列的第一個非零元素一定存儲在B中下中下標為標為0的位置上，該列中其它非零元素應存放在的位置上，該列中其它非零元素應存放在B中中后面連續(xù)的位置上，那么第后面連續(xù)的位置上，那么第1列的第一個非零元素在列的第一個非零元素在B中的位置便等于第中的位置便等于第0列的第一個非零元素在列的第一個非零元素在B中的位中的位置

39、加上第置加上第0列的非零元素的個數(shù)，以此類推。列的非零元素的個數(shù)，以此類推。 基本思想：基本思想：順序取，直接存。順序取，直接存。即即在在A中依次取三元中依次取三元組，交換其行號和列號放到組，交換其行號和列號放到B 中中適當適當位置。位置。矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉置算法三元組順序表轉置算法算法算法如何確定當前從如何確定當前從A中取出的三元組在中取出的三元組在B中的位置？中的位置？數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉置算法三元組順序表轉置算法算法算法 row col item0123456MaxTerm

40、- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15第第0列第列第1個非零元素個非零元素第第0列有列有2個非零元素個非零元素第第1列第列第1個非零元素個非零元素數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義引入兩個數(shù)組作為輔助數(shù)據(jù)結構：引入兩個數(shù)組作為輔助數(shù)據(jù)結構：numnu：存儲矩陣存儲矩陣A中某列的非零元素的個數(shù)；中某列的非零元素的個數(shù)；cpotnu：初值表示矩陣初值表示矩陣A中某列的第一個非零元素中某列的第一個非零元素在在B

41、中的位置。中的位置。 數(shù)據(jù)結構設計：數(shù)據(jù)結構設計：cpot0=0；cpotcol=cpotcol- -1+numcol- -1； 1colnunum與與cpot存在如下遞推關系：存在如下遞推關系：矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉置算法三元組順序表轉置算法算法算法數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7

42、（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲 col 0 1 2 3 4 5 numcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根據(jù)矩陣根據(jù)矩陣A計算計算num和和cpot 數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣A中中col列

43、元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot0cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)

44、）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0 3 0 22cpot3數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01

45、234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot1cpot2cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5cpot5數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1

46、 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot1cpot2cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1數(shù)據(jù)結構（數(shù)據(jù)結構（C+

47、版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot2cpot4 0 0 15cpo

48、t0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1 2 1 3cpot2cpot1數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234

49、566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11 2 1 3cpot2cpot1 3 2 6cpot3數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的

50、壓縮存儲將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot4 0 0 15cpot0 3 0 22 5 0 -15cpot5 1 1 11 2 1 3cpot2cpot1 3 2 6cpot3 0 4 91cpot0數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義1. 設置轉置后矩陣設置轉置后矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)；的行數(shù)、列數(shù)和非零元素的個數(shù)；2. 計算計算A中每一列的非零元素個數(shù)

51、；中每一列的非零元素個數(shù)；3. 計算計算A中每一列的第一個非零元素在中每一列的第一個非零元素在B中的下標；中的下標；4. 依次取依次取A中的每一個非零元素對應的三元組；中的每一個非零元素對應的三元組； 4.1 確定該元素在確定該元素在B中的下標中的下標pb； 4.2 將該元素的行號列號交換后存入將該元素的行號列號交換后存入B中中pb的位置；的位置； 4.3 預置該元素所在列的下一個元素的存放位置；預置該元素所在列的下一個元素的存放位置；矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉置算法三元組順序表轉置算法偽代碼偽代碼數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義采用采用鏈

52、接鏈接存儲結構存儲三元組表，每個非零元素對應存儲結構存儲三元組表，每個非零元素對應的三元組存儲為一個鏈表結點，結構為：的三元組存儲為一個鏈表結點，結構為： rowcolitemdownrightrow：存儲非零元素的行號存儲非零元素的行號col：存儲非零元素的列號存儲非零元素的列號item：存儲非零元素的值存儲非零元素的值right：指針域，指向同一行中的下一個三元組指針域，指向同一行中的下一個三元組down：指針域，指向同一列中的下一個三元組指針域，指向同一列中的下一個三元組矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲十字鏈表十字鏈表數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海

53、洋大學廣東海洋大學 謝仕義謝仕義 2 0 2M=3 0 0 50 1 0 02 0 0 0矩陣的壓縮存儲矩陣的壓縮存儲 0 0 3 0 3 5 1 1 1稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲十字鏈表十字鏈表數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義廣義表：廣義表：n（n0）個數(shù)據(jù)元素的有限序列，記作：個數(shù)據(jù)元素的有限序列，記作： LS(a1，a2，an)其中：其中：LS是廣義表的名稱，是廣義表的名稱，ai（1in）是是LS的成員的成員（或直接元素），（或直接元素），它可以是單個的數(shù)據(jù)元素它可以是單個的數(shù)據(jù)元素，也可以也可以是一個廣義表是一個廣義表，分別稱為，分別稱為

54、LS的的單元素（或原子）單元素（或原子）和和子子表表。 廣義線性表廣義線性表廣義表廣義表廣義表的邏輯結構：直接元素之間是線性關系。廣義表的邏輯結構：直接元素之間是線性關系。廣義表的基本概念廣義表的基本概念通常用大寫字母表示廣義表，用小寫字母表示單元素。通常用大寫字母表示廣義表，用小寫字母表示單元素。 數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義長度：長度：廣義表廣義表LS中的直接元素的個數(shù)；中的直接元素的個數(shù)；深度：深度：廣義表廣義表LS中括號的最大嵌套層數(shù)。中括號的最大嵌套層數(shù)。表頭：表頭：廣義表廣義表LS非空時，稱第一個元素為非空時，稱第一個元素為LS的表頭；的表

55、頭；表尾：表尾：廣義表廣義表LS中除表頭外其余元素組成的廣義表。中除表頭外其余元素組成的廣義表。廣義線性表廣義線性表廣義表廣義表廣義表廣義表( )( )和廣義表和廣義表( )( )有什么不同？有什么不同？ 廣義表的基本概念廣義表的基本概念數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義A ( )B (e)C (a, (b，c，d)D (A, B, C) E (a, E)F ( )廣義線性表廣義線性表廣義表廣義表廣義表的示例廣義表的示例長度？深度？表頭？表尾？長度？深度？表頭？表尾？數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義A ( )B (e)C

56、 (a, (b，c，d)D (A, B, C) E (a, E)F ( )廣義線性表廣義線性表廣義表廣義表廣義表的圖形表示廣義表的圖形表示ABeCabcdD數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義廣義線性表廣義線性表廣義表廣義表廣義表可以采用順序存儲結構嗎？廣義表可以采用順序存儲結構嗎？由于廣義表中的數(shù)據(jù)元素的類型不統(tǒng)一，因此難以由于廣義表中的數(shù)據(jù)元素的類型不統(tǒng)一，因此難以采用順序存儲結構來存儲。采用順序存儲結構來存儲。 若廣義表不空，則可分解為表頭和表尾；反之，一若廣義表不空，則可分解為表頭和表尾；反之，一對確定的表頭和表尾可唯一地確定一個廣義表。對確定的表頭和表尾可唯一地確定一個廣義表。 采用頭尾表示法存儲廣義表采用頭尾表示法存儲廣義表 如何采用鏈接存儲結構存儲廣義表？如何采用鏈接存儲結構存儲廣義表？數(shù)據(jù)結構（數(shù)據(jù)結構（C+版）版）廣東海洋大學廣東海洋大學 謝仕義謝仕義廣義表的存儲結構廣義表的存儲結構頭尾表示法頭尾表示法廣義線性表廣義線性表廣義表廣義表廣義表中的數(shù)