——数据结构（C语言）课程设计题目：可视化弗洛伊德最短路径一．实习目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

二．问题描述设计、实现随机或手动建立一个有向图，可以使用弗洛伊德算法输出有向图中节点之间最短路径及权值，并把有向图和弗洛伊德算法得出的最短路径及最小权值可视化。

三．需求分析（1）可随机建立有向图，并在屏幕上使图可视化；（2）可手动建立有向图，添加节点、删除节点、移动节点、添加边、删除边、设置权值，并在屏幕上使图可视化；（3）对已建立的有向图实现弗洛伊德算法找出最短路径，并在屏幕上使最短路径及最小权值矩阵可视化；四．概要设计∙．系统中子程序及功能要求：数据对象V：一个集合，该集合中的所有元素具有相同的特性数据关系R：R={VR}VR={<x,y>|P(x,y)^(x,y属于V)}（1）OnButtonCreategraph()//随机建图按钮；（2）OnButtonHuman()//手动建图按钮；（3）OnButtonAddvertex()//添加节点按钮；（4）OnButtonDeletevertex()//删除节点按钮；（5）OnButtonMovevertex()//移动节点按钮；（6）OnButtonAddedge()//添加边按钮；（7）OnButtonDeleteedge()//删除边按钮；（8）OnButtonSetweight()//设置权值按钮；（9）OnButtonFloyd()//弗洛伊德算法按钮；（10）DrawDGRandom(TCenterPoint, pDC)//随机建图；（11）DrawDiGraph(CDC *pDC)//图可视化；（12）DrawVexs(CDC *pDC)//节点可视化；（13）DrawEdges(CDC *pDC)//边可视化；（14）InitHand()//存储节点；（15）CreateDGHand(CPoint centerpoint)//手动建图；（16）AddVertsHand()//添加节点；（17）DeleteVex(CPoint vPoint)//删除节点；（18）AddEdgesHand()//添加边；（19）DeleteEdge(CGraphVertex* pBeginVex, CGraphVertex* pEndVex)//删除边；（20）SetEdgeWeightHand ()//设置权值；（21）Floyd()//弗洛伊德算法；（22）DrawFloyd(CDC *pDC)//弗洛伊德可视化；∙各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序 1、2、3、4、5、6、7、8、9子程序1可调用子程序10子程序2、3可调用子程序14、15子程序3可调用子程序16子程序4可调用子程序17子程序6可调用子程序18子程序7可调用子程序19子程序8可调用子程序20子程序9可调用子程序21子程序10可调用子程序11子程序16可调用子程序12子程序17可调用子程序12、19子程序18、19、20可调用子程序13子程序21可调用子程序22五．测试分析按照附录中的测试数据，得出如下测试、分析结果：1.建图功能：（1）随机建图：随机去顶节点的个数与位置及节点之间边的连接、方向与权值大小，并在屏幕上输出图结构；测试结果：可随机输出一有向图。

（2）手动建图：a、添加节点：手动添加节点并放在任意位置；结果：可在任意位置添加节点。

b、删除节点：手动删除一节点；结果：只能按顺序删除，无法任意删除，有待改进。

c、移动节点：可将某一节点移动到其他位置；结果：尚未实现。

d、添加边：在任意两个不同节点之间添加任意方向的边；结果：可以实现添加任意方向的边。

e、删除边：删除任意一条已存在的边；结果：可以删除任意一条存在的边。

d、设置权值：给任意一条已存在的边赋予权值；结果：可以赋予权值；（3）弗洛伊德算法：对已确定的有向图通过Floyd算法找到任意两点间的最短路径并在屏幕上输出最短路径及权值的矩阵；结果：可正确输出路径及权值。

六．使用说明1．运行程序，首先出现主界面。

主界面首先包括两个个选项：选项一：随机建图，点击按钮可在屏幕上输出一随机有向图；选项二：手动建图，可以手动建立有向图。

2．手动建图，出现6个新的选项：选项一：添加节点，在任意位置点击添加一节点；选项二：删除节点，可删除一个节点；选项三：移动节点, 可以移动一节点到其他位置（待改进）；选项四: 添加边，点击一个节点后再点击另外一个即可添加该方向的边；选项五：删除边，点击按钮后输入想删除的边的两个节点即可删除该边；选项六：设置权值，点击按钮后输入想添加的边的两个节点及权值即可给该边赋予权值。

3．弗洛伊德算法：对屏幕上已显示的有向图运行Floyd算法，输出最短路径及权值。

七．附录：测试数据九．附C 语言实现源码∙ 系统用到的抽象数据类型定义：∙ class CDiGraph∙ {∙ public:∙ CDiGraph();∙virtual ~CDiGraph();∙public:∙基本数据：∙void DrawFloyd(CDC* pDC);∙void Floyd();∙void Transform();∙void InitHand();∙//有向图的当前顶点数目∙int vexnum;∙//有向图的当前边数目∙int arcnum;∙//有向图深度优先已经遍历顶点数目∙int m_nDFSnum;∙//有向图存储链表∙CTypedPtrList <CObList,CGraphVertex*> m_DigraphList;∙CString Arrayvex[MAX];∙int Arrayweight[MAX][MAX];∙CString Path[MAX][MAX];基本操作：void CreateDGRandom(CPoint vCenterPoint);//自动创建有向图void CreateDGHand(CPoint vCenterPoint);//手动创建有向图///////////////////////////////////////////////////////// 有向图基本函数 /////////////////////////////////////////////////////////int LocateInList(CString vName);//判断顶点vPoint是否在有向图存储链表CGraphVertex* IsPointInList(CPoint vPoint);//判断顶点名vName是否在有向图存储链表CGraphVertex* IsNameInList(CString vName);//判断边(pBeginVex,pEndVex)是否在有向图中BOOL IsEdgeExist(CGraphVertex* pBeginVex,CGraphVertex* pEndVex); //判断名为vName的顶点是否在有向图中存储链表中CGraphVertex* IsVexNameInList(CString vName);//查找名为vName的顶点在有向图中存储链表中的地址CGraphVertex* FindVexNameInList(CString vName);//设置边(vBeginVex,vEndVex)的权值void SetEdgeWeight(CString vBeginVex,CString vEndVex,int vWeight);void DeleteVex(CPoint vPoint);//删除显示位置为vPoint的顶点void DeleteEdge(CGraphVertex* pBeginVex,CGraphVertex* pEndVex); //删除边(pBeginVex,pEndVex)void InsertEdge(CGraphVertex* pBeginVex,CGraphVertex* pEndVex,int weight);//插入顶点(pBeginVex,pEndVex)之间的边///////////////////////////////////////////////////////// 有向图显示函数 // /////////////////////////////////////////////////////////有向图可视化显示void DrawDiGraph(CDC *pDC);//显示有向图边void DrawEdges(CDC *pDC);//显示有向图顶点void DrawVexs(CDC *pDC);∙};画图类：∙class CDiGraphDraw : public CFormView∙{∙protected:∙CDiGraphDraw(); // protected constructor used by dynamic creation∙DECLARE_DYNCREATE(CDiGraphDraw)∙∙// Form Data∙public:∙//{{AFX_DATA(CDiGraphDraw)∙enum { IDD = IDD_DIGRHDRAW_FORMVIEW };∙// NOTE: the ClassWizard will add data members here∙//}}AFX_DATA∙∙// Attributes∙public:∙∙// Operations∙public:∙void DrawFloyd(CDC *pDC);∙//画出弗洛伊德算法的结果∙void Floyd();∙void SetEdgeWeightHand();∙//手动设置权值∙void DelEdgesHand();∙//手动删除边∙void AddEdgesHand();∙//手动添边∙void MovVertsHand();∙BOOL m_Capture;∙void DelVertsHand();∙//手动删除顶点∙void AddVertsHand();∙//手动添加顶点∙void CreateDGHand();∙//手动创建有向图∙void CreateDGRandom();∙//自动创建有向图∙void ComputeFloyd();∙CGraphVertex* m_pEndNode;∙CGraphVertex* m_pBeginNode;∙CPoint m_StartPoint;∙int m_FunType;∙void DrawDGHand(CDC *pDC);∙void DrawDGRandom(CPoint vCenterPoint, CDC *pDC);∙static DWORD WINAPI DiGraphproc(LPVOID lpParameter); ∙CDataStructVisualDoc* GetDocument();∙CDataStructVisualDoc* pDoc;∙bool m_StartFlag;∙HANDLE hEventDiGraph;∙HANDLE hThreadDiGraph;∙int m_flag;∙有向图边的类：∙class CGraphEdge : public CObject∙{∙public:∙CGraphEdge();∙virtual ~CGraphEdge();∙public:∙bool EdgeDraw(CGraphVertex* pBeginVex,CDC *pDC);∙int info;∙int m_weight;//边的权值∙COLORREF m_color;//图边颜色∙CGraphVertex* m_pAdjVertex;∙CGraphEdge* m_pNextEdge;∙}∙有向图顶点的类：∙class CGraphVertex : public CObject∙{∙public:∙CGraphVertex();∙virtual ~CGraphVertex();∙public:∙bool VexDraw(CDC *pDC);∙CPoint m_point;∙COLORREF m_color; //图顶点颜色∙CGraphEdge* m_pFirstEdge;∙char m_strname;∙BOOL m_bvisit;∙int m_nvisit;∙int m_pos;∙∙};∙弗洛伊德算法及其画图的代码：∙void CDiGraph::Floyd()∙{∙Transform();∙int A[MAX][MAX];∙int i,j,k;∙for(i=0;i<vexnum;i++)∙{∙for(j=0;j<vexnum;j++)∙{∙A[i][j]=Arrayweight[i][j];∙if(A[i][j]!=0&&A[i][j]<INT_MAX)∙{∙Path[i][j]=Arrayvex[i]+Arrayvex[j];∙}∙}∙}∙for(k=0;k<vexnum;k++)∙{∙for(i=0;i<vexnum;i++)∙{∙for(j=0;j<vexnum;j++)∙{∙if(A[i][j]>(A[i][k]+A[k][j]))∙{∙if(A[i][k]<INT_MAX&&A[k][j]<INT_MAX)∙{∙A[i][j]=A[i][k]+A[k][j];∙if(Path[i][k]!='0'&&Path[k][j]!='0') ∙{∙ Path[i][j]=Path[i][k]+Arrayvex[j]; ∙}∙∙}∙}∙}∙}∙}∙for(i=0;i<vexnum;i++)∙{∙for(j=0;j<vexnum;j++)∙{∙Arrayweight[i][j]=A[i][j];∙}∙}∙}∙∙void CDiGraph::DrawFloyd(CDC *pDC)∙{∙CString str;∙CPoint m_point;∙m_point.y=50;∙m_point.x=700;∙pDC->MoveTo(m_point.x,m_point.y);∙pDC->LineTo(m_point.x-10,m_point.y+10);∙pDC->MoveTo(m_point.x-10,m_point.y+10);∙pDC->LineTo(m_point.x-10,m_point.y + vexnum*20 - 10); ∙pDC->MoveTo(m_point.x-10,m_point.y + vexnum*20 - 10); ∙pDC->LineTo(m_point.x,m_point.y + vexnum*20 );∙for(int i=0;i<vexnum;i++)∙{∙m_point.x=700;∙for(int j=0;j<vexnum;j++)∙{∙if(Arrayweight[i][j]<INT_MAX)∙{∙str.Format("%d",Arrayweight[i][j]);∙pDC->TextOut(m_point.x,m_point.y,str);∙m_point.x+=20;∙}∙else∙{∙str.Format("%d",Arrayweight[0][0]);∙pDC->TextOut(m_point.x,m_point.y,str);∙m_point.x+=20;∙}∙}∙m_point.y+=20;∙}∙pDC->MoveTo(m_point.x-10,m_point.y);∙pDC->LineTo(m_point.x,m_point.y-10);∙pDC->MoveTo(m_point.x,m_point.y-10);∙pDC->LineTo(m_point.x,m_point.y-vexnum*20+10);∙pDC->MoveTo(m_point.x,m_point.y-vexnum*20+10);∙pDC->LineTo(m_point.x-10,m_point.y-vexnum*20);∙∙m_point.y=250;∙m_point.x=700;∙pDC->MoveTo(m_point.x,m_point.y);∙pDC->LineTo(m_point.x-10,m_point.y+10);∙pDC->MoveTo(m_point.x-10,m_point.y+10);∙pDC->LineTo(m_point.x-10,m_point.y + vexnum*20 - 10);∙pDC->MoveTo(m_point.x-10,m_point.y + vexnum*20 - 10);∙pDC->LineTo(m_point.x,m_point.y + vexnum*20 );∙for(i=0;i<vexnum;i++)∙{∙m_point.x=700;∙for(int j=0;j<vexnum;j++)∙{∙str.Format("%s",Path[i][j]);∙pDC->TextOut(m_point.x,m_point.y,str);∙m_point.x+=45;∙}∙m_point.y+=20;∙}∙pDC->MoveTo(m_point.x-10,m_point.y);∙pDC->LineTo(m_point.x,m_point.y-10);∙pDC->MoveTo(m_point.x,m_point.y-10);∙pDC->LineTo(m_point.x,m_point.y-vexnum*20+10);∙pDC->MoveTo(m_point.x,m_point.y-vexnum*20+10);∙pDC->LineTo(m_point.x-10,m_point.y-vexnum*20);∙}∙界面显示：∙class CLeftPane : public CFormView∙{∙protected:∙CLeftPane(); // protected constructor used by dynamic creation∙DECLARE_DYNCREATE(CLeftPane)∙∙// Form Data∙public:∙//{{AFX_DATA(CLeftPane)∙enum { IDD = IDD_LEFTPANE_FORMVIEW };∙CTreeCtrl m_LeftTree;∙//}}AFX_DATA∙∙// Attributes∙public:∙∙// Operations∙public:∙CRightFrame* m_pRightSwitchFrame;∙∙// Overrides∙// ClassWizard generated virtual function overrides∙//{{AFX_VIRTUAL(CLeftPane)∙public:∙virtual void OnInitialUpdate();∙protected:∙virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support∙virtual void CalcWindowRect(LPRECT lpClientRect, UINT nAdjustType = adjustBorder);∙//}}AFX_VIRTUAL∙∙// Implementation∙protected:∙virtual ~CLeftPane();∙#ifdef _DEBUG∙virtual void AssertValid() const;∙virtual void Dump(CDumpContext& dc) const;∙#endif∙∙// Generated message map functions∙//{{AFX_MSG(CLeftPane)∙afx_msg void OnSize(UINT nType, int cx, int cy);∙afx_msg void OnCancelMode();∙afx_msg void OnSelchangedLeftpaneTree(NMHDR* pNMHDR, LRESULT* pResult);∙//}}AFX_MSG∙DECLARE_MESSAGE_MAP()∙private:∙void InitTree();∙HTREEITEM m_Root;∙CImageList m_TreeImageList;∙CRect m_sRect;∙};树的显示：∙void CLeftPane::InitTree()∙{∙LPSTR pszText;∙m_TreeImageList.Create(16,16,TRUE,6,1);∙HICON hIcon;∙hIcon=::LoadIcon(AfxGetResourceHandle(),MAKEINTRESOURCE(IDI_ICON1 ));∙m_TreeImageList.Add(hIcon);∙hIcon=::LoadIcon(AfxGetResourceHandle(),MAKEINTRESOURCE(IDI_ICON2 ));∙m_TreeImageList.Add(hIcon);∙hIcon=::LoadIcon(AfxGetResourceHandle(),MAKEINTRESOURCE(IDI_ICON3 ));∙m_TreeImageList.Add(hIcon);∙hIcon=::LoadIcon(AfxGetResourceHandle(),MAKEINTRESOURCE(IDI_ICON4 ));∙m_TreeImageList.Add(hIcon);∙hIcon=::LoadIcon(AfxGetResourceHandle(),MAKEINTRESOURCE(IDI_ICON5 ));∙m_TreeImageList.Add(hIcon);∙m_LeftTree.SetImageList(&m_TreeImageList,TVSIL_NORMAL);∙//////////////////////在树视图控件添加信息/////////////////////////////////////∙m_LeftTree.DeleteAllItems();//清空当前书控件所有节点∙m_Root=m_LeftTree.InsertItem("动态切换视图"); //插入根节点∙TV_INSERTSTRUCT TCItem; //设屏蔽∙TCItem.item.mask=TVIF_TEXT|TVIF_PARAM|TVIF_IMAGE|TVIF_SELECTEDIMA GE;∙TCItem.hInsertAfter=TVI_LAST;//在最后项之后∙CString strTreeNodeName="测试一";∙pszText=strTreeNodeName.LockBuffer();∙TCItem.hParent=m_Root;∙TCItem.item.pszText=pszText;∙TCItem.item.iImage=1;∙TCItem.item.iSelectedImage=2;∙HTREEITEM hCurrent=m_LeftTree.InsertItem(&TCItem);∙m_LeftTree.SetItemData(hCurrent,1);∙strTreeNodeName="测试二";∙pszText=strTreeNodeName.LockBuffer();∙TCItem.hParent=m_Root;∙TCItem.item.pszText=pszText;∙TCItem.item.iImage=1;∙TCItem.item.iSelectedImage=2;∙hCurrent=m_LeftTree.InsertItem(&TCItem);∙m_LeftTree.SetItemData(hCurrent,2);∙m_LeftTree.Expand(m_Root, TVE_EXPAND); //展开根节点∙strTreeNodeName="单链表";∙pszText=strTreeNodeName.LockBuffer();∙TCItem.hParent=m_Root;∙TCItem.item.pszText=pszText;∙TCItem.item.iImage=1;∙TCItem.item.iSelectedImage=2;∙hCurrent=m_LeftTree.InsertItem(&TCItem);∙m_LeftTree.SetItemData(hCurrent,3);∙m_LeftTree.Expand(m_Root, TVE_EXPAND); //展开根结点∙∙strTreeNodeName="有向图";∙pszText=strTreeNodeName.LockBuffer();∙TCItem.hParent=m_Root;∙TCItem.item.pszText=pszText;∙TCItem.item.iImage=1;∙TCItem.item.iSelectedImage=2;∙hCurrent=m_LeftTree.InsertItem(&TCItem);∙m_LeftTree.SetItemData(hCurrent,31);∙strTreeNodeName="创建有向图";∙pszText=strTreeNodeName.LockBuffer();∙TCItem.hParent=hCurrent;∙TCItem.item.pszText=pszText;∙TCItem.item.iImage=3;∙TCItem.item.iSelectedImage=4;∙HTREEITEM hCurrent_CrtUndiGraph=m_LeftTree.InsertItem(&TCItem);∙m_LeftTree.SetItemData(hCurrent_CrtUndiGraph,4);∙m_LeftTree.Expand(m_Root, TVE_EXPAND); //展开根结点∙}界面切换功能：void CLeftPane::OnSelchangedLeftpaneTree(NMHDR* pNMHDR, LRESULT* pResult){NM_TREEVIEW* pNMTreeView = (NM_TREEVIEW*)pNMHDR;// TODO: Add your control notification handler code hereint nIndex=-1;UINT nView;nIndex=m_LeftTree.GetItemData(m_LeftTree.GetSelectedItem());switch(nIndex){case 1:nView=VIEW_SPLITTER1;//if (nView) m_pRightPaneFrame->SwitchToView(nView);break;case 2:nView=VIEW_SPLITTER2;//if (nView) m_pRightPaneFrame->SwitchToView(nView);break;case 3:nView=VIEW_SPLITTERLINKLIST;break;case 4:nView=VIEW_SPLITTER_CRTDIGRAPH;break;default:break;}m_pRightSwitchFrame->SwitchToView(nView);*pResult = 1;}十．小组成员分工情况表最开始的树及有向图是由每个人独立完成来熟悉操作和代码，在做有向图及弗洛伊德算法时，王朴和李元主要研究有向图的建立及可视化，包赫和李崇飞主要研究弗洛伊德算法程序，出现问题时由4个人一起讨论、试验来解决，最后程序由大家共同做出。