數(shù)據(jù)結(jié)構(gòu)第五章講義課件

1、!數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的壓縮存儲(chǔ) 第五章 數(shù)組和廣義表廣義表的定義廣義表的存儲(chǔ)結(jié)構(gòu)一、 數(shù)組的定義 數(shù)組： 由一組名字相同、下標(biāo)不同的變量構(gòu)成 數(shù)組中各元素具有統(tǒng)一的類(lèi)型； 數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，只有存取元素和修改元素值的操作。因此一般選用順序存儲(chǔ)。2二維數(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è)mn的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)

2、，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由若干個(gè)n1維數(shù)組組成的線性表。3二、 數(shù)組的運(yùn)算 給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素;給定一組下標(biāo)，修改數(shù)據(jù)元素的值.4!數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的壓縮存儲(chǔ) 第五章 數(shù)組和廣義表廣義表的定義廣義表的存儲(chǔ)結(jié)構(gòu)一、次序約定1以行序?yàn)橹餍?存放規(guī)則：具體實(shí)現(xiàn)時(shí)，按行號(hào)從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，依次類(lèi)推 在BASIC語(yǔ)言、 PASCAL語(yǔ)言、 C/C+語(yǔ)言等高級(jí)語(yǔ)言程序設(shè)計(jì)中，都是按行優(yōu)先順序存放的。61以行序?yàn)橹餍?0a00 1a012a02n-1a0,n-1na10 2n-1a1,n-1m*n

3、-1am-1,n-1第0行第1行72以列序?yàn)橹餍?0a00 1A102A20m-1Am-1,0ma01 2m-1Am-1,-1m*n-1am-1,n-1第0列第1列8二維數(shù)組地址計(jì)算通式：設(shè)一般的二維數(shù)組是Ac1.d1, c2.d23.任一元素的地址計(jì)算（意義：數(shù)組中的任一元素可隨機(jī)存?。簞t列優(yōu)先存儲(chǔ)的通式為：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=單個(gè)元素長(zhǎng)度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長(zhǎng)度aij本行前面的元素個(gè)數(shù)已知三要素開(kāi)始結(jié)點(diǎn)的存放地址（即基地址）維

4、數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L9例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 請(qǐng)問(wèn)按列存儲(chǔ)的公式相同嗎？答：盡管是方陣，但公式仍不同。應(yīng)為： Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 例1軟考題：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的占 個(gè)字節(jié)。 288答： Volu

5、me=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=28810例3 ：考研題 ：設(shè)數(shù)組a160, 170的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58的存儲(chǔ)地址為 。根據(jù)列優(yōu)先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：請(qǐng)注意審題！想一想：若數(shù)組是a059, 069，結(jié)果是否仍為8950？895011N維數(shù)組任一元素的地址計(jì)算Loc(j1,j2,jn)=LOC(0,0,0)其中Cn=L, Ci-1=biCi， 1in每個(gè)元素長(zhǎng)

6、度數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長(zhǎng)度與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出低維優(yōu)先的地址計(jì)算公式：三維數(shù)組且列優(yōu)先時(shí)的元素地址要會(huì)計(jì)算！12例4：【考研資格考試】假設(shè)有三維數(shù)組A798，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，元素A536的第一個(gè)字節(jié)地址為多少？答： 元素A536的第1個(gè)字節(jié)地址 1000 +（5*9*8+3*8+6)*6=3448 只要計(jì)算出任一數(shù)組元素的地址，就能對(duì)其輕松地進(jìn)行讀寫(xiě)操作！計(jì)算地址的意義：13二、N維數(shù)組的順序存儲(chǔ)表示#define MAX_ARRAY_DIM 8 /假設(shè)最大維數(shù)為8 typed

7、ef struct ElemType *base; /數(shù)組元素基址 int dim; /數(shù)組維數(shù) int *bound; /數(shù)組各維長(zhǎng)度信息保存區(qū)基址 int *constants ; /數(shù)組映像函數(shù)常量的基址 Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說(shuō)明（有5個(gè)）（請(qǐng)閱讀教材P93-95）14!數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的壓縮存儲(chǔ) 第五章 數(shù)組和廣義表廣義表的定義廣義表的存儲(chǔ)結(jié)構(gòu)一、對(duì)稱(chēng)矩陣壓縮對(duì)稱(chēng)矩陣定義：若一個(gè)n階方陣A中元素滿足下列條件：aij=aji 其中 0 i, jn-1 ， 則稱(chēng)A為對(duì)稱(chēng)矩陣。1 12 9 0 12 0 5 11 9 5 7 32 0 11 32

8、4 A=壓縮存儲(chǔ)原則：對(duì)稱(chēng)的兩個(gè)元素可以共用一個(gè)存儲(chǔ)單元，只需存放主對(duì)角線及主對(duì)角線以下的元素，這樣僅需 n(n+1)/2個(gè)存貯單元，將近節(jié)約一半存貯單元。S012345678911209570113241 12 9 0 12 0 5 11 9 5 7 32 0 11 32 4 A=S與A的對(duì)應(yīng)關(guān)系如下：二、下（上）三角矩陣壓縮下（上）三角稱(chēng)矩陣定義：矩陣下（上）三角部分元素是隨機(jī)的，而上（下）三角部分元素全部相同（為某常數(shù)C）或全為0。1 0 0 0 12 0 0 09 5 7 0 0 11 32 4 A=壓縮存儲(chǔ)原則：下三角矩陣的壓縮存放與對(duì)稱(chēng)矩陣存放類(lèi)似，但必須多一個(gè)存儲(chǔ)單元存放上三角部

9、分元素，使用的存儲(chǔ)單元數(shù)目為n(n+1)/2+1。S11209570113240123456789101 0 0 0 12 0 0 09 5 7 0 0 11 32 4 A=0S與A的對(duì)應(yīng)關(guān)系如下：思考一下：上三角矩陣A壓縮到S后的對(duì)應(yīng)關(guān)系如何？三、對(duì)角矩陣壓縮對(duì)角矩陣定義：若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱(chēng)為對(duì)角矩陣。常見(jiàn)的有三對(duì)角矩陣、五對(duì)角矩陣、七對(duì)角矩陣等。1 11 0 0 0 12 0 5 0 00 5 7 6 0 0 0 32 4 2 A=0 0 0 4 3 壓縮存儲(chǔ)原則：在一個(gè)nn的三對(duì)角矩陣中，只有n+n-1+n-1個(gè)非零元素，故只

10、需3n-2個(gè)存儲(chǔ)單元即可，零元已不占用存儲(chǔ)單元。故可將nn三對(duì)角矩陣A壓縮存放到只有3n-2個(gè)存儲(chǔ)單元的s向量中。四、稀疏矩陣壓縮存儲(chǔ)稀疏矩陣定義：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 0 0 18 0 0 0 0 0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 0 0 18 0 0 0 0 ije123456121213931-3351443245218壓縮存儲(chǔ)原則：只存儲(chǔ)非零元。需要一個(gè)一維數(shù)組存放每一個(gè)非零元素，并記錄每個(gè)非零元素的行號(hào)、列標(biāo)、

11、元素值。（也要求按行（列）優(yōu)先存儲(chǔ)）0 12 9 0 0 0 00 0 0 0 0 0 0 -3 0 0 0 14 0 00 0 24 0 0 0 0 0 18 0 0 0 0 00 0 0 0 0 0 0問(wèn)題：下面這個(gè)矩陣與上頁(yè)的矩陣是否一樣，壓縮存儲(chǔ)后得到的一維組數(shù)值是否一樣？所以，壓縮后除了存儲(chǔ)非零元素外，還需要存儲(chǔ)原矩陣的行號(hào)和列標(biāo)。#define MAXSIZE 100typedef struct int i, j; Elemtype e; Triple;類(lèi)型定義：Typedef struct Triple dataMAXESIZE; /存放非零元素 int mu,nu; /存放對(duì)應(yīng)

12、矩陣的行號(hào)、列標(biāo) int tu; /記錄非零元素的個(gè)數(shù)TSMatrix;舉例：稀疏矩陣的轉(zhuǎn)置運(yùn)算0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 00 0 3 0 012 0 0 0 18 9 0 0 24 0 0 0 0 0 00 0 14 0 0 0 0 0 0 0 13-32112251831934245314已知三元組表M.data求三元組表T.data轉(zhuǎn)置MT目的：121213931-3351443245218Tij=Mji？28若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的

13、轉(zhuǎn)置運(yùn)算，這種說(shuō)法正確嗎？ 提問(wèn)：121213931-3351443245218211231913-353143424251813-32112251831934245314ij互換答：肯定不正確！i j e i j e i j e （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）。轉(zhuǎn)置運(yùn)算的主要三個(gè)操作：有兩種實(shí)現(xiàn)轉(zhuǎn)置的方法壓縮轉(zhuǎn)置快速(壓縮)轉(zhuǎn)置T.data.i=M.data.j;T.data.j=M.data.i;T

14、.data.e=M.data.e;T.mu=M.nu;T.nu=M.mu;已知三元組表M.data求三元組表T.data121213931-3351443245218i j e q1234 p1234.方法1：壓縮轉(zhuǎn)置思路：反復(fù)掃描M表（記為M.data）中的列序（j=1n），依次進(jìn)行轉(zhuǎn)置存儲(chǔ)到T表中。 1 3 -3 2 1 12 2 5 18 3 1 9 5 3 14 3 4 24i j e q=1; for(col=1;col=M.nu;col+) for(p=1;p=M.tu;p+) if(M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.d

15、atap.i; T.dataq.e=M.datap.e; q+; 算法中主要程序段：方法2 快速轉(zhuǎn)置思路：依次把M.data中的元素直接送入T.data的恰當(dāng)位置上（即三元組的p指針不回溯）。關(guān)鍵：怎樣尋找T.data的“恰當(dāng)”位置？求三元組表T.data121213931-3351443245218i j e q1234 p1234. 3 1 9 2 1 12 1 3 -3 5 3 14 3 4 24 2 5 18已知三元組表M.datai j e 如果能預(yù)知M矩陣每一列(即T的每一行)的非零元素個(gè)數(shù)，就能很快得知每一列的第一個(gè)非零元素在T.data中的位置，則掃描M.data時(shí)便可以將每個(gè)

16、元素準(zhǔn)確定位解決思路：1）先確定M中每一列第一個(gè)非零元在T中位置 實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組 cpotcol:指示M中第col列第一個(gè)非零元在T 中的位置 numcol:表示矩陣M中第col列中非零元個(gè)數(shù)設(shè)計(jì)步驟：col123456numcol122010cpotcol1121213931-3351443245218i j e 已知三元組表M.data顯然有：cpot1=1;cpotcol=cpotcol-1+numcol-1;24667 /求numcol: for(p=1;p=M.tu;p+) col=M.datap.j; numcol+; /求cpotcol cpot1=1; for(col=2;c

17、ol=M.nu;col+) cpotcol=cpotcol-1+numcol-1; 部分程序段：2）再到M中從頭到尾掃描每一個(gè)元素，按其列值和cpotcol的值存放在T中；設(shè)計(jì)步驟：求三元組表T.data121213931-3351443245218i j e q1234 p1234. 3 1 9 2 1 12 1 3 -3 5 3 14已知三元組表M.datai j e col123456cpotcol12466756求三元組表T.data121213931-3351443245218i j e q1234 p1234. 3 1 9 2 1 12 1 3 -3 5 3 14已知三元組表M.d

18、atai j e col123456cpotcol23567756設(shè)計(jì)中一個(gè)技巧：每存入一個(gè)列為col的元素，其cpotcol值+1，使其不再固定指向本列第一個(gè)非零元素，而是預(yù)備給同列的下一非零元素定位之用 3 4 24 2 5 18 1 2 4 6 6 7部分程序段： for(p=1;p=M.tu;p+) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; cpotcol+; 求該元素在T中的位置元素轉(zhuǎn)置技巧應(yīng)用1. 與常規(guī)算法相比，附加了生成輔助向量表的工作。增開(kāi)了

19、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)2. 從時(shí)間上，此算法用了4個(gè)并列的單循環(huán)，而且其中前3個(gè)單循環(huán)都是用來(lái)產(chǎn)生輔助向量表的。 該算法的時(shí)間復(fù)雜度nu+tu+nu+tu=O(nu+tu）討論：最?lèi)毫忧闆r是矩陣中全為非零元素，此時(shí)tu=nu*mu而此時(shí)的時(shí)間復(fù)雜度也只是O(mu*nu)，并未超過(guò)傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。小結(jié)：增設(shè)輔助向量，犧牲空間效率換取時(shí)間效率?？焖俎D(zhuǎn)置算法的效率分析：!數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的壓縮存儲(chǔ) 第五章 數(shù)組和廣義表廣義表的定義廣義表的存儲(chǔ)結(jié)構(gòu)廣義表是線性表的推

20、廣，也稱(chēng)為列表（lists）記為： LS = ( a1 , a2 , ， an ) 廣義表名 表頭(Head） 表尾 (Tail)1、定義：用小寫(xiě)字母表示原子類(lèi)型，用大寫(xiě)字母表示列表。第一個(gè)元素是表頭，而其余元素組成的表稱(chēng)為表尾；n是表長(zhǎng)在廣義表中約定：特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表！422、特點(diǎn)：有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼表中元素個(gè)數(shù)表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享討論：廣義表與線性表的區(qū)別和聯(lián)系？ 廣義表中元素既可以是原子類(lèi)型，也可以是列表；當(dāng)每個(gè)元素都為原子且類(lèi)型相同時(shí)，就是線性表。43E

21、=(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)，共享表443.兩種重要的基本操作：GetHead ( L) 取表頭(可能是原子或列表) 初始條件：廣義表L存在。 操作結(jié)果：取廣義表L的頭。 GetTail ( L )

22、 取表尾(一定是列表) 初始條件：廣義表L存在。 操作結(jié)果：取廣義表L的尾。451. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;例：求下列廣義表操作的結(jié)果（嚴(yán)題集5.10）(k, p, h)（b）(a,b)5. GetTail【（e）】 ; 6. GetHead 【 ( ( ) )】 .7. GetTail【 ( ( ) ) 】 .(a,b)( )( )(c,d)( )46!數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的壓縮存儲(chǔ) 第五章 數(shù)組和廣義表廣義表的定義廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列