資料結構之數組和廣義表

四、數組和廣義表

• 數組的定義

1. 數組是我們熟悉的資料類型，數組中各元素具有統一的類型，并且數組元素的下标一般具有固定的上界和下界，是以，數組的處理比其它複雜的結構更為簡單。
2. 任何數組A都可以看作一個線性表。數組維數确定後，資料元素個數和元素之間的關系不再發生改變，适合順序存儲。
3. 數組的基本操作                                                                                                 

   

• 數組的順序表示和實作

1. 行優先順序                                                                                                

   

2. 列優先順序                                                                                                           

   

• 矩陣的壓縮存儲

1. 有些特殊矩陣，非零元素呈某種規律分布或者矩陣中出現大量的零元素的情況下，會占用許多單元去存儲重複的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節省存儲空間，對這類矩陣進行壓縮存儲——即為多個相同的非零元素隻配置設定一個存儲空間；對零元素不配置設定空間。
2. 特殊矩陣：所謂特殊矩陣是指非零元素或零元素的分布有一定規律的矩陣，如對稱矩陣、三角矩陣、對角矩陣等等。                                                                     

   

• 對稱矩陣

1. 

2. 對稱矩陣中元素關于主對角線對稱，故隻要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣能節約近一半的存儲空間。
3. n2 個元素可以壓縮到 n（n+1）/2個空間中。                                                   

   

4. 

• 三角矩陣

1. 以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣它的下三角中的元素均為常數。下三角矩陣正好相反，它的主對角線上方均為常數。

   

2. 

3. 

• 稀疏矩陣

1. 

2. 除了記錄非零元素的值之外，還必須同時幾下它所在的行和列的位置。稀疏矩陣的存儲方法一般有三種：三元組法、行邏輯連接配接順序表和十字連結清單法。

3. 

• 廣義表

1. 是由零個或多個原子或子表組成的優先序列，是線性表的推廣。

   

   

2. 

   

   

   

   

• 廣義表的存儲結構

1. 廣義表中的資料元素可以具有不同的結構，是以，難以用順序存儲結構表示，通常采用鍊式存儲結構，每個資料元素可用一個節點表示。由于廣義表中有兩種資料元素，是以需要有兩種結構的節點——一種是表結點，一種是原子結點。
2. 表結點由三個域組成：标志域、訓示表頭的指針的指針域和訓示表尾的指針域；而原子域隻需兩個域：标志域和值域。                                                  

   

   

3. 表結點由三個域組成：标志域、訓示表頭的指針域和指向下一個元素的指針；原子結點的三個域為：标志域、值域和指向下一個元素的指針。

   

   

作者：龍貓小爺

連結：http://www.jianshu.com/p/2469a4d9708e

來源：簡書

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。