數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蛘n程設(shè)計(jì)

1、課題二拓?fù)渑判?問題的提出2.1問題的提出任務(wù)：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判?。程序所?shí)現(xiàn)的功能：建立對(duì)應(yīng)的鄰接表，對(duì)該圖進(jìn)行拓?fù)渑判?，并顯示排序結(jié)果。輸入：頂點(diǎn)數(shù),邊數(shù)及各頂點(diǎn)信息（數(shù)據(jù)格式為整形）輸出：拓?fù)渑判蚪Y(jié)果。2.2概要設(shè)計(jì)1.拓?fù)渑判蚴侵赣赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序。更直觀地講，一個(gè)偏序是自反的、反對(duì)稱的，用圖表示時(shí)每個(gè)點(diǎn)都有環(huán)且只有單向邊。拓?fù)渑判虻娜蝿?wù)是在這個(gè)偏序上得到一個(gè)全序，即得到一個(gè)完成整個(gè)項(xiàng)目的各步驟的序列。2解決拓?fù)渑判虻姆椒ㄈ缦拢海?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之。（2）從圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，或者

2、當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止。后一種情況則說明有向圖中存在環(huán)。具體的算法實(shí)現(xiàn)參照源程序。3構(gòu)造鄰接表圖：鄰接表圖4.為了避免重復(fù)檢測(cè)入度為零的頂點(diǎn)，源程序中設(shè)了一個(gè)棧，暫存所有入度為零的頂點(diǎn)：typedefstructstack棧的結(jié)構(gòu)，存儲(chǔ)圖的頂點(diǎn)序號(hào)4源代碼/采用尾插法創(chuàng)的鄰接圖棧的結(jié)構(gòu)，存儲(chǔ)圖的頂點(diǎn)序號(hào)弧結(jié)點(diǎn)頂點(diǎn)數(shù)組指向與頂點(diǎn)鄰接的第一條弧鄰接表圖請(qǐng)輸入圖的頂點(diǎn)數(shù)和弧數(shù)且頂點(diǎn)數(shù)不能超過請(qǐng)輸入頂點(diǎn)值輸入圖的頂點(diǎn)輸入圖的弧請(qǐng)輸入請(qǐng)輸入第條1弧的弧尾和弧頭求每個(gè)頂點(diǎn)的入度值入度頂點(diǎn)入棧記求每個(gè)頂點(diǎn)的入度值入度頂點(diǎn)入棧記+錄+輸;出/的/頂點(diǎn)數(shù)把與頂點(diǎn)把與頂點(diǎn)相/鄰接的頂點(diǎn)的入度拓?fù)渑判虿怀晒?/p>

3、拓?fù)渑判虺晒Y(jié)果與分析2.4.它的時(shí)間復(fù)雜度是O(G.vexnum+G.arcnum)。2.整個(gè)程序的關(guān)鍵就是采用尾插法創(chuàng)的鄰接表圖，運(yùn)用棧來實(shí)現(xiàn)各個(gè)數(shù)值的輸入輸出及存儲(chǔ)。3注意*的使用，并不是什么情況下都用*，它有時(shí)候會(huì)造成數(shù)據(jù)破壞，利用破壞的值進(jìn)行運(yùn)算，結(jié)果可想而知，所以，如果沒返回值時(shí)，一般不要用。4為了避免重復(fù)檢測(cè)入度為零的頂點(diǎn)，源程序中設(shè)了一個(gè)棧，暫存所有入度為零的頂點(diǎn)，此程序段書寫如下：建零入度頂點(diǎn)棧入度為者進(jìn)棧對(duì)輸出頂點(diǎn)計(jì)數(shù)輸出號(hào)頂點(diǎn)并計(jì)數(shù)對(duì)號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1一旦入度為0則入棧5測(cè)試的數(shù)據(jù)如下：第一組結(jié)果（有向無環(huán)圖）C:FilesMicriosuftVisualStu

4、diaByProjectslC:FilesMicriosuftVisualStudiaByProjectsl1123Debug：123.虞輸入圉的頂*裁和切庶卞且頂點(diǎn)谿卜能赳出恥加輸入頂點(diǎn)值：1234G晴輸入第1條弧的弧尼和弧頭:12笹入影條弧的弧尾和弧頭:舍輸入第3條弧的弧尾和弧頭:脣輸入第4茶弧的弧尾和弧頭=51情嗡入第E條弧的弧尾和弧頭:52i青愉入第6條弧的弧匡和弧頭；B31234師撲排序成功tPressanyJceitocontinueB第二組結(jié)果（有向有環(huán)圖）：誦輸入圏的頂點(diǎn)數(shù)和弧數(shù)V且頂點(diǎn)數(shù)不能超過陰請(qǐng)輸.入頂點(diǎn)值:1M輸入第丄條弧的弧尾和弧頭晴輸入第2條弧的弧尾和弧頭情輸入第5條弧的弧尾和弧頭情輸入第6條弧的弭層和弧頭障輸入第?條弧的弧足