基于DOS菜單的應(yīng)用程序

1、 算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告系 （院）： 計算機科學(xué)學(xué)院 專業(yè)班級： 計科11005 姓 名： 學(xué) 號： 指導(dǎo)教師： 設(shè)計時間： 2012.6.11 - 2012.6.18 設(shè)計地點： 12教機房 目錄一、課程設(shè)計目的2二、設(shè)計任務(wù)及要求2三、需求分析2四、總體設(shè)計4五、詳細(xì)設(shè)計與實現(xiàn)含代碼和實現(xiàn)界面8六、課程設(shè)計小結(jié)15一設(shè)計目的1能根據(jù)實際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，分析并正確確定數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲結(jié)構(gòu)，并能設(shè)計出解決問題的有效算法。2提高程序設(shè)計和調(diào)試能力。學(xué)生通過上機實習(xí)，驗證自己設(shè)計的算法的正確性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代

2、碼中的錯誤并且修改。3初步掌握軟件開發(fā)過程中問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能。4訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。5培養(yǎng)根據(jù)選題需要選擇學(xué)習(xí)書籍，查閱文獻(xiàn)資料的自學(xué)能力。二設(shè)計任務(wù)及要求根據(jù)算法與數(shù)據(jù)結(jié)構(gòu)課程的結(jié)構(gòu)體系，設(shè)計一個基于dos菜單的應(yīng)用程序。要利用多級菜單實現(xiàn)各種功能。比如，主界面是大項，主要是學(xué)過的各章的名字諸如線性表、棧與隊列、串與數(shù)組及廣義表等，子菜單這些章中的節(jié)或者子節(jié)。要求所有子菜單退出到他的父菜單。編程實現(xiàn)時，要用到c+的面向?qū)ο蟮墓δ堋? 需求分析 菜單運用極其廣泛，應(yīng)用于各行各業(yè)。菜單運用

3、起來極其方便。隨著社會的發(fā)展，社會的行業(yè)出現(xiàn)多樣化，也就需要各式各樣的菜單。這就需要設(shè)計人員十分精細(xì)的設(shè)計。進(jìn)一步了解算法與數(shù)據(jù)結(jié)構(gòu)課程的知識結(jié)構(gòu)體系，繪制整個課程的知識結(jié)構(gòu)邏輯示意圖，類似于：排序查找圖樹串、數(shù)組、廣義表棧和隊列線性表 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計最小生成樹關(guān)鍵路徑冒泡排序插入排序快速排序shell排序最短路徑矩陣乘法矩陣轉(zhuǎn)置刪除元素插入元素創(chuàng)建鏈表查找元素應(yīng)用廣義表希哈查找技術(shù)二叉搜索樹折半查找順序查找樹的表達(dá)形式huffman壓縮解壓二叉樹括號匹配進(jìn)制轉(zhuǎn)換十進(jìn)制轉(zhuǎn)八進(jìn)制十進(jìn)制轉(zhuǎn)二進(jìn)制退出解壓文件壓縮文件根據(jù)算法與數(shù)據(jù)及結(jié)構(gòu)的課程安排，可以設(shè)計如上所示的菜單。在主菜單里可以有“線性表”

4、、“棧和隊列”、“串、數(shù)組、廣義表”、“樹”、“圖”、“查找”、“排序”。然后要在線性表里創(chuàng)建一個子菜單實現(xiàn)“創(chuàng)建鏈表”、“插入元素”、“刪除元素”、“查找元素”的功能。并且可以退出這個子菜單回到上一級菜單。棧和隊列創(chuàng)建一個子菜單，包含進(jìn)制轉(zhuǎn)換和括號匹配的功能。進(jìn)制轉(zhuǎn)換里又分為十進(jìn)制轉(zhuǎn)八進(jìn)制、十進(jìn)制轉(zhuǎn)二進(jìn)制。串、數(shù)組、廣義表里可以創(chuàng)建子菜單包含矩陣乘法、矩陣轉(zhuǎn)置的功能。樹里創(chuàng)建子菜單，有樹的創(chuàng)建、先序遍歷、中序遍歷、后序遍歷、樹的高度、葉子數(shù)這幾個選項。這些子菜單都能退出回到上一級菜單。四總體設(shè)計設(shè)計菜單類根據(jù)實際使用，我們知道菜單類的主要功能就是顯示菜單項與響應(yīng)用戶選項。所以我們可以這樣設(shè)計

5、一個菜單基類：class cmenubasepublic:cmenubase(void);cmenubase(void);virtual void showmenu()=0;virtual void event(int evenid)=0;protected:cmenubase* m_pparent;根據(jù)所繪制的知識結(jié)構(gòu)圖，設(shè)計dos菜單。例如在此基礎(chǔ)上，所有菜單類都繼承這個類，以此來實現(xiàn)“顯示”與“響應(yīng)事件”的多態(tài)性。例如，主菜單類的設(shè)計為：class cmainmenu:public cmenubasepublic:cmainmenu(void);cmainmenu(void);virtu

6、al void showmenu();virtual void event(int evenid);和基類基本沒有區(qū)別。其實現(xiàn)可以為void cmainmenu:showmenu()coutn *數(shù)據(jù)結(jié)構(gòu)課程設(shè)計*n;cout * 1 線性表 2 棧與隊列 3 串、數(shù)組和廣義表 *n;cout * 4 樹 5 圖 6 查找 *n;cout * 7 排序 8 退出 *n;coutshowmenu();通過構(gòu)造函數(shù)，將當(dāng)前菜單對象作為子菜單的父菜單，以后退出子菜單時，子菜單將將顯示權(quán)讓給其父菜單：#define exit_submenu tmp=m_pparent;delete pbase;pba

7、se=tmp;pbase-showmenu();這樣設(shè)計，無論有多少級菜單，其編程風(fēng)格都是一樣的，只需管理當(dāng)前的菜單交接，而無需知道它是從哪兒來的。還定義了線性表、棧和隊列、數(shù)組串和廣義表、樹等模板類。線性表的類如下：class clistmenu:public cmenubasepublic:clistmenu(cmenubase*);clistmenu(void);virtual void showmenu();virtual void event(int evenid);protected:void createlist_l(int n);status listinsert_l(int

8、i,elemtype e);status listout_l();status listdelete_l(int i,elemtype &e);status getelem_l(int i,elemtype &e);linklist l;棧和隊列的類如下class cstackmenu:public cmenubasechar name20;public:cstackmenu(cmenubase*);cstackmenu(void)virtual void showmenu();virtual void event(int evenid);protected:status initstack(

9、);status push (selemtype e);status pop(selemtype &e);void kuohao();sqstack s;進(jìn)制轉(zhuǎn)換的類定義如下class cjinzhimenu:public cmenubasechar name20;public:cjinzhimenu(cmenubase*);cjinzhimenu(void)virtual void showmenu();virtual void event(int evenid);protected:void conversion_8();void conversion_2();status initsta

10、ck();status push (jelemtype x);status pop(jelemtype &x);jsqstack s;數(shù)組的類定義如下：class cshuzumenu:public cmenubasechar name200;public:cshuzumenu(cmenubase*);cshuzumenu(void)virtual void showmenu();virtual void event(int evenid);protected:status creat_2(rlsmatrix &m,int x,int y);status putout_2(rlsmatrix

11、&m);status multsmatrix(rlsmatrix &m, rlsmatrix & n, rlsmatrix &q);status fasttransposesmatrix(tsmatrix &m, tsmatrix &t);void zhuanzhi();void chengfa();樹的類定義如下：class cshumenu:public cmenubasechar name20;public:cshumenu(cmenubase*);cshumenu(void)virtual void showmenu();virtual void event(int evenid);p

12、rotected:statuss visit(telemtype e);statuss createbitree(bitree &t1);statuss xianordertraverse(bitree t1);statuss zhongordertraverse(bitree t1);statuss houordertraverse(bitree t1);int depth(bitree t1);int countleaf(bitree t1);bitree t;每一級的菜單函數(shù)都可以根據(jù)以上類的模板來寫。方便且不容易遺漏出錯。5 詳細(xì)設(shè)計與實現(xiàn)線性表菜單顯示如下：線性鏈表菜單的設(shè)計則可能為

13、其實現(xiàn)則類似于clistmenu:clistmenu(cmenubase*parent)m_pparent=parent;void clistmenu:showmenu()cout *線性表*n;cout * 1 創(chuàng)建線性表 2 插入元素 *n;cout * 3 查找元素 4 刪除元素 *n;cout * 5 瀏覽 6 退出 *n;cout *n;void clistmenu:event(int evenid)cmenubase*tmp;switch(evenid)case id_create_list:coutn;list.createlist_l(n);cout當(dāng)前鏈表元素為endl;li

14、st.listout_l();system(pause);break;case id_list_insert:couti;coute; list.listinsert_l(i,e);cout當(dāng)前鏈表元素為endl;list.listout_l();system(pause);break;case id_list_show:list.listout_l();system(pause);break;case id_list_return:exit_submenubreak;case id_list_delete:couti;list.listdelete_l( i,e);cout當(dāng)前鏈表元素為en

15、dl;list.listout_l();system(pause);break;case id_list_find:couti;list.getelem_l(i,e);system(pause); break;default:invalidateaction();break;線性鏈表各功能具體實現(xiàn)代碼如下：創(chuàng)建鏈表：void clistmenu:createlist_l(int n)int i;linklist p; l=(linklist)malloc(sizeof(lnode); l-next =null; for(i=n;i0;i-) p=(linklist)malloc(sizeof(

16、lnode); cinp-data ; p-next = l-next;l-next = p;界面如下：查找元素：status clistmenu:getelem_l(int i,elemtype &e)int j;linklist p; p=l-next;j=1; while(p&jnext; j+; if(!p|ji) return error; e = p-data ;coutdata endl; return ok;插入元素：status clistmenu:listinsert_l(int i,elemtype e)linklist p,s; p=l;int j=0; while(p

17、&jnext;+j; if(!p|ji)return 0; s=(linklist)malloc(sizeof(lnode); s-data =e;s-next=p-next;p-next=s; return 1;刪除元素：status clistmenu:listdelete_l(int i,elemtype &e)linklist p,q;int j; p=l;j=0; while(p-next&jnext;j+; if(!(p-next)|ji-1)return 0; q=p-next;p-next=q-next;e=q-data;free(q); return 1;瀏覽所有元素：sta

18、tus clistmenu:listout_l()linklist p;p=l-next ;while(p) coutdata next ;return 0;棧和隊列菜單顯示界面如下：棧和隊列的菜單設(shè)計如下：其菜單函數(shù)為：void cstackmenu:showmenu()system(cls);/清屏cout *棧和隊列*n;cout * 1 括號匹配 2 進(jìn)制轉(zhuǎn)換 3 迷宮問題 4退出 *n;cout *n;cstackmenu stack(pbase);void cstackmenu:event(int evenid)cmenubase*tmp;switch(evenid) case i

19、d_kuo_hao: stack.kuohao();system(pause);break; case id_jin_zhi: submenu(cjinzhimenu);break;case id_mi_gong: cout此小項未完成endl;case id_stack_return: exit_submenu break;default:invalidateaction();break;其他項目做法與線性鏈表類似。由于字?jǐn)?shù)有限，其他項目功能的具體實現(xiàn)就不一一介紹了。我們這里定義了一些菜單常量，其定義可以放在一個resource.h文件中：#define id_list 1#define i

20、d_stack_queue 2#define id_str_arr_gl 3#define id_tree 4#define id_graph 5#define id_search 6#define id_sort 7#define id_exit 8#define id_create_list 1#define id_list_insert 2#define id_list_find 3#define id_list_delete 4#define id_list_show 5#define id_list_return 6#define id_kuo_hao 1 #define id_ji

21、n_zhi 2#define id_mi_gong 3#define id_stack_return 4#define id_ba 1#define id_er 2#define id_jinzhi_return 3#define id_cheng_fa 1#define id_zhuan_zhi 2#define id_shuzu_return 3#define id_chuang_shu 1#define id_xian 2#define id_zhong 3#define id_hou 4#define id_ye_zi_shu 5#define id_jiao_huan 6#define id_gao_du 7#define id_shu_return 8#define submenu(submenu )tmp=pbase;pbase=new submenu(tmp);#define exit_submenu tmp=m_pparent;delete pbase;pbase=tmp;void invalidateaction();在主函數(shù)中應(yīng)用菜單對象。bool main_exit;cmenubase*pbase;list*plist;void main()mai