Code666 (代码贴、代码片段)

[C++] 数据结构与算法----4.2 用数组存储图：1、插入一个顶点2、删除一条弧3、删 →→→→→进入此内容的聊天室

来自 , 2020-08-29, 写在 C++, 查看 170 次.
URL http://www.code666.cn/view/f8bf09f5
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. const int Infinity=-1;
  5. typedef char VexType;
  6. struct VexCell//顶点的信息
  7. {
  8.         VexType data;//顶点数据
  9.         bool visited;//是否被访问过
  10. };
  11. struct ArcCell//弧的信息(结构体)
  12. {
  13.         int adj;    
  14. };
  15. const MVN=21;
  16. struct MGraph
  17. {
  18.         VexCell vexs[MVN];//顶点数组
  19.         ArcCell arcs[MVN][MVN];//邻接矩阵
  20.         int kind,vexnum,arcnum;//类型，顶点数，弧数
  21. };
  22. int LocateVex(MGraph &G,VexType v);//查找顶点
  23. bool InsertVex(MGraph &G,VexType u);//插入顶点
  24. bool InsertArc(MGraph &G,VexType u,VexType v,int w=1);//插入弧
  25. bool DeleteArc(MGraph &G,VexType u,VexType v);//删除弧
  26. bool DeleteVex(MGraph &G,VexType v);//删除顶点
  27. void CreateGraph(MGraph&G,char fn[]);//建立图
  28. void Show(MGraph &G);
  29. int main()
  30. {
  31.        
  32.         int count1=0;
  33.         int count2=0;
  34.         MGraph G;
  35.         char fn[]="fn.txt";
  36.         CreateGraph(G,fn);
  37.         Show(G);
  38.         VexType x='s',y='a',z='b',f='a';
  39.         cout<<"插入顶点:"<<x<<endl;
  40.         InsertVex(G,x);
  41.         Show(G);
  42.         cout<<"删除弧的两个顶点:"<<y<<z<<endl;
  43.         DeleteArc(G,y,z);
  44.         Show(G);
  45.         cout<<"要删除的顶点："<<z<<endl;
  46.         DeleteVex(G,f);
  47.         Show(G);
  48.         return 0;
  49. }
  50.  
  51. bool InsertVex(MGraph&G,VexType u)
  52. {
  53.         int i;
  54.         if(G.vexnum+1>MVN)return false;
  55.         i=LocateVex(G,u);
  56.         if(i>0)return false;
  57.         G.vexnum++;
  58.         G.vexs[G.vexnum].data=u;
  59.         for(i=1;i<=G.vexnum;i++)
  60.                 G.arcs[i][G.vexnum].adj=G.arcs[G.vexnum][i].adj=Infinity;
  61.         return true;
  62. }
  63. bool InsertArc(MGraph&G,VexType u,VexType v,int w)
  64. {
  65.         int i,j;
  66.         i=LocateVex(G,u);if(i==0)return false;
  67.         j=LocateVex(G,v);
  68.         if(j==0||j==i||G.arcs[i][j].adj!=Infinity)return false;
  69.         G.arcs[i][j].adj=w;
  70.         G.arcnum++;
  71.         if(G.kind>=3)
  72.         {
  73.                 G.arcs[j][i].adj=w;
  74.             G.arcnum++;
  75.         }
  76.         return true;
  77. }
  78. int LocateVex(MGraph&G,VexType v)
  79. {
  80.         int i;
  81.         for(i=G.vexnum;i>0&&G.vexs[i].data!=v;i--);
  82.         return i;
  83. }
  84. bool DeleteArc(MGraph& G,VexType u,VexType v)
  85. {
  86.         int i,j;
  87.         i=LocateVex(G,u);if(i==0)return false;
  88.         j=LocateVex(G,v);
  89.         if(j==0||G.arcs[i][j].adj==Infinity)return false;
  90.         G.arcs[i][j].adj=Infinity;
  91.         G.arcnum--;
  92.         if(G.kind>=3)
  93.         {
  94.                 G.arcs[j][i].adj=Infinity;G.arcnum--;
  95.         }
  96.         return true;
  97. }
  98. bool DeleteVex(MGraph &G,VexType v)
  99. {
  100.         int i,j;
  101.         j=LocateVex(G,v);
  102.         G.vexs[j]=G.vexs[G.vexnum];
  103.         for(i=1;i<=G.vexnum;i++)
  104.         {
  105.                 if(G.arcs[i][j].adj!=Infinity)G.arcnum--;
  106.                 if(G.arcs[j][i].adj!=Infinity)G.arcnum--;
  107.         }
  108.         if(j<G.vexnum)
  109.         {
  110.                 for(i=1;i<=G.vexnum;i++)
  111.                         G.arcs[i][j]=G.arcs[i][G.vexnum];
  112.                 for(i=1;i<=G.vexnum;i++)
  113.                         G.arcs[j][i]=G.arcs[i][G.vexnum];
  114.         }
  115.         G.vexnum--;
  116.         return true;
  117. }
  118. void CreateGraph(MGraph&G,char fn[])
  119. {
  120.         int i,j,w;VexType u,v;ifstream f;
  121.         f.open(fn);f>>G.kind;i=0;
  122.         while(true)
  123.         {
  124.                 f>>u;if(u=='#')break; i++;G.vexs[i].data=u;
  125.         }
  126.         G.vexnum=i;
  127.         for(i=1;i<=G.vexnum;i++)
  128.                 for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=Infinity;
  129.         G.arcnum=0;
  130.         while(true)//边
  131.         {
  132.                 f>>u>>v;if(u=='#'||v=='#')break;
  133.                 if(G.kind==1||G.kind==3)
  134.                         w=1;
  135.                 else f>>w;
  136.                 InsertArc(G,u,v,w);
  137.         }
  138.         f.close();
  139. }
  140. void Show(MGraph &G)
  141. {
  142.         int i=1,j=1;
  143.         cout<<"所有顶点为：";
  144.         for(i;i<=G.vexnum;i++)
  145.                 cout<<G.vexs[i].data<<" ";
  146.         cout<<endl<<"所有弧为：";
  147.         if(G.kind==1)
  148.         {
  149.                 for(i=1;i<=G.vexnum;i++)
  150.                         for(j=1;j<= G.vexnum;j++)
  151.                                 if(G.arcs[i][j].adj==1)
  152.                                         cout<<"<"<<G.vexs[i].data<<","<<G.vexs[j].data<<"> ";
  153.         }
  154.         else
  155.         {
  156.                 for(i=1;i<=G.vexnum;i++)
  157.                         for(j=1;j<i;j++)
  158.                                 if(G.arcs[i][j].adj==1)
  159.                                         cout<<"("<<G.vexs[i].data<<","<<G.vexs[j].data<<") ";
  160.         }
  161.         cout << endl;
  162. }
  163.  
  164. //fn.txt
  165. 1
  166. a b c #
  167. a b
  168. b c
  169. a c
  170. # #

回复 "数据结构与算法----4.2 用数组存储图：1、插入一个顶点2、删除一条弧3、删"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666