测绘软件实习报告.doc

测 绘 软 件 设 计 与 实 现2011年11月15日目录实验一 图的创建、遍历及其MST的构建 3实验二 快速排序算法的实现 8实验三 矩阵类的设计与实现 10实验四 Windows绘图 15实验五 面向对象的高程网平差程序设计与实现 19实验一 图的创建、遍历及其MST的构建一、实验目的通过上机实践，进一步了解图的创建、遍历及其MST的构建，巩固所学课本知识二、实验过程#include#include#include#define INF 32767#define MAXV 100typedef int InfoType;typedef struct{ int no; InfoType info;}VertexType;typedef struct{ int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV];}MGraph;typedef struct ANode{ int adjvex; struct ANode *nextarc; InfoType info;}ArcNode;typedef int Vertex;typedef struct Vnode{ Vertex data; ArcNode *firstarc;}VNode;typedef VNode AdjList[MAXV];typedef struct{ AdjList adjlist; int n,e;}ALGraph;void MatToList(MGraph g,ALGraph *&G){ int i,j,n=g.n; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); for(i=0;iadjlist[i].firstarc=NULL; for(i=0;i=0;j--) if(g.edges[i][j]!=0) { p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; } G->n=n; G->e=g.e;}void ListToMat(ALGraph *G,MGraph &g){ int i,j,n=G->n; ArcNode *p; for(i=0;iadjlist[i].firstarc; while(p!=NULL) { g.edges[i][p->adjvex]=p->info; p=p->nextarc; } } g.n=n; g.e=G->e;}void DispMat(MGraph g){ int i,j; int zz=99; for(i=0;in;i++) { p=G->adjlist[i].firstarc; if(p!=NULL) printf("%3d",i); while(p!=NULL) { printf("%3d",p->adjvex); p=p->nextarc; } printf("\n"); }};int visited[MAXV];void DFS(ALGraph *G,int v){ ArcNode *p; visited[v]=1; printf("%3d",v); p=G->adjlist[v].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) DFS(G,p->adjvex); p=p->nextarc; }}void DFS1(ALGraph *G,int v){ ArcNode *p; ArcNode *St[MAXV]; int top=-1,w,i; for(i=0;in;i++) visited[i]=0; printf("%3d",v); visited[v]=1; top++; St[top]=G->adjlist[v].firstarc; while(top>-1) { p=St[top]; top--; while(p!=NULL) { w=p->adjvex; if(visited[w]==0) { printf("%3d",w); visited[w]=1; top++; St[top]=G->adjlist[w].firstarc; break; } p=p->nextarc; } } printf("\n");}void BFS(ALGraph *G,int v){ ArcNode *p; int queue[MAXV],front=0,rear=0; int visited[MAXV]; int w,i; for(i=0;in;i++) visited[i]=0; printf("%3d",v); visited[v]=1; rear=(rear+1)%MAXV; queue[rear]=v; while(front!=rear) { front=(front+1)%MAXV; w=queue[front]; p=G->adjlist[w].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) { printf("%3d",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc; } } printf("\n");}void Prim(MGraph g,int v){ int lowcost[MAXV],min,n=g.n; int closest[MAXV],i,j,k; for(i=0;i=0&&temp.w