第5章數(shù)組和廣義表數(shù)組和廣義表都是線性表的擴(kuò)展，其元素本身也是一種線性表。數(shù)組是一種常用的結(jié)構(gòu)類型，幾乎所有的程序設(shè)計(jì)語言都有數(shù)組類型。廣義表是一種非線性的數(shù)據(jù)結(jié)構(gòu)，是線性表的一種推廣。1【本章重點(diǎn)】①數(shù)組的存儲(chǔ)結(jié)構(gòu)及元素地址的計(jì)算；②特殊矩陣、稀疏矩陣的壓縮存儲(chǔ)。2【本章難點(diǎn)】

稀疏矩陣的壓縮存儲(chǔ)。3【本章內(nèi)容】數(shù)組特殊矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)習(xí)題545.1數(shù)組數(shù)組的基本概念：數(shù)組中各元素具有相同的類型，數(shù)組元素具有值和確定元素位置的下標(biāo)。數(shù)組可以是一維數(shù)組、二維數(shù)組、三維數(shù)組等等。一維數(shù)組又稱為向量，多維數(shù)組是向量的擴(kuò)充。一維數(shù)組可表示為An=[a1,a2,…,an]，每個(gè)數(shù)據(jù)元素對應(yīng)一個(gè)數(shù)組下標(biāo)，它具有線性表的結(jié)構(gòu)，即除了第一個(gè)元素和最后一個(gè)元素，每個(gè)元素存在一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素。5

6數(shù)組的存儲(chǔ)結(jié)構(gòu)一維數(shù)組的存儲(chǔ)結(jié)構(gòu)：一維數(shù)組的存儲(chǔ)結(jié)構(gòu)與線性表的順序存儲(chǔ)結(jié)構(gòu)類似。二維數(shù)組的存儲(chǔ)結(jié)構(gòu)：存放二維數(shù)組或多維數(shù)組，就必須按照某種順序?qū)?shù)組中的元素形成一個(gè)線性序列，然后將這個(gè)線性序列存放在內(nèi)存中。（1）行優(yōu)先順序存儲(chǔ)

將數(shù)組元素按行向量的順序存儲(chǔ)，即第i+1行的元素存放在第i行的元素之后。元素存儲(chǔ)的線性序列為

a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn（2）列優(yōu)先順序存儲(chǔ)

將數(shù)組元素按列向量的順序存儲(chǔ)，即第j+1列的元素存放在第j列的元素之后。元素存儲(chǔ)的線性序列為

a11,a21,…,am1,a12,a22,…,am2,…,a1n,a2n,…,amn7已知二維數(shù)組存儲(chǔ)的起始地址，下標(biāo)的上、下界，以及每個(gè)數(shù)組元素所占用的存儲(chǔ)單元個(gè)數(shù)，就可以計(jì)算出元素aij的存儲(chǔ)地址，從而對數(shù)組元素隨機(jī)存取。二維數(shù)組A[c1..d1,c2..d2]按行優(yōu)先的順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占d個(gè)存儲(chǔ)單元，計(jì)算元素aij的地址公式：Loc(aij)=Loc(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d

其中Loc(ac1c2)是數(shù)組的起始地址，元素aij前面的i-c1行中共有(i-c1)×(d2-c2+1)個(gè)元素，第i行上元素aij前面又有j-c2個(gè)元素。二維數(shù)組A[c1..d1,c2..d2]按列優(yōu)先的順序存儲(chǔ)在內(nèi)存中，元素aij的地址計(jì)算公式：Loc(aij)=Loc(ac1c2)+[(j-c2)×(d1-c1+1)+i-c1]×d不難寫出一維數(shù)組A[c..d]中元素ai的地址計(jì)算公式：Loc(ai)=Loc(ac)+(i-c+1)×d8【例5.1】假設(shè)二維數(shù)組按行優(yōu)先的順序存儲(chǔ)，分別計(jì)算數(shù)組A[1..m,1..n]和A[0..m-1,0..n-1]中元素aij的地址。（1）行下標(biāo)的下界是1，上界是m；列下標(biāo)的下界是1，上界是n。元素aij的地址是 Loc(aij)=Loc(a11)+[(i-1)×n+j-1]×d（2）行下標(biāo)的下界是0，上界是m-1；列下標(biāo)的下界是0，上界是n-1。元素aij的地址是 Loc(aij)=Loc(a00)+(i×n+j)×d95.2

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

特殊矩陣是指n階方陣中非零元素或零元素的分布具有一定的規(guī)律。特殊矩陣的壓縮存儲(chǔ)就是為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，零元素不分配存儲(chǔ)空間，從而達(dá)到節(jié)省存儲(chǔ)空間的目的。1、三角矩陣

在n階方陣中，以主對角線劃分，如果矩陣的下三角（不包括主對角線）中的元素均為值相同的常數(shù)，則稱為上三角矩陣，反之稱為下三角矩陣。

在多數(shù)情況下，三角矩陣的常數(shù)為零。10（a）上三角矩陣（b）下三角矩陣用向量A[0..n(n+1)/2]壓縮存儲(chǔ)三角矩陣，其中A[0]~A[n(n+1)/2-1]存儲(chǔ)矩陣的下（上）三角中的元素，向量的最后一個(gè)分量A[n(n+1)/2]存儲(chǔ)三角矩陣中的常數(shù)。如何根據(jù)矩陣元素的下標(biāo)i、j，計(jì)算矩陣元素在一維數(shù)組中的下標(biāo)k。（1）下三角矩陣按行優(yōu)先的順序存儲(chǔ)，A[k]與aij的對應(yīng)關(guān)系為（2）上三角矩陣按列優(yōu)先的順序存儲(chǔ)，A[k]與aij的對應(yīng)關(guān)系為11

【例】分別采用一維數(shù)組存儲(chǔ)4階下三角矩陣和上三角矩陣。12

2、對稱矩陣若n階方陣A中的元素關(guān)于主對角線對稱，即滿足下述性質(zhì)：則稱A為對稱矩陣。如果采用一維數(shù)組存儲(chǔ)矩陣中的上三角或下三角元素，使對稱的兩個(gè)元素共享同一個(gè)存儲(chǔ)空間，可以節(jié)省近一半的存儲(chǔ)空間?？梢杂孟蛄緼[0..n(n+1)/2-1]壓縮存儲(chǔ)對稱矩陣。對于下三角部分的元素aij（i>j），可以看作按行優(yōu)先的順序存儲(chǔ)，A[k]與aij的對應(yīng)關(guān)系為：對于上三角部分的元素aij（i<j），可以看作按列優(yōu)先的順序存儲(chǔ)，A[k]與aij的對應(yīng)關(guān)系為：13

【例】一個(gè)4階對稱方陣，按行優(yōu)先的順序存儲(chǔ)下三角矩陣，按列優(yōu)先的順序存儲(chǔ)上三角矩陣。14

3、對角矩陣對角矩陣是指方陣中的所有非零元素集中在以主對角線為中心的帶狀區(qū)域內(nèi)，帶狀區(qū)域之外的元素值均為零。對角矩陣的帶寬可以是3，5，7，...帶寬為3的對角矩陣又稱為三對角矩陣。當(dāng)|i-j|>1時(shí)，元素aij為0。一般地，對于k對角矩陣（k為奇數(shù)），當(dāng)|i-j|>(k-1)/2時(shí)，元素aij為0。15

n階三對角矩陣有3n-2個(gè)非零元素，采用向量A[0..3n-3]按行優(yōu)先的順序壓縮存儲(chǔ)三對角矩陣。每個(gè)非零元素與向量下標(biāo)的對應(yīng)關(guān)系為16

A[2(i-1)+j-1]=aij

1≤i≤n，i-1≤j≤i+1稀疏矩陣的定義：設(shè)矩陣Amn中有t個(gè)非零元素，若t遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即t<<m×n，），并且非零元素在矩陣中的分布沒有規(guī)律，則稱A為稀疏矩陣。存儲(chǔ)系數(shù)矩陣中的非零元素，除了存儲(chǔ)元素值外，還必須存儲(chǔ)該元素的位置信息。通常對稀疏矩陣進(jìn)行壓縮存儲(chǔ)可以采用順序存儲(chǔ)結(jié)構(gòu)的三元組表或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的十字鏈表。175.3稀疏矩陣的壓縮存儲(chǔ)1、稀疏矩陣的三元組表存儲(chǔ)將稀疏矩陣中的非零元素的行號、列號和元素值作為一個(gè)三元組（i，j，aij）所有非零元素的三元組按行優(yōu)先（或列優(yōu)先）的順序排列，便得到一個(gè)其結(jié)點(diǎn)均是三元組的線性表——三元組表。三元組表的結(jié)構(gòu)類型定義描述為#defineMaxSize1000//最大非零元素個(gè)數(shù)typedefintdatatype;typedefstruct{inti,j;//非零元素的行、列號datatypev;//非零元素的元素值}Node;//三元組結(jié)構(gòu)類型typedefstruct{intm,n,t;//行數(shù),列數(shù),非零元素個(gè)數(shù)Nodedata[MaxSize];//存放三元組表的向量}spmatrix;//稀疏矩陣的三元組表結(jié)構(gòu)類型18【例】用三元組表存儲(chǔ)稀疏矩陣。19矩陣的轉(zhuǎn)置（用三元組表存儲(chǔ)矩陣）20算法5.1矩陣的轉(zhuǎn)置（用三元組表存儲(chǔ)矩陣）voidTransMat(spmatrix*a,spmayrix*b)//返回稀疏矩陣A的轉(zhuǎn)置，ano和bno分別指示a→data和b→data中結(jié)點(diǎn)序號//col指示*a的列號(即*b的行號){intano,bno,col;b->m=a->n;b->n=a->m;//A和B的行列數(shù)交換b->t=a->t;//非零元素個(gè)數(shù)if(b->t>0)//有非零元素，則轉(zhuǎn)置{bno=0；for(col=1;col<=a->n;col++)//按*a的列序轉(zhuǎn)置，對a->data掃描n趟 for(ano=0;ano<a->t;ano++)//掃描一趟三元組表 if(a->data[ano].j==col){//列號為col則進(jìn)行置換 b->data[bno].i=a->data[ano].j;//a的列號變?yōu)閎的行號 b->data[bno].j=a->data[ano].i;//a的行號變?yōu)閎的列號 b->data[bno].v=a->data[ano].v; bno++;//b->data結(jié)點(diǎn)序號加1 }}}//TransMat算法的基本思想是：對a->data按列掃描n趟，在第col趟掃描中，找出所