中国矿业大学测绘软件实习报告

《中国矿业大学测绘软件实习报告》由会员分享，可在线阅读，更多相关《中国矿业大学测绘软件实习报告（17页珍藏版）》请在装配图网上搜索。

1、-中国矿业大学测绘软件设计与实现实验报告学号：姓名：班级：指导教师：王永波实验一 二叉树的构建及其遍历算法的实现实验目的：完成二叉树的构建以及二叉树的遍历等，加深对树以及二叉树的遍历相关知识的理解。实验容：1.二叉树类的定义及建立。2.二叉树的前序、中序、后序遍历。主要代码：. z.-template class C_LJH_BinTreepublic:C_LJH_BinTree();/构造函数，根据输入前序序列由键盘输入C_LJH_BinTree();/析构函数void PreOrder();/前序遍历void InOrder();/中序遍历void PostOrder();/后序遍历pri

2、vate: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 newCh

3、ild0;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_BinTre

4、e: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请

5、输入二叉树的前序遍历：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

6、!=-1 Edgev1v2 : 0;int getFirstNeighbor(int v);/取顶点v的第一个邻接顶点int getNe*tNeighbor(int v,int w);/取v的邻接顶点w的下一邻接顶点bool insertVerte*(char verte*);/插入顶点verte*bool insertEdge(int v1,int v2,int weight);/插入边(v1,v2),权为weightbool removeVerte*(int v);/删去顶点v和所有与它相关联的边bool removeEdge(int v1,int v2);/在图中删去边(v1,v2)in

7、t getVerte*Pos(char verte*)/给出顶点verte*的位置,如果该顶点不在图则返回-1for(int i=0;inumVertices;i+)if(VerticesListi=verte*) return i;return -1;int mini();/求图中所有边的最小权值bool input();/输入函数bool output();/输出函数void kruskal();/kruskal算法void prim();/prim算法protected:int ma*Vertices;/图中最大顶点数int numEdges;/图中当前边数int numVertices

8、;/图中当前顶点数private:char *VerticesList;/顶点表int * *Edge;/邻接矩阵int visit50;/便利时的辅助工具primnode closeedge50;/为实现prim 函数的辅助结点;LJH_Graphmt*:LJH_Graphmt*(int sz)/构造函数ma*Vertices=sz;numVertices=0;numEdges=0;int i,j;VerticesList=new charma*Vertices;/创立顶点表数组Edge=(int * *)new int *ma*Vertices;/创立邻接矩阵数组for(i=0;ima*V

9、ertices;i+)Edgei=new intma*Vertices;for(i=0;ima*Vertices;i+)/邻接矩阵初始化for(j=0;jma*Vertices;j+)Edgeij=(i=j) 0 : ma*Weight;int LJH_Graphmt*:getFirstNeighbor(int v) if(v!=-1)for(int i=0;i0&Edgevima*Weight)return i;return -1;int LJH_Graphmt*:getNe*tNeighbor(int v,int w)/给出顶点v的*邻接顶点w的下一个邻接顶点的位置，如果找不到，则函数返回

10、-1if(v!=-1&w!=-1)for(int i=w+1;i0&Edgevima*Weight) return i;return -1;bool LJH_Graphmt*:insertVerte*(char verte*)/插入顶点verte*if(numVertices=ma*Vertices) return false;/顶点表满，不插入VerticesListnumVertices+=verte*;return true;bool LJH_Graphmt*:insertEdge(int v1,int v2,int weight)/插入边(v1,v2),权为weightif(v1!=-

11、1&v1numVertices&v2!=-1&v2numVertices&Edgev1v2=ma*Weight)/插入条件()Edgev1v2=Edgev2v1=weight;numEdges+;return true;else return false;bool LJH_Graphmt*:removeVerte*(int v)/删去顶点v和所有与它相关联的边if(v=numVertices)return false;/v不在图中，不删除int i,j;VerticesListv=VerticesListnumVertices-1;/顶点表中删除该结点for(i=0;i0&Edgeivma*W

12、eight) numEdges-;for(i=0;inumVertices;i+)/用最后一列填补第v列Edgeiv=EdgeinumVertices-1;numVertices-;/顶点个数减1for(j=0;j-1&v1-1&v20&Edgev1v2ma*Weight)Edgev1v2=Edgev2v1=ma*Weight;/删除边(v1,v2)numEdges-;return true;else return false;bool LJH_Graphmt*:input()int i,j,k,n,m;char e1,e2;int weight;cout请输入顶点数和边数:nm;/输入顶点数

13、n和边数mcout请输入顶点的值：endl;for(i=0;ie1;this-insertVerte*(e1);i=0;while(im)cout请输入端点信息:e1e2weight;/输入端点信息j=this-getVerte*Pos(e1);/查顶点号k=this-getVerte*Pos(e2);if(j=-1|k=-1)cout边两端点信息输入有误，请重新输入！insertEdge(j,k,weight);i+;return true;bool LJH_Graphmt*:output()/输出函数int i,j,n,m;char e1,e2;int w;n=this-NumberOfV

14、ertices();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_Graphmt*:mini()/求图中所有边的最小权值，并返回 static int i; int min=0; for (int j=0;jcloseedgej.lowcost) min=j; i=

15、min;cout包括边(closeedgei.begve*,closeedgei.endve*); return i;/图的深度优先搜索函数/void DFS(LJH_Graphmt* & G,int v,bool visited);/先声明函数，后使用void DFS(LJH_Graphmt* & G,char & v)/从顶点v出发，对图G进展深度优先遍历的主要过程int i,loc,n=G.NumberOfVertices();/取图中顶点的个数bool * visited=new booln;/创立辅助数组for(i=0;in;i+)/初始化辅助数组visitedvisitedi=0;

16、loc=G.getVerte*Pos(v);/取得v结点在图中的位置DFS(G,loc,visited);/从顶点0开场深度优先搜索delete visited;void DFS(LJH_Graphmt* & 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.getNe*tNeighb

17、or(v,w);/取v排在w后的下一个邻接顶点/图的广度优先搜索函数/void BFS(LJH_Graphmt* 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.getVerte*Pos(v);/取顶点v的位置号coutG.getValue(loc)endl;/访问顶点vvisitedloc=1;/做

18、已访问标记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.getNe*tNeighbor(loc,w);/找

19、顶点loc的下一个邻接顶点，重复检测v的所有邻接顶点delete visited;/kruskal函数的实现/void LJH_Graphmt*:kruskal() int a,b,k=0; int min=ma*Weight; 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=ma*Weight; for (in

20、t 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=ma*Weight; coutendl;/Prim函数的实现/void LJH_Graphmt*:prim() char u; c

21、out请输入起始顶点：u; int i=this-getVerte*Pos(u); visiti=1; for(int j=0;jnumVertices;j+) closeedgej.begve*=u; closeedgej.endve*=VerticesListj; closeedgej.lowcost=Edgeij; for (int m=1;mnumVertices;m+) int n=mini(); visitn=1; closeedgen.lowcost=ma*Weight; for (int p=0;pnumVertices;p+) if(!visitp) if(Edgepnclo

22、seedgep.lowcost) closeedgep.lowcost=Edgepn;closeedgep.begve*=VerticesListn; 实验结果：实验体会：经过这次实验让我更深刻的理解了类的创立及相互间调用，能够对二维数组的动态开辟空间和释放空间有了更深刻的理解，对图的遍历及构建最小生成树也有了深刻的体会。总之，在这次试验中，学到了许多，也提高了自己的编程能力。. z.-. z.-实验三、矩阵类的设计与实现实验目的：通过上机实践，实现矩阵的生成、加减乘除运算，以及求矩阵的转置、求逆和行列式。同时加深对矩阵的理论的理解，并用计算机程序算法来描述矩阵生成及运算。实验容：通过构造矩阵

23、类，实现矩阵的定义，包括：矩阵的加减乘除，求矩阵的转置、求逆等，求矩阵的行列式。主要代码：. z.-class LJH_CMatri*public:LJH_CMatri*(); / 默认构造函数LJH_CMatri*(int row, int column); / 构造函数一LJH_CMatri*(const LJH_CMatri*& m); / 复制构造函数LJH_CMatri*(); / 默认析构函数void input();/矩阵输入void output(); / 输出该矩阵LJH_CMatri* transpose(); / 矩阵转置/LJH_CMatri* yuzishi(int

24、i,int j);/求矩阵的第(i,j)的余子式double hanglieshi();/求矩阵的行列式LJH_CMatri* bansui();/求矩阵的伴随矩阵LJH_CMatri* inverse(); / 矩阵求逆(伴随矩阵除以行列式)/LJH_CMatri* inv();/矩阵求逆(用高斯约当法)LJH_CMatri* & change(int k,int l);/交换矩阵的第k行和第l行int ma*_cloumn(int k);/求矩阵第k列的最大行数/ 设置(i,j)的值void setValue(int row, int column, double value) _Arow

25、column = 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

26、 _row, /*行*/ _column; / 列;void LJH_CMatri*:input()/输入函数int i,j;cout请输入矩阵的行数：_row;cout请输入矩阵的列数：_column;cout请输入矩阵中的元素：endl;for(i=0;i_row;i+)for(j=0;j_Aij;void LJH_CMatri*: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(

27、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_CMatri*:hanglieshi()/求矩阵的行列式if(_row!=_column)cerr此矩阵无行列式endl;if(_row=1&_column=1)return _A00;elseint i;double sum=0;for(i=0;iyuzis

28、hi(0,i).hanglieshi();return sum;LJH_CMatri* LJH_CMatri*:bansui()/求伴随矩阵LJH_CMatri* 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_CMatri* LJH_CMatri*:inverse()/矩阵求逆LJH_CMatri* temp;int n;n=this-hanglieshi();temp=this-bans

29、ui();int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)temp._Aij/=n;return temp;LJH_CMatri* & LJH_CMatri*: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_CMatri*:ma*_cloumn(int k)/求矩阵第k列中从第k个元素之后绝对值最大的行数int m=k;double ma*=fabs(_Akk);for(int

30、i=k+1;ima*)ma*=fabs(_Aik);m=i;return m;LJH_CMatri* LJH_CMatri*:inv()/矩阵求逆，通过行列变换int i,j,m;LJH_CMatri* E1;E1=*this;if(this-_row!=this-_column)cerr该矩阵不能求逆endl;elseif(E1.hanglieshi()=0)cerr该矩阵不可逆：endl;else/把矩阵E赋值成单位阵LJH_CMatri* E;/创立一个和当前方阵阶数一样的单位矩阵E._row=E1._row;E._column=E1._column;for(i=0;iE1._row;i

31、+)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.ma*_cloumn(i);if(hang!=i)E1.change(i,hang);E.change(i,hang);double *ishu;for(m=i+1;mE1._row;m+)/第m行*ishu=E1._Ami/E1._Aii;for(j=0;j_column-1;i0;i-)/double *ishu1;for(m=0;mi;m+)*ishu1=E1._A

32、mi/E1._Aii;for(j=0;j_column;j+)E1._Amj=E1._Amj-*ishu1*E1._Aij;E._Amj=E._Amj-*ishu1*E._Aij; /矩阵单位化double *ishu3;for(i=0;iE1._column;i+)*ishu3=1/E1._Aii;for(j=0;jE1._column;j+)E1._Aij*=*ishu3;E._Aij*=*ishu3;return E;void main()LJH_CMatri* array1,array2,array3,array4,array5,array6,array7;cout请输入矩阵array

33、1相关信息：;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

34、.inv();array4=array1.transpose();coutarray1逆矩阵为：endl;array3.output();coutendl; coutarray1转置矩阵为：endl; array4.output(); coutendl;. z.-实验结果:实验体会：做这个实验，尽管花费很长时间。但我收获很多。这个实验综合了我们所学的C+面向对象类的设计，以及我们如何利用自己所学的知识，把它转换为代码C+程序。比方在实现矩阵的转置和矩阵的求逆这方面，涉及递归调用。通过构造一个跟需求矩阵同阶的单位矩阵，然后通过行变换把该矩阵变成单位阵，原来的单位阵也做相应变化，便得到所求的逆矩阵

35、。此外，这个实验还让我们复习了以前所学的函数重载，运算符重载等知识。经过这次实验，获益匪浅。实验四、基于直接法列主元素法的线性方程组求解实验目的：基于直接法列主元素法与迭代法Jacobi迭代与Gauss-Seidel迭代法的线性方程组求解.对各种迭代的收敛条件，和收敛速度做个比拟。掌握这些函数的实现。实验容：完成基于直接法列主元素法与迭代法Jacobi迭代与Gauss-Seidel迭代法的线性方程组求解并且对各种迭代的收敛条件，和收敛速度做个比拟。比拟方程组右端对求解是否有影响。同时掌握这些函数的实现。主要代码：. z.-void Matri*:ColPivot(Matri*& m) /列主元

36、素法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=

37、0;i-) /自下往上逐步回代求得真解for(j=m._row-1;j=i+1;j-)m._Aim._row -= m._*j*m._Aij;m._*i= m._Aim._row/m._Aii;cout用列主元素法求得的方程组的解：endl;for(i=0;im._row;i+)cout*i+1=m._*i ;coutendl;void Matri*:DirectLU(Matri*& m) /LU分解法int i,j,/*k,*/t;double *L,*b;b = new double m._row;L = new double *m._row; /对LU分解中的L矩阵的存分配、初始化for

38、 (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._Ajt -= Lji*m._Ait;coutL矩阵:endl;for(i=0;im._row;i+)for

39、 (j=0;jm._row;j+)coutLij ;coutendl;coutU矩阵:endl;for(i=0;im._row;i+)for (j=0;jm._row;j+)coutm._Aij ;coutendl;coutb矩阵：endl;for (i=0;im._row;i+)coutbiendl;double *Y; /引入矩阵Y，利用公式LY=b，求解得到YY = new doublem._row;for(i=0;im._row;i+)Yi=0;for (i=0;im._row;i+)for(j=0;j=0;i-) /利用公式U*=Y，求解得到*for(j=m._row-1;j=i+1

40、;j-)Yi -= m._*j*m._Aij;m._*i= Yi/m._Aii;cout用LU分解法求得的方程组的解：endl;for(i=0;im._row;i+)cout*i+1=m._*i ;coutendl;void Matri*:Jacobi(Matri*& m) /Jacobi雅克比迭代法int i,j,k=0;double epsilon,s,*Y;for(i=0;im._row;i+)m._*i=0;Y = new double m._row;while (true)epsilon=0;k+;for (i=0;im._row;i+)s=0;for (j=0;jm._row;j+

41、)if(i!=j) s += m._Aij*m._*j;Yi = (m._Aim._row-s)/m._Aii;epsilon += fabs(Yi-m._*i);if (epsilon1e-6)cout迭代次数为：k=1000)cout方法是发散的！endl;break;for (i=0;im._row;i+)m._*i= Yi;cout用Jacobi雅克比迭代法求得的方程组的解：endl;for(i=0;im._row;i+)cout*i+1=m._*i ;coutendl;void Matri*:GaussSeidel(Matri*& m) /Gauss-Seidel高斯-赛德尔迭代法int i,j,k=0;double epsilon,s,*Y,ma*,temp;Y = new double m._row;for(i=0;im._row;i+)m._*i=0;Yi=0;while (true)epsilon=0;k+;for (i=0;im._row;i+)s=0;for (j=0;jm._row;j+)if(j!=i) s += m._Ai