資料結構課程設計

濱江學院

題目拓撲排序

專業：電腦科學與技術

班級計科1班

學號20112308021

姓名王昊

指導教師李振巨集

日期：2013 年 11 月 20 日

目錄一、引言2

二、系統設計2

1.需求分析2

1.1問題描述2

1.2基於鄰接表的儲存結構2

1.3基本要求3

1.4程式的功能3

2.概要設計4

2.1採用鄰接鍊錶作為有向圈的存貯結構4

2.2基本設計4

2.3演算法中用到的所有各種資料型別的定義5

2.4各程式模組之間的層次呼叫關係5

3.詳細設計5

3.1設計拓撲排序的步驟5

3.2拓撲排序問題的特徵6

3.3演算法設計6

3.4演算法編碼實現7

3.5演算法和各模組的**7

3.6演算法的時間複雜度和空間複雜度8

三、系統實現8

除錯分析8

四、設計體會9

五、參考文獻10

一、引言

資料結構是一門理論性很強、思維抽象、難度較大的課程，是基礎課和專業課之間的橋梁。該課程的先行課程是計算機導論、離散數學等，後續課程有作業系統、編譯原理、資料庫原理、軟體工程等。通過本門課程的學習，我們應該能透徹地理解各種資料物件的特點，學會資料的組織方法和實現方法，並進一步培養良好的程式設計能力和解決實際問題的能力，而且該課程的研究方法對我們學生在學校和離校後的工作和學習，也有重要意義。

資料結構是電子資訊科學與技術專業的一門核心專業基礎課，在該專業的課程體系中起著承上啟下的作用，學好了資料結構對於提高理論認知水平和實踐能力有著極為重要的作用。學習資料結構的最終目的是為了獲得求解問題問能力。對於現實世界中的問題，應該能從中抽象出乙個適當的數學模型，該數學模型在計算機內部的資料結構來表示，然後設計乙個解此數學模型的演算法，在進行程式設計除錯，最後活的問題的解答。

基於此原因，現在我們開設資料結構課程設計。針對資料結構課程的特點，著眼於培養我們的實踐能力。實習課程是為了加強程式設計能力的培養，鼓勵學生使用新興的程式語言。

相信通過資料結構課程實踐，無論是理論知識，還是動手能力，同學們都會有不同程度的提高

二、系統設計

1、需求分析

1.1、問題描述

本次課程設計題目是：用鄰接表構造圖然後進行拓撲排序，輸出拓撲排序序列

拓撲排序的基本思想為：

1).從有向圖中選乙個無前驅的頂點輸出；

2).將此頂點和以它為起點的弧刪除

3).重複1),2)直到不存在無前驅的頂點；

4).若此時輸出的頂點數小於有向圖中的頂點數，則說明有向圖中存在迴路，否則輸出的頂點的順序即為乙個拓撲序列。

1.2、基於鄰接表的儲存結構

入度為零的頂點即為沒有前驅的頂點，我們可以附設乙個存放各頂點入度的陣列indegree[ ]，於是有：

（1）找g中無前驅的頂點——查詢indegree[i]為零的頂點vi；

（2）刪除以i為起點的所有弧——對鏈在頂點i後面的所有鄰接頂點k將對應的 indegree[k] 減1。

為了避免重複檢測入度為零的頂點，可以再設定乙個輔助棧，若某一頂點的入度減為0，則將它入棧。每當輸出某一入度為0的頂點時，便將它從棧中刪除。

1.3、基本要求

（1）輸入的形式和輸入值的範圍；

輸入：學期課時，一學期的課時上線，每門課的課程號，直接先修關係的課程號。

（2）首先是輸入要排序的頂點數和弧數，都為整型，中間用分隔符隔開；再輸入各頂點的值，為正型，中間用分隔符隔開；然後輸入各條弧的兩個頂點值，先輸入弧頭，再輸入弧尾，中間用分隔符隔開，輸入的值只能是開始輸入的頂點值否則系統會提示輸入的值的頂點值不正確，請重新輸入，只要繼續輸入正確的值就行。

（3）輸出的形式；若無解，則報告錯誤資訊；否則輸出教學計畫。

（4）首先輸出建立的鄰接表，然後是最終各頂點的出度數，再是拓撲排序的序列，並且每輸出乙個頂點，就會輸出一次各頂點的入度數。

（5）程式所能達到的功能；

因為該程式是求拓撲排序，所以演算法的功能就是要輸出拓撲排序的序列，在乙個有向圖中，若用頂點表示活動，有向邊就表示活動間先後順序，那麼輸出的拓撲序列就表示各頂點間的關係為反映出各點的儲存結構，以鄰接表儲存並輸出各頂點的入度。

1.4、程式的功能

排課問題是現在各個學校必須面臨的乙個問題。而且隨著近年來學生規模的擴招,教育機構的複雜化，課程各類的多樣化，排課的問題越來越難。儘管目前對排課採用了程式設計的計算機智慧型排課系統，但是仍然存在著這樣或者那樣的問題。

最為突出的乙個問題，比如，有一些排課方案,看上去完美無缺,或者效率比較高,甚至達到了最優解，但是具體地去實施的時候，發現整個課程的設計方案有著大的漏洞，經常出現的問題是，排課的拓撲圖出現了一些環，以至於進入了死迴圈。該課程設計的目的就是針對於如何檢測環的存在而避免錯誤的排課方案。本文採用的演算法是基於拓撲序列的拓撲排序演算法對特定條件的排課問題提出的一種解決方案，具體的實驗結果是展示出乙個符合條件的課程拓撲序列，整個演算法的設計與實現過程將要用到鄰接表,堆疊等資料結構等等。

2、概要設計

2.1 採用鄰接鍊錶作為有向圈的存貯結構

鍊錶由兩部分組成，一部分是表頭結點。反映各門課程的編號、該課程的前趨課程數及後繼課程的首位址。形式如下：

另一部分是表結點，反映各課程的鏈結關係，形式如下：

2.2基本設計

以頂點代表課程，弧代表課程的先後修關係，按表中條件建立有向無環圖的鄰接表結構並統計得到初始的入度為0的頂點，利用拓撲排序演算法來進行課程安排。假定乙個進修班的學生必須完成所列的全部課程。在這裡，課程代表活動，學習每門課程的先決條件是學完它的全部先修課程，如「3」課程就必須在它的兩門先修課程「1」和「2」之後，「9」課程則可以在後修課程之前隨時安排，因為它是基礎課程。

通常我們把這種頂點代表活動，邊代表活動間先後關係的有向圖稱作頂點活動網，簡稱aov網。—個aov網應該是—個有向無環圖，即不應該帶有迴路，因為若帶有迴路，則回路上的所有活動都無法進行。

在aov網中，若不存在迴路，則所有活動可排列成乙個線性序列，使得每個活功的所有前驅活動都排列在該活動的前面，我們稱此序列為拓撲序列(topological order)，由aov網構造拓撲序列的過程叫做拓撲排序(topological sort)。aov網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。

由aov網構造拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序進行每一項活動，就能夠保證在開始每一項活動時，它的所有前驅活動都已完成，從而使得整個工程按順序進行。由構造拓撲序列的拓撲排序演算法主要是迴圈執行以下兩步，直到不存在入度為0的頂點為止。

(1)選擇乙個入度為0的頂點並輸出之；

(2)從網中刪除該頂點及所有從該頂點出發的邊。

迴圈結束時，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」錯誤資訊，否則輸出的頂點序列就是一種拓撲序列。

為了在計算機上實現拓撲排序演算法，aov網採用鄰接表表示較方便，不過要在表頭結點結構中增加乙個儲存頂點入度的域(indegree)。在進行拓撲排序中，為了把拓撲排序都儲存起來，而且又便於插入、刪除和節省儲存，最好的方法是把它們鏈結成乙個棧。另一方面，當乙個頂點入度為0時，鄰接表中的對應表頭結點中的入度域(indegree)就沒有用了，可正好利用它作為鏈棧單元使用，用來儲存下乙個入度為0的頂點序號，通過所有入度為0的表頭結點中的入度域就可以把入度為0的頂點(對應表頭結點)都靜態鏈結起來。

在這個鏈棧中，棧頂指標top指向第乙個入度為0的項點vi〔對應表頭向量中的第i個分量，即vi的表頭結點)，vi的表頭結點的入度域指向第二個入度為0的頂點vj，依此類推，最後乙個入度為0的表頭結點的入度域應置為0（即空指標），表示棧底。採用鄰接表作為實現上述演算法的資料結構。演算法首先掃瞄鄰接表，求出圖中每個頂點的入度存於陣列in中，然後將所有入度為0的頂點組成乙個鍊錶並作為鏈結儲存的棧進行操作，top向棧頂。

資料結構課程設計

資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦