中国石油大学数据结构课程设计.doc

《中国石油大学数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《中国石油大学数据结构课程设计.doc（22页珍藏版）》请在沃文网上搜索。

1、可视化弗洛伊德最短路径一实习目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二问题描述设计、实现随机或手动建立一个有向图，可以使用弗洛伊德算法输出有向图中节点之间最短路径及权值，并把有向图和弗洛伊德算法得出的最短路径及最小权值可视化。三需求分析 （1） 可随机建立有向图，并在屏幕上使图可视化； （2） 可手动建立有向图，添加节点、删除节点、移动节点、添加边、删除边、设置权值，并在屏幕上使图可视化； （3） 对已建立的有向图实现弗洛伊德算法找出最短路径，并在屏幕上

2、使最短路径及最小权值矩阵可视化；四概要设计 系统中子程序及功能要求： 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R=VR VR=|P(x,y)(x,y属于V) （1） OnButtonCreategraph()/随机建图按钮；（2） OnButtonHuman()/手动建图按钮；（3） OnButtonAddvertex()/添加节点按钮；（4） OnButtonDeletevertex()/删除节点按钮；（5） OnButtonMovevertex()/移动节点按钮；（6） OnButtonAddedge()/添加边按钮；（7） OnButtonDeleteedge

3、()/删除边按钮；（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） Del

4、eteVex(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子程序

5、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、 删除节点：手动删除一节点；结果：只

6、能按顺序删除，无法任意删除，有待改进。c、 移动节点：可将某一节点移动到其他位置；结果：尚未实现。d、 添加边：在任意两个不同节点之间添加任意方向的边；结果：可以实现添加任意方向的边。e、 删除边：删除任意一条已存在的边；结果：可以删除任意一条存在的边。 d、 设置权值：给任意一条已存在的边赋予权值； 结果：可以赋予权值；（3） 弗洛伊德算法：对已确定的有向图通过Floyd算法找到任意两点间的最短路径 并在屏幕上输出最短路径及权值的矩阵；结果：可正确输出路径及权值。 六使用说明 1运行程序，首先出现主界面。主界面首先包括两个个选项：选项一：随机建图，点击按钮可在屏幕上输出一随机有向图；选项二：

7、手动建图，可以手动建立有向图。 2手动建图，出现6个新的选项： 选项一：添加节点，在任意位置点击添加一节点； 选项二：删除节点，可删除一个节点； 选项三：移动节点, 可以移动一节点到其他位置（待改进）； 选项四: 添加边，点击一个节点后再点击另外一个即可添加该方向的边； 选项五：删除边，点击按钮后输入想删除的边的两个节点即可删除该边； 选项六：设置权值，点击按钮后输入想添加的边的两个节点及权值即可给该边赋予权值。 3弗洛伊德算法：对屏幕上已显示的有向图运行Floyd算法，输出最短路径及权值。 七附录：测试数据 九附C语言实现源码 系统用到的抽象数据类型定义： class CDiGraph pu

8、blic: CDiGraph(); virtual CDiGraph(); public: 基本数据： void DrawFloyd(CDC* pDC); void Floyd(); void Transform(); void InitHand(); /有向图的当前顶点数目 int vexnum; /有向图的当前边数目 int arcnum; /有向图深度优先已经遍历顶点数目 int m_nDFSnum; /有向图存储链表 CTypedPtrList m_DigraphList; CString ArrayvexMAX; int ArrayweightMAXMAX; CString Path

9、MAXMAX;基本操作：void CreateDGRandom(CPoint vCenterPoint); /自动创建有向图 void CreateDGHand(CPoint vCenterPoint); /手动创建有向图/ 有向图基本函数 / / int LocateInList(CString vName); /判断顶点vPoint是否在有向图存储链表 CGraphVertex* IsPointInList(CPoint vPoint); /判断顶点名vName是否在有向图存储链表 CGraphVertex* IsNameInList(CString vName); /判断边(pBegin

10、Vex,pEndVex)是否在有向图中 BOOL IsEdgeExist(CGraphVertex* pBeginVex,CGraphVertex* pEndVex); /判断名为vName的顶点是否在有向图中存储链表中CGraphVertex* IsVexNameInList(CString vName); /查找名为vName的顶点在有向图中存储链表中的地址CGraphVertex* FindVexNameInList(CString vName); /设置边(vBeginVex,vEndVex)的权值void SetEdgeWeight(CString vBeginVex,CString

11、 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 DrawDiGrap

12、h(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

13、_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 D

14、elVertsHand(); /手动删除顶点 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)

15、; 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 EdgeDr

16、aw(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

17、; /图顶点颜色 CGraphEdge* m_pFirstEdge; char m_strname; BOOL m_bvisit; int m_nvisit; int m_pos; ; 弗洛伊德算法及其画图的代码： void CDiGraph:Floyd() Transform(); int AMAXMAX; int i,j,k; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) Aij=Arrayweightij; if(Aij!=0&AijINT_MAX) Pathij=Arrayvexi+Arrayvexj; for(k=0;kvexnum;k+) for(

18、i=0;ivexnum;i+) for(j=0;j(Aik+Akj) if(AikINT_MAX&AkjINT_MAX) Aij=Aik+Akj; if(Pathik!=0&Pathkj!=0) Pathij=Pathik+Arrayvexj; for(i=0;ivexnum;i+) for(j=0;jMoveTo(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 + vexnu

19、m*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;ivexnum;i+) m_point.x=700; for(int j=0;jvexnum;j+) if(ArrayweightijTextOut(m_point.x,m_point.y,str); m_point.x+=20; else str.Format(%d,Arrayweight00); pDC-TextOut(m_point.x,m_po

20、int.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=25

21、0; 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;ivexnum;i+)

22、 m_point.x=700; for(int j=0;jTextOut(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-Lin

23、eTo(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 ; CTreeCtrlm_LeftTree; /AFX_DATA / Attribute

24、s 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(LP

25、RECT 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, i

26、nt 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.C

27、reate(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_TreeI

28、mageList.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.DeleteAll

29、Items();/清空当前书控件所有节点 m_Root=m_LeftTree.InsertItem(动态切换视图);/插入根节点 TV_INSERTSTRUCT TCItem; /设屏蔽 TCItem.item.mask=TVIF_TEXT|TVIF_PARAM|TVIF_IMAGE|TVIF_SELECTEDIMAGE; TCItem.hInsertAfter=TVI_LAST;/在最后项之后 CString strTreeNodeName=测试一; pszText=strTreeNodeName.LockBuffer(); TCItem.hParent=m_Root; TCItem.ite

30、m.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.it

31、em.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.iSelectedIm

32、age=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; hCurren

33、t=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)

34、; 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 n

35、View;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=

36、VIEW_SPLITTER_CRTDIGRAPH;break;default:break;m_pRightSwitchFrame-SwitchToView(nView);*pResult = 1;十小组成员分工情况表 最开始的树及有向图是由每个人独立完成来熟悉操作和代码，在做有向图及弗洛伊德算法时，王朴和李元主要研究有向图的建立及可视化，包赫和李崇飞主要研究弗洛伊德算法程序，出现问题时由4个人一起讨论、试验来解决，最后程序由大家共同做出。十一课程总结 通过两周8天的程序设计课程，对工程的建立及算法的运算与嵌套有了更深刻的理解和操作能力，对团队合作完成一个工程有了一定的了解，团队合作意识加深了很

37、多。 完成了有向图弗洛伊德算法找到最短路径及权值的课程设计，对数据结构有了进一步的接触及操作，将书上的算法搬到程序的过程中加强了编程能力。十二项目进度及成绩评定课题名称： 完成者： 1、设计进度及完成情况日 期内 容2014年1月6参看关于图的生成的相关资料，理解了图、有向图和无向图及其操作的概念和它的作用。系统认识了图的生成的构造算法和对它的各种操作算法。2014年1月9完成总体设计，划分了功能模块。根据图和构造算法的特点设计好了程序使用的结构体。2014年1月13骤个实现细分的功能模块。完成各个功能模块的编写和调试。2014年1月15将各功能模块集成并调试，发现数个错误。修改了多个错误，处理了内存溢出问题。完成全部程序并完成报告的编写。2、成绩评定：设计成绩： （教师填写）指导老师： （签字）2012 年 月 日忽略此处.