4.2數(shù)組
數(shù)組：按一定格式排列起來的，具有相同類型的數(shù)據(jù)元素的集合。
**一維數(shù)組：**若線性表中的數(shù)據(jù)元素為非結(jié)果的簡單元素，則稱為一維數(shù)組。
**一維數(shù)組的邏輯結(jié)構(gòu)：**線性結(jié)構(gòu)，定長的線性表。
**聲明格式：**數(shù)據(jù)類型 變量名稱 [長度] ；
例如：int num[5] = {0,1,2,3,4}；
**二維數(shù)組：**若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱為二維數(shù)組。
二維數(shù)組的邏輯結(jié)構(gòu)：
- 非線性結(jié)構(gòu)：每一個數(shù)據(jù)元素既在一個行表中，又在一個列表中。
- 線性結(jié)構(gòu)定長的線性表：該線性表的每個數(shù)據(jù)元素也是一個定長的線性表。
**聲明格式：**數(shù)據(jù)類型 變量名稱 [行數(shù)] [列數(shù)]；
例如：int num [5] [8];
在C語言中，一個二維數(shù)組類型也可以定義為一維數(shù)組類型（其分量類型為一維數(shù)組類型），即：
typedef int array2[m][n];
等價于：
typedef int array1[n];
typedef array1 array2[m];
**三維數(shù)組：**若二維數(shù)組中的元素又是一個一維數(shù)組，則稱作三維數(shù)組。
**n維數(shù)組：**若 n - 1 維數(shù)組中的元素又是一個一維數(shù)組結(jié)構(gòu)，則稱作 n 維數(shù)組。
**結(jié)論：**線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴展。
**數(shù)組特點：**結(jié)構(gòu)固定——定義后，維數(shù)和維界不再改變。
**數(shù)組基本操作：**除了結(jié)構(gòu)的初始化和銷毀之外，只有取元素和修改元素值的操作。
4.2.1數(shù)組的順序存儲結(jié)構(gòu)
數(shù)組特點：結(jié)構(gòu)固定——維數(shù)和維界不變。
一般都是采用順序存儲結(jié)構(gòu)來表示數(shù)組。
**注意：**數(shù)組可以是多維的，但存儲數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問題。
一維數(shù)組：
例：有數(shù)組定義：int a[5]
每個元素占用4字節(jié)，假設(shè)a[0]存儲在2000單元，a[3]地址是多少？
LOC(0) = a = 2000 L=4
LOC(3) = 3*4+2000
LOC(i) = i*L + 首地址
存儲單元是一維結(jié)構(gòu)，而數(shù)組是個多維結(jié)構(gòu)，則用一組連續(xù)存儲單元存放數(shù)組的數(shù)據(jù)元素就有個次序約定問題。
二維數(shù)組可有兩種存儲方式：
-
以行序為主序；
設(shè)數(shù)組開始存儲位置LOC(0,0)，存儲每個元素需要L個存儲單元
數(shù)組元素a[i] [j]的存儲位置是：LOC(i,j)=LOC(0,0) + (n * i + j) * L
-
以列序為主序。
**三維數(shù)組：**按頁/行/列存放，頁優(yōu)先的順序存儲。
4.2.2特殊矩陣的壓縮存儲
**矩陣：**一個由 m*n 個元素排成的 m 行 n 列的表。
**矩陣的常規(guī)存儲：**將矩陣描述為一個二維數(shù)組。
矩陣的常規(guī)存儲的特點：
- 可以對其元素進行隨機存取。
- 矩陣運算非常簡單；存儲的密度為1.
**不適宜常規(guī)存儲的矩陣：**值相同的元素很多且呈某種規(guī)律分布；零元素多。
**矩陣的壓縮存儲：**為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。
1、什么是壓縮存儲
若多個數(shù)據(jù)元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。
2、什么樣的矩陣能夠壓縮？
一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。
3、什么叫稀疏矩陣？
矩陣中非零元素的個數(shù)較少（一般小于5%）
1.對稱矩陣
**【特點】：**在 n*n 的矩陣 a 中，滿足如下性質(zhì)：aij=aji（1≤i , j≤n）
**【存儲方法】：**只存儲下（或者上）三角（包括主對角線）的數(shù)據(jù)元素。共占用 n(n+1)/2個元素空間。
**【存儲結(jié)構(gòu)】：**對稱矩陣上下三角中的元素數(shù)均為：n(n+1)/2
? 可以以行序為主序?qū)⒃卮娣旁谝粋€一維數(shù)組 sa[ n(n+1)/2 ]中。
2.三角矩陣
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-6FofxLkg-1690537372616)(https://tse1-mm.cn.bing.net/th?id=OIF-C.uHr%2bn0jNJ2j8NRD2iircPA&pid=ImgDet&rs=1)]
**【特點】：**對角線以下（或者以上）的數(shù)據(jù)元素（不包括對角線）全部為常數(shù)c。
**【存儲方法】：**重復(fù)元素c共享一個元素存儲空間，共占用n(n+1)/2+1個元素空間：[1…n(n+1)/2+1]
上三角矩陣：
下三角矩陣：
3.對角矩陣（帶狀矩陣）
**【特點】：**在n*n的方陣中，所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。
4.稀疏矩陣
**稀疏矩陣：**設(shè)在 m*n 的矩陣中有 t 個非零元素。
? 令 δ = t / (m*n)
? 當(dāng) δ ≤ 0.05 時稱為稀疏矩陣。
**壓縮存儲原則：**存各非零元素的值，行列位置和矩陣的行列數(shù)。
4.1三元組順序表
注意：為更可靠描述，通常再加一個“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個數(shù)。
三元組順序表又稱有序的雙下標(biāo)法。
三元組順序表的優(yōu)點：非零元素在表中按行序有序存儲，因此便于進行依行順序處理的矩陣運算。
三元組順序表的缺點：不能隨機存取。若按行號存取某一行中的非零元素，則需從頭開始進行查找。
4.2十字鏈表
-
**優(yōu)點：**它能夠靈活地插入因運算而產(chǎn)生的新的非零元素，刪除因運算而產(chǎn)生的新的零元素，實現(xiàn)矩陣的各種運算。
-
在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了(row，col，value)以外，還要有兩個域：
- right：用于鏈接同一行中的下一個非零元素。
- down：用以鏈接同一列中的下一個非零元素。
-
十字鏈表中結(jié)點的結(jié)構(gòu)示意圖：
4.3廣義表
4.3.1廣義表定義
廣義表（又稱列表Lists）是n≥0個元素 a0，a1，…，an-1的有限序列，其中每一個ai或者是原子，或者是一個廣義表。
例如：中國舉辦的國際足球邀請賽，參賽隊伍名單可表示如下：
（阿根廷，巴西，德國，法國，（），西班牙，意大利，英國，（國家隊，山東魯能，廣州恒大））
在這個表中，敘利亞隊?wèi)?yīng)排在法國隊的后面，但未能參加，成為空表。國家隊，山東魯隊，廣州恒大均作為東道主的參賽隊參加，構(gòu)成一個小的線性表，成為原線性表的一個數(shù)據(jù)元素。這種拓寬了的線性表就是廣義表。
-
廣義表通常記作：LS=( a1，a2，…，an
-
習(xí)慣上，一般用大寫字母表示廣義表，小寫字母表示原子。
-
**表頭：**若LS非空（n≥1），則其第一個元素a1就是表頭。記作head（LS）=a1.
注意：表頭可以是原子，也可以是子表。
-
表尾：除表頭之外的其他元素組成的表。記作tail（LS）=（a2，…，an）
注意：表尾不是最后一個元素，而是一個子表。
例如：（1） A=() 空表，長度為0
? （2）B=(( )) 長度為1，表頭、表尾均為（）。
? （3）C=(a,(b,c)) 長度為2，由原子a和子表（b，c）構(gòu)成。表頭為a，表尾為((b，c))
? （4）D=(x,y,z) 長度為3，每一項都是原子。表頭為x，表尾為（y，z）
? （5）E=(C,D) 長度為2，每一項都是子表。表頭為C，表尾為（D）
? （6）F=(a,F) 長度為2，第一項為原子，第二項為它本身。表頭為a，表尾為（F）。F=(a，(a，(a，…)))
4.3.2廣義表的性質(zhì)
-
廣義表的數(shù)據(jù)元素有相對應(yīng)次序；一個直接前驅(qū)和一個直接后繼。
-
廣義表的長度定義為最外層所包括元素的個數(shù)，如C=(a,(b,c))是長度為2的廣義表。
-
廣義表的深度定義為該廣義表展開后所含括號的重數(shù)。
注意：“原子”的深度為0；“空表”的深度為1。
-
廣義表可以為其他廣義表共享：如：廣義表B就共享表A。在B中不必列出A的值，而是通過名稱來引用。B=(A)
-
廣義表可以是一個遞歸的表。
注意：遞歸表的深度是無窮值，長度是有限值。
-
廣義表是一個多層次結(jié)構(gòu)，廣義表的元素可以是單元數(shù)，也可以是子表，而子表的元素還可以是子表。
4.3.3廣義表和線性表的區(qū)別
廣義表可以看成是線性表的推廣，線性表是廣義表的特例。
廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下，它可以兼容線性表、數(shù)組、數(shù)和有向圖等各種常見的數(shù)據(jù)結(jié)構(gòu)。
當(dāng)二維數(shù)組的每行（或每列）作為子表處理時，二維數(shù)組即為一個廣義表。
另外，數(shù)和有向圖也可以用廣義表來表示。文章來源：http://www.zghlxwxcb.cn/news/detail-615983.html
由于廣義表不僅集中了線性表，數(shù)組，數(shù)和有向圖等常見數(shù)據(jù)結(jié)構(gòu)的特點，而且可有效地利用存儲空間，因此在計算機的許多應(yīng)用領(lǐng)域都有成功使用廣義表的實例。文章來源地址http://www.zghlxwxcb.cn/news/detail-615983.html
4.3.4廣義表的基本運算
- 求表頭GetHead(L)：非空廣義表的第一個元素，可以是一個單一元素，也可以是一個子表。
- 求表尾GetTail(L)：非空廣義表除去表頭元素以外其他元素所構(gòu)成的表，表尾一定是一個表。
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)—數(shù)組和廣義表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
