第5章數組和廣義表（Arrays&Lists）5.1數組的定義5.2數組的順序存儲表示和實現5.3矩陣的壓縮存儲5.4廣義表的定義5.5廣義表的存儲結構15.1數組的定義數組：由一組名字相同、下標不同的變量構成注意：這里討論的數組與高級語言中的數組有所區別：高級語言中的數組是順序結構；而這里的數組既可以是順序的，也可以是鏈式結構，用戶可根據需要選擇。答：對的。因為——①數組中各元素具有統一的類型；②數組元素的下標一般具有固定的上界和下界，即數組一旦被定義，它的維數和維界就不再改變。③數組的基本操作比較簡單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的操作。判斷：“數組的處理比其它復雜的結構要簡單”，對嗎？2二維數組的特點：一維數組的特點：1個下標，ai是ai+1的直接前驅2個下標，每個元素ai,j受到兩個關系（行關系和列關系）的約束：一個m×n的二維數組可以看成是m行的一維數組，或者n列的一維數組。N維數組的特點：n個下標，每個元素受到n個關系約束一個n維數組可以看成是由若干個n－1維數組組成的線性表。a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=3N維數組的數據類型定義n_ARRAY=(D,R)其中：

Ri

={<aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

>|

aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

D}數據關系：R={R1,R2，….Rn}數據對象：D={aj1,j2…jn|ji為數組元素的第i維下標，aj1,j2…jn

Elemset}數組的抽象數據類型定義略，參見教材P90構造數組、銷毀數組、讀數組元素、寫數組元素基本操作：45.2數組的順序存儲表示和實現問題：計算機的存儲結構是一維的，而數組一般是多維的，怎樣存放？解決辦法：事先約定按某種次序將數組元素排成一列序列，然后將這個線性序列存入存儲器中。例如：在二維數組中，我們既可以規定按行存儲，也可以規定按列存儲。注意：若規定好了次序，則數組中任意一個元素的存放地址便有規律可尋，可形成地址計算公式；約定的次序不同，則計算元素地址的公式也有所不同；C和PASCAL中一般采用行優先順序；FORTRAN采用列優先。5補充：計算二維數組元素地址的通式

設一般的二維數組是A[c1..d1,c2..d2]，這里c1,c2不一定是0或1無論規定行優先或列優先，只要知道以下三要素便可隨時求出任一元素的地址（意義：數組中的任一元素可隨機存取）：二維數組列優先存儲的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij

…

ad1,c2…ad1,d2

Amn=單個元素長度aij之前的行數數組基址總列數，即第2維長度aij本行前面的元素個數①開始結點的存放地址（即基地址）②維數和每維的上、下界；③每個數組元素所占用的單元數則行優先存儲時的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L6a(0,0)a(0,1)……a(0,3)a(1,0)a(1,1)……a(1,3)………………………………a(3,2)………………………………………………a(6,0)…………a(6,3)01230123456例1：如何求出a(3,2)的存儲地址？要事先確定：①是行優先方式還是列優先方式？②數組的首地址是多少？③每個元素的長度？否則無法求出結果7例3：已知二維數組Am,m按行存儲的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,請問按列存儲的公式相同嗎？答：盡管是方陣，但公式仍不同。應為：Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例2〖軟考題〗：一個二維數組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數組元素用相鄰的6個字節存儲，存儲器按字節編址。那么，這個數組的體積是

個字節。288答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2888例4：〖00年華科考研題〗：設數組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。根據列優先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950答：請注意審題！想一想：若數組是a[0…59,0…69]，結果是否仍為8950？8950維界雖未變，但此時的a[32,58]不再是原來的a[32,58]9Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N維數組，其中任一元素的地址該如何計算？其中Cn=L,Ci-1=bi×Ci，1<i≤n每個元素長度數組基址前面若干元素占用的地址字節總數第i維長度與所存元素個數有關的系數，可用遞推法求出教材已給出低維優先的地址計算公式（見P93（5-2）式）該式稱為n維數組的映像函數：三維數組且列優先時的元素地址要會計算！10例5：【華科專科考研資格考試】假設有三維數組A7×9×8，每個元素用相鄰的6個字節存儲，存儲器按字節編址。已知A的起始存儲位置（基地址）為1000，末尾元素A[6][8][7]的第一個字節地址為多少？若按高地址優先存儲時，元素A[4][7][6]的第一個字節地址為多少？

答：

①末尾元素A[6][8][7]的第1個字節地址＝1000+(7×9×8)×6－6=4018

②按高地址優先存儲時，元素A[4][7][6]的第1個字節地址＝?提示：將第3維看作“頁碼”，前面兩維就是每頁上的二維數組。A[4][7][6]=1000+(7×9×6)×6+(7×7+4)×6=（高維地址計算通式參見清華殷人昆教材的解釋）3586只要計算出任一數組元素的地址，就能對其輕松地進行讀寫操作！計算地址的意義：11#defineMAX_ARRAY_DIM8//假設最大維數為8typedefstruct{ELemType*base;//數組元素基址intdim;//數組維數int*bound;//數組各維長度信息保存區基址int*constants;//數組映像函數常量的基址}Array;即Ci信息保存區數組的基本操作函數說明（有5個）（請閱讀教材P93-95）N維數組的順序存儲表示（見教材P93）12^……行指針向量a11a12…^a1nam1am2…^amn補充：數組的鏈式存儲方式—用帶行指針向量的單鏈表來表示。注：鏈式數組的運算請參見“稀疏矩陣的轉置”注意：本章所討論的數組與高級語言中的數組有所區別：高級語言中的數組只是順序結構；而本章的數組既可以是順序的，也可以是鏈式結構，用戶可根據需要選擇。135.3矩陣的壓縮存儲討論：1.什么是壓縮存儲？若多個數據元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。2.所有二維數組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。3.什么樣的矩陣具備以上壓縮條件？

一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。4.什么叫稀疏矩陣？矩陣中非零元素的個數較少（一般小于5%）重點介紹稀疏矩陣的壓縮和相應的操作。14對稱矩陣

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序為主序：15三角矩陣

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序為主序：16對角矩陣

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序為主序：17稀疏矩陣定義：非零元較零元少，且分布沒有一定規律的矩陣壓縮存儲原則：只存矩陣的行列維數和每個非零元的行列下標及其值18一、稀疏矩陣的壓縮存儲問題：如果只存儲稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？解決思路：對每個非零元素增開若干存儲單元，用來存放其所在的行號和列號，便可準確反映該元素所在位置。實現方法：將每個非零元素用一個三元組（i，j，aij）來表示，則每個稀疏矩陣可用一個三元組表來表示。二、稀疏矩陣的操作19例2：寫出右圖所示稀疏矩陣的壓縮存儲形式。0

1290000

00000-30001400

0240000

18000015

00-700

(1,2,12)

，(1,3,9)，(3,1,-3)，(3,5,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7)解：至少有4種存儲形式。法1：用線性表表示：0

1290000

00000

-30001400

024

0000

18000015

00-700()例1：三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數據項，分別表示該元素的

、

和

。行下標列下標元素值20法2：用十字鏈表表示用途：方便稀疏矩陣的加減運算方法：每個非0元素占用5個域right

downvji同一列中下一非零元素的指針同一行中下一非零元素的指針十字鏈表的特點：①每行非零元素鏈接成帶表頭結點的循環鏈表；②每列非零元素也鏈接成帶表頭結點的循環鏈表。則每個非零元素既是行循環鏈表中的一個結點；又是列循環鏈表中的一個結點，即呈十字鏈狀。122100H19311825稀疏矩陣的加減運算容易實現21法3：用三元組矩陣表示：0

1290000

00000

-30001400

0240000

18000015

00-700121213931-3351443245218611564-7注意：為更可靠描述，通常再加一行“總體”信息：即總行數、總列數、非零元素總個數668ijvalue稀疏矩陣壓縮存儲的缺點：012345678將失去隨機存取功能！22法4：用帶輔助向量的三元組表示。方法：

增加2個輔助向量：①記錄每行非0元素個數，用NUM（i）表示；②記錄稀疏矩陣中每行第一個非0元素在三元組中的行號，用POS（i）表示。76531211202NUM(i)6543POS(i)21i0

12

90000

00000

-30001400

024

0000

18

000015

00-700-7461516182524341453-3139311221866vji0123456783用途：便于高效訪問稀疏矩陣中任一非零元素。POS(i)如何計算？POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)用途后述23總結：右圖所示稀疏矩陣的壓縮存儲形式。0

1290000

00000-30001400

0240000

18000015

00-700至少有4種存儲形式。法1：用線性表表示；法2：用十字鏈表表示；法3：用三元組矩陣表示；法4：用帶輔助向量的三元組表示。

0

1290000

00000

-30001400

024

0000

18000015

00-700便于高效訪問稀疏矩陣中任一非零元素失去隨機存儲功能24例3：下面的三元組表表示一個稀疏矩陣，試還原出它的稀疏矩陣。64612221123134445366116ijvalue01234566460

0000

00000000

0000

0000

0000

20012

000

30000

0040

06016

00025typedefstruct{

Triple

data[MAXSIZE+1];//三元組表，以行為主序存入一維向量data[]中intmu;//矩陣總行數intnu;//矩陣總列數inttu;//矩陣中非零元素總個數}TsMatrix;

三元組表的順序存儲表示（見教材P98）對三元組表data[]的整體定義

#defineMAXSIZE125000

//設非零元素最大個數125000typedefstruct{inti;//元素行號intj;//元素列號ElemTypee;//元素值}Triple;

對表中每個結點的結構定義26二、稀疏矩陣的操作0

129

0000

00000-3

000

14

00

0

24

0000

18

000015

00

-7

000

0–3001512

00018

0

90024000

0000-70

0140000

00000(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)已知三元組表a.data求三元組表b.data轉置后MT（以轉置運算為例，加減用十字鏈表）目的：27答：肯定不正確！除了：（1）每個元素的行下標和列下標互換（即三元組中的i和j互換）；還需要：（2）T的總行數mu和總列數nu也要互換；

（3）重排三元組內各元素順序，使轉置后的三元組也按行（或列）為主序有規律的排列。上述（1）和（2）容易實現，難點在（3）。若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算，這種說法正確嗎？有兩種實現轉置的方法壓縮轉置快速(壓縮)轉置提問：28令：M矩陣中的列變量用col表示；

num[col]：存放M中第col

列中非0元素個數

cpos[col]：存放M中第col列的第一個非0元素的位置

（即b.data中待計算的“恰當”位置所需參考點）討論：求出按列優先的輔助向量后，如何實現快速轉置？col123456num[col]222110cpos[col]1計算式：cpos(1)＝1cpos[col]＝cpos[col-1]+num[col-1]

357890

1290000

00000-30001400

0240000

18000015

00-700Mcol123456由a.data中每個元素的列信息，可以直接從輔助向量cpos[col]中查出在b.data中的“基準”位置，進而得到當前元素之位置。想一想：是從原始矩陣M中來統計num[col]呢，還是從對應的三元組表a.data中統計更合理？三元組表a.data(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(1,3,9)(1,2,12)col

p/t1234...29Status

FastTransposeSMatrix（TSMatirxM,TSMatirx&T）{T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;col++)num[col]=0;

for(t=1;t

<=M.tu;t++){col=M.data[t].j;++num[col];}cpos[1]=1;

for(col=2;col<=M.nu;col++)cpos[col]=cpos[col-1]+num[col-1];for(p=1;p<=M.tu;p++){col=M.data[p].j;q=cpos[col

];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].value=M.data[p].value;

++cpos[col];

}

//for}//ifreturnOK;}//FastTranposeSMatrix;快速轉置算法描述：//M是順序存儲的三元組表，求M的轉置矩陣T//先清0,再//統計每列非零元素個數//再生成每列首元位置輔助向量//p指向a.data，循環次數為非0元素總個數tu//查輔助向量得q，即T中位置前3個for循環用來產生兩個輔助向量重要！巧妙修改向量內容（列坐標加1），使其不再固定指向本列第一個非零元素，而是預備給同列的下一非零元素定位之用元素轉置301.與常規算法相比，附加了生成輔助向量表的工作。增開了2個長度為列長的數組(num[]和cpos[]）。傳統轉置：O(mu*nu)壓縮轉置：O(mu*tu)壓縮快速轉置：O(nu+tu)快速轉置算法的效率分析：2.從時間上，此算法用了4個并列的單循環，而且其中前3個單循環都是用來產生輔助向量表的。

for(col=1;col<=M.nu;col++){};循環次數＝nu（列數）;

for(i=1;i<=M.tu;i++){};循環次數＝tu（非0元素個數）;

for(col=2;col<=M.nu;col++){};循環次數＝nu;

for(p=1;p<=M.tu;p++){};循環次數＝tu;

該算法的時間復雜度＝nu+tu+nu+tu=O(nu+tu）討論：最惡劣情況是矩陣中全為非零元素，此時tu=nu*mu而此時的時間復雜度也只是O(mu*nu)，并未超過傳統轉置算法的時間復雜度。小結：稀疏矩陣相乘的算法略，見教材P101-103增設輔助向量，犧牲空間效率換取時間效率。31第5章數組和廣義表（Arrays&Lists）①元素的值并非原子類型，可以再分解，表中元素也是一個線性表（即廣義的線性表）。②所有數據元素仍屬同一數據類型。5.1數組的定義5.2數組的順序表示和實現5.3矩陣的壓縮存儲5.4廣義表的定義5.5廣義表的存儲結構數組和廣義表的特點：一種特殊的線性表325.4廣義表的定義廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)廣義表名表頭(Head）

表尾(Tail)1、定義：①用小寫字母表示原子類型，用大寫字母表示列表。②第一個元素是表頭，而其余元素組成的表稱為表尾；n是表長在廣義表中約定：特別提示：任何一個非空表，表頭可能是原子，也可能是列表；但表尾一定是列表！332、特點：有次序性有長度有深度可遞歸可共享一個直接前驅和一個直接后繼＝表中元素個數＝表中括號的重數自己可以作為自己的子表可以為其他廣義表所共享討論：廣義表與線性表的區別和聯系？

廣義表中元素既可以是原子類型，也可以是列表；當每個元素都為原子且類型相同時，就是線性表。34E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E為遞歸表1）A=()2）B=(e)3）C=(a,(b,c,d))4）D=(A,B,C)5）E=(a,E)例1：求下列廣義表的長度。n=0，因為A是空表n=1，表中元素e是原子n=2，a為原子，(b,c,d)為子表n=3，3個元素都是子表n=2，a為原子，E為子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表35ABDCeabcd②A=(a,(b,A))例2：試用圖形表示下列廣義表.（設

代表子表，代表元素）

e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的長度為3，深度為3②的長度為2，深度為∞深度＝括號的重數＝結點的層數36廣義表的抽象數據類型定義見教材P107-108ADTGlist{數據對象：D={ei|i=1,2,……,n;n≥0;ei∈AtomSet或Glist}數據關系：R1={<ei-1,ei>|ei-1,ei∈D,2≤i≤n}基本操作：InitGList(&L);

操作結果：創建空的廣義表L.CreateGList