数据结构课程设计-前序+中序构造二叉树的算法演示.doc

数据结构课程设计报告数据结构课程设计报告题 目：前序+中序构造二叉树的算法演示学生姓名：卜崇宇学 号：2012014312专 业：计算机科学与技术班 级：计科1202指导教师：刘勇 2013年 12 月 30 日目录目录2任务书3【摘要】41程序主要功能62. 程序总体设计61）文件结构62） 主要类73） 程序结构73. 程序详细设计83.1 主窗体(CMylog:Dialog):83.2 窗体 2_二叉树的后序输出和树的高度(D2:Dialog):93.3 窗体3_辅助功能(D11:Dialog):93.4 窗体4_构造过程(XP:Dialog):94. 运行结果95. 附录：（代码）14任务书课程名称数据结构课程设计设计题目 前序+中序构造二叉树的算法演示指导教师刘勇时间2013.12.302014.1.3一、教学要求二、设计资料及参数三、设计要求及成果学号最后2位%21+1所得结果对应的课设题目如2012014452将选择20题1 中国象棋 2 五子棋 3 链表的算法（构造、插入、删除、反转）演示 4 栈的算法（构造、入栈、出栈）演示 5 四则运算表达式的算法演示（用栈实现） 6 走迷宫的算法演示（用栈实现） 7 前序+中序构造二叉树的算法演示 8 哈夫曼树的算法演示 9 图的拓扑排序算法演示 10 图的关键路径算法演示 11 图的最短路径算法演示-迪杰斯特拉算法 12 图的最短路径算法演示-弗洛伊德算法 13 OJ做题情况分析：班级总AC排名、宿舍总AC排名、2-8定律、做题时间点分布排名、周末做题比例 14 快速排序的算法演示15 堆排序的算法演示16 坦克大战17 最小生成树算法演示-迪杰斯特拉算法18 最小生成树算法演示-普利姆算法19 平衡二叉树的算法演示20 二叉排序树的算法演示21 排序算法性能分析（选择、冒泡、插入、快速、堆排序、希尔排序、未排序因子）以最短路径算法举例：成绩 完成情况D,C- 基本没有完成 C,C+ 用DOS界面基本完成算法，有明显BUGB- 用DOS界面完成算法，数据量较小，没有明显BUGB 用DOS界面完成算法，数据量较大，没有明显BUGB+,A- 用MFC或者C#完成界面，数据量较大，没有明显BUGA 用MFC或者C#完成界面，数据量较大，有应用背景，没有明显BUG，既能一步出结果，也能单步看过程A+ 满足A的基础上，没有任何BUG，数据量大，功能完备，界面美观大方、考虑到代码重用性以上是程序成绩，结合报告的成绩：如果报告写得不好，降低1到2个档次如果报告写的很好，则提升1到2个档次报告写得好的标准有：格式一致、分章分节有目录、没有错别字、有图有表有题注、图表在文字中有引用、有关键代码、有设计算法20 功能20 界面15 问题35 报告30四、进度安排第一天 选择课程设计题目，分析课题的要求，设计程序结构第二天 编程第三天 编程，写报告第四天 提交课程设计报告（打印稿及电子稿）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。六、建议参考资料【摘要】本次课程设计我主要采用了树和二叉树，递归和非递归等的知识。我采用MFC进行实现的，计算过程展现的活灵活现、操作方便和通俗易懂等，是本课设的主要特点。通过本次课程设计，我对数据结构和MFC语言有了更深的理解，让我把学到的理论应用于具体实践中，锻炼了我各方面的能力，从而让我更快提高，本次课设很大程度上增加了我的自学能力和提高了专业知识水平。前序+中序构造二叉树的算法演示具有以下功能：1. 通过前序和中序单步实现二叉树的构造，不符合的输入会有提示。2. 通过前序和中序一步实现二叉树的构造，不符合的输入会有提示。3. 在遍历过程中可以返回单步构造时的上一步。4. 一首轻音乐或者一个搞笑的图片会让人轻松片刻。5. 显示代码执行的过程。6. 操作方便，直接鼠标右击可点击菜单栏，选择不同的功能。1程序主要功能程序的主要功能包括：1） 输入前序和中序，如果输入前序或者中序不能构成二叉树，不会像某些程序一样面临崩溃，很人性化的给你提示。2） 通过前序和中序一步实现二叉树的构造，不符合的输入会有提示3） 在遍历过程中可以返回单步构造时的上一步。4） 一首轻音乐或者一个搞笑的图片会让人轻松片刻。5）显示代码执行的过程。6）操作方便，直接鼠标右击可点击菜单栏，选择不同的功能。2. 程序总体设计1）文件结构 主窗体（二叉树） 菜单 辅助功能 算法演示 2）主要类/数据结构 #includeD2.h #includeD11.h #includeXP.h 3）程序结构class BITree private: tree root; int keynum; public: BITree() void Judge(char *pre,char *in); /判断不符合的情况 void Search(char *pre,char *in) ; /建立二叉树 void Pre() ; /前序确定位置 void Post(); /后序 int GetHight() ; /树的高度 Class CMyDlg : public CDialogpublic: CMyDlg(CWnd* pParent = NULL);/ standard constructor void DrawRect(int x1,int x2,int x3,int x4); /画长方形void DrawLine(int x1,int x2,int x3,int x4); /画线void DrawCir(int x1,int x2,int x3); /画圆void FillBack();/填充背景 void OnButton2();/一步生成图形void OnButton3();/单步生成图形HBRUSH OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor);void OnButton4();/重置void OnButton5(); /上一步 void OnMenuitem32774();/菜单函数关闭 void OnMenuitem32786();/菜单函数音乐class D2 : public CDialogpublic: D2(CWnd* pParent = NULL); virtual void OnSetFont(CFont* pFont);protected:virtual void DoDataExchange(CDataExchange* pDX); protected: void OnOK(); BOOL OnInitDialog();void OnPaint(); void OnButton3();/关闭窗口;class D11 : public CDialog public:D11(CWnd* pParent = NULL); virtual void DoDataExchange(CDataExchange* pDX); protected: void OnPaint();/显示一张图片virtual BOOL OnInitDialog();class XP: public CDialog public:XP()CWnd* pParet = NULL); virtual void DoDataExchange(CDataExchange* pDX); protected: void OnPaint();/显示构造过程virtual BOOL OnInitDialog();3. 程序详细设计3.1主窗体:(CMylog:CDialog) （1）void DrawRect(int x1,int x2,int x3,int x4); 根据四个值来画长方形，(x1,x2)长方形代表左上角的坐标，(x3,x4)代表长方形的长和宽。此函数用于实现上一步的功能。 （2）void DrawLine(int x1,int x2,int x3,int x4); 根据直线的起始点和终止点来画直线。其中，(x1,x2)是起始点坐标，（x3,x4）是终止点坐标。 （3）void DrawCir(int x1,int x2,int x3); 根据圆的圆心（x1,x2）和圆的半径x3画圆。 （4）void FillBack(); 自动填充背景，主要实现重置功能。 （5）void OnButton2(); 步生成图形的按钮函数，调用DrawRect(),DrawLine(),DrawCir()数实现功能。 （6）void OnButton3(); 单步生成图形，调用DrawRect(),DrawLine(),DrawCir()函数实现功能。 （7）void OnButton4(); 清空编辑框中的内容，重置二叉树。调用MFC的类函数。 （8）void OnButton5(); 实现上一步 （9）void OnMenuitem32774(); 打开子对话框，其他的类似函数不在现实。 （10）void OnMenuitem32786(); 实现声音的关闭。3.2窗体2:（D2:CDialog） （1）void OnPaint(); 显示树的高度和后序遍历。 （2）void OnButton3(); 退出函数。3.3窗体3：（D11:CDialog） void OnPaint(); 显示恶搞图片。3.4窗体4:（XP:CDialog） void OnPaint(); 用于显示构造过程。4. 运行结果 各运行功能的截图。 图1.单步生成 图2.一步生成 图3.上一步（1） 图4.上一步（2） 图5.后序的实现 图6.人性化的提示（1） 图7.人性化的提示（2） 图8.比较过程 图9.帮助对话框5. 附录：（关键代码）/*(CMylog:CDialog)*/文件内容：class BITree private: tree root; int keynum; public: BITree() root =NULL; keynum=1; void Judge(char *pre,char *in) for(int i=0;idata=pre0; strcpy(pr1pi,pre); strcpy(in1pi,in); pi+; int i; for(i=0;ileft=lchild; head-right=rchild; return head; int Pow() int t=GetHight(),k=1; for(int i=0;ileft); Post(p-right); popoi=p-data; poi+; void Pre(BINode *&p,int t,int x,int y) if(p!=0) tytp1.x=x; tytp1.y=y; tytp1.d=p-data; tp1+; int k=t/2; if(p-left) txtp.x=x; txtp.y=y; txtp.x1=x-k; txtp+.y1=y+50; Pre(p-left,k,x-k,y+50); if(p-right) txtp.x=x; txtp.y=y; txtp.x1=x+k; txtp+.y1=y+50; Pre(p-right,k,x+k,y+50); int GetHight() return GetHight(root); int GetHight(tree p) if(p=NULL|kx!=1) return 0 ; else int t = GetHight(p-left); int t1 = GetHight(p-right); if(tt1) return 1+t; else return 1+t1; ; void CMyDlg:DrawLine(int x1,int x2,int x3,int x4)CClientDC dc(this);dc.MoveTo(x1,x2);/从当前点移动到画图起始点dc.LineTo(x3,x4); dc.ReleaseAttribDC();void CMyDlg:DrawRect(int x1,int x2,int x3,int x4) HDC hdc=:GetDC(m_hWnd); CClientDC dc(this);CBrush brush(RGB(0,0,0); /dc.Rectangle(x1,x2,x3,x4);dc.FillRect(CRect(x1,x2,x3,x4),&brush);dc.ReleaseAttribDC();void CMyDlg:DrawCir(int x1,int x2,int x3) HDC hdc=:GetDC(m_hWnd); CClientDC dc(this); dc.Ellipse(x1-x3,x2-x3,x1+x3,x2+x3); dc.ReleaseAttribDC();void CMyDlg:FillBack() CRect rect; CPaintDC dc(this); GetClientRect(rect); dc.FillSolidRect(rect,RGB(189,250,200);void CMyDlg:OnButton4() CClientDC dc(this);CFont font;font.CreatePointFont(200,楷书,NULL);CFont *pOldFont=dc.SelectObject(&font);dc.SetTextColor(RGB(0,0,0);TEXTMETRIC tm;dc.GetTextMetrics(&tm); HDC hdc; hdc=:GetDC(m_hWnd);dc.SetBkMode(TRANSPARENT); char a100,b100; kx=1; if(x=0) BITree t; UpdateData(true); strcpy(a,m_1); strcpy(b,m_2); t.Judge(a,b); t.Search(a,b); if(hight=t.GetHight()&t.GetHight()=6)MessageBox(树的高度需保持在6以内); else t.Pre(); hight=t.GetHight(); t.Post(); UpdateData(false); DrawLine(txx1.x,txx1.y+25,txx1.x1,txx1.y1+25);x1+;*(D2:CDialog)*/文件内容：void D2:OnPaint() CPaintDC dc(this); CRect rect; GetClientRect(rect); dc.FillSolidRect(rect,RGB(189,250,200); har p100; CFont font; font.CreatePointFont(300,楷体,NULL);CFont *pOldFont=dc.SelectObject(&font);dc.SetTextColor(RGB(0,0,0);TEXTMETRIC tm;dc.GetTextMetrics(&tm); HDC hdc; hdc=:GetDC(m_hWnd);dc.SetBkMode(TRANSPARENT);:SelectObject(hdc,CreatePen(PS_SOLID,2,RGB(0,0,0);dc.TextOut(400,25,二叉树);UpdateData(true);extern char po100;extern int hight;char t19;if(hight=1)itoa(hight-1,t,10); m_2=t;else m_2=空白输入; m_1=po; UpdateData(false);*(D11:CDialog)*/文件内容：void D11:OnPaint() CPaintDC dc(this); CRect rect; GetClientRect(rect); dc.FillSolidRect(rect,RGB(189,250,200); char p100; CFont font; font.CreatePointFont(200,楷体,NULL);/字体的大小和字体 CFont *pOldFont=dc.SelectObject(&font); dc.SetTextColor(RGB(0,0,0);/字体颜色RGB TEXTMETRIC tm; dc.GetTextMetrics(&tm); HDC hdc; hdc=:GetDC(m_hWnd);dc.SetBkMode(TRANSPARENT);:SelectObject(hdc,CreatePen(PS_SOLID,2,RGB(0,0,0); dc.TextOut(0,0,二叉树，不能称的上是个高端大气上档次的程序。); dc.TextOut(0,25,其中，有三个主要功能:); dc.TextOut(0,50,第一：单步实现输出构造出来的二叉树); dc.TextOut(0,