gra_ol.cpp

数据结构中所有算法的实现

#include "d:\cpp\head.h"
#define MAX_VERTEX_NUM 20
typedef char VertexType;
typedef struct ArcBox{
  int tailvex,headvex;
  struct ArcBox *hlink,*tlink;
  //InfoType *info;
}ArcBox;
typedef struct VexNode{
  VertexType data;
  ArcBox *firstin,*firstout;
}VexNode;
typedef struct{
  VexNode xlist[MAX_VERTEX_NUM];
  int vexnum,arcnum;
}OLGraph;
Status CreateDG(OLGraph &G){
  int i,j,k;
  char t,v1,v2;
  ArcBox *p;
  printf("Input the number of vexnum,arcnum:");
  scanf("%d,%d",&G.vexnum,&G.arcnum);scanf("%c",&t);
  printf("Input %d ge vertex:",G.vexnum);
  for(i=0;i<G.vexnum;++i){
    scanf("%c",&G.xlist[i].data);
    G.xlist[i].firstin=G.xlist[i].firstout=NULL;
  }//for
  scanf("%c",&t);
  for(k=0;k<G.arcnum;++k){
    printf("Input di %d tiao bian v1,v2:",k);
    scanf("%c,%c",&v1,&v2); scanf("%c",&t);
    for(i=0;i<G.vexnum;++i)if(G.xlist[i].data==v1)break;
    for(j=0;j<G.vexnum;++j)if(G.xlist[j].data==v2)break;
    p=(ArcBox*)malloc(sizeof(ArcBox));
    p->tailvex=i;
    p->headvex=j;
    p->hlink=G.xlist[j].firstin;
    p->tlink=G.xlist[i].firstout;
    //p->info=NULL;
    G.xlist[j].firstin=G.xlist[i].firstout=p;
  }//for
  return OK;
}//CreateDG
int InDegree(OLGraph G,VertexType v){
  int i,d;
  ArcBox *p;
  for(i=0;i<G.vexnum;++i)if(G.xlist[i].data==v)break;
  p=G.xlist[i].firstin;
  d=0;
  while(p){
      p=p->hlink;
      d++;
  }//while
  return d;
}//InDegree
void main(){
  OLGraph G;
  CreateDG(G);
  printf("\n--------%d",InDegree(G,'4'));
}//main