// bo7-2.cpp 圖的鄰接表存儲(存儲結構由c7-21.h定義)的基本操作(14個)
 #include"bo2-3.cpp" // 不帶頭結點的單鏈表基本操作
 #include"func2-4.cpp" // 不帶頭結點的單鏈表擴展操作
 int LocateVex(ALGraph G,VertexType u)
 { // 初始條件：圖G存在，u和G中頂點有相同特征(頂點名稱相同)
   // 操作結果：若G中存在頂點u，則返回該頂點在圖中位置(序號)；否則返回-1
   int i;
   for(i=0;i<G.vexnum;++i) // 對于所有頂點依次查找
     if(strcmp(u.name,G.vertices[i].data.name)==0) // 頂點與給定的u的頂點名稱相同
       return i; // 返回頂點序號
   return -1; // 圖G中不存在與頂點u有相同名稱的頂點
 }

 void CreateGraph(ALGraph &G)
 { // 采用鄰接表存儲結構，構造圖或網G(用一個函數構造4種圖)
   int i,j,k;
   VertexType v1,v2; // 頂點類型
   ElemType e; // 表結點的元素類型(存儲弧的信息)
   char s[3]="邊";
   printf("請輸入圖的類型(有向圖：0 有向網：1 無向圖：2 無向網：3)：");
   scanf("%d",&G.kind);
   if(G.kind<2) // 有向
     strcpy(s,"弧");
   printf("請輸入圖的頂點數,邊數：");
   scanf("%d,%d",&G.vexnum,&G.arcnum);
   printf("請輸入%d個頂點的值(名稱<%d個字符)：\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 構造頂點向量
   { Input(G.vertices[i].data); // 輸入頂點信息
     G.vertices[i].firstarc=NULL; // 初始化與該頂點有關的出弧鏈表
   }
   printf("請輸入%d條%s的",G.arcnum,s);
   switch(G.kind)
   { case  DG:printf("弧尾 弧頭：\n"); // 設圖沒有弧(邊)信息
              break;
     case  DN:printf("弧尾 弧頭 弧的信息：\n");
              break;
     case UDG:printf("頂點1 頂點2：\n"); // 設圖沒有弧(邊)信息
              break;
     case UDN:printf("頂點1 頂點2 邊的信息：\n");
   }
   for(k=0;k<G.arcnum;++k) // 構造相關弧鏈表
   { scanf("%s%s",v1.name,v2.name); // 輸入2頂點名稱
     i=LocateVex(G,v1); // 弧尾
     j=LocateVex(G,v2); // 弧頭
     e.info=NULL; // 給待插表結點e賦值，設圖無弧(邊)信息
     if(G.kind%2) // 網
       InputArc(e.info); // 動態生成存儲空間，輸入弧的相關信息，在func7-4.cpp中
     e.adjvex=j; // 弧頭
     ListInsert(G.vertices[i].firstarc,1,e);
     // 將e插在第i個元素(出弧)的表頭，在bo2-3.cpp中
     if(G.kind>=2) // 無向圖或網，產生第2個表結點，并插在第j個元素(入弧)的表頭
     { e.adjvex=i; // e.info不變，不必再賦值
       ListInsert(G.vertices[j].firstarc,1,e); // 插在第j個元素的表頭，在bo2-3.cpp中
     }
   }
 }

 void CreateFromFile(ALGraph &G,char* filename)
 { // 采用鄰接表存儲結構，由文件構造圖或網G(用一個函數構造4種圖)
   int i,j,k;
   VertexType v1,v2; // 頂點類型
   ElemType e; // 表結點的元素類型(存儲弧的信息)
   FILE *f; // 文件指針類型
   f=fopen(filename,"r"); // 以讀的方式打開數據文件，并以f表示
   fscanf(f,"%d",&G.kind); // 由文件輸入G的類型
   fscanf(f,"%d",&G.vexnum); // 由文件輸入G的頂點數
   for(i=0;i<G.vexnum;++i) // 構造頂點向量
   { InputFromFile(f,G.vertices[i].data); // 由文件輸入頂點信息
     G.vertices[i].firstarc=NULL; // 初始化與該頂點有關的出弧鏈表
   }
   fscanf(f,"%d",&G.arcnum); // 由文件輸入G的弧(邊)數
   for(k=0;k<G.arcnum;++k) // 構造相關弧鏈表
   { fscanf(f,"%s%s",v1.name,v2.name); // 由文件輸入2頂點名稱
     i=LocateVex(G,v1); // 弧尾
     j=LocateVex(G,v2); // 弧頭
     e.info=NULL; // 給待插表結點e賦值，設圖無弧(邊)信息
     if(G.kind%2) // 網
       InputArcFromFile(f,e.info);
       // 動態生成存儲空間，由文件輸入弧的相關信息，在func7-4.cpp中
     e.adjvex=j; // 弧頭
     ListInsert(G.vertices[i].firstarc,1,e);
     // 將e插在第i個元素(出弧)的表頭，在bo2-3.cpp中
     if(G.kind>=2) // 無向圖或網，產生第2個表結點，并插在第j個元素(入弧)的表頭
     { e.adjvex=i; // e.info不變，不必再賦值
       ListInsert(G.vertices[j].firstarc,1,e); // 插在第j個元素的表頭，在bo2-3.cpp中
     }
   }
   fclose(f); // 關閉數據文件
 }

 VertexType GetVex(ALGraph G,int v)
 { // 初始條件：圖G存在，v是G中某個頂點的序號。操作結果：返回v的值
   if(v>=G.vexnum||v<0) // 圖G中不存在序號為v的頂點
     exit(OVERFLOW);
   return G.vertices[v].data; // 返回該頂點的信息
 }

 Status PutVex(ALGraph &G,VertexType v,VertexType value)
 { // 初始條件：圖G存在，v是G中某個頂點。操作結果：對v賦新值value
   int k=LocateVex(G,v); // k為頂點v在圖G中的序號
   if(k!=-1) // v是G的頂點
   { G.vertices[k].data=value; // 將新值賦給頂點v(其序號為k)
     return OK;
   }
   return ERROR; // v不是G的頂點
 }

 int FirstAdjVex(ALGraph G,int v)
 { // 初始條件：圖G存在，v是G中某個頂點的序號
   // 操作結果：返回v的第1個鄰接頂點的序號。若頂點在G中沒有鄰接頂點，則返回-1
   ArcNode *p=G.vertices[v].firstarc; // p指向頂點v的第1個鄰接頂點
   if(p) // 頂點v有鄰接頂點
     return p->data.adjvex; // 返回v的第1個鄰接頂點的序號
   else
     return -1; // 頂點v沒有鄰接頂點
 }

 Status equalvex(ElemType a,ElemType b)
 { // DeleteArc()、DeleteVex()和NextAdjVex()要調用的函數
   if(a.adjvex==b.adjvex) // 表結點的頂位置(序號)相同
     return OK;
   else
     return ERROR;
 }

 int NextAdjVex(ALGraph G,int v,int w)
 { // 初始條件：圖G存在，v是G中某個頂點的序號，w是v的鄰接頂點的序號
   // 操作結果：返回v的(相對于w的)下一個鄰接頂點的序號。
   //           若w是v的最后一個鄰接頂點，則返回-1
   LinkList p,p1; // p1在Point()中用作輔助指針，Point()在func2-4.cpp中
   ElemType e; // 表結點的元素類型(存儲弧的信息)
   e.adjvex=w;
   p=Point(G.vertices[v].firstarc,e,equalvex,p1);
   // p指向頂點v的鏈表中鄰接頂點為w的結點
   if(!p||!p->next) // 未找到w或w是最后一個鄰接點
     return -1;
   else // p->data.adjvex==w
     return p->next->data.adjvex; // 返回v的(相對于w的)下一個鄰接頂點的序號
 }

 void InsertVex(ALGraph &G,VertexType v)
 { // 初始條件：圖G存在，v和圖中頂點有相同特征
   // 操作結果：在圖G中增添新頂點v(不增添與頂點相關的弧，留待InsertArc()去做)
   G.vertices[G.vexnum].data=v; // 構造新頂點向量
   G.vertices[G.vexnum].firstarc=NULL; // 沒有與頂點相關的弧
   G.vexnum++; // 圖G的頂點數加1
 }

 Status InsertArc(ALGraph &G,VertexType v,VertexType w)
 { // 初始條件：圖G存在，v和w是G中兩個頂點
   // 操作結果：在G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>
   ElemType e; // 表結點的元素類型(存儲弧的信息)
   int i,j;
   char s1[3]="邊",s2[3]="—"; // 無向的情況
   if(G.kind<2) // 有向
   { strcpy(s1,"弧");
     strcpy(s2,"→");
   }
   i=LocateVex(G,v); // 弧尾或邊的序號
   j=LocateVex(G,w); // 弧頭或邊的序號
   if(i<0||j<0) // v和w至少有1個不是G中的頂點
     return ERROR;
   G.arcnum++; // 圖G的弧或邊的數目加1
   e.adjvex=j; // 弧頭表結點的值
   e.info=NULL; // 初值，設圖無弧(邊)信息
   if(G.kind%2) // 網
   { printf("請輸入%s%s%s%s的信息：",s1,v.name,s2,w.name);
     InputArc(e.info); // 動態生成存儲空間，輸入弧的相關信息，在func7-4.cpp中
   }
   ListInsert(G.vertices[i].firstarc,1,e); // 將e插在弧尾的表頭，在bo2-3.cpp中
   if(G.kind>=2) // 無向，生成另一個表結點
   { e.adjvex=i; // 弧尾表結點的值，e.info不變
     ListInsert(G.vertices[j].firstarc,1,e); // 將e插在弧頭的表頭
   }
   return OK;
 }

 Status DeleteArc(ALGraph &G,VertexType v,VertexType w)
 { // 初始條件：圖G存在，v和w是G中兩個頂點
   // 操作結果：在G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>
   int i,j,n;
   ElemType e; // 表結點的元素類型(存儲弧的信息)
   i=LocateVex(G,v); // i是頂點v(弧尾)的序號
   j=LocateVex(G,w); // j是頂點w(弧頭)的序號
   if(i<0||j<0||i==j) // v和w至少有1個不是G中的頂點，或v和w是G中的同一個頂點
     return ERROR;
   e.adjvex=j; // 弧頭表結點的值
   n=LocateElem(G.vertices[i].firstarc,e,equalvex);
   // 在弧尾鏈表中找弧頭表結點，將其在鏈表中的位序賦給n
   if(n) // 存在該弧
   { ListDelete(G.vertices[i].firstarc,n,e); // 在弧尾鏈表中刪除弧頭表結點，并用e返回其值
     G.arcnum--; // 弧或邊數減1
     if(G.kind%2) // 網，設圖無弧(邊)信息
       free(e.info); // 釋放動態生成的弧(邊)信息空間
     if(G.kind>=2) // 無向，刪除對稱弧<w,v>
     { e.adjvex=i; // 弧尾表結點的值
       n=LocateElem(G.vertices[j].firstarc,e,equalvex);
       // 在弧頭鏈表中找弧尾表結點，將其在鏈表中的位序賦給n
       ListDelete(G.vertices[j].firstarc,n,e);
       // 在弧頭鏈表中刪除弧尾表結點，并用e返回其值
     }
     return OK;
   }
   else // 未找到待刪除的弧
     return ERROR;
 }

 Status DeleteVex(ALGraph &G,VertexType v)
 { // 初始條件：圖G存在，v是G中某個頂點。操作結果：刪除G中頂點v及其相關的弧(邊)
   int i,k;
   LinkList p; // 表結點的指針類型
   k=LocateVex(G,v); // k為待刪除頂點v的序號
   if(k<0) // v不是圖G的頂點
     return ERROR;
   for(i=0;i<G.vexnum;i++)
     DeleteArc(G,v,G.vertices[i].data); // 刪除由頂點v發出的所有弧
   if(G.kind<2) // 有向
     for(i=0;i<G.vexnum;i++)
       DeleteArc(G,G.vertices[i].data,v); // 刪除發向頂點v的所有弧
   for(i=0;i<G.vexnum;i++) // 對于adjvex域>k的結點，其序號-1
   { p=G.vertices[i].firstarc; // p指向弧結點的單鏈表
     while(p) // 未到表尾
     { if(p->data.adjvex>k) // adjvex域>k
         p->data.adjvex--; // 序號-1(因為前移)
       p=p->next; // p指向下一個結點
     }
   }
   for(i=k+1;i<G.vexnum;i++)
     G.vertices[i-1]=G.vertices[i]; // 頂點v后面的頂點依次前移
   G.vexnum--; // 頂點數減1
   return OK;
 }

 void DestroyGraph(ALGraph &G)
 { // 初始條件：圖G存在。操作結果：銷毀圖G
   int i;
   for(i=G.vexnum-1;i>=0;i--) // 由大到小逐一刪除頂點及與其相關的弧(邊)
     DeleteVex(G,G.vertices[i].data);
 }
 
 void Display(ALGraph G)
 { // 輸出圖的鄰接矩陣G
   int i;
   ArcNode *p;
   char s1[3]="邊",s2[3]="—"; // 無向的情況
   if(G.kind<2) // 有向
   { strcpy(s1,"弧");
     strcpy(s2,"→");
   }
   switch(G.kind)
   { case  DG:printf("有向圖\n");
              break;
     case  DN:printf("有向網\n");
              break;
     case UDG:printf("無向圖\n");
              break;
     case UDN:printf("無向網\n");
   }
   printf("%d個頂點，依次是：",G.vexnum);
   for(i=0;i<G.vexnum;++i)
     Visit(GetVex(G,i)); // 根據頂點信息的類型，訪問第i個頂點，在func7-1.cpp中
   printf("\n%d條%s：\n",G.arcnum,s1);
   for(i=0;i<G.vexnum;i++)
   { p=G.vertices[i].firstarc; // p指向序號為i的頂點的第1條弧(邊)
     while(p) // p不為空
     { if(G.kind<=1||i<p->data.adjvex) // 有向或無向兩次中的一次
       { printf(" %s%s%s",G.vertices[i].data.name,s2,
         G.vertices[p->data.adjvex].data.name);
         if(G.kind%2) // 網
           OutputArc(p->data.info); // 輸出弧(邊)信息(包括權值)，在func7-4.cpp中
       }
       p=p->nextarc; // p指向下一個表結點
     }
     printf("\n");
   }
 }