数据结构课程设计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 Graph4、 程序的主要函数 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)给出某一确定顶点到所有其它顶点的最短路径。#includeusing 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的第一个邻接点的序号。如果不存在返回-1int 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[]);//深度优先搜索 void DFTraverse (); //深度遍历 void TopologicalOrder(); //拓扑排序void ShortestPath(int n,int v);//最短路径};///////////////////////////////////////////////////////////////////////////////////templateint Graph::GetVertexPos(const Type &v ){ //根据顶点v查找该顶点在邻接表中的位置 for(int i=0;iGraph::Graph( Type v[] , int num=MaxVertexes) :CurrentNumVertexes(0), CurrentNumArcs(0){ Type tail, head; int i=0,e,h,t,w,p=0; while(p[MaxVertexes];//创建顶点表 for(i=0;i> e;//输入边的条数 cout<>tail>>head>>w; //输入一条边 int j=GetVertexPos(head); while((t=GetVertexPos(tail))==-1) cout<<"输入的顶点(tail)不存在"; while((h = GetVertexPos(head ))==-1) cout<<"输入的顶点(head)不存在"; InsertArc (t,h,w); //插入一条边 InDegree[j]++; //顶点j的入度加1 cout<Type Graph::GetValue(int v){ //取图中顶点v的值，如果顶点v不存在，则返回空 if(v>=0&&vint Graph::Getweight(int v1,int v2){//取出以顶点v1和v2为两端点的边上的权值 if(v1>=0&&v1=0&&v2adjvex==v2) {return p->weight;} else {p=p->nextarc; } } } return NULL;}templateint Graph::GetFirstNeighbor(int v){//查找顶点v的第一个邻接顶点的位置 if(v>=0&&vadjvex; } return -1; }templateint Graph::GetNextNeighbor(int v1,int v2){//查找顶点v1的在v2之后的下一个邻接顶点，如果不存在返回-1 if (v1!=-1){ ArcNode *p=VTable[v1].firstarc; while(p!=NULL){ if(p->adjvex==v2&&p->nextarc!=NULL) return p->nextarc->adjvex;//返回下一个邻接顶点在邻接表中的位置 else p=p->nextarc; } } return -1;//没有查到下一个邻接顶点返回-1}
templateint Graph::InsertArc(int v1,int v2,int w){//在图中插入弧 if(v1>=0&&v1adjvexnextarc; } newnode->nextarc=p->nextarc; p->nextarc=newnode; return 1; } VTable[v1].firstarc=newnode; return 1; } return -1;}templateint Graph::InVertex(Type &v){//在图中插入顶点，插入成功则返回1，否则返回0 if(CurrentNumVertexesvoid Graph::link(){ cout<<"输出邻接表:"<"<"<void Graph::TopologicalOrder(){ int m=0;//m为输出的顶点数，初始值为0 for(int i=0;i=0&&n=0&&tvoid Graph::DFS(const int v,int visited[ ]){ cout<< VTable[v].data<<" "; //访问顶点 v visited[v] =1; //顶点v 作访问标记 int w = GetFirstNeighbor (v); while (w != -1) { //若顶点 w 存在 if (!visited[w]) DFS (w,visited); w = GetNextNeighbor(v,w); } //重复检测 v 的所有邻接顶点}templatevoid Graph ::DFTraverse () { int i, n = NumberOfVertexes() ; //取图的顶点个数 int * visited = new int [n]; //定义访问标记数组 visited for ( i = 0; i < n; i++ ) visited [i] = 0; //访问标记数组 visited 初始化 for ( i = 0; i < n; i++ ) //对图中的每一个顶点进行判断 if (!visited [i]) DFS (i, visited ); delete[ ]visited; //释放 visited }//求最短路径templatevoid Graph::ShortestPath(int n,int v){ int min,u; dist=new int[n]; s=new int[n]; path=new int[n]; for(int j=0;j
}//主函数void main(){ char op; do{ int m,i=0,j=0,w; char a[20],c; cout<<"请你输入顶点的个数:"; cin>>m; for(i=0;i>a[i]; cout<G(a,m); G.link(); cout<<"深度遍历:"<>c; w=G.GetVertexPos(c); G.ShortestPath(m,w);loop:cout<<"是继续？(Y or N)"<>op; if(op=='N'||op=='n')break; if(op!='Y'&&op!='y'&&op!='N'&&op!='n')goto loop; }while(op=='Y'||op=='y');}
