毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

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

更新时间:2007-10-20:  来源:毕业论文
数据结构课程设计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 Type> 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<iostream>
using namespace std;
const int MaxVertexes=20;  //最大的顶点数           
const int b=10000;
template <class Type> class Graph ;
struct ArcNode{//定义边结点
    friend class Graph <class Type>;
    int adjvex;                     //和边(或弧)相关联的另一个顶点序号
    int weight;                     //边(或弧)上的信息
    ArcNode *nextarc ;              //指向下一条边结点的指针
ArcNode(int v,int w ) : adjvex( v ),weight(w),nextarc( NULL ){ }
};//构造函数
template <class Type>
struct VertexNode{// 定义顶点结点
friend class Graph <class Type>;
    Type data;                      //顶点的信息
    ArcNode *firstarc ;             //指向依附该顶点的边链表
};
template <class Type>class Graph
{
 VertexNode<Type> * 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[]);//深度优先搜索
   void DFTraverse ();            //深度遍历
   void TopologicalOrder();       //拓扑排序
void ShortestPath(int n,int v);//最短路径
};
///////////////////////////////////////////////////////////////////////////////////
template<class Type>int Graph<Type>::
GetVertexPos(const Type &v ){    //根据顶点v查找该顶点在邻接表中的位置
 for(int i=0;i<CurrentNumVertexes;i++)
  if(VTable[i].data==v)   return i;
  return -1;
}
template<class Type>Graph<Type>::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(int j=0;j<MaxVertexes;j++){
   Arcs[p][j]=b;
   if(p==j)  {Arcs[p][j]=0;}
  }
  p++;
 }
 InDegree=new int[MaxVertexes];
    VTable=new VertexNode<Type>[MaxVertexes];//创建顶点表
    for(i=0;i<num;i++)             //输入各顶点信息
 {  InVertex(v[i]);            //在顶点表中插入顶点v[i]
  InDegree[i]=0;
 }
 cout<<"输入边的条数:";  cin >> e;//输入边的条数
 cout<<endl;
 for(i=0;i< e;i++){             //逐条输入边
  cout<<"输入第"<<i+1<<"条边:(弧头,弧尾,权值)";  
  cin>>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<<endl;
 } 
}
template<class Type>Type Graph<Type>::
GetValue(int v){                 //取图中顶点v的值,如果顶点v不存在,则返回空
 if(v>=0&&v<CurrentNumVertexes) return VTable[v].data;
 return NULL;
}
template<class Type>int Graph<Type>::
Getweight(int v1,int v2)
{//取出以顶点v1和v2为两端点的边上的权值
 if(v1>=0&&v1<CurrentNumVertexes&&v2>=0&&v2<CurrentNumVertexes){
      ArcNode *p=VTable[v1].firstarc;
   while(p!=NULL){
    if(p->adjvex==v2)  {return p->weight;}
    else               {p=p->nextarc;    }
   }
 } return NULL;
}
template<class Type>int Graph<Type>::
GetFirstNeighbor(int v){//查找顶点v的第一个邻接顶点的位置
 if(v>=0&&v<CurrentNumVertexes){   
       ArcNode *p=VTable[v].firstarc;
    if(p!=NULL)  return p->adjvex; 
    } 
 return -1;     
}
template<class Type>int Graph<Type>::
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
}

[1] [2] 下一页

数据结构课程设计C++图邻接矩阵-邻接表的建立下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©lwfree.cn 六维论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。