數(shù)據(jù)結(jié)構(gòu)(C++)課程設(shè)計報告教學(xué)計劃編制問題

1、上海電力學(xué)院數(shù)據(jù)結(jié)構(gòu)（c+）課程設(shè)計題目: 教學(xué)計劃編制問題 姓 名： 石鑫磊 學(xué) 號： 20113296 院系： 計算機(jī)科學(xué)與技術(shù)學(xué)院 專業(yè)年級： 信息安全2011級 2013年07月04日一、設(shè)計題目大學(xué)的每個專業(yè)都要編制教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限都相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程的開設(shè)時間的安排必須滿足先修關(guān)系。每個課程的先修關(guān)系都是確定的，可以有任意多門，也可以沒有。每一門課程恰好一個學(xué)期。試在這樣的情況下設(shè)置一個教學(xué)計劃編制程序。在大學(xué)的某個專業(yè)中選取幾個課程作為頂點(diǎn),通過各門課的先修關(guān)系來構(gòu)建個圖,該圖用鄰接表來

2、存儲,鄰接表的頭結(jié)點(diǎn)存儲每門課的信息。本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信息來編排出每學(xué)期要學(xué)的課程。二、需求分析（一）運(yùn)行環(huán)境（軟、硬件環(huán)境）設(shè)計環(huán)境和器材硬件：計算機(jī)軟件：microsoft visula c+在本課程設(shè)計中，系統(tǒng)開發(fā)平臺為windows xp或win 7，程序運(yùn)行環(huán)境為visual c+ 6.0，程序設(shè)計語言為c+。visual c+一般分為三個版本：學(xué)習(xí)版、專業(yè)版和企業(yè)版，不同版本適合于不同類型的應(yīng)用開發(fā)。實(shí)驗(yàn)中可以使用這三個版本的任意一種，在本課程設(shè)計中，以visual c+ 6.0為編程環(huán)境。visual c+以擁有“語法高亮”，intellisense（

3、自動編譯功能）以及高級除錯功能而著稱。比如，它允許用戶進(jìn)行遠(yuǎn)程調(diào)試和單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動正在調(diào)試的程序。其編譯及建置系統(tǒng)以預(yù)編譯頭文件、最小重建功能及累加鏈接著稱。這些特征明顯縮短程式編輯、編譯及鏈接的時間花費(fèi)，在大型軟件計劃上尤其顯著。visual c+ 6.0秉承visual c+ 以前版本的優(yōu)異特性，為用戶提供了一套良好的開發(fā)環(huán)境，主要包括文本編輯器、資源編輯器、工程創(chuàng)建工具和debugger調(diào)試器等等。用戶可以在集成開發(fā)環(huán)境中創(chuàng)建工程，打開工程，建立、打開和編輯文本，編譯、鏈接、運(yùn)行和調(diào)試應(yīng)用程序。（二）輸入的形式和輸入值的范圍數(shù)據(jù)輸入

4、的方式是鍵盤輸入。輸入的數(shù)據(jù)多是整型的或是浮點(diǎn)型的，還有一些字符（以中文的形式）。輸入的數(shù)值型的數(shù)據(jù)大都是小于100的數(shù)值。（三）輸出的形式描述輸出的是教學(xué)編制計劃，就是形如：“第二學(xué)期學(xué)的課程有:普通物理 線性代數(shù) 匯編語言”這樣的形式。（四）功能描述 輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號。允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔?；否則將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式自行設(shè)計。（五）測試數(shù)據(jù)學(xué)

5、期總數(shù)：6 學(xué)分上限：10該專業(yè)共開設(shè)12門課，課程號從0112，學(xué)分順序?yàn)?，3，4，2，2，4，4，4，7，5，2，3。三、概要設(shè)計（一）抽象數(shù)據(jù)類型定義描述（對各類的成員及成員函數(shù)進(jìn)行抽象描述，參見書或ppt及實(shí)驗(yàn)）抽象數(shù)據(jù)類型：為實(shí)現(xiàn)上述功能需建立一個結(jié)點(diǎn)類，線性表類，圖類。adt graph數(shù)據(jù)對象v:v是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系r:r=vrvr=(v,w)|v,wv,(v,w)表示v和w之間存在直接先修關(guān)系基本操作p:void creatpre(algraph *cgraph);void findindegree(algraph *cgraph,int i

6、ndegree);void layout1(algraph *cgraph,queue *q);void layout2(algraph *cgraph,queue *q);adt graph隊列的定義:adt list數(shù)據(jù)對象:d=ai|aielemset,i=1,2,n,n=0數(shù)據(jù)關(guān)系:r1=ai-1 ai|ai-1,aid,i=2,n基本操作:void queue_init(queue *q);void queue_in(queue *q,int x);int queue_out(queue *q);int queue_empty(queue *q);adt stack（二）功能模塊設(shè)計

7、主程序：void main()int choice;queue q;queue.queue_init(&q);algraph cgraph;cgraph=graph.input();system(cls);graph.output(cgraph);coutendlendl;judgement.judgingcricle(&cgraph,&q);if(!whethercricle)while(1)cout請選擇編排策略:tendl;cout1.使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻;tendl;cout2.使課程盡可能地集中在前幾個學(xué)期中。tendl;coutchoice;system(cls);i

8、f(choice=1) edit.layout1(&cgraph,&q);else edit.layout2(&cgraph,&q);cout請選擇繼續(xù)編排策略或退出程序（0退出 1繼續(xù)）:tchoice;system(cls);if(choice=0)break; （三）模塊層次調(diào)用關(guān)系本程序只有兩個模塊,調(diào)用關(guān)系簡單主程序模塊拓?fù)渑判蚰Ktopsort流程圖：所有頂點(diǎn)是否處理完？將入度為0的頂點(diǎn)入棧是否為空？用數(shù)組outles保存每次入棧的入度為0的頂點(diǎn)；并進(jìn)行相應(yīng)的調(diào)整。將當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)減1輸出課程名稱對每個學(xué)期的課程量進(jìn)行控制鄰接表類成員函數(shù)topsort否是否是運(yùn)行結(jié)束鄰接表構(gòu)造

9、函數(shù)algraph初始化頂點(diǎn)表初始化邊表，并在相應(yīng)的邊表中插入結(jié)點(diǎn)結(jié)束運(yùn)行 鄰接表algraph的構(gòu)造函數(shù)四、詳細(xì)設(shè)計教學(xué)計劃編制系統(tǒng)主要是處理課程之間的依賴關(guān)系。表列出了若干門計算機(jī)系本科課程，其中有些課程不要求先修課程，例如，c1是獨(dú)立于其他課程的基礎(chǔ)課，而有些課程卻需要有先修課程，比如，學(xué)完程序設(shè)計語言c+和離散數(shù)學(xué)后才能學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。課程代號課程名稱先修課程c1高等數(shù)學(xué)無c2計算機(jī)科學(xué)導(dǎo)論無c3離散數(shù)學(xué)c1c4程序設(shè)計語言c+c1、c2c5數(shù)據(jù)結(jié)構(gòu)c3、c4c6計算機(jī)原理c2、c4c7數(shù)據(jù)庫原理c4、c5、c6先修課程規(guī)定了課程之間的依賴關(guān)系，這種關(guān)系可以用aov網(wǎng)來表示，其中頂點(diǎn)表示

10、課程，弧表示依賴關(guān)系。c1c7c6c4c5c3c2程序的主要功能是實(shí)現(xiàn)課程的排序，以滿足同一學(xué)期所修的課程相互之間無依賴關(guān)系，并且已修完其所有先修課程。本程序需要基于圖的基本操作來實(shí)現(xiàn)算法的基本思想： 1、圖的構(gòu)建：建立一個結(jié)點(diǎn)類，類的元素有字符型變量用來存儲字母，整形變量用來存儲位置，該類型的指針，指向下一個元素。建立一個線性表類，完成線性表的構(gòu)建。建立一個圖類，完成圖的信息的讀取，（如有n個點(diǎn)，則建立n個線性表，將每個結(jié)點(diǎn)與其指向的結(jié)點(diǎn)組成一個線性表，并記錄線性表的長度）。2、topsort算法：先計算每個點(diǎn)的入度，保存在數(shù)組中。找到第一個入度為0的點(diǎn)，將該點(diǎn)所連的各點(diǎn)的入度減一。再在這些

11、點(diǎn)中找入度為0 的點(diǎn)。如果找到，重復(fù)上述操作。如果找不到，則跳出while循環(huán)，再搜索其他的點(diǎn)，看入度是否為0。再重復(fù)上述操作，如果所有的入度為0的點(diǎn)都被尋找到，但個數(shù)少于輸入頂點(diǎn)的個數(shù)，說明該圖存在環(huán)。3、 鄰接表類的定義鄰接表是一種順序存儲與鏈接存儲相結(jié)合的存儲方法。在鄰接表中存在兩種結(jié)點(diǎn)結(jié)構(gòu)：頂點(diǎn)表結(jié)點(diǎn)和邊表結(jié)點(diǎn)。頭結(jié)點(diǎn)表結(jié)點(diǎn) nextarcadjvexfirstarcvex五、調(diào)試分析包括調(diào)試過程中遇到的問題及解決的方法、算法的時間空間復(fù)雜性分析、經(jīng)驗(yàn)體會。（一）實(shí)驗(yàn)過程中出現(xiàn)的問題及解決方法我在實(shí)驗(yàn)過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，網(wǎng)上也只有拓

12、撲排序的算法，對于課程設(shè)計要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。（二）實(shí)驗(yàn)體會上機(jī)實(shí)踐是學(xué)生對本門課程所學(xué)知識的一種全面、綜合的能力訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成必不可少的一個教學(xué)環(huán)節(jié)，也是對課堂教學(xué)效果的一種檢驗(yàn)。通常，實(shí)習(xí)題中的問題比平時的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)題注重原理與應(yīng)用的結(jié)合，目的讓學(xué)生學(xué)會如何把書上學(xué)到的知識運(yùn)用于解決實(shí)際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計工作所必需的基本技能。同時，通過實(shí)踐能使書上的知識變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的

13、作用。平時的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)習(xí)題是軟件設(shè)計的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧，可以多人合作，有利于一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，實(shí)踐環(huán)節(jié)中有很重要的一點(diǎn)，就是機(jī)器是比任何教師都嚴(yán)格的主考官。經(jīng)過此次課程設(shè)計，我認(rèn)識到了理論與實(shí)踐結(jié)合的重要性，僅僅只是從課本上學(xué)到算法原理是遠(yuǎn)遠(yuǎn)不夠的。在實(shí)踐中，我們總會出現(xiàn)許多錯誤。這就要求我們以一個腳踏實(shí)地的態(tài)度來處理問題。我深刻地認(rèn)識到自己寫程序的不足，使我們學(xué)到了好多有用的知識，讓我們明白了c+語言的語句用法。六、測試結(jié)果要求輸入學(xué)期總數(shù)、一個學(xué)期的學(xué)分上限、需要編排

14、課程總數(shù)、課程名、課程號、該課程的學(xué)分，按照出現(xiàn)的每一步來輸入該課程設(shè)計所提供的相關(guān)數(shù)據(jù)。學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學(xué)分順序?yàn)?，3，4，2，2，4，4，4，7，5，2，3。然后還要輸入課程先修課程總數(shù)，可以算出有16種關(guān)系，分別輸出。接著程序會根據(jù)這些數(shù)據(jù)，自動生成建立好的鄰接表，用戶可以根據(jù)系統(tǒng)顯示的選擇編排策略進(jìn)行選擇，有兩種編排策略，最后結(jié)果體現(xiàn)在實(shí)驗(yàn)的正確測試結(jié)果里。輸入的內(nèi)容如下:課程編號 課程名稱 學(xué)分 先決條件01 計算機(jī)基礎(chǔ) 2 無02 離散數(shù)學(xué) 3 0103 數(shù)據(jù)結(jié)構(gòu) 4 01，02 04 匯編語言 2 0105 語言的設(shè)計和分

15、析 2 03，04 06 計算機(jī)原理 4 1007 編譯原理 4 05，03 08 操作系統(tǒng) 4 03，0609 高等數(shù)學(xué) 7 無 10 普通物理 5 0911 線性代數(shù) 2 0912 數(shù)值分析 3 09，11，01七 、附錄：程序設(shè)計源代碼#include#include#include#includeusing namespace std;#define null 0#define max_course_num 100/最大課程個數(shù)typedef struct char c3; cid; /課程號typedef struct course cid id3; char name30; flo

16、at xf; course;/課程typedef struct precourse int adjvex;struct precourse *nextarc; precourse;/先修的課程節(jié)點(diǎn)typedef structcourse course;precourse *firstarc;coursenode;/課程節(jié)點(diǎn)typedef structcoursenode coursesmax_course_num;/鄰接表int xqs;int num;float xfsx;algraph;/課程圖typedef struct int datamax_course_num;int f,r;qu

17、eue;int whethercricle=0;int jxq; class queuepublic:void queue_init(queue *q);void queue_in(queue *q,int x);int queue_out(queue *q);int queue_empty(queue *q);queue;void queue:queue_init(queue *q)/隊初始化q-f=q-r=0;void queue:queue_in(queue *q,int x)/入隊if(q-r+1)%max_course_num=q-f)cout隊滿tr=(q-r+1)%max_cou

18、rse_num;q-dataq-r=x;int queue:queue_out(queue *q)/出隊if(q-f=q-r)cout隊空tf=(q-f+1)%max_course_num;return q-dataq-f;int queue:queue_empty(queue *q)/隊判空 1為空if(q-f=q-r)return 1;else return 0;class graphpublic:algraph input();void output(algraph cgraph);void creatpre(algraph *cgraph);graph;void graph:creat

19、pre(algraph *cgraph)/建立先修關(guān)系system(cls);int choice;int i,n; int j;precourse *p,*q;coutendl建立先修關(guān)系:tendl;coutendl輸入的每一門課程號的編號：tendl;for(i=0;inum;i+)if(i%4=0)coutendl;cout(i+1coursesi.course.id);coutendl;coutn請根據(jù)以上的編號，輸入每一門課程的先修課程號的編號（輸入0 表示沒有或結(jié)束）：tendl;for(i=0;inum;i+)printf(%s的先修課程:,cgraph-coursesi.co

20、urse.id);cinj;n=0;while(j)/判斷輸入的課程編號是否正確while(jcgraph-num|j=i+1)if(j=i+1)cout先修課程號不可能是本課程號n;elsecout輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中endl;coutj;p=(precourse *)malloc(sizeof(precourse);p-adjvex=j-1;p-nextarc=null;if(n=0)cgraph-coursesi.firstarc=p;q=cgraph-coursesi.firstarc;n+;elseq-nextarc=p;q=p;n+;cinj;cout(1)重

21、新建立先修關(guān)系t(2)確定n;coutchoice;if(choice=1)creatpre(cgraph);jxq=0;algraph graph:input()/輸入并建立課程圖algraph cgraph;int xqzs=0,kczs=0; int i;int choice;float xf,xfsx=0;cout教學(xué)計劃編制nendl;cout輸入?yún)?shù):n;coutxqzs;cgraph.xqs=xqzs;coutkczs;cgraph.num=kczs;coutxfsx;cgraph.xfsx=xfsx;cout4.每門課的課程號(固定占3位的字母數(shù)字串)、課程名、學(xué)分endl;f

22、or(i=0;ikczs;i+)/輸入課程號，課程名，學(xué)分cout課程號:;scanf(%s,cgraph.coursesi.course.id);cout課程名:;scanf(%s,cg);coutxf;coutxfsx|xf=0)/判斷輸入的學(xué)分是否合格coutxf;cgraph.coursesi.course.xf=xf;cgraph.coursesi.firstarc=null;cout(1)重新輸入t(2)確定endl;coutchoice;if(choice=1)system(cls);input();else creatpre(&

23、cgraph);/建立先修關(guān)系return cgraph;void graph:output(algraph cgraph)/輸出先修關(guān)系int i,j,n;precourse *p;cout先修關(guān)系如下:nendl;cout課程編號t課程名稱t先決條件endl;for(i=0;iadjvex;printf( %s ,cgraph.coursesn.course.id);p=p-nextarc;j+;if(j=0)cout 無;coutendl;class judgementpublic:void findindegree(algraph *cgraph,int indegree);void

24、judgingcricle(algraph *cgraph,queue *q2);judgement;void judgement:findindegree(algraph *cgraph,int indegree)int i;precourse *p;for(i=0;inum;i+)indegreei=0;p=cgraph-coursesi.firstarc;while(p)indegreei+;p=p-nextarc;void judgement:judgingcricle(algraph *cgraph,queue *q2)/判斷是否有環(huán)和課程入隊int indegreemax_cour

25、se_num;/入度int i,m,j,pd=0;float xf=0;precourse *p;queue q;queue.queue_init(&q);/隊初始化findindegree(cgraph,indegree);/找入度for(i=0;inum;i+)if(indegreei=0&(xf+cgraph-coursesi.course.xf)xfsx)queue.queue_in(&q,i);indegreei-;xf+=cgraph-coursesi.course.xf;m=0;xf=0;queue.queue_in(&q,-1); /把-1入隊 用來判斷jxq+;while(1

26、)i=queue.queue_out(&q);queue.queue_in(q2,i);if(i!=-1)m+;for(j=0;jnum;j+)if(j!=i)if(indegreej=0&(xf+cgraph-coursesj.course.xf)xfsx)queue.queue_in(&q,j);indegreej-;xf+=cgraph-coursesj.course.xf;elsep=cgraph-coursesj.firstarc;while(p)if(p-adjvex=i)indegreej-;if(indegreej=0&(xf+cgraph-coursesj.course.xf

27、)xfsx)queue.queue_in(&q,j);indegreej-;pd=1;xf+=cgraph-coursesj.course.xf;p=p-nextarc;elseif(pd)pd=0;queue.queue_in(&q,-1);jxq+;xf=0;else break;if(jxqcgraph-xqs)coutendl錯誤報告：n在xqs學(xué)期內(nèi)是無法修完這些課程endl;exit(0);if(mnum)coutn錯誤報告：endl;cout存在循環(huán)，因此課程安排不了endl;whethercricle=1;queue.queue_in(q2,-1);class editpublic:void layout1(algraph *cgraph,queue *q);void layout2(algraph *cgraph,queue *q);edit;void edit:layout1(algraph *cgraph,queue *q)coutn學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻:nnum/cgraph-xqs*1.0f;queue q1=*q;int n;int x;n=0;ck0=-1;for(i=0;i20;i+)j=queue.queue_out(&q1);cki=j