廣義表(2),圖(1)-1

1、2022-1-315.4 廣義表的類型定義廣義表的類型定義5.5 廣義表的表示方法廣義表的表示方法5.6 廣義表操作應(yīng)用舉例廣義表操作應(yīng)用舉例第五章 數(shù)組和廣義表2022-1-325.5 廣義表的表示方法廣義表的表示方法采用鏈表存儲(chǔ)結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn):原子結(jié)點(diǎn)：原子結(jié)點(diǎn)：tag=0 datatag=1 hp tp2022-1-33廣義表存儲(chǔ)結(jié)構(gòu)定義廣義表存儲(chǔ)結(jié)構(gòu)定義Typedef enum ATOM, LIST ElemTag;Typedef struct ElemTag tag; / 區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn) Union /原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 AtomType atom; /原子結(jié)點(diǎn)的值域

2、 Struct struct GLNode *hp, *tp; ptr; / ptr是表結(jié)點(diǎn)的指針域， /ptr.hp和和ptr.tp分別指向表頭和表尾 ;Glist;tag=0 datatag=1 hp tpGlist L；L.tag=ATOM;L.atom=原子值；原子值；Glist L；L.tag=LIST;L.ptr.hp= 表頭指針；表頭指針；L.ptr.tp = 表尾指針；表尾指針；2022-1-341 1。 表頭、表尾分析法表頭、表尾分析法構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法: : 1 1。表頭表尾分析法。表頭表尾分析法2 2。子表分析法。子表分析法若表頭為原子，

3、則為若表頭為原子，則為空表空表 ls = NULL非空表非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否則，依次類推。否則，依次類推。2022-1-35例：例：L = ( a, ( x, y ), (x) 表頭表尾分析法表頭表尾分析法 1 L 1 1 (x)(x,y),(x) 1 (x,y) 1 (x) 1 (y)0 x x0 a a0 y y(x) 1 0 x x2022-1-36 1 1 1 ls 2 2。子表分析法。子表分析法若子表為原子，則為若子表為原子，則為空表空表 ls=NULL非空表非空表指向子表1 的指針tag=0 data否則，依次類推。否則，依次類

4、推。指向子表2 的指針指向子表n 的指針2022-1-37例：例：LS=( a, (x,y), (x) ) 子表分析法子表分析法ls1111 x a 0 a x 0 x y 0 y x 0 x(x) (x, y)a11xy1(x) 2022-1-38例：用子表分析法求廣義表的字符串表達(dá)式例：用子表分析法求廣義表的字符串表達(dá)式L111111111110 a0 b110 a0 b (b) b a ( a, (b) ) ( ) b a ( a, b, ( ) ) ( a, b, ( ), ( ) ,( a, (b) ) ( ) L= ( a, b, ( ), ( ) ,( a, (b) ) , (

5、) ) ( ) ( ) ( ) 2022-1-39例例:L L= ( a, L ) = ( a, (a, (a, ) 10 a1aL2022-1-3105.4 廣義表的類型定義廣義表的類型定義5.5 廣義表的表示方法廣義表的表示方法5.6 廣義表操作應(yīng)用舉例廣義表操作應(yīng)用舉例第五章 數(shù)組和廣義表2022-1-311例一例一 求廣義表的深度求廣義表的深度例二例二 復(fù)制廣義表復(fù)制廣義表例三例三 創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)2022-1-312廣義表的深度廣義表的深度= =Max 子表的深度子表的深度 +1例一例一 求廣義表的深度求廣義表的深度可以直接求解的兩種簡(jiǎn)單情況為: 空表的深度空

6、表的深度 = 1 原子的深度原子的深度 = 0 將廣義表分解成 n 個(gè)子表，分別(遞歸)求得每個(gè)子表的深度,2022-1-313例：例：LS=( a, (x,y), (x) ) 子表分析法子表分析法L1111 x a 0 a x 0 x y 0 y x 0 x(x) (x, y)a11xy1(x) 2+100010122022-1-314 int GlistDepth(Glist L) / 返回指針L所指的廣義表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep;

7、 return max + 1; / GlistDepthif (!L) return 1; /空表if (L-tag = ATOM) return 0; 2022-1-315例二例二 復(fù)制廣義表復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成。新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡(jiǎn)單情況為: 空表復(fù)制求得的新表還是空表空表復(fù)制求得的新表還是空表; 原子結(jié)點(diǎn)可以直接復(fù)制求得。原子結(jié)點(diǎn)可以直接復(fù)制求得。 將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，2022-1-316若若 ls= NULL 則則 newls = NULL否則否則 構(gòu)造結(jié)點(diǎn)構(gòu)造結(jié)點(diǎn) newls, 由由

8、 表頭表頭ls-ptr.hp 復(fù)制得復(fù)制得 newhp 由由 表尾表尾 ls-ptr.tp 復(fù)制得復(fù)制得 newtp 并使并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp復(fù)制廣義表的算法描述如下復(fù)制廣義表的算法描述如下: :1 ptr.hp ptr.tp2022-1-317Status CopyGList(Glist &T, Glist L) if (!L) T = NULL; / 復(fù)制空表 else if ( !(T = new GLNode) ) exit(OVERFLOW); / 建表結(jié)點(diǎn) T-tag = L-tag; if (L-tag

9、 = ATOM) T-atom = L-atom; / 復(fù)制單原子結(jié)點(diǎn) else CopyGList(newhp, L-ptr.hp); / 復(fù)制求得表頭 CopyGList(newtp, L-ptr.tp) ; / 復(fù)制求得表尾 T-ptr.hp = newhp; T-ptr.tp = newtp; / else return OK; / CopyGList2022-1-318 假設(shè)以字符串 S = (1, 2, , n ) 的形式定義廣義表 L，建立相應(yīng)的存儲(chǔ)結(jié)構(gòu)。 采用表頭表尾構(gòu)造法，用S中的第一個(gè)子串 1定義 L 的表頭表頭，其余子串(2, , n )定義L 的一個(gè)表尾，表尾，從而將問

10、題分解成更小規(guī)模的子問題，再組合組合成一個(gè)廣義表。 可以直接求解的兩種簡(jiǎn)單情況為:由串由串 ( ) 建立的廣義表是建立的廣義表是空表空表;由單字符建立的子表只是一個(gè)原子結(jié)點(diǎn)。由單字符建立的子表只是一個(gè)原子結(jié)點(diǎn)。例三例三 創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)2022-1-319如何將一個(gè)由字符串形式定義的廣義表如何將一個(gè)由字符串形式定義的廣義表分解成表頭表尾？分解成表頭表尾？S = ( a, ( x, y ), ( ( x ) ) )1. 脫去串脫去串 S 的外層括弧的外層括弧 sub=SubString(S,2,StrLength(S)-1); 2. 分離出子表串分離出子表串 sever(

11、sub, hsub); hsub=a; tsub= ( x, y ) , ( ( x ) ) sub= a, ( x, y ), ( ( x ) ) 2022-1-320例：例：L = ( a, ( x, y ), (x) 去掉括號(hào)去掉括號(hào)，分離表頭和表尾分離表頭和表尾 1 L 1 (x) 1 (x,y),(x) 1 (x,y) 1 (x) 1 y0 x x0 a a0 y y(x) 1 0 x x2022-1-3211。若。若 S = ( ) 則則 L = NIL 否則否則 2. 構(gòu)造第一個(gè)廣義表頭結(jié)點(diǎn) L,3. 脫去串 S 的外層括弧6. 若若剩余串空，則L-ptr.tpNULL 否則，構(gòu)

12、造廣義表表尾結(jié)點(diǎn) L-ptr.tp, 轉(zhuǎn)轉(zhuǎn)4對(duì)對(duì)剩余串S繼續(xù)處理。依次類推，直至剩余串為空串止。5. 創(chuàng)建廣義表表頭 L-ptr.hp; 如果1的長度大于1，則遞歸遞歸；否則為原子4. 從串 S 中分解出表頭字符串1, 2022-1-322void CreateGList(Glist &L, String S) if (空串) L = NULL; / 創(chuàng)建空表 else L = new GLNode; / 生成表結(jié)點(diǎn) L-tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); / 脫去串 S 的外層括弧 / else 根據(jù)根據(jù)sub中所含中所

13、含n個(gè)子串建立表頭表尾個(gè)子串建立表頭表尾;2022-1-323do sever(sub, hsub); / 分離出表頭子串hsub=i if (!StrEmpty(sub) p-ptr.tp=new(sizeof(GLNode); / 建立表尾結(jié)點(diǎn)(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub);p-ptr.tp = NULL; / 表尾為空表創(chuàng)建由串創(chuàng)建由串hsub定義的廣義表表頭定義的廣義表表頭p-ptr.hp;2022-1-324if (StrLength(hsub)=1) / 1 1長度等于長度等于1 1，原子，原子 p-ptr.hp=(GLis

14、t)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 創(chuàng)建單原子結(jié)點(diǎn)創(chuàng)建單原子結(jié)點(diǎn)else CreateGList( p-ptr.hp, hsub); /否則，遞歸建廣義表表頭否則，遞歸建廣義表表頭 2022-1-3257.1 圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義7.2 圖的存儲(chǔ)表示圖的存儲(chǔ)表示7.3 圖的遍歷圖的遍歷7.4 最小生成樹最小生成樹7.5 重（雙）連通圖和關(guān)節(jié)點(diǎn)重（雙）連通圖和關(guān)節(jié)點(diǎn)7.6 兩點(diǎn)之間的最短路徑問題兩點(diǎn)之間的最短路徑問題7.7 拓?fù)渑判蛲負(fù)渑判?.8 關(guān)鍵路徑關(guān)鍵路徑第七章 圖2022

15、-1-3267.1 圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義 一、一、圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義二、名詞和術(shù)語二、名詞和術(shù)語三、基本操作三、基本操作2022-1-327 圖圖是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集 V 和一個(gè)和一個(gè)弧集弧集 VR構(gòu)構(gòu) 成的數(shù)據(jù)結(jié)構(gòu)。成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, VR ) 其中，VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 w 為 弧頭弧頭，v 為弧尾弧尾。 謂詞 P(v,w) 定義了弧 的意義或信息。 一、一、圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義2022-1-328 由于“弧”是有方向的，因此稱由頂點(diǎn)集頂點(diǎn)集和弧集弧集構(gòu)成的圖為有向圖。EACBD例如

16、例如: :G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 二、名詞和術(shù)語二、名詞和術(shù)語1.1.有向圖：有向圖：2022-1-329若VR 必有VR, 則稱頂點(diǎn) v 和頂點(diǎn) w 之間存在一條邊(v,w) 。BCAFED由頂點(diǎn)集頂點(diǎn)集和邊邊集集構(gòu)成的圖稱作無向圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) 3.3.邊：邊：2.2.無向圖：無向圖：2022-1-330ABECFAEFBBC設(shè)圖G=(V, VR)

17、和圖 G =(V, VR),且 VV, VRVR,則稱 G 為 G 的子圖子圖。1597211132 弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。4. 子圖子圖：5. 有向網(wǎng)，無向網(wǎng)有向網(wǎng)，無向網(wǎng)：2022-1-331無向完全圖無向完全圖有向完全圖有向完全圖 將含有 e=n(n-1) 條弧的有向圖有向圖 稱作有向完全圖。有向完全圖。稀疏圖稀疏圖：如果邊或弧的個(gè)數(shù)滿足 enlogn， 則稱作稀疏圖，否則稱作稠密圖。6. 完全圖、稀疏圖、稠密圖完全圖、稀疏圖、稠密圖：假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊， 如果e=n(n-1)/2 ，則該圖為，則該圖為無向完全圖。無向完全圖。2022-1-332鄰接點(diǎn)：鄰接

18、點(diǎn)：假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊邊， 則稱頂點(diǎn)v 和w 互為鄰接點(diǎn)鄰接點(diǎn)，例如例如: :TD(B) = 3TD(A) = 2度：度：與頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目邊的數(shù)目。ACDFEB7.7.鄰接點(diǎn)、度鄰接點(diǎn)、度2022-1-333頂點(diǎn)的出度出度: : 以頂點(diǎn)v 為弧尾的弧的數(shù)目;ABECF對(duì)有向圖來說對(duì)有向圖來說，頂點(diǎn)的入度入度: : 以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度度( (TD)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3由于弧有方向，則有入度入度和出度出度之分8.8.入度、出度入度、出度2022-1-33

19、4設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑路徑。路徑上邊的數(shù)目稱作路徑長度路徑長度。ABECF如如: :從A到F長度為 3 的路徑A,B,C,F簡(jiǎn)單路徑簡(jiǎn)單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路簡(jiǎn)單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的簡(jiǎn)單路徑簡(jiǎn)單路徑。9. 路徑、路徑長度、簡(jiǎn)單路徑、簡(jiǎn)單回路路徑、路徑長度、簡(jiǎn)單路徑、簡(jiǎn)單回路ABC ABCFB2022-1-335若無向圖中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖連通圖;若無向圖為非連通圖，則圖中各個(gè)連通

20、子圖稱作此圖的連通分量連通分量。10. 連通圖、連通分量連通圖、連通分量BACDFEG1BACDFEG22022-1-336 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖強(qiáng)連通圖。ABECFABECF對(duì)有向圖，對(duì)有向圖，否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量強(qiáng)連通分量。11. 強(qiáng)連通圖、強(qiáng)連通分量強(qiáng)連通圖、強(qiáng)連通分量2022-1-337 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。BACDFE12. 生成樹生成樹 BACDFEBACDFEBACDFE2022-1-338對(duì)非連通圖，則

21、稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林生成森林。13. 生成森林生成森林BAEECDF非連通圖非連通圖BAEECDF生成森林生成森林2022-1-3391. 結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀3. 插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)5. 對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作2. 對(duì)頂點(diǎn)的訪問操作對(duì)頂點(diǎn)的訪問操作6. 遍歷遍歷4. 插入和刪除弧插入和刪除弧三、基本操作三、基本操作2022-1-340CreatGraph(&G, V, VR): / 按定義(V, VR) 構(gòu)造圖DestroyGraph(&G): / 銷毀圖1. 結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀2022-1-3412. 對(duì)頂點(diǎn)的訪問操作對(duì)頂點(diǎn)的訪問操作LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在 / 圖中“位置位置” ；否則返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對(duì) v 賦值v