拓撲排序課程設計Word版

1、傳播優(yōu)秀word版文檔 ，希望對您有幫助，可雙擊去除！課 程 設 計 報 告課程名稱 數(shù)據(jù)結(jié)構 課題名稱 1.拓撲排序 2.成績管理 專 業(yè) 計算機科學與技術 班 級 計算機1181 學 號 201113030128 姓 名 蔡彪 指導教師 劉鐵武 2013年 6月30 日湖南工程學院課 程 設 計 任 務 書課程名稱 數(shù)據(jù)結(jié)構 課 題 1.拓撲排序 2.成績管理 專業(yè)班級 計算機1181 學生姓名 蔡彪 學 號 201113030128 指導老師 劉鐵武 審 批 任務書下達日期 2013 年 6 月 17 日任務完成日期 2013 年 6 月 30 日一設計內(nèi)容：問題1：拓撲排序大學期間各專

2、業(yè)都要制訂相應的教學計劃。每個專業(yè)開設的課程預先已確定。而各門課程間有的是相互獨立的，而有的則有先修后修的限定。試設計相應的課程設置程序，實現(xiàn)對某專業(yè)各學期的課程的排布，其中每門課需一定的課時，而各學期的總課時不能超過上限。測試數(shù)據(jù)學期課時上限數(shù)：350各課程所需學時：48課程先、后修關系如圖：194212101136578問題3：成績管理編制一應用軟件實現(xiàn)對班級成績管理?；竟δ苡袑W生信息的增刪（轉(zhuǎn)入或退學）、查找（從當前點向前或向后雙向的）、錄入、統(tǒng)計（如總分，及格率等）。建議用雙鏈表實現(xiàn)。二設計要求：課程設計報告內(nèi)容說明1)需求分析程序的功能；輸入輸出的要求。2)概要設計程序的模塊構成以

3、及模塊之間的層次結(jié)構、各模塊的調(diào)用關系；每個模塊的功能；課題涉及的數(shù)據(jù)結(jié)構和數(shù)據(jù)庫結(jié)構；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構，它們之間有什么關系等。3)詳細設計采用c語言定義相關的數(shù)據(jù)類型；寫出各模塊的類c碼算法；畫出各函數(shù)的調(diào)用關系圖、主要函數(shù)的流程圖。4)調(diào)試分析以及設計體會測試數(shù)據(jù)：準備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果；程序調(diào)試中遇到的問題以及解決問題的方法；課程設計過程經(jīng)驗教訓、心得體會。5)使用說明用戶使用手冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。6)書寫格式見附帶說明。7)附錄參考書目； 源程序清單（帶注釋）成績評定：

4、指導老師負責驗收程序的運行結(jié)果，并結(jié)合學生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設計報告等進行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學的課程設計成績。具體考核標準包含以下幾個部分： 平時出勤 （占10%） 系統(tǒng)需求分析、功能設計、數(shù)據(jù)結(jié)構設計及程序總體結(jié)構合理與否（占10%） 程序能否完整、準確地運行，個人能否獨立、熟練地調(diào)試程序（占40%） 設計報告（占30%）注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?獨立完成情況（占10%）。 運行所設計的系統(tǒng)。三.進度安排第17周星期一星期二星期三星期四星期五星期六星期日上午8：0012：008:3011:3

5、08:3011:30下午13：3017：3013:0016:00第18周星期一星期二星期三星期四星期五星期六星期日上午8：0012：008:3011:30下午13：3017：3013:0016:0013:0016:00參考書籍1.c程序設計課程設計 劉振安編著 tp312c5632.c+ builder和delphi課程設計與系統(tǒng)開發(fā)案例 伍俊良 清華大學出版社 7-302-06072-x 3.visual c+課程設計案例精編 嚴華峰 中國水利水電出版社 7-5084-2007-1 2004 4.visual c+課程設計與系統(tǒng)開發(fā)案例 伍俊良 清華大學出版社 7-302-05968-3 2

6、0025.visual c+語言課程設計 : 案例精選與編程指導 陳清華朱紅 東南大學出版社 7-81089-275-4 2003 6.visualc+課程設計案例精編 中國水利水電出版社 7-5084-1004-1 2002 7.數(shù)據(jù)結(jié)構課程設計案例精編 : 用c/c+描述 李建學李光元吳春芳 清華大學出版社 7-302-14536-9 2007 （編程平臺不限，vc+, c+ builder等等。）目 錄課題1第一章 拓撲排序（一）目的與要求(二)設計方法與原理 (三)需求分析 第二章 總體設計（一）系統(tǒng)流程圖 （二）詳細設計第三章 系統(tǒng)調(diào)試 （一）系統(tǒng)調(diào)試（二）結(jié)果分析第四章 總結(jié)附錄：

7、源程序課題2第一章 成績管理 （一）目的與要求(二)設計方法與原理 (三)需求分析 第二章 總體設計（一）系統(tǒng)流程圖 （二）詳細設計第三章 系統(tǒng)調(diào)試（一）系統(tǒng)調(diào)試（二）結(jié)果分析第四章 總結(jié)附錄：源程序課題1第1章 ：拓撲排序（1）目的與要求： 目的： （1）要求學生達到熟練掌握語言的基本知識和技能； （2）基本掌握面向?qū)ο蟪绦蛟O計的基本思路和方法； （3）能夠利用所學的基本知識和技能，解決簡單的程序設計問題。 要求： （1）選擇合適的存儲結(jié)構，建立有向無環(huán)圖，并輸出該圖； （2）實現(xiàn)拓撲排序算法； （3）運用拓撲排序?qū)崿F(xiàn)對教學計劃安排的檢驗。（2）設計方法與原理 在aov網(wǎng)中為了更好地完成工程

8、，必須滿足活動之間先后關系，需要將各活動排一個先后次序即為拓撲排序。拓撲排序可以應用于教學計劃的安排，根據(jù)課程之間的依賴關系，制定課程安排計劃。按照用戶輸入的課程數(shù)，課程間的先后關系數(shù)目以及課程間兩兩間的先后關系，程序執(zhí)行后會給出符合拓撲排序的課程安排計劃。（3）需求分析 程序的功能： 該程序的功能主要是根據(jù)圖的拓撲排序算法，依某專業(yè)的課程先、后修關系圖，實現(xiàn)該專業(yè)課程的排布。其中，每門課程需設定課時，而各學期的總課時不能超過上限。 輸入輸出要求： 首先，創(chuàng)建課程先、后關系圖。其中，需要輸入該關系圖的結(jié)點數(shù)(課程數(shù))、結(jié)點信息及弧的信息等；然后，輸入該專業(yè)課程的學期數(shù)，并在拓撲排序過程中，依次

9、輸入某學期的課程安排。所以，最終輸出為各個學期所安排的課程結(jié)果，并且，課程安排符合課程先、后關系圖的一個拓撲排序。第2章 ：總體設計（1）系統(tǒng)流程圖 1.1.1模塊功能流程圖 程序調(diào)用關系及模塊功能運行流程如下： 結(jié)束拓撲排序創(chuàng)建圖退出系統(tǒng)分支選擇處理 主函數(shù)main() 開始 1 2 3 圖1.1 程序調(diào)用關系及模塊功能流程圖 1.1.2數(shù)據(jù)結(jié)構及數(shù)據(jù)類型 圖的存儲結(jié)構有鄰接矩陣和鄰接表。在該程序中采用了鄰接表來存儲有向圖。在鄰接表中，需要定義頭結(jié)點的結(jié)構體數(shù)據(jù)類型，用以存儲圖的結(jié)點信息，并且在每個頭結(jié)點后連接一個單鏈表，用以存儲以該頭結(jié)點為弧尾，鏈表中結(jié)點為弧頭的弧。所以還需定義表結(jié)點的結(jié)

10、構體數(shù)據(jù)類型，用以存儲圖中弧的信息。最后，定義有向圖的結(jié)構體數(shù)據(jù)類型，其中的數(shù)據(jù)項包含一個指向頭結(jié)點首地址的指針和頂點數(shù)、弧數(shù)的整型數(shù)據(jù)類型。 1.1.3 拓撲排序算法 拓撲排序算法描述如下： (1)在有向圖中選一個沒有前驅(qū)的頂點且輸出之。即入度為零的結(jié)點。 (2)從圖中刪除該頂點和所有以它為尾的弧。即以該結(jié)點為弧尾的弧的弧頭結(jié)點的入度值減一。 (3)重復上述兩步，直至全部結(jié)點均已輸出，或者當前結(jié)點中不存在無前驅(qū)的頂點為止。后一種情況則說明有向圖中存在環(huán)，拓撲排序失敗。 然而，在此課題中是為了依拓撲排序算法而設計課程的安排序列。顯然，在同一學期里的課程是相互獨立的，不存在先、后修關系。由此，對

11、于某個學期課程的安排，其安排的課程范圍是有向圖中某次拓撲排序中所有沒有前驅(qū)頂點結(jié)點的集合，則該學期課程的安排可以在該集合中選擇，并且選擇結(jié)果滿足的總課時沒有超過上限。同時，由此次選擇結(jié)果，可以產(chǎn)生下個學期課程安排的范圍。重復上述操作，直至所有課程都選擇完。另外，還應設計一個能夠檢測所有課程是否在規(guī)定的學期內(nèi)修完。若檢測到在規(guī)定學期內(nèi)課程沒有修完，則需重新設定學期數(shù)或者重新進行課程安排。（2）詳細設計 1.2.1 采用c語言定義結(jié)構體數(shù)據(jù)類型 頭結(jié)點的頂點信息結(jié)構體數(shù)據(jù)類型 typedef struct vertextype char name20;/頂點編號，即課程編號 cha

12、r sbname20;/課程名稱 int outdegree;/頂點的出度 int indegree;/頂點的入度 int weight;/課時 bool mark;/在拓撲排序時，標記該結(jié)點是否已訪問 int id;/確定該課程屬于哪個學期 vertextype; 頭結(jié)點結(jié)構體數(shù)據(jù)類型 typedef struct vnode vertextype data;/頂點信息 arcnode *first;/指向第一條依附該結(jié)點的弧的指針 vnode; 表結(jié)點結(jié)構體數(shù)據(jù)類型 typedef struct arcnode int adjvex;/該弧所指向的頂點的位置

13、 struct arcnode*next;/指向下一條弧的指針 arcnode; 圖的結(jié)構體數(shù)據(jù)類型 typedef struct graph vnode *head;/指向頭結(jié)點首地址的指針 int vexnum,arcnum;/圖的定點數(shù)和弧數(shù) graph; 學期課程結(jié)構體數(shù)據(jù)類型 typedef struct subject int count;/某學期所安排的課程數(shù) int *head;/某學期所安排課程對應結(jié)點在圖中的存儲置 subject,*psubject; 1.2.2 各模塊的類c碼算法 創(chuàng)建有向圖的類c碼算法： status g

14、create(graph&g) scanf("%d",g.vexnum); if(!(g.head=(vnode*)malloc(g.vexnum*sizeof(vnode) exit(overflow); for(i=0;i<g.vexnum;i+) scanf("%s%s%d",&g., &g.headi.data.sbname,&g.headi.data.weight); /輸入結(jié)點信息，各頭結(jié)點的入度、出度、學期編號id均初始化為零 /訪問標記mark初始化為false,并給指針

15、域first分配內(nèi)存空間 j=0; while(1)/輸入弧，并以輸入字符"#"結(jié)束 scanf("%s%s",ch1,ch2); if(strcmp(ch1,"#")=0) break; n=glocatevex(g,ch1);/獲取弧尾結(jié)點存儲位置 m=glocatevex(g,ch2);/獲取弧頭結(jié)點存儲位置 if(n!=-1&&m!=-1)/輸入的弧存在 j+; ptr1=g.headn.first; while(ptr1->next!=null) ptr1=ptr1->next; if(!(ptr

16、2=(arcnode*)malloc(sizeof( arcnode)exit(overflow); ptr2->adjvex=m; ptr1->next=ptr2; ptr2->next=null; g.headn.data.outdegree+; g.headm.data.indegree+; return ok; 拓撲排序的類c碼算法： status gsort(graph g,int max) scanf("%d",&n);/輸入學期數(shù) psubject p;/對p分配連續(xù)的n個空間，并對p進行初始化 /其中，count初始

17、化為零，指針head分配連續(xù)的g.vexnum個空間 k=0;i=0; while(k<=n) while(i<g.vexnum) max=0;x=0;mark=false; /max標記某學期的總課時，x標記某學期的課程數(shù) /mark用于判斷有向圖中是否存在回路 for(j=0;j<g.vexnum;j+) if(g.headj.data.indegree=0&&g.headj.data. mark=false) printf(g.headj.data);/輸出該頭結(jié)點信息 mark=true; if(g.headj.data.id=k) g.headj.d

18、ata.id+; if(!mark)return error;/圖中存在回路，拓撲排序失敗 while(1)/根據(jù)當前學期輸出的可安排課程，選擇所要安排的 課程，輸入"#"表示當前學期課程選擇結(jié)束 scanf("%s",name); if(strcmp(name,"#")=0) break; m=glocatevex(g,name);/獲取當前課程所對應頭 結(jié)點的存儲位置 if(m!=-1) if(g.headm.data.indegree=0&& g.headm.data.id=k+1) /所選課程符合當前學期安排

19、max+=g.headm.data.weight; if(max>max) max-=g.headm.data.weight; /若所選課程的總課時超出上限，則選擇其 它可選課程或退出當前學期的課程安排 選擇 else if(k=n) break;/課程安排已超過所安排的 學期數(shù)，則推出課程選擇 pk.headx=m;/存儲該學期所選 課程所對應頭結(jié)點在在圖中的存儲位置 g.headm.data.mark=true;/標 記該頭結(jié)點已被排序了 ptr2=g.headm.first->next; i+; x+; while(ptr2!=null)/使以該頭結(jié) 點為弧尾的所有弧的弧頭結(jié)

20、點的入度減 一及其學期標號作相應的變換 if(g.headptr2->adjvex. data.id=k+1) g.headptr2->adjvex. data.id+; g.headptr2->adjvex. data.indegree-; ptr2=ptr2->next; if(n=k)/若課程安排已超過所安排的學期數(shù)，則重新設定 學期數(shù)或重新進行課程安排 scanf("%d",&y);/輸入操作選擇項 switch(y) case 1:/重新設定學期數(shù) scanf("%d",&n);/重新輸入學期數(shù)，并對p重

21、 新分配連續(xù)的n個空間，并對其進行初始化 break; case 2:/重新進行課程安排 break; default:break; g=setg(g);/對圖進行初始化處理，并依存儲結(jié)構產(chǎn)生各 頭結(jié)點的度值 i=0;k=0; continue; pk.count=x; k+; /課程以選完，而學期的課程沒有安排完 if(k=n) break; printf(".n");/輸出課程已安排完，該學期沒有課程 安排 k+; printf(p);/輸出各學期的課程安排 return ok; 第3章 ：系統(tǒng)調(diào)試（1）系統(tǒng)調(diào)試 1.3.1 調(diào)試分析 測試數(shù)據(jù)：(如下圖

22、所示的有向圖) 194212101136578 圖1.2 課程先、后修關系圖 另外，學期課時上限數(shù)為：120 測試方案 (1)正確的輸入及輸出： 1、構建圖1.2所示的有向圖 圖1.3 輸入圖中的頂點信息 圖 1.4 輸入圖中的弧 2、拓撲排序過程(即課程安排過程) 圖 1.5 輸入學期課時上限數(shù)及學期數(shù) 圖 1.6 第一學期的課程安排 圖1.7 第二、三學期的課程安排 圖1.8 第四學期的課程安排 圖 1.9 學期課程安排已超過學期數(shù)并重新輸入學期數(shù)或重新安排學期課程 圖1.10 重新安排第一、二學期的課程 圖1.11 重新安排第三、四學期的課程 圖1.12 重新安排第五、六

23、學期的課程 圖1.13 各學期課程安排結(jié)果 3、構建一個存在環(huán)的有向圖并進行拓撲排序 圖1.14 構建一個存在環(huán)的有向圖 圖1.15 因圖中存在回路，拓撲排序失敗 (2)錯誤的輸入及輸出 若在創(chuàng)建圖時，輸入有相同編號的結(jié)點，則可能使程序的輸出發(fā)生錯誤,使程序不能結(jié)束。 圖1.16 在創(chuàng)建圖的過程中，輸入的結(jié)點編號存在相同 圖1.17 因圖中有結(jié)點編號相同的結(jié)點而產(chǎn)生錯誤的選定課程的結(jié)果（2）結(jié)果分析 在開始調(diào)試程序的過程中，遇到的主要問題是邏輯錯誤及程序不能實現(xiàn)所需的要求。第一個問題是：怎樣依拓撲排序的算法來產(chǎn)生某個學期的課程安排，另外，怎樣確定某個學期到底安排幾門課程。若把所有拓撲排序結(jié)果都

24、輸出出來，顯然，這是一個非常不好的想法。經(jīng)過對這個問題的思考后，若把某個學期所能選的課都顯示出來，然后，用戶根據(jù)顯示出來的課程來安排該學期的課程，隨后，依安排結(jié)果產(chǎn)生下個學期所能選的課程的集合。該種想法不僅解決了怎樣依拓撲排序來安排某個學期的課程，并且給用戶安排課程提供了很大的靈活性，用戶可以根據(jù)需求來安排某個學期的課程。第一個問題得到解決并編寫程序后，便產(chǎn)生了第二個問題：在產(chǎn)生的某個學期所能安排的課程范圍里存在有先后關系的課程或程序不能結(jié)束。經(jīng)過分析發(fā)現(xiàn)：在選取某個學期所能安排課程的集合的過程中，會使圖中的某些結(jié)點的入度由非零減到成零，使原本應為下一學期的課程變換到當前學期中，所以應設定一個

25、課程學期標號，標記課程在拓撲排序過程中所對應的學期。由此，在頭結(jié)點的信息域中增設了一個整型變量id，用以標記在拓撲排序中該結(jié)點應該屬于哪個學期，并為拓撲排序增設了一個條件限制。第四章：總結(jié) 通過對該課題的設計過程，不僅讓我對圖的存儲方法及圖的拓撲排序算法加深了理解，更讓我深深的了解到理論知識與實踐應用上的區(qū)別。該課題在理論上是應用了圖的拓撲排序的思想，然而它不是單純的拓撲排序，而是在拓撲排序的基礎上，應用圖的拓撲排序來解決課程安排的問題。課程安排的結(jié)果不僅要符合拓撲排序的要求，并且在同一學期的課程是相互獨立的，所以，這就要設計新的算法，對拓撲序列的產(chǎn)生添加新的限制條件。同時，也讓我認識到算法在

26、程序設計中的重要性，算法是程序設計的靈魂。附錄：源程序#include<stdio.h>#include<stdlib.h>#include<string.h>/表結(jié)點typedef struct arcnodeint adjvex;struct arcnode*next;arcnode;/頂點信息typedef struct vertextypechar name20;char sbname20;int outdegree;int indegree;int weight;bool mark;int id;vertextype;/頭結(jié)點typedef str

27、uct vnodevertextype data;arcnode*first;vnode;/圖數(shù)據(jù)類型typedef struct graphvnode *head;int vexnum,arcnum;graph;/存儲課程信息的結(jié)構體數(shù)據(jù)類型typedef struct subjectint count;int*head;subjiect,*psubject;int glocatevex(graph g,char ch)for(int i=0;i<g.vexnum;i+)if(!strcmp(g.,ch)return i;printf("改圖中沒

28、有該結(jié)點!n");return -1;/建立有向圖-鄰接表graph gcreate()graph g;arcnode*ptr1,*ptr2;char ch110,ch210;int n,m,j=0;printf(" 創(chuàng)建該專業(yè)課程先、后修關系圖:請輸入圖的頂點數(shù)(課程數(shù))及弧數(shù)：n");printf(" 頂點數(shù)：vexnum=");scanf("%d",&g.vexnum);printf("n 輸入圖中頂點的基本信息：(課程信息)n"); printf(" -課程編號-課程名稱-課時-

29、n");g.head=(vnode*)malloc(g.vexnum*sizeof(vnode);if(g.head=null)printf("內(nèi)存分配錯誤!n");exit(0);for(int i=0;i<g.vexnum;i+)scanf("%s%s%d",&g.,&g.headi.data.sbname,&g.headi.data.weight);g.headi.data.outdegree=0;g.headi.data.indegree=0;g.headi.data.mark

30、=false;g.headi.data.id=0;if(!(g.headi.first=(arcnode*)malloc(sizeof(arcnode)printf("內(nèi)存分配錯誤!n");exit(0);g.headi.first->next=null;printf("n 輸入圖中弧的基本信息：n");printf(" -課程編號尾結(jié)點-課程編號頭結(jié)點-(以輸入""#""表示結(jié)束)n");while(1)scanf("%s",ch1);if(strcmp(ch1,&q

31、uot;#")=0)break;scanf("%s",ch2); n=glocatevex(g,ch1);m=glocatevex(g,ch2);if(n!=-1&&m!=-1)j+; ptr1=g.headn.first; while(ptr1->next!=null) ptr1=ptr1->next; if(!(ptr2=(arcnode*)malloc(sizeof(arcnode) printf("內(nèi)存分配錯誤!n"); exit(0); ptr2->adjvex=m; ptr1->next=pt

32、r2; ptr2->next=null; g.headn.data.outdegree+; g.headm.data.indegree+;elseprintf("在此圖中，沒有該弧:%s->%sn",ch1,ch2);printf("nn");g.arcnum=j;return g;/拓撲排序void gsort(graph g,int max)int i=0,max,k=0,m,n,x,y,t,u;char name20,ch;psubject p;arcnode*ptr2;printf("請輸入該專業(yè)學習的學期數(shù)：")

33、;scanf("%d",&n);if(!(p=(psubject)malloc(n*sizeof(subject)printf("內(nèi)存分配錯誤!n");exit(0);for(int l=0;l<n;l+)if(!(pl.head=(int*)malloc(g.vexnum*sizeof(int)printf("內(nèi)存分配錯誤!n");exit(0);pl.count=0;while(k<=n) while(i<g.vexnum)printf("第%d學期的課程安排有：(剩余%d門課程未安排)n&qu

34、ot;,k+1,g.vexnum-i);printf("-課程編號-課程名稱-課時-n");max=0;x=0;for(int j=0;j<g.vexnum;j+)if(g.headj.data.indegree=0&&g.headj.data.mark=false) printf(" %s %s %dn",g.,g.headj.data.sbname,g.headj.data.weight);if(g.headj.data.id=k) g.headj.data.id+;printf("請選擇

35、該學期要安排的課程：(以輸入""#""結(jié)束)n");while(1) scanf("%s",name);if(strcmp(name,"#")=0)break;m=glocatevex(g,name);if(m!=-1)if(g.headm.data.indegree=0&&g.headm.data.id=k+1)max+=g.headm.data.weight;if(max>max)printf("課時超限，請重新選擇其他課程或輸入""#"&

36、quot;退出選擇!n");max-=g.headm.data.weight;else if(k=n) break; pk.headx=m; ptr2=g.headm.first->next; g.headm.data.mark=true; i+; x+; while(ptr2!=null)if(g.headptr2->adjvex.data.id=k+1)g.headptr2->adjvex.data.id+; g.headptr2->adjvex.data.indegree-; ptr2=ptr2->next; elseprintf("選擇

37、課程%s不合理!請重新選擇!n",name);elseprintf("輸入的課程編號%s錯誤!請重新輸入!n",name);if(k=n) printf("課程安排已超出學期數(shù)！請選擇以下選項，重新制定課程安排：n"); printf(" 1、重新設定學期安排n"); printf(" 2、重新安排學期課程n"); while(1) ch=getchar(); if(ch='n') continue; if(ch>=49&&ch<=50) break; else printf("選項輸入錯誤!請重新選擇!n"); y=ch-48; switch(y) case 1: for( u=0;u<n;u+) free(pu.head); free(p); printf("輸入學期數(shù)："); scanf("%d",&n); if(!(p=(psubject)malloc(n*sizeof(subject) printf("內(nèi)存分配錯誤!n"); exit(0); for(t=0;t<n;t+) if(!(pt.head=(int*)malloc(