演算法與資料結構
課程設計報告
題目： 拓撲排序
一． 問題描述
對乙個有向無環圖g進行拓撲排序，是將g中所有頂點排成乙個線性序列，使得圖中任意一對由某個集合上的乙個偏序得到該集合上的乙個全序，這個操作就稱之為拓撲排序。偏序集合中僅有部分成員之間顆比較，而全序指集合中全體成員之間均可比較，而由偏序定義得到拓撲有序的操作便是拓撲排序。
乙個表示偏序的有向圖可用來表示乙個流程圖，通過抽象出來就是aov-網，若從頂點i到頂點j有一條有向路徑，則i是j的前驅，j是i的後繼。若（i，j）是一條弧，則i是j的直接前驅；j是i的直接後繼。
在aov-網中，不應該出現有向環，用拓撲排序就可以判斷網中是否有環，若網中所有頂點都在它的拓撲有序序列中，則該aov-網必定不存在環。
拓撲排序方法步驟：
1.從有向圖上選擇乙個沒有入度的節點並輸出。
2.從網中刪去改點並刪去從該頂點發出的全部有向邊。
3.重複上述兩步，直到剩餘網中不再存在沒有前驅的頂點為止。
二． 演算法設計
1.採用鄰接表作為有向圖的儲存結構，且需要編寫計算頂點入度的函式findindegre0（）。刪除入度為零的頂點，及以它為尾的弧的操作，可以換以弧頭頂點入度減一來實現。
避免重複檢測入度為零的頂點，需另設一棧儲存所有入度為零的頂點。當有向圖上某一頂點入度為零則將該頂點入棧，棧不為空時輸出棧頂，並將與該元素鄰接的頂點的入度減一，若減一後，入度為零，則繼續入棧重複上述步驟。
2.操作的結果：
（1）全部頂點被輸出，網中沒有迴路。
（2）未輸出全部頂點，剩餘頂點均有前驅，網中有迴路。
3.主要資料結構：（1）圖的鄰接表儲存形式;
（2）棧。
4.總體設計流程：
三． 演算法實現
1.源程式為：
#include<>
#include<>
#define true 1
#define false 0
#define max_vextex_num 20
#define m 20
#define stack_init_size 100
#define stackincrement 10
圖的鄰接表儲存結構
typedef struct arcnode弧結點結構型別*/
arcnode;
typedef struct vnode鄰接表頭結點型別*/
vnode,adjlist[max_vextex_numadjlist為鄰接表型別*/
typedef struct
algraph;
void creatgraph(algraph *g) /*通過使用者互動產生乙個圖的鄰接表*/
for (i=1;i<=g->arcnum;i記錄圖中由兩點確定的弧*/
printf
printf("\n建立的鄰接表為:\n");
/*列印生成的鄰接表（以一定的格式）*/
for(i=1;i<=g->vexnum;i++)
printf
}typedef struct棧的儲存結構
sqstack;
void initstack(sqstack *s初始化棧*/
s->top=s->base;
s->stacksize=stack_init_size;
}void push(sqstack *s,int e壓入新的元素為棧頂*/
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement;
}*s->top++=ee作為新的棧頂元素*/
}int pop(sqstack *s,int *e彈出棧頂，用e返回*/
排序課程設計報告C
一需求分析 1.執行環境 microsoft visual studio 2005 2.程式所實現的功能 對直接插入排序 折半插入排序 氣泡排序 簡單選擇排序 快速排序 堆排序 歸併排序演算法的演示，並且輸出每一趟的排序情況。3.程式的輸入 包含輸入的資料格式和說明 1 排序種類三輸入 2 排序數的...
資料結構排序綜合課程設計報告
資料結構 課程設計報告 專業電腦科學與技術 班級 1 姓名王昕 學號 20101308003 指導教師顧韻華 起止時間 2011.10 2011.12 課程設計 排序綜合 一 任務描述 1 至少採用三種方法實現上述問題求解 提示，可採用的方法有插入排序 希爾排序 氣泡排序 快速排序 選擇排序 堆排序...
球閥課程設計報告 ProE課程設計
一.課題名稱 球閥班級 12機自a1 小組成員 李軍帥 組長 李軍帥 二.球閥的功能和工作原理描述 1.球閥的工作原理 球閥的主要驅動原件是裝配於閥杆上端的扳手，球閥的啟閉元件是位於閥桿下端的球體。球閥的主要工作原理是 當給扳手施加某一轉矩，扳手驅動閥桿旋轉，閥桿將扳手的轉矩傳遞給位於閥桿下端的球體...