c/c++语言开发共享图的两种存储结构及四种形态——邻接矩阵、邻接表；有向图、无向图、有向网、无向网。

 1 #include <iostream>   2 using namespace std;   3 //无穷大   4 #define infinity int_max   5 //最大顶点个数   6 #define max_vertex_num 20   7 //顶点类型   8 typedef char vertextype;   9 typedef int vrtype;  10 typedef char infotype;  11  //图的四种类型  12 typedef enum {dg = 1, dn, udg, udn} graphkind;  13   14 //弧的结构体定义  15 typedef struct arccell  16 {  17     // 对于网来说是权值；对于图来说就是0或1  18     vrtype adj;  19     //该弧相关信息的指针（现在暂且可以理解为字符指针）  20     infotype* info;  21 }arccell, adjmatrix[max_vertex_num][max_vertex_num];  22   23 //图的结构体定义  24 typedef struct  25 {  26     vertextype vexs[max_vertex_num];  27      //arcs可以先简单地理解为一个数组名  28     adjmatrix arcs;  29     //当前图中的顶点数和弧数  30     int vexnum, arcnum;  31     //图的种类标志  32     graphkind kind;  33 }mgraph;

void creategraph(mgraph &g);  void createudn(mgraph &g);  int locatevex(mgraph g , int v1);  void createudg(mgraph &g);  void createdg(mgraph &g);  void createdn(mgraph &g);  void print(mgraph g);  int main(void)  {      mgraph g;      creategraph(g);      return 0;  }

void creategraph(mgraph &g)  {      cout << "1、有向图" << endl;      cout << "2、有向网" << endl;      cout << "3、无向图" << endl;      cout << "4、无向网" << endl;      cout << "你需要创建哪一种类型的图?" << endl;      //此处运用了强转（不能直接从键盘上给枚举变量赋值）      cin >> (int&)g.kind;      switch (g.kind)      {          case 1:              return createdg(g);              break;          case 2:              return createdn(g);              break;          case 3:              return createudg(g);              break;          case 4:              return createudn(g);              break;      }  }  //创建有向网  void createdn(mgraph &g)  {      cout << "该图有多少顶点以及多少条弧?" << endl;      cin >> g.vexnum  >> g.arcnum;      cout << "请输入顶点:" << endl;      for(int i = 0; i < g.vexnum; i++)      {          //cin相当于c里面的scanf函数          cin >> g.vexs[i];      }      for(int i = 0; i < g.vexnum; i++)      {          for(int j = 0; j < g.vexnum; j++)          {              //先假设每两个点之间都没有边              g.arcs[i][j].adj = infinity;          }      }      cout << "请输入各弧的两个端点及其权值" << endl;      vertextype v1, v2;      //用于暂时存储每条弧的权值      vrtype temp;      int i, j;      //有向网不具备对称性      for(int k = 0; k < g.arcnum; k++)      {          cin >> v1 >> v2 >> temp;          //利用存储顶点所用的一维数组中对应点的下标          i = locatevex(g, v1), j = locatevex(g, v2),          g.arcs[i][j].adj = temp;      }      print(g);  }  //创建有向图  void createdg(mgraph &g)  {      cout << "该图有多少顶点以及多少条边?" << endl;      cin >> g.vexnum  >> g.arcnum;      cout << "请输入顶点:" << endl;      for(int i = 0; i < g.vexnum; i++)      {          cin >> g.vexs[i];      }      for(int i = 0; i < g.vexnum; i++)      {          for(int j = 0; j < g.vexnum; j++)          {              //先假定图中没有弧              g.arcs[i][j].adj = 0;          }      }      cout << "请输入各弧的两个端点" << endl;      vertextype v1, v2;      //用于暂时存储每条弧的'权值'(存在即为1,否则为0)      //因为temp的取值只能为1或0，所以不需要再输入      vrtype temp = 1;      int i, j;      //有向图不具备对称性      for(int k = 0; k < g.arcnum; k++)      {          cin >> v1 >> v2;          i = locatevex(g, v1), j = locatevex(g, v2),          g.arcs[i][j].adj = temp;      }      print(g);  }  //创建无向图（对称）  void createudg(mgraph &g)  {      cout << "该图有多少顶点以及多少条边?" << endl;      cin >> g.vexnum  >> g.arcnum;      cout << "请输入顶点:" << endl;      for(int i = 0; i < g.vexnum; i++)      {          cin >> g.vexs[i];      }      for(int i = 0; i < g.vexnum; i++)      {          for(int j = 0; j < g.vexnum; j++)          {              //先假设每两个点之间都没有边              g.arcs[i][j].adj = 0;          }      }      cout << "请输入各弧的两个端点(下三角)" << endl;      vertextype v1, v2;      vrtype temp = 1;      int i, j;      //考虑到无向图具有对称性（先只输入(邻接矩阵)下三角里存在的边）      for(int k = 0; k < g.arcnum; k++)      {          cin >> v1 >> v2;          i = locatevex(g, v1), j = locatevex(g, v2),          g.arcs[i][j].adj = temp;          //将上三角里的每条弧同样添加上权值          g.arcs[j][i].adj = g.arcs[i][j].adj;      }      print(g);  }  //创建无向网（对称）  void createudn(mgraph &g)  {      cout << "该图有多少顶点以及多少条边?" << endl;      cin >> g.vexnum  >> g.arcnum;      cout << "请输入顶点:" << endl;      for(int i = 0; i < g.vexnum; i++)      {          cin >> g.vexs[i];      }      for(int i = 0; i < g.vexnum; i++)      {          for(int j = 0; j < g.vexnum; j++)          {              //先假设每两个点之间都没有边(无穷远)              g.arcs[i][j].adj = infinity;          }      }      cout << "请输入各弧的两个端点及其权值(下三角)" << endl;      vertextype v1, v2;      vrtype temp;      int i, j;      //考虑到无向图具有对称性（先只输入(邻接矩阵)下三角里存在的边）      for(int k = 0; k < g.arcnum; k++)      {          cin >> v1 >> v2 >> temp;          i = locatevex(g, v1), j = locatevex(g, v2),          g.arcs[i][j].adj = temp;          //将上三角里的每条弧同样添加上权值          g.arcs[j][i].adj = g.arcs[i][j].adj;      }      print(g);  }   //返回该顶点在一维数组中的下标（当然每一个人创建的一维数组可以是不同的）  int locatevex(mgraph g , int v1)  {      for(int i = 0; i < g.vexnum; i++)      {          if(g.vexs[i] == v1)              return i;      }  }  void print(mgraph g)  {      cout << "存储的一维数组如下:" << endl;      for(int i = 0; i < g.vexnum; i++)      {          cout << g.vexs[i] << 't';      }      cout << endl;      cout << "邻接矩阵如下:" << endl;      for(int i = 0; i < g.vexnum; i++)      {          for(int j = 0; j < g.vexnum; j++)          {              cout << g.arcs[i][j].adj << 't';          }          cout << endl;      }  }

  1 #include <iostream>    2 #include <string>    3 using namespace std;    4 using std :: string;    5 typedef string infortype;    6 //顶点类型    7 typedef char vertextype;    8 typedef int status;    9 typedef enum {udg = 1, dg, udn, dn} graphkind;   10 //最大顶点个数   11 #define max_vertex_num 20   12 #define error -1   13 #define ok 1   14 //表节点的定义   15 typedef struct arcnode   16 {   17     //该弧所指向的顶点的位置（相对地址）   18     int adjvex;   19     //指向下一条弧的指针   20     struct arcnode* nextarc;   21     //该弧相关信息的指针（例如权值）   22     infortype info;   23 }arcnode;   24 //头节点的定义   25 typedef struct vnode   26 {   27     //顶点信息   28     vertextype data;   29     //指向第一条依附该顶点的弧的指针   30     arcnode* firstarc;   31 }vnode, adjlist[max_vertex_num];   32 //图的定义   33 typedef struct   34 {   35     //存放头节点的一维数组   36     adjlist vertices;   37     //图的当前顶点数和弧数   38     int vexnum, arcnum;   39     //图的种类标志   40     graphkind kind;   41 }algraph;   42 void creategraph(algraph& g);   43 status createudn(algraph& g);   44 status createudg(algraph& g);   45 status createdg(algraph& g);   46 status createdn(algraph& g);   47 int locatevex(vnode vertices[], int vexnum, vertextype e);   48 void print(const algraph& g);   49 int main(void)   50 {   51     algraph g;   52     creategraph(g);   53     return 0;   54 }   55 void creategraph(algraph& g)   56 {   57     int reply;   58     cout << "1. 无向图" << endl;   59     cout << "2. 有向图" << endl;   60     cout << "3. 无向网" << endl;   61     cout << "4. 有向网" << endl;   62     //其实逆与正是差不多的，根本上还是取决于用户的输入   63     cout << "5. 逆有向网" << endl;   64     cout << "6. 逆有向图" << endl;   65     cout << "你想创建哪一种类型的图?" << endl;   66     cin >> reply;   67     switch(reply)   68     {   69     case 1:   70         createudg(g);   71         break;   72     case 2:   73         createdg(g);   74         break;   75     case 3:   76         createudn(g);   77         break;   78     case 4:   79         createdn(g);   80         break;   81     case 5:   82         createdn(g);   83         break;   84     case 6:   85         createdg(g);   86         break;   87     default:   88         exit(-1);   89     }   90 }   91 //构造无向网   92 status createudn(algraph& g)   93 {   94     vertextype e;   95     int num;   96     cout << "该图共有多少个顶点、多少条弧?" << endl;   97     cin >> g.vexnum >> g.arcnum;   98     cout << "请输入各顶点:" << endl;   99     for(int i = 0; i < g.vexnum; i++)  100     {  101         //注意存储结构  102         cin >> g.vertices[i].data;  103         //先将头节点的指针域设为空  104         g.vertices[i].firstarc = null;  105     }  106     for(int i = 0; i < g.vexnum; i++)  107     {  108         //(强调引用)  109         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针  110         //所以接连各节点不想以前那样简单了  111         arcnode* &ptr = g.vertices[i].firstarc;  112         cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl;  113         cin >> num;  114         if(num > 0)  115         {  116             int index;  117             arcnode* p = null;  118             cout << "请将这些顶点及弧所带信息依次输入:" << endl;  119             //先处理一个节点（为了方便后面的操作）  120             ptr = new arcnode;  121             if(ptr)  122             {  123                 cin >> e;  124                 //输入弧上的信息  125                 cin >> ptr->info;  126                 index = locatevex(g.vertices, g.vexnum, e);  127                 p = ptr;  128                 p->adjvex = index;  129                 p->nextarc = null;  130             }  131             else  132                 return error;  133             for(int j = 1; j < num; j++)  134             {  135                 arcnode* ptr2 = new arcnode;  136                 if(ptr2)  137                 {  138                     //注意各变量的类型，不要搞混了  139                     cin >> e;  140                     //输入弧上的信息  141                     cin >> ptr2->info;  142                     index = locatevex(g.vertices, g.vexnum, e);  143                     ptr2->adjvex = index;  144                     ptr2->nextarc = null;  145                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）  146                     p->nextarc = ptr2;  147                     p = p->nextarc;  148                 }  149                 else  150                     return error;  151             }  152         }  153     }  154     print(g);  155     return ok;  156 }  157 //构造无向图  158 status createudg(algraph& g)  159 {  160     vertextype e;  161     int num;  162     cout << "该图共有多少个顶点、多少条弧?" << endl;  163     cin >> g.vexnum >> g.arcnum;  164     cout << "请输入各顶点:" << endl;  165     for(int i = 0; i < g.vexnum; i++)  166     {  167         //注意存储结构  168         cin >> g.vertices[i].data;  169         //先将头节点的指针域设为空  170         g.vertices[i].firstarc = null;  171     }  172     for(int i = 0; i < g.vexnum; i++)  173     {  174         //(强调引用)  175         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针  176         //所以接连各节点不想以前那样简单了  177         arcnode* &ptr = g.vertices[i].firstarc;  178         cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl;  179         cin >> num;  180         if(num > 0)  181         {  182             int index;  183             arcnode* p = null;  184             cout << "请将这些顶点依次输入:" << endl;  185             //先处理一个节点（为了方便后面的操作）  186             ptr = new arcnode;  187             if(ptr)  188             {  189                 cin >> e;  190                 index = locatevex(g.vertices, g.vexnum, e);  191                 p = ptr;  192                 p->adjvex = index;  193                 p->nextarc = null;  194             }  195             else  196                 return error;  197             for(int j = 1; j < num; j++)  198             {  199                 //注意各变量的类型，不要搞混了  200                 cin >> e;  201                 index = locatevex(g.vertices, g.vexnum, e);  202                 arcnode* ptr2 = new arcnode;  203                 if(ptr2)  204                 {  205                     ptr2->adjvex = index;  206                     ptr2->nextarc = null;  207                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）  208                     p->nextarc = ptr2;  209                     p = p->nextarc;  210                 }  211                 else  212                     return error;  213             }  214         }  215     }  216     print(g);  217     return ok;  218 }  219 //构造有向图  220 status createdg(algraph& g)  221 {  222     vertextype e;  223     int num;  224     cout << "该图共有多少个顶点、多少条弧?" << endl;  225     cin >> g.vexnum >> g.arcnum;  226     cout << "请输入各顶点:" << endl;  227     for(int i = 0; i < g.vexnum; i++)  228     {  229         //注意存储结构  230         cin >> g.vertices[i].data;  231         //先将头节点的指针域设为空  232         g.vertices[i].firstarc = null;  233     }  234     for(int i = 0; i < g.vexnum; i++)  235     {  236         //(强调引用)  237         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针  238         //所以接连各节点不想以前那样简单了  239         arcnode* &ptr = g.vertices[i].firstarc;  240         cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl;  241         cin >> num;  242         if(num > 0)  243         {  244             int index;  245             arcnode* p = null;  246             cout << "请将这些顶点依次输入:" << endl;  247             //先处理一个节点（为了方便后面的操作）  248             ptr = new arcnode;  249             if(ptr)  250             {  251                 cin >> e;  252                 index = locatevex(g.vertices, g.vexnum, e);  253                 p = ptr;  254                 p->adjvex = index;  255                 p->nextarc = null;  256             }  257             else  258                 return error;  259             for(int j = 1; j < num; j++)  260             {  261                 //注意各变量的类型，不要搞混了  262                 cin >> e;  263                 index = locatevex(g.vertices, g.vexnum, e);  264                 arcnode* ptr2 = new arcnode;  265                 if(ptr2)  266                 {  267                     ptr2->adjvex = index;  268                     ptr2->nextarc = null;  269                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）  270                     p->nextarc = ptr2;  271                     p = p->nextarc;  272                 }  273                 else  274                     return error;  275             }  276         }  277     }  278     print(g);  279     return ok;  280 }  281 //构造有向网  282 status createdn(algraph& g)  283 {  284     vertextype e;  285     int num;  286     cout << "该图共有多少个顶点、多少条弧?" << endl;  287     cin >> g.vexnum >> g.arcnum;  288     cout << "请输入各顶点:" << endl;  289     for(int i = 0; i < g.vexnum; i++)  290     {  291         //注意存储结构  292         cin >> g.vertices[i].data;  293         //先将头节点的指针域设为空  294         g.vertices[i].firstarc = null;  295     }  296     for(int i = 0; i < g.vexnum; i++)  297     {  298         //(强调引用)  299         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针  300         //所以接连各节点不想以前那样简单了  301         arcnode* &ptr = g.vertices[i].firstarc;  302         cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl;  303         cin >> num;  304         if(num > 0)  305         {  306             int index;  307             arcnode* p = null;  308             cout << "请将这些顶点及弧所带信息依次输入:" << endl;  309             //先处理一个节点（为了方便后面的操作）  310             ptr = new arcnode;  311             if(ptr)  312             {  313                 cin >> e;  314                 //输入弧上的信息  315                 cin >> ptr->info;  316                 index = locatevex(g.vertices, g.vexnum, e);  317                 p = ptr;  318                 p->adjvex = index;  319                 p->nextarc = null;  320             }  321             else  322                 return error;  323             for(int j = 1; j < num; j++)  324             {  325                 arcnode* ptr2 = new arcnode;  326                 if(ptr2)  327                 {  328                     //注意各变量的类型，不要搞混了  329                     cin >> e;  330                     //输入弧上的信息  331                     cin >> ptr2->info;  332                     index = locatevex(g.vertices, g.vexnum, e);  333                     ptr2->adjvex = index;  334                     ptr2->nextarc = null;  335                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）  336                     p->nextarc = ptr2;  337                     p = p->nextarc;  338                 }  339                 else  340                     return error;  341             }  342         }  343     }  344     print(g);  345     return ok;  346 }  347 //定位顶点在一维数组中的位置  348 int locatevex(vnode vertices[], int vexnum, vertextype e)  349 {  350     int i;  351     for(i = 0; i < vexnum; i++)  352     {  353         if(vertices[i].data == e)  354             break;  355     }  356     return i;  357 }  358 //打印图  359 void print(const algraph& g)  360 {  361     cout << "您所创建的图用邻接表存储结构展示如下:" << endl;  362     for(int i = 0; i < g.vexnum; i++)  363     {  364         cout  << "[" << g.vertices[i].data << "]";  365         arcnode* ptr = g.vertices[i].firstarc;  366         while(ptr)  367         {  368             //打印出下标（从零开始）  369             cout  << "—>" << ptr->adjvex;  370             ptr = ptr->nextarc;  371         }  372         cout << endl;  373     }  374 }