《程序設(shè)計課程設(shè)計》指導(dǎo)書2013

《《程序設(shè)計課程設(shè)計》指導(dǎo)書2013》由會員分享，可在線閱讀，更多相關(guān)《《程序設(shè)計課程設(shè)計》指導(dǎo)書2013（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、課程設(shè)計題目，利用C語言作為開發(fā)工具，使學(xué)生通過課程設(shè)計掌握高級編程語言的知識和編程技術(shù)，掌握程序設(shè)計的思想和方法，初步具備利用計算機(jī)求解實際問題的能力。 通過《程序設(shè)計課程設(shè)計》課程的學(xué)習(xí)，能夠幫助學(xué)生加深理解數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、C語言基本概念，達(dá)到培養(yǎng)學(xué)生良好程序設(shè)計的習(xí)慣和運用 C 語言編寫程序解決實際問題的能力。使學(xué)生學(xué)會把書本知識用于解決實際問題，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。同時使學(xué)生在程序設(shè)計方法及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。 通過該課程設(shè)計，學(xué)生應(yīng)該掌握C或C++語言程序設(shè)計的方法、數(shù)據(jù)結(jié)構(gòu)和離散數(shù)學(xué)理論知識，熟悉C或C++程序的開發(fā)環(huán)

3、境及C或C++程序的調(diào)試過程，鞏固和加深對理論課中知識的理解，提高學(xué)生對所學(xué)知識的綜合運用能力；學(xué)生應(yīng)該具有如下基本技能：①培養(yǎng)學(xué)生查閱參考資料、手冊的自學(xué)能力，通過獨立思考深入鉆研問題，學(xué)會自己分析、解決問題。②通過對所選題目方案分析比較，確立方案，編制程序與調(diào)試程序。③能熟練調(diào)試程序，在教師的指導(dǎo)下，完成課題任務(wù)。④根據(jù)個人的設(shè)計調(diào)試過程，按課程設(shè)計報告的要求撰寫設(shè)計報告。 選用教材及主要參考書： 1 教材 呼克佑. C語言程序設(shè)計. 電子工業(yè)出版社,2013 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)(C語言版) 清華大學(xué)出版社，2012 2、主要參考書 [1] 譚浩強(qiáng). 程序設(shè)計題解與上機(jī)指導(dǎo)(三

4、版) . 清華大學(xué)出版社，2012 [2] 邱仲潘. C語言參考手冊. 機(jī)械工業(yè)出版社，2004 [3] 譚浩強(qiáng). C語言程序設(shè)計（三版）. 清華大學(xué)出版社，2012 [4] 方世昌. 離散數(shù)學(xué).西安電子科技大學(xué)出版社，2003 [5] 丁亞濤. C語言程序設(shè)計.高等教育出版社，2003 目 錄 前 言 1 一．課程設(shè)計報告要求 1 二．課程設(shè)計報告示例——迷宮問題 2 三．設(shè)計題目 12 1．文本文件單詞的檢索與計數(shù) 12 2．停車場管理 16 3．交通咨詢系統(tǒng)設(shè)計（最短路徑問題） 17 4．學(xué)生管理系統(tǒng) 21 一．課程設(shè)計報告要求 課

5、程設(shè)計報告封面應(yīng)給出專業(yè)、班級、姓名、學(xué)號、指導(dǎo)教師和完成日期，報告開頭給出題目，內(nèi)容包括以下五項： 1．【問題描述】 簡要描述問題，然后說明程序設(shè)計的任務(wù)，程序要做什么。明確規(guī)定以下內(nèi)容： （1） 輸入的形式和輸入值的范圍； （2） 輸出的形式； （3） 程序所能達(dá)到的功能； （4） 測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。 2．【設(shè)計需求及分析】 說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系。實現(xiàn)設(shè)計中定義的所有數(shù)據(jù)類型，對每個操作寫出偽碼算法；對主程序和其他模塊也寫出偽碼算法（偽碼算法的詳細(xì)程度為

6、按照偽碼算法可以在計算機(jī)鍵盤直接輸入高級程序設(shè)計語言程序）；畫出函數(shù)的調(diào)用關(guān)系圖。 3．【設(shè)計功能的實現(xiàn)】（用C或C++描述） //說明：用C或C++實現(xiàn)代碼設(shè)計。 4．【實例測試及運行結(jié)果】 列出測試結(jié)果，包括輸入和輸出。測試數(shù)據(jù)應(yīng)該完整、嚴(yán)格。 測試分析內(nèi)容包括： （1） 測試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論與分析； （2） 算法的時空分析和改進(jìn)設(shè)想； （3） 經(jīng)驗和體會。 5．【實現(xiàn)提示】 使用說明：說明如何使用該程序，列出每一步的操作步驟。 附錄：列出程序文件名的清單以及必要的帶注釋的源程序。 心得體會等等。 二．課程設(shè)計報告示例——迷宮

7、問題 專業(yè)： 班級： 姓名： 學(xué)號： 完成日期： 【問題描述】 編制一個求解迷宮通路的程序。 以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo),d 表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為： （1，1，1），（1，2，2），（2，

8、2，2），（3，2，3），（3，1，2）…… 【設(shè)計需求及分析】 （1）以二維數(shù)組MAZE[M+2][N+2]表示迷宮，其中：MAZE[0][J]和MAZE[M+1][J]（0≤J≤N+1）及MAZE[I][0]和MAZE[I][N+1]（0≤I≤M+1）為添加的一圈障礙。數(shù)組中以元素值為0表示通路，1表示障礙。限定迷宮的大小M，N≤10。 （2）用戶以文件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù)M和列數(shù)N；從第2行至第M+1行（每行N個數(shù)）為迷宮值，同一行中的兩個數(shù)字之間用空白字符相隔。 （3）迷宮的入口位置和出口位置可由用戶隨時設(shè)定。 （4）若設(shè)定的迷宮存在通路，

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

10、：D={ai|ai∈charset,i=1,2,……,n,n≥0} 數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2……,n} 基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧S。 DestroyStack(&S) 初始條件：棧S已存在。 操作結(jié)果：銷毀棧S。 ClearStack(&S) 初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。 StackLength(&S) 初始條件：棧S已存在。 操作結(jié)果：返回棧S的長度。 StackEmpty(&S) 初始條件：棧S已存在。 操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。

11、 GetTop(S,&e) 初始條件：棧S已存在。 操作結(jié)果：若棧S不空，則以e返回棧頂元素。 Push(&S,e) 初始條件：棧S已存在。 操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。 Pop(&S,&e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。 StackTraverse(S,visit( )) 初始條件：棧S已存在。 操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit( ). }ADT stack 2．設(shè)定迷宮的抽象數(shù)據(jù)類型為： ADT maze{ 數(shù)據(jù)對象：D={ai,j|ai,j∈{‘ ’、‘#’、‘@’、‘*’}

12、，0≤i≤m+1,0≤j≤n+1,m,n≤10} 數(shù)據(jù)關(guān)系：R={ROW，COL} ROW={|ai-1,j，ai,j∈D,i=1,……，m+1,j=0,……，n+1} COL={|ai,j-1,ai,j∈D,i=0,……，m+1,j=1,……，n+1} 基本操作： InitMaze(&M,a,row,col) 初始條件：二維數(shù)組a[row+2][col+2]已存在，其中自第1行至第row+1行、每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。 操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白字符表示通路，

13、以字符‘#’表示障礙，并在迷宮四周加上一圈障礙。 MazePath(&M) 初始條件：迷宮M已被賦值。 操作結(jié)果：若迷宮M中存在一條通路，則按如下規(guī)定改變迷宮M的狀態(tài)：以字符“*”表示路徑上的位置，字符“@”表示“死胡同”；否則迷宮的狀態(tài)不變。 PrintMaze(M) 初始條件：迷宮M已存在。 操作結(jié)果：以字符形式輸出迷宮。 }ADT maze; 3.本程序包含三個模塊 1）主程序模塊 void main( ) { 初始化 do{ 接受命令； 處理命令； }while(命令！=“退出”)； } 2）棧模塊----實現(xiàn)棧抽象數(shù)據(jù)類型 3）迷宮模塊----實

14、現(xiàn)迷宮抽象數(shù)據(jù)類型 4．求解迷宮中一條通路的偽碼算法： 設(shè)定當(dāng)前位置的初值為入口位置； do{ 若當(dāng)前位置可通， 則{ 將當(dāng)前位置插入棧頂； //納入路徑 若該位置是出口位置，則結(jié)束； //求得路徑存放在棧中 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； } 否則{ 若棧不空且棧位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則{刪去棧頂位置； //后退一步，從路徑中刪去該通道塊，

15、 若棧不空，則重新測試新的棧頂位置， 直到找到一個可通的相鄰塊或出棧至?？眨? } } }while(棧不空)； {?？照f明沒有路徑存在} 詳細(xì)設(shè)計示例如下： 1．坐標(biāo)位置類型 typedef struct{ int r,c; //迷宮中行、列的范圍 }PosType; 2．迷宮類型 typedef struct{ int m,n; char arr[RANGE][RANGE]; //各位置取值‘ ’,‘#’,‘@’或‘*’ }MazeType; void InitMaze(MazeType &

16、maze,int a[][],int row,int col) //按照用戶輸入的row行和col列的二維數(shù)組（元素值為0或1） //設(shè)置迷宮的初值，包括加上邊緣一圈的值 bool MazePath(MazeType &maze,PosType start,PosType end) //求解迷宮maze中，從入口start到出口end的一條路徑 //若存在，則返回TRUE；否則返回FALSE void PrintMaze(MazeType maze) //將迷宮以字符型方陣的形式輸出到標(biāo)準(zhǔn)輸出文件上 3．棧類型 typedef struct{ int st

17、ep; //當(dāng)前位置在路徑上的“序號” PosType seat; //當(dāng)前的坐標(biāo)位置 directiveType di; //往下一坐標(biāo)位置的方向 }ElemType; //棧的元素類型 typedef struct NodeType{ ElemType data; NodeType *next; }NodeType,*LinkType; //結(jié)點類型，指針類型 typedef struct{ LinkType top; int size;

18、 }Stack; //棧類型 棧的基本操作設(shè)置如下： void InitStack(Stack &S) //初始化，設(shè)S為空棧（S.top=NULL） void DestroyStack(stack &S) //銷毀棧S，并釋放所占空間 void ClearStack(Stack &S) //將S清為空棧 int stackLength(Stack S) //返回棧S的長度S.size Status StackEmpty(Stack S) //若S為空棧（S.top==NULL）,則返回TRUE;否則返回FALSE Status GetTop(Stack

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

20、visit 其中部分操作的算法： Status Push(Stack &S,ElemType e) {//若分配空間成功，則在S的棧頂插入新的棧頂元素e，并返回TRUE； //否則棧不變，并返回FALSE if (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(Sta

21、ckEmpty(S)) return FALSE; else{ p=S.top; S.top=S.top->next; e=p->date; S.size--; return TRUE; } } 4.求迷宮路徑的偽碼算法： Status MazePath(MazeType maze,PosType start,PosType end) { //若迷宮中存在從入口start到出口end的通道,則求得一條存入在棧中 //（從棧底到棧頂為從入口到出口的路徑），并返回TRUE；否則返回FALSE InitStack(S); curpos=start; //設(shè)定“

22、當(dāng)前位置”為“入口位置” curstep=1; found=FALSE; //探索第一步 do{ if (Pass(maze,curpos)){ //當(dāng)前位置可以通過，即是未曾走到過的通道塊留下足跡 FootPrint(maze,curpos); e=(curstep,curpos,1); Push(S,e); //加入路徑 if(Same(curpos,end)) found=TRUE; //到達(dá)終點（出口） else{ curpos=NextPos(curpos,1); //下一位

23、置是當(dāng)前位置的東鄰 curstep++; //探索下一步 }//else }//if else //當(dāng)前位置不能通過 if(!StackEmpty(S)){ Pop(S,e); while(e.di==4&&!StackEmpty(S)){ MarkPrint(maze,e,seat); Pop(S,e); curstep--; //留下不能通過的標(biāo)記，并退回一步 }//while if(e.di<4){ e.di++; Push(S.e); //

24、換下一個方向探索 curpos=NextPos(e.seat,e.di); //設(shè)定當(dāng)前位置是該新方向上的相鄰塊 }//if }//if }while(!StackEmpty(S)&&!found); return found; }//MazePath 5．主函數(shù)和其他函數(shù)的偽碼算法 void main( ) {//主程序 Initialization(); //初始化 do{ ReadCommand(cmd);//讀入一個操作命

25、令符 Interpret(cmd); //解釋執(zhí)行操作命令符 }while(cmd!=‘q’&&cmd!=‘Q’); }//main void Initialization() { //系統(tǒng)初始化 clrscr();//清屏 在屏幕上方顯示操作命令清單： CreatMaze—c MazePath—m PrintMaze—p Quit—q; 在屏幕下方顯示操作命令提示框： }//Initialization void ReadCommand(char &cmd) { //讀入操作命令符 顯

26、示鍵入操作命令符的提示信息； do{ cmd=getche() }while(cmd[‘c’,‘C’，‘m’,‘M’,‘p’,‘P’,‘q’,‘Q’])； }//ReadCommand void Interpret(char cmd) {//解釋執(zhí)行操作命令 switch(cmd){ case ‘c’,’C’:提示用戶輸入“迷宮數(shù)據(jù)的文件名filename”； 從文件讀入數(shù)據(jù)分別存儲在rnum，cnum和二維數(shù)組a2中； InitMaze(ma,a2,rnum,cnum); // 創(chuàng)建迷宮 輸出迷宮建立完畢的信息 break

27、; case‘m’,‘M’:提示用戶輸入迷宮的入口from和出口 term的坐標(biāo)位置； if(MazePath(ma,from,term))//存在路徑 提示用戶察看迷宮； else 輸出該迷宮沒有從給定的入口到出口的路徑的信息； break； case‘p’,‘P’:PrintMaze(ma): //將標(biāo)記路徑信息的迷宮輸出到終端 }//switch }//InterPret 6．函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)： 主程序 Initialization ReadCommand InterPre

28、t InitMaze MazePath PrintMaze InitStack Push Pop StackEmpty StackTraverse FootPrint MarkPrint Pass NextPos Same 附錄：源程序文件名清單： base.H //公用的常量和類型 stkpas.H //棧類型 maze.H //迷宮類型 testmaze.C //主程序 【

29、實例測試及運行結(jié)果】 迷宮的測試數(shù)據(jù)如下：左上角（1，1）為入口，右下角（9，8）為出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 提示：當(dāng)入口位置為（1，1）

30、，出口位置為（9，8）時，輸出數(shù)據(jù)應(yīng)為： * * # @ @ @ # * # @ @ @ # * * @ @ # # # * # # # # @ * * * # * * * @ # * * * # * # # # # # * # # # # * # # # * * 測試結(jié)果示例： 三組測試數(shù)據(jù)和輸出結(jié)果分別如下： 1．輸入文件名為：m1.dat，其中迷宮數(shù)據(jù)為： 3 2 0 0 0 0 0 0

31、 入口位置：1 1 出口位置：3 2 求解路徑后輸出的迷宮： * * * * 2．輸入文件名：m2.dat，其中迷宮數(shù)據(jù)為： 3 4 0 0 0 0 0 0 1 1 0 0 0 0 入口位置：1 1 出口位置：3 4 求解路徑后輸出的迷宮： * * @ @ * # # * * * 3．輸入文件名：m3.dat，其中迷宮數(shù)據(jù)同題目中的測試數(shù)據(jù)。 入口位置：1 1 出口位置：9 8 求解路徑后輸出的迷宮正確，并和需求分析中所列相同。 4．輸入文件名：m4.dat，其中迷宮數(shù)據(jù)為：

32、4 9 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 入口位置：1 1 出口位置：4 9 輸出信息為：此迷宮從入口到出口沒有路徑。 【實現(xiàn)提示】 計算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。 可以二維數(shù)組存儲迷宮數(shù)據(jù)，

33、通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。 用戶手冊： （1）本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：TestMaze.exe （2）進(jìn)入演示程序后，即顯示文本方式的用戶界面： **********************************************************************CreatMaze-c MazePath-m PrintMaze-p Quit-q * ***

34、****************************************************************** Operation:- *********************************************************************Enter a operation code: c，m，p OR q * **************************************

35、******************************* 鍵入操作命令符 操作命令清單 操作提示信息 （3）進(jìn)入“產(chǎn)生迷宮（CreatMaze）”的命令后，即提示鍵入迷宮數(shù)據(jù)的文件名，結(jié)束符為“回車符”，該命令執(zhí)行之后輸出“迷宮已建成”。 （4）進(jìn)入“求迷宮路徑（MazePath）” 的命令后，即提示鍵入入口位置（行號和列號，中間用空格分開，結(jié)束符為“回車符”）和出口位置（行號和列號，中間用空格分開，結(jié)束符為“回車符”），該命令執(zhí)行之后輸出相應(yīng)信息。若迷宮中存在路徑，則執(zhí)行此命令后，迷宮狀態(tài)已改變，若要重復(fù)執(zhí)行此命令，無論

36、是否改變出口和入口的位置，均需重新輸入迷宮數(shù)據(jù)。 （5）輸入“顯示迷宮”的命令后，隨即輸出當(dāng)前的迷宮，即迷宮的初始狀態(tài)或求出路徑之后的狀態(tài)。 心得體會： 1．本次作業(yè)比較簡單，只有一個核心算法，即求迷宮的路徑，所以總的調(diào)試比較順利，只在調(diào)試MazePath算法時，遇到兩個問題：其一是，起初輸出的迷宮中沒有加上‘@’的記號，后發(fā)現(xiàn)是因為在MarkPrint函數(shù)中的迷宮參數(shù)丟失“變參”的原因；其二是，由于回退時沒有將curpos隨之減一，致使棧中路徑上的序號有錯。 2．棧的元素中的step域沒有太多用處，可以省略。 3．StackTraverse在調(diào)試過程中很有用，它可以插入在MazeP

37、ath算法中多處，以察看解迷宮過程中走的路徑是否正確，但對最后的執(zhí)行版本沒有用。 4．本題中三個主要算法：InitMaze,MazePath和PrintMaze的時間復(fù)雜度均為0（m*n），本題的空間復(fù)雜度亦為0（m*n）（棧所占最大空間） 5．經(jīng)驗體會：借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口，可以加快找到程序中疵點。 【選作內(nèi)容】 （1） 編寫遞歸形式的算法，求得迷宮中所有可能的通路； （2） 以方陣形式輸出迷宮及其通路。 三．設(shè)計題目 1． 文本文件單詞的檢索與計數(shù) 專業(yè)： 班級： 姓名： 學(xué)號： 完成日期

38、： 1.1【問題描述】 假設(shè)有如下的英文文本文檔：(此處為太原理工大學(xué)學(xué)校簡介英文版) TAIYUAN UNIVERSITY OF TECHNOLOGY Taiyuan 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 three earliest national universities in Chi

39、na. 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 211” --- the national higher education

40、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 are producing splendor and pers

41、pectives 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 researching levels. Taiyuan Uni

42、versity of Technology will be turning itself into a research-based university. 設(shè)計C或C++程序，統(tǒng)計在這樣的英文文本文件中，出現(xiàn)了多少個單詞，每個單詞出現(xiàn)了幾次。連續(xù)的英文字符都認(rèn)為是單詞(不包括數(shù)字)，單詞之間用空格或標(biāo)點符號分隔。 1.2【設(shè)計需求及分析】 要統(tǒng)計英文文本文件中出現(xiàn)了哪些單詞，就要從文件中讀取字符，讀取出來的連續(xù)英文字符認(rèn)為是一個單詞，遇空格或標(biāo)點符號單詞結(jié)束。 使用線性表記錄單詞以及每個單詞出現(xiàn)的次數(shù)。線性表中的單詞按字典順序存儲。 線性表的順序存儲結(jié)構(gòu)如下： #define

43、LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量 #define LISTINCREMENT 10 //線性表存儲空間的分配增量 typedef struct{ char word[21] //存儲單詞，不超過20個字符 int count; //單詞出現(xiàn)的次數(shù) } ElemType; typedef struct{ ElemType *elem; //存儲空間基址 int length; //當(dāng)前長度 in

44、t listsize; //當(dāng)前分配的存儲容量 } Sqlist; 1.3【設(shè)計功能的實現(xiàn)】（用C或C++語言描述） //說明：要求由學(xué)生來完成代碼的編寫。 1.3.1 實現(xiàn)順序表的基本操作 ⑴順序表的初始化：InitList(SqList &L) ⑵順序表上查找指定的單詞：LocateElem(SqList &L,char *s) 若找到，單詞的出現(xiàn)次數(shù)增1，返回0，否則返回該單詞的插入位置。 ⑶在順序表上插入新的單詞：InsertList(SqList &L,int i，char *s) 要求按字典順序有序。新單詞的出現(xiàn)次數(shù)為1.

45、 ⑷輸出順序表上存儲的單詞統(tǒng)計信息：PrintList(SqList &L) 輸出文件中每個單詞出現(xiàn)的次數(shù)以及文件中總的單詞數(shù)(可輸出到文件中)。 1.3.2 統(tǒng)計單詞數(shù) 統(tǒng)計過程如下： （1）輸入要統(tǒng)計單詞的文本文件名，打開相應(yīng)的文件； （2）初始化順序表； （3）從文本文件中讀取字符，直到文件結(jié)束。具體描述如下： While (讀文件沒有結(jié)束結(jié)束) { 過濾單詞前的非字母字符； 讀取一個單詞，以字符串形式存儲在一個字符數(shù)組中； 在線性表中查找該單詞，若找到，單詞的出現(xiàn)次數(shù)加1，否則返回其插入位置； 上一步中

46、，若沒找到，則進(jìn)行插入操作； 處理下一個單詞。 } （4）關(guān)閉文件，輸出統(tǒng)計結(jié)果。 1.4【實例測試及運行結(jié)果】 1.4.1 運行實例一 （說明：由學(xué)生自己來給出） 1.4.1 運行實例二 （說明：由學(xué)生自己來給出） 2．停車場管理 專業(yè)： 班級： 姓名： 學(xué)號： 完成日期： 2.1【問題描述】 設(shè)停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在停車場的最

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

48、，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。 2.3【設(shè)計功能的實現(xiàn)】（用C或C++語言描述） //說明：此內(nèi)容由學(xué)生自己設(shè)計完成。 2.4【實例測試及運行結(jié)果】 設(shè)n=2，輸入數(shù)據(jù)為：（‘A’,1,5）,（‘A’,2,10）,（‘D’,1,15）,（‘A’,3,20）,（‘A’,4,25）,（‘A’5,30）,（‘D’,2,35）,（‘D’,4,40）,（‘E’,0,0）。其中：‘A’表示到達(dá)（arrival）；‘D’表示離去（departure）；‘E

49、’表示輸入結(jié)束（end）。 2.5【實現(xiàn)提示】 需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進(jìn)入停車場的時刻。 //說明：要求由學(xué)生來補充。 3．交通咨詢系統(tǒng)設(shè)計（最短路徑問題） 專業(yè)： 班級： 姓名： 學(xué)號： 完成日期： 3.1【問題描述】 在交通網(wǎng)絡(luò)非常發(fā)達(dá),交通工具和交通方式不斷更新的今天,人們在出差、旅游或做其他出行時，不僅關(guān)心節(jié)省交通費用，而

50、且對里程和所需要的時間等問題也感興趣。對于這樣一個人們關(guān)心的問題，可用一個圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計算機(jī)建立一個交通咨詢系統(tǒng)。圖中的頂點表示城市，邊表示城市之間的交通關(guān)系。這個交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問題。例如，問題之一：“一位旅客要從A城到B城，他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線?！奔僭O(shè)圖中每一站都需要換車，那么這個問題反映到圖上就是要找一條從頂點A到頂點B的所含邊數(shù)目最少的路徑。我們只需要從頂點A出發(fā)對圖作廣度優(yōu)先搜索，一旦遇到頂點B就終止。由此所得廣度優(yōu)先生成樹上，從根頂點A到頂點B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上A與B之間的頂點就是路徑的中轉(zhuǎn)站，但這只是一

51、類最簡單的圖的最短路徑問題。系統(tǒng)還可以回答諸如此類的等等的路徑選擇問題。 設(shè)計一個交通咨詢系統(tǒng)，為出差、旅游或做其他出行的客人提供各種路徑選擇信息查詢服務(wù)。 3.2【設(shè)計需求及分析】 設(shè)計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市頂點到另一城市頂點之間的最短路徑（里程）或最低花費或最少時間等問題。對于不同的咨詢要求，可輸入城市間的路程或所需時間或所需費用。 本設(shè)計共分三部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；三是實現(xiàn)任兩個城市頂點之間的最短路徑問題。 3.2.1建立圖的存儲結(jié)構(gòu) 鄰接矩陣是表示圖形中頂點之間相鄰關(guān)系的矩陣。圖的鄰接矩陣是定義如下的n階方陣：

52、設(shè)G=（V，E）是一個圖，結(jié)點集為。 G的鄰接矩陣 當(dāng)鄰接矩陣的行表頭、列表頭順序一定時，一個圖的鄰接矩陣表示是唯一的。 圖的鄰接矩陣表示，除了需用一個二維數(shù)組存儲頂點之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個具有n個元素的一維數(shù)組來存儲頂點信息，其中下標(biāo)為i的元素存儲頂點i的信息。因此，圖的鄰接矩陣的存儲結(jié)構(gòu)定義如下： #definf MVNum 50 //最大頂點數(shù) typedef struct { VertexType vexs[MVNum]; //頂點數(shù)組，類型假定為char型 Adjmatrix arcs[MVNum][

53、MVNum]; //鄰接矩陣，假定為int型 }MGraph; 3.2.2單源最短路徑 最短路徑的提法很多。在這里先討論單源最短路徑問題：即已知有向圖（帶權(quán)），我們希望找出從某個源點SV到G中其余各頂點的最短路徑。 為了敘述方便，我們把路徑上的開始點稱為源點，路徑的最后一個頂點為終點。 那么，如何求得給定有向圖的單源最短路徑呢？迪杰斯特拉（Dijkstra）提出按路徑長度遞增產(chǎn)生諸點的最短路徑算法，稱之為迪杰斯特拉算法。 迪杰斯特拉算法求最短路徑的實現(xiàn)思想是：設(shè)G=（V，E）是一個有向圖，結(jié)點集為，，cost是表示G的鄰接矩陣，cost[i][j]表示有向邊的權(quán)。

54、若不存在有向邊，則cost[i][j]的權(quán)為無窮大（這里取值為32767）。設(shè)S是一個集合，其中的每個元素表示一個頂點，從源點到這些頂點的最短距離已經(jīng)求出。設(shè)頂點v1為源點，集合S的初態(tài)只包含一個元素，即頂點v1。數(shù)組dist記錄從源點到其他頂點當(dāng)前的最短距離，其初值為dist[i]=cost[v1][i],i=1,2,……,n。從S之外的頂點集合V-S中選出一個頂點w，使dist[w]的值最小。于是從源點到達(dá)w只通過S中頂點，把w加入集合S中，調(diào)整dist中記錄的從源點到V-S中每個頂點v的距離：從原來的dist[v]和dist[w]+cost[w][v]中選擇較小的值作為新的di

55、st[v]。重復(fù)上述過程，直到V-S為空。 最終結(jié)果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數(shù)組dist記錄了源點到V中其余各頂點之間的最短路徑，path是最短路徑的路徑數(shù)組，其中path[i]表示從源點到頂點i之間的最短路徑的前驅(qū)頂點。 因此，迪杰斯特拉算法可用自然語言描述如下： 初始化S和D，置空最短路徑終點集，置初始的最短路徑值； S[v1]=TRUE; D[v1]=0； //S集初始時只有源點，源點到源點的距離為0； While (S集中頂點數(shù)

56、短路徑及距離； } 3.2.3任意一對頂點間最短路徑 任意一對頂點間最短路徑問題，是對于給定的有向網(wǎng)絡(luò)圖G=（V，E），要對G中任意一對頂點有序?qū)Α皏,w(vw)”,找出v到w的最短路徑。 要解決這個問題，我們可以依次把有向網(wǎng)絡(luò)圖中每個頂點作為源點，重復(fù)執(zhí)行前面討論的迪杰斯特拉算法n次，即可以求得每對頂點之間的最短路徑。 這里還可以用另外一種方法，稱作費洛伊德（Floyd）算法。 費洛伊德（Floyd）算法算法的基本思想是：假設(shè)求從頂點 vi到vj的最短路徑。如果從vi到vj存在一條長度為arcs[i][j]的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑

57、,v1>和是否存在。如果存在，則比較和< vi,v1,vj >的路徑長度，取長度較短者為當(dāng)前所求得的最短路徑。該路徑是中間頂點序號不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點v2為中間頂點的路徑，若沒有，則說明從vi到vj的當(dāng)前最短路徑就是前一步求出的；若有，那么可分解為和,而這兩條路徑是前一次找到的中間頂點序號不大于1的最短路徑，將這兩條路徑長度相加就得到路徑的長度。將該長度與前一次中求出的從vi到vj的中間頂點序號不大于1的最短路徑比

58、較，取其長度較短者作為當(dāng)前求得的從vi到vj的中間頂點序號不大于2的最短路徑。依此類推，直到頂點vn加入當(dāng)前從vi到vj的最短路徑后，選出從vi到vj的中間頂點序號不大于n的最短路徑為止。由于圖G中頂點序號不大于n，所以vi到vj的中間頂點序號不大于n的最短路徑，已考慮了所有頂點作為中間頂點的可能性，因此，它就是vi到vj的最短路徑。 3.3【設(shè)計功能的實現(xiàn)】（用C或C++語言描述） 3.3.1 建立有向圖的存儲結(jié)構(gòu) //說明：要求由學(xué)生來完成代碼的編寫。 3.3.2 迪杰斯特拉算法 //說明：要求由學(xué)生來完成代碼的編寫。 3.3.3 費洛伊德算法 //說明：要求由學(xué)生來

59、完成代碼的編寫。 3.3.4 運行主控程序 //說明：要求由學(xué)生來完成代碼的編寫。 3.4【實例測試及運行結(jié)果】 3.4.1 運行實例一 （求給定有向圖3-1的最短路徑） 圖3-1 一個有向圖 具體要求之一：求頂點到其余頂點的最短路徑；分別求頂點b到頂點d之間的最短路徑、頂點到頂點d之間的最短路徑。 提示：為了操作方便，對于圖的頂點都是用序號來表示的，所以頂點的字母就用其對應(yīng)的序號來操作：如用1來代替，……。 3.4.2 運行實例二 （求給定有向圖3-2的最短路徑） 圖3-2 一個簡單的交通網(wǎng)絡(luò)圖 圖3-2 是一個簡單的交通網(wǎng)絡(luò)圖。 具體要求之一：

60、求頂點“北京”到其余各城市之間的最短路徑；并分別求“成都”到“上?！敝g以及“上?！钡健拔靼病敝g的最短路徑。 提示：為了操作方便，對于圖的頂點都是用序號來表示的，所以頂點的城市名稱就用其對應(yīng)的編號來操作：如北京用1來代替，……。 3.5【實現(xiàn)提示】 //說明：學(xué)生自己補充。 4．學(xué)生管理系統(tǒng) 專業(yè)： 班級： 姓名： 學(xué)號： 完成日期： 4.1【問題描述】 大學(xué)里有各種類型的學(xué)生，校方需要對這些學(xué)生的信息進(jìn)行計算機(jī)管理。所開發(fā)的軟件應(yīng)包括各類學(xué)生的添加、修改、刪除和查找等功能?？紤]到軟件的可

61、重用性、可擴(kuò)展性和可維護(hù)性，校方?jīng)Q定采用面向?qū)ο蟮某绦蛟O(shè)計方法來開發(fā)系統(tǒng)。學(xué)生信息需要以文件方式保存到計算機(jī)硬盤中。另外，系統(tǒng)的用戶界面應(yīng)該盡可能友好，方便用戶使用。 4.2【設(shè)計需求及分析】 (1) 使用C++語言開發(fā)，充分利用面向?qū)ο蟪绦蛟O(shè)計的類、對象、繼承、封裝和多態(tài)性等 (2) 概念設(shè)計和實現(xiàn)該管理系統(tǒng)。 (3) 設(shè)計一個Person（人員）類，考慮到通用性，只抽象出所有類型人員都具有的屬性：name（姓名）, id（身份證號），gender（性別），birthday（出生日期）等等。其中“出生日期”為內(nèi)嵌子對象，是一個Date（日期）類型，Date類具有屬性: year(年)

62、，month（月），day（日）。用成員函數(shù)實現(xiàn)對人員信息的錄入和顯示等必要功能操作。 (4) 從Person類派生出Student（學(xué)生）類，添加屬性： studentNo（學(xué)號），schoolName（學(xué)校），classIn (班級)。從Person類派生出Teacher（教師）類，添加屬性：teacherNo（教師編號），schoolName（學(xué)校），department（部門）。 (5) 從Student類中派生出UnderGraduate（本科生）類，添加屬性：major（專業(yè)）。從Student類中派生出Graduate（研究生）類，添加屬性：direction（研究方向），a

63、dviserName（導(dǎo)師姓名）。 (6) 從Graduate類和Teacher類派生出TＡ（助教博士生）類。 (7) 寫程序測試上述各類，看能否正常運行。 (8) 構(gòu)建必要的輔助類，實現(xiàn)對本科生、研究生和助教博士生的添加、修改、刪除、查詢管理。 (9) 根據(jù)需要定義類的構(gòu)造函數(shù)、析構(gòu)函數(shù)、拷貝構(gòu)造函數(shù)、成員函數(shù)。必要時重載函數(shù)。 (10) 要求將Person類設(shè)置為虛基類，以消除其派生類成員訪問的二義性問題（注意在虛基類各級派生類的構(gòu)造函數(shù)實現(xiàn)時調(diào)用虛基類的構(gòu)造函數(shù)）。 (11) 要求在Person類中定義虛函數(shù)displayDetails（），用于顯示當(dāng)前對象的信息；同時定義虛

64、函數(shù)inputData( )，用于從鍵盤獲取當(dāng)前對象的信息。Person類所有派生類也要定義同名虛函數(shù)，使程序可以實現(xiàn)動態(tài)多態(tài)性。 (12) 用菜單方式設(shè)計主控模塊程序。 (13) 對程序源代碼要給出各部分的詳細(xì)注釋，這也是該題目的考核重點之一。 (14) 用UML語言描述系統(tǒng)用到的類及其關(guān)系。 4.3【設(shè)計功能的實現(xiàn)】（用C或C++語言描述） //說明：此內(nèi)容由學(xué)生自己設(shè)計完成。 //以下代碼僅供參考。 程序框架: /************************************************* Copyright (C), 2013, Tyut

65、File name: main.cpp Author: gaobaolu Version: 1.0 Date: 2013.6.10 Description: 應(yīng)用程序主函數(shù) *************************************************/ #include #include #include "date.h" #include "person.h" #include "student.h" #include "teacher.h" #include "under

66、graduate.h" #include "graduate.h" #include "ta.h" #include "undergraduateManager.h" using namespace std; int main(int argc, char *argv[]) { int choiceN; UndergraduateManager unMan; cout<<"********************************************************"<