测绘软件实习报告.docx

测绘软件实习报告.docx

《测绘软件实习报告.docx》由会员分享，可在线阅读，更多相关《测绘软件实习报告.docx（61页珍藏版）》请在冰点文库上搜索。

测绘软件实习报告

测绘软件

设计与实现

2011年11月15日

实验一图的创建、遍历及其MST的构建

一、实验目的

通过上机实践，进一步了解图的创建、遍历及其MST的构建，巩固所学课本知识。

二、实验过程

#include

#include

#include

#defineINF32767

#defineMAXV100

typedefintInfoType;

typedefstruct

{

intno;

InfoTypeinfo;

}VertexType;

typedefstruct

{

intedges[MAXV][MAXV];

intn,e;

VertexTypevexs[MAXV];

}MGraph;

typedefstructANode

{

intadjvex;

structANode*nextarc;

InfoTypeinfo;

}ArcNode;

typedefintVertex;

typedefstructVnode

{

Vertexdata;

ArcNode*firstarc;

}VNode;

typedefVNodeAdjList[MAXV];

typedefstruct

{AdjListadjlist;

intn,e;

}ALGraph;

voidMatToList（MGraphg,ALGraph*&G）

{

inti,j,n=g.n;

ArcNode*p;

G=（ALGraph*）malloc（sizeof（ALGraph））;

for（i=0;i

G->adjlist[i].firstarc=NULL;

for（i=0;i

for（j=n-1;j>=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;

}

voidListToMat（ALGraph*G,MGraph&g）

{

inti,j,n=G->n;

ArcNode*p;

for（i=0;i

for（j=0;j

g.edges[i][j]=0;

for（i=0;i

{

p=G->adjlist[i].firstarc;

while（p!

=NULL）

{

g.edges[i][p->adjvex]=p->info;

p=p->nextarc;

}

}

g.n=n;

g.e=G->e;

}

voidDispMat（MGraphg）

{

inti,j;

intzz=99;

for（i=0;i

{

for（j=0;j

if（g.edges[i][j]==INF）

printf（"%3s",""）;

else

printf（"%3d",g.edges[i][j]）;

printf（"\n"）;

}

}voidDispAdj（ALGraph*G）

{

inti;

ArcNode*p;

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"）;

}

};

intvisited[MAXV];

voidDFS（ALGraph*G,intv）

{

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;

}

}

voidDFS1（ALGraph*G,intv）

{

ArcNode*p;

ArcNode*St[MAXV];

inttop=-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"）;

}

voidBFS（ALGraph*G,intv）

{

ArcNode*p;

intqueue[MAXV],front=0,rear=0;

intvisited[MAXV];

intw,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"）;

}

voidPrim（MGraphg,intv）

{

intlowcost[MAXV],min,n=g.n;

intclosest[MAXV],i,j,k;

for（i=0;i

{

lowcost[i]=g.edges[v][i];

closest[i]=v;

}

for（i=0;i

{

min=INF;

for（j=0;j

if（lowcost[j]!

=0&&lowcost[j]

{

min=lowcost[j];

k=j;

}

printf（"边（%d,%d）权为:

%d\n",closest[k],k,min）;

lowcost[k]=0;

for（j=0;j

if（g.edges[k][j]!

=0&&g.edges[k][j]

{

lowcost[j]=g.edges[k][j];

closest[j]=k;

}

}

}

/////////////////////////////////////typedefstruct

{

intu;

intv;

intw;

}Edge;

voidSortEdge（MGraphg,EdgeE[]）

{

inti,j,k=0;

Edgetemp;

for（i=0;i

for（j=0;j

if（g.edges[i][j]

{

E[k].u=i;

E[k].v=j;

E[k].w=g.edges[i][j];

k++;

}

for（i=0;i

{

temp=E[i];

j=i-1;

while（j>=0&&temp.w

{

E[j+1]=E[j];

j--;

}

E[+1]=temp;

}

}

voidKruskal（EdgeE[],intn,inte）

{

inti,j,m1,m2,sn1,sn2,k;

intvset[MAXV];

for（i=0;i

vset[i]=i;

k=1;

j=0;

while（k

{

m1=E[j].u;

m2=E[j].v;

sn1=vset[m1];

sn2=vset[m2];

if（sn1!

=sn2）

{

printf（"（%d,%d）:

%d\n",m1,m2,E[j].w）;

k++;

for（i=0;i

if（vset[i]==sn2）

vset[i]=sn1;

}

j++;

}

}

/////////////////////////////////////

voidmain（）

{

inti,j,u=3;

MGraphg,g1;

ALGraph*G;

EdgeE[MAXV];

intB[MAXV][11];

intA[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};

g.n=6;

g.e=10;

for（i=0;i

for（j=0;j

g.edges[i][j]=A[i][j];

printf（"\n"）;

printf（"图G的邻接表：

\n"）;

MatToList（g,G）;

DispAdj（G）;

printf（"图G的邻接表转换成邻接矩阵\n"）;

ListToMat（G,g1）;

DispMat（g1）;

printf（"从顶点0开始的DFS（递归算法）:

\n"）;

DFS（G,0）;

printf（"\n"）;

printf（"从顶点0开始的DFS（非递归算法）:

\n"）;

DFS1（G,0）;

printf（"从顶点0开始的BFS（递归算法）:

\n"）;

BFS（G,0）;

printf（"\n"）;

for（i=0;i

for（j=0;j

B[i][j]=INF;

B[0][1]=1;

B[0][2]=4;

B[0][3]=12;

B[0][5]=2;

B[1][2]=8;

B[2][3]=5;

B[2][5]=9;

B[3][4]=3;

B[4][5]=7;

for（i=0;i

for（j=0;j

A[j][i]=A[i][j];

for（i=0;i

for（j=0;j

g.edges[i][j]=B[i][j];

printf（"\n"）;

printf（"\n"）;

printf（"普里姆算法求解结果:

\n"）;

Prim（g,0）;

printf（"\n"）;

SortEdge（g,E）;

printf（"\n"）;

printf（"\n"）;

printf（"克鲁斯卡尔算法求解结果:

\n"）;

Kruskal（E,g.n,g.e）;

printf（"\n"）;

}

三、实验成果

四、实验体会

通过此次上机实践，基本上掌握了图的创建过程，对于程序设计，在设计过程中遇到很多问题，但是通过相互讨论及老师指导，已经基本掌握了基于深度优先的图的遍历算法的设计与实现、基于广度优先的图的遍历算法的设计与实现、基于Prim算法的最小生成树的构建、基于Kruskal算法的最小生成树的构建。

实验二快速排序算法的实现

一、实验目的

通过上机实践巩固课堂所学快速排序算法相关知识，通过讨论，同学之间相互学习，彻底了解实验内容，完成实验作业。

二、实验过程

#include

voidXXXquicksort（intdata[],intlow,inthigh）

{

inti,pivot,j;

if（low

{

pivot=data[low];

i=low;

j=high;

while（i

{

while（i=pivot）

j--;

if（i

data[i++]=data[j];

while（i

i++;

if（i

data[j--]=data[i];

}

data[i]=pivot;

XXXquicksort（data,low,i-1）;

XXXquicksort（data,i+1,high）;

}

}

voidmain（）

{

inta[6];

inti;

cout<<"请输入待排序数组"<

for（i=0;i<6;i++）

{

cin>>a[i];

}

cout<

cout<<"由输入得结果为：

"<

for（i=0;i<6;i++）

{

cout<

}

cout<

XXXquicksort（a,0,5）;

cout<<"快速排序后的结果为：

"<

for（i=0;i<6;i++）

{

cout<

}

cout<

}

三、实验成果

四、实验体会

此次上机实践主要是实现快速排序算法，这个实验相对于其他实验，比较简单，做起来问题不是很多，经过几次调试，基本上就能完成。

实验三矩阵类的设计与实现

一、实验目的

通过上机实践，巩固课堂老师所讲关于矩阵设计的知识，通过反复的调试，找错，设计出矩阵。

二、实验过程

#include

#include

#include

#include

classXXXMatrix

{

private:

introws,columns;

double**element;

public:

XXXMatrix（introws=4,intcolumns=4）;

XXXMatrix（int*mat,introws,intcolumns）;

XXXMatrix（constXXXMatrix&m）;

~XXXMatrix（）;

intrintv（intn,doublea[][4]）;

XXXMatrix&inverse（XXXMatrix&mat）;

XXXMatrix&transpose（doublea[][4]）;

voidinit（introws,intcolumns）;

doubleget（inti,intj）;

boolset（inti,intj,intvalue）;

friendostream&operator<<（ostream&out,XXXMatrix&mat）;

XXXMatrix&operator+=（XXXMatrix&mat）;

XXXMatrix&operator=（constXXXMatrix&mat）;

booloperator==（constXXXMatrix&mat）;

booloperator!

=（constXXXMatrix&mat）;

XXXMatrix&operator-（XXXMatrix&mat）;

XXXMatrix&operator-（）;

XXXMatrix&operator*（XXXMatrix&mat）;

};

voidXXXMatrix:

:

init（introws,intcolumns）

{

if（rows<=0||columns<=0）

throw"矩阵行或列数非正数异常";

this->rows=rows;

this->columns=columns;

element=newdouble*[rows];

for（inti=0;i

{

element[i]=newdouble[columns];

for（intj=0;j

element[i][j]=0;

}

}

XXXMatrix:

:

XXXMatrix（introws,intcolumns）

{

init（rows,columns）;

}

XXXMatrix:

:

XXXMatrix（int*mat,introws,intcolumns）

{

init（rows,columns）;

for（inti=0;i

for（intj=0;j

element[i][j]=*（mat+i*columns+j）;

}

XXXMatrix:

:

XXXMatrix（constXXXMatrix&m）

{

init（m.rows,m.columns）;

for（inti=0;i

for（intj;j

element[i][j]=m.element[i][j];

}

XXXMatrix:

:

~XXXMatrix（）

{

for（inti=0;i

delete（element[i]）;

delete（element）;

}

doubleXXXMatrix:

:

get（inti,intj）

{

if（i>=0&&i=0&&j

returnelement[i][j];

}

boolXXXMatrix:

:

set（inti,intj,intvalue）

{

if（i>=0&&i=0&&j

{

element[i][j]=value;

returntrue;

}

returnfalse;

}

ostream&operator<<（ostream&out,XXXMatrix&mat）

{

out<<"矩阵XXXMatrix（"<

for（inti=0;i

{

for（intj=0;j

out<

out<<"\n";

}

returnout;

}

XXXMatrix&XXXMatrix:

:

operator=（constXXXMatrix&mat）

{

if（this->rows==mat.rows&&this->columns==mat.columns）

{

for（inti=0;i

for（intj=0;j

element[i][j]=mat.element[i][j];

return*this;

}

throw"两个矩阵阶数不同，不能相加";

}

boolXXXMatrix:

:

operator==（constXXXMatrix&mat）

{

if（this->rows==mat.rows&&this->columns==mat.columns）

{

for（inti=0;i

{

for（intj=0;j

if（this->element[i][j]!

=mat.element[i][j]）

{

break;

returnfalse;

}

else

returntrue;

}

}

}

boolXXXMatrix:

:

operator!

=（constXXXMatrix&mat）

{if（this->rows==mat.rows&&this->columns==mat.columns）

{

for（inti=0;i

{

for（intj=0;j

if（this->element[i][j]==mat.element[i][j]）

{

break;

returnfalse;

}

else

returntrue;

}

}

}

XXXMatrix&XXXMatrix:

:

operator-（XXXMatrix&mat）

{

if（this->rows==mat.rows&&this->columns==mat.columns）

{

for（inti=0;i