Icoding平台第六次作业解析-图的储存

T1

邻接矩阵
试在邻接矩阵存储结构上实现图的基本操作 matrix_insert_vertex 和matrix_insert_arc，相关定义如下：

typedef int VertexType;

typedef enum{
DG, UDG
}GraphType;

typedef struct{
VertexType vertex[MAX_VERTEX_NUM]; //顶点向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum, arcnum; //图的当前顶点数和弧数
GraphType type; //图的种类标志
}MatrixGraph;

int matrix_locate_vertex(MatrixGraph MG, VertexType vex); //返回顶点 v 在vertex数组中的下标，如果v不存在，返回-1
bool matrix_insert_vertex(MatrixGraph G, VertexType v);
bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w);

当成功插入顶点或边时，函数返回true，否则（如顶点或边已存在、插入边时顶点v或w不存在）返回false。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-06-10, Wed, 13:06:59
    * 最高分数：100
    */
   
   
   #include "graph.h" // 请不要删除，否则检查不通过
   #include <stdio.h>
   
   bool matrix_insert_vertex(MatrixGraph* G, VertexType v)
   {
       if (matrix_locate_vertex(G, v) != -1 || G->vexnum + 1 >= MAX_VERTEX_NUM)
           return false;
       G->vertex[G->vexnum] = v;
       G->vexnum++;
       for (int i = 0; i < G->vexnum; i++)
           G->arcs[i][G->vexnum - 1] = G->arcs[G->vexnum - 1][i] = 0;
       return true;
   }
   
   bool matrix_insert_arc(MatrixGraph* G, VertexType v, VertexType w)
   {
       int i = matrix_locate_vertex(G, v), j = matrix_locate_vertex(G, w);
       if (i == -1 || j == -1)
           return false;
       else if (G->arcs[i][j] == 1)
           return false;
       else {
           G->arcs[i][j] = 1;
           G->arcs[j][i] = 1;
       }
       G->arcnum += 1;
       return true;
   }

---

T2

邻接表1
试在邻接表存储结构上实现图的基本操作 insert_vertex 和 insert_arc，相关定义如下：

typedef int VertexType;

typedef enum{
DG, UDG
}GraphType;

typedef struct ArcNode
{
int adjvex;
InfoPtr *info;
struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode;
typedef struct
{
VNode vertex[MAX_VERTEX_NUM];
int vexnum, arcnum;
GraphType type;
}ListGraph;

int locate_vertex(ListGraph* G, VertexType v); //返回顶点 v 在vertex数组中的下标，如果v不存在，返回-1
bool insert_vertex(ListGraph G, VertexType v);
bool insert_arc(ListGraph *G, VertexType v, VertexType w);
bool is_empty(Stack S); // 栈为空时返回 true，否则返回 false

当成功插入顶点或边时，函数返回true，否则（如顶点或边已存在、插入边时顶点v或w不存在）返回false。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-06-12, Thu, 16:07:33
    * 最高分数：100
    */
   
   
   #include "graph.h" //请勿删除，否则检查不通过
   #include <stdio.h>
   
   bool insert_vertex(ListGraph* G, VertexType v)
   {
       if (locate_vertex(G, v) != -1 || G->vexnum + 1 >= MAX_VERTEX_NUM)
           return false;
       G->vertex[G->vexnum].data = v;
       G->vertex[G->vexnum].firstarc = NULL;
       G->vexnum++;
       return true;
   }
   
   bool insert_arc(ListGraph* G, VertexType v, VertexType w)
   {
       if (locate_vertex(G, v) == -1 || locate_vertex(G, w) == -1)
           return false;
       return true;
   }

---

T3

邻接表2
试在邻接表存储结构上实现图的基本操作 del_vertex，相关定义如下：

typedef int VertexType;

typedef enum{
DG, UDG
}GraphType;

typedef struct ArcNode{
int adjvex;
InfoPtr info;
struct ArcNode nextarc;
}ArcNode;

typedef struct VNode{
VertexType data;
ArcNode firstarc;
}VNode;
typedef struct{
VNode vertex[MAX_VERTEX_NUM];
int vexnum, arcnum;
GraphType type;
}ListGraph;

int locate_vertex(ListGraph *G, VertexType v); //返回顶点 v 在vertex数组中的下标，如果v不存在，返回-1
bool del_vertex(ListGraph *G, VertexType v); //删除顶点 v

当成功删除顶点或边时，函数返回true，否则（如顶点或边不存在、删除边时顶点v或w不存在）返回false。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-06-13, Sat, 11:09:26
    * 最高分数：100
    */
   
   
   #include "graph.h" //请勿删除，否则检查不通过
   #include <stdio.h>
   
   bool del_vertex(ListGraph* G, VertexType v)
   {
       int t = locate_vertex(G, v), i;
       if (t < 0)
           return false;
       ArcNode *q, *p;
       p = G->vertex[t].firstarc;
       while (p) {
           q = p;
           p = p->nextarc;
           free(q);
           G->arcnum--;
       }
       G->vertex[t].firstarc = NULL;
       for (i = 0; i < G->vexnum; i++) {
           p = G->vertex[i].firstarc;
           while (p && p->adjvex != t) {
               q = p;
               p = p->nextarc;
           }
           if (p && p->adjvex == t) {
               if (p == G->vertex[i].firstarc) {
                   G->vertex[i].firstarc = p->nextarc;
                   free(p);
               } else {
                   q->nextarc = p->nextarc;
                   free(p);
               }
               G->arcnum--;
           }
       }
       for (i = t + 1; i < G->vexnum; i++) {
           G->vertex[i - 1] = G->vertex[i];
       }
       G->vexnum--;
       return true;
   }

---