數組

概念

• 數組：按一定格式排列起來的，具有相同類型的數據元素的集合。
• 線性表結構是數組結構的一個特例， 而數組結構又是線性表結構的擴展。
• 數組特點：結構固定。定義后，維數和維界不再改變。
• 基本操作：除了結構的初始化和銷毀之外， 只有取元素和修改元素值的操作，不做插入和刪除的操作。
• 數組中數據元素具有相同的數據類型。
• 數組中的每個數據元素都有對應的下標。
• 數組是一種隨機存儲結構，可隨機存取數組中的任意數據元素。
• 注意：數組可以是多維的，但存儲數據元素的內存單元地址是一維的，因此，在存儲數組結構之前，需要解決將多維關系映射到一維關系的問題。 ?

一維數組

• 一維數組：若線性表中的數據元素為非結構的簡單元素， 則稱為一維數組。
• 一維數組的邏輯結構：線性結構。定長的線性表。
• 聲明格式： 數據類型?變量名稱[長度]；（C語言格式）
  • ?int array[5] = {0, 1, 2, 3, 4};
• 聲明格式： 數據類型[] 變量名稱；（Java格式）
  • int[] array = {1, 2, 3, 4}; //靜態
  • int[] array = new int[4]; //動態

二維數組

• 二維數組：若一維數組中的數據元素又是一維數組結構，則稱為二維數組。
• 二維數組主要有兩種存儲方式：按行優先存放（以行為主序），按列優先存放（以列為主序）
• 二維數組的邏輯結構
  • ?非線性結構：每一個數據元素既在一個行表中，又在一個列表中。
  • 線性結構（定長的線性表）：該線性表的每個數據元素也是一個定長的線性表。
• 聲明格式： 數據類型 變量名稱[行數][列數]；（C語言格式）
  • ??int array[5][5];
• ?聲明格式： 數據類型[][]?變量名稱；（Java格式）

  • int[][] array = {{1, 1, 1}, {2, 3, 4, 5}, {0, 0, 0, 0}};

?基本操作

?

特殊矩陣的壓縮存儲?

概念

• 特殊矩陣：一個矩陣內的元素（非零元素：1,2,3...?或?零元素：0）的分布有著一定的規律。在高階矩陣的情況下，可以利用特殊矩陣的分布規律對它們進行壓縮存儲，已達到提高存儲空間的效率。
• 壓縮存儲：若多個數據元素的值都相同，則只分配一個元素值的存儲空間，零元素不占用存儲空間。
• 對稱矩陣，對角矩陣，稀疏矩陣，三角矩陣都是特殊矩陣的主要形式，都是方陣，并且行列數都相同。

對稱矩陣

• 如何辨別什么是對稱矩陣？
  • 在一個行列數相同n階方陣（A[n][n]）中元素a滿足下標i,j = j,i（i >= 0, j <= n - 1）的情況，那么這樣的一個n階方陣就叫對稱矩陣。
• 存儲方法：只存儲下（或者上）三角（包括主對角線）的 數據元素。共占用n(n + 1) / 2個元素空間，如果以行序為主序，則元素下標為a[n(n + 1) / 2]。?

??

?三角矩陣

• 上三角矩陣：指矩陣下三角部分中的元素均為常數c的n階方陣。
• 下三角矩陣：指矩陣上三角部分中的元素均為常數c的n階方陣。

???

• 存儲方法：重復元素c共享一個元素存儲空間，共占用n (n + 1) / 2 + 1個元素 空間：s[1...n (n + 1) / 2 + 1]?

對角矩陣?

• 若一個n階方陣A滿足其所有非零元素都集中在以主對角線為中心的帶狀區域中，則稱其為n階對角矩陣。?

?????

稀疏矩陣

• 矩陣m * n中非零元素t的個數較少（一般小于5%）,t / m * n <= 0.05，則稱為稀疏矩陣
• 稀疏矩陣的分布沒有規律，具有隨機性
• 稀疏矩陣的表示方法：三元組，十字鏈表
• 三元組順序表：又稱有序的雙下標法。存儲稀疏矩陣中的非零元素的行，列，值，一般存儲在第二行依次往下，第一行存儲的是矩陣的行，列，非零元素的個數
  • 優點：非零元在表中按行序有序存儲，因此便于進行依行順序處理的矩陣運算。
  • 缺點：不能隨機存取。若按行號存取某一行中的非零元，則需從頭開始進行查找。

?????

• 十字鏈表的優點：它能夠靈活地插入因運算而產生的新的非零元素， 刪除因運算而產生的新的零元素，實現矩陣的各種運算。
• 在十字鏈表中，矩陣的每一個非零元素用一個結點表示， 該結點除了（row，col，value)以外，還要有兩個域：
  • ?right：用于鏈接同一行中的下一個非零元素
  • down：用于鏈接同一列中的下一個非零元素

???