數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表1(嚴(yán)蔚敏)

嚴(yán)習(xí)題集的5.185.30共2題第5章作業(yè)預(yù)告：1數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)：2第5章數(shù)組和廣義表（Arrays&Lists）①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表（即廣義的線性表）。②所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型。5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)數(shù)組和廣義表的特點(diǎn)：一種特殊的線性表35.1數(shù)組的定義數(shù)組：由一組名字相同、下標(biāo)不同的變量構(gòu)成注意：這里討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組有所區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而這里的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。答：對(duì)的。因?yàn)椤贁?shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單”，對(duì)嗎？4二維數(shù)組的特點(diǎn)：一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai是ai+1的直接前驅(qū)2個(gè)下標(biāo)，每個(gè)元素ai,j受到兩個(gè)關(guān)系（行關(guān)系和列關(guān)系）的約束：一個(gè)m×n的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由若干個(gè)n－1維數(shù)組組成的線性表。a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=5N維數(shù)組的數(shù)據(jù)類型定義n_ARRAY=(D,R)其中：Ri={<aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

>|

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

D}數(shù)據(jù)關(guān)系：R={R1,R2，….Rn}數(shù)據(jù)對(duì)象：D={aj1,j2…jn|ji為數(shù)組元素的第i維下標(biāo)，aj1,j2…jn

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

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

ad1,c2…ad1,d2

Amn=單個(gè)元素長(zhǎng)度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長(zhǎng)度aij本行前面的元素個(gè)數(shù)①開始結(jié)點(diǎn)的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個(gè)數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L8a(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)的存儲(chǔ)地址？要事先確定：①是行優(yōu)先方式還是列優(yōu)先方式？②數(shù)組的首地址是多少？③每個(gè)元素的長(zhǎng)度？否則無(wú)法求出結(jié)果9例3：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

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

個(gè)字節(jié)。288答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=28810例4：〖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？8950維界雖未變，但此時(shí)的a[32,58]不再是原來(lái)的a[32,58]11Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N維數(shù)組，其中任一元素的地址該如何計(jì)算？其中Cn=L,Ci-1=bi×Ci，1<i≤n每個(gè)元素長(zhǎng)度數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長(zhǎng)度與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出教材已給出低維優(yōu)先的地址計(jì)算公式（見P93（5-2）式）該式稱為n維數(shù)組的映像函數(shù)：三維數(shù)組且列優(yōu)先時(shí)的元素地址要會(huì)計(jì)算！12例5：【?？瓶佳匈Y格考試】假設(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ì)算地址的意義：13#defineMAX_ARRAY_DIM8//假設(shè)最大維數(shù)為8typedefstruct{ELemType*base;//數(shù)組元素基址intdim;//數(shù)組維數(shù)int*bound;//數(shù)組各維長(zhǎng)度信息保存區(qū)基址int*constants;//數(shù)組映像函數(shù)常量的基址}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說(shuō)明（有5個(gè)）（請(qǐng)閱讀教材P93-95）N維數(shù)組的順序存儲(chǔ)表示（見教材P93）14^……行指針向量a11a12…^a1nam1am2…^amn補(bǔ)充：數(shù)組的鏈?zhǔn)酱鎯?chǔ)方式—用帶行指針向量的單鏈表來(lái)表示。注：鏈?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ù)需要選擇。155.3矩陣的壓縮存儲(chǔ)討論：1.什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2.所有二維數(shù)組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。3.什么樣的矩陣具備以上壓縮條件？

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

1290000

00000-30001400

024

0000

18000015

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

、

和

。行下標(biāo)列下標(biāo)元素值18法2：用三元組矩陣表示：0

1290000

00000-30001400

024

0000

18000015

00-700121213931-3351443245218611564-7注意：為更可靠描述，通常再加一行“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個(gè)數(shù)668ijvalue稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：012345678將失去隨機(jī)存取功能！19法三：用帶輔助向量的三元組表示。方法：增加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)用途后續(xù)20法四：用十字鏈表表示用途：方便稀疏矩陣的加減運(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)，即呈十字鏈狀。122100H19311825稀疏矩陣的加減運(yùn)算容易實(shí)現(xiàn)21例3：下面的三元組表表示一個(gè)稀疏矩陣，試還原出它的稀疏矩陣。64612221123134445366116ijvalue01234566460

0000

00000000

0000

0000

0000

20012

000

30000

0040

06016

00022typedefstruct{

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)定義23二、稀疏矩陣的操作

0

12

9

0000

00000-3

000

14

00

0

24

0000

18

000015

00

-7

000

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)算為例，加減用十字鏈表）目的：24答：肯定不正確！除了：（1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的i和j互換）；還需要：（2）T的總行數(shù)mu和總列數(shù)nu也要互換；（3）重排三元組內(nèi)各元素順序，使轉(zhuǎn)置后的三元組也按行（或列）