數(shù)據(jù)結(jié)構(gòu)-基于C++語言（微課版） 課件 6-十字鏈表

本節(jié)內(nèi)容：十字鏈表圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)十字鏈表：十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。由于用鄰接表存儲有向圖時(shí)，既需要鄰接表，又需要逆鄰接表，把兩表合二為一，用十字鏈表表示。在十字鏈表中,圖中每一條弧用一個(gè)弧結(jié)點(diǎn)表示，它由六個(gè)域組成。圖中的每個(gè)頂點(diǎn)用一個(gè)頂點(diǎn)結(jié)點(diǎn)表示，它由三個(gè)域組成。圖的存儲結(jié)構(gòu)十字鏈表：弧結(jié)點(diǎn)的結(jié)構(gòu)tagweighttailvextailnextarcheadvexheadnextarc

邊結(jié)點(diǎn)：tag：標(biāo)記域，標(biāo)記該弧是否被處理過；weight：信息域，存儲弧的權(quán)值；tailvex、headvex：頂點(diǎn)域，分別表示弧尾頂點(diǎn)和弧頭頂點(diǎn)的序號；tailnextarc：鏈接指針，指向下一條以頂點(diǎn)tailvex為始點(diǎn)(弧尾)的弧；headnextarc：鏈接指針，指向下一條以頂點(diǎn)headvex為終點(diǎn)(弧頭)的?。粓D的存儲結(jié)構(gòu)十字鏈表：頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)圖中的每一個(gè)頂點(diǎn)用一個(gè)頂點(diǎn)結(jié)點(diǎn)表示，所有頂點(diǎn)結(jié)點(diǎn)組成一個(gè)順序表，它由三個(gè)域組成：data：存儲有關(guān)頂點(diǎn)的信息；firstinarc：鏈接指針，指向第一條以該頂點(diǎn)為終點(diǎn)的??；firstoutarc：鏈接指針，指向第一條以該頂點(diǎn)為始點(diǎn)的弧。

data頂點(diǎn)結(jié)點(diǎn)：firstinarcfirstoutarc圖的存儲結(jié)構(gòu)十字鏈表特點(diǎn)：在有向圖的十字鏈表中，從頂點(diǎn)結(jié)點(diǎn)中的firstoutarc域出發(fā)，統(tǒng)計(jì)鏈表中弧結(jié)點(diǎn)的個(gè)數(shù)，可求得該頂點(diǎn)的出度，從頂點(diǎn)結(jié)點(diǎn)中的firstinarc域出發(fā)，統(tǒng)計(jì)鏈表中弧結(jié)點(diǎn)的個(gè)數(shù)，可求得該頂點(diǎn)的入度。G1V2V0V10102^01212^^21^^弧結(jié)點(diǎn)V0V2V1頂點(diǎn)結(jié)點(diǎn)^鄰接矩陣、鄰接表、鄰接多重表、十字鏈表的比較：在邊稀疏（e<<n（n-1）/2）的情況下，用鄰接表、鄰接多重表表示圖比鄰接矩陣節(jié)省存儲空間；在鄰接表上容易找到任何一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)（vi和vj）之間是否有邊或弧相連，則需搜索第i個(gè)或第j個(gè)鏈表，因此，不及鄰接矩陣方便；鄰接表、鄰接矩陣：無向圖、有向圖；鄰接多重表：無向圖；十字