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

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

更新时间:2007-10-20:  来源:毕业论文

 

template<class Type>int Graph<Type>::
InsertArc(int v1,int v2,int w)
{//在图中插入弧<v1,v2>
  if(v1>=0&&v1<CurrentNumVertexes){
   Arcs[v1][v2]=w;
   ArcNode *newnode =new ArcNode(v2,w);
   ArcNode *h=VTable[v1].firstarc;
   if(h!=NULL){  
    ArcNode *p=h;
    while(h!=NULL&&h->adjvex<v2){
     p=h;     h=h->nextarc;
    }
    newnode->nextarc=p->nextarc;
    p->nextarc=newnode;
    return 1;
   }  
   VTable[v1].firstarc=newnode;
   return 1;
  }   
  return -1;
}
template<class Type>int Graph<Type>::
InVertex(Type &v)
{//在图中插入顶点,插入成功则返回1,否则返回0
  if(CurrentNumVertexes<MaxVertexes-1){//若顶点表未满
   VTable[CurrentNumVertexes].data=v;
   VTable[CurrentNumVertexes].firstarc=NULL;
   CurrentNumVertexes++;           return 1;
  }
  return -1; 
}
///////////////////////////////////////////////////////////////////////
//以下是实验要求的函数
//输出邻接表
template<class Type>void Graph<Type>::link(){ 
 cout<<"输出邻接表:"<<endl;
 for(int i=0;i<CurrentNumVertexes;i++){   
  cout<<GetValue(i);
  int a=GetFirstNeighbor(i);
  if(a!=-1) cout<<"->"<<GetValue(a)<<Getweight(i,a);
  for(int j=a;j!=-1;j=a){
   a=GetNextNeighbor(i,j);
  if(a!=-1) cout<<"->"<<GetValue(a)<<Getweight(i,a);
  }
  cout<<endl;
 }
}
//拓扑排序
template<class type>void Graph<type>::
TopologicalOrder()

 int m=0;//m为输出的顶点数,初始值为0
 for(int i=0;i<CurrentNumVertexes;i++){
  for(int n=0;n<CurrentNumVertexes;n++){
   if(InDegree[n]==0){
    m++;//输出的顶点数加1 
    cout<<VTable[n].data<<endl;
    InDegree[n]=-1;
    for(int t=0;t<CurrentNumVertexes;t++){
     if(n>=0&&n<CurrentNumVertexes){
      if(t>=0&&t<CurrentNumVertexes){
       if(Arcs[n][t]!=0&&Arcs[n][t]!=b)
                      InDegree[t]--;
      }
     }  
                 }
    for(int h=0;h<CurrentNumVertexes;h++){
     cout<<InDegree[h]<<"  ";
    }  cout<<endl;        break; 
   }
  }
 }
 if(m<CurrentNumVertexes)  cout<<"AOV网络中有回路(有向环)!"<<endl;
}
//深度遍历
template<class Type>
void Graph<Type>::
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 的所有邻接顶点
}
template<class Type>
void Graph <Type> ::
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 
}
//求最短路径
template<class Type>void Graph<Type>::
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<n;j++){
  dist[j]=Arcs[v][j];         s[j]=0;
  if(j!=v&&dist[j]<MaxVertexes) path[j]=v;
  else path[j]=-1;           s[v]=1;
 }
 for(int i=0;i<=n-1;i++){
  min=MaxVertexes;      u=v;
  for(int j=0;j<n;j++)
   if(!s[j]&&dist[j]<min){
    u=j;    min=dist[j];
   }
   s[u]=1;
   for(int w=0;w<n;w++)
     if(!s[w]&&dist[u]+Arcs[u][w]<dist[w])
     {
      dist[w]=dist[u]+Arcs[u][w];
      path[w]=u;
     }
     if(v!=i&&dist[i]!=10000&&v!=path[i])
     cout<<GetValue(v)<<"到顶点"<<GetValue(i)<<"的最短路径是:"<<GetValue(v)<<GetValue(path[i])<<GetValue(i)<<endl;
                    else if(v!=i&&dist[i]!=10000)
                    cout<<GetValue(v)<<"到顶点"<<GetValue(i)<<"的最短路径是:"<<GetValue(path[i])<<GetValue(i)<<endl;
  }
       for(int m=0;m<n;m++)
  cout<<GetValue(v)<<"到顶点"<<GetValue(m)<<"的最短路径长度是:"<<dist[m]<<endl;

}
//主函数
void main(){
 
 char op;
 do{
  int m,i=0,j=0,w;
     char a[20],c; 
  cout<<"请你输入顶点的个数:";   cin>>m;
  for(i=0;i<m;i++){
   cout<<"请输入第"<<j<<"个结点:";
   cin>>a[i]; cout<<endl;  j=j+1;
  }
  Graph<char>G(a,m);
  G.link();
  cout<<"深度遍历:"<<endl;
  G.DFTraverse();
  cout<<endl;
  cout<<"拓扑排序:"<<endl;    
  G.TopologicalOrder();
  cout<<endl;
  cout<<"输入最小路径的源头结点:"<<endl;
  cin>>c;
  w=G.GetVertexPos(c);
  G.ShortestPath(m,w);
loop:cout<<"是继续?(Y or N)"<<endl;
  cin>>op;
  if(op=='N'||op=='n')break;
  if(op!='Y'&&op!='y'&&op!='N'&&op!='n')goto loop;
 }while(op=='Y'||op=='y');
}

上一页  [1] [2] 

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

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