《程序設計課程設計》指導書2013

《《程序設計課程設計》指導書2013》由會員分享，可在線閱讀，更多相關《《程序設計課程設計》指導書2013（34頁珍藏版）》請在裝配圖網上搜索。

1、程序設計課程設計指導書軟件學院 計算機工程系2013年6月17日前 言程序設計課程設計是計算機科學與技術專業(yè)的重要實踐性課程。目的在于培養(yǎng)學生分析問題和解決問題的能力，為學生提供了一個既動手又動腦，獨立實踐的機會。將課本上的數據結構、離散數學和C語言的理論知識和實際應用問題進行有機結合，提高學生程序設計、程序調試及項目開發(fā)能力。為后續(xù)課程： 操作系統(tǒng)、軟件工程，編譯原理等課程的學習奠定必要的實踐基礎。本課程設計是利用數據結構、離散數學、C語言理論和實驗課中學到的編程知識和編程技巧，通過布置具有一定難度、一定編程量的課程設計題目，利用C語言作為開發(fā)工具，使學生通過課程設計掌握高級編程語言的知識和

2、編程技術，掌握程序設計的思想和方法，初步具備利用計算機求解實際問題的能力。通過程序設計課程設計課程的學習，能夠幫助學生加深理解數據結構、離散數學、C語言基本概念，達到培養(yǎng)學生良好程序設計的習慣和運用 C 語言編寫程序解決實際問題的能力。使學生學會把書本知識用于解決實際問題，起到深化理解和靈活掌握教學內容的目的。同時使學生在程序設計方法及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。通過該課程設計，學生應該掌握C或C+語言程序設計的方法、數據結構和離散數學理論知識，熟悉C或C+程序的開發(fā)環(huán)境及C或C+程序的調試過程，鞏固和加深對理論課中知識的理解，提高學生對所學知識的綜合運用能力；學

3、生應該具有如下基本技能：培養(yǎng)學生查閱參考資料、手冊的自學能力，通過獨立思考深入鉆研問題，學會自己分析、解決問題。通過對所選題目方案分析比較，確立方案，編制程序與調試程序。能熟練調試程序，在教師的指導下，完成課題任務。根據個人的設計調試過程，按課程設計報告的要求撰寫設計報告。選用教材及主要參考書：1 教材呼克佑. C語言程序設計. 電子工業(yè)出版社,2013嚴蔚敏. 數據結構(C語言版) 清華大學出版社，20122、主要參考書1 譚浩強. 程序設計題解與上機指導(三版) . 清華大學出版社，20122 邱仲潘. C語言參考手冊. 機械工業(yè)出版社，20043 譚浩強. C語言程序設計（三版）. 清華

4、大學出版社，20124 方世昌. 離散數學.西安電子科技大學出版社，20035 丁亞濤. C語言程序設計.高等教育出版社，2003目 錄前 言1一課程設計報告要求1二課程設計報告示例迷宮問題2三設計題目121文本文件單詞的檢索與計數122停車場管理163交通咨詢系統(tǒng)設計（最短路徑問題）174學生管理系統(tǒng)21 一課程設計報告要求課程設計報告封面應給出專業(yè)、班級、姓名、學號、指導教師和完成日期，報告開頭給出題目，內容包括以下五項：1【問題描述】簡要描述問題，然后說明程序設計的任務，程序要做什么。明確規(guī)定以下內容：（1） 輸入的形式和輸入值的范圍；（2） 輸出的形式；（3） 程序所能達到的功能；（4

5、） 測試數據：包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。2【設計需求及分析】說明本程序中用到的所有抽象數據類型的定義、主程序的流程以及各程序模塊之間的層次（調用）關系。實現設計中定義的所有數據類型，對每個操作寫出偽碼算法；對主程序和其他模塊也寫出偽碼算法（偽碼算法的詳細程度為按照偽碼算法可以在計算機鍵盤直接輸入高級程序設計語言程序）；畫出函數的調用關系圖。3【設計功能的實現】（用C或C+描述）/說明：用C或C+實現代碼設計。4【實例測試及運行結果】列出測試結果，包括輸入和輸出。測試數據應該完整、嚴格。測試分析內容包括：（1） 測試過程中遇到的問題是如何解決的以及對設計與實現的回顧

6、討論與分析；（2） 算法的時空分析和改進設想；（3） 經驗和體會。5【實現提示】使用說明：說明如何使用該程序，列出每一步的操作步驟。附錄：列出程序文件名的清單以及必要的帶注釋的源程序。心得體會等等。二課程設計報告示例迷宮問題專業(yè)： 班級： 姓名： 學號： 完成日期： 【問題描述】編制一個求解迷宮通路的程序。以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一

7、個坐標,d 表示走到下一坐標的方向。如：對于下列數據的迷宮，輸出的一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）【設計需求及分析】（1）以二維數組MAZEM+2N+2表示迷宮，其中：MAZE0J和MAZEM+1J（0JN+1）及MAZEI0和MAZEIN+1（0IM+1）為添加的一圈障礙。數組中以元素值為0表示通路，1表示障礙。限定迷宮的大小M，N10。（2）用戶以文件的形式輸入迷宮的數據：文件中第一行的數據為迷宮的行數M和列數N；從第2行至第M+1行（每行N個數）為迷宮值，同一行中的兩個數字之間用空白字符相隔。（3）迷宮的入口位置和出口位置可由用戶

8、隨時設定。（4）若設定的迷宮存在通路，則以長方陣形式將迷宮及其通路輸出到標準輸出文件（即終端）上，其中，字符“#”表示障礙，字符“*”表示路徑上的位置，字符“”表示“死胡同”，即曾經經過但不能到達出口的位置，其余用空格符表示。若設定的迷宮不存在通路，則報告相應信息。（5）本程序只求出一條成功的通路。然而，只需要對迷宮求解的函數作小量修改，便可求得全部路徑?！驹O計功能的實現】（用C或C+語言描述）說明：此內容由學生自己設計完成。提示：程序應包含的執(zhí)行命令有：1）創(chuàng)建迷宮； 2）求解迷宮； 3）輸出迷宮的解。概要設計示例如下：1設定棧的抽象數據類型定義為：ADT stack數據對象：D=ai|ai

9、charset,i=1,2,n,n0數據關系：R1=|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作結果：構造一個空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結果：將S清為空棧。StackLength(&S)初始條件：棧S已存在。操作結果：返回棧S的長度。StackEmpty(&S)初始條件：棧S已存在。操作結果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S已存在。操作結果：若棧S不空，則以e返回棧頂元素。Push(&S,e)初始條件：棧S

10、已存在。操作結果：在棧S的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S已存在。操作結果：刪除S的棧頂元素，并以e返回其值。StackTraverse(S,visit( )初始條件：棧S已存在。操作結果：從棧底到棧頂依次對S中的每個元素調用函數visit( ).ADT stack2設定迷宮的抽象數據類型為：ADT maze數據對象：D=ai,j|ai,j 、#、*，0im+1,0jn+1,m,n10數據關系：R=ROW，COLROW=|ai-1,j，ai,jD,i=1,，m+1,j=0,，n+1COL=|ai,j-1,ai,jD,i=0,，m+1,j=1,，n+1基本操作：Init

11、Maze(&M,a,row,col)初始條件：二維數組arow+2col+2已存在，其中自第1行至第row+1行、每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。操作結果：構成迷宮的字符型數組，以空白字符表示通路，以字符#表示障礙，并在迷宮四周加上一圈障礙。MazePath(&M)初始條件：迷宮M已被賦值。操作結果：若迷宮M中存在一條通路，則按如下規(guī)定改變迷宮M的狀態(tài)：以字符“*”表示路徑上的位置，字符“”表示“死胡同”；否則迷宮的狀態(tài)不變。PrintMaze(M)初始條件：迷宮M已存在。操作結果：以字符形式輸出迷宮。ADT maze;3.本程序包含三個模塊1）

12、主程序模塊void main( ) 初始化do接受命令；處理命令；while(命令！=“退出”)；2）棧模塊-實現棧抽象數據類型3）迷宮模塊-實現迷宮抽象數據類型4求解迷宮中一條通路的偽碼算法：設定當前位置的初值為入口位置；do若當前位置可通，則 將當前位置插入棧頂； /納入路徑 若該位置是出口位置，則結束； /求得路徑存放在棧中 否則切換當前位置的東鄰方塊為新的當前位置；否則若棧不空且棧位置尚有其他方向未被探索，則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置； /后退一步，從路徑中刪去該通道塊， 若棧不空，則重新測試新的棧頂位

13、置， 直到找到一個可通的相鄰塊或出棧至棧空；while(棧不空)；?？照f明沒有路徑存在詳細設計示例如下：1坐標位置類型typedef structint r,c; /迷宮中行、列的范圍PosType;2迷宮類型typedef struct int m,n; char arrRANGERANGE; /各位置取值 ,#,或*MazeType;void InitMaze(MazeType &maze,int a,int row,int col)/按照用戶輸入的row行和col列的二維數組（元素值為0或1）/設置迷宮的初值，包括加上邊緣一圈的值bool MazePath(MazeType &maze,

14、PosType start,PosType end)/求解迷宮maze中，從入口start到出口end的一條路徑/若存在，則返回TRUE；否則返回FALSEvoid PrintMaze(MazeType maze)/將迷宮以字符型方陣的形式輸出到標準輸出文件上3棧類型typedef structint step; /當前位置在路徑上的“序號”PosType seat; /當前的坐標位置directiveType di; /往下一坐標位置的方向ElemType; /棧的元素類型typedef struct NodeTypeElemType data;NodeType *next;NodeType

15、,*LinkType; /結點類型，指針類型typedef structLinkType top;int size;Stack; /棧類型棧的基本操作設置如下：void InitStack(Stack &S)/初始化，設S為空棧（S.top=NULL）void DestroyStack(stack &S)/銷毀棧S，并釋放所占空間void ClearStack(Stack &S)/將S清為空棧int stackLength(Stack S)/返回棧S的長度S.sizeStatus StackEmpty(Stack S)/若S為空棧（S.top=NULL）,則返回TRUE;否則返回FALSESt

16、atus GetTop(Stack s,ElemType e)/若棧S不空,則以e帶回棧頂元素并返回TRUE,否則返回FALSE;Status Push(Stack &S,ElemType e) /若分配空間成功,則在S的棧頂插入新的棧頂元素e,并返回TRUE,/否則棧不變,并返回FALSEStatus Pop(Stack &S,ElemType &e)/若棧不空,則刪除S的棧頂元素并以e帶回其值，且返回TRUE /否則返回FALSEvoid StackTraverse(Stack s,Status(*visit)(ElemType e)/從棧底到棧頂依次對S中的每個結點調用函數visit其中

17、部分操作的算法：Status Push(Stack &S,ElemType e)/若分配空間成功，則在S的棧頂插入新的棧頂元素e，并返回TRUE；/否則棧不變，并返回FALSEif (MakeNode(p,e)p-next=s.top; s.top=p;s.size+; return TRUE;else return FALSE;Status Pop(Stack &S,ElemType &e)/若棧不空，則刪除S的棧頂元素并以e帶回其值，且返回TRUE，/否則返回FALSE，且e無意義if(StackEmpty(S) return FALSE;elsep=S.top; S.top=S.top-

18、next;e=p-date; S.size-; return TRUE; 4.求迷宮路徑的偽碼算法：Status MazePath(MazeType maze,PosType start,PosType end)/若迷宮中存在從入口start到出口end的通道,則求得一條存入在棧中/（從棧底到棧頂為從入口到出口的路徑），并返回TRUE；否則返回FALSEInitStack(S); curpos=start; /設定“當前位置”為“入口位置”curstep=1; found=FALSE; /探索第一步doif (Pass(maze,curpos) /當前位置可以通過，即是未曾走到過的通道塊留下足

19、跡FootPrint(maze,curpos); e=(curstep,curpos,1);Push(S,e); /加入路徑if(Same(curpos,end) found=TRUE; /到達終點（出口）else curpos=NextPos(curpos,1); /下一位置是當前位置的東鄰 curstep+; /探索下一步 /else/ifelse /當前位置不能通過if(!StackEmpty(S) Pop(S,e); while(e.di=4&!StackEmpty(S)MarkPrint(maze,e,seat); Pop(S,e); curstep-; /留下不能通過的標記，并退回

20、一步/whileif(e.di4) e.di+; Push(S.e); /換下一個方向探索 curpos=NextPos(e.seat,e.di); /設定當前位置是該新方向上的相鄰塊 /if /ifwhile(!StackEmpty(S)&!found); return found;/MazePath5主函數和其他函數的偽碼算法void main( ) /主程序 Initialization(); /初始化 do ReadCommand(cmd);/讀入一個操作命令符 Interpret(cmd); /解釋執(zhí)行操作命令符 while(cmd!=q&cmd!=Q);/mainvoid Init

21、ialization() /系統(tǒng)初始化 clrscr();/清屏在屏幕上方顯示操作命令清單： CreatMazec MazePathm PrintMazep Quitq;在屏幕下方顯示操作命令提示框：/Initializationvoid ReadCommand(char &cmd) /讀入操作命令符顯示鍵入操作命令符的提示信息； do cmd=getche()while(cmdc,C，m,M,p,P,q,Q)；/ReadCommandvoid Interpret(char cmd)/解釋執(zhí)行操作命令switch(cmd) case c,C:提示用戶輸入“迷宮數據的文件名filename”；從

22、文件讀入數據分別存儲在rnum，cnum和二維數組a2中； InitMaze(ma,a2,rnum,cnum); / 創(chuàng)建迷宮 輸出迷宮建立完畢的信息 break;casem,M:提示用戶輸入迷宮的入口from和出口 term的坐標位置； if(MazePath(ma,from,term)/存在路徑提示用戶察看迷宮；else 輸出該迷宮沒有從給定的入口到出口的路徑的信息；break；casep,P:PrintMaze(ma): /將標記路徑信息的迷宮輸出到終端/switch/InterPret6函數的調用關系圖反映了演示程序的層次結構：主程序Initialization ReadCommand

23、 InterPretInitMaze MazePath PrintMazeInitStack Push Pop StackEmpty StackTraverseFootPrint MarkPrint Pass NextPos Same附錄：源程序文件名清單：base.H /公用的常量和類型stkpas.H /棧類型maze.H /迷宮類型testmaze.C /主程序【實例測試及運行結果】迷宮的測試數據如下：左上角（1，1）為入口，右下角（9，8）為出口。0010001000100010000011010111001000010000010001010111100111000101110000

24、00提示：當入口位置為（1，1），出口位置為（9，8）時，輸出數據應為： *#*#*#*#*#*#*#*#*#*#*測試結果示例：三組測試數據和輸出結果分別如下：1輸入文件名為：m1.dat，其中迷宮數據為：3 20 00 00 0入口位置：1 1出口位置：3 2求解路徑后輸出的迷宮：*2輸入文件名：m2.dat，其中迷宮數據為：3 40 0 0 0 0 0 1 1 0 0 0 0入口位置：1 1出口位置：3 4求解路徑后輸出的迷宮：*#*3輸入文件名：m3.dat，其中迷宮數據同題目中的測試數據。入口位置：1 1出口位置：9 8求解路徑后輸出的迷宮正確，并和需求分析中所列相同。4輸入文件名：

25、m4.dat，其中迷宮數據為：4 90 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 00 0 1 1 1 0 0 1 10 0 1 1 1 0 1 0 0入口位置：1 1出口位置：4 9輸出信息為：此迷宮從入口到出口沒有路徑?！緦崿F提示】計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路?？梢远S數組存儲迷宮數據，通常設定入口點的下標為（1，1），出口點的下標為（m,n）。為處理方便起見，可在迷

26、宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。用戶手冊：（1）本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：TestMaze.exe（2）進入演示程序后，即顯示文本方式的用戶界面：*CreatMaze-c MazePath-m PrintMaze-p Quit-q * Operation:-*Enter a operation code: c，m，p OR q * *鍵入操作命令符操作命令清單操作提示信息（3）進入“產生迷宮（CreatMaze）”的命令后，即提示鍵入迷宮數據的文件名，結束符為“回車符”，該命令執(zhí)行之后輸出“迷宮已建成”。（4）進入“求迷宮路徑（

27、MazePath）” 的命令后，即提示鍵入入口位置（行號和列號，中間用空格分開，結束符為“回車符”）和出口位置（行號和列號，中間用空格分開，結束符為“回車符”），該命令執(zhí)行之后輸出相應信息。若迷宮中存在路徑，則執(zhí)行此命令后，迷宮狀態(tài)已改變，若要重復執(zhí)行此命令，無論是否改變出口和入口的位置，均需重新輸入迷宮數據。（5）輸入“顯示迷宮”的命令后，隨即輸出當前的迷宮，即迷宮的初始狀態(tài)或求出路徑之后的狀態(tài)。心得體會：1本次作業(yè)比較簡單，只有一個核心算法，即求迷宮的路徑，所以總的調試比較順利，只在調試MazePath算法時，遇到兩個問題：其一是，起初輸出的迷宮中沒有加上的記號，后發(fā)現是因為在MarkPr

28、int函數中的迷宮參數丟失“變參”的原因；其二是，由于回退時沒有將curpos隨之減一，致使棧中路徑上的序號有錯。2棧的元素中的step域沒有太多用處，可以省略。3StackTraverse在調試過程中很有用，它可以插入在MazePath算法中多處，以察看解迷宮過程中走的路徑是否正確，但對最后的執(zhí)行版本沒有用。4本題中三個主要算法：InitMaze,MazePath和PrintMaze的時間復雜度均為0（m*n），本題的空間復雜度亦為0（m*n）（棧所占最大空間）5經驗體會：借助DEBUG調試器和數據觀察窗口，可以加快找到程序中疵點?！具x作內容】（1） 編寫遞歸形式的算法，求得迷宮中所有可能的

29、通路；（2） 以方陣形式輸出迷宮及其通路。三設計題目1 文本文件單詞的檢索與計數專業(yè)： 班級： 姓名： 學號： 完成日期： 1.1【問題描述】假設有如下的英文文本文檔：(此處為太原理工大學學校簡介英文版)TAIYUAN UNIVERSITY OF TECHNOLOGYTaiyuan University of Technology (TUT) has its history traced all the way back to the Western Learning School of Shanxi Grand Academy (1902), which was one of the thr

30、ee earliest national universities in China. With the tradition and development of over 100 years, TUT is now a general university with engineering as the major, sciences and technology integrated and coordinate development of multiple disciplines. It is a university that is included in the “Project

31、211” - the national higher education promotion program for 100 top universities in China.Recollecting the centennial history, generations of TUT have created its mission and glory of a century with responsibility and confidence; expecting the promising tomorrow, over 30,000 TUT students and faculty

32、are producing splendor and perspectives by their wisdom and diligence. In the new era, Taiyuan University of Technology, following the Conception of Scientific Development, is determined to further the reformation on education, to reinforce the teaching management so as to upgrade its teaching and r

33、esearching levels. Taiyuan University of Technology will be turning itself into a research-based university.設計C或C+程序，統(tǒng)計在這樣的英文文本文件中，出現了多少個單詞，每個單詞出現了幾次。連續(xù)的英文字符都認為是單詞(不包括數字)，單詞之間用空格或標點符號分隔。 1.2【設計需求及分析】要統(tǒng)計英文文本文件中出現了哪些單詞，就要從文件中讀取字符，讀取出來的連續(xù)英文字符認為是一個單詞，遇空格或標點符號單詞結束。使用線性表記錄單詞以及每個單詞出現的次數。線性表中的單詞按字典順序存儲。線性表的

34、順序存儲結構如下：#define LIST_INIT_SIZE 100 /線性表存儲空間的初始分配量#define LISTINCREMENT 10 /線性表存儲空間的分配增量typedef struct char word21 /存儲單詞，不超過20個字符 int count; /單詞出現的次數 ElemType;typedef struct ElemType *elem; /存儲空間基址 int length; /當前長度int listsize; /當前分配的存儲容量 Sqlist;1.3【設計功能的實現】（用C或C+語言描述）/說明：要求由學生來完成代碼的編寫。1.3.1 實現順序表的

35、基本操作順序表的初始化：InitList(SqList &L)順序表上查找指定的單詞：LocateElem(SqList &L,char *s) 若找到，單詞的出現次數增1，返回0，否則返回該單詞的插入位置。在順序表上插入新的單詞：InsertList(SqList &L,int i，char *s) 要求按字典順序有序。新單詞的出現次數為1.輸出順序表上存儲的單詞統(tǒng)計信息：PrintList(SqList &L) 輸出文件中每個單詞出現的次數以及文件中總的單詞數(可輸出到文件中)。1.3.2 統(tǒng)計單詞數統(tǒng)計過程如下：（1）輸入要統(tǒng)計單詞的文本文件名，打開相應的文件；（2）初始化順序表；（3）

36、從文本文件中讀取字符，直到文件結束。具體描述如下：While (讀文件沒有結束結束) 過濾單詞前的非字母字符； 讀取一個單詞，以字符串形式存儲在一個字符數組中； 在線性表中查找該單詞，若找到，單詞的出現次數加1，否則返回其插入位置； 上一步中，若沒找到，則進行插入操作； 處理下一個單詞。（4）關閉文件，輸出統(tǒng)計結果。1.4【實例測試及運行結果】1.4.1 運行實例一（說明：由學生自己來給出）1.4.1 運行實例二（說明：由學生自己來給出）2停車場管理專業(yè)： 班級： 姓名： 學號： 完成日期： 2.1【問題描述】設停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按

37、車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在停車場的最北端）,若停車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。2.2【設計需求及分析】以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車

38、牌照號碼以及到達或離去的時刻。對每一組輸入數據進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現，隊列以鏈表結構實現。2.3【設計功能的實現】（用C或C+語言描述）/說明：此內容由學生自己設計完成。2.4【實例測試及運行結果】設n=2，輸入數據為：（A,1,5）,（A,2,10）,（D,1,15）,（A,3,20）,（A,4,25）,（A5,30）,（D,2,35）,（D,4,40）,（E,0,0）。其中：A表示到達（arrival）；D表示離去（departur

39、e）；E表示輸入結束（end）。2.5【實現提示】需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現。輸入數據按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數據項：汽車的牌照號碼和進入停車場的時刻。/說明：要求由學生來補充。3交通咨詢系統(tǒng)設計（最短路徑問題）專業(yè)： 班級： 姓名： 學號： 完成日期： 3.1【問題描述】在交通網絡非常發(fā)達,交通工具和交通方式不斷更新的今天,人們在出差、旅游或做其他出行時，不僅關心節(jié)省交通費用，而且對里程和所需要的時間等問題也感興趣。對于這樣一個人們關心的問題，可用一個圖結構來表示交通網絡系統(tǒng)，利用計算機建立一個交通

40、咨詢系統(tǒng)。圖中的頂點表示城市，邊表示城市之間的交通關系。這個交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問題。例如，問題之一：“一位旅客要從A城到B城，他希望選擇一條途中中轉次數最少的路線?！奔僭O圖中每一站都需要換車，那么這個問題反映到圖上就是要找一條從頂點A到頂點B的所含邊數目最少的路徑。我們只需要從頂點A出發(fā)對圖作廣度優(yōu)先搜索，一旦遇到頂點B就終止。由此所得廣度優(yōu)先生成樹上，從根頂點A到頂點B的路徑就是中轉次數最少的路徑。路徑上A與B之間的頂點就是路徑的中轉站，但這只是一類最簡單的圖的最短路徑問題。系統(tǒng)還可以回答諸如此類的等等的路徑選擇問題。設計一個交通咨詢系統(tǒng)，為出差、旅游或做其他出行的客

41、人提供各種路徑選擇信息查詢服務。3.2【設計需求及分析】設計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市頂點到另一城市頂點之間的最短路徑（里程）或最低花費或最少時間等問題。對于不同的咨詢要求，可輸入城市間的路程或所需時間或所需費用。本設計共分三部分，一是建立交通網絡圖的存儲結構；二是解決單源最短路徑問題；三是實現任兩個城市頂點之間的最短路徑問題。3.2.1建立圖的存儲結構鄰接矩陣是表示圖形中頂點之間相鄰關系的矩陣。圖的鄰接矩陣是定義如下的n階方陣：設G=（V，E）是一個圖，結點集為。G的鄰接矩陣當鄰接矩陣的行表頭、列表頭順序一定時，一個圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需用一個二維

42、數組存儲頂點之間的相鄰關系的鄰接矩陣外，通常還需要使用一個具有n個元素的一維數組來存儲頂點信息，其中下標為i的元素存儲頂點i的信息。因此，圖的鄰接矩陣的存儲結構定義如下：#definf MVNum 50 /最大頂點數typedef struct VertexType vexsMVNum; /頂點數組，類型假定為char型 Adjmatrix arcsMVNumMVNum; /鄰接矩陣，假定為int型MGraph;3.2.2單源最短路徑最短路徑的提法很多。在這里先討論單源最短路徑問題：即已知有向圖（帶權），我們希望找出從某個源點SV到G中其余各頂點的最短路徑。為了敘述方便，我們把路徑上的開始點稱

43、為源點，路徑的最后一個頂點為終點。那么，如何求得給定有向圖的單源最短路徑呢？迪杰斯特拉（Dijkstra）提出按路徑長度遞增產生諸點的最短路徑算法，稱之為迪杰斯特拉算法。迪杰斯特拉算法求最短路徑的實現思想是：設G=（V，E）是一個有向圖，結點集為，cost是表示G的鄰接矩陣，costij表示有向邊的權。若不存在有向邊，則costij的權為無窮大（這里取值為32767）。設S是一個集合，其中的每個元素表示一個頂點，從源點到這些頂點的最短距離已經求出。設頂點v1為源點，集合S的初態(tài)只包含一個元素，即頂點v1。數組dist記錄從源點到其他頂點當前的最短距離，其初值為disti=costv1i,i=1

44、,2,n。從S之外的頂點集合V-S中選出一個頂點w，使distw的值最小。于是從源點到達w只通過S中頂點，把w加入集合S中，調整dist中記錄的從源點到V-S中每個頂點v的距離：從原來的distv和distw+costwv中選擇較小的值作為新的distv。重復上述過程，直到V-S為空。最終結果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數組dist記錄了源點到V中其余各頂點之間的最短路徑，path是最短路徑的路徑數組，其中pathi表示從源點到頂點i之間的最短路徑的前驅頂點。因此，迪杰斯特拉算法可用自然語言描述如下：初始化S和D，置空最短路徑終點集，置初始的最短路徑值；Sv1=TRUE;

45、 Dv1=0； /S集初始時只有源點，源點到源點的距離為0；While (S集中頂點數n)開始循環(huán)，每次求得v1到某個v頂點的最短路徑，并加v到S集中；Sv=TRUE；更新當前最短路徑及距離；3.2.3任意一對頂點間最短路徑任意一對頂點間最短路徑問題，是對于給定的有向網絡圖G=（V，E），要對G中任意一對頂點有序對“v,w(vw)”,找出v到w的最短路徑。要解決這個問題，我們可以依次把有向網絡圖中每個頂點作為源點，重復執(zhí)行前面討論的迪杰斯特拉算法n次，即可以求得每對頂點之間的最短路徑。這里還可以用另外一種方法，稱作費洛伊德（Floyd）算法。費洛伊德（Floyd）算法算法的基本思想是：假設求從

46、頂點 vi到vj的最短路徑。如果從vi到vj存在一條長度為arcsij的路徑，該路徑不一定是最短路徑，還需要進行n次試探。首先考慮路徑和是否存在。如果存在，則比較和的路徑長度，取長度較短者為當前所求得的最短路徑。該路徑是中間頂點序號不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點v2為中間頂點的路徑，若沒有，則說明從vi到vj的當前最短路徑就是前一步求出的；若有，那么可分解為和,而這兩條路徑是前一次找到的中間頂點序號不大于1的最短路徑，將這兩條路徑長度相加就得到路徑的長度。將該長度與前一次中求出的從vi到vj的中間頂點序號不大于1的最短路徑比較，取其長度較短者作為當前求得的從vi到vj

47、的中間頂點序號不大于2的最短路徑。依此類推，直到頂點vn加入當前從vi到vj的最短路徑后，選出從vi到vj的中間頂點序號不大于n的最短路徑為止。由于圖G中頂點序號不大于n，所以vi到vj的中間頂點序號不大于n的最短路徑，已考慮了所有頂點作為中間頂點的可能性，因此，它就是vi到vj的最短路徑。3.3【設計功能的實現】（用C或C+語言描述）3.3.1 建立有向圖的存儲結構/說明：要求由學生來完成代碼的編寫。3.3.2 迪杰斯特拉算法/說明：要求由學生來完成代碼的編寫。3.3.3 費洛伊德算法/說明：要求由學生來完成代碼的編寫。3.3.4 運行主控程序/說明：要求由學生來完成代碼的編寫。3.4【實例

48、測試及運行結果】3.4.1 運行實例一（求給定有向圖3-1的最短路徑）圖3-1 一個有向圖具體要求之一：求頂點到其余頂點的最短路徑；分別求頂點b到頂點d之間的最短路徑、頂點到頂點d之間的最短路徑。提示：為了操作方便，對于圖的頂點都是用序號來表示的，所以頂點的字母就用其對應的序號來操作：如用1來代替，。3.4.2 運行實例二（求給定有向圖3-2的最短路徑）圖3-2 一個簡單的交通網絡圖圖3-2 是一個簡單的交通網絡圖。具體要求之一：求頂點“北京”到其余各城市之間的最短路徑；并分別求“成都”到“上海”之間以及“上?！钡健拔靼病敝g的最短路徑。提示：為了操作方便，對于圖的頂點都是用序號來表示的，所以

49、頂點的城市名稱就用其對應的編號來操作：如北京用1來代替，。3.5【實現提示】/說明：學生自己補充。4學生管理系統(tǒng)專業(yè)： 班級： 姓名： 學號： 完成日期： 4.1【問題描述】大學里有各種類型的學生，校方需要對這些學生的信息進行計算機管理。所開發(fā)的軟件應包括各類學生的添加、修改、刪除和查找等功能。考慮到軟件的可重用性、可擴展性和可維護性，校方決定采用面向對象的程序設計方法來開發(fā)系統(tǒng)。學生信息需要以文件方式保存到計算機硬盤中。另外，系統(tǒng)的用戶界面應該盡可能友好，方便用戶使用。4.2【設計需求及分析】(1) 使用C+語言開發(fā)，充分利用面向對象程序設計的類、對象、繼承、封裝和多態(tài)性等(2) 概念設計和

50、實現該管理系統(tǒng)。(3) 設計一個Person（人員）類，考慮到通用性，只抽象出所有類型人員都具有的屬性：name（姓名）, id（身份證號），gender（性別），birthday（出生日期）等等。其中“出生日期”為內嵌子對象，是一個Date（日期）類型，Date類具有屬性: year(年)，month（月），day（日）。用成員函數實現對人員信息的錄入和顯示等必要功能操作。(4) 從Person類派生出Student（學生）類，添加屬性： studentNo（學號），schoolName（學校），classIn (班級)。從Person類派生出Teacher（教師）類，添加屬性：teache

51、rNo（教師編號），schoolName（學校），department（部門）。(5) 從Student類中派生出UnderGraduate（本科生）類，添加屬性：major（專業(yè)）。從Student類中派生出Graduate（研究生）類，添加屬性：direction（研究方向），adviserName（導師姓名）。(6) 從Graduate類和Teacher類派生出T（助教博士生）類。(7) 寫程序測試上述各類，看能否正常運行。(8) 構建必要的輔助類，實現對本科生、研究生和助教博士生的添加、修改、刪除、查詢管理。(9) 根據需要定義類的構造函數、析構函數、拷貝構造函數、成員函數。必要時重載

52、函數。(10) 要求將Person類設置為虛基類，以消除其派生類成員訪問的二義性問題（注意在虛基類各級派生類的構造函數實現時調用虛基類的構造函數）。(11) 要求在Person類中定義虛函數displayDetails（），用于顯示當前對象的信息；同時定義虛函數inputData( )，用于從鍵盤獲取當前對象的信息。Person類所有派生類也要定義同名虛函數，使程序可以實現動態(tài)多態(tài)性。(12) 用菜單方式設計主控模塊程序。(13) 對程序源代碼要給出各部分的詳細注釋，這也是該題目的考核重點之一。(14) 用UML語言描述系統(tǒng)用到的類及其關系。4.3【設計功能的實現】（用C或C+語言描述）/說明

53、：此內容由學生自己設計完成。/以下代碼僅供參考。程序框架:/*Copyright (C), 2013, TyutFile name: main.cppAuthor: gaobaolu Version: 1.0 Date: 2013.6.10Description: 應用程序主函數 */#include #include #include date.h#include person.h#include student.h#include teacher.h#include undergraduate.h#include graduate.h#include ta.h#include undergraduateManager.husing namespace std;int main(int argc, char *argv) int choiceN;UndergraduateManager unMan; cout*endl; cout*|*| |*|*endl; cout*|*| 歡迎您使用學生管理系統(tǒng) |*|*endl; cout*|*| |*|*endl;