C语言数据结构-图-邻接表2-试在邻接表存储结构上实现图的基本操作 del_vertex

爱被打了一巴掌 2023-01-20 09:46 38阅读 0赞

# 邻接表2 #

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

//顶点为int
    typedef int VertexType;
    
    //图的种类：DG 表示有向图, DN 表示有向网, UDG 表示无向图, UDN 表示无向网
    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);

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

### 提供代码 ###

#include <stdio.h>
    #include "graph.h" //请勿删除，否则检查不通过
    
    
    bool del_vertex(ListGraph *G, VertexType v){
    
    
    }

### 参考思路 ###

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][] ###

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][] ###

### 参考答案 ###

bool del_vertex(ListGraph* G, VertexType v)
    {
        int i;
        int V = locate_vertex(G, v);
        //检查是否存在该节点
        if (V == -1)
            return false;
    
        //先删除从该节点出发的边和该节点
        while (G->vertex[V].firstarc)
        {
            ArcNode* P = G->vertex[V].firstarc;
            if (P->nextarc)
            { //先free表头结点后面的
                ArcNode* temp = P->nextarc;
                P->nextarc = temp->nextarc;
                free(temp);
            }
            else {
                free(P); //free表头结点
                G->vertex[V].firstarc = NULL;
            }
            G->arcnum--; //边的数量-1
        }
        G->vexnum--; //结点的数量-1
        for (i = V; i < G->vexnum; i++)
        { //表头结点中，后面的向前移动
            G->vertex[i] = G->vertex[i + 1];
        }
    
        //再删除到该节点的边
        for (i = 0; i < G->vexnum; i++)
        {
            ArcNode* P = G->vertex[i].firstarc, * pNode = NULL;
            ArcNode* temp; //存储要被删掉的结点
            while (P)
            {
                if (V == P->adjvex)
                { //P的下个结点是V
                    if (!pNode)
                    { //P是表头结点
                        temp = G->vertex[i].firstarc;
                        G->vertex[i].firstarc = P->nextarc;
                    }
                    else {
                        pNode->nextarc = P->nextarc;
                        temp = P;
                    }
                    P = P->nextarc;
                    free(temp);
                    G->arcnum--;
                }
                else {
                    pNode = P;
                    P = P->nextarc;
                }
            }
        }
        return true;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221021/1b72007ff3f048e6ac7f29f935928248.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221021/89691c64b4e5410d9231cfb68f513c2b.png