Code666 (代码贴、代码片段)

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

来自 , 2020-10-09, 写在 C++, 查看 158 次.
URL http://www.code666.cn/view/955cb567
  1. #include<iostream>
  2. using namespace std;
  3. const int MVN = 21;
  4. typedef char VeuType;//顶点元素类型
  5. typedef struct ArcNode
  6. {
  7.         int adjveu;//弧指向的顶点位置
  8.         int adj;//权
  9.         ArcNode *neutarc;//指向下一条弧的顶点
  10. }*ArcPtr;
  11. struct VeuNode
  12. {
  13.         VeuType data;//顶点数据
  14.         ArcPtr firstarc;//指向第一条依附于该顶点的弧
  15.         bool visited;//是否被访问过
  16. };
  17. struct ALGraph
  18. {
  19.         VeuNode veus[MVN];
  20.         int kind, veunum, arcnum;//类型，顶点数，弧数
  21. };
  22. int LocateVeu(ALGraph &G, VeuType v);//在图G中查找顶点
  23. bool InsertArc(ALGraph &G, VeuType u, VeuType v, int w = 1);
  24. void CreateGraph(ALGraph &G, int Kind, char v[]);
  25. void GraphPrint(ALGraph &G);
  26. bool insertdian(ALGraph &G, VeuType u);//插入一个顶点
  27. bool DeleteHu(ALGraph &G, VeuType u, VeuType v);//删除一条弧
  28. bool Deletedian(ALGraph &G, VeuType u);
  29. int main()
  30. {
  31.         char g[] = "sacd#sascsdacadcd#";
  32.         cout << "原始序列为 "<< endl<<g <<endl;
  33.         int Kind = 1;
  34.         ALGraph G;
  35.         CreateGraph(G, Kind, g);
  36.         GraphPrint(G);
  37.         VeuType v = 'c';
  38.         Deletedian(G, v);
  39.         cout << "删除顶点" <<v<< endl;
  40.         GraphPrint(G);
  41.         VeuType u = 'e';
  42.         insertdian(G, u);
  43.         cout << "插入顶点" <<u<< endl;
  44.         GraphPrint(G);
  45.         VeuType v1 = 's';
  46.         VeuType v2 = 'a';
  47.         cout << "删除弧<"<<v1<<","<<v2<<">" << endl;
  48.         DeleteHu(G, v1, v2);
  49.         GraphPrint(G);
  50.         return 0;
  51. }
  52.  
  53. int LocateVeu(ALGraph &G, VeuType v)
  54. {
  55.         int i;
  56.         for (i = G.veunum; i > 0 && G.veus[i].data != v; i--);
  57.         return i;
  58. }
  59. bool InsertArc(ALGraph &G, VeuType u, VeuType v, int w )
  60. {
  61.         ArcPtr p;
  62.         int i, j;
  63.         bool found;
  64.         i = LocateVeu(G, u);
  65.         if (i == 0)
  66.         {
  67.                 return false;
  68.         }
  69.         j = LocateVeu(G, v);
  70.         if (j == 0 || j == i)
  71.         {
  72.                 return false;
  73.         }
  74.         for (found = false, p = G.veus[i].firstarc; p && !found; p = p->neutarc)//若弧存在，插入失败
  75.         {
  76.                 if (p->adjveu == j)
  77.                 {
  78.                         found = true;
  79.                 }
  80.         }
  81.         if (found)
  82.         {
  83.                 return false;
  84.         }
  85.         G.arcnum++;
  86.         p = new ArcNode;
  87.         p->adjveu = j;
  88.         p->adj = w;
  89.         p->neutarc = G.veus[i].firstarc;
  90.         G.veus[i].firstarc = p;//表头插入弧，假设对弧的次序无要求
  91.         if (G.kind <= 2)
  92.         {
  93.                 return true;
  94.         }
  95.         G.arcnum++;
  96.         p = new ArcNode;
  97.         p->adjveu = i;
  98.         p->adj = w;
  99.         p->neutarc = G.veus[j].firstarc;
  100.         G.veus[j].firstarc = p;
  101.         return true;
  102. }
  103. void CreateGraph(ALGraph &G, int Kind, char v[])
  104. {
  105.         int i, w;
  106.         G.kind = Kind;
  107.         G.arcnum = 0;
  108.         i = 0;
  109.         while (true)
  110.         {
  111.                 if (v[i] == '#')
  112.                 {
  113.                         break;
  114.                 }
  115.                 i++;
  116.                 G.veus[i].data = v[i - 1];
  117.                 G.veus[i].firstarc = NULL;
  118.         }
  119.         G.veunum = i;
  120.         i++;
  121.         while (true)
  122.         {
  123.                 if (v[i] == '#')
  124.                 {
  125.                         break;
  126.                 }
  127.                 if (G.kind == 1 || G.kind == 3)
  128.                 {
  129.                         w = 1;
  130.                 }
  131.                 else
  132.                 {
  133.                         w = v[i + 2] - 48;
  134.                 }
  135.                 InsertArc(G, v[i], v[i + 1], w);
  136.                 i = i + 2;
  137.                 if (w == 2 || w == 4)
  138.                 {
  139.                         i++;
  140.                 }
  141.         }
  142.        
  143. }
  144. void GraphPrint(ALGraph &G)
  145. {
  146.         ArcPtr p;
  147.         cout << "顶点数：" << G.veunum << "       " << "弧数：" << G.arcnum << endl;;
  148.         cout << "邻接表" << endl;
  149.         for (int i = 1; i <= G.veunum; i++)
  150.         {
  151.                 cout << G.veus[i].data;
  152.                 for (p = G.veus[i].firstarc; p; p = p->neutarc)
  153.                 {
  154.                         cout << "->" << p->adjveu;
  155.                 }
  156.                 cout << endl;
  157.                
  158.         }
  159. }
  160. bool insertdian(ALGraph &G, VeuType u)
  161. {
  162.         int i;
  163.         i = LocateVeu(G, u);
  164.         if (i != 0)
  165.         {
  166.                 return false;
  167.         }
  168.         G.veunum++;
  169.         G.veus[G.veunum].data = u;
  170.         G.veus[G.veunum].firstarc = NULL;
  171.         return true;
  172. }
  173. bool DeleteHu(ALGraph &G, VeuType u, VeuType v)
  174. {
  175.         ArcPtr p,q; int i, j; bool found;
  176.         i = LocateVeu(G, u);
  177.         if (i == 0) return false;
  178.         j = LocateVeu(G, v);
  179.         if (j == 0 || j == i)return false;
  180.         found = false;
  181.         p = NULL;
  182.         q = G.veus[i].firstarc;
  183.         while (q && !found)
  184.         {
  185.                 if (q->adjveu == j)found = true;
  186.                 else {
  187.                         p = q;
  188.                         q = q->neutarc;
  189.                 }
  190.         }
  191.         if (!found)return false;//没有该弧
  192.         if (p) p->neutarc = q->neutarc;
  193.         else G.veus[i].firstarc = q->neutarc;
  194.        
  195.         delete q; G.arcnum--;
  196.         if (G.kind <= 2) return true;
  197.         //无向图的情况
  198.         found = false;          
  199.         p = NULL;
  200.         q = G.veus[j].firstarc;
  201.         while (q && !found)
  202.         {
  203.                 if (q->adjveu == i)found = true;
  204.                 else {
  205.                         p = q;
  206.                         q = q->neutarc;
  207.                 }
  208.         }
  209.         if (p) p->neutarc = q->neutarc;
  210.         else G.veus[j].firstarc = q->neutarc;
  211.         delete q;
  212.         G.arcnum--;
  213.         return true;
  214.        
  215. }
  216. bool Deletedian(ALGraph &G, VeuType u)
  217. {
  218.         ArcPtr p, q; int i,j; bool found;
  219.         i = LocateVeu(G, u);
  220.         if (i == 0) return false;
  221.        
  222.         //删除出弧，弧数对应减少
  223.         p = G.veus[i].firstarc;
  224.         while (p)
  225.         {
  226.                 q = p;
  227.                 p = p->neutarc;
  228.                 delete q;
  229.                 G.arcnum--;
  230.         }
  231.         //删除入弧,弧数对应减少
  232.         for ( j = 1; j <= G.veunum; j++)
  233.         {
  234.                 if (j != i)
  235.                 {
  236.                         found = false;
  237.                         p = NULL;
  238.                         q = G.veus[j].firstarc;
  239.                         while (q && !found)
  240.                         {
  241.                                 if (q->adjveu == i) found = true;
  242.                                 else
  243.                                 {
  244.                                         p = q;
  245.                                         q = q->neutarc;
  246.                                 }
  247.                         }
  248.                         if (!found)
  249.                                 continue;
  250.                         if (p)
  251.                                 p->neutarc = q->neutarc;
  252.                         else
  253.                                 G.veus[j].firstarc = q->neutarc;
  254.                         delete q;
  255.                         G.arcnum--;
  256.                 }
  257.         }
  258.         G.veus[i] = G.veus[G.veunum];
  259.         for ( j = 1; j <= G.veunum; j++)
  260.         {
  261.                
  262.                 for (p= G.veus[j].firstarc;p;p=p->neutarc)
  263.                 {
  264.                         if (p->adjveu == G.veunum)
  265.                         {
  266.                                 p->adjveu = i;
  267.                                 break;
  268.                         }
  269.                 }
  270.         }
  271.         G.veunum--;
  272.         return true;
  273.        
  274. }
  275.  

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

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

captcha

贴代码片段 - Code666