數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組B

1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2第5章數(shù)組和廣義表（Arrays&Lists）5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表（即廣義的線性表）。②所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型。數(shù)組和廣義表的特點(diǎn)：一種特殊的線性表3順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。（難點(diǎn)是：多維數(shù)組與一維數(shù)組的地址映射關(guān)系）例1：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,請(qǐng)問按列存儲(chǔ)的公式相同嗎？

答：盡管是方陣，但公式仍不同，要作修改：

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例2：〖00年計(jì)算機(jī)系考研題〗設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

。根據(jù)列優(yōu)先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950答：請(qǐng)注意審題！想一想：若數(shù)組是a[0…59,0…69]，結(jié)果是否仍為8950？89504例3：【專科考研資格考試】假設(shè)有三維數(shù)組A7×9×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，末尾元素A[6][8][7]的第一個(gè)字節(jié)地址為多少？若按高地址優(yōu)先存儲(chǔ)時(shí)，元素A[4][7][6]的第一個(gè)字節(jié)地址為多少？

答：

①末尾元素A[6][8][7]的第1個(gè)字節(jié)地址＝

1000+(7×9×8)×6－6=4018

②按高地址優(yōu)先存儲(chǔ)時(shí)，元素A[4][7][6]的第1個(gè)字節(jié)地址＝提示：將第3維看作“頁(yè)碼”，前面兩維就是每頁(yè)上的二維數(shù)組。（高維地址計(jì)算通式參見清華殷人昆教材的解釋）3586只要計(jì)算出任一數(shù)組元素的地址，就能對(duì)其輕松地進(jìn)行讀寫操作！計(jì)算地址的意義：5^……行指針向量a11a12…^a1nam1am2…^amn補(bǔ)充：數(shù)組的鏈?zhǔn)酱鎯?chǔ)方式—用帶行指針向量的單鏈表來表示。注：鏈?zhǔn)綌?shù)組的運(yùn)算請(qǐng)參見“稀疏矩陣的轉(zhuǎn)置”注意：本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組有所區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。65.3矩陣的壓縮存儲(chǔ)討論：1.什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2.所有二維數(shù)組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。3.什么樣的矩陣具備以上壓縮條件？

一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。4.什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）重點(diǎn)介紹稀疏矩陣的壓縮和相應(yīng)的操作。7一、稀疏矩陣的壓縮存儲(chǔ)問題：如果只存儲(chǔ)稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？解決思路：對(duì)每個(gè)非零元素增開若干存儲(chǔ)單元，用來存放其所在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置。實(shí)現(xiàn)方法：將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來表示，則每個(gè)稀疏矩陣可用一個(gè)三元組表來表示。二、稀疏矩陣的操作8例1：

三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的

、

和

。行下標(biāo)列下標(biāo)元素值例2：寫出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。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種存儲(chǔ)形式。法1：用線性表表示：0

1290000

00000-30001400

024

0000

18000015

00-700()9法2：用三元組矩陣表示：0

1290000

00000-30001400

024

0000

18000015

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

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

i)21i0

1290000

00000-30001400

024

0000

18000015

00-700-7461516182524341453-3139311221866vji0123456783用途：便于高效訪問稀疏矩陣中任一非零元素。POS(i)如何計(jì)算？POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)11法四：用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：每個(gè)非0元素占用5個(gè)域rightdownvji同一列中下一非零元素的指針同一行中下一非零元素的指針十字鏈表的特點(diǎn)：①每行非零元素鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表；②每列非零元素也鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表。則每個(gè)非零元素既是行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)；又是列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，即呈十字鏈狀。122100H1931182512typedefstruct{

Triple

data[MAXSIZE+1];//三元組表，以行為主序存入一維向量

data[]中

intmu;//矩陣總行數(shù)

intnu;//矩陣總列數(shù)

inttu;//矩陣中非零元素總個(gè)數(shù)}TsMatrix;三元組表的順序存儲(chǔ)表示（見教材P98）對(duì)三元組表data[]的整體定義

#defineMAXSIZE125000//設(shè)非零元素最大個(gè)數(shù)125000typedefstruct{inti;//元素行號(hào)

intj;//元素列號(hào)

ElemTypee;//元素值}Triple;對(duì)表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義13二、稀疏矩陣的操作

0

12

90000

00000-30001400

0240000

18000015

00-7000

0–3001512

000180

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轉(zhuǎn)置后MT（以轉(zhuǎn)置運(yùn)算為例）目的：14答：肯定不正確！除了：（1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的i和j互換）；還需要：（2）T的總行數(shù)mu和總列數(shù)nu也要互換；（3）重排三元組內(nèi)各元素順序，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。上述（1）和（2）容易實(shí)現(xiàn)，難點(diǎn)在（3）。

若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？有兩種實(shí)現(xiàn)轉(zhuǎn)置的方法壓縮轉(zhuǎn)置快速(壓縮)轉(zhuǎn)置提問：15方法1：壓縮轉(zhuǎn)置思路：反復(fù)掃描a表（記為a.data）中的列序，從j=1～n依次進(jìn)行轉(zhuǎn)置。三元組表a.data三元組表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④(2,5,18)⑤(3,1,9)⑥(3,4,24)⑦(4,6,-7)⑧(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)1122colq1234討論：每個(gè)元素的列分量怎樣書寫？a.data[p].jp1234......16StatusTransPoseSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){

q=1;for(col=1;col<=M.nu;col++){for(p=1;p<=M.tu;p++){if(M.data[p].j==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;q++;}}}

}returnOK;}//TranposeSMatrix;壓縮轉(zhuǎn)置算法描述：（見教材P99）//用三元組表存放稀疏矩陣M，求M的轉(zhuǎn)置矩陣T//q是轉(zhuǎn)置矩陣T的結(jié)點(diǎn)編號(hào)//col是掃描M三元表列序的變量//p是M三元表中結(jié)點(diǎn)編號(hào)這里的M和T其實(shí)都是三元組表形式！17三元組表a.data三元組表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④(2,5,18)⑤(3,1,9)⑥(3,4,24)⑦(4,6,-7)⑧(5,3,14)(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(1,3,9)(1,2,12)1122colq1234p1234......1、主要時(shí)間消耗在查找M.data[p].j=col的元素，由兩重循環(huán)完成:for(col=1;col<=M.nu;col++)循環(huán)次數(shù)＝列長(zhǎng)度nu

{for(p=1;p<=M.tu;p++)循環(huán)次數(shù)＝非零元素個(gè)數(shù)tu壓縮轉(zhuǎn)置算法的效率分析：所以該算法的時(shí)間復(fù)雜度為O(nu*tu)----即M的列數(shù)與M中非零元素的個(gè)數(shù)之積最惡劣情況：M中全是非零元素，此時(shí)非零元素總數(shù)tu=mu*nu，時(shí)間復(fù)雜度為O(nu2*mu)注：若M中基本上是非零元素時(shí)，即使用傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過是O(nu*mu)（程序見教材P99）結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。前提：僅適用于非零元素個(gè)數(shù)很少（即tu<<mu*nu）的情況。18方法2

快速轉(zhuǎn)置三元組表a.data三元組表b.data③(1,3,-3)①(2,1,12)⑥(2,5,18)②(3,1,9)⑧(4,6,-7)④(5,3,14)⑦(1,6,15)⑤(3,4,24)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)思路：依次把a(bǔ).data中的元素直接送入b.data的恰當(dāng)位置上（即M三元組的p指針不回溯）。關(guān)鍵：怎樣尋找b.data的“恰當(dāng)”位置？p1234q3519如果能預(yù)知M矩陣每一列(即T的每一行)的非零元素個(gè)數(shù)，又能預(yù)知第一個(gè)非零元素在b.data中的位置,則掃描a.data時(shí)便可以將每個(gè)元素準(zhǔn)確定位（因?yàn)橐阎舾蓞⒖键c(diǎn)）。技巧：先生成三元組表的兩個(gè)輔助向量，讓它攜帶每行（或列）的非零元素個(gè)數(shù)NUM(i)以及每行（或列）的第一個(gè)非零元素在三元組表中的位置POS(i)

等信息。設(shè)計(jì)思路：i123456NUM(i)202112POS(i)133567注：為實(shí)現(xiàn)轉(zhuǎn)置運(yùn)算，應(yīng)當(dāng)按列生成

M矩陣的輔助向量計(jì)算式：POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)輔助向量的樣式：請(qǐng)注意a.data特征：每列首個(gè)非零元素必定先被掃描到。20令：M矩陣中的列變量用col表示；

num[col]：存放M中第col列中非0元素個(gè)數(shù)

cpot[col]：存放M中第col列的第一個(gè)非0元素的位置

（即b.data中待計(jì)算的“恰當(dāng)”位置所需參考點(diǎn)）討論：求出按列優(yōu)先的輔助向量后，如何實(shí)現(xiàn)快速轉(zhuǎn)置？col123456num[col]222110cpot[col]1計(jì)算式：cpot(1)＝1cpot[col]

＝

cpot[col-1]+num[col-1]

357890

12

90000

00000-30001400

0240000

18000015

00-700Mcol123456由a.data中每個(gè)元素的列信息，可以直接從輔助向量cpot[col]中查出在b.data中的“基準(zhǔn)”位置，進(jìn)而得到當(dāng)前元素之位置。三元組表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)colp1234...想一想：是從原始矩陣M中統(tǒng)計(jì)num[col]方便些，還是從對(duì)應(yīng)的三元組表a.data中統(tǒng)計(jì)更方便？21StatusFastTransposeSMatrix（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(i=1;i<=M.tu;i++){col=M.data[i].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;快速轉(zhuǎn)置算法描述：//M是順序存儲(chǔ)的三元組表，求M的轉(zhuǎn)置矩陣T//先統(tǒng)計(jì)每列非零元素個(gè)數(shù)//再生成每列首元位置輔助向量//p指向a.data，循環(huán)次數(shù)為非0元素總個(gè)數(shù)tu//查輔助向量得q，即T中位置前3個(gè)for循環(huán)用來產(chǎn)生兩個(gè)輔助向量重要！修改向量?jī)?nèi)容（列坐標(biāo)加1），預(yù)備給同列的下一非零元素定位之用元素轉(zhuǎn)置221.

與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了2個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組(num[]和cpos[]）。傳統(tǒng)轉(zhuǎn)置：O(mu*nu)壓縮轉(zhuǎn)置：O(mu*tu)壓縮快速轉(zhuǎn)置：O(nu+tu)快速轉(zhuǎn)置算法的效率分析：2.

從時(shí)間上，此算法用了4個(gè)并列的單循環(huán)，而且其中前3個(gè)單循環(huán)都是用來產(chǎn)生輔助向量表的。

for(col=1;col<=M.nu;col++){};循環(huán)次數(shù)＝nu;

for(i=1;i<=M.tu;i++){};循環(huán)次數(shù)＝tu;

for(col=2;col<=M.nu;col++){};循環(huán)次數(shù)＝nu;

for(p=1;p<=M.tu;p++){};循環(huán)次數(shù)＝tu;

該算法的時(shí)間復(fù)雜度＝nu+tu+nu+tu=O(nu+tu）討論：最惡劣情況是矩陣中全為非零元素，此時(shí)tu=nu*mu而此時(shí)的時(shí)間復(fù)雜度也只是O(mu*nu)，并未超過傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。小結(jié)：稀疏矩陣相乘的算法略，見教材P101-103增設(shè)輔助向量，犧牲空間效率換取時(shí)間效率。235.4廣義表的定義廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)

廣義表名表頭(Head）表尾(Tail)1、定義：①第一個(gè)元素是表頭，而其余元素組成的表稱為表尾；②用小寫字母表示原子類型，用大寫字母表示列表。n是表長(zhǎng)在廣義表中約定：討論：廣義表與線性表的區(qū)別和聯(lián)系？廣義表中元素既可以是原子類型，也可以是列表；當(dāng)每個(gè)元素都為原子且類型相同時(shí)，就是線性表。242、特點(diǎn)：有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。25E=(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：求下列廣義表的長(zhǎng)度。n=0，因?yàn)锳是空表n=1，表中元素e是原子n=2，a為原子，(b,c,d)為子表n=3，3個(gè)元素都是子表n=2，a為原子，E為子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表26ABDCeabcd②A=(a,(b,A))例2：試用圖形表示下列廣義表.（設(shè)代表子表，

代表元素）

e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的長(zhǎng)度為3，深度為3②的長(zhǎng)度為2，深度為∞深度＝括號(hào)的重?cái)?shù)＝結(jié)點(diǎn)的層數(shù)27介紹兩種特殊的基本操作：GetHead(L)——取表頭(可能是原子或列表);GetTail(L)——取表尾(一定是列表)

。廣義表的抽象數(shù)據(jù)