数据结构课程设计报告(2).doc

计算机与信息学院数据结构课程设计实验报告专 业 班 级计算机074班学生姓名及学号课程教学班号0002任 课 教 师实验指导教师实验地点2008 2009 学年第 二 学期题目1：设计程序完成如下功能：对给定的图结构，用kruskal算法的基本思想求解图的最小生成树，并给出动态演示过程题目2：设计一个模拟计算器的程序，要求能包含加、减、乘、除、括号运算符，以及sqrt和abs对任意整型表达式进行求解。 要求：要检测运算执行的条件并给出错误警报 一、动态演示kruskal算法1、题目分析及建立模型在图的算法中，求最小生成树有着十分重要的理论和现实意义，二kruskal算法正是求解这一问题的经典算法。kruskal算法的主要思想即是通过不断地寻求满足一定条件（即所选边不能构成环）的最小权值的边，直至找出图的最小生成树为止。为了能够动态地演示kruskal算法求解最小生成树的过程，首先的问题是如何动态的建立一个图，然后的问题才是怎样动态地演示kruskal算法。所以为了解决这个问题，我从这两个方面逐一入手进行求解，利用mfc的知识进行演示。2、算法的设计与具体的设计思路a、程序界面的设计 首先为了建立一个图，需要知道一个图的节点数，由于界面有限，这里将节点数限制在8以内（包括8），超出8个将会给出提示。所以在程序界面中必须有图节点数目的输入，这里设计了一个编辑框用于输入图的节点数目。另外，一个完整的图还必须有一定的边信息，包括边的起始端点和权值，以便求解最小生成树。而这些信息完全是由用户确定的，并且由用户输入的图的节点数确定。这里在用于输入节点数的编辑框下设置两个列表框和一个编辑框分别用于边的起始端点和权值的输入。另外，为了使节点数和边信息产生关联，这里又设置了一个“应用”按钮，为了将边信息与图相关联，又设置了一个“增加边”按钮，最后还有一个“动态演示kruskal算法”的操作按钮以及一个退出按钮。此外，在界面的右端设置一个图形演示区，已进行动态演示。完整的程序界面如下：b、按钮响应函数的设计 在上述界面中有三个主要按钮，分别是“应用”“增加边”以及“动态演示kruskal算法,下面分别设计其响应函数 “应用”按钮的主要作用是把图的节点数和边信息和图相关联。用户在编辑框m_vexnum中输入结点，然后点击“应用”按钮后，在两个列表框m_start和m_end中自动添加n各结点，同时在演示区中画出n个节点，如下所示:为了关联相关信息，在csmilegraph1dlg中增加如下变量：graph graph; int vexnum;在按钮的响应函数onapply()中完成如下功能，一是在初始化图graph：/初始化一个图graph.graph_vexnum = 0;for(int j = 0; j 8; j+)graph.data j = (char)(a+j);for(int i = 0; i 8; i+)for(int j = 0; j 8; j+)graph.adjmatrix ij = graph.adjmatrix ji =inf;二是将编辑框中的内容与图和列表框关联起来同时在演示区中绘制n个节点，如下所示：/输入图的节点数cstring s ;m_vexnum.getwindowtext (s);int v_num = (int)atoi(s); /添加图的相关参数graph.graph_vexnum = v_num;for(int t = 0; t graph.graph_vexnum ; t+)graph.data t = (char)(a+t);if(v_num0) draw(v_num);else if(v_num8)messagebox(请输入1到8之间的一个数!);elsemessagebox(你还没有输入结点数!);m_start.resetcontent();m_end.resetcontent ();for(int k = 0; k v_num; k+)m_start.addstring (vexnodek);m_end.addstring (vexnodek);为了在演示区中绘制n个结点，在onapply函数中调用函数draw(v_num);在函数draw(int n)中绘制n个节点，为了限制结点个数，在演示区中固定了8个点供演示。这8个点的组成形式如下：将这8个点保存在point数组point中，同时以这8个点为中心作8个矩形rect rcdraw8保存图的结点的外接矩形，并根据m_vexnum的大小利用mfc绘图函数绘制m_vexnum内切圆作为图的结点。“增加边”按钮的主要功能是输入图的边信息并与图关联起来，为此在csmilegraph1dlg类中增加变量edge edge56用于保存用户输入的边信息。用户通过两个列表框选择一条边的两个端点并把其权值输入到下面的编辑框中，然后单击“增加边”按钮即可完成：在演示区中绘制一条边并显示其权值，修改图graph的边信息，即改变其邻接矩阵值。这里规定：两次输入同一条边、输入的结点不存在、结点相同均视为无效，并给出提示，演示如下: 无效输入一、一条边的两个端点相同 无效输入二、输入边已经存在正常情况下可得到如下所示的图：以上效果均通过按钮的响应函数onaddedge()来实现:int start,end;/保存一条边的两个端点start = m_start.getcursel (); end = m_end.getcursel (); cstring val ; m_value.getwindowtext (val);/获取权值 int value = atoi(val); /处理特殊情况 if(graph.adjmatrixstartend!=inf) messagebox(改边已经存在); else if(start=lb_err|end=lb_err) messagebox(结点不存在!); else if(start=end) messagebox(起始端点不应为同一结点!); else /增加图的边 edgeedge_num.start = start; edgeedge_num.end = end; edgeedge_num.val = value; edge_num+;/边数/修改图的邻接矩阵 graph.adjmatrix startend = graph.adjmatrix endstart = value; drawedge(start,end,val);/绘制两个端点分别为start和/end,权值为val的边 在onaddedge()函数中调用了一个绘制边的函数drawedge(int,int,int),三个参数分别表示新增边的起始端点序号和权值，这里成为“起始端点”只是表述方便，实际上所建立的是无向图。而在函数drawedge中，主要利用了mfc的绘图函数ellipse()、lineto()、textout()等，具体实现细节请见源码，这里不再赘述。“动态演示kruskal算法”的响应函数为本题的核心，kruskal算法的实现在此。这里先说明一下此按钮的功能：用户按下此按钮后，将在演示区中动态的寻求最小权值的边并用差异颜色重画以达到突出的目的，依次找出所有的符合条件的边后,擦除其他边只显示最小生成树的各边，具体过程如下:图1、动态寻找过程 图2、最终结果 下面介绍一下kruskal算法的实现思想，因为kruskal算法是不断的从图的边中寻求权值最小的边，所以首先对图的所有边按权值进行排序，这里使用快速排序，因此在csmilegraph1dlg中又增加了两个成员函数partition()和qiuck_sort()来实现数组edge的排序工作。接下来就是不断的从排好序边中依次选取满足条件的边。这里满足的【条件】是指所选边和之前所选边不能构成环。为此，特设置两个标志数组visited和is_min_tree分别标记结点和边是否已被选中。如果visitedi = visitedj或者is_min_treei,j=true说明再选取边（i,j）即会构成环，应当舍弃，继续往下寻找，直至找出含有n的节点的n-1个最小生成树的n-1条边,这里需要进行n-1趟循环。3、程序实现a、图的实现 本题采用邻接矩阵存储图，定义一个graph和edge结构体分别保存图的具体信息和边信息。定义如下：struct edgenodeint start;/起点int end;/终点int val;/权值;struct graphint adjmatrix88;/邻接矩阵char data8;/节点值int graph_vexnum;/节点数;b、排序的实现void csmilegraph1dlg:partition(edgenode *edge, int s, int t, int &cutpoint) edgenode tmp; tmp.start = edges.start ; tmp.end = edges.end;tmp.val = edges.val ; int i = s; int j = t; while(ij) while(i edgei.val) j-; if(ij) edgei.start = edgej.start; edgei.end = edgej.end;edgei.val = edgej.val;i+; while(ij&edgei.val edgej.val) i+; if(ij) edgej.start = edgei.start; edgej.end = edgei.end;edgej.val = edgei.val;j-; edgei.start = tmp.start; edgei.end = tmp.end;edgei.val = tmp.val;cutpoint = i; void csmilegraph1dlg:quick_sort(edgenode *edge, int s, int t)if(st)int i;partition(edge,s,t,i);/取得划分点quick_sort(edge,s,i-1);/对左半部分进行快速排序quick_sort(edge,i+1,t);/对右半部分进行快速排序c、kruskal算法的实现/把图的边按照权值大小排序quick_sort(edge,0,edge_num-1);int visited8 ;/标记每一条支边的端点以判断是否形成回路for(i=0;i8;i+)visitedi = i;/初始化int min = inf;int min_start,min_end;/标志数组判断某一边是否为最小生成树的一支bool is_min_tree88;/标记一条边是否被选中for(min_start = 0; min_start8 ; min_start+)for(min_end = 0; min_end8 ; min_end+)is_min_treemin_startmin_end = is_min_treemin_endmin_start = false;/初始化 int count = 0;/kruskal算法演示1: 排序法for(int s = 0; s graph.graph_vexnum - 1; s+)if(countedge_num) int m = edgecount.start; int n = edgecount.end;while(visitedm=visitedn)/找不能构成环的边 count+; m = edgecount.start; n = edgecount.end;/如果边不能构成环，则记录并绘制改边if(visitedm!=visitedn&!is_min_treemn&!is_min_treenm) min_start = m; min_end = n; min = edgecount.val; count+; for(int k = 0; k graph.graph_vexnum; k+)if(visitedk=visitedmin_end|visitedk=min_end)visitedk = visitedmin_start;/为选中结点做标记is_min_treemin_startmin_end = is_min_treemin_endmin_start = true;/未选中边做标记/循环结束，找到n-1条边4、总结 本题主要利用vc+实现kruskal算法的动态演示，其中不断的使用mfc的绘图函数。对于图的存储，此处使用了邻接矩阵的结构。kruskal算法是一个经典的算法，通过此次课程设计，加深了对这一算法的理解和认识。二、计算器的实现1、分析与建模 计算器的实现是一个经典的应用，可以应用到许多知识上，如栈、二叉树等。本题中采用栈来实现。一个数字计算器要能够完成数学表达式的求值，而一个数学表达式包含数值和操作符两部分，这里就需要设置两个栈来保存数据和运算符，分别记为数据栈和操作符栈。然后通过栈的常用操作来实现表达式的求值运算。同时，要对一个数学表达式进行求值还需要规定一定的运算规则，主要是运算符的优先级，因为这决定了表达式的计算次序。2、设计的具体思路a、界面的设计依据题目要求，需要对表达式进行求值。首先需要设计一个“窗口“让用户输入表达式并输出计算结果，因此在界面上设计一个m_result编辑框实现此功能。此外，还需要设计0-9个数字按钮，还有+ - * / sqrt和abs几个运算符按钮以及左右括号外加一个=按钮。为了能够动态地显示计算过程，这里又设置了一个演示区用于演示表达式的计算过程，即数据和操作符入栈和出栈的过程。另外，在界面中增加两个按钮分别表示作者信息和使用说明及注意事项。最后，设置clear和(*,/,)(+,-)#，同一级别的运算符按照从左到右结合。此外，规定左括号优先级最高，可直接入栈，而遇到右括号则需要计算表达式的值直至遇到左括号。 数学表达式中的异常一般包括:除法运算时除数为0、左右括号不匹配、幂运算底数为零、开方运算底数为负;程序需要对这些异常进行处理，一般输出提示。d、表达式的运算 对于用户输入的表达式采用字符数组的结构来保存，因此在ccalucatordlg中增加变量express用于保存表达式，同时设计一个计数器count用于记录表达式计算的进程。然后利用double result(cahr*)进行计算。函数中的参数即为表达式的字符数组，计算后返回double值。同时在函数result中用调用了ccalculatordlg的两个成员函数is_digit()、priority()和cal()分别用来判断一个字符是否是数字或者小数点、定义运算符的优先级、计算定义操作符的运算，并分别返回bool、int、double。而在函数result中主要是从字符数组的起始端开始计算直至遇到结束标志，对于不同的字符元素有不同的计算原则，如下: 如果为数字直接压入数据栈; 如果为左括号则直接压入运算符栈 如果遇到右括号，则不断地对两个栈进行运算直到遇到第一个左括号，同时弹出遇到的第一个左括号:如果遇到的是双目运算符则连续从数据栈中取出两个数; 如果遇到的是单目操作符则只弹出一个数据 如果运算符栈顶是左括号则无论是数据还是操作符都对应压入数据栈和操作符栈 如果当前操作符的优先级较高则直接压入运算符栈 如果当前操作符的优先级低于运算符栈顶的操作符则取出栈顶运算符进行运算直至当前运算符的优先级高于栈顶运算符为止 遇到表达式数组中的结束标志#，进行剩余计算 另外，将用户输入的表达式字符数组初始化为全为#.同时，在进行计算的时候实时地利用mfc绘图函数将数据和操作符出入栈的情形绘制出来，已达到动态演示的目的。3、程序实现 在具体的程序实现中，主要进行的是表达式求值算法的实现。因为是利用栈来进行运算，所以需要定义两个栈分别为数据栈和操作符栈。/声明浮点型堆栈class stack_doublepublic:stack_double();bool is_empty()const;bool is_full()const;double get_top()const;void push(const double& x);void pop();private:double datamax_len1;int top;class stack_charpublic:stack_char();bool is_empty()const;bool is_full()const;char get_top()const;void push(const char& x);void pop();private:char datamax_len1;int top;下面需要实现的是优先级的定义和result函数的实现:/定义各运算符的优先级int ccalculatordlg:cal_level(char op1, char op2)if(op1=+|op1=-)if(op2=*|op2=/|op2=a|op2=s|op2=)return -1;else if(op2=#|op2=()return 1;elsereturn 0;else if(op1=*|op1=/)if(op2=+|op2=-|op2=#|op2=()return 1;else if(op2=|op2=a|op2=s)return -1;elsereturn 0;else if(op1=|op1=a|op1=s)if(op2=+|op2=-|op2=*|op2=/|op2=#|op2=()return 1;elsereturn 0;else if(op1=#)return -1;/判断一个字符是否为数字bool ccalculatordlg:is_digit(char ch)if(ch=0&chupdatewindow ();/避免系统自动更新窗口cdc* pdc = pwnd-getdc ();/获得所需绘图设备环境/cbrush b(pdc-getbkcolor();/获取原有区域背景cpen* poldpen;cpen pnewpen(ps_solid,2,rgb(255,34,67);poldpen = pdc-selectobject (&pnewpen);crect rcclient;pwnd-getclientrect (rcclient);cpoint p1 = rcclient.topleft ();cpoint p2 = rcclient.bottomright ();/pdc-fillrect(&rcclient,&b);/清除原有图形int px_topleft = p1.x;int py_topleft = p1.y ;int px_bottomright = p2.x ;int py_bottomright = p2.y ;cbrush b(pdc-getbkcolor();/获取原有区域背景pdc-fillrect(&rcclient,&b);/清除原有图形/绘制数据栈int num_x = px_topleft+130;int num_y = py_bottomright-75; pdc-moveto (px_topleft+100,py_bottomright-75);pdc-lineto (px_topleft+200,py_bottomright-75);pdc-moveto (px_topleft+200,py_bottomright-75);pdc-lineto (px_topleft+200,py_topleft+100);pdc-moveto (px_topleft+100,py_bottomright-75); pdc-lineto (px_topleft+100,py_topleft+100);pdc-textout (px_topleft+125,py_bottomright-60,数据栈);/绘制运算符栈int op_x = px_topleft+330;int op_y = py_bottomright-75; pdc-moveto (px_topleft+300,py_bottomright-75);pdc-lineto (px_topleft+400,py_bottomright-75);pdc-moveto (px_topleft+400,py_bottomright-75);pdc-lineto (px_topleft+400,py_topleft+100);pdc-moveto (px_topleft+300,py_bottomright-75); pdc-lineto (px_topleft+300,py_topleft+100);pdc-textout (px_topleft+315,py_bottomright-60,运算符栈); stack_double num; stack_char oper; num.push (0); pdc-textout (num_x,num_y-25*num_count,0); num_count+; sleep(2000); oper.push (#); pdc-textout (op_x,op_y-25*op_count,#); op_count+; sleep(2000); int i = 0; while(unsolvedi!=#) /如果为数字直接压入数据栈 if(is_digit(unsolvedi) cstring tm; tm.empty(); int n = 0; int temp = i; while(is_digit(unsolvedi) n+; i+; for(int xx = 0; xx textout (num_x,num_y-25*num_count,s); num_count+; cstring tt; tt.format(%0.3f,num.get_top(); tt += 入栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); /i+; continue; /如果为左括号则直接压入运算符栈 else if(unsolvedi=() oper.push(); pdc-textout (op_x,op_y-25*op_count,(); op_count+; pdc-textout(px_topleft+450,py_topleft+50,( 入栈 ); sleep(2000); i+; continue; /如果遇到右括号，则不断地对两个栈进行运算直到遇到第一个左括号，同时弹出遇到的第一个左括号 else if(unsolvedi=) while(oper.get_top()!=() char op = oper.get_top(); /如果遇到的是双目运算符则连续从数据栈中取出两个数 if(op!=s&op!=a) double num1 = num.get_top(); num.pop(); cstring tt; num_count-; pdc-textout (num_x,num_y-25*num_count, ); tt.empty(); tt.format(%0.3f,num1); tt += 出栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); double num2 = num.get_top(); num.pop(); num_count-; pdc-textout (num_x,num_y-25*num_count, ); tt.empty(); tt.format(%0.3f,num2); tt += 出栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); num.push(cal(num2,op,num1); cstring s; s.format (%0.3f,num.get_top (); pdc-textout (num_x,num_y-25*num_count,s); tt.empty(); tt.format(%0.3f,num.get_top(); tt += 入栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); num_count+; sleep(2000); /如果遇到的是单目操作符则只弹出一个数据 else if(op=s|op=a) double num1 = num.get_top(); num.pop(); cstring tt; num_count-; pdc-textout (num_x,num_y-25*num_count, ); tt.empty(); tt.format(%0.3f,num1); tt += 出栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); num.push(cal(0,op,num1); cstring s; s.format (%0.3f,num.get_top (); pdc-textout (num_x,num_y-25*num_count,s); num_count+; tt.empty(); tt.format(%0.3f,num.get_top(); tt += 入栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); oper.pop(); op_count-; pdc-textout (op_x,op_y-25*op_count, ); cstring tt; tt.empty(); tt += op; tt += 出栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); if(oper.get_top()=#) messagebox(括号不匹配!); oper.pop(); op_count-; pdc-textout (op_x,op_y-25*op_count, ); pdc-textout(px_topleft+450,py_topleft+50,( 出栈 ); sleep(2000); i+; continue; /如果运算符栈顶是左括号则无论是数据还是操作符都对应压入数据栈和操作符栈 else if(oper.get_top()=() if(is_digit(unsolvedi) cstring tm; tm.empty(); int n = 0; int temp = i; while(is_digit(unsolvedi) n+; i+; for(int xx = 0; xx textout (num_x,num_y-25*num_count,s); num_count+; cstring tt; tt.empty(); tt.format(%0.3f,num.get_top(); tt += 入栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); /i+; continue; else oper.push(unsolvedi); pdc-textout (op_x,op_y-25*op_count,oper.get_top(); op_count+; cstring tt; tt.empty(); tt += oper.get_top(); tt += 入栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); i+; continue; /如果当前操作符的优先级较高则直接压入运算符栈 else if(cal_level(unsolvedi,oper.get_top()0) oper.push(unsolvedi); pdc-textout (op_x,op_y-25*op_count,oper.get_top(); op_count+; cstring tt; tt.empty(); tt += oper.get_top(); tt += 入栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(2000); i+; continue; /如果当前操作符的优先级低于运算符栈顶的操作符则取出栈顶运算符进行运算 /直至当前运算符的优先级高于栈顶运算符为止 else if(!(cal_level(unsolvedi,oper.get_top()0) while(!(cal_level(unsolvedi,oper.get_top()0) char op = oper.get_top(); if(op!=s&op!=a) double num1 = num.get_top(); num.pop(); num_count-; pdc-textout (num_x,num_y-25*num_count, ); cstring tt; tt.empty(); tt.format(%0.3f,num1); tt += 出栈 ; pdc-textout(px_topleft+450,py_topleft+50,tt); sleep(20