1-104.c

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

 Status InsertArc(OLGraph *G,VertexType v,VertexType w)
 { /* 初始条件: 有向图G存在,v和w是G中两个顶点 */
   /* 操作结果: 在G中增添弧<v,w> */
   int i,j;
   int IncInfo;
   char str[MAX_Info];
   ArcBox *p;
   i=LocateVex(*G,v); /* 弧尾的序号 */
   j=LocateVex(*G,w); /* 弧头的序号 */
   if(i<0||j<0)
     return ERROR;
   p=(ArcBox *)malloc(sizeof(ArcBox)); /* 生成新结点 */
   p->tailvex=i; /* 给新结点赋值 */
   p->headvex=j;
   p->hlink=(*G). xlist[j].firstin; /* 插在入弧和出弧的链头 */
   p->tlink=(*G). xlist[i].firstout;
   (*G). xlist[j].firstin=(*G). xlist[i].firstout=p;
   (*G). arcnum++; /* 弧数加1 */
   printf("要插入的弧是否含有其它信息(是: 1,否: 0): ");
   scanf("%d",&IncInfo);
   if(IncInfo)
   {
     printf("请输入该弧的相关信息(<%d个字符): ",MAX_Info);
     scanf("%s",str);
     p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
     strcpy(p->info,str);
   }
   else
     p->info=NULL;
   return OK;
 }

 Status DeleteArc(OLGraph *G,VertexType v,VertexType w)
 { /* 初始条件: 有向图G存在,v和w是G中两个顶点 */
   /* 操作结果: 在G中删除弧<v,w> */
   int i,j;
   ArcBox *p1,*p2;
   i=LocateVex(*G,v); /* 弧尾的序号 */
   j=LocateVex(*G,w); /* 弧头的序号 */
   if(i<0||j<0||i==j)
     return ERROR;
   p2=(*G). xlist[i].firstout; /* 将弧结点从出弧链表中删去 */
   if(p2&&p2->headvex==j) /* 第1个结点为待删除结点 */
     (*G). xlist[i].firstout=p2->tlink;
   else
   {
     while(p2&&p2->headvex!=j) /* 向后找 */
     {
       p1=p2;
       p2=p2->tlink;
     }
     if(p2) /* 没到表尾 */
       p1->tlink=p2->tlink;
   }
   p2=(*G). xlist[j].firstin; /* 将弧结点从入弧链表中删去 */
   if(p2&&p2->tailvex==i)
     (*G). xlist[j].firstin=p2->hlink;
   else
   {
     while(p2&&p2->tailvex!=i)
     {
       p1=p2;
       p2=p2->hlink;
     }
     if(p2) /* 没到表尾 */
       p1->hlink=p2->hlink;
   }
   if(p2->info) /* 释放弧结点 */
     free(p2->info);
   free(p2);
   (*G). arcnum--; /* 弧数减1 */
   return OK;
 }

 Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组 */
 Status(*VisitFunc)(VertexType); /* 函数变量 */
 void DFS(OLGraph G,int i) /* DFSTraverse()调用 */
 {
   ArcBox *p;
   visited[i]=TRUE; /* 访问标志数组置1(已被访问) */
   VisitFunc(G.xlist[i].data); /* 遍历第i个顶点 */
   p=G.xlist[i].firstout; /* p指向第i个顶点的出度 */
   while(p&&visited[p->headvex]) /* p没到表尾且该弧的头顶点已被访问 */
     p=p->tlink; /* 查找下一个结点 */
   if(p&&!visited[p->headvex]) /* 该弧的头顶点未被访问 */
     DFS(G,p->headvex); /* 递归调用DFS() */
 }

 void DFSTraverse(OLGraph G,Status(*Visit)(VertexType))
 { /* 初始条件: 有向图G存在,v是G中某个顶点,Visit是顶点的应用函数 */
   /* 操作结果: 从第1个顶点起,按深度优先递归遍历有向图G,并对每个顶点调用 */
   /*           函数Visit一次且仅一次。一旦Visit()失败,则操作失败 */
   int i;
   for(i=0;i<G.vexnum;i++)
     visited[i]=FALSE; /* 访问标志数组置初值(未被访问) */
   VisitFunc=Visit;
   for(i=0;i<G.vexnum;i++) /* 由序号0开始,继续查找未被访问过的顶点 */
     if(!visited[i])
       DFS(G,i);
   printf("\n");
 }

 typedef int QElemType;
 /* c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列) */
 #define MAXQSIZE 5 /* 最大队列长度(对于循环队列，最大队列长度要减1) */
 typedef struct
 {
   QElemType *base; /* 初始化的动态分配存储空间 */
   int front; /* 头指针,若队列不空,指向队列头元素 */
   int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
 }SqQueue;
 /* bo3-3.c 循环队列(存储结构由c3-3.h定义)的基本操作(9个) */
 Status InitQueue(SqQueue *Q)
 { /* 构造一个空队列Q */
   (*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
   if(!(*Q).base) /* 存储分配失败 */
     exit(OVERFLOW);
   (*Q).front=(*Q).rear=0;
   return OK;
 }
 Status QueueEmpty(SqQueue Q)
 { /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
   if(Q.front==Q.rear) /* 队列空的标志 */
     return TRUE;
   else
     return FALSE;
 }
 Status EnQueue(SqQueue *Q,QElemType e)
 { /* 插入元素e为Q的新的队尾元素 */
   if(((*Q).rear+1)%MAXQSIZE==(*Q).front) /* 队列满 */
     return ERROR;
   (*Q).base[(*Q).rear]=e;
   (*Q).rear=((*Q).rear+1)%MAXQSIZE;
   return OK;
 }

 Status DeQueue(SqQueue *Q,QElemType *e)
 { /* 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR */
   if((*Q).front==(*Q).rear) /* 队列空 */
     return ERROR;
   *e=(*Q).base[(*Q).front];
   (*Q).front=((*Q).front+1)%MAXQSIZE;
   return OK;
 }
 void BFSTraverse(OLGraph G,Status(*Visit)(VertexType))
 { /* 初始条件: 有向图G存在,Visit是顶点的应用函数。算法7.6 */
   /* 操作结果: 从第1个顶点起,按广度优先非递归遍历有向图G,并对每个顶点调用 */
   /*           函数Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
   /*           使用辅助队列Q和访问标志数组visited */
   int v,u,w;
   VertexType u1,w1;
   SqQueue Q;
   for(v=0;v<G.vexnum;v++)
     visited[v]=FALSE;
   InitQueue(&Q);
   for(v=0;v<G.vexnum;v++)
     if(!visited[v])
     {
       visited[v]=TRUE;
       Visit(G.xlist[v].data);
       EnQueue(&Q,v);
       while(!QueueEmpty(Q))
       {
         DeQueue(&Q,&u);
         strcpy(u1,*GetVex(G,u));
         for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
           if(!visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
           {
             visited[w]=TRUE;
             Visit(G.xlist[w].data);
             EnQueue(&Q,w);
           }
       }
     }
   printf("\n");
 }

 void Display(OLGraph G)
 { /* 输出有向图G */
   int i;
   ArcBox *p;
   printf("共%d个顶点,%d条弧:\n",G.vexnum,G.arcnum);
   for(i=0;i<G.vexnum;i++)
   {
     printf("顶点%s: 入度: ",G.xlist[i].data);
     p=G.xlist[i].firstin;
     while(p)
     {
       printf("%s ",G.xlist[p->tailvex].data);
       p=p->hlink;
     }
     printf("出度: ");
     p=G.xlist[i].firstout;
     while(p)
     {
       printf("%s ",G.xlist[p->headvex].data);
       if(p->info) /* 该弧有相关信息 */
         printf("弧信息: %s ",p->info);
       p=p->tlink;
     }
     printf("\n");
   }
 }
 Status visit(VertexType v)
 {
   printf("%s ",v);
   return OK;
 }

 void main()
 {
   int j,k,n;
   OLGraph g;
   VertexType v1,v2;
   CreateDG(&g);
   Display(g);
   printf("修改顶点的值，请输入原值 新值: ");
   scanf("%s%s",v1,v2);
   PutVex(&g,v1,v2);
   printf("插入新顶点，请输入顶点的值: ");
   scanf("%s",v1);
   InsertVex(&g,v1);
   printf("插入与新顶点有关的弧，请输入弧数: ");
   scanf("%d",&n);
   for(k=0;k<n;k++)
   {
     printf("请输入另一顶点的值 另一顶点的方向(0:弧头 1:弧尾): ");
     scanf("%s%d",v2,&j);
     if(j)
       InsertArc(&g,v2,v1);
     else
       InsertArc(&g,v1,v2);
   }
   Display(g);
   printf("删除一条弧，请输入待删除弧的弧尾 弧头：");
   scanf("%s%s",v1,v2);
   DeleteArc(&g,v1,v2);
   Display(g);
   printf("删除顶点及相关的弧，请输入顶点的值: ");
   scanf("%s",v1);
   DeleteVex(&g,v1);
   Display(g);
   printf("深度优先搜索的结果:\n");
   DFSTraverse(g,visit);
   printf("广度优先搜索的结果:\n");
   BFSTraverse(g,visit);
   DestroyGraph(&g);
 }