首先最開始我們先回憶一下數(shù)組的概念

1.數(shù)組的定義

數(shù)組是由n個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的有限序列，每個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素，每個(gè)元素在n個(gè)線性關(guān)系中的序號(hào)稱為該元素的下標(biāo)，下標(biāo)的取值范圍稱為數(shù)組的維界。

數(shù)組與線性表的關(guān)系

數(shù)組是線性表的推廣

• 一維數(shù)組可以視為一個(gè)線性表
• 二維數(shù)組可視為其元素為定長(zhǎng)線性表的線性表
• 數(shù)組一旦被定義，其維數(shù)和維界就不再改變，因此除了數(shù)組結(jié)構(gòu)的初始化和銷毀外，數(shù)組只能執(zhí)行存儲(chǔ)元素和修改元素的操作

在了解完數(shù)組的定義后，我們?cè)倭私庖幌聰?shù)組在內(nèi)存中是如何存儲(chǔ)的

2.數(shù)組的存儲(chǔ)結(jié)構(gòu)

一個(gè)數(shù)組的所有元素在內(nèi)存中占用一段連續(xù)的存儲(chǔ)空間

一維數(shù)組的存儲(chǔ)如下：

對(duì)于多維數(shù)組，比如二維數(shù)組來(lái)說(shuō)，有兩種映射方法：按行優(yōu)先 和 按列優(yōu)先

按行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相等先存儲(chǔ)列號(hào)較小的元素

按列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相等先存儲(chǔ)行號(hào)較小的元素

習(xí)題1

在了解數(shù)組在內(nèi)存中的存儲(chǔ)方式后，我們可以開始用數(shù)組來(lái)存儲(chǔ)矩陣中的元素了！

3.對(duì)稱矩陣

概念

對(duì)于一個(gè)n階方陣A中的任意一個(gè)元素a_i,j都有a_i,j=a_j,i，則稱為對(duì)稱矩陣

對(duì)于一個(gè)對(duì)稱矩陣我們可以將其中的元素劃分為3個(gè)部分：上三角區(qū)，主對(duì)角線和下三角區(qū)

存儲(chǔ)方法選擇

土辦法

用一個(gè)n*n的數(shù)組去完完整整地將整個(gè)矩陣中的元素給存儲(chǔ)下來(lái)。

壓縮存儲(chǔ)法

我們發(fā)現(xiàn)對(duì)于n階對(duì)稱矩陣，上三角區(qū)的所有元素與下三角區(qū)的所有元素相同，若采用上述的土辦法，將會(huì)浪費(fèi)幾乎一半的空間，因此我們將其中重復(fù)相同的元素只存放一次。

存儲(chǔ)主對(duì)角線和下三角區(qū)

可見，采取行優(yōu)先的原則將主對(duì)角線和下三角區(qū)的元素存入數(shù)組B當(dāng)中

那么在數(shù)組B當(dāng)中，a_i,j對(duì)應(yīng)B[?]呢？我們可以自己通過(guò)計(jì)算得出一個(gè)映射公式

習(xí)題1

習(xí)題2

4.三角矩陣

概念

存儲(chǔ)方法選擇

土辦法

用一個(gè)n*n的數(shù)組去完完整整地將整個(gè)矩陣中的元素給存儲(chǔ)下來(lái)。

壓縮存儲(chǔ)法

與對(duì)稱矩陣不同之處在于，存儲(chǔ)完下三角區(qū)和主對(duì)角線上的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量一次。

按行存儲(chǔ)主對(duì)角線和下三角區(qū)+常量C

按行存儲(chǔ)主對(duì)角線和上三角區(qū)+常量C

5.三對(duì)角矩陣

概念

對(duì)角矩陣稱為帶狀矩陣；在三對(duì)角矩陣中，所有非零元素都集中在以主對(duì)角線為中心的3條對(duì)角線的區(qū)域，其他區(qū)域的元素都為零

存儲(chǔ)方法選擇

壓縮存儲(chǔ)法

習(xí)題1

6.稀疏矩陣

概念

矩陣中非零元素的個(gè)數(shù)t，相對(duì)矩陣元素的個(gè)數(shù)s來(lái)說(shuō)非常少，即s>>t的矩陣稱為稀疏矩陣。

存儲(chǔ)方法選擇

三元組存儲(chǔ)

十字鏈表法

?