C語(yǔ)言課程設(shè)計(jì)拓補(bǔ)排序

1、荊楚理工學(xué)院課程設(shè)計(jì)成果學(xué)院計(jì)算機(jī)工程學(xué)院 班級(jí)：xxxx學(xué)生姓名:xxxx學(xué) 號(hào):xxxxx設(shè)計(jì)地點(diǎn)（單位）_xxx 設(shè)計(jì)題目:拓?fù)渑判蛲瓿扇掌冢?2014 年12月28日成績(jī)（五級(jí)記分制）:教師簽名:指導(dǎo)教師評(píng)語(yǔ)：荊楚理工學(xué)院課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目：拓?fù)渑判驅(qū)W生姓名xxx課程名稱數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)班業(yè)級(jí) 專xxx點(diǎn)地xx起止時(shí) 問(wèn)2014.12.25-2015.1.9設(shè) 計(jì) 內(nèi) 容 及 要 求問(wèn)題描述：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判?。設(shè) 計(jì) 參 數(shù)進(jìn) 度 要 求兩個(gè)星期內(nèi)完成。參 考 資 料1李素若，陳萬(wàn)華等編著.數(shù)據(jù)結(jié)構(gòu).北京：中國(guó)水利水電出版社，2014.7.北京：中 國(guó)水?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題解咨及上

2、機(jī)指導(dǎo).2李素若，理輝，嚴(yán)永松編著.,2014.9.利水電出版社2006.北京：清華大學(xué)出版社，面向?qū)ο蟪绦蛟O(shè)計(jì).3譚浩強(qiáng).c+其 它說(shuō) 明1.本表應(yīng)在每次實(shí)施前一周由負(fù)責(zé)教師填寫二份，教研室審批后交學(xué)院院備案，一 份由負(fù)責(zé)教師留用。2.若填寫內(nèi)容較多可另紙附后。3.一題多名學(xué)生共用的，在設(shè) 計(jì)內(nèi)容、參數(shù)、要求等方面應(yīng)肩所區(qū)別。教研室主任：指導(dǎo)教師：2015年1月9 日目錄1問(wèn)題描述12基本要求13算法思想14數(shù)據(jù)結(jié)構(gòu)24.1 鏈?zhǔn)疥?duì)列的存儲(chǔ)類型為24.2 圖的類型（鄰接表存儲(chǔ)結(jié)構(gòu)）為 25模塊劃分 25.1 鏈?zhǔn)疥?duì)列操作25.2 有向圖（dag於口接表存儲(chǔ)結(jié)構(gòu)（alg）的操作35.3 拓?fù)渑?/p>

3、序及拓?fù)錂z測(cè)算法 35.4 主函數(shù) 46 測(cè)試數(shù)據(jù) 46.1 對(duì)“建立有向圖并輸出” 的測(cè)試 46.2 對(duì)“建立有向圖并求一個(gè)拓?fù)渑判蛐蛄小?的測(cè)試 46.3 對(duì)“檢測(cè)用戶輸入的課程安排” 的測(cè)試 47 測(cè)試情況 57.1 對(duì)“建立有向圖并輸出” 的測(cè)試 57.2 對(duì)“建立有向圖并求一個(gè)拓?fù)渑判蛐蛄小?的測(cè)試 77.3 對(duì)“檢測(cè)用戶輸入的課程安排” 的測(cè)試 88 系統(tǒng)開發(fā)所用到的技術(shù)11參考文獻(xiàn) 13附錄 全部代碼 141 問(wèn)題描述在aovw中為了更好地完成工程，必須滿足活動(dòng)之間先后關(guān)系，需要將各活動(dòng)排一個(gè)先后次序即為拓?fù)渑判颉?拓?fù)渑判蚩梢詰?yīng)用于教學(xué)計(jì)劃的安排， 根據(jù)課程之間的依賴關(guān)系， 制

4、定課程安排計(jì)劃。 按照用戶輸入的課程數(shù)， 課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系， 程序執(zhí)行后會(huì)給出符合拓?fù)渑判虻恼n程安排計(jì)劃。2 基本要求1、選擇合適的存儲(chǔ)結(jié)構(gòu)，建立有向無(wú)環(huán)圖，并輸出該圖；2 、實(shí)現(xiàn)拓?fù)渑判蛩惴ǎ? 、運(yùn)用拓?fù)渑判驅(qū)崿F(xiàn)對(duì)教學(xué)計(jì)劃安排的檢驗(yàn)。3 算法思想1、采用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)有向圖；有向圖需通過(guò)頂點(diǎn)數(shù)、弧數(shù)、頂點(diǎn)以及弧等信息建立。2 、拓?fù)渑判蛩惴╲oid topologicalsort(algraph g) 中，先輸出入度為零的頂點(diǎn)， 而后輸出新的入度為零的頂點(diǎn)， 此操作可利用?；蜿?duì)列實(shí)現(xiàn)。 考慮到教學(xué)計(jì)劃安排的實(shí)際情況，一般先學(xué)基礎(chǔ)課(入度為零) ，再學(xué)專業(yè)課

5、(入度不為零) ，與隊(duì)列先進(jìn)先出的特點(diǎn)相符，故采用隊(duì)列實(shí)現(xiàn)。3 、拓?fù)渑判蛩惴╲oid topologicalsort(algraph g) ，大體思想為：1) 遍歷有向圖各頂點(diǎn)的入度，將所有入度為零的頂點(diǎn)入隊(duì)列；2) 隊(duì)列非空時(shí)，輸出一個(gè)頂點(diǎn)，并對(duì)輸出的頂點(diǎn)數(shù)計(jì)數(shù)；3) 該頂點(diǎn)的所有鄰接點(diǎn)入度減一，若減一后入度為零則入隊(duì)列；4) 重復(fù) 2) 、 3) ，直到隊(duì)列為空，若輸出的頂點(diǎn)數(shù)與圖的頂點(diǎn)數(shù)相等則該圖可拓?fù)渑判?，否則圖中有環(huán)。5) 、要對(duì)教學(xué)計(jì)劃安排進(jìn)行檢驗(yàn)，因此編寫了檢測(cè)用戶輸入的課程序列是否是拓?fù)湫蛄械乃惴╲oid topsortcheck(algraph g) ，大體思想為：1) 用

6、戶輸入待檢測(cè)的課程序列，將其存入數(shù)組；2) 檢查課程序列下一個(gè)元素是否是圖中的頂點(diǎn)(課程) ，是則執(zhí)行3) ，否則輸出“課程xx 不存在”并跳出；3) 判斷該頂點(diǎn)的入度是否為零，是則執(zhí)行4) ，否則輸出“入度不為零”并跳出；4) 該頂點(diǎn)的所有鄰接點(diǎn)入度減一；5) 重復(fù) 2) 、 3) 、 4)直到課程序列中所有元素均被遍歷，則該序列是拓?fù)湫蛄?，否則不是拓?fù)湫蛄小?4 數(shù)據(jù)結(jié)構(gòu)4.1 鏈?zhǔn)疥?duì)列的存儲(chǔ)類型為typedef int elemtype;typedef struct qnode elemtype data;struct qnode *next; qnode,*queueptr;typed

7、ef struct queueptr front;queueptr rear; linkqueue;4.2 圖的類型（鄰接表存儲(chǔ)結(jié)構(gòu)）為typedef char vertextype20;/ 頂點(diǎn)信息（名稱） typedef struct arcnode/鏈表結(jié)點(diǎn) int vexpos;/ 該弧所指向的頂點(diǎn)在數(shù)組中的位置struct arcnode *next;/指向當(dāng)前起點(diǎn)的下一條弧的指針 arcnode;typedef struct vnode/ 頭結(jié)點(diǎn) vertextype name;/ 頂點(diǎn)信息（名稱）int indegree;/ 頂點(diǎn)入度arcnode *firstarc;/ 指向當(dāng)

8、前頂點(diǎn)的第一條弧的指針 vnode,adjlistmax_vertex_num; typedef struct adjlist vexhead;/ 鄰接表頭結(jié)點(diǎn)數(shù)組int vexnum,arcnum;/ 圖的頂點(diǎn)數(shù)和弧數(shù) algraph;5 模塊劃分5.1 鏈?zhǔn)疥?duì)列操作1) void initqueue(linkqueue *q)功能：初始化鏈?zhǔn)疥?duì)列參數(shù)： *q 待初始化的隊(duì)列2) int queueempty(linkqueue q)功能：判斷空隊(duì)列 2參數(shù)： q 待判斷的隊(duì)列返回值：隊(duì)列為空返回 1 ；隊(duì)列非空返回 03) void enqueue(linkqueue *q, elemty

9、pe e) 功能：元素入隊(duì)列參數(shù)： *q 待操作的隊(duì)列； e 要入隊(duì)列的元素4) void dequeue(linkqueue *q, elemtype *e) 功能：元素出隊(duì)列參數(shù)： *q 待操作的隊(duì)列； *e 記錄出隊(duì)列元素的變量5.2 有向圖(dag)鄰接表存儲(chǔ)結(jié)構(gòu)(alg)的操作1) int locatevex(algraph g,vertextype v)功能：頂點(diǎn)在頭結(jié)點(diǎn)數(shù)組中的定位參數(shù)： g 待操作的圖； v 要在圖中定位的頂點(diǎn)返回值：頂點(diǎn)存在則返回在頭結(jié)點(diǎn)數(shù)組中的下標(biāo)；否則返回圖的頂點(diǎn)數(shù)2) int creategraph(algraph *g)功能：建立圖函數(shù)內(nèi)包含了由用戶輸

10、入頂點(diǎn)數(shù)、弧數(shù)、頂點(diǎn)以及弧的操作參數(shù)： *g 待操作的圖返回值：圖建立成功返回 1；圖建立失敗返回 0錯(cuò)誤判斷：包含頂點(diǎn)數(shù)、弧數(shù)是否正確的判斷；包含用戶輸入的弧的頂點(diǎn)是否存在的判斷3) void printgraph(algraph g)功能：輸出有向圖參數(shù)： g 待輸出的圖4) int creategraph2(algraph *g)功能：建立預(yù)置課程圖(輸出函數(shù)內(nèi)預(yù)置課程信息，并自動(dòng)建立有向圖)參數(shù)： *g 待操作的圖返回值：圖建立成功返回 1；圖建立失敗返回 0錯(cuò)誤判斷：包含頂點(diǎn)數(shù)、弧數(shù)是否正確的判斷包含弧的頂點(diǎn)是否存在的判斷5) void printgraph2(algraph g)功

11、能：輸出預(yù)置課程圖參數(shù)： g 待輸出的圖5.3 拓?fù)渑判蚣巴負(fù)錂z測(cè)算法1) void topologicalsort(algraph g)功能：實(shí)現(xiàn)拓?fù)渑判騾?shù)： g 待進(jìn)行拓?fù)渑判虻膱D錯(cuò)誤判斷：包含有向圖是否有環(huán)的判斷2) void topsortcheck(algraph g)功能：運(yùn)用拓?fù)渑判虻乃枷霗z測(cè)教學(xué)計(jì)劃函數(shù)內(nèi)包含了由用戶輸入待檢測(cè)的課程序列的操作3參數(shù)： g 待操作的圖錯(cuò)誤判斷：包含用戶輸入的課程是否存在的判斷包含不是拓?fù)湫蛄械脑?該課程有多少個(gè)先決課程未學(xué))5.4 主函數(shù)void main()功能：主函數(shù)利用 while 語(yǔ)句和 switch 語(yǔ)句實(shí)現(xiàn)菜單化調(diào)用函數(shù)1.1 對(duì)

12、“建立有向圖并輸出”的測(cè)試1)正確的有向圖信息頂點(diǎn)數(shù)和弧數(shù)：4,3頂點(diǎn):a b c d邊:a b b c c d2) 錯(cuò)誤的邊頂點(diǎn)數(shù)和弧數(shù):4,3頂點(diǎn):a b c d邊:a b b c c e3) 錯(cuò)誤的頂點(diǎn)數(shù)或弧數(shù)頂點(diǎn)數(shù)和弧數(shù):3,76.2 對(duì)“建立有向圖并求一個(gè)拓?fù)渑判蛐蛄小钡臏y(cè)試1)有向圖能實(shí)現(xiàn)拓?fù)渑判蝽旤c(diǎn)數(shù)和弧數(shù)：5,5頂點(diǎn):a b c d e邊:a d d c c b e a e c有向圖不能實(shí)現(xiàn)拓?fù)渑判?):5,5 頂點(diǎn)數(shù)和弧數(shù):a b c d e 頂點(diǎn)b ae a 邊：a d d c c b6.3 對(duì)“檢測(cè)用戶輸入的課程安排”的測(cè)試1)課程序列符合拓?fù)湫蛄姓n程序歹 hc9 c10

13、 c11 c6 c1 c12 c4 c2 c3 c5 c7 c842) 課程序列中有課程不存在課程序歹 hc9 c10 c11 c6 c1 c12 c4 c2 c13 c5 c7 c83) 課程序列不是拓?fù)湫蛄姓n程序歹 hc9 c10 c11 c1 c8 c6 c12 c4 c2 c3 c5 c77測(cè)試情況程序初始執(zhí)行界面(以下測(cè)試編號(hào)與本文第七節(jié)測(cè)試數(shù)據(jù)編號(hào)一一對(duì)應(yīng))對(duì)“建立有向圖并輸出”的測(cè)試 7.151)正確的有向圖信息,并輸出有向圖有向圖信息正確的情況下，程序顯示“有向圖建立成功” 錯(cuò)誤的邊 2).不是有向圖中的頂點(diǎn)，程序能判斷本錯(cuò)誤并顯示相應(yīng)的e(c e)的一個(gè)頂點(diǎn)本測(cè)試中，第三條邊

14、提示信息。3)錯(cuò)誤的頂點(diǎn)數(shù)或弧數(shù)條有向邊，則個(gè)頂點(diǎn)，兩頂點(diǎn)間最多有23,7本測(cè)試中，頂點(diǎn)數(shù)和弧數(shù)分別為。若有向圖共有n；3*(3-1)=6front=q-rear=(queueptr)malloc(sizeof(qnode);if (!(q-front) exit(0);q-front-next=null; */* 2. 判斷空隊(duì)列 int queueempty(linkqueue q) if(q.front=q.rear) return 1;elsereturn 0; 14/* 3. 入隊(duì)列 */void enqueue(linkqueue *q, elemtype e) queueptr

15、p;p=(queueptr)malloc(sizeof(qnode);if (!p) exit(0);p-data=e; p-next=null;q-rear-next=p;q-rear=p; */出隊(duì)列 /* 4.void dequeue(linkqueue *q, elemtype *e) queueptr p; if(q-front!=q-rear) p=q-front-next; *e=p-data;q-front-next=p-next;if (q-rear=p) q-rear=q-front; free(p); /*/*/ /*以下為有向圖(dag)(alg)的操作鄰接表存儲(chǔ)結(jié)構(gòu)/

16、*/#define max_vertex_num 20 /最大頂點(diǎn)個(gè)數(shù)/typedef char vertextype20;/ 頂點(diǎn)信息(名稱) */ 圖的類型定義(鄰接表存儲(chǔ)結(jié)構(gòu)) /*鏈表結(jié)點(diǎn) typedef struct arcnode / 該弧所指向的頂點(diǎn)在數(shù)組中的位置intvexpos; /指向當(dāng)前起點(diǎn)的下一條弧的指針struct arcnode *next; / arcnode;typedef struct vnode / 頭結(jié)點(diǎn) vertextype name; / 頂點(diǎn)信息(名稱)15int indegree; / 頂點(diǎn)入度arcnode *firstarc; / 指向當(dāng)前頂點(diǎn)

17、的第一條弧的指針 vnode,adjlistmax_vertex_num;typedef struct adjlist vexhead; / 鄰接表頭結(jié)點(diǎn)數(shù)組int vexnum,arcnum; / 圖的頂點(diǎn)數(shù)和弧數(shù) algraph;/* 5. 頂點(diǎn)在頭結(jié)點(diǎn)數(shù)組中的定位 */int locatevex(algraph g,vertextype v) int i;for(i=0;ig.vexnum;i+)if(strcmp(v,g.)=0) break;return i; */* 6. 建立圖(鄰接表) 0 int creategraph(algraph *g) / 成

18、功建立返回 1，不成功則返回 int i,j,k; vertextype v1,v2;arcnode *newarc; printf(輸入頂點(diǎn)數(shù)和弧數(shù)輸入有向圖頂點(diǎn)數(shù)和弧數(shù)vexnum,arcnum:); /scanf(%d,%d,&(*g).vexnum,&(*g).arcnum); / 輸入并判斷頂點(diǎn)數(shù)和弧數(shù)是否 正確if(*g).vexnum0|(*g).arcnum(*g).vexnum*(*g).vexnum-1) printf(頂點(diǎn)數(shù)或弧數(shù)不正確，有向圖建立失敗！ n);return 0; printf(輸入 %d 個(gè)頂點(diǎn) :,(*g).vexnum); / 輸入頂點(diǎn)名稱for(i

19、=0;i(*g).vexnum;i+) scanf(%s,(*g).); printf(頂點(diǎn)列表:n共有d個(gè)頂點(diǎn)：，(*g).vexnum);/ 輸出頂點(diǎn)名稱for(i=0;i(*g).vexnum;i+)printf(%s ,(*g).);for(i=0;i(*g).vexnum;i+) / 鄰接表初始化 (*g).vexheadi.firstarc=null;(*g).vexheadi.indegree=0;16printf(n 輸入 %d 條邊 :vi vjn,(*g).arcnum); / 輸入有向圖的邊f(xié)or(k=0;k=(*g).

20、vexnum)頂點(diǎn)軸灌晴龍羽存在，有向圖建立失??！n,v1);return 0; if(j=(*g).vexnum)n,v2);return 0; 頂點(diǎn)軸灌晴龍8存在，有向圖建立失??！ newarc=(arcnode*)malloc(sizeof(arcnode); / 前插法建頂點(diǎn)鏈表 newarc-vexpos=j;if(*g).vexheadi.firstarc=null) newarc-next=null;(*g).vexheadi.firstarc=newarc; else newarc-next=(*g).vexheadi.firstarc-next;(*g).vexheadi.f

21、irstarc-next=newarc; 對(duì)應(yīng)頂點(diǎn)入度計(jì)數(shù)加 1(*g).vexheadj.indegree+; / printf(有向圖建立成功！ n);return 1;/* 7. 按鄰接表方式輸出有向圖 */void printgraph(algraph g) int i;arcnode *p;printf(輸出有向圖 :n);for(i=0; );p=p-next; printf();/ 為避免演示時(shí)要輸入過(guò)多數(shù)據(jù)，以下函數(shù)將課程編號(hào)、課程間的先后關(guān)系通過(guò)數(shù)組預(yù)置/* 8. 建立預(yù)置課程圖(鄰接表)*/int creategraph2(algraph *g) /

22、 成功建立返回1，不成功則返回0 int i,j,k; vertextype v1,v2; arcnode *newarc;vertextype subjectname12= c1,c2,c3,c4, / 課程名稱c5,c6,c7,c8,c9,c10,c11,c12 ,relationv116= c1,c1,c2,c1, / 基礎(chǔ)課c3,c4,c11,c5,c3,c3,c6,c9,c9,c9,c10,c11,relationv216= c2,c3,c3,c4, / 以上面課程為基礎(chǔ)的課c5,c5,c6,c7,c7,c8,c8,c10, c11,c12,c12,c12,;/* 輸出本程序使用的課

23、程及先后關(guān)系表*/printf(本程序預(yù)置了如下課程及先后關(guān)系 :n);printf( 課程編號(hào)課程名稱先決條件 nc1程序設(shè)計(jì)基礎(chǔ)無(wú) nc2離散數(shù)學(xué)c1nc3數(shù)據(jù)結(jié)構(gòu)c1,c2nc4匯編語(yǔ)言c1nc5語(yǔ)言的設(shè)計(jì)和分析 c3,c4nc6計(jì)算機(jī)原理c11nc7編譯原理c5,c3nc8操作系統(tǒng)c3,c6n18c9高等數(shù)學(xué)無(wú) nc10線性代數(shù)c9nc11普通物理c9nc12數(shù)值分析c9,c10,c1n);system(pause);(*g).vexnum=12; (*g).arcnum=16;if(*g).vexnum0|(*g).arcnum(*g).vexnum*(*g).vexnum-1) p

24、rintf(課程數(shù)或先后關(guān)系不正確，有向圖建立失敗！ n);return 0; / 判斷課程數(shù)和弧數(shù)是否正確for(i=0;i(*g).vexnum;i+) strcpy(*g).,subjectnamei); for(i=0;i(*g).vexnum;i+) / 鄰接表初始化 (*g).vexheadi.firstarc=null;(*g).vexheadi.indegree=0; for(k=0;k=(*g).vexnum)軸灌晴龍課程 s不存在，有向圖建立失??！n,v1);return 0; if(j=(*g).vexnum)前插法建課程鏈表軸灌晴龍課程s存在，

25、有向圖建立失敗！n,v2);return 0; newarc=(arcnode*)malloc(sizeof(arcnode); / newarc-vexpos=j;if(*g).vexheadi.firstarc=null) newarc-next=null;(*g).vexheadi.firstarc=newarc; else newarc-next=(*g).vexheadi.firstarc-next;(*g).vexheadi.firstarc-next=newarc; 1對(duì)應(yīng)課程入度計(jì)數(shù)加 (*g).vexheadj.indegree+; /19printf(有向圖建立成功！ n)

26、;return 1;/* 9. 按鄰接表方式輸出預(yù)置課程圖 */void printgraph2(algraph g) int i;arcnode *p;printf(輸出有向圖 :n);for(i=0; );p=p-next;printf( );/*/*/ /* 以下為拓?fù)渑判蛩惴?*/*/* 10. 拓?fù)渑判?void topologicalsort(algraph g) int i,k,count;elemtype e;arcnode *p; */ linkqueue q; /* 定義隊(duì)列 initqueue(&q);for(i=0; inext) /遍歷當(dāng)前課程

27、的鄰接點(diǎn) k=p-vexpos; / 鄰接點(diǎn)位置if(!(-g.vexheadk.indegree) /每個(gè)鄰接點(diǎn)入度減1 后若為零則入隊(duì)列enqueue(&q,k);printf();if(countg.vexnum) printf(該有向圖有回路，無(wú)法完成拓?fù)渑判颍?n); /*/* 以下為拓?fù)錂z測(cè)算法 */*/* 11. 運(yùn)用拓?fù)渑判虻乃枷霗z測(cè)教學(xué)計(jì)劃 */void topsortcheck(algraph g) int i,k; arcnode *p; vertextype v,checklist12;/待檢測(cè)序列topologicalsort(g);printf(輸入待檢測(cè)的課程序列 :n);for(i=0; ig.vexnum; i+) / 輸入待檢測(cè)序列scanf(%s,checklisti);for(i=0; i=g.vexnum) / 判斷課程是否存在?軸灌晴龍課程 $不存在！ n,v);return; if(g.vexheadk.indegree!=0) / 判斷課程入度是否為零軸灌晴龍學(xué)習(xí)課程$時(shí)