图邻接矩阵 邻接表的建立c++_数据结构课程设计

一.需求分析 1.运行环境

硬件：计算机486/64M以上

操作系统： WIN9x 以上/WIN2000/WIN XP/WIN ME 相关软件：vistualC++ 2．程序所实现的功能：

（1）建立并显示图的邻接表。

（2）深度优先遍历，显示遍历结果。

（3）对该图进行拓扑排序，显示排序结果。

（4）给出某一确定顶点到所有其它顶点的最短路径。 3.程序的输入，包含输入的数据格式和说明 (1)输入顶点数,及各顶点信息(数据格式为整形) (2)输入边数,及权值(数据格式为整形) 4.程序的输出，程序输出的形式

(1)输出图的邻接表、深度优先遍历结果、拓扑排序结果。 (2)输入某一确定顶点到其它所有顶点的最短路径。 5.测试数据 二、设计说明

1、 算法设计的思想

建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。 2、 主要的数据结构设计说明

图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。 3、 程序的主要模板template class Graph 4、 程序的主要函数

Graph、link()、DFTraverse()、TopologicalOrder()、 TopologicalOrder()、GetVertexPos()、ShortestPath 三、上机结果及体会 1、 实际完成的情况说明

主要程序参考教材《数据结构——C++版》。 2、 程序的性能分析 可连续建图

3、 上机过程中出现的问题及其解决方案。 编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。 4、 程序中可以改进的地方说明

程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度度加长的代价。

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

实现假想：随用户的输入可以随时动态的显示图的生成。 6、 收获及体会

编写程序即是一件艰苦的工作，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题。 四、参考文献

数据结构（C++版） 叶核亚 主编 机械工业出版社

数据结构经典算法实现与习题解答 汪杰 编著 人民邮电出版社 数据结构课程设计 苏仕华 编著 机械工业出版社 数据结构程序设计题典 李春葆 编著 清华大学出版社

数据结构课程与题解（用C/C++描述） 胡圣荣 编著 北京大学出版社

[程序运行流程图]

char op //程序控制变量

If(op=='Y'||op=='y')

if(op=='N'||op=='n')

//本程序是邻接矩阵，邻接表的利用，共有4项功能,分别是： //(1)建立并显示图的邻接表。

//(2)以非递归方式进行深度优先遍历，显示遍历结果。 //(3)对该图进行拓扑排序，显示排序结果。

//(4)给出某一确定顶点到所有其它顶点的最短路径。 #include using namespace std;

const int MaxVertexes=20; //最大的顶点数 const int b=10000;

template class Graph ; struct ArcNode{//定义边结点

friend class Graph ;

int adjvex; //和边（或弧）相关联的另一个顶点序号 int weight; //边（或弧）上的信息 ArcNode *nextarc ; //指向下一条边结点的指针 ArcNode(int v,int w ) : adjvex( v ),weight(w),nextarc( NULL ){ } };//构造函数

template

struct VertexNode{// 定义顶点结点 friend class Graph ;

Type data; //顶点的信息

ArcNode *firstarc ; //指向依附该顶点的边链表 };

template class Graph {

VertexNode * VTable; //顶点表

int CurrentNumVertexes; //当前的顶点数

int CurrentNumArcs; //当前的边（或弧）数 public:

int GetVertexPos( const Type &v );// 取顶点v在数组中的位置 Graph(Type v[],int num=MaxVertexes); //构造函数 Type GetValue(int v); //取图中顶点v的值，如果顶点v不存在则返回空 int Getweight(int v1,int v2); //取边（或弧）上的权值

int GetFirstNeighbor(int v); //取图中顶点v的第一个邻接点的序号。如果不存在返回-1

int GetNextNeighbor(int v1, int v2); //取图中下一个邻接点 int Arcs[MaxVertexes][MaxVertexes];//用数组记录每个边的信息 int InVertex(Type &v); //在图中插入结点

int InsertArc(int v1, int v2,int w);//在图中插入依附于v1和v2的边或弧，w是信息

int NumberOfVertexes( ){return CurrentNumVertexes; } //返回当前的顶点数 int NumberOfArcs(){ return CurrentNumArcs; } //返回当前的边（或弧）数 int *dist; //最短路径长度数组

int *InDegree; //入度数组，记录每个顶点的入度 int *path; //最短路径的数组 int *s; //最短路径终点数组 void link(); //输出邻接链表

void DFS(const int v,int visited[]);//深度优先搜索