Question

Я начинающий изучать Graph в ADT, язык C.

Это код, полученный отладкой. Код проблемы if(pg>visitInfo[visitV] == 0) из ALGraphDFS.c И отладочная программа сказала, что в верхнем коде возникает ошибка на этих последовательностях вызовов.

DFShowGraphVertex(&graph, A); printf("\n") (main code)
VisitVertex(pg, visitV);
if (pg->visitInfo[visitV] == 0)....

Я не мог понять, почему это было ошибкой. Потому что я использовал enum {A,B,C...} и создал массив visitInfo, используя этот код.

pg->visitInfo = (int *)malloc(sizeof(int) * pg->numV);
memset(pg->visitInfo, 0, sizeof(int) * pg->numV);

(numV означает номер вершины в DFS. А pg означает struct _ual)

Не могли бы вы помочь мне найти проблему в этом коде? Это будет очень полезно для меня. Всего кодов для DFS под этой строкой.

Спасибо

P.S. Эти коды находятся в книге под названием Introduction to Data Structures Using C для изучения ADT.

Имя файла: ALGraphDFS.h / DLinkedList.h / ArrayBaseStack.h / ALGraphDFS.c / DLinkedList.c / ArrayBaseStack.c / DFSMain.c

[ALGraphDFS.h]

#ifndef __AL_GRAPH_DFS__
#define __AL_GRAPH_DFS__

#include "DLinkedList.h"

enum {A,B,C,D,E,F,G,H,I,J};

typedef struct _ual {
    int numV;
    int numE;
    List * adjList;
    int * visitInfo;
} ALGraph;

void GraphInit(ALGraph * pg, int nv);

void GraphDestroy(ALGraph * pg);

void AddEdge(ALGraph * pg, int fromV, int toV);

void ShowGraphEdgeInfo(ALGraph * pg);

void DFShowGraphVertex(ALGraph * pg, int startV);

#endif

[DLinkedList.h]

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

typedef int LData;

typedef struct _node {
    LData data;
    struct _node * next;
} Node;

typedef struct _linkedList {
    Node * head;
    Node * cur;
    Node * before;
    int numOfData;
    int(*comp)(LData d1, LData d2);
} LinkedList;

typedef LinkedList List;

void ListInit(List * plist);
void LInsert(List * plist, LData data);

int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);

LData LRemove(List * plist);
int LCount(List * plist);

void SetSortRule(List * plist, int(*comp)(LData d1, LData d2));

#endif

[ArrayBaseStack.h]

#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE    1
#define FALSE   0
#define STACK_LEN   100

typedef int Data;

typedef struct _arrayStack {
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

[ALGraphDFS.c]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraphDFS.h"
#include "DLinkedList.h"
#include "ArrayBaseStack.h"

int WhoIsPrecede(int data1, int data2);

void GraphInit(ALGraph * pg, int nv) {
    int i;

    pg->adjList = (List*)malloc(sizeof(List) * nv);
    pg->numV = nv;
    pg->numE = 0;

    for (i = 0; i < nv; i++) {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
    }

    pg->visitInfo = (int *)malloc(sizeof(int) * pg->numV);
    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);

}

void GraphDestroy(ALGraph * pg) {
    if (pg->adjList != NULL)
        free(pg->adjList);

    if (pg->visitInfo != NULL)
        free(pg->visitInfo);
}

void AddEdge(ALGraph * pg, int fromV, int toV) {
    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);
    pg->numE += 1;
}

void ShowGraphEdgeInfo(ALGraph * pg) {
    int i;
    int vx;

    for (i = 0; i < pg->numV; i++) {
        printf("Connected %c: ", i + 65);
        if (LFirst(&(pg->adjList[i]), &vx)) {
            printf("%c ", vx + 65);
            while (LNext(&(pg->adjList[i]), &vx))
                printf("%c ", vx + 65);
        }
        printf("\n\n");
    }
}

int VisitVertex(ALGraph * pg, int visitV) {
    if (pg->visitInfo[visitV] == 0) {
        pg->visitInfo[visitV] = 1;
        printf("%c ", visitV + 65);
        return TRUE;
    }

    return FALSE;
}

void DFShowGraphVertex(ALGraph * pg, int startV) {
    Stack stack;
    int visitV = startV;
    int nextV;

    StackInit(&stack);
    VisitVertex(pg, visitV);
    SPush(&stack, visitV);

    while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) {
        int visitFlag = FALSE;

        if (VisitVertex(pg, nextV) == TRUE) {
            SPush(&stack, visitV);
            visitV = nextV;
            visitFlag = TRUE;
        }
        else {
            while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) {
                if (VisitVertex(pg, nextV) == TRUE) {
                    SPush(&stack, visitV);
                    visitV = nextV;
                    visitFlag = TRUE;

                    break;
                }
            }
        }

        if (visitFlag == FALSE) {
            if (SIsEmpty(&stack) == TRUE)
                break;
            else
                visitV = SPop(&stack);
        }
    }
    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}    

int WhoIsPrecede(int data1, int data2) {
    if (data1 < data2)
        return 0;
    else
        return 1;
}

[DLinkedList.c]

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"

void ListInit(List * plist) {
    plist->head = (Node*)malloc(sizeof(Node));
    plist->head->next = NULL;
    plist->comp = NULL;
    plist->numOfData = 0;
}

void FInsert(List * plist, LData data) {
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    newNode->next = plist->head->next;
    plist->head = newNode;

    (plist->numOfData)++;
}

void SInsert(List * plist, LData data) {
    Node * newNode = (Node*)malloc(sizeof(Node));
    Node * pred = plist->head;
    newNode->data = data;

    while (pred->next != NULL && plist->comp(data, pred->next->data) != 0) {
        pred = pred->next;
    }

    newNode->next = pred->next;
    pred->next = newNode;

    (plist->numOfData)++;
}

void LInsert(List * plist, LData data) {
    if (plist->comp == NULL)
        FInsert(plist, data);
    else
        SInsert(plist, data);
}

int LFirst(List * plist, LData * pdata) {
    if (plist->head->next == NULL)
        return FALSE;

        plist->before = plist->head;
        plist->cur = plist->head->next;

        *pdata = plist->head->data;
        return TRUE;
    }

    int LNext(List * plist, LData * pdata) {
        if (plist->cur->next == NULL)
            return FALSE;

    plist->before = plist->cur;
    plist->cur = plist->cur->next;

    *pdata = plist->cur->data;
    return TRUE;
}    

LData LRemove(List * plist) {
    Node * rpos = plist->cur;
    LData rdata = rpos->data;

    plist->before->next = plist->cur->next;
    plist->cur = plist->before;

    free(rpos);
    (plist->numOfData)--;
    return rdata;
}

int LCount(List * plist) {
    return plist->numOfData;
}

void SetSortRule(List * plist, int(*comp)(LData d1, LData d2)) {
    plist->comp = comp;
}

[ArrayBaseStack.c]

#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"

void StackInit(Stack * pstack) {
    pstack->topIndex = -1;
}

int SIsEmpty(Stack * pstack) {
    if (pstack->topIndex == -1)
        return TRUE;
    else
        return FALSE;
}

void SPush(Stack * pstack, Data data) {
    pstack->topIndex += 1;
    pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack * pstack) {
    int rIdx;

    if (SIsEmpty(pstack)) {
        printf("Error! \n");
        exit(-1);
    }

    rIdx = pstack->topIndex;
    pstack->topIndex -= 1;

    return pstack->stackArr[rIdx];
}

Data SPeek(Stack * pstack) {
    if (SIsEmpty(pstack)) {
        printf("Error! \n");
        exit(-1);
    }

    return pstack->stackArr[pstack->topIndex];
}

[DFSMain.c]

#include <stdio.h>
#include "ALGraphDFS.h"

int main(void) {
    ALGraph graph;
    GraphInit(&graph, 7);

    AddEdge(&graph, A, B);
    AddEdge(&graph, A, D);
    AddEdge(&graph, B, C);
    AddEdge(&graph, D, C);
    AddEdge(&graph, D, E);
    AddEdge(&graph, E, F);
    AddEdge(&graph, E, G);

    ShowGraphEdgeInfo(&graph);

    DFShowGraphVertex(&graph, A); printf("\n");
    DFShowGraphVertex(&graph, C); printf("\n");
    DFShowGraphVertex(&graph, E); printf("\n");
    DFShowGraphVertex(&graph, G); printf("\n");

    GraphDestroy(&graph);
    return 0;
}

Gaurav Sehgal · Answer 1 · 27 апреля 2018

void ListInit(List * plist) {
plist->head = (Node*)malloc(sizeof(Node));
plist->head->next = NULL;
plist->comp = NULL;
plist->numOfData = 0;
}

Вы никогда не инициализируете plist->data здесь, что является мусором. Когда вы звоните DFShowGraphVertex(),

while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) {
    int visitFlag = FALSE;
    if (VisitVertex(pg, nextV) == TRUE) {

При вызове VisitVertex nextV содержит этот мусор, потому что LFirst просто возвращает первый узел.

РЕДАКТИРОВАТЬ: Если вы рассматриваете первый узел в каждом списке смежности как фиктивный узел, то LFirst() должен начинаться со второго узла. Лучшим подходом было бы вообще не иметь фиктивного узла.

Ошибка отладки: график DFS (поиск в глубину), ADT

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Ошибка отладки: график DFS (поиск в глубину), ADT

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы