测绘软件实习报告.doc

中国矿业大学测绘软件设计与实现实验报告学号： 姓名： 班级： 指导教师：王永波实验一 二叉树的构建及其遍历算法的实现实验目的：完成二叉树的构建以及二叉树的遍历等，加深对树以及二叉树的遍历相关知识的理解。实验内容：1.二叉树类的定义及建立。2.二叉树的前序、中序、后序遍历。主要代码：template class C_LJH_BinTreepublic:C_LJH_BinTree();/构造函数，根据输入前序序列由键盘输入C_LJH_BinTree();/析构函数void PreOrder();/前序遍历void InOrder();/中序遍历void PostOrder();/后序遍历private:T data;C_LJH_BinTree *lchild,*rchild; bool NO_Die;template C_LJH_BinTree:C_LJH_BinTree()NO_Die = false;lchild = NULL;rchild = NULL;char ch;cinch;if (ch = #) NO_Die = true;/若为#，代表空节点 else this-data = ch;/保存输入的节点/左子树C_LJH_BinTree *newChild0 = new C_LJH_BinTree();if (newChild0-NO_Die)delete newChild0;elsethis-lchild= newChild0;/右子树C_LJH_BinTree *newChild1 = new C_LJH_BinTree();/直接创建子节点，if (newChild1-NO_Die)delete newChild1;elsethis-rchild= newChild1;/析构函数template C_LJH_BinTree:C_LJH_BinTree()if (lchild) delete lchild; /删除父节点之前，先删除子节点if (rchild) delete rchild; /前序遍历template void C_LJH_BinTree:PreOrder()coutdatalchild-PreOrder();if (rchild!=NULL)this-rchild-PreOrder(); /中序遍历template void C_LJH_BinTree:InOrder()if (lchild) lchild-InOrder();coutdataInOrder(); /后序遍历template void C_LJH_BinTree:PostOrder()if (lchild) lchild-PostOrder();if (rchild) rchild-PostOrder();coutdatat;int main()cout请输入二叉树的前序遍历：endl;cout（以#作为分支结尾，例如：A B # # C # #）endl;C_LJH_BinTree m_tree;coutendl;cout前序遍历为：endl;m_tree.PreOrder(); coutendl; cout中序遍历为：endl;m_tree.InOrder();coutendl; cout后序遍历为：endl;m_tree.PostOrder();cout=0&i=numVertices ? VerticesListi : NULL;int getWeight(int v1,int v2)/取边(v1,v2)上的权值return v1!=-1&v2!=-1 ? Edgev1v2 : 0;int getFirstNeighbor(int v);/取顶点v的第一个邻接顶点int getNextNeighbor(int v,int w);/取v的邻接顶点w的下一邻接顶点bool insertVertex(char vertex);/插入顶点vertexbool insertEdge(int v1,int v2,int weight);/插入边(v1,v2),权为weightbool removeVertex(int v);/删去顶点v和所有与它相关联的边bool removeEdge(int v1,int v2);/在图中删去边(v1,v2)int getVertexPos(char vertex)/给出顶点vertex的位置,如果该顶点不在图内则返回-1for(int i=0;inumVertices;i+)if(VerticesListi=vertex) return i;return -1;int mini();/求图中所有边的最小权值bool input();/输入函数bool output();/输出函数void kruskal();/kruskal算法void prim();/prim算法protected:int maxVertices;/图中最大顶点数int numEdges;/图中当前边数int numVertices;/图中当前顶点数private:char *VerticesList;/顶点表int * *Edge;/邻接矩阵int visit50;/便利时的辅助工具primnode closeedge50;/为实现prim 函数的辅助结点;LJH_Graphmtx:LJH_Graphmtx(int sz)/构造函数maxVertices=sz;numVertices=0;numEdges=0;int i,j;VerticesList=new charmaxVertices;/创建顶点表数组Edge=(int * *)new int *maxVertices;/创建邻接矩阵数组for(i=0;imaxVertices;i+)Edgei=new intmaxVertices;for(i=0;imaxVertices;i+)/邻接矩阵初始化for(j=0;jmaxVertices;j+)Edgeij=(i=j)? 0 : maxWeight;int LJH_Graphmtx:getFirstNeighbor(int v) if(v!=-1)for(int i=0;i0&EdgevimaxWeight)return i;return -1;int LJH_Graphmtx:getNextNeighbor(int v,int w)/给出顶点v的某邻接顶点w的下一个邻接顶点的位置，如果找不到，则函数返回-1if(v!=-1&w!=-1)for(int i=w+1;i0&EdgevimaxWeight) return i;return -1;bool LJH_Graphmtx:insertVertex(char vertex)/插入顶点vertexif(numVertices=maxVertices) return false;/顶点表满，不插入VerticesListnumVertices+=vertex;return true;bool LJH_Graphmtx:insertEdge(int v1,int v2,int weight)/插入边(v1,v2),权为weightif(v1!=-1&v1numVertices&v2!=-1&v2numVertices&Edgev1v2=maxWeight)/插入条件(?)Edgev1v2=Edgev2v1=weight;numEdges+;return true;else return false;bool LJH_Graphmtx:removeVertex(int v)/删去顶点v和所有与它相关联的边if(v=numVertices)return false;/v不在图中，不删除int i,j;VerticesListv=VerticesListnumVertices-1;/顶点表中删除该结点for(i=0;i0&EdgeivmaxWeight) numEdges-;for(i=0;inumVertices;i+)/用最后一列填补第v列Edgeiv=EdgeinumVertices-1;numVertices-;/顶点个数减1for(j=0;j-1&v1-1&v20&Edgev1v2maxWeight)Edgev1v2=Edgev2v1=maxWeight;/删除边(v1,v2)numEdges-;return true;else return false;bool LJH_Graphmtx:input()int i,j,k,n,m;char e1,e2;int weight;cout请输入顶点数和边数:nm;/输入顶点数n和边数mcout请输入顶点的值：endl;for(i=0;ie1;this-insertVertex(e1);i=0;while(im)cout请输入端点信息:e1e2weight;/输入端点信息j=this-getVertexPos(e1);/查顶点号k=this-getVertexPos(e2);if(j=-1|k=-1)cout边两端点信息输入有误，请重新输入！insertEdge(j,k,weight);i+;return true;bool LJH_Graphmtx:output()/输出函数int i,j,n,m;char e1,e2;int w;n=this-NumberOfVertices();m=this-NumberOfEdges();cout顶点的个数为：nendl;cout边的条数为：mendl;cout所有边的信息为：endl;for(i=0;in;i+)for(j=i+1;jgetWeight(i,j);if(w0&wgetValue(i);e2=this-getValue(j);cout(e1,e2,w)endl;return true;int LJH_Graphmtx:mini()/求图中所有边的最小权值，并返回 static int i; int min=0; for (int j=0;jcloseedgej.lowcost) min=j; i=min;cout包括边(closeedgei.begvex,closeedgei.endvex); return i;/图的深度优先搜索函数/void DFS(LJH_Graphmtx & G,int v,bool visited);/先声明函数，后使用void DFS(LJH_Graphmtx & G,char & v)/从顶点v出发，对图G进行深度优先遍历的主要过程int i,loc,n=G.NumberOfVertices();/取图中顶点的个数bool * visited=new booln;/创建辅助数组for(i=0;in;i+)/初始化辅助数组visitedvisitedi=0;loc=G.getVertexPos(v);/取得v结点在图中的位置DFS(G,loc,visited);/从顶点0开始深度优先搜索delete visited;void DFS(LJH_Graphmtx & G,int v,bool visited)coutG.getValue(v)endl;/访问顶点vvisitedv=1;/顶点v作访问标记int w=G.getFirstNeighbor(v);/找v的第一个邻接顶点wwhile(w!=-1)/若邻接顶点w存在if(visitedw=0)DFS(G,w,visited);/若w未被访问，递归访问顶点ww=G.getNextNeighbor(v,w);/取v排在w后的下一个邻接顶点/图的广度优先搜索函数/void BFS(LJH_Graphmtx G,char v)/从顶点v出发，以广度优先的次序横向搜索图，算法中使用了一个队列。int i,w,n=G.NumberOfVertices();/去图中的定点个数bool *visited=new booln;/用来记录顶点是否被访问过，被访问值为1，为被访问值为0for(i=0;in;i+)/初始化visitedi=0;int loc=G.getVertexPos(v);/取顶点v的位置号coutG.getValue(loc)endl;/访问顶点vvisitedloc=1;/做已访问标记LJH_Queue Q;/定义一个辅助队列Q.EnQueue(loc);/顶点进队，实现分层访问while(!Q.IsEmpty()/循环访问所有结点，判断队列是否为空Q.DeQueue(loc);/从队列中退出顶点locw=G.getFirstNeighbor(loc);/找顶点loc的第一个邻接点wwhile(w!=-1)/若邻接点w存在if(visitedw=false)/若未被访问coutG.getValue(w)endl;/访问顶点wvisitedw=1;/标记w已经被访问Q.EnQueue(w);/顶点w进队列w=G.getNextNeighbor(loc,w);/找顶点loc的下一个邻接顶点，重复检测v的所有邻接顶点delete visited;/kruskal函数的实现/void LJH_Graphmtx:kruskal() int a,b,k=0; int min=maxWeight; int Edge12020; for (int m=0;mnumVertices;m+) visitm=m;/每一个顶点属于一颗树 for (int i=0;inumVertices;i+) for(int j=0;jnumVertices;j+)Edge1ij=Edgeij; while (knumVertices-1) min=maxWeight; for (int i=0;inumVertices;i+) for (int j=0;jnumVertices;j+) if (Edge1ijmin) a=i;b=j;min=Edge1ij; if (visita!=visitb) cout包括边(VerticesLista,VerticesListb); k+; for (int n=0;nnumVertices;n+) if (visitn=visitb)visitn=visita; else Edge1ab=Edgeba=maxWeight; coutendl;/Prim函数的实现/void LJH_Graphmtx:prim() char u; cout请输入起始顶点：u; int i=this-getVertexPos(u); visiti=1; for(int j=0;jnumVertices;j+) closeedgej.begvex=u; closeedgej.endvex=VerticesListj; closeedgej.lowcost=Edgeij; for (int m=1;mnumVertices;m+) int n=mini(); visitn=1; closeedgen.lowcost=maxWeight; for (int p=0;pnumVertices;p+) if(!visitp) if(Edgepncloseedgep.lowcost) closeedgep.lowcost=Edgepn;closeedgep.begvex=VerticesListn; 实验结果：实验体会：经过这次实验让我更深刻的理解了类的创建及相互间调用，能够对二维数组的动态开辟空间和释放空间有了更深刻的理解，对图的遍历及构建最小生成树也有了深刻的体会。总之，在这次试验中，学到了许多，也提高了自己的编程能力。实验三、矩阵类的设计与实现实验目的：通过上机实践，实现矩阵的生成、加减乘除运算，以及求矩阵的转置、求逆和行列式。同时加深对矩阵的理论的理解，并用计算机程序算法来描述矩阵生成及运算。实验内容：通过构造矩阵类，实现矩阵的定义，包括：矩阵的加减乘除，求矩阵的转置、求逆等，求矩阵的行列式。主要代码： class LJH_CMatrixpublic:LJH_CMatrix(); / 默认构造函数LJH_CMatrix(int row, int column); / 构造函数一LJH_CMatrix(const LJH_CMatrix& m); / 复制构造函数LJH_CMatrix(); / 默认析构函数void input();/矩阵输入void output(); / 输出该矩阵LJH_CMatrix transpose(); / 矩阵转置/LJH_CMatrix yuzishi(int i,int j);/求矩阵的第(i,j)的余子式double hanglieshi();/求矩阵的行列式LJH_CMatrix bansui();/求矩阵的伴随矩阵LJH_CMatrix inverse(); / 矩阵求逆(伴随矩阵除以行列式)/LJH_CMatrix inv();/矩阵求逆(用高斯约当法)LJH_CMatrix & change(int k,int l);/交换矩阵的第k行和第l行int max_cloumn(int k);/求矩阵第k列的最大行数/ 设置(i,j)的值void setValue(int row, int column, double value) _Arowcolumn = value; double getValue(int row, int column) const return _Arowcolumn; / 设置行、列的值void setRow(const int row) _row = row; int getRow() const return _row; void setColunm(const int column) _column = column; int getColumn() const return _column; public:/ 成员变量double* _A; / 或用这个定义vectorvector _A;int _row, /*行*/ _column; / 列;void LJH_CMatrix:input()/输入函数int i,j;cout请输入矩阵的行数：_row;cout请输入矩阵的列数：_column;cout请输入矩阵中的元素：endl;for(i=0;i_row;i+)for(j=0;j_Aij;void LJH_CMatrix:output()/输出函数int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)cout_Aij ;cout_column;tem._column=this-_row;int i,j;for(i=0;i_row;i+)for(j=0;j_row-1;temp._column=this-_column-1;int m,n,k=0,l;for(m=0;m_row;m+)l=0;for(n=0;n_column;n+)if(m!=i&n!=j)temp._Akl=_Amn;if(n!=j) l+;if(m!=i) k+;return temp;double LJH_CMatrix:hanglieshi()/求矩阵的行列式if(_row!=_column)cerr此矩阵无行列式endl;if(_row=1&_column=1)return _A00;elseint i;double sum=0;for(i=0;iyuzishi(0,i).hanglieshi();return sum;LJH_CMatrix LJH_CMatrix:bansui()/求伴随矩阵LJH_CMatrix temp;temp._column=this-_column;temp._row=this-_row;int i,j;for(i=0;i_row;i+)for(j=0;jyuzishi(i,j).hanglieshi();return temp;LJH_CMatrix LJH_CMatrix:inverse()/矩阵求逆LJH_CMatrix temp;int n;n=this-hanglieshi();temp=this-bansui();int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)temp._Aij/=n;return temp;LJH_CMatrix & LJH_CMatrix:change(int k,int l)/交换矩阵的第k行和第l行int i;double j;for(i=0;i_column;i+)j=_Aki;_Aki=_Ali;_Ali=j;return *this;int LJH_CMatrix:max_cloumn(int k)/求矩阵第k列中从第k个元素之后绝对值最大的行数int m=k;double max=fabs(_Akk);for(int i=k+1;imax)max=fabs(_Aik);m=i;return m;LJH_CMatrix LJH_CMatrix:inv()/矩阵求逆，通过行列变换int i,j,m;LJH_CMatrix E1;E1=*this;if(this-_row!=this-_column)cerr该矩阵不能求逆endl;elseif(E1.hanglieshi()=0)cerr该矩阵不可逆：endl;else/把矩阵E赋值成单位阵LJH_CMatrix E;/创建一个和当前方阵阶数相同的单位矩阵E._row=E1._row;E._column=E1._column;for(i=0;iE1._row;i+)for(j=0;jE1._row;j+)E._Aij=0;for(i=0;iE1._row;i+)E._Aii=1;/化上三角阵int i,j,hang;for(i=0;iE1._column-1;i+)/hang=E1.max_cloumn(i);if(hang!=i)E1.change(i,hang);E.change(i,hang);double xishu;for(m=i+1;mE1._row;m+)/第m行xishu=E1._Ami/E1._Aii;for(j=0;j_column-1;i0;i-)/double xishu1;for(m=0;mi;m+)xishu1=E1._Ami/E1._Aii;for(j=0;j_column;j+)E1._Amj=E1._Amj-xishu1*E1._Aij;E._Amj=E._Amj-xishu1*E._Aij; /矩阵单位化double xishu3;for(i=0;iE1._column;i+)xishu3=1/E1._Aii;for(j=0;jE1._column;j+)E1._Aij*=xishu3;E._Aij*=xishu3;return E;void main()LJH_CMatrix array1,array2,array3,array4,array5,array6,array7;cout请输入矩阵array1相关信息：;array1.input();cout输入的矩阵为：endl;array1.output();cout请输入矩阵array2相关信息：;array2.input();cout输入的矩阵为：endl;array2.output(); cout两矩阵求和：endl; array5=array1+array2; array5.output(); cout两矩阵相乘：endl; array6=array1*array2; array6.output(); cout两矩阵相乘：endl; array7=array1-array2; array7.output();array3=array1.inv();array4=array1.transpose();coutarray1逆矩阵为：endl;array3.output();coutendl; coutarray1转置矩阵为：endl; array4.output(); coutendl;实验结果:实验体会：做这个实验，尽管花费很长时间。但我收获很多。这个实验综合了我们所学的C+面向对象类的设计，以及我们如何利用自己所学的知识，把它转换为代码C+程序。比如在实现矩阵的转置和矩阵的求逆这方面，涉及递归调用。通过构造一个跟需求矩阵同阶的单位矩阵，然后通过行变换把该矩阵变成单位阵，原来的单位阵也做相应变化，便得到所求的逆矩阵。此外，这个实验还让我们复习了以前所学的函数重载，运算符重载等知识。经过这次实验，获益匪浅。实验四、基于直接法（列主元素法）的线性方程组求解实验目的：基于直接法（列主元素法）与迭代法（Jacobi迭代与Gauss-Seidel迭代法）的线性方程组求解.对各种迭代的收敛条件，和收敛速度做个比较。掌握这些函数的实现。实验内容：完成基于直接法（列主元素法）与迭代法（Jacobi迭代与Gauss-Seidel迭代法）的线性方程组求解并且对各种迭代的收敛条件，和收敛速度做个比较。比较方程组右端对求解是否有影响。同时掌握这些函数的实现。主要代码：void Matrix:ColPivot(Matrix& m) /列主元素法int i,j,k,t;double l;for (i=0;im._row;i+) k=i; /寻找主元for (j=i+1;jm._row;j+) if(fabs(m._Aki)fabs(m._Aji)k=j;if(k!=i)for (j=0;jm._row+1;j+)swap(m._Aij,m._Akj);for (j=i+1;jm._row;j+) /将增广矩阵化为上三角矩阵l=m._Aji/m._Aii;for(t=i;tm._row+1;t+)m._Ajt -= l*m._Ait;if (m._Am._rowm._row=0&m._Am._rowm._row+1!=0)cout=0;i-) /自下往上逐步回代求得真解for(j=m._row-1;j=i+1;j-)m._Aim._row -= m._Xj*m._Aij;m._Xi= m._Aim._row/m._Aii;cout用列主元素法求得的方程组的解：endl;for(i=0;im._row;i+)coutxi+1=m._Xi ;coutendl;void Matrix:DirectLU(Matrix& m) /LU分解法int i,j,/*k,*/t;double *L,*b;b = new double m._row;L = new double *m._row; /对LU分解中的L矩阵的内存分配、初始化for (i=0;im._row;i+)Li = new double m._row;for(i=0;im._row;i+) for (j=0;jm._row;j+)if(i=j)Lij=1;elseLij=0;for (i=0;im._row;i+) /得到b矩阵bi=m._Aim._row;for (i=0;im._row;i+) for (j=i+1;jm._row;j+) /将系数矩阵化为上三角矩阵得到U矩阵Lji=m._Aji/m._Aii;for(t=i;tm._row;t+)m._Aj