测绘软件实习报告.docx

中国矿业大学成绩：测绘软件设计与实现实验报告学号：07093043姓名： 况佳亮 班级：测绘09-4班 指导教师：王永波学院：环境与测绘学院 2011年 11 月 12 日实验一图的创建、遍历、及其MST的构建实验目的 图的创建 。 基于深度优先的图的遍历算法的设计与实现 。 基于广度优先的图的遍历算法的设计与实现 。 基于Prim算法的最小生成树的构建。 基于Kruskal算法的最小生成树的构建 。实验过程#include#include” KJL_Queue.h”using namespace std;/定义为prim服务的辅助结点struct primnodepublic: char begvex;/开始结点 char endvex;/结束结点 int lowcost;/中间权值;class KJL_Graphmtx/图的邻接矩阵定义 public:KJL_Graphmtx(int sz=DefaultVertices);/构造函数KJL_Graphmtx()/析构函数delete VerticesList;delete Edge;bool GraphEmpty()/判断图是否为空if(numEdges=0)return true;else return false;bool GraphFull()/判断图是否为满if(numVertices=maxVertices|numEdges=maxVertices*(maxVertices-1)/2)return true;else return false;int NumberOfVertices()/返回当前顶点数return numVertices;int NumberOfEdges()/返回当前边数return numEdges;char getValue(int i)/取顶点i的值，i不合理返回0return i=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 函数的辅助结点;KJL_Graphmtx:KJL_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 KJL_Graphmtx:getFirstNeighbor(int v)/给出顶点位置v的第一个邻接顶点的位置，如果找不到，则函数返回-1if(v!=-1)for(int i=0;i0&EdgevimaxWeight)return i;return -1;int KJL_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 KJL_Graphmtx:insertVertex(char vertex)/插入顶点vertexif(numVertices=maxVertices) return false;/顶点表满，不插入VerticesListnumVertices+=vertex;return true;bool KJL_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 KJL_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 KJL_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 KJL_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 KJL_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(KJL_Graphmtx & G,int v,bool visited);/先声明函数，后使用void DFS(KJL_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(KJL_Graphmtx & G,int v,bool visited)/从顶点v出发，对图G进行深度优先遍历的子过程/从顶点位置v出发，以深度优先的次序访问所有可读入的尚未访问过的顶点。/算法中用到一个vistied，对已访问过的顶点做访问标记。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(KJL_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;/做已访问标记KJL_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 KJL_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 KJL_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; 实验结果实验体会经过这次实验让我更深刻的理解了C+类的的结构，能够对二维数组的动态开辟空间和释放空间有了更深刻的理解，对图的遍历及构建最小生成树也有了深刻的体会。总之，在这次试验中，学到了许多，也提高了自己的编程能力。实验二、快速排序算法的实现实验目的 选取表中一个元素rk（一般选第一个元素），令x=rk称为控制关键字，用控制关键字和无序区中其余元素关键字进行比较 设置两个指示器i，j，分别表示线性表第一个和最后一个元素位置 将j逐渐减小，逐次比较rj与x，直到出现一个rjx，然后将ri移动到rj位置 重复上述过程，知道i=j位置，并将x移动到rj位置，此时线性表以x为界分割成两个子区间 实现快速排序功能实验过程#includeusing namespace std;const maxSize=100;int partition(int data,int first,int end)/在实现快速排序函数时要用，这是快速排序的一趟算法int i=first;int j=end;int temp;while(ij)while(ij&datai=dataj) /向右扫描j-;if(ij)temp=datai;datai=dataj;dataj=temp;i+;while(ij&datai=dataj) /向左扫描i+;if(ij)temp=datai;datai=dataj;dataj=temp;j-;return i;class KJL_CSortpublic:KJL_CSort();KJL_CSort();public:/ 排序算法的具体实现void QuickSort();void input();void output();private:/ 成员变量int *data;int first,end;int size;/当前数组大小;KJL_CSort:KJL_CSort()first =0;end=0;size=0;data=new int maxSize;for(int j=0;jmaxSize;j+)dataj=0;KJL_CSort:KJL_CSort()delete data;void KJL_CSort:input()int i;cout请输入数组大小：size;end=size-1;cout输入数组的值：endl;int m;for(i=0;idatai;void KJL_CSort:output()int i;for(i=0;isize;i+)coutdatai ;coutendl;void KJL_CSort:QuickSort()int pivot;if(firstend)pivot=partition(data,first,end);end=pivot-1;QuickSort();first=pivot+1;QuickSort();first=0;end=size-1;void main()KJL_CSort biao;biao.input();cout快速排序前的顺序：endl;biao.output();biao.QuickSort();cout快速排序后的顺序：endl;biao.output();实验结果实验体会快速排序法，是众多排序方法中的一种，这种方法的优点在于它的比较次数少，每经过一趟比较，都可以把一个无序的数组分成两个部分，左边的部分全部小于（大于）右边的部分。在实现这个算法过程中，采用的时递归调用的方式。这让我对递归又有了更深层次的理解，对数组的排序，也不仅仅局限于冒泡，选择排序，在快速排序的基础上设计了以个快速排序类。实验三、矩阵类的设计与实现实验目的 按照上述矩阵类的设计，完成相应函数的编码 对于矩阵数据的存储，可以选用如下两种方式来实现 使用double* _A来存储矩阵;实验过程#include#includeusing namespace std;const maxSize=100;#define maxnum 50class KJL_CMatrixpublic:KJL_CMatrix(); / 默认构造函数KJL_CMatrix(int row, int column); / 构造函数一KJL_CMatrix(const KJL_CMatrix& m); / 复制构造函数KJL_CMatrix(); / 默认析构函数KJL_CMatrix& operator=(const KJL_CMatrix& m); / 赋值运算符bool operator=(const KJL_CMatrix& m); / 比括较运算符bool operator!=(const KJL_CMatrix& m); / 比括较运算符KJL_CMatrix operator+(const KJL_CMatrix& m); / 加运算符KJL_CMatrix operator-(const KJL_CMatrix& m); / 减运算符KJL_CMatrix& operator+=(const KJL_CMatrix& m); /+=运算符KJL_CMatrix& operator-=(const KJL_CMatrix& m); / -=运算符KJL_CMatrix operator-();/ 取负数KJL_CMatrix operator*(const KJL_CMatrix& m); / 乘法运算符void input();/矩阵输入void output(); / 输出该矩阵KJL_CMatrix transpose(); / 矩阵转置/KJL_CMatrix yuzishi(int i,int j);/求矩阵的第(i,j)的余子式double hanglieshi();/求矩阵的行列式KJL_CMatrix bansui();/求矩阵的伴随矩阵KJL_CMatrix inverse(); / 矩阵求逆(伴随矩阵除以行列式)/KJL_CMatrix inv();/矩阵求逆(用高斯约当法)KJL_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; / 列;KJL_CMatrix:KJL_CMatrix()/矩阵默认构造函数_row=0;_column=0;_A=(double * *) new double maxSize;int i;for(i=0;imaxSize;i+)_Ai=new doublemaxSize;int j;for(i=0;imaxSize;i+)for(j=0;jmaxSize;j+)_Aij=0;KJL_CMatrix:KJL_CMatrix(int row, int column)/构造函数重载 _row=row;_column=column;_A=(double * *) new double maxSize;int i;for(i=0;imaxSize;i+)_Ai=new doublemaxSize;int j;for(i=0;imaxSize;i+)for(j=0;jmaxSize;j+)_Aij=0;KJL_CMatrix:KJL_CMatrix(const KJL_CMatrix& m)/复制构造函数_row=m._row;_column=m._column;int i,j;_A=(double * *) new double maxSize;for(i=0;imaxSize;i+)_Ai=new doublemaxSize;for(i=0;imaxSize;i+)/初始化for(j=0;jmaxSize;j+)_Aij=0;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij=m._Aij;KJL_CMatrix:KJL_CMatrix()/析构函数delete _A;void KJL_CMatrix:input()/输入函数int i,j;cout请输入矩阵的行数：_row;cout请输入矩阵的列数：_column;cout请输入矩阵：endl;for(i=0;i_row;i+)for(j=0;j_Aij;void KJL_CMatrix:output()/输出函数int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)cout_Aij ;coutendl;KJL_CMatrix & KJL_CMatrix:operator=(const KJL_CMatrix & m)/=函数重载_row=m._row;_column=m._column;int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij=m._Aij;return *this;KJL_CMatrix KJL_CMatrix:operator-()/取负号负号重载int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij=-_Aij;return *this;KJL_CMatrix KJL_CMatrix:operator+(const KJL_CMatrix& m)/加号函数重载if(_row!=m._row|_column!=m._column)cerr矩阵不能相加！endl;int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij=_Aij+m._Aij;return *this;KJL_CMatrix& KJL_CMatrix:operator+=(const KJL_CMatrix& m)/+=符号函数重载if(_row!=m._row|_column!=m._column)cerr矩阵不能+=！endl;int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij+=m._Aij;return *this;KJL_CMatrix& KJL_CMatrix:operator-=(const KJL_CMatrix& m)/-=符号函数重载if(_row!=m._row|_column!=m._column)cerr矩阵不能-=！endl;int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij-=m._Aij;return *this;KJL_CMatrix KJL_CMatrix:operator-(const KJL_CMatrix& m)/减号函数重载if(_row!=m._row|_column!=m._column)cerr矩阵不能相减！endl;int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)_Aij=_Aij-m._Aij;return *this;KJL_CMatrix KJL_CMatrix:operator*(const KJL_CMatrix& m)/乘号符号函数重载KJL_CMatrix temp(_row,m._column);if(_column!=m._row)cerr矩阵不能相乘！endl;int i,j,n;for(i=0;i_row;i+)for(j=0;j_row;j+)for(n=0;n_column;n+)temp._Aij+=_Ain*m._Anj;return temp;bool KJL_CMatrix:operator =(const KJL_CMatrix& m)/=函数重载if(_row!=m._row|_column!=m._column)return false;int i,j;for(i=0;i_row;i+)for(j=0;j_column;j+)if(_Aij!=m._Aij)return false;return true;bool KJL_CMatrix:operator !=(const KJL_CMatrix& m)/!=函数重载if(_row!=m._row|_column!=m._column)return true;int i,j;for(i=0;i_row;i+)for(j=0;j_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 KJL_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;KJL_CMatrix KJL_CMatrix:bansui()/求伴随矩阵KJL_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;KJL_CMatrix KJL_CMatrix:inverse()/矩阵求逆KJL_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;KJL_CMatrix & KJL_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 KJL_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;KJL_CMatrix KJL_CMatrix:inv()/矩阵求逆，通过行列变换int i,j,m;KJL_CMatrix E1;E1=*this;if(this-_row!=this-_column)cerr该矩阵不能求逆endl;elseif(E1.hanglieshi()=0)cerr该矩阵不可逆：endl;else/把矩阵E赋值成单位阵KJL_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