数据结构课程设计报告-含菜单(共17页).doc

《数据结构课程设计报告-含菜单(共17页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-含菜单(共17页).doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 算法与数据结构课程设计报告系 （院）： 计算机科学学院 专业班级： 计科11005 姓 名： 张林峰 学 号： 指导教师： 詹泽梅 设计时间： 2012.6.11 - 2012.6.18 设计地点： 12教机房 目录15一设计目的1能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3初步掌握软件开发过程中问题分析、系统设计、程序编码、测

2、试等基本方法和技能。4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5培养根据选题需要选择学习书籍，查阅文献资料的自学能力。二设计任务及要求根据算法与数据结构课程的结构体系，设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。比如，主界面是大项，主要是学过的各章的名字诸如线性表、栈与队列、串与数组及广义表等，子菜单这些章中的节或者子节。要求所有子菜单退出到他的父菜单。编程实现时，要用到C+的面向对象的功能。三 需求分析 菜单运用极其广泛，应用于各行各业。菜单运用起来极其方便。随着社会的发展，社会的行业出现多样化，也就需要各式各样的菜单。

3、这就需要设计人员十分精细的设计。进一步了解算法与数据结构课程的知识结构体系，绘制整个课程的知识结构逻辑示意图，类似于：排序查找图树串、数组、广义表栈和队列线性表 数据结构课程设计最小生成树关键路径冒泡排序插入排序快速排序shell排序最短路径矩阵乘法矩阵转置删除元素插入元素创建链表查找元素应用广义表希哈查找技术二叉搜索树折半查找顺序查找树的表达形式Huffman压缩解压二叉树括号匹配进制转换十进制转八进制十进制转二进制退出解压文件压缩文件根据算法与数据及结构的课程安排，可以设计如上所示的菜单。在主菜单里可以有“线性表”、“栈和队列”、“串、数组、广义表”、“树”、“图”、“查找”、“排序”。然

4、后要在线性表里创建一个子菜单实现“创建链表”、“插入元素”、“删除元素”、“查找元素”的功能。并且可以退出这个子菜单回到上一级菜单。栈和队列创建一个子菜单，包含进制转换和括号匹配的功能。进制转换里又分为十进制转八进制、十进制转二进制。串、数组、广义表里可以创建子菜单包含矩阵乘法、矩阵转置的功能。树里创建子菜单，有树的创建、先序遍历、中序遍历、后序遍历、树的高度、叶子数这几个选项。这些子菜单都能退出回到上一级菜单。四总体设计设计菜单类根据实际使用，我们知道菜单类的主要功能就是显示菜单项与响应用户选项。所以我们可以这样设计一个菜单基类：class CMenuBasepublic:CMenuBase

5、(void);CMenuBase(void);virtual void ShowMenu()=0;virtual void Event(int EvenID)=0;protected:CMenuBase* m_pParent;根据所绘制的知识结构图，设计DOS菜单。例如在此基础上，所有菜单类都继承这个类，以此来实现“显示”与“响应事件”的多态性。例如，主菜单类的设计为：class CMainMenu:public CMenuBasepublic:CMainMenu(void);CMainMenu(void);virtual void ShowMenu();virtual void Event(

6、int EvenID);和基类基本没有区别。其实现可以为void CMainMenu:ShowMenu()coutn *数据结构课程设计*n;cout * 1 线性表 2 栈与队列 3 串、数组和广义表 *n;cout * 4 树 5 图 6 查找 *n;cout * 7 排序 8 退出 *n;coutShowMenu();通过构造函数，将当前菜单对象作为子菜单的父菜单，以后退出子菜单时，子菜单将将显示权让给其父菜单：#define EXIT_SUBMENU tmp=m_pParent;delete pBase;pBase=tmp;pBase-ShowMenu();这样设计，无论有多少级菜单，

7、其编程风格都是一样的，只需管理当前的菜单交接，而无需知道它是从哪儿来的。还定义了线性表、栈和队列、数组串和广义表、树等模板类。线性表的类如下：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 i,ElemType e);Status ListOut_L();Statu

8、s 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();Status Push (SElemType e);Status Pop

9、(SElemType &e);void Kuohao();SqStack S;进制转换的类定义如下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 InitStack();Status Push (JElemType x);Status

10、Pop(JElemType &x);JSqStack s;数组的类定义如下：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 &M);Status MultSMatrix(RLSMatrix &M, R

11、LSMatrix & 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);protected:Statuss Visit(TElemType e);St

12、atuss 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;每一级的菜单函数都可以根据以上类的模板来写。方便且不容易遗漏出错。五 详细设计与实现线性表菜单显示如下：线性链表菜单的设计则可能为其实现则类似于CListMenu:CListMenu(CMenuBase*p

13、arent)m_pParent=parent;void CListMenu:ShowMenu()cout *线性表*n;cout * 1 创建线性表 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当前链表元素为endl;list.ListOut_L();system(pause);break;cas

14、e ID_LIST_INSERT:couti;coute; list.ListInsert_L(i,e);cout当前链表元素为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当前链表元素为endl;list.ListOut_L();system(pause);brea

15、k;case ID_LIST_FIND:couti;list.GetElem_L(i,e);system(pause); break;default:InvalidateAction();break;线性链表各功能具体实现代码如下：创建链表：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(LNode); cinp-data ; p-next = L-next;L-

16、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&jnext;+j; if(!p|ji)return 0; s=(LinkL

17、ist)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;浏览所有元素：Status CListMenu:ListOut_L()LinkList p;p=

18、L-next ;while(p) coutdata next ;return 0;栈和队列菜单显示界面如下：栈和队列的菜单设计如下：其菜单函数为：void CStackMenu:ShowMenu()system(cls);/清屏cout *栈和队列*n;cout * 1 括号匹配 2 进制转换 3 迷宫问题 4退出 *n;cout *n;CStackMenu stack(pBase);void CStackMenu:Event(int EvenID)CMenuBase*tmp;switch(EvenID) case ID_KUO_HAO: stack.Kuohao();system(pause

19、);break; case ID_JIN_ZHI: SUBMENU(CJinzhiMenu);break;case ID_MI_GONG: cout此小项未完成endl;case ID_STACK_RETURN: EXIT_SUBMENU break;default:InvalidateAction();break;其他项目做法与线性链表类似。由于字数有限，其他项目功能的具体实现就不一一介绍了。我们这里定义了一些菜单常量，其定义可以放在一个resource.h文件中：#define ID_LIST 1#define ID_STACK_QUEUE 2#define ID_STR_ARR_GL 3

20、#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_JIN_ZHI 2#define ID_MI_GONG 3#define ID_

21、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#d

22、efine SUBMENU(submenu )tmp=pBase;pBase=new submenu(tmp);#define EXIT_SUBMENU tmp=m_pParent;delete pBase;pBase=tmp;void InvalidateAction();在主函数中应用菜单对象。bool MAIN_EXIT;CMenuBase*pBase;List*pList;void main()MAIN_EXIT=false;pBase=new CMainMenu;pBase-ShowMenu();int EventID=0;char CammandLine255=0;while(MA

23、IN_EXIT=false)cinCammandLine;if(strlen(CammandLine)=0)coutEvent(EventID);if(pBase)delete pBase;if(pList)delete pList;在这儿定义了两个全局指针，菜单指针pBase和链表指针pList（要的话还可以添加其他指针）。六 课程设计小节 经过一学期的数据结构课程的学习，我现在编程已经比以前模块化多了，这样既不容易出错，而且出了错也较容易查出，其可读性也加强了。学会了运用类，知道了继承、多态。在做数组那个大项时出现了问题，运行处结果了，但同时也弹出了一个debug error，经过老师的指

24、导，原来是差一个引用字符，也就是要使形参和实参指向同一个字母。还有树里也出了问题，不能遍历，请教张凡凡同学，也得到了解决，是因为我重复定义了visit。程序的实用性是很重要的，这就是我的收获。另外，由于编程的积累，我发现调试程序的速度明显加快了，这是个很好的进步，不过，我编程的速度仍然有待提高，我思考过了，导致慢的原因可能有以下几点：1、打字速度慢。（这点的确的克服）2、算法没有很熟，只是想一想能出来，而远没有应到的境界。3、编程时精神不能太集中，不过这点一比以前好多了。4、这是最后，也是最重要的一点，编的程序还不够多，所谓熟能生巧嘛。综上所述，我还是要好好努力，继续历练的，以提高编程能力目标而继续热情的奋斗！指导老师意见：成绩: 教师签名： 年 月 日专心-专注-专业