课程设计实验报告二叉树旋转.docx
- 文档编号:13625665
- 上传时间:2023-06-15
- 格式:DOCX
- 页数:106
- 大小:588.76KB
课程设计实验报告二叉树旋转.docx
《课程设计实验报告二叉树旋转.docx》由会员分享,可在线阅读,更多相关《课程设计实验报告二叉树旋转.docx(106页珍藏版)》请在冰点文库上搜索。
课程设计实验报告二叉树旋转
数据结构课程设计报告
计算机科学与技术
姓名:
傅海平
专业:
计算机科学与技术
班级:
0711班
指导老师:
祝建华
2009年9月9日
1.摘要
本程序实现了图论中比较经典的算法,如Dijkstra,Floyd,Prim算法,完成了景点的图形化显示,是一个易于操作的图形景点显示程序。
关键字:
图算法,MFC,图形界面,旅游助手
2.前言
3.正文
3.1课程设计意义
1.了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
4.初步训练软件设计开发的一般性方法和工作流程,培养和提高自己的动手能力。
3.2课程设计选题及实现环境
3.2.1课程设计选题
某市有若干个(≥10)旅游景点,用一个无向网表示构成这个景点网。
其中,
1.每个顶点代表一个景点,数据项如下:
(1)景点名称
(2)景点介绍
(3)景点办公电话
(4)其它,如景点等级、坐标位置等
2.每条边代表两个景点间可直达,权值代表距离,也可考虑加些坐标信息表示边的走向,以便图形显示时使用。
系统实现功能:
1.输入各个景点信息和边形成一个无向连通网(含增删改的功能)。
2.求一个景点到另外景点的最短距离。
3.求每对景点间的最短距离。
4.从某景点出发,游玩所有景点后回到起点,设计一条最短路径。
5.其它。
要求:
1.用文件保存无向网
2.图形方式显示无向网
3.2.2实现环境
此次数据结构课程设计所采用的编程环境为MicrosoftVisualStudio2008TeamSuit版本,编程语言为VC++,并采用微软的MFC类库进行界面的编写,整个课程设计的过程中,图论部分的核心算法使用纯粹的C++代码编写,中间很少用到STL(C++标准模版库)作为算法实现的工具,所有组建均从底层编码完善的,因此很能体现此次数据结构课程设计的意义。
3.3需求分析
3.3.1总体功能描述
本系统实现的主要功能:
1.输入各个景点信息和边形成一个无向连通图(含增删改的功能)。
2.深度优先搜索遍历各个景点。
3.广度优先搜索遍历各个景点
4.查看和修改单个景点信息。
5.求一个景点到另外景点的最短距离。
6.求某两个景点间所有路径,据此可以依照某一条件为所有路径排序。
7.求每对景点间的最短距离。
8.从某景点出发,游玩所有景点后回到起点,设计一条最短路径。
本系统实现的附属功能:
1.图形化输入各个景点和各条路线的信息。
2.图形化显示所有景点及路线信息。
3.状态栏动态显示鼠标位置,鼠标本身也可以感知各个景点位置,即:
如果在浏览模式下当鼠标移动到某一景点上的时候其形状会发生变化。
4.查询景点信息时,可以生成各个景点的图片预览。
5.可以鼠标拖动地图上的各个景点,从而改变每个景点的位置。
6.可以鼠标删除某个景点,此时与该景点相关联的边均自动删除。
7.鼠标删除某条路线,此时只需鼠标连续点击两个景点,则与此相关联的边将删除。
3.3.2数据结构定义
1.景点信息结构定义
typedefstruct_NODE_TYPE//描述景点的节点信息
{
CStringm_strName;//景点名称;
CStringm_strID;//景点ID;
CStringm_strManager;//景点负责人;
CStringm_strTelPhone;//景点电话;
UINTm_nRank;//景点等级;
UINTm_nPrice;//景点票价;
CStringm_strProfile;//景点简介;
CStringm_strFileName;//原图片名称;
CPointm_Point;//景点坐标;
boolm_bDrawColor;
booloperator==(const_NODE_TYPE&tmp)//重载==运算符;
{
returnm_strID==tmp.m_strID;
}
booloperator!
=(const_NODE_TYPE&tmp)
{
returnm_strID!
=tmp.m_strID;//重载!
=操作符;
}
_NODE_TYPE()//默认的构造函数
{
m_strName=_T("Null");
m_strID=_T("Null");
m_strProfile=_T("Null");
m_strFileName=_T("Null");
m_Point=0;
m_nPrice=0;
m_nRank=0;
m_strManager=_T("Null");
m_strTelPhone=_T("Null");
m_bDrawColor=false;
}
_NODE_TYPE(const_NODE_TYPE&tmp)//带参数的构造函数
{
m_strName=tmp.m_strName;
m_strID=tmp.m_strID;
m_strProfile=tmp.m_strProfile;
m_strFileName=tmp.m_strFileName;
m_Point=tmp.m_Point;
m_nPrice=tmp.m_nPrice;
m_strManager=tmp.m_strManager;
m_nRank=tmp.m_nRank;
m_strTelPhone=tmp.m_strTelPhone;
m_bDrawColor=tmp.m_bDrawColor;
}
_NODE_TYPE&operator=(const_NODE_TYPE&tmp)//拷贝构造函数
{
m_strName=tmp.m_strName;
m_strID=tmp.m_strID;
m_strProfile=tmp.m_strProfile;
m_strFileName=tmp.m_strFileName;
m_Point=tmp.m_Point;
m_nPrice=tmp.m_nPrice;
m_strManager=tmp.m_strManager;
m_nRank=tmp.m_nRank;
m_strTelPhone=tmp.m_strTelPhone;
m_bDrawColor=tmp.m_bDrawColor;
return*this;
}
}NODETYPE,*pNODETYPE;
2.路线信息结构的定义
typedefstruct_EDGE_TYPE//道路节点类型
{
intm_firstNodePos;//记录该边起始景点在NoteTable里面的位置,在保存图的时候必须用到;
CStringm_strRouteName;
UINTm_nLength;
_EDGE_TYPE()//默认构造函数
{
m_firstNodePos=0;
m_strRouteName=_T("Null");
m_nLength=0;
}
_EDGE_TYPE(const_EDGE_TYPE&tmp)//带参数的构造函数
{
m_firstNodePos=tmp.m_firstNodePos;
m_strRouteName=tmp.m_strRouteName;
m_nLength=tmp.m_nLength;
}
_EDGE_TYPE&operator=(const_EDGE_TYPE&tmp)//拷贝构造函数
{
m_firstNodePos=tmp.m_firstNodePos;
m_strRouteName=tmp.m_strRouteName;
m_nLength=tmp.m_nLength;
return*this;
}
_EDGE_TYPE&operator+(const_EDGE_TYPE&tmp)//重载+运算符
{
m_nLength=m_nLength+tmp.m_nLength;
return*this;
}
booloperator<(const_EDGE_TYPE&tmp)//重载<运算符
{returnthis->m_nLength booloperator<(unsignedinttmpValue)//重载<运算符 {returnthis->m_nLength }EDGETYPE,*pEDGETYPE; 注意: 以上数据结构的定义只是景点和路线的基本信息定义,由于实验中采用了类模版编程技术,在实现图算法的时候景点和路线的类型是不确定的,因此在算法实现时所采用的数据结构定义如下: 3.图算法中顶点数据结构的定义 template structCVertex { public: TdataNode;//顶点数据结构类型; CEdge CVertex() { this->pAdjList=NULL; } CVertex(Tdata) { this->dataNode=data; this->pAdjList=NULL; } booloperator! =(constCVertex { returnthis->dataNode! =V.dataNode; } booloperator==(constCVertex { returnthis->dataNode==V.dataNode; } }; 4.图算法中边的数据结构定义 template structCEdge { public: CEdge(){} CEdge(intnum,Eweight): destVertex(num),costOfEdge(weight) { this->pNextEdge=NULL } booloperator! =(CEdge { return(destVertex! =R.destVertex)? true: false; } public: intdestVertex;//记录另外一个顶点的位置; EcostOfEdge;//边的权值 CEdge }; 5.图(CGraphLink)类数据结构定义(图存储结构采用了邻接表的存储结构) template classCGraphLink { public: CGraphLink(void); CGraphLink(intnum); ~CGraphLink(void); boolisGraphEmpty()const { if(numVertices==0)returntrue; elsereturnfalse; } boolisGraphFull()const { if(numVertices==maxNumOfVertex|| numEdges==maxNumOfVertex*(maxNumOfVertex-1)/2)returntrue; elsereturnfalse; } intGetNumberOfVertices(void) { returnnumVertices; } intGetNumberOfEdges(void) { returnnumEdges; } TGetValue(inti); EGetWeight(intV1,intV2); intGetFirstNeighbor(intV); intGetNextNeighbor(intV,intW); boolInsertVertex(constT&vertex); boolInertEdge(intV1,intV2,EcostOfEdge); boolRemoveVertex(intV); boolRemoveEdge(intV1,intV2); voidDepthFirstSearch(constCGraphLink voidBreadthFirstSearch(constCGraphLink intGetVertexPos(constTvertex); voidFindArticulationPoints(CGraphLink voidShortestPathByDijkstra(CGraphLink voidShortestPathByBellman_Ford(CGraphLink voidShortestPathByFloyd(CGraphLink voidMinSpanTreeByPrim(CGraphLink voidShowShortestPath(CGraphLink vector boolisCircle(intpop,vector intnumEdges;//当前的边数目; intnumVertices;//当前顶点数; intmaxNumOfVertex;//最大顶点数; CVertex }; 3.4功能模块分析 系统主要分为以下几个模块: 1、景点信息模块: 包括添加景点,删除景点,移动景点位置,查看景点信息,搜索相关景点 2、路线模块: 包括添加路线,删除路线,查看路线信息等 3、搜索模块: 包括深度有限遍历,广度优先遍历,两点间所有路径搜索,两点间最短路径搜索,景区所有景点最短路径搜索。 4、保存模块: 包括保存图片信息,保存其他基本信息。 5、读入模块: 包括读入图片信息,读入其他信息。 3.5关键算法分析 3.5.1图的相关概念 1.邻接表存储结构 2.深度优先搜索DFS(DepthFirstSearch) 1.算法简介 正如算法名称那样,深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。 在深度优先搜索中,对于最新发现的顶点,如果它还有以此为起点而未探测到的边,就沿此边继续搜索下去。 当结点v的所有的边都己被探寻过后,搜索将回溯到发现结点v有那条边的始结点。 这一过程一直进行到已发现从源结点可达的所有结点为止。 如果还存在未被发现的结点,则选择其中一个作为源结点并重复以上过程,整个进程反复进行直到所有结点都被发现为止。 2.算法伪代码: 1.访问顶点v;VISITED[v]=1; 2.w=顶点v的第一个邻接点; 3.while(w存在) 3.1if(w未被访问)从顶点w出发递归执行该算法; 3.2w=顶点v的下一个邻接点; 3.C++代码: template voidCGraphLink : DepthFirstSearch(constCGraphLink { boolisVisited[DEFAULTMAXVERTEX]={0}; CEdge inttop=0; *nodeContainer=G.NodeTable[V].dataNode; nodeContainer++; isVisited[V]=true; p=G.NodeTable[V].pAdjList; while(top>0||p! =NULL) { while(p! =NULL) { if(isVisited[p->destVertex]! =0)p=p->pNextEdge; else { (*nodeContainer)=G.NodeTable[p->destVertex].dataNode; nodeContainer++; isVisited[p->destVertex]=true; myStack[++top]=p; p=G.NodeTable[p->destVertex].pAdjList; } } if(top>0) { p=myStack[top--]; p=p->pNextEdge; } } } 3.广度优先搜索 1.算法简介 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。 Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 已知图G=(V,E)和一个源点s,宽度优先搜索以一种系统的方式探寻G的边,从而“发现”s所能到达的所有顶点,并计算s到所有这些顶点的距离(最少边数),该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。 对从s可达的任意顶点v,宽度优先树中从s到v的路径对应于图G中从s到v的最短路径,即包含最小边数的路径。 该算法对有向图和无向图同样适用。 之所以称之为宽度优先算法,是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展,就是说,算法首先搜索和s距离为k的所有顶点,然后再去搜索和S距离为k+1的其他顶点。 为了保持搜索的轨迹,宽度优先搜索为每个顶点着色: 白色、灰色或黑色。 算法开始前所有顶点都是白色,随着搜索的进行,各顶点会逐渐变成灰色,然后成为黑色。 在搜索中第一次碰到一顶点时,我们说该顶点被发现,此时该顶点变为非白色顶点。 因此,灰色和黑色顶点都已被发现,但是,宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。 若(u,v)∈E且顶点u为黑色,那么顶点v要么是灰色,要么是黑色,就是说,所有和黑色顶点邻接的顶点都已被发现。 灰色顶点可以与一些白色顶点相邻接它们代表着已找到和未找到顶点之间的边界。 2.算法伪代码: 1.初始化队列Q; 2.访问顶点v;visited[v]=1;顶点v入队Q; 3.while(队列Q非空) 3.1v=队列Q的队头元素出队; 3.2w=顶点v的第一个邻接点; 3.3while(w存在) 3.3.1如果w未被访问,则 访问顶点w;visited[w]=1;顶点w入队列Q; 3.3.2w=顶点v的下一个邻接点; 1.C++代码: template voidCGraphLink : BreadthFirstSearch(constCGraphLink { boolisVisited[DEFAULTMAXVERTEX]={0}; intmyQueue[DEFAULTMAXVERTEX],nFront,nRear; CEdge nFront=nRear=0; *nodeContainer=G.NodeTable[V].dataNode; nodeContainer++; isVisited[V]=true; myQueue[++nRear]=V; while(nFront! =nRear) { V=myQueue[++nFront]; p=G.NodeTable[V].pAdjList; while(p! =NULL) { if(isVisited[p->destVertex]==0) { V=p->destVertex; (*nodeContainer)=G.NodeTable[p->destVertex].dataNode; nodeContainer++; isVisited[V]=true; myQueue[++nRear]=V; } p=p->pNextEdge; } } } 3.5.2Dijkstra算法 1.算法简介: Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。 主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 2.算法伪代码: 1.初始化数组dist、path和s; 2.while(s中的元素个数 2.1在dist[n]中求最小值,其下标为k(则vk为正在生成的终点); 2.2输出dist[j]和path[j]; 2.3修改数组dist和path; 2.4将顶点vk添加到数组s中; 3.C++代码: template voidCGraphLink : ShortestPathByDijkstra(CGraphLink
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课程设计实验报告 二叉树旋转 课程设计 实验 报告 二叉 旋转