1-105.c

1.7.1 图的邻接矩阵存储表示 311 范例1-102 图的邻接矩阵存储表示 ∷相关函数：CreateFAG函数 CreateDG函数 1.7.2 图的邻接表存储表示 324 范例1-10

#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 80 /* 相关信息字符串的最大长度+1 */
typedef char InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
#define MAX_VERTEX_NUM 20
typedef enum{unvisited,visited}VisitIf;
typedef struct EBox
{
  VisitIf mark; /* 访问标记 */
  int ivex,jvex; /* 该边依附的两个顶点的位置 */
  struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */
  InfoType *info; /* 该边信息指针 */
}EBox;
typedef struct
{
  VertexType data;
  EBox *firstedge; /* 指向第一条依附该顶点的边 */
}VexBox;
typedef struct
{
  VexBox adjmulist[MAX_VERTEX_NUM];
  int vexnum,edgenum; /* 无向图的当前顶点数和边数 */
}AMLGraph;
int LocateVex(AMLGraph G,VertexType u)
{ /* 初始条件: 无向图G存在,u和G中顶点有相同特征 */
  /* 操作结果: 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1 */
  int i;
  for(i=0;i<G.vexnum;++i)
    if(strcmp(u,G.adjmulist[i].data)==0)
      return i;
  return -1;
}
Status CreateGraph(AMLGraph *G)
{ /* 采用邻接多重表存储结构,构造无向图G */
  int i,j,k,l,IncInfo;
  char s[MAX_INFO];
  VertexType va,vb;
  EBox *p;
  printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1，否:0): ");
  scanf("%d,%d,%d",&(*G).vexnum,&(*G).edgenum,&IncInfo);
  printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
  for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
  {
    scanf("%s",(*G).adjmulist[i].data);
    (*G).adjmulist[i].firstedge=NULL;
  }
  printf("请顺序输入每条边的两个端点(以空格作为间隔):\n");
  for(k=0;k<(*G).edgenum;++k) /* 构造表结点链表 */
  {
    scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
    i=LocateVex(*G,va); /* 一端 */
    j=LocateVex(*G,vb); /* 另一端 */
    p=(EBox*)malloc(sizeof(EBox));
    p->mark=unvisited; /* 设初值 */
    p->ivex=i;
    p->jvex=j;
    p->info=NULL;
    p->ilink=(*G).adjmulist[i].firstedge; /* 插在表头 */
    (*G).adjmulist[i].firstedge=p;
    p->jlink=(*G).adjmulist[j].firstedge; /* 插在表头 */
    (*G).adjmulist[j].firstedge=p;
    if(IncInfo) /* 边有相关信息 */
    {
      printf("请输入该弧的相关信息(<%d个字符)：",MAX_INFO);
      gets(s);
      l=strlen(s);
      if(l)
      {
        p->info=(char*)malloc((l+1)*sizeof(char));
        strcpy(p->info,s);
      }
    }
  }
  return OK;
}
VertexType* GetVex(AMLGraph G,int v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
  if(v>=G.vexnum||v<0)
    exit(ERROR);
  return &G.adjmulist[v].data;
}
Status PutVex(AMLGraph *G,VertexType v,VertexType value)
{ /* 初始条件: 无向图G存在,v是G中某个顶点 */
  /* 操作结果: 对v赋新值value */
  int i;
  i=LocateVex(*G,v);
  if(i<0) /* v不是G的顶点 */
    return ERROR;
  strcpy((*G).adjmulist[i].data,value);
  return OK;
}

int FirstAdjVex(AMLGraph G,VertexType v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点 */
  /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
  int i;
  i=LocateVex(G,v);
  if(i<0)
    return -1;
  if(G.adjmulist[i].firstedge) /* v有邻接顶点 */
    if(G.adjmulist[i].firstedge->ivex==i)
      return G.adjmulist[i].firstedge->jvex;
    else
      return G.adjmulist[i].firstedge->ivex;
  else
    return -1;
}

int NextAdjVex(AMLGraph G,VertexType v,VertexType w)
{ /* 初始条件: 无向图G存在,v是G中某个顶点,w是v的邻接顶点 */
  /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
  /*           若w是v的最后一个邻接点,则返回-1 */
  int i,j;
  EBox *p;
  i=LocateVex(G,v); /* i是顶点v的序号 */
  j=LocateVex(G,w); /* j是顶点w的序号 */
  if(i<0||j<0) /* v或w不是G的顶点 */
    return -1;
  p=G.adjmulist[i].firstedge; /* p指向顶点v的第1条边 */
  while(p)
    if(p->ivex==i&&p->jvex!=j) /* 不是邻接顶点w(情况1) */
      p=p->ilink; /* 找下一个邻接顶点 */
    else if(p->jvex==i&&p->ivex!=j) /* 不是邻接顶点w(情况2) */
      p=p->jlink; /* 找下一个邻接顶点 */
    else /* 是邻接顶点w */
      break;
  if(p&&p->ivex==i&&p->jvex==j) /* 找到邻接顶点w(情况1) */
  {
    p=p->ilink;
    if(p&&p->ivex==i)
      return p->jvex;
    else if(p&&p->jvex==i)
      return p->ivex;
  }
  if(p&&p->ivex==j&&p->jvex==i) /* 找到邻接顶点w(情况2) */
  {
    p=p->jlink;
    if(p&&p->ivex==i)
      return p->jvex;
    else if(p&&p->jvex==i)
      return p->ivex;
  }
  return -1;
}

Status InsertVex(AMLGraph *G,VertexType v)
{ /* 初始条件: 无向图G存在,v和G中顶点有相同特征 */
  /* 操作结果: 在G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
  if((*G).vexnum==MAX_VERTEX_NUM) /* 结点已满，不能插入 */
    return ERROR;
  if(LocateVex(*G,v)>=0) /* 结点已存在,不能插入 */
    return ERROR;
  strcpy((*G).adjmulist[(*G).vexnum].data,v);
  (*G).adjmulist[(*G).vexnum].firstedge=NULL;
  (*G).vexnum++;
  return OK;
}

Status DeleteArc(AMLGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 无向图G存在,v和w是G中两个顶点 */
  /* 操作结果: 在G中删除弧<v,w> */
  int i,j;
  EBox *p,*q;
  i=LocateVex(*G,v);
  j=LocateVex(*G,w);
  if(i<0||j<0||i==j)
    return ERROR;  /* 图中没有该点或弧 */
  /* 以下使指向待删除边的第1个指针绕过这条边 */
  p=(*G).adjmulist[i].firstedge; /* p指向顶点v的第1条边 */
  if(p&&p->jvex==j) /* 第1条边即为待删除边(情况1) */
    (*G).adjmulist[i].firstedge=p->ilink;
  else if(p&&p->ivex==j) /* 第1条边即为待删除边(情况2) */
    (*G).adjmulist[i].firstedge=p->jlink;
  else /* 第1条边不是待删除边 */
  {
    while(p) /* 向后查找弧<v,w> */
    {
      if(p->ivex==i&&p->jvex!=j) /* 不是待删除边 */
      {
        q=p;
        p=p->ilink; /* 找下一个邻接顶点 */
      }
      else if(p->jvex==i&&p->ivex!=j) /* 不是待删除边 */
      {
        q=p;
        p=p->jlink; /* 找下一个邻接顶点 */
      }
      else /* 是邻接顶点w */
        break;
    }
    if(!p) /* 没找到该边 */
      return ERROR;
    if(p->ivex==i&&p->jvex==j) /* 找到弧<v,w>(情况1) */
      if(q->ivex==i)
        q->ilink=p->ilink;
      else
        q->jlink=p->ilink;
    else if(p->ivex==j&&p->jvex==i) /* 找到弧<v,w>(情况2) */
      if(q->ivex==i)
        q->ilink=p->jlink;
      else
        q->jlink=p->jlink;
  }
  /* 以下由另一顶点起找待删除边且删除之 */
  p=(*G).adjmulist[j].firstedge; /* p指向顶点w的第1条边 */
  if(p->jvex==i) /* 第1条边即为待删除边(情况1) */
  {
    (*G).adjmulist[j].firstedge=p->ilink;
    if(p->info) /* 有相关信息 */
      free(p->info);
    free(p);
  }
  else if(p->ivex==i) /* 第1条边即为待删除边(情况2) */
  {
    (*G).adjmulist[j].firstedge=p->jlink;
    if(p->info) /* 有相关信息 */
      free(p->info);
    free(p);
  }
  else /* 第1条边不是待删除边 */
  {
    while(p) /* 向后查找弧<v,w> */
      if(p->ivex==j&&p->jvex!=i) /* 不是待删除边 */
      {
        q=p;
        p=p->ilink; /* 找下一个邻接顶点 */
      }
      else if(p->jvex==j&&p->ivex!=i) /* 不是待删除边 */
      {
        q=p;
        p=p->jlink; /* 找下一个邻接顶点 */
      }
      else /* 是邻接顶点v */
        break;
    if(p->ivex==i&&p->jvex==j) /* 找到弧<v,w>(情况1) */
    {
      if(q->ivex==j)
        q->ilink=p->jlink;
      else
        q->jlink=p->jlink;
      if(p->info) /* 有相关信息 */
        free(p->info);
      free(p);
    }
    else if(p->ivex==j&&p->jvex==i) /* 找到弧<v,w>(情况2) */
    {
      if(q->ivex==j)
        q->ilink=p->ilink;
      else
        q->jlink=p->ilink;
      if(p->info) /* 有相关信息 */
        free(p->info);
      free(p);
    }
  }
  (*G).edgenum--;
  return OK;
}

Status DeleteVex(AMLGraph *G,VertexType v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点 */
  /* 操作结果: 删除G中顶点v及其相关的边 */
  int i,j;
  VertexType w;
  EBox *p;