數(shù)組

概念

• 數(shù)組：按一定格式排列起來(lái)的，具有相同類型的數(shù)據(jù)元素的集合。
• 線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個(gè)特例， 而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。
• 數(shù)組特點(diǎn)：結(jié)構(gòu)固定。定義后，維數(shù)和維界不再改變。
• 基本操作：除了結(jié)構(gòu)的初始化和銷毀之外， 只有取元素和修改元素值的操作，不做插入和刪除的操作。
• 數(shù)組中數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。
• 數(shù)組中的每個(gè)數(shù)據(jù)元素都有對(duì)應(yīng)的下標(biāo)。
• 數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。
• 注意：數(shù)組可以是多維的，但存儲(chǔ)數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲(chǔ)數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問(wèn)題。 ?

一維數(shù)組

• 一維數(shù)組：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡(jiǎn)單元素， 則稱為一維數(shù)組。
• 一維數(shù)組的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。定長(zhǎng)的線性表。
• 聲明格式： 數(shù)據(jù)類型?變量名稱[長(zhǎng)度]；（C語(yǔ)言格式）
  • ?int array[5] = {0, 1, 2, 3, 4};
• 聲明格式： 數(shù)據(jù)類型[] 變量名稱；（Java格式）
  • int[] array = {1, 2, 3, 4}; //靜態(tài)
  • int[] array = new int[4]; //動(dòng)態(tài)

二維數(shù)組

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

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

?基本操作

?

特殊矩陣的壓縮存儲(chǔ)?

概念

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

對(duì)稱矩陣

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

??

?三角矩陣

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

???

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

對(duì)角矩陣?

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

?????

稀疏矩陣

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

?????

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

???