《算法與數據結構課程設計》進度表班級：計科11101-11105課程設計題目：圖的基本操作及應用數據結構課程設計是在學完數據結構課程之后的實踐教學環節。該實踐教學是軟件設計的綜合訓練，包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧。要求學生在設計中逐步提高程序設計能力，培養科學的軟件工作方法。設計目的能根據實際問題的具體情況，結合數據結構課程中的基本理論和基本算法，分析并正確確定數據的邏輯結構，合理地選擇相應的存儲結構，并能設計出解決問題的有效算法。提高程序設計和調試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改。初步掌握軟件開發過程中問題分析、系統設計、程序編碼、測試等基本方法和技能。訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風。培養根據選題需要選擇學習書籍，查閱文獻資料的自學能力。設計任務設計一個基于DOS菜單的應用程序。要利用多級菜單實現各種功能。內容如下：無向圖的基本操作及應用創建無向圖的鄰接矩陣創建無向圖的鄰接表無向圖的深度優先遍歷無向圖的廣度優先遍歷無向網的基本操作及應用創建無向網的鄰接矩陣創建無向網的鄰接表求最小生成樹有向圖的基本操作及應用創建有向圖的鄰接矩陣創建有向圖的鄰接表拓撲排序有向網的基本操作及應用創建有向網的鄰接矩陣創建有向網的鄰接表關鍵路徑單源最短路徑每對頂點之間的最短路徑設計指導第一步：根據設計任務，設計DOS菜單。例如應c:\DocuMentsandSettingsVAdsinistrator\^^\...及作用用用用操應應應應本及及及及基圖本本本本一一基基基基X勺〔.勺：?勺：?勺：?lnplnplnplnp一一圖網圖網??向向向向出一一無無有有退二12345X二******選擇1之后應該類似于TOC\o"1-5"\h\zXJCNJCNNXNXNXNXJCX^F向圖的本才罕［乍屆應用NJCNJCNJCNJCNJCNJCNJCN創建無向圖的鄰腰矩陣 *創建無向圖的鄰卷表 *無向圖的榛度仕憲遍歷 *無向圖的廣度恍先遍歷 *退出 *第二步：設計菜單voidShowMainMenu(){cout<<"\n";cout<<"***************圖的基本操作及應用******************\n";cout<<"*1無向圖的基本操作及應用*\n";cout<<"*2無向網的基本操作及應用*\n";cout<<"*3有向圖的基本操作及應用*\n";cout<<"*4有向網的基本操作及應用*\n";cout<<"*5退出*\n";cout<<"***************************************************\n"；}voidUDG(){MGraphMG;ALGraphALG;intn;do{cout<<"\n";cout<<"***************無向圖的基本操作及應用***************\n"cout<<"*1創建無向圖的鄰接矩陣*\n";cout<<"*2創建無向圖的鄰接表*\n";cout<<"*3無向圖的深度優先遍歷*\n";cout<<"*4無向圖的廣度優先遍歷*\n";cout<<"*5退出 *\n”;cout<<"****************************************************\n"；cin>>n;switch(n){case1:CreatUDG_M(MG);break;case2:CreatUDG_ALG(ALG);dispgraph(ALG);break;case3:break;case4:break;default:if(n!=5)cout<<"錯誤，重新輸入\n”;}}while(n!=5);}voidUDN(){MGraphMN;ALGraphALN;intn;do{cout<<"\n";cout<<"***************無向網的基本操作及應用***************\n";TOC\o"1-5"\h\zcout<<" * 1創建無向網的鄰接矩陣 *\n";cout<<" * 2創建無向網的鄰接表 *\n";cout<<" * 3 prim算法求最小生成樹 *\n";cout<<" * 4 kraskal算法求最小生成樹 *\n";cout<<" * 5 退出 *\n";cout<<"****************************************************\n";cin>>n;switch(n){case1:CreatUDN_M(MN);break;case2:CreatUDN_ALG(ALN);dispgraph_N(ALN);break;case3:break;case4:break;default:if(n!=5)cout<<"錯誤，重新輸入\n”;}}while(n!=5);}voidDG(){intn;do{cout<<"\n";cout<<"***************有向圖的基本操作及應用***************\n";TOC\o"1-5"\h\zcout<<" * 1創建有向圖的鄰接矩陣 *\n”;cout<<" * 2創建有向圖的鄰接表 *\n";cout<<" * 3 拓撲排序 *\n";cout<<" * 4 退出 *\n";cout<<"****************************************************\n";cin>>n;switch(n){case1:break;case2:break;case3:break;default:if(n!=4)cout<<"錯誤，重新輸入\n”;}}while(n!=4);}voidDN()intn;do{cout<<"\n”;cout<<"***************有向網的基本操作及應用***************\n"；cout<<"*1創建有向網的鄰接矩陣*\n";cout<<"*2創建有向網的鄰接表*\n";cout<<"*3關鍵路徑*\n";cout<<"*4單源頂點最短路徑問題*\n";cout<<"*5每對頂點間最短路徑問題*\n";cout<<"*6退出*\n";cout<<"****************************************************\n"；cin>>n;switch(n){case1:break;case2:break;case3:break;case4:break;case5:break;default:if(n!=6)cout<<"錯誤，重新輸入\n”;}}while(n!=6);}voidmain(){intn;do{ShowMainMenu();cin>>n;switch(n){case1:UDG();break;case2:

UDN();break;case3:DG();break;case4:DN();break;default:if(n!=5)cout<<"錯誤，重新輸入\n”;}}while(n!=5);}無論多少級菜單，都可以用這種模式實現，并且當前菜單不用擔心前面的問題，只需編寫當前的功能函數。第二步：添加功能函數。對于使用類來做的同學，根據實際使用，我們知道菜單類的主要功能就是顯示菜單項與響應用戶選項。所以我們可以這樣設計一個菜單基類：classCMenuBase所以我們可以這樣設計一個菜單基類：classCMenuBase{public:CMenuBase(void);~CMenuBase(void);virtualvoidShowMenu()=0;virtualvoidEvent(intEvenID)=0;protected:CMenuBase*m_pParent;MenuBase#m_pParent:MenuBase率+Event(inEvenlD:int)+ShowMenu()+MenuBase0+^^MenuBase0};在此基礎上，所有菜單類都繼承這個類，以此來實現單類的設計為：classCMainMenu:publicCMenuBase{public:};在此基礎上，所有菜單類都繼承這個類，以此來實現單類的設計為：classCMainMenu:publicCMenuBase{public:CMainMenu(void);~CMainMenu(void);virtualvoidShowMenu();virtualvoidEvent(intEvenID);顯示”與“響應事件”的多態性。例如，主菜ClainHenu+CMainMenu()+^CMairLMenu()+ShowMenu()+Event(inEvenlD:int)};和基類基本沒有區別。其實現可能為voidCMainMenu::ShowMenu(){cout<<"\n**************《數據結構課程設計》*****************\n";cout<<"*1線性表2棧與隊列3串、數組和廣義表*\n”;cout<<"*4樹5圖 6查找 *\n”;cout<<"*7排序8退出 *\n";cout<<"***************************************************\n"；}voidCMainMenu::Event(intEvenID){CMenuBase*tmp;switch(EvenID){caseID_LIST:break;caseID_STACK_QUEUE:SUBMENU(CStackAndQueueMenu)break;// caseID_EXIT:MAIN_EXIT=true;break;default:InvalidateAction();break;}}注意：這里的關鍵是如何進入子菜單，我們用了一個宏命令，例如SUBMENU(CListMenu),其定義為：#defineSUBMENU(submenu) tmp=pBase;\pBase=newsubmenu(tmp);\pBase->ShowMenu();通過構造函數，將當前菜單對象作為子菜單的父菜單，以后推出子菜單時，子菜單將將顯示權讓給其父菜單：#defineEXIT_SUBMENUtmp=m_pParent;\deletepBase;\pBase=tmp;\pBase->ShowMenu();這樣設計，無論有多少級菜單，其編程風格都是一樣的，只需管理當前的菜單交接，而無需知道它是從哪兒來的。成績評定實習報告(文字不得少于4000字)課程設計目的；設計任務及要求；需求分析；詳細設計(實現過程)；課程設計小結(難點、收獲、存在不足、改進)；程序實現完成基本結構圖，程序中有三級菜單，完成基本操作者及格；在第一條的基礎上，任務完成的越多，成績等級越高。使用面向對象實現的可以適當加分。成績由三部分組成：平時考核(20%)、程序實現(50%)、實習報告(30%)申請不在機房做的同學：平時成績就加入到程序實現里面也就是程序實現70%《算法與數據結構課程設計》時間安排班級：計科11級人數：170時間：13年6月17日-13年6月29日班級：計科11級人數：170上機學時：40學時17周周一周二周三周四周五周日上午計 科11101-11105下午晚上計科11101-11105計科11101-11105計科11101-11105計科11101-11105計科11101-1110518周周一周二周三周四周五上午下午晚上計科11101-11005計科11101-11105計科11101-11105說明：每班安排1名指導教師，負責布置任務、指導編程及編寫報告、指導學生熟悉開發環境和輔導學生調試程序，并對學生進行考勤。最后對學生完成的系統進行現場驗收和評定成績。計科11101周云才計科11102馮偉計科11103馮偉計科11104陳勇計科1110