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

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

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

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

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