中国矿业大学测绘软件实习报告.docx
《中国矿业大学测绘软件实习报告.docx》由会员分享，可在线阅读，更多相关《中国矿业大学测绘软件实习报告.docx（44页珍藏版）》请在冰点文库上搜索。
中国矿业大学测绘软件实习报告
中国矿业大学
测绘软件设计与实现
实验报告
学 号：
姓 名：
班 级：
指导教师：
王永波
实验一二叉树的构建及其遍历算法的实现
实验目的：
完成二叉树的构建以及二叉树的遍历等，加深对树以及二叉树的遍历相关知识的理解。
实验内容：
1.二叉树类的定义及建立。
2.二叉树的前序、中序、后序遍历。
主要代码：
template
classC_LJH_BinTree
{
public:
C_LJH_BinTree（）;//构造函数，根据输入前序序列由键盘输入
~C_LJH_BinTree（）;//析构函数
voidPreOrder（）;//前序遍历
voidInOrder（）;//中序遍历
voidPostOrder（）;//后序遍历
private:
Tdata;
C_LJH_BinTree*lchild,*rchild;
boolNO_Die;
};
template
C_LJH_BinTree:
:
C_LJH_BinTree（）
{
NO_Die=false;
lchild=NULL;
rchild=NULL;
charch;
cin>>ch;
if（ch=='#'）
{
NO_Die=true;//若为#，代表空节点
}
else
{
this->data=ch;//保存输入的节点
//左子树
C_LJH_BinTree*newChild0=newC_LJH_BinTree（）;
if（newChild0->NO_Die）
deletenewChild0;
else
this->lchild=newChild0;
//右子树
C_LJH_BinTree*newChild1=newC_LJH_BinTree（）;//直接创建子节点，
if（newChild1->NO_Die）
deletenewChild1;
else
this->rchild=newChild1;
}
}
//析构函数
template
C_LJH_BinTree:
:
~C_LJH_BinTree（）
{
if（lchild）deletelchild;//删除父节点之前，先删除子节点
if（rchild）deleterchild;
}
//前序遍历
template
voidC_LJH_BinTree:
:
PreOrder（）
{
cout<data<<"\t";//先输出父节点，然后子节点按照父节点做
if（lchild!
=NULL）
this->lchild->PreOrder（）;
if（rchild!
=NULL）
this->rchild->PreOrder（）;
}
//中序遍历
template
voidC_LJH_BinTree:
:
InOrder（）
{
if（lchild）lchild->InOrder（）;
cout<data<<"\t";
if（rchild）rchild->InOrder（）;
}
//后序遍历
template
voidC_LJH_BinTree:
:
PostOrder（）
{
if（lchild）lchild->PostOrder（）;
if（rchild）rchild->PostOrder（）;
cout<data<<"\t";
}
intmain（）
{
cout<<"请输入二叉树的前序遍历：
"<cout<<"（以#作为分支结尾，例如：
AB##C##）"<C_LJH_BinTreem_tree;
cout<cout<<"前序遍历为：
"<m_tree.PreOrder（）;
cout<cout<<"中序遍历为：
"<m_tree.InOrder（）;
cout<cout<<"后序遍历为：
"<m_tree.PostOrder（）;
cout<return0;
}
实验结果：
实验体会：
通过本次试验，理解了二叉树类的构建、二叉树的建立及其遍历。
作为第一次实验，内容上实现实验所要求的目没有多大的难处，但其从数据结构出发，让我回忆起很多以前学过的知识，对我来说，收获不少。
实验二图的创建、遍历及其MST的构建
实验目的：
完成图的创建、遍历及最小数的构建，加深对图的认识以及对相关课本知识的认识。
实验内容：
1.图的创建。
2.基于深度优先的图的遍历算法的设计与实现。
3.基于广度优先的图的遍历算法的设计与实现。
4.基于Prim算法的最小生成树的构建。
5.基于Kruskal算法的最小生成树的构建。
主要代码：
structprimnode
{public:
charbegvex;//开始结点
charendvex;//结束结点
intlowcost;//中间权值};
classLJH_Graphmtx//图的邻接矩阵定义
{public:
LJH_Graphmtx（intsz=DefaultVertices）;//构造函数
~LJH_Graphmtx（）//析构函数
{delete[]VerticesList;delete[]Edge;}
boolGraphEmpty（）//判断图是否为空
{if（numEdges==0）returntrue;
elsereturnfalse;}
boolGraphFull（）//判断图是否为满
{if（numVertices==maxVertices||numEdges==maxVertices*（maxVertices-1）/2）
returntrue;
else
returnfalse;}
intNumberOfVertices（）//返回当前顶点数
{returnnumVertices;}
intNumberOfEdges（）//返回当前边数
{returnnumEdges;}
chargetValue（inti）//取顶点i的值，i不合理返回0
{returni>=0&&i<=numVertices?
VerticesList[i]:
NULL;}
intgetWeight（intv1,intv2）//取边（v1,v2）上的权值
{returnv1!
=-1&&v2!
=-1?
Edge[v1][v2]:
0;}
intgetFirstNeighbor（intv）;//取顶点v的第一个邻接顶点
intgetNextNeighbor（intv,intw）;//取v的邻接顶点w的下一邻接顶点
boolinsertVertex（charvertex）;//插入顶点vertex
boolinsertEdge（intv1,intv2,intweight）;//插入边（v1,v2）,权为weight
boolremoveVertex（intv）;//删去顶点v和所有与它相关联的边
boolremoveEdge（intv1,intv2）;//在图中删去边（v1,v2）
intgetVertexPos（charvertex）//给出顶点vertex的位置,如果该顶点不在图内则返回-1
{for（inti=0;iif（VerticesList[i]==vertex）returni;
return-1;}
intmini（）;//求图中所有边的最小权值
boolinput（）;//输入函数
booloutput（）;//输出函数
voidkruskal（）;//kruskal算法
voidprim（）;//prim算法
protected:
intmaxVertices;//图中最大顶点数
intnumEdges;//图中当前边数
intnumVertices;//图中当前顶点数
private:
char*VerticesList;//顶点表
int**Edge;//邻接矩阵
intvisit[50];//便利时的辅助工具
primnodecloseedge[50];//为实现prim函数的辅助结点};
LJH_Graphmtx:
:
LJH_Graphmtx（intsz）//构造函数
{maxVertices=sz;
numVertices=0;
numEdges=0;
inti,j;
VerticesList=newchar[maxVertices];//创建顶点表数组
Edge=（int**）newint*[maxVertices];//创建邻接矩阵数组
for（i=0;iEdge[i]=newint[maxVertices];
for（i=0;ifor（j=0;jEdge[i][j]=（i==j）?
0:
maxWeight;}
intLJH_Graphmtx:
:
getFirstNeighbor（intv）{if（v!
=-1）
{for（inti=0;iif（Edge[v][i]>0&&Edge[v][i]return-1;}
intLJH_Graphmtx:
:
getNextNeighbor（intv,intw）//给出顶点v的某邻接顶点w的下一个邻接顶点的位置，如果找不到，则函数返回-1
{if（v!
=-1&&w!
=-1）
{for（inti=w+1;iif（Edge[v][i]>0&&Edge[v][i]return-1;}
boolLJH_Graphmtx:
:
insertVertex（charvertex）//插入顶点vertex
{if（numVertices==maxVertices）returnfalse;//顶点表满，不插入
VerticesList[numVertices++]=vertex;
returntrue;}
boolLJH_Graphmtx:
:
insertEdge（intv1,intv2,intweight）//插入边（v1,v2）,权为weight
{if（v1!
=-1&&v1=-1&&v2?
?
）
{Edge[v1][v2]=Edge[v2][v1]=weight;
numEdges++;
returntrue;}
else
returnfalse;}
boolLJH_Graphmtx:
:
removeVertex（intv）//删去顶点v和所有与它相关联的边
{if（v<0&&v>=numVertices）returnfalse;//v不在图中，不删除
inti,j;
VerticesList[v]=VerticesList[numVertices-1];//顶点表中删除该结点
for（i=0;iif（Edge[i][v]>0&&Edge[i][v]for（i=0;iEdge[i][v]=Edge[i][numVertices-1];
numVertices--;//顶点个数减1
for（j=0;jEdge[v][j]=Edge[numVertices-1][j];
returntrue;}
boolLJH_Graphmtx:
:
removeEdge（intv1,intv2）//在图中删去边（v1,v2）
{if（v1>-1&&v1-1&&v20&&Edge[v1][v2]{Edge[v1][v2]=Edge[v2][v1]=maxWeight;//删除边（v1,v2）
numEdges--;
returntrue;}
else
returnfalse;}
boolLJH_Graphmtx:
:
input（）
{inti,j,k,n,m;
chare1,e2;
intweight;
cout<<"请输入顶点数和边数:
"<cin>>n>>m;//输入顶点数n和边数m
cout<<"请输入顶点的值：
"<for（i=0;i{cin>>e1;
this->insertVertex（e1）;}
i=0;
while（i{cout<<"请输入端点信息:
"<cin>>e1>>e2>>weight;//输入端点信息
j=this->getVertexPos（e1）;//查顶点号
k=this->getVertexPos（e2）;
if（j==-1||k==-1）
cout<<"边两端点信息输入有误，请重新输入！
"<else
{this->insertEdge（j,k,weight）;
i++;}}
returntrue;}
boolLJH_Graphmtx:
:
output（）//输出函数
{inti,j,n,m;
chare1,e2;
intw;
n=this->NumberOfVertices（）;
m=this->NumberOfEdges（）;
cout<<"顶点的个数为：
"<cout<<"边的条数为：
"<cout<<"所有边的信息为：
"<for（i=0;ifor（j=i+1;j{w=this->getWeight（i,j）;
if（w>0&&w{e1=this->getValue（i）;
e2=this->getValue（j）;cout<<"（"<returntrue;}
intLJH_Graphmtx:
:
mini（）//求图中所有边的最小权值，并返回
{staticinti;
intmin=0;
for（intj=0;j{if（!
visit[j]）
{if（closeedge[min].lowcost>closeedge[j].lowcost）
{min=j;}}}
i=min;
cout<<"包括边（"<returni;}
//图的深度优先搜索函数////////
voidDFS（LJH_Graphmtx&G,intv,boolvisited[]）;//先声明函数，后使用
voidDFS（LJH_Graphmtx&G,char&v）//从顶点v出发，对图G进行深度优先遍历的主要过程
{inti,loc,n=G.NumberOfVertices（）;//取图中顶点的个数
bool*visited=newbool[n];//创建辅助数组
for（i=0;i{visited[i]=0;}
loc=G.getVertexPos（v）;//取得v结点在图中的位置
DFS（G,loc,visited）;//从顶点0开始深度优先搜索
delete[]visited;}
voidDFS（LJH_Graphmtx&G,intv,boolvisited[]）
{cout<visited[v]=1;//顶点v作访问标记
intw=G.getFirstNeighbor（v）;//找v的第一个邻接顶点w
while（w!
=-1）//若邻接顶点w存在
{if（visited[w]==0）
DFS（G,w,visited）;//若w未被访问，递归访问顶点w
w=G.getNextNeighbor（v,w）;//取v排在w后的下一个邻接顶点}}
//图的广度优先搜索函数////////
voidBFS（LJH_GraphmtxG,charv）//从顶点v出发，以广度优先的次序横向搜索图，算法中使用了一个队列。
{inti,w,n=G.NumberOfVertices（）;//去图中的定点个数
bool*visited=newbool[n];//用来记录顶点是否被访问过，被访问值为1，为被访问值为0
for（i=0;ivisited[i]=0;
intloc=G.getVertexPos（v）;//取顶点v的位置号
cout<visited[loc]=1;//做已访问标记
LJH_QueueQ;//定义一个辅助队列
Q.EnQueue（loc）;//顶点进队，实现分层访问
while（!
Q.IsEmpty（））//循环访问所有结点，判断队列是否为空
{Q.DeQueue（loc）;//从队列中退出顶点loc
w=G.getFirstNeighbor（loc）;//找顶点loc的第一个邻接点w
while（w!
=-1）//若邻接点w存在
{if（visited[w]==false）//若未被访问
{cout<visited[w]=1;//标记w已经被访问
Q.EnQueue（w）;//顶点w进队列w=G.getNextNeighbor（loc,w）;//找顶点loc的下一个邻接顶点，重复检测v的所有邻接顶点}}
delete[]visited;}
//////kruskal函数的实现//////
voidLJH_Graphmtx:
:
kruskal（）
{inta,b,k=0;
intmin=maxWeight;
intEdge1[20][20];
for（intm=0;mvisit[m]=m;//每一个顶点属于一颗树
for（inti=0;ifor（intj=0;jEdge1[i][j]=Edge[i][j];
while（k{min=maxWeight;
for（inti=0;i{for（intj=0;j{if（Edge1[i][j]{a=i;b=j;min=Edge1[i][j];}}}
if（visit[a]!
=visit[b]）
{cout<<"包括边（"<k++;
for（intn=0;n{if（visit[n]==visit[b]）visit[n]=visit[a];}}
elseEdge1[a][b]=Edge[b][a]=maxWeight;}
cout<////////////Prim函数的实现////
voidLJH_Graphmtx:
:
prim（）
{charu;
cout<<"请输入起始顶点：
"<>u;
inti=this->getVertexPos（u）;visit[i]=1;
for（intj=0;j{closeedge[j].begvex=u;
closeedge[j].endvex=VerticesList[j];
closeedge[j].lowcost=Edge[i][j];}
for（intm=1;m{intn=mini（）;visit[n]=1;closeedge[n].lowcost=maxWeight;
for（intp=0;p{if（!
visit[p]）
{if（Edge[p][n]{closeedge[p].lowcost=Edge[p][n];
closeedge[p].begvex=VerticesList[n];}}}}}
实验结果：
实验体会：
经过这次实验让我更深刻的理解了类的创建及相互间调用，能够对二维数组的动态开辟空间和释放空间有了更深刻的理解，对图的遍历及构建最小生成树也有了深刻的体会。
总之，在这次试验中，学到了许多，也提高了自己的编程能力。
实验三、矩阵类的设计与实现
实验目的：
通过上机实践，实现矩阵的生成、加减乘除运算，以及求矩阵的转置、求逆和行列式。
同时加深对矩阵的理论的理解，并用计算机程序算法来描述矩阵生成及运算。
实验内容：
通过构造矩阵类，实现矩阵的定义，包括：
矩阵的加
升级会员 