// bo7-3.cpp 有向圖的十字鏈表存儲(存儲結構由c7-3.h定義)的基本函數(15個)
 int LocateVex(OLGraph G,VertexType u)
 { // 返回頂點u在有向圖G中的位置(序號),如不存在則返回-1
   int i;
   for(i=0;i<G.vexnum;++i) // 用循環查找該結點
     if(!strcmp(G.xlist[i].data,u))
       return i;
   return -1;
 }

 Status CreateDG(OLGraph &G)
 { // 采用十字鏈表存儲表示,構造有向圖G。算法7.3
   int i,j,k;
   int IncInfo;
   char str[MAX_Info];
   ArcBox *p;
   VertexType v1,v2;
   printf("請輸入有向圖的頂點數,弧數,弧是否含其它信息(是:1，否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("請輸入%d個頂點的值(<%d個字符):\n",G.vexnum,MAX_VERTEX_NAME);
   for(i=0;i<G.vexnum;++i)
   { // 構造表頭向量
     scanf("%s",&G.xlist[i].data); // 輸入頂點值
     G.xlist[i].firstin=NULL; // 初始化指針
     G.xlist[i].firstout=NULL;
   }
   printf("請輸入%d條弧的弧尾和弧頭(空格為間隔):\n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   { // 輸入各弧并構造十字鏈表
     scanf("%s%s",&v1,&v2);
     i=LocateVex(G,v1); // 確定v1和v2在G中的位置
     j=LocateVex(G,v2);
     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;
     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;
 }

 void DestroyGraph(OLGraph &G)
 { // 初始條件: 有向圖G存在
   // 操作結果: 銷毀有向圖G
   int j;
   ArcBox *p,*q;
   for(j=0;j<G.vexnum;j++) // 對所有頂點
   {
     p=G.xlist[j].firstout; // 僅處理出弧
     while(p)
     {
       q=p;
       p=p->tlink;
       if(q->info)
         free(q->info);
       free(q);
     }
   }
   G.arcnum=0;
   G.vexnum=0;
 }

 VertexType& GetVex(OLGraph G,int v)
 { // 初始條件:有向圖G存在,v是G中某個頂點的序號。操作結果:返回v的值
   if(v>=G.vexnum||v<0)
     exit(ERROR);
   return G.xlist[v].data;
 }

 Status PutVex(OLGraph &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.xlist[i].data,value);
   return OK;
 }

 int FirstAdjVex(OLGraph G,VertexType v)
 { // 初始條件: 有向圖G存在,v是G中某個頂點
   // 操作結果: 返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點,則返回-1
   int i;
   ArcBox *p;
   i=LocateVex(G,v);
   p=G.xlist[i].firstout; // p指向頂點v的第1個出弧
   if(p)
     return p->headvex;
   else
     return -1;
 }

 int NextAdjVex(OLGraph G,VertexType v,VertexType w)
 { // 初始條件: 有向圖G存在,v是G中某個頂點,w是v的鄰接頂點
   // 操作結果: 返回v的(相對于w的)下一個鄰接頂點的序號,
   //           若w是v的最后一個鄰接頂點,則返回-1
   int i,j;
   ArcBox *p;
   i=LocateVex(G,v); // i是頂點v的序號
   j=LocateVex(G,w); // j是頂點w的序號
   p=G.xlist[i].firstout; // p指向頂點v的第1個出弧
   while(p&&p->headvex!=j)
     p=p->tlink;
   if(p) // w不是v的最后一個鄰接頂點
     p=p->tlink; // p指向相對于w的下一個鄰接頂點
   if(p) // 有下一個鄰接頂點
     return p->headvex;
   else
     return -1;
 }

 void InsertVex(OLGraph &G,VertexType v)
 { // 初始條件: 有向圖G存在,v和有向圖G中頂點有相同特征
   // 操作結果: 在有向圖G中增添新頂點v(不增添與頂點相關的弧,留待InsertArc()去做)
   strcpy(G.xlist[G.vexnum].data,v);
   G.xlist[G.vexnum].firstin=G.xlist[G.vexnum].firstout=NULL;
   G.vexnum++;
 }

 Status DeleteVex(OLGraph &G,VertexType v)
 { // 初始條件: 有向圖G存在,v是G中某個頂點
   // 操作結果: 刪除G中頂點v及其相關的弧
   int j,k;
   ArcBox *p,*q;
   k=LocateVex(G,v); // k是頂點v的序號
   if(k<0) // v不是圖G的頂點
     return ERROR;
   // 以下刪除頂點v的出弧
   for(j=0;j<G.vexnum;j++) // 頂點v的出弧是其它頂點的入弧
   {
     if(j==k)
       continue;
     p=G.xlist[j].firstin; // 在其它頂點的入弧鏈表中刪除頂點v的出弧
     while(p)
       if(p->tailvex==k&&p==G.xlist[j].firstin) // 待刪結點為首結點
       {
         G.xlist[j].firstin=p->hlink;
         break;
       }
       else if(p->tailvex!=k) // 沒找到待刪結點
       {
         q=p;
         p=p->hlink;
       }
       else // 找到待刪結點且不是首結點
       {
         q->hlink=p->hlink;
         break;
       }
   }
   p=G.xlist[k].firstout; // 刪除與頂點v有關的出弧
   while(p)
   {
     q=p->tlink; // q指向p的下一個出弧
     if(p->info) // 釋放p
       free(p->info);
     free(p);
     G.arcnum--;
     p=q;
   }
   // 以下刪除頂點v的入弧
   for(j=0;j<G.vexnum;j++) // 頂點v的入弧是其它頂點的出弧
   {
     if(j==k)
       continue;
     p=G.xlist[j].firstout; // 在其它頂點的出弧鏈表中刪除頂點v的入弧
     while(p)
       if(p->headvex==k&&p==G.xlist[j].firstout) // 待刪結點為首結點
       {
         G.xlist[j].firstout=p->tlink;
         break;
       }
       else if(p->headvex!=k) // 沒找到待刪結點
       {
         q=p;
         p=p->tlink;
       }
       else // 找到待刪結點且不是首結點
       {
	 q->tlink=p->tlink;
         break;
       }
   }
   p=G.xlist[k].firstin; // 刪除與頂點v有關的入弧
   while(p)
   {
     q=p->hlink; // q指向p的下一個入弧
     if(p->info) // 釋放p
       free(p->info);
     free(p);
     G.arcnum--;
     p=q;
   }
   for(j=k+1;j<G.vexnum;j++) // 序號>k的頂點依次向前移
     G.xlist[j-1]=G.xlist[j];
   G.vexnum--; // 頂點數減1
   for(j=0;j<G.vexnum;j++) // 結點序號>k的要減1
   {
     p=G.xlist[j].firstout; // 處理出弧
     while(p)
     {
       if(p->tailvex>k)
         p->tailvex--; // 序號-1
       if(p->headvex>k)
         p->headvex--; // 序號-1
       p=p->tlink;
     }
   }
   return OK;
 }

 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;
 #include"c3-3.h"
 #include"bo3-3.cpp"
 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");
   }
 }