C++大数据结构以邻接矩阵方式确定有向网.docx

C++大数据结构以邻接矩阵方式确定有向网.docx

《C++大数据结构以邻接矩阵方式确定有向网.docx》由会员分享，可在线阅读，更多相关《C++大数据结构以邻接矩阵方式确定有向网.docx（22页珍藏版）》请在冰点文库上搜索。

C++大数据结构以邻接矩阵方式确定有向网

《数据结构》

课程设计报告

设计题目：

以邻接矩阵方式确定有向网

班级：

：

学号：

完成日期：

1、需求分析

1、运行环境（软、硬件环境）：

处理器：

英特尔酷睿（Core）i5-2410MCPU2.30GHz

物理存：

2G

操作系统：

MicrosoftWindowns7

开发环境：

MicrosoftVisualStudio2008

2、程序所实现的功能：

（1）建立并显示出它的邻接链表；

（2）以非递归的方式进行深度优先遍历，显示遍历的结果，

（并随时显示栈的入、出情况）；

（3）对改图进行拓扑排序，显示拓扑排序的结果，并随时

显示入度域的变化情况；

（4）给出某一确定顶点到所有其他顶点的最短路径；

3、程序的输入，包含输入的数据格式和说明：

（1）输入节点数个数

（2）输入顶点信息（空格隔开）

（3）输入权值信息（以弧尾值弧头值权值信息，空格

隔开000结束；）

4、程序的输出，程序输出的形式：

（1）邻接链表输出

（2）深度优先遍历输出（3）拓扑排序输出（4）最短路径输出

5、测试数据：

（1）节点个数：

5个

（2）顶点信息：

abcde

（3）权值信息：

ab1bc2cd3de4ad5dc6000

2、设计说明

1、算法设计的思想：

建程序主要是通过建立一个图的模板类来调用相应的构造函数以及相应的成员函数来实现其功能，首先用结构体来存储边节点和顶点节点，用邻接矩阵来存储此有向图，遍历的过程采用双从循环来使得遍历达到最底端，最短路径采用了递归的思想循环调用最短路径函数来完成最短路径的查找，拓扑排序中首先优先输出入度为零的节点，然后通过删除该节点继续此过程进行排序。

2、主要的数据结构设计说明：

图的邻接矩阵结构设计：

顶点数、弧数、矩阵数组、和点数组

栈结构：

包括栈顶和栈底

点结构：

包括顶点和弧相关的指针信息。

3、程序的主要流程图：

有向图

输出邻接表

深度优先遍历

入度域变化

最短路径

拓扑排序

4、主要模块和函数:

1、邻接矩阵创建有向网voidCreatGraph（MGraph*g）

伪码：

依次存储节点数、顶点信息、权值

2、打印有向网的邻接矩阵voidPrintGraph（MGraph*g）

伪码：

依次打印邻接矩阵

3、打印有向网的邻接表voidPrintList（MGraph*g）

伪码：

输出矩阵每行不为零值纵坐标对应的节点

4、非递归深度优先遍历voidDFSTraverse（MGraph*g）

伪码：

1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，并将最后入栈值出栈；

2.再将最后入栈值定为横坐标，重复上述操作，直到空；

3.出栈，重复第二步操作；

4.重复第三部操作，直到栈空；

5、获取每个节点的入度voidFindInDegree（）

伪码：

获取邻接矩阵每行非零值个数

6、拓扑排序intTopologicalSort（MGraph*g）

伪码：

1.先将度为零节点入栈

2.出栈，对i号节点的每个邻接点入度减1

3.若入度减为0，则入栈

4.重复2，3步，直至栈空

7、任意两点最短距离voidShortestPath_FLOYD（MGraph*g）

伪码：

先看两点之间有无直接路径，若有，则看有无通过中间点更短

若无，则看有无中间点连通

三、源程序代码：

#include

#include

#include

usingnamespacestd;

#defineMAX_VERTEX_NUM20//最大顶点个数

#defineSTACK_INIT_SIZE100//存储空间初始分配量

#defineSTACKINCREMENT10//存储空间分配增量

#defineOVERFLOW0

#defineERROR0

#defineOK1

#defineINFINITY100

typedefstructArcCell//图的邻接矩阵结构定义

{

charadj;//顶点

int*info;//弧相关信息指针

}VertexNode;

typedefstruct

{

VertexNodevexs[MAX_VERTEX_NUM];//顶点向量

intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵

intvexnum,arcnum;//定点数和弧数

}MGraph;

typedefstruct

{

int*base;//栈底指针

int*top;//栈顶指针

intstacksize;//存储空间

}SqStack;

/*

函数名称：

findnode

函数功能描述：

返回结点在数组位置

函数调用之前的预备条件：

定义并赋值结点数组

返回后的处理：

返回值（如果有的话）：

int

函数的输入参数：

SqStack&S，结点字符a

函

*/

intfindnode（chara,MGraph*S）

{

for（inti=1;i<（S->vexnum+1）;i++）

{if（S->vexs[i].adj==a）

returni;}

return-1;

}

/*

函数名称：

InitStack

函数功能描述：

构造一个空栈

函数调用之前的预备条件：

定义邻接矩阵结构体

返回后的处理：

返回值（如果有的话）：

OVERFLOW或OK

函数的输入参数：

SqStack&S

函数的输出参数：

函数的抽象算法（伪码）：

存储分配

*/

intInitStack（SqStack&S）//构造一个空栈

{

S.base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;

if（!

S.base）//存储分配失败

returnOVERFLOW;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}

/*

函数名称：

StackEmpty

函数功能描述：

判断栈是否为空栈

函数调用之前的预备条件：

已构造一个栈

返回后的处理：

返回值（如果有的话）：

OK或ERROR

函数的输入参数：

SqStack&S

函数的输出参数：

函数的抽象算法（伪码）：

栈底与栈顶比较

*/

intStackEmpty（SqStack&S）

{

if（S.top==S.base）//空栈

returnOK;

else

returnERROR;

}

/*

函数名称：

Push

函数功能描述：

插入新的栈顶元素

函数调用之前的预备条件：

已构造一个栈

返回后的处理：

返回值（如果有的话）：

OK

函数的输入参数：

SqStack&S,inte

函数的输出参数：

函数的抽象算法（伪码）：

指针移动

*/

intPush（SqStack&S,inte）//插入新的栈顶元素

{

if（S.top-S.base>=S.stacksize）//栈满，追加存储空间

{

S.base=（int*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（int））;

if（!

S.base）//存储分配失败

return（OVERFLOW）;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

}

/*

函数名称：

GetTop

函数功能描述：

获取的栈顶元素

函数调用之前的预备条件：

已构造一个栈

返回后的处理：

返回值（如果有的话）：

e或ERROR

函数的输入参数：

SqStack&S,inte

函数的输出参数：

函数的抽象算法（伪码）：

指针移动

*/

intGetTop（SqStack&S,int&e）

{

if（S.top==S.base）

returnERROR;

e=*（S.top-1）;

returne;

}

/*

函数名称：

Pop

函数功能描述：

删除栈顶元素

函数调用之前的预备条件：

已构造一个栈

返回后的处理：

返回值（如果有的话）：

e

函数的输入参数：

SqStack&S,int&e

函数的输出参数：

e

函数的抽象算法（伪码）：

指针移动

*/

intPop（SqStack&S,int&e）//删除栈顶元素

{

if（S.top==S.base）

returnERROR;

e=*--S.top;

returne;

}

/*

函数名称：

CreatGraph

函数功能描述：

邻接矩阵创建有向网

函数调用之前的预备条件：

定义邻接矩阵结构体

返回后的处理：

返回值（如果有的话）：

函数的输入参数：

MGraph*g

函数的输出参数：

函数的抽象算法（伪码）：

依次存储节点数、顶点信息、权值

*/

voidCreatGraph（MGraph*g）//邻接矩阵创建有向网

{

inti,j,m,o,p;

charr1,r2;//m权值

cout<<"请输入节点数：

\n";

cin>>g->vexnum;//获取节点数

cout<<"请输入有向网顶点信息（空格间开）：

\n";

for（i=1;i<=g->vexnum;i++）//获取顶点信息

{

cin>>g->vexs[i].adj;

}

for（i=1;i<=g->vexnum;i++）//初始化邻接矩阵

for（j=1;j<=g->vexnum;j++）

{

g->arcs[i][j]=0;

}

cout<<"请输入权值信息（以弧尾值弧头值权值顺序，空格间开，000结束）:

\n";

cin>>r1>>r2>>m;//权值信息

while（r1!

='0'&&r2!

='0'&&m!

=0）//生成邻接矩阵转

{

o=findnode（r1,g）;

p=findnode（r2,g）;

g->arcs[o][p]=m;

cin>>r1>>r2>>m;

}

}

/*

函数名称：

PrintList

函数功能描述：

打印有向网的邻接表

函数调用之前的预备条件：

已创建有向网CreatGraph

返回后的处理：

返回值（如果有的话）：

函数的输入参数：

MGraph*g

函数的输出参数：

g->vexs[j].adj

函数的抽象算法（伪码）：

输出矩阵每行不为零值纵坐标对应的节点

*/

voidPrintList（MGraph*g）//打印有向网的邻接表

{

inti,j;

for（i=1;i<=g->vexnum;i++）

{

cout<<（g->vexs[i].adj）;

for（j=1;j<=g->vexnum;j++）

{

if（g->arcs[i][j]!

=0）//获取非零值

{

cout<<"-->"<<（g->vexs[j].adj）;

}

}

cout<<"-->NULL\n";//一行结束，打印空

}

}

/*

函数名称：

DFSTraverse

函数功能描述：

非递归深度优先遍历

函数调用之前的预备条件：

已创建有向网CreatGraph

返回后的处理：

返回值（如果有的话）：

函数的输入参数：

MGraph*g

函数的输出参数：

g->vexs[i].adj

函数的抽象算法（伪码）：

1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，并将最后入栈值出栈；

2.再将最后入栈值定为横坐标，重复上述操作，直到空；

3.出栈，重复第二步操作；

4.重复第三部操作，直到栈空；

*/

voidDFSTraverse（MGraph*g）//非递归深度优先遍历

{

intvisited[MAX_VERTEX_NUM],i=1,j,e=1;//visited[]标记向量，e出栈值

SqStacks;

InitStack（s）;

Push（s,i）;//首节点入栈

cout<<"插入栈顶元素：

\n"<

cout<<"-->"<vexs[i].adj<

visited[i]=1;//有输出，即为1

while（!

StackEmpty（s））

{

i=e;//从e行开始

for（j=g->vexnum;j>=1;j--）//从右向左寻找

{

if（g->arcs[i][j]&&（visited[j]!

=1））//非零即入栈

{

Push（s,j）;

cout<<"插入栈顶元素：

"<

}

}

Pop（s,e）;//该行最左非零值入栈

cout<<"删除栈顶元素：

"<

if（visited[e]!

=1）//未被标记

{

cout<<"-->"<vexs[e].adj<

visited[e]=1;

}

}

}

/*

函数名称：

FindInDegree

函数功能描述：

获取每个节点的入度，并存储在indegree数组中

函数调用之前的预备条件：

已创建有向网CreatGraph

返回后的处理：

返回值（如果有的话）：

函数的输入参数：

MGraph*g

函数的输出参数：

indegree[]

函数的抽象算法（伪码）：

获取邻接矩阵每行非零值个数

*/

voidFindInDegree（MGraph*g,intindegree[MAX_VERTEX_NUM]）//获取每个节点的入度，并存储在indegree数组中

{

inti,j,n;//n入度

for（i=1;i<=g->vexnum;i++）

{

n=0;

for（j=1;j<=g->vexnum;j++）

if（g->arcs[j][i]）//每行非零值个数

n++;

indegree[i]=n;//存储入度

}

}

/*

函数名称：

TopologicalSort

函数功能描述：

拓扑排序

函数调用之前的预备条件：

已创建有向网CreatGraph；获取每个节点的入度FindInDegree

返回后的处理：

返回值（如果有的话）：

函数的输入参数：

MGraph*g

函数的输出参数：

g->vexs[i].adj

函数的抽象算法（伪码）：

1.先将度为零节点入栈

2.出栈，对i号节点的每个邻接点入度减1

3.若入度减为0，则入栈

4.重复2，3步，直至栈空

*/

intTopologicalSort（MGraph*g）//拓扑排序

{

intindegree[MAX_VERTEX_NUM],i,j,k,count;//count输出顶点计数

SqStackS;

FindInDegree（g,indegree）;//对各顶点求入度

InitStack（S）;

for（i=1;i<=g->vexnum;i++）//建立零入度顶点栈

if（!

indegree[i]）//入度为零入栈

Push（S,i）;

count=0;

while（!

StackEmpty（S））

{

Pop（S,i）;

cout<<"\n-->"<vexs[i].adj;

++count;

for（j=1;j<=g->vexnum;j++）

{

if（g->arcs[i][j]）

{

k=j;

if（!

（--indegree[k]））

Push（S,k）;

cout<<"\t此时"<vexs[k].adj<<"入度：

"<

}

}

}

if（countvexnum）//有回路

returnERROR;

else

returnOK;

}

/*

函数名称：

ShortestPath_FLOYD

函数功能描述：

任意两点最短距离

函数调用之前的预备条件：

已创建有向网CreatGraph

返回后的处理：

返回值（如果有的话）：

函数的输入参数：

MGraph*g

函数的输出参数：

dist[i][j]

函数的抽象算法（伪码）：

先看两点之间有无直接路径，若有，则看有无通过中间点更短

若无，则看有无中间点连通

*/

voidShortestPath_FLOYD（MGraph*g）//任意两点最短距离

{

intdist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//dist[]两点间路径长度

inti,j,k;

for（i=1;i<=g->vexnum;i++）//初始化

for（j=1;j<=g->vexnum;j++）

dist[i][j]=g->arcs[i][j];

for（i=1;i<=g->vexnum;i++）

{

for（j=1;j<=g->vexnum;j++）

{

cout<vexs[i].adj<<"-->"<vexs[j].adj<<":

\t";

for（k=1;k<=g->vexnum;k++）

if（i!

=j&&i!

=k&&j!

=k）//三点互不相同

{

if（dist[i][j]）//有直接路径

{

if（dist[i][k]&&dist[k][j]）

if（dist[i][j]>dist[i][k]+dist[k][j]）//有中间更短路径

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

}

else

{

if（dist[i][k]&&dist[k][j]）

dist[i][j]=dist[i][k]+dist[k][j];//取中间路径

}

}

cout<

}

cout<

}

}

voidmain（）//主函数

{

MGraph*g=（MGraph*）malloc（sizeof（MGraph））;

CreatGraph（g）;

cout<<"***********************************************\n邻接链表输出：

\n";

PrintList（g）;

cout<<"***********************************************\n深度优先遍历：

\n";

DFSTraverse（g）;

cout<<"***********************************************\n拓扑排序：

";

TopologicalSort（g）;

cout<<"\n***********************************************\n最短路径:

\n";

ShortestPath_FLOYD（g）;

}

4、输出结果：

五：

上机结果及体会

1、实际完成情况说明：

本次数据结构课程设计，在同学以及老师的帮助下，完成了实验题目所要求的

（1）建立并显示出它的邻接链表；

（2）以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）（3）对该图进行拓扑排序，显示拓扑排序的结果，并随时显示入度域的变化情况；（4）给出某一确定顶点到所有其他顶点的最短路径；四个基本功能要求。

虽然在算法的选择上可能还有不足之处，但总体完成情况和进度还行，所以本次课程设计总体上还是成功的。

2、课程设计遇到的问题及解决方法：

1.语法错误太多，由于大部分函数都是按照书上的思想进行设计的，思想是没问题的，可是书上存在印刷错误，语法错误比较容易，只需要根据说明逐个修改即可，此外还有大括号匹配错误。

2.出现了死循环，在输出邻接表的过程中出现了死循环，主要是循环过程中的条件出现了问题，修改后已经解决了，还要注意的是:

必须按照输入格式进行输入，不然也可能出现错误。

3.拓扑排序时，刚开时出现错误，由于不能利用递归算法实现，所以利用栈来实现的，刚开始没有注意栈是“后进先出”，后来改正了。

3、程序的性能分析：

程序符合任务的规定说明，且没有错误，易读，且程序根据逻辑关系能分解成有效执行的函数。

对于一个n个顶点e条边的有向网，初始化其邻接矩阵时间复杂度为

O（n2）。

建立其邻接链表的时间复杂度为O（n+e）。

拓扑排序的时间复杂度为

O（n+e）。

最短路径采用弗洛伊德算法时间复杂度为O（n3）。

4、程序中可以改进的地方说明：

（1）首先，这个程序输入时格式过于复杂，所以需要在以后改进此程序的输入界面。

（2）其次，输入顶点以及权值时，假如输错，没有报错处理的函数，所以可以写一个当输入格式出现错误时报错的函数。

（3）另外算法上也可以选择更加简便的算法,降低程序的时间复杂度和空间复杂度。

5、程序中可以扩充的功能及设计实现假想：

（1）还可以实现广度优先遍历，还可以利用普里姆或者克鲁斯卡尔算法来求最小生成树。

（2随用户的输入可以随时动态的显示图的生成。

（3）多运用些C++以及数据结构知识，使程序更加简洁易懂，健壮。

6、收获及体会：

通过这次的课程设计，对数据结构这门儿科目有了更深层次的认识，首先平时的学习毕竟只是理论上的学习，如果不拿来实践那就相当于白学，通过这次课程设计发现了好多小错误，这在平时作业中是无法发现的，真正的错误只有把它放到编译系统中才能明确的显示出来。

其次，这次课程设计更加让我发现了自己编程能力的差劲，好像根本就离不开书本，离开书本以后仿佛大脑就不知道该做什么，让我清晰的认识到自己还处于一个井底之蛙的状态，对编程实在实践的太少了，虽然思想重要，但是最终编程总是要运用到实践中去的，接下来得好好的进行练习。

六、参考文献

缪准扣，顾训穰，俊。

数据结构——C++实现。

科学，2002