锐客网

  1. 首页 > 生活百科 > it技术 > >

数据结构与算法第四次实验报告图

IT知识算法数据结构实验报告

花门楼前见秋草，岂能贫贱相看老。这篇文章主要讲述数据结构与算法第四次实验报告图相关的知识，希望能为你提供帮助。


数据结构与算法
第四次实验报告






姓名：许恺
学号：2014011329
班级：计算机14-1
















中国石油大学(北京)计算机科学与技术系










1、图的定义，文件为"Graph.h"
#ifndef GRAPH_H//定义头文件
#define GRAPH_H
#include< string> //引入标准库中的头文件
using namespace std;
const int MaxSize=12;
struct ArcNode//定义边表结点

int adjvex; //邻接点域
ArcNode *next; //指向下一个边结点的指针
;
template < class T>
struct VertexNode//定义顶点表结点

T vertex; //顶点的名称
ArcNode *firstedge; //边表的头指针
;
template < class T>
class Graph

public:
//*****************************邻接矩阵函数***********************************//
Graph(int* a, T* v,int n ); //构造函数，初始化具有n个顶点的图
~Graph( ); //析构函数
void Dijkstra( int v,int endv); //最小距离
void Floyd();
void PutOutVexInfo(); //取顶点信息
void PutOutArcInfo(); //输出路径
void SetArc(int v1,int v2,int arclength); //修改路径
void DeleteVex(int pos); //删除顶点pos的信息
void InsertVex(int num,T name); //在num的位置上插入一顶点，值为name
void DeleteArc(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j
void InsertArc(int i, int j,int n); //在图中插入一条边，其依附的两个顶点的编号为i和j
//*****************************邻接表函数************************************//
Graph(T a[ ], int n, int e); //构造函数，初始化具有n个顶点的图
T GetVex_L(int i); //取图中第i个顶点数据信息
void PutVex_L(int i, T value); //将图中第i个顶点的数据域置为value
void InsertVex_L(int i, T value); //在图中插入一个顶点，其编号为i，值为value
void DeleteVex_L(int i); //删除图中第i个顶点
void InsertArc_L(int i, int j); //在图中插入一条边，其依附的两个顶点的编号为i和j
void DeleteArc_L(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j
void DFSTraverse_L(int v); //深度优先遍历图
void BFSTraverse_L(int v); //广度优先遍历图
private:
int vertexNum,arcNum; //图的顶点数和边数
//*****************************邻接矩阵************************************//
T vertex[MaxSize]; //存放图中顶点的数组
int arc[MaxSize][MaxSize]; //存放图中边的数组
//*****************************邻接表************************************//
VertexNode< T> adjlist[MaxSize];
;
#endif
2、图的实现函数，文件为“Graph.cpp”
#include< iostream>
#include < string> //引入标准库中的头文件
#include "Graph.h" //引入头文件
using namespace std;
//****************************邻接矩阵图操作**********************************//
/*
前置条件：图不存在
输入：无
功能：图的初始化
输出：无
后置条件：构造一个有值的图
*/
template < class T>
Graph< T> ::Graph(int* a,T* v, int n )//构造图

int i,j;
vertexNum=n; //顶点数
for (i=0; i< MaxSize; i++)//初始化邻接矩阵
for (j=0; j< MaxSize; j++)//定义边
arc[i][j] = 10000;
for ( i=0; i< vertexNum; i++)
vertex[i]=v[i]; //存储顶点信息
for (i=0; i< vertexNum; i++)//给边赋置
for (j=0; j< vertexNum; j++)
arc[i][j]=*(a+i*n+j);

/*
前置条件：图已存在
输入：无
功能：输出图中所有顶点的数据信息
输出：图中所有顶点的数据信息
后置条件：图保持不变
*/
template < class T>
void Graph< T> ::PutOutVexInfo()//取顶点

int i=0; //假设源点是第0个顶点，即顶点序号是0
if (i> vertexNum) throw "位置"; //错误抛出异常
else

for(i=0; i< vertexNum; i++)//输出图中所有的顶点

cout< < vertex[i]< < "\\n";



/* 前置条件：图已存在
输入：顶点v1,v2
功能：修改顶点v1、v2的路径
输出：修改后图中所有的路径
后置条件：图保持不变
*/
template < class T>
void Graph< T> ::SetArc(int v1,int v2,int arclength)//修改路径
//假设源点是第0个顶点，即顶点序号是0
if ( v1> vertexNum|| v2> vertexNum) throw "位置"; //错误抛出异常
else

arc[v1][v2]=arclength; //修改v1顶点到v2顶点的距离
arc[v2][v1]=arclength;


/*
前置条件：图已存在
输入：无
功能：输出图中所有的路径
输出：图中所有顶点的数据信息
后置条件：图保持不变
*/
template < class T>
void Graph< T> ::PutOutArcInfo()//输出图中所有的路径

int i=0; //假设源点是第0个顶点，即顶点序号是0
int j=0;
if ( i> vertexNum|| j> vertexNum) throw "位置"; //错误抛出异常
else

for(i=0; i< vertexNum; i++)
//输出任意两点之间的路径
for(j=0; j< i; j++)

if(arc[i][j]< 10000)//两点之间存在路径
//若两点间有路，则输出该两点间的路径
cout< < "从"< < vertex[i]< < "到"< < vertex[j]< < "的路径长度为："< < arc[i][j]< < "\\n";




/*
前置条件：图已存在
输入：顶点name,位置i
功能：在图中i位置插入一个顶点name
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，图中增加了一个顶点
*/
template < class T>
void Graph< T> ::InsertVex(int num,T name)//在图中插入一个顶点，其编号为i，值为value
//假设源点是第0个顶点，即顶点序号是0
if ( num< 0|| num> vertexNum) throw "位置"; //如果num输入不正确抛出异常
int row; //行
int col; //列
int numv; //最后一个顶点所在的位置
numv = vertexNum-1;
if(num> -1)//num存在
vertexNum++; //顶点数加1
for(int i=numv; i> num-1; i--)//i从最后一个顶点的下一个位置开始循环
vertex[i]=vertex[i-1]; //把从num位置的顶点到最后一个顶点均向后移一位
vertex[num]=name; //把要插入的顶点的值放在num位置上
for(row=numv; row> =0; row--)//把从num列到最后一列的元素均向下移一列

for(col=numv; col> =num; col--)
arc[row][col+1]=arc[row][col];
arc[row][num]=10000;

for(row=numv; row> =num; row--)//把从num行到最后一行的元素均向下移一行
for(col=0; col< =numv+1; col++)
arc[row+1][col]=arc[row][col];
for(col=0; col< vertexNum; col++)
arc[num][col]=10000; //把num位置所在的行、列的值均置为无穷大

/*
前置条件：图已存在
输入：顶点pos
功能：在图中删除顶点pos
输出：如果删除不成功，抛出异常
后置条件：如果删除成功，图中减少了一个顶点,相应顶点所建立的边也消去
*/
template < class T>
void Graph< T> ::DeleteVex(int pos)//删除第pos个顶点
//假设源点是第0个顶点，即顶点序号是0
if ( pos< 0|| pos> MaxSize) throw "位置"; //如果pos输入不正确抛出异常
int row; //行
int col; //列
int numv=vertexNum; //numv等于顶点数
if(pos> -1)//pos存在

for(int i=pos; i< numv-1; i++)
vertex[i]=vertex[i+1]; //把从pos到最后的每个点的位置依次向前移一位
vertexNum--; //顶点数减1
for(row=0; row< numv; row++)

for(col=pos; col< numv; col++)
arc[row][col]=arc[row][col+1]; //从pos列到最后一列的元素均向前移一列
arc[row][numv-1]=10000; //把pos所在的列上的值置为无穷大

for(row=pos; row< numv; row++)
for(col=0; col< numv; col++)
arc[row][col]=arc[row+1][col]; //从pos行到最后一行的元素均向上移一行


/*
前置条件：图已存在
输入：顶点v ，endv
功能：假如endv存在，求v到endv的最短路径；假如不输入endv，则求v到任意顶点的最短路径
输出：所求得的最短路径及所经历的位置
后置条件：图保持不变
*/
template < class T>
void Graph< T> ::Dijkstra(int v,int endv)//求最短路径，从v顶点到endv点的最短路径

if ( v> vertexNum) throw "位置"; //v顶点或endv顶点输出不正确则抛出异常
int numv=vertexNum; //顶点数
int dist[MaxSize]; //最短长度
int path[MaxSize]; //当前找到的最短路径
int s[MaxSize]; //存放源点和已生成的终点的集合
int max= 10000; //代表无穷大
int i,j,k,wm;
for(i=0; i< numv; i++)//按网的邻接矩阵确定各顶点最短路径的初值

dist[i]=arc[v][i];
if(i!=v& & dist[i]< max)//如果v、i之间有路
path[i]=v; //当前找到的最短路径为v
else
path[i]=-1; //否则v与i顶点不存在路径
s[i] = 0; //给s集合确定初值0

s[v]=1; dist[v]=0; //将顶点v本身排除在外
for(k =0; k< numv-1; k++)//求其他numv-1各顶点的最短路径

wm = max; j=v; //确定当前最短路径wm及顶点的序号j
for( i=0; i< numv; i++)

if(!s[i]& & dist[i]< wm)//如果v、i之间有路

j=i;
wm = dist[i]; //把当前找到的路径确定为最大值


s[j]=1;
for(i =0; i< numv; i++)//更新未确定最短路径各顶点的当前最短路径

//如果v、i两点的距离加上i、j小于从v点到j点的距离
if(!s[i]& & dist[j]+arc[j][i]< dist[i])

dist[i]=dist[j]+arc[j][i]; path[i]=j; //dist[i]取最小值



if (endv < numv & & endv > =0 )//endv点存在

string mmm=""; //初始化字符串
int j =endv;
while(j > -1 )

string nnn = vertex[j]; //依次把顶点存放在nnn字符串中
nnn+=mmm;
mmm = " "+nnn;
j = path[j];

//输出从v点到endv点的最短路径
cout< < "从 "< < vertex[v].c_str()< < " 到 "
< < vertex[endv].c_str()< < " 的最短路径长度："
< < dist[endv]< < " 路径："< < mmm.c_str()< < "\\n";

else//endv点不存在
for(i=0; i< numv; i++)

string mmm=""; //初始化字符串
int j =i;
while(j > -1 )
【数据结构与算法第四次实验报告图】
string nnn = vertex[j]; //依次把顶点存放在nnn字符串中
nnn+=mmm;
mmm = " "+nnn;
j = path[j];

cout< < "从 "< < vertex[v].c_str()< < " 到 "
< < vertex[i].c_str()< < " 的最短路径长度："< < dist[i]< < " 路径："
< < mmm.c_str()< < "\\n"; //输出从v点到任意点的最短路径


/*
前置条件：图已存在
输入：顶点n、w
功能：在图中删除顶点n、w 依附的边
输出：如果删除不成功，抛出异常
后置条件：如果删除成功，图中减少了一条边
*/
template < class T>
void Graph< T> ::DeleteArc(int n, int w)//删除i、j两顶点依附的边

if ( n> MaxSize|| w> MaxSize) throw "位置"; //如果输入不正确抛出异常
arc[n][w]=arc[w][n]=10000; //删除w顶点和n顶点之间的路径

/* 前置条件：图已存在
输入：顶点i、j
功能：在图中插入顶点i、j及其所依附的边
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，图中增加了一条边
*/
template < class T>
void Graph< T> ::InsertArc(int i, int j,int n)//在图中插入一条边，其依附的两个顶点的编号为i和j

if ( i> MaxSize||j> MaxSize) throw "位置"; //如果输入不正确抛出异常
arc[i][j]=n;
arc[j][i]=n;
//输出所插入的两个顶点之间的距离
cout< < "从"< < vertex[i]< < "到"< < vertex[j]< < "的路径长度为："< < arc[i][j]< < "\\n";

/* 前置条件：图已存在
输入：顶点i、j
功能：在图中插入顶点i、j及其所依附的边
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，图中增加了一条边
*/
template < class T>
void Graph< T> ::Floyd()

int i,j,k;
int dist[8][8];
string path[8][8];
for (i=0; i< vertexNum; i++)
for (j=0; j< vertexNum; j++)

dist[i][j]=arc[i][j];
if (dist[i][j]!=10000)
path[i][j]=vertex[i]+vertex[j];
else path[i][j]="";

for (k=0; k< vertexNum; k++)
for (i=0; i< vertexNum; i++)
for (j=0; j< vertexNum; j++)
if (dist[i][k]+dist[k][j]< dist[i][j])

dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=path[i][k]+path[k][j];

for(i=0; i< 8; i++)
for(j=0; j< 8; j++)
cout< < "从 "< < vertex[i].c_str()< < " 到 "< < vertex[j].c_str()< < " 的最短路径长度："< < dist[i][j]< < " 路径："< < path[i][j]< < "\\n";
//输出从v点到任意点的最短路径

//****************************邻接表图操作************************************//
/*
*前置条件：图不存在
*输 入：无
*功 能：图的初始化
*输 出：无
*后置条件：得到一个有向图
*/
template < class T>
Graph< T> ::Graph(T a[ ], int n, int e)

arcNum = e; //边数
vertexNum=n; //顶点数
int i,j;
for (i=0; i< vertexNum; i++)

VertexNode< T> tempvertex;
tempvertex.vertex = a[i];
tempvertex.firstedge = NULL;
adjlist[i] = tempvertex;

for (int k=0; k< arcNum; k++)//依次输入每一条边，并在相应边表中插入结点

cout< < "请输入边所依附的两个顶点的序号";
cin> > i> > j; //输入边所依附的两个顶点的序号
ArcNode *s=new ArcNode; s-> adjvex=j; //生成一个边表结点s
s-> next=adjlist[i].firstedge; //将结点s插入到结点i的边表的表头
adjlist[i].firstedge=s;

InsertArc_L(0,1); //插入边
InsertArc_L(0,2);
InsertArc_L(0,3);
InsertArc_L(1,3);
InsertArc_L(1,4);
InsertArc_L(2,0);
InsertArc_L(2,4);
InsertArc_L(3,1);
InsertArc_L(3,4);
InsertArc_L(4,2);
InsertArc_L(4,3);

/* 前置条件：图已存在
* 输 入：无
* 功 能：销毁图
* 输 出：无
* 后置条件：释放图所占用的存储空间
*/
template < class T>
Graph< T> ::~Graph( )

for (int i=0; i< vertexNum; i++)

ArcNode * p=adjlist[i].firstedge;
while (p!=NULL)//循环删除

adjlist[i].firstedge=p-> next;
delete p; //释放结点空间
p=adjlist[i].firstedge;



/*
*前置条件：图已存在
*输 入：顶点i
*功 能：输出图中顶点i的数据信息
*输 出：图中顶点i的数据信息
*后置条件：图保持不变
*/
template < class T>
T Graph< T> ::GetVex_L(int i)

if ( i> vertexNum || i< 0 ) throw "输入顶点的位置不正确"; //顶点i不存在则抛出异常
return adjlist[i].vertex; //返回第i个顶点的数据域

/*
*前置条件：图已存在
*输 入：顶点i
*功 能：将图中顶点i的数据域置为value
*输 出：无
*后置条件：图保持不变
*/
template < class T>
void Graph< T> ::PutVex_L(int i, T value)

if ( i> vertexNum || i< 0 ) throw "输入顶点的位置不正确"; //顶点i不存在则抛出异常
adjlist[i].vertex = value; //第i个顶点的数据域置为value

/*
*前置条件：图已存在
*输 入：顶点value,位置i
*功 能：在图中i位置插入一个顶点name
*输 出：如果插入不成功，抛出异常
*后置条件：如果插入成功，图中增加了一个顶点
*/
template < class T>
void Graph< T> ::InsertVex_L(int i, T value)

if ( i> vertexNum || i< 0 || i> MaxSize ) throw "输入顶点的位置不正确"; //顶点i不存在则抛出异常
vertexNum++; //顶点数加1
VertexNode< T> tempvertex;
tempvertex.vertex = value;
tempvertex.firstedge = NULL;
adjlist[i] = tempvertex; //第i个顶点的数据域置为value

/*
*前置条件：图已存在
*输 入：顶点i
*功 能：在图中删除顶点i
*输 出：如果删除不成功，抛出异常
*后置条件：如果删除成功，图中减少了一个顶点,相应顶点所建立的边也消去
*/
template < class T>
void Graph< T> ::DeleteVex_L(int i)

if ( i< 0 || i> MaxSize) throw "位置"; //顶点输入错误则抛出异常
int k;
for ( k=0; k< vertexNum; k++)//删掉入度边
if(k!=i) DeleteArc(k, i);
ArcNode *s; //生成一个边表结点s
if( adjlist[i].firstedge != NULL)

ArcNode *s;
s=adjlist[i].firstedge-> next;
while(s!=NULL)

ArcNode *p;
p = s;
adjlist[i].firstedge-> next = s-> next;
s=s-> next;
delete p; //删除p结点

s=adjlist[i].firstedge;
adjlist[i].firstedge=NULL;
delete s;

for (k=i; k< vertexNum; k++)

adjlist[k]=adjlist[k+1]; //存储顶点信息

vertexNum--; //顶点数减1
for (k=0; k< vertexNum; k++)
if( adjlist[k].firstedge != NULL )

s=adjlist[k].firstedge; //将结点s插入到结点i的边表的表头
while(s!=NULL)

if(s-> adjvex > i)//搜索i结点
s-> adjvex--;
s = s-> next;



/*
*前置条件：图已存在
*输 入：顶点i、j
*功 能：在图中插入顶点i、j及其所依附的边
*输 出：如果插入不成功，抛出异常
*后置条件：如果插入成功，图中增加了一条边
*/
template < class T>
void Graph< T> ::InsertArc_L(int i, int j)

if ( i> MaxSize || j> MaxSize) throw "位置"; //顶点输入错误则抛出异常
ArcNode *s=new ArcNode; s-> adjvex=j; //生成一个边表结点s
s-> next=adjlist[i].firstedge; //将结点s插入到结点i的边表的表头
adjlist[i].firstedge=s;

/*
*前置条件：图已存在
*输 入：顶点i、j
*功 能：在图中删除顶点i、j 依附的边
*输 出：如果删除不成功，抛出异常
*后置条件：如果删除成功，图中减少了一条边
*/
template < class T>
void Graph< T> ::DeleteArc_L(int i, int j)

if ( i> MaxSize|| j> MaxSize) throw "位置"; //顶点输入错误则抛出异常
ArcNode *s;
ArcNode *tempnode;
s = adjlist[i].firstedge;
tempnode = adjlist[i].firstedge;
while(s!=NULL & & s-> adjvex!=j)

tempnode = s;
s = s-> next;

if(s!=NULL)

tempnode-> next = s-> next;
delete s;


/*
*前置条件：图已存在
*输 入：遍历的起始顶点v
*功 能：从顶点v出发深度优先遍历图
*输 出：图中顶点的一个线性排列
*后置条件：图保持不变
*/
template < class T>
void Graph< T> ::DFSTraverse_L(int v)

if ( v> vertexNum) throw "位置"; //顶点输入错误则抛出异常
ArcNode * p;
int j;
cout< < adjlist[v].vertex< < " ";
visited[v]=1;
p=adjlist[v].firstedge;
while (p)//依次搜索顶点v的邻接点j

j=p-> adjvex;
if (visited[j]==0) DFSTraverse_L(j);
p=p-> next;


/*
*前置条件：图已存在
*输 入：遍历的起始顶点v
*功 能：从顶点v出发广度优先遍历图
*输 出：图中顶点的一个线性排列
*后置条件：图保持不变
*/
template < class T>
void Graph< T> ::BFSTraverse_L(int v)

if(v> vertexNum) throw "weizhi";
intQ[9];
int front ,rear,j;
ArcNode *p=NULL;
front = -1;
rear = -1; //初始化顺序队列
cout < < adjlist[v].vertex< < "";
visited[v] = 1;
Q[++rear] = v;
while (front != rear) //当队列非空时

v=Q[++front] ;
p = adjlist[v].firstedge; //工作指针p指向顶点v的边表
while (p != NULL)

j = p-> adjvex;
if (visited[j] == 0)

cout < < adjlist[j].vertex< < "";
visited[j] = 1;
Q[++rear] = j;

p=p-> next;



3、图的测试函数，文件为“GraphMain.cpp”
#include < iostream>
#include < string> //引入标准库中的头文件
#include "Graph.cpp"//引用 Graph.cpp 文件
using namespace std;
int main(int argc, char* argv[])

const int numv = 8; //顶点数
int choose=1; //控制
int which; //功能选择变量
string name; //插入顶点的值
int cost[numv][numv]=//按邻接矩阵确定顶点的权值
10000,130,80,260,10000,10000,10000,10000,
130,10000,10000,75,10000,265,10000,10000,
80,10000,10000,10000,50,10000,10000,10000,
260,75,10000,10000,120,85,400,10000,
10000,10000,50,120,10000,10000,350,200,
10000,265,10000,85,10000,10000,120,10000,
10000,10000,10000,400,350,120,10000,150,
10000,10000,10000,10000,200,10000,150,10000
; //当前找到的最短路径
string vname[numv]="一教","二教","三教","图书馆","新食堂","逸夫楼","学研大厦","校医院"; //初始化各顶点
int* p; //定义指针p
string* q; //定义指针q
p = & cost[0][0]; //p指针指向cost数组的起始位置
q = vname; //q指针指向vname数组
Graph< string> g(p, q, numv ); //调用Graph程序
while ( choose==1 )//控制

cout < < "-------功能选项---------" < < "\\n";
cout < < "0、查看顶点信息请按0" < < "\\n"; //输入你要进行的操作的序号
cout < < "1、查看边的信息请按1" < < "\\n";
cout < < "2、需要修改请按2" < < "\\n";
cout < < "3、Dijkstra求最短路径请按3" < < "\\n";
cout < < "4、删除某个顶点请按4" < < "\\n";
cout < < "5、插入某个顶点请按5" < < "\\n";
cout < < "6、删除某条边请按6" < < "\\n";
cout < < "7、插入某条边请按7" < < "\\n";
cout < < "8、退出请按8" < < "\\n";
cout < < "-----------------------" < < "\\n";
cin > > which;
switch( which )//功能选择

case 0: //输出图的各顶点的值
try

cout < < "顶点信息如下："< < "\\n";
g.PutOutVexInfo();

catch(char*)

cout< < "输出不正确！"< < endl;

break;
case 1://输出图中的路径
int i;
int j;
cout< < "所有的边的信息为:"< < "\\n";
try

g.PutOutArcInfo();

catch(char*)

cout< < "输出不正确！"< < endl;

break;
case 2://修改图中的边长
cout< < "change";
cin> > i> > j;
int length;
cout< < "length";
cin> > length;
try

g.SetArc(i,j,length);

catch(char*)

cout< < "输出顶点不正确！"< < endl;

break;
case 3://求最短路径
cout< < "请输入源顶点:"< < "\\n";
int vv ;
cin> > vv;
cout< < "请输入结束顶点，若要全部显示请输入88:"< < "\\n";
int vvt ;
cin> > vvt;
try

g.Dijkstra(vv,vvt);

catch(char*)

cout< < "输出顶点不正确！"< < endl;

break;
case 4://删除hh顶点
int hh ;
cout< < "请输入要删除的顶点"< < "\\n";
cin> > hh;
try

g.DeleteVex(hh);

catch(char*)

cout< < "删除失败！"< < endl;

break;
case 5://在nn位置插入值为name的顶点
int nn ;
cout< < "请输入要插入的顶点的位置和名称"< < "\\n";
cin> > nn> > name;
try

g.InsertVex(nn,name);

catch(char*)

cout< < "插入失败！"< < endl;

break;
case 6://删除pos1到pos2之间的距离
int pos1;
int pos2;
cout< < "请输入两顶点："< < "\\n";
cin> > pos1> > pos2;
try

g.DeleteArc(pos1,pos2);

catch(char*)

cout< < "插入失败！"< < endl;

break;
case 7://插入从pos1到pos2的路径
int m;
cout< < "请输入两顶点："< < "\\n";
cin> > pos1> > pos2;
cout< < "请输入路径："< < "\\n";
cin> > m;
try

g.InsertArc(pos1,pos2,m);

catch(char*)

cout< < "插入失败！"< < endl;

break;
case 8://退出
choose=0;
break;


return 0;

4、图的邻接表测试函数，文件为“GraphMain_L.cpp”
#include < iostream>
#include < string>
#include "graph.cpp"
using namespace std;
int visited[MaxSize];
void main( )

int which;
int j;
string name;
int choose=1;
string a[5] = "石油大学（北京）","政法大学","化工大学","北京警察学院","国防大学";
Graph< string> algraphTest( a, 5, 0); //构造图
while ( choose==1 )//控制

cout < < "-------功能选项---------" < < "\\n";
cout < < "0、输出顶点信息请按0" < < endl; //输入所要进行的操作的序号
cout < < "1、输出任意一个顶点信息请按1" < < endl;
cout < < "2、插入顶点请按2" < < endl;
cout < < "3、修改顶点请按3" < < endl;
cout < < "4、删除顶点请按4" < < endl;
cout < < "5、深度优先遍历请按5" < < endl;
cout < < "6、广度优先遍历请按6" < < endl;
cout < < "7、退出请按7" < < endl;
cin > > which;
switch( which )//功能选择

case 0:
for(j=0; j< 5; j++ )
cout< < algraphTest.GetVex_L(j)< < " "; //输出顶点
cout< < endl;
break;
case 1:
int i;
cout< < "请输入顶点："< < endl;
cin> > i;
try

cout< < algraphTest.GetVex_L(i)< < endl; //输出i顶点的数据域

catch(char* s)

cout< < s< < endl;

break;
case 2://在图中的i位置插入一顶点值为name
cout< < "请输入顶点及名字："< < endl;
cin> > i> > name;
try

algraphTest.InsertVex_L(i, name);

catch(char* s)

cout< < s< < endl;

break;
case 3://修改图中一顶点的值
cout< < "请输入顶点及名字："< < endl;
cin> > i> > name;
try

algraphTest.PutVex_L(i, name);

catch(char* s)

cout< < s< < endl;

break;
case 4://删除图中一顶点的值
cout< < "请输入顶点："< < endl;
cin> > i;
try

algraphTest.DeleteVex_L(i);

catch(char* s)

cout< < s< < endl;

break;
case 5://图的深度优先搜索
cout< < "请输入顶点："< < endl;
cin> > i;
cout< < endl< < "从第"< < i< < "个顶点深度优先遍历图"< < endl;
try

for (int ii=0; ii< MaxSize; ii++) visited[ii] = 0;
algraphTest.DFSTraverse_L(i);

catch(char* s)

cout< < s< < endl;

break;
case 6://图的广度优先搜索
cout< < "请输入顶点："< < endl;
cin> > i;
cout< < endl< < "从第"< < i< < "个顶点广度优先遍历图"< < endl;
try

for (int ii=0; ii< MaxSize; ii++) visited[ii] = 0;
algraphTest.BFSTraverse_L(i);

catch(char*s)

cout< < s< < endl;

break;
case 7://退出
choose=0;
break;



注意问题
１．注意理解各算法实现时所采用的存储结构。
２．注意区别正、逆邻接矩阵。
程序运行贴图：
广度优先遍历
?

数据结构与算法第四次实验报告图

文章图片
?




心得和总结：
这次的报告经由老师大大的点拨会了好多，而且课件上也有代码，方便点直接拿过来就可以了，但是我不想这么做，代码是我自己打的，虽然也借鉴了课件，但是基本还是以学知识为主，毕竟是吃饭的本事，不能这么草草了事，希望我能在以后也灵活运用这里的知识。







    推荐阅读


    上一篇：#yyds干货盘点# 更高级别的抽象---函数式思想

    下一篇：Java语言程序设计 上机实验6掌握Java的图形用户界面编程，掌握布局管理器和事件的响应方法