c - C 中邻接表的图实现

Question

我刚刚开始学习 C，作为自学练习，我正在用 C 实现数据结构和算法。现在我正在研究一个图，这是它的数据结构表示。

typedef int graphElementT;
typedef struct graphCDT *graphADT;

typedef struct vertexTag
{
    graphElementT element;
    int visited;
    struct edgeTag *edges;
    struct vertexTag *next; 
} vertexT;

typedef struct edgeTag
{
    int weight;
    vertexT *connectsTo;
    struct edgeTag *next;
} edgeT;

typedef struct graphCDT
{
    vertexT *vertices;
} graphCDT;

我向该图添加了一个 addVertex 函数。

int addVertex(graphADT graph, graphElementT value)
{
    vertexT *new = malloc(sizeof(*new));

    vertexT *vert;
    new->element = value;
    new->visited = 0;
    new->edges = NULL;
    new->next = NULL;

    int i = 0;

    for(vert=graph->vertices; vert->next != NULL; vert=vert->next)
    {
        if(vert->element == value)
        {
            printf("already exists\n");
            return 0;
        }
    }   

    vert->next = new;

    //free(new);
    printf("\ninserted %d\n", vert->element);   

    return 1;       
}

除了三件事之外，这一切都很好。

1. 如果新添加的顶点与列表中的最后一个顶点相同，则无法看到它。为了防止这种情况，我将 for 循环限制条件更改为 vert != NULL，但这会导致段错误。

2. 如果我尝试释放临时分配的指针，它会通过指针重置内存指针，这会在顶点列表的末尾添加一个无限循环。有没有办法在不重写它指向的内存的情况下释放指针？或者实际上并不需要释放指针？

3. 破坏图表是否意味着破坏每条边和顶点？或者有更好的方法吗？

此外，如果这种图形数据结构不是一个好的结构并且有更好的实现，我将不胜感激。

Answer 1

1

如果将限制条件更改为 vert!=NULL ，并且循环以 vert==NULL 结束，即，要添加的顶点不存在，那么您将阅读下一条语句:

vert->next = new;

这意味着您正在访问 NULL 、vert 指针，因此会出现段错误。

现在，为了允许检查最后一个元素是否不是要添加的顶点，并且为了防止段错误，请执行以下操作:

for(vert=graph->vertices; vert->next != NULL; vert=vert->next)
{
    if(vert->element == value)
    {
        printf("already exists\n");
        return 0;
    }
}   

if(vert->element == value)
    {
        printf("already exists\n");
        return 0;
    }

vert->next = new;

2

临时"new"指针是分配给您添加的顶点的内存位置。它不会被释放，因为释放它意味着您删除了刚刚添加的顶点:O。

3

是的，破坏图表本质上是一样的。

将链表实现为图的邻接表实现始终是一个好习惯。尽管您始终可以使用 C++“2 D Vector”来实现相同的操作。