测绘软件设计与实现

实验一：二叉树的基本操作实现及其应用一、实验目的1．熟悉二叉树结点的结构和对二叉树的基本操作。2．掌握对二叉树每一种操作的具体实现。3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4.会用二叉树解决简单的实际问题。二、实验内容设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。1.初始化二叉树.2.按先序序列建立二叉树.3.判断二叉树是否为空.4.先序、中序、后续序列遍历二叉树.5.求二叉树的深度.6.求二叉树节点的个数.三、代码清单#includeiostreamusingnamespacestd;#includestdlib.htypedefstructBitNode//用结构体定义二叉树节点{chardata;structBitNode*lchild,*rchild;}*BitTree;classC_JDC_BinTree{public:C_JDC_BinTree(){};//构造函数~C_JDC_BinTree(){};//析构函数voidBinTreeInit(BitTree&BT);//初始化二叉树，即把树根指针置空intBinTreeCreat(BitTree&BT);//按先序次序建立一个二叉树voidBinTreeEmpty(BitTree&BT);//检查二叉树是否为空voidBinTraverse(BitTree&BT);//先序序列遍历二叉树voidBinTraversezh(BitTree&BT);//先序序列遍历二叉树voidBinTraverseho(BitTree&BT);//先序序列遍历二叉树intBinTreeDepth(BitTreeBT);//求二叉树的深度intBinTreeCount(BitTreeBT);//求二叉树中所有结点数};//···············公共函数实现部分····················voidC_JDC_BinTree::BinTreeInit(BitTree&BT)//初始化二叉树，即把树根指针置空{BT=(BitTree)malloc(sizeof(BitNode));BT-data=NULL;cout二叉树初始化成功!endl;}intC_JDC_BinTree::BinTreeCreat(BitTree&BT)//按先序次序建立一个二叉树{charch;cinch;if(ch=='#')BT=NULL;else{if(!(BT=(BitTree)malloc(sizeof(BitNode))))exit(0);BT-data=ch;BinTreeCreat(BT-lchild);BinTreeCreat(BT-rchild);}return0;}voidC_JDC_BinTree::BinTreeEmpty(BitTree&BT)//检查二叉树是否为空{if(BT-data==NULL)cout是空二叉树!endl;elsecout不是空二叉树!endl;}voidC_JDC_BinTree::BinTraverse(BitTree&BT)//先序序列遍历二叉树{if(BT!=NULL){coutBT-data;BinTraverse(BT-lchild);BinTraverse(BT-rchild);}}voidC_JDC_BinTree::BinTraversezh(BitTree&BT)//中序序列遍历二叉树{if(BT!=NULL){BinTraversezh(BT-lchild);coutBT-data;BinTraversezh(BT-rchild);}}voidC_JDC_BinTree::BinTraverseho(BitTree&BT)//后续序列遍历二叉树{if(BT!=NULL){BinTraverseho(BT-lchild);BinTraverseho(BT-rchild);coutBT-data;}}intC_JDC_BinTree::BinTreeDepth(BitTreeBT)//求二叉树的深度{intdepthval;if(BT){intdepthLeft=BinTreeDepth(BT-lchild);intdepthRight=BinTreeDepth(BT-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);}elsedepthval=0;returndepthval;}intC_JDC_BinTree::BinTreeCount(BitTreeBT)//求二叉树中所有结点数{intnode;if(BT){intlchild=BinTreeCount(BT-lchild);intrchild=BinTreeCount(BT-rchild);node=lchild+rchild+1;}elsenode=0;returnnode;}//·············主函数部分················intmain(){C_JDC_BinTreea;inti;BitTreeBT;cout\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~endl\t\t~-~二叉树的创建、遍历~-~endl\t\t1.初始化二叉树.2.按先序序列建立二叉树.endl\t\t3.判断二叉树是否为空.4.先序、中序、后续序列遍历二叉树.endl\t\t5.求二叉树的深度.6.求二叉树节点的个数.endl\t\t7.退出endl\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~endl;while(1){cout输出你所需的操作:;cini;if(i==1)a.BinTreeInit(BT);elseif(i==2){cout输入你要建立的二叉树:endl;a.BinTreeCreat(BT);}elseif(i==3)a.BinTreeEmpty(BT);elseif(i==4){cout先序序列遍历二叉树endl;a.BinTraverse(BT);coutendl;cout中序序列遍历二叉树endl;a.BinTraversezh(BT);coutendl;cout后续序列遍历二叉树endl;a.BinTraverseho(BT);coutendl;}elseif(i==5)cout二叉树的深度:a.BinTreeDepth(BT)endl;elseif(i==6)cout二叉树的节点数a.BinTreeCount(BT)endl;elsebreak;}return0;}四、测试截图五、总结二叉树是数据结构中最重要的结构之一，编程实现二叉树的构建及遍历是我们的重点内容。在编程过程中，如何建立二叉树困扰了好长时间，最终通过翻阅《C++数据结构与实现》，借助按先序建立二叉树的思想解决了这个问题，之后通过不断调试，完成二叉树的构建、遍历等。实验二：图的创建与遍历班级：测绘工程10-2班姓名：姜德才学号：07103077指导老师：王永波一、实验目的：1．掌握图的存储结构及其构造方法2．掌握图的两种遍历算法及其执行过程二、实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。三、代码清单//Test02_JDC.cpp:Definestheentrypointfortheconsoleapplication.#includestdafx.h#includeiostreamusingnamespacestd;#includequeue#defineMAX_VEX_NUM20//最大顶点数queueintq;structMGraph{charvexs[MAX_VEX_NUM];//顶点向量//AdjMatrixintarcs[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵intvexnum,arcnum;};MGraphG;//申明一个无向图的邻接矩阵类型intvisited[MAX_VEX_NUM];//设置标志数组classC_JDC_Graph{public:C_JDC_Graph(){};//构造函数~C_JDC_Graph(){};//析构函数intLocatevex(MGraphG,charv);//图的基本操作，寻找V的位置intCreateUDG(MGraph&G);//数组邻接矩阵表示法构造无向图intFirstadj(MGraphG,inti);//顶点下标为i的顶点的第一个邻接顶点intNext_adj(MGraphG,inti,intk);//顶点下标为i的顶点相对于k的下一个顶点,k为i的当前邻接顶点,二者都是顶点下标voiddfs_graph(MGraphG,intv);//无向图的深度优先遍历，从第v个顶点出发，v为顶点下标voiddfstraverse(MGraphG,intvex);//从vex开始深度遍历图//intbfstraverse(MGraphG);//无向图的广度遍历，从第v个顶点出发，v为顶点下标};intC_JDC_Graph::Locatevex(MGraphG,charv)//图的基本操作，寻找V的位置{inti=0;while(iG.vexnum&&v!=G.vexs[i])i++;if(iG.vexnum)returni;//查找成功则返回顶点的下标elsereturn-1;}intC_JDC_Graph::CreateUDG(MGraph&G)//数组邻接矩阵表示法构造无向图{charv1,v2;cout请输入图的顶点数和弧数endl;cinG.vexnumG.arcnum;cout请输入顶点值endl;for(inti=0;iG.vexnum;i++)//构造顶点向量cinG.vexs[i];for(intq=0;qG.vexnum;q++)//初始化邻接矩阵for(intp=0;pG.vexnum;p++)G.arcs[q][p]=0;for(intk=0;kG.arcnum;k++)//构造邻接矩阵{cout输入该弧依附的顶点endl;cinv1v2;inta=Locatevex(G,v1);intb=Locatevex(G,v2);G.arcs[a][b]=1;G.arcs[b][a]=G.arcs[a][b];}for(intn=0;nG.vexnum;n++)//输出顶点coutG.vexs[n];coutendl;coutendl;cout该图的邻接矩阵表示为：\n;for(intx=0;xG.vexnum;x++)//输出邻接矩阵{for(inty=0;yG.vexnum;y++)coutG.arcs[x][y];coutendl;}return1;}//CreateUDGintC_JDC_Graph::Firstadj(MGraphG,inti)//顶点下标为i的顶点的第一个邻接顶点{intj=0;while(jG.vexnum&&G.arcs[i][j]!=1)j=j+1;if(jG.vexnum)returnj;elsereturn-1;}intC_JDC_Graph::Next_adj(MGraphG,inti,intk)//顶点下标为i的顶点相对于k的下一个顶点,k为i的当前邻接顶点,二者都是顶点下标{intj=k+1;while(jG.vexnum&&G.arcs[i][j