資料結構----數組

數組

按照一定格式排列起來的，具有相同類型的資料元素的集合

一維數組：

int num[5] = {0,1,2,3,4}

二維數組：若一維數組中的元素又是一維數組結構，稱為二維數組

int num[2][3]; 兩行三列

• 因為一個二維數組等于一個一維數組裡面放入一維數組，是以二維數組的還可以使用下面的方式定義：

  typedef elemtype array2[m][n]

  等價于：elemtype為資料的類型，可以為int，float等

  typedef elemtype arry1[n]

  typedef arry1 arry2[m]

三維數組：若二位數數組中的元素又是一個一維數組，則稱作為三維數組。

n維數組:若n-1維數組中的元素又是一個一維數組結構，則稱作n維數組。

• 線性表結構是數組結構的一個特例，而數組結構又是線性表結構的擴充。
• 數組特點：結構固定，定以後維數和維界不再改變
• 數組的基本操作：除了結構的初始化和銷毀以外，隻有取元素和修改元素值的操作。

數組的存儲

• 因為數組的結構固定，維數和維界不變，且數組的基本操作一般為初始化，銷毀，取元素，修改元素值，一般不做插入和删除操作，故數組一般都是用順序存儲，而不使用鍊式存儲的方式。
• 注意：數組可以是多元的，但存儲資料元素的記憶體單元位址是一維的，是以，在存儲數組結構之前，需要解決将多元關系映射到一維關系的問題。
  • 列如：定義數組

    int a[5]

    ；每個元素占用4個位元組，假設a[0]存儲在2000單元，a[3]存儲在2012到2015；

    

  • 假設初始的位址為i，第i個元素的存儲位址LOC(I) = a+i*L，L是資料結構占用的大小，如int型L=4，a是起始位址；
• 二維數組的空間存儲結構
  • 有兩種存儲方式，行優先與列優先，C語言與JAVA等都是使用的行優先的存儲方式

    

    行存儲方式就是一行一行的存儲，如上圖所示；同理列序的存儲方式就是按照列一列一列的存儲
  • 有二維數組A[m][n],LOC(a[i][j]) = LOC(0, 0) + (ni+j)L;L是資料類型占用的大小，如int的時候就是4；i是所在行數，j是所在的列數，注意i和j都是從0開始的，不是從1開始的。
• 三維數組，每一個頁來存，頁内按照二維數組的存儲方式
• n維元素的存儲方式

  

特殊矩陣的壓縮存儲

• 對稱矩陣

  

  

• 三角矩陣

  

• 對角矩陣

  

• 稀疏矩陣

  三元組的法進行儲存

  

第一行代表目前矩陣有多少行多少列，且一共有多少個元素是非零的

• 三元組法的缺點，順序讀取與存儲，插入和查找麻煩

  

• 稀疏矩陣的鍊式存儲結構----十字連結清單

廣義表

• 廣義表的長度與與深度
  • 長度：最外層所包含元素的個數
  • 深度：廣義表展開後所包含的括号重數