第5講 數(shù)組和廣義表.ppt

1、Chapter 5Array /數(shù)組存放空間 int ArraySize; /當(dāng)前長度 void getArray ( ); /建立數(shù)組空間 public: Array( int Size=DefaultSize ); Array( const Array,Array( ) delete elements; Array /擴(kuò)充數(shù)組 ,一維數(shù)組公共操作的實(shí)現(xiàn),template void Array : getArray ( ) /私有函數(shù)：創(chuàng)建數(shù)組存儲空間 elements = new TypeArraySize; ,template Array : Array ( int sz ) Array

2、Size = sz; getArray ( ); ,template Array:Array(Array ,template Array:Array(Array ,template Type ,template void Array : Resize ( int sz ) if ( sz = 0 /按新的大小確定傳送元素個數(shù),Type *srcptr=elements; Type *destptr=newarray; while (n-)*destptr+=*srcptr+; delete elements; elements = newarray; ArraySize = sz; ,多維數(shù)組

3、,多維數(shù)組是一維數(shù)組的推廣 多維數(shù)組是一種非線性結(jié)構(gòu)。其特點(diǎn)是每一個數(shù)據(jù)元素可以有多個直接前驅(qū)和多個直接后繼。 數(shù)組元素的下標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡單。,數(shù)組元素的遍歷 1)以行序?yàn)橹餍?按行排列): 先排最右的下標(biāo),依次向左,最后 排最左的下標(biāo) 2)以列序?yàn)橹餍?按列排列): 先排最左的下標(biāo),依次向右,最 后排最右的下標(biāo),例如：,稱為基地址或基址。,以“行序?yàn)橹餍颉钡拇鎯τ诚?二維數(shù)組A中任一元素ai,j 的存儲位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0

4、,2,a1,0,a1,1,a1,2,L,L,對于一般意義二維數(shù)組Ac1:d1,c2:d2，設(shè)每個元素占用1個存儲單元，LOC(c1,c2)是第一個元素ac1c2的存儲位置,則按行存放時，aij的存儲位置為： LOC(i,j)=LOC(c1,c2)+(d2-c2+1)(i-c1)+(j-c2) 則列行存放時，aij的存儲位置為： LOC(i,j)=LOC(c1,c2)+(d1-c1+1)(j-c2)+(i-c1),推廣到一般情況，可得到 n 維數(shù)組數(shù)據(jù)元素存儲位置的映象關(guān)系,稱為 n 維數(shù)組的映象函數(shù)。數(shù)組元素 的存儲位置是其下標(biāo)的線性函數(shù)。,其中 cn = L，ci-1 = bi ci , 1

5、 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,對于n維數(shù)組的一般情況Ac1:d1,c2:d2,cn:dn，設(shè)每個元素占用個存儲單元，LOC(c1,c2, cn)是第一個元素ac1c2cn的存儲位置,則按行存放時，aj1j2jn的存儲位置如下： LOC(j1j2jn)=LOC(c1,c2, ,cn)+(j1-c1)(d2-c2+1)(dn-cn+1) +( j2-c2)(d3-c3+1)(dn-cn+1) +( jn-1-c n-1)(dn-cn+1) +( jn-c n)l,則列行存放時，aj1j2jn的存儲位置如下： LOC(

6、j1j2jn)=LOC(c1,c2, , cn)+(j1-c1) +(d1-c1+1) ( j2-c2) +(d1-c1+1)(dn-2-cn-2+1) (jn-1-cn-1) +(d1-c1+1)(dn-1-cn-1+1) (jn-cn)l,稀疏矩陣(Sparse Matrix),非零元素個數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素個數(shù),假設(shè) m 行 n 列的矩陣含 t 個非零元素，則稱 為稀疏因子。 通常認(rèn)為 0.05 的矩陣為稀疏矩陣。,以常規(guī)方法，即以二維數(shù)組表示 高階的稀疏矩陣時產(chǎn)生的問題:,1) 零值元素占了很大空間;,2) 計(jì)算中進(jìn)行了很多和零值的運(yùn)算， 遇除法，還需判別除數(shù)是否為零。,1) 盡可能少存

7、或不存零值元素；,解決問題的原則,2) 盡可能減少沒有實(shí)際意義的運(yùn)算；,3) 操作方便。 即： 1. 能盡可能快地找到與下標(biāo)值 (i，j)對應(yīng)的元素， 2. 能盡可能快地找到同一行或 同一列的非零值元。,1) 特殊矩陣 非零元在矩陣中的分布有一定規(guī)則 例如: 三角矩陣 對角矩陣,2) 隨機(jī)稀疏矩陣 非零元在矩陣中隨機(jī)出現(xiàn),有兩類稀疏矩陣：,特殊矩陣 非零元在矩陣中的分布有一定規(guī)則 例如: 對稱矩陣 三角矩陣 三對角矩陣,n階對稱矩陣 aij=aji 1=j j(j-1)/2+i-1 當(dāng)ij,K=,矩陣的壓縮存儲 對稱矩陣,三角矩陣共計(jì)元素個數(shù)為： n(n+1)/2,三角矩陣,對角矩陣,Loc(

8、aij)=Loc(a11)+2(i-1)+(j-1) |i-j|1,隨機(jī)稀疏矩陣的順序壓縮存儲,三元組表示法,隨機(jī)稀疏矩陣的鏈?zhǔn)綁嚎s存儲,十字鏈表,隨機(jī)稀疏矩陣 非零元在矩陣中隨機(jī)出現(xiàn),十字鏈表,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,11,2,1,Typedef struct OLNode int i, j; ElemType e; struct OLNode *right, *right; Typedef struct OLink * rhead, *lhead; int mu, nu,tu; ,#define MAXSIZE 12500

9、 typedef struct int i, j; /該非零元的行下標(biāo)和列下標(biāo) ElemType e; / 該非零元的值 Triple; / 三元組類型,三元組順序表（C語言版）,typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型,已知稀疏矩陣,三元組順序表示例,三元組表示為,稀疏矩陣三元組表的抽象數(shù)據(jù)類型 (C+版) const int MaxTerms=1000; template class SparseMatrix; template class Trituple friend class S

10、parseMatrix private: int row, col; /非零元素行號/列號 Type value; /非零元素的值 ,templateclass SparseMatrix int Rows,Cols,Terms;/行/列/非零元素數(shù) Trituple smArrayMaxTerms; public: /三元組表 SparseMatrix (int Row, int Col,int Term); SparseMatrix /轉(zhuǎn)置,SparseMatrix /相乘 ,稀疏矩陣的轉(zhuǎn)置,用常規(guī)的二維數(shù)組表示時的算法,其時間復(fù)雜度為: O(munu),for (col=1; col=nu

11、; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,一個 mn 的矩陣 A，它的轉(zhuǎn)置矩陣 B 是一個 nm 的矩陣，且 Aij = Bji。即矩陣 A 的行成為矩陣 B 的列，矩陣 A 的列成為矩陣 B 的行。 在稀疏矩陣的三元組表中，非零矩陣元素按行存放。當(dāng)行號相同時，按列號遞增的順序存放。 稀疏矩陣的轉(zhuǎn)置運(yùn)算要轉(zhuǎn)化為對應(yīng)三元組表的轉(zhuǎn)置。,稀疏矩陣,轉(zhuǎn)置矩陣,用三元組表表示的稀疏矩陣及其轉(zhuǎn)置,稀疏矩陣轉(zhuǎn)置算法思想,設(shè)矩陣列數(shù)為 Cols，對矩陣三元組表掃描Cols 次。第 k 次檢測列號為 k 的項(xiàng)。 第 k 次掃描找尋所有列號為 k 的

12、項(xiàng)，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。,template SparseMatrix,for ( int k = 0; k a.Cols; k+ ) for ( int i = 0; i a.Terms; i+ ) if ( a.smArrayi.col = k ) b.smArrayCurrentP.row = a.smArrayi.col; b.smArrayCurrentP.col = a.smArrayi.row; b.smArrayCurrentP.value= a.smArrayi.value;,CurrentP+; return b; ,時間復(fù)雜度O(nu*tu

13、),按a.data中三元組的次序進(jìn)行轉(zhuǎn)換,如果能預(yù)先確定矩陣M中的每一列（即T中 每一行）的第一個非零元在b.data中應(yīng)有置， 則在對a.data中的三元組依次轉(zhuǎn)置時，便可直接放到b.data中恰當(dāng)?shù)奈恢蒙先ァ?（先求M中每一列非零元素的個數(shù)。）,首先應(yīng)該確定每一列的第一個非零元在三元組中的位置。,cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;,Status FastTransposeSMatrix(TSMatrix M, TSMatrix / FastTransposeSMatrix,轉(zhuǎn)置矩陣元素

14、,Col = M.datap.j; / p=1 col=2; p=2 col=5 q = cpotcol; / p=1 q=cpot2=2; p=2 q=cpot5=5 T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol,分析算法FastTransposeSMatrix的時間復(fù)雜度：,時間復(fù)雜度為: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p

15、=1; p=M.tu; +p) ,Section 2 General List,1.廣義表的概念 n(0)個表元素組成的 有限序列,記作 LS = (a0, a1, a2, , an-1) LS是表名,ai是表元素,它可以是表(稱為 子表),可以是數(shù)據(jù)元素(稱為原子) 2.n為表的長度。n=0的廣義表為空表 3.n0時,表的第一個表元素稱為廣義表 的表頭(head),除此之外,其它表元素組 成的表稱為廣義表的表尾(tail),廣義表的 抽象數(shù)據(jù)類型定義,ADT Glist 數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個數(shù)據(jù)對象

16、 數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist,基本操作:,廣 義 表 的基本操作,結(jié)構(gòu)的創(chuàng)建和銷毀 InitGList(,狀態(tài)函數(shù) GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);,插入和刪除操作 InsertFirst_GL(,遍歷 Traverse_GL(L, Visit();,廣義表是遞歸定義的線性結(jié)構(gòu)，,LS = ( 1, 2, , n ) 其中：i 或?yàn)樵?或?yàn)閺V義表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D

17、, F) B = (a, B) = (a, (a, (a, , ) ) ),廣義表是一個多層次的線性結(jié)構(gòu),例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,廣義表 LS = ( 1, 2, , n ) 的結(jié)構(gòu)特點(diǎn),1)廣義表中的數(shù)據(jù)元素有相對次序,廣義表的長度定義為最外層包含元素 個數(shù),廣義表的深度定義為所含括弧的重數(shù) “原子”的深度為 0 “空表”的深度為 1,4)廣義表可以是一個遞歸的表,5)任何一個非空廣義表 LS = ( 1, 2, , n) 均可分解為 表頭 Head(LS) = 1 和 表尾 Tail(L

18、S) = ( 2, , n) 兩部分,例如: D=(E, F)=(a,(b, c),F),Head(D)=E Tail(D)=(F),Head(E)=a Tail(E)=(b, c),Head(b, c)=(b, c) Tail(b, c)=( ),Head(b, c)=b Tail(b, c)=(c),Head(c)=c Tail(c)=( ),5.5 廣義表的表示方法,通常采用頭、尾指針的鏈表結(jié)構(gòu),表結(jié)點(diǎn): 原子結(jié)點(diǎn)：,tag=1 hp tp,tag=0 data,廣義表的頭尾鏈表存儲表示,Typedef enumATOM, LIST ElemTag; Typedef struct GLN

19、ode ElemTag tag; union AtomType atom; struct struct GLNode *hp, *tpptr; ; *glist,若子表為原子，則為,空表 ls=NIL,非空表,1,指向子表1 的指針,tag=0 data,否則，依次類推。,1,指向子表2 的指針,1,指向子表n 的指針,ls,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),ls,第二種鏈表表示方法,表結(jié)點(diǎn): 原子結(jié)點(diǎn)：,tag=1 hp tp,tag=0 atom tp,5.6 廣義表操作的遞歸函數(shù),遞歸函數(shù) 一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它

20、必須滿足以下兩個條件：,1)在每一次調(diào)用自己時，必須是(在某 種意義上)更接近于解;,2)必須有一個終止處理或計(jì)算的準(zhǔn)則。,廣義表從結(jié)構(gòu)上可以分解成,廣義表 = 表頭 + 表尾,或者,廣義表 = 子表1 + 子表2 + + 子表n,因此常利用分治法求解之。 算法設(shè)計(jì)中的關(guān)鍵問題是，如何將 l 個子問題的解組合成原問題的解。,廣義表的頭尾鏈表存儲表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; / 標(biāo)志域 union AtomType atom; / 原子結(jié)

21、點(diǎn)的數(shù)據(jù)域 struct struct GLNode *hp, *tp; ptr; ; *GList,tag=1,hp tp,ptr,表結(jié)點(diǎn),例一 求廣義表的深度,例二 復(fù)制廣義表,例三 創(chuàng)建廣義表的存儲結(jié)構(gòu),廣義表的深度=Max 子表的深度 +1,例一 求廣義表的深度,可以直接求解的兩種簡單情況為： 空表的深度 = 1 原子的深度 = 0,將廣義表分解成 n 個子表，分別(遞歸)求得每個子表的深度，,int GlistDepth(Glist L) / 返回指針L所指的廣義表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-

22、ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepth,if (!L) return 1; if (L-tag = ATOM) return 0;,1,1,1,L,for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; ,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,pp-ptr.hp,例二 復(fù)制廣義表,新的廣義表由新的表頭和表尾構(gòu)成。,可以直接求解的兩種簡單情況為： 空表復(fù)制求得的新表

23、自然也是空表; 原子結(jié)點(diǎn)可以直接復(fù)制求得。,將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，,若 ls= NIL 則 newls = NIL 否則 構(gòu)造結(jié)點(diǎn) newls, 由 表頭ls-ptr.hp 復(fù)制得 newhp 由 表尾 ls-ptr.tp 復(fù)制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp,復(fù)制求廣義表的算法描述如下:,Status CopyGList(Glist / CopyGList,分別復(fù)制表頭和表尾,CopyGList(T-ptr.hp, L-ptr.hp); / 復(fù)制求得表頭T-ptr.hp的一

24、個副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); / 復(fù)制求得表尾T-ptr.tp 的一個副本L-ptr.tp,語句 CopyGList(T-ptr.hp, L-ptr.hp); 等價于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp;,例三 創(chuàng)建廣義表的存儲結(jié)構(gòu),對應(yīng)廣義表的不同定義方法相應(yīng)地有不同的創(chuàng)建存儲結(jié)構(gòu)的算法。,假設(shè)以字符串 S = (1, 2, , n ) 的形式定義廣義表 L，建立相應(yīng)的存儲結(jié)構(gòu)。,由于S中的每個子串i定義 L 的一個子表，從而產(chǎn)生 n 個子問題，即分別由這 n個子串 (遞歸)建立 n

25、 個子表，再組合成一個廣義表。,可以直接求解的兩種簡單情況為： 由串( )建立的廣義表是空表； 由單字符建立的子表只是一個原子結(jié)點(diǎn)。,如何由子表組合成一個廣義表？,首先分析廣義表和子表在存儲結(jié)構(gòu)中的關(guān)系。,先看第一個子表和廣義表的關(guān)系:,1,L,指向廣義表 的頭指針,指向第一個 子表的頭指針,再看相鄰兩個子表之間的關(guān)系:,1,1,指向第i+1個 子表的頭指針,指向第i個 子表的頭指針,可見，兩者之間通過表結(jié)點(diǎn)相鏈接。,若 S = ( ) 則 L = NIL； 否則，構(gòu)造第一個表結(jié)點(diǎn) *L， 并從串S中分解出第一個子串1，對應(yīng)創(chuàng)建第一個子廣義表 L-ptr.hp； 若剩余串非空，則構(gòu)造第二個表結(jié)

26、點(diǎn) L-ptr.tp，并從串S中分解出第二個子串 2，對應(yīng)創(chuàng)建第二個子廣義表 ； 依次類推，直至剩余串為空串止。,void CreateGList(Glist /脫去串S的外層括弧 / else ,由sub中所含n個子串建立n個子表;,do sever(sub, hsub); / 分離出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一個子表的表結(jié)點(diǎn)*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub); p-ptr.tp = NULL; / 表尾為空表,創(chuàng)建由串

27、hsub定義的廣義表p-ptr.hp;,if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 創(chuàng)建單原子結(jié)點(diǎn) else CreateGList(p-ptr.hp, hsub); /遞歸建廣義表,后置遞歸的設(shè)計(jì)思想為:,遞歸的終結(jié)狀態(tài)是，當(dāng)前的問題可以直接求解，對原問題而言，則是已走到了求解的最后一步。,鏈表是可以如此求解的一個典型例子。 例如：編寫“刪除單鏈表中所有值為x 的數(shù)據(jù)元素”的算法。,1) 單鏈表是一種順序結(jié)構(gòu)，必須從第一個結(jié)點(diǎn)起，逐

28、個檢查每個結(jié)點(diǎn)的數(shù)據(jù)元素；,分析:,2) 從另一角度看，鏈表又是一個遞歸結(jié)構(gòu)，若 L 是線性鏈表 (a1, a2, , an) 的頭指針，則 L-next是線性鏈表 (a2, , an)的頭指針。,a1,a2,a3,an,L,例如:,a1,a2,a3,an,L,a1,a2,a3,an,L,已知下列鏈表,1) “a1=x”，則 L 仍為刪除 x 后的鏈表頭指針,2) “a1x”，則余下問題是考慮以 L-next 為頭指針的鏈表,a1,L-next,L-next=p-next,p=L-next,void delete(LinkList / delete,刪除廣義表中所有元素為x的原子結(jié)點(diǎn),分析:

29、比較廣義表和線性表的結(jié)構(gòu)特點(diǎn)：,相似處：都是鏈表結(jié)構(gòu)。,不同處：1)廣義表的數(shù)據(jù)元素可能還是個 廣義表； 2)刪除時，不僅要刪除原子結(jié)點(diǎn)， 還需要刪除相應(yīng)的表結(jié)點(diǎn)。,void Delete_GL(Glist / 考察第一個子表 if (head-tag = Atom) L = L-ptr.tp; / 修改指針 free(head); / 釋放原子結(jié)點(diǎn) free(p); / 釋放表結(jié)點(diǎn) Delete_GL(L, x); / 遞歸處理剩余表項(xiàng),1,L,0 x,1,p,L,head,if (head-tag = LIST) /該項(xiàng)為廣義表 Delete_GL(head, x); Delete_GL(

30、L-ptr.tp, x); / 遞歸處理剩余表項(xiàng),1,L,0 a,1,1,head,L-ptr.tp,回溯法是一種“窮舉”方法。其基本思想為：,假設(shè)問題的解為 n 元組 (x1, x2, , xn)， 其中 xi 取值于集合 Si。 n 元組的子組 (x1, x2, , xi) (in) 稱為部分解，應(yīng)滿足一定的約束條件。 對于已求得的部分解 (x1, x2, , xi) ， 若在添加 xi+1Si+1 之后仍然滿足約束條件， 則得到一個新的部分解 (x1, x2, , xi+1) , 之后繼續(xù)添加 xi+2Si+2 并檢查之。,例一、皇后問題求解,設(shè)四皇后問題的解為 (x1, x2, x3,

31、 x4), 其中： xi (i=1,2,3,4) Si=1, 2, 3, 4 約束條件為：其中任意兩個xi 和xj不能位于棋盤的同行、同列及同對角線。,按回溯法的定義，皇后問題求解過程為： 解的初始值為空；首先添加 x1=1, 之后添加滿足條件的 x2=3，由于對所有的 x31,2, 3, 4都不能找到滿足約束條件的部分解(x1, x2, x3), 則回溯到部分解(x1), 重新添加滿足約束條件的x2=4, 依次類推。,void Trial(int i, int n) / 進(jìn)入本函數(shù)時，在nn棋盤前i-1行已放置了互不攻 / 擊的i-1個棋子?，F(xiàn)從第 i 行起繼續(xù)為后續(xù)棋子選擇 / 滿足約束條

32、件的位置。當(dāng)求得(in)的一個合法布局 / 時，輸出之。 if (in) 輸出棋盤的當(dāng)前布局; else for (j=1; j=n; +j) 在第 i 行第 j 列放置一個棋子; if (當(dāng)前布局合法) Trial(i+1, n); 移去第 i 行第 j 列的棋子; / trial,回溯法求解的算法一般形式：,void B(int i, int n) / 假設(shè)已求得滿足約束條件的部分解(x1,., xi-1)，本函 /數(shù)從 xi 起繼續(xù)搜索，直到求得整個解(x1, x2, xn)。 if (in) else while ( ! Empty(Si) 從 Si 中取 xi 的一個值 viSi; if (x1, x2, , xi) 滿足約束條件 B( i+1, n); / 繼續(xù)求下一個部分解 從 Si 中刪除值 vi; / B,綜合幾點(diǎn)： 1. 對于含有遞歸特性的問題，最好設(shè)計(jì)遞歸形式的算法。但也不要單純追求形式，應(yīng)在算法設(shè)計(jì)的分析過程中“就事論事”。例如，在利用分割求解設(shè)計(jì)算法時，子問題和原問題的性質(zhì)相同；或者，問題的當(dāng)前一步解決之