数据结构课程设计报告.doc
46页
计算机与信息学院数据结构课程设计实验报告专 业 班 级计算机07—4班学生姓名及学号课程教学班号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 [i][j] = graph.AdjMatrix [j][i] =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_num<=8&&v_num>0) Draw(v_num); else if(v_num<=0||v_num>8) MessageBox("请输入1到8之间的一个数!!!!"); else MessageBox("你还没有输入结点数!!"); m_Start.ResetContent(); m_End.ResetContent (); for(int k = 0; k < v_num; k++) { m_Start.AddString (VexNode[k]); m_End.AddString (VexNode[k]); }为了在演示区中绘制n个结点，在OnApply函数中调用函数Draw(v_num);在函数Draw(int n)中绘制n个节点，为了限制结点个数，在演示区中固定了8个点供演示。
这8个点的组成形式如下：将这8个点保存在Point数组point中，同时以这8个点为中心作8个矩形Rect rcDraw[8]保存图的结点的外接矩形，并根据m_vexnum的大小利用MFC绘图函数绘制m_vexnum内切圆作为图的结点增加边 ”按钮的主要功能是输入图的边信息并与图关联起来，为此在CsmileGraph1Dlg类中增加变量Edge edge[56]用于保存用户输入的边信息用户通过两个列表框选择一条边的两个端点并把其权值输入到下面的编辑框中，然后单击“增加边 ”按钮即可完成：在演示区中绘制一条边并显示其权值，修改图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.AdjMatrix[start][end]!=INF) MessageBox("改边已经存在"); else if(start==LB_ERR||end==LB_ERR) { MessageBox("结点不存在!!!"); } else if(start==end) MessageBox("起始端点不应为同一结点!!!"); else { //增加图的边 edge[edge_num].start = start; edge[edge_num].end = end; edge[edge_num].val = value; edge_num++;//边数//修改图的邻接矩阵 graph.AdjMatrix [start][end] = graph.AdjMatrix [end][start] = 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分别标记结点和边是否已被选中如果visited[i] = visited[j]或者is_min_tree[i,j]=true说明再选取边（i,j）即会构成环，应当舍弃，继续往下寻找，直至找出含有n的节点的n-1个最小生成树的n-1条边,这里需要进行n-1趟循环。
3、程序实现A、图的实现 本题采用邻接矩阵存储图，定义一个Graph和Edge结构体分别保存图的具体信息和边信息定义如下：struct EdgeNode { int start;//起点 int end;//终点 int val;//权值 }; struct Graph { int AdjMatrix[8][8];//邻接矩阵 char data[8];//节点值 int graph_vexnum;//节点数 };B、排序的实现void CSmileGraph1Dlg::partition(EdgeNode *edge, int s, int t, int &cutpoint){ EdgeNode tmp; tmp.start = edge[s].start ; tmp.end = edge[s].end; tmp.val = edge[s].val ; int i = s; int j = t; while(i
