c - 调试错误: Kruskal Algorithm, ADT

Question

刚刚开始学习ADT、C语言图。

这是调试捕获的代码。调试结果为plist->cur was 0xCDCCDCD。(来自DLinkedList.c)调试程序表示上层代码在这些调用序列上发生错误。

ConKruskalMST(&graph);(main code)
if (!IsConnVertex(pg, edge.v1, edge.v2));(ALGraphKruskal.c, line 172)
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE); (ALGraphKruskal.c, 
line 108)
*cur -> 0xCDCDCDCD{data = ?? next = ??} can't read memory of data, next

我不明白为什么会出现这个错误。你能帮我找出这段代码的问题吗？这对我很有帮助。 Kruskal 的总代码在此行下。

谢谢

附注这些代码在《使用C学习ADT的数据结构入门》一书中。

文件名-> ALEdge.h/ALGraphKruskal.h/ArrayBaseStack.h/DLinkedList.h/PriorityQueue.h/UsefulHeap.h/ALGraphKruskal.c/ArrayBaseStack.c/DLinkedList.c/KruskalMain.c/PriorityQueue.c/有用的堆.c

[ALEdge.h]

#ifndef __AL_EDGE__
#define __AL_EDGE__
typedef struct _edge {
    int v1;
    int v2;
    int weight;
} Edge;
#endif

[ALGraphKruskal.h]

#ifndef __AL_GRAPH_KRUSKAL__
#define __AL_GRAPH_KRUSKAL__

#include "DLinkedList.h"
#include "PriorityQueue.h"
#include "ALEdge.h"
#include "ArrayBaseStack.h"

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

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

void GraphInit(ALGraph * pg, int nv);
void GraphDestroy(ALGraph * pg);
void AddEdge(ALGraph * pg, int fromV, int toV, int weight);
void ShowGraphEdgeInfo(ALGraph * pg);
int IsConnVertex(ALGraph * pg, int v1, int v2);
void ConKruskalMST(ALGraph * pg);
void ShowGraphEdgeWeightInfo(ALGraph * pg);

#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

[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

[PriorityQueue.h]

#ifndef __PRIORITY_QUEUE_H__
#define __PRIORITY_QUEUE_H__

#include "UsefulHeap.h"

typedef Heap PQueue;
typedef HData PQData;

void PQueueInit(PQueue * ppq, PriorityComp pc);
int PQIsEmpty(PQueue * ppq);

void PEnqueue(PQueue * ppq, PQData data);
PQData PDequeue(PQueue * ppq);

#endif __PRIORITY_QUEUE_H__

[UsefulHeap.h]

#ifndef __USEFUL_HEAP_H__
#define __USEFUL_HEAP_H__
#define TRUE    1
#define FALSE   0

#define HEAP_LEN    100
#include "ALEdge.h"

typedef Edge HData;
typedef int PriorityComp(HData d1, HData d2);

typedef struct _heap {
    PriorityComp * comp;
    int numOfData;
    HData heapArr[HEAP_LEN];
} Heap;

void HeapInit(Heap * ph, PriorityComp pc);
int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data);
HData HDelete(Heap * ph);

#endif

[ALGraphKruskal.c]

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

int WhoIsPrecede(int data1, int data2);
int PQWeightComp(Edge d1, Edge d2);

int PQWeightComp(Edge d1, Edge d2) {
    return d1.weight - d2.weight;
}

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);

    PQueueInit(&(pg->pqueue), PQWeightComp);
}

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, int weight) {
    Edge edge = { fromV, toV, weight };

    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);
    pg->numE += 1;

    PEnqueue(&(pg->pqueue), edge);
}

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

    for (i = 0; i < pg->numV; i++) {

        printf("%c connects with: ", i + 65);

        if (LFirst(&(pg->adjList[i]), &vx)) {

            printf("%c ", vx + 65);

            while (LNext(&(pg->adjList[i]), &vx))
                printf("%c ", vx + 65);
        }
        printf("\n");
    }
}

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

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

int IsConnVertex(ALGraph * pg, int v1, int v2) {
    Stack stack;
    int visitV = v1;
    int nextV;

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

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

        if (nextV == v2) {
            memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
            return TRUE;
        }

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

                if (nextV == v2) {
                    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
                    return TRUE;
                }

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

void RemoveWayEdge(ALGraph * pg, int fromV, int toV) {
    int edge;

    if (LFirst(&(pg->adjList[fromV]), &edge)) {
        if (edge == toV) {
            LRemove(&(pg->adjList[fromV]));
            return;
        }
        while (LNext(&(pg->adjList[fromV]), &edge)) {
            if (edge == toV) {
                LRemove(&(pg->adjList[fromV]));
                return;
            }
        }
    }
}


void RemoveEdge(ALGraph * pg, int fromV, int toV) {
    RemoveWayEdge(pg, fromV, toV);
    RemoveWayEdge(pg, toV, fromV);
    (pg->numE)--;
}

void RecoverEdge(ALGraph * pg, int fromV, int toV, int weight) {
    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);
    (pg->numE)--;
}

void ConKruskalMST(ALGraph * pg) {
    Edge recvEdge[20];
    Edge edge;
    int eidx = 0;
    int i;

    while (pg->numE + 1 > pg->numV) {
        edge = PDequeue(&(pg->pqueue));
        RemoveEdge(pg, edge.v1, edge.v2);
        if (!IsConnVertex(pg, edge.v1, edge.v2)) {
            RecoverEdge(pg, edge.v1, edge.v2, edge.weight);
            recvEdge[eidx++] = edge;
        }
    }

    for (i = 0; i < eidx; i++) {
        PEnqueue(&(pg->pqueue), recvEdge[i]);
    }
}

void ShowGraphEdgeWeightInfo(ALGraph * pg) {
    PQueue copyPQ = pg->pqueue;
    Edge edge;

    while (!PQIsEmpty(&copyPQ)) {
        edge = PDequeue(&copyPQ);
        printf("(%c-%c), w:%d \n", edge.v1 + 65, edge.v2 + 65, edge.weight);
    }
}

[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];
}

[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->next = 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->cur->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;
}

[KruskalMain.c]

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

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

    AddEdge(&graph, A, B, 9);
    AddEdge(&graph, B, C, 2);
    AddEdge(&graph, A, C, 12);
    AddEdge(&graph, A, D, 8);
    AddEdge(&graph, D, C, 6);
    AddEdge(&graph, A, F, 11);
    AddEdge(&graph, F, D, 4);
    AddEdge(&graph, D, E, 3);
    AddEdge(&graph, E, C, 7);
    AddEdge(&graph, F, E, 13);

    ConKruskalMST(&graph);
    ShowGraphEdgeInfo(&graph);
    ShowGraphEdgeWeightInfo(&graph);

    GraphDestroy(&graph);

    return 0;
}

[PriorityQueue.c]

#include "PriorityQueue.h"
#include "UsefulHeap.h"

void PQueueInit(PQueue * ppq, PriorityComp pc) {
    HeapInit(ppq, pc);
}

int PQIsEmpty(PQueue * ppq) {
    return HIsEmpty(ppq);
}

void PEnqueue(PQueue * ppq, PQData data) {
    HInsert(ppq, data);
}

PQData PDequeue(PQueue * ppq) {
    return HDelete(ppq);
}

[UsefulHeap.c]

#include "UsefulHeap.h"

void HeapInit(Heap * ph, PriorityComp pc) {
    ph->numOfData = 0;
    ph->comp = pc;
}

int HIsEmpty(Heap * ph) {
    if (ph->numOfData == 0)
        return TRUE;
    else
        return FALSE;
}

int GetParentIDX(int idx) {
    return idx / 2;
}

int GetLChildIDX(int idx) {
    return idx * 2;
}

int GetRChildIDX(int idx) {
    return GetLChildIDX(idx) + 1;
}

int GetHiPriChildIDX(Heap * ph, int idx) {
    if (GetLChildIDX(idx) > ph->numOfData)
        return 0;

    else if (GetLChildIDX(idx) == ph->numOfData)
        return GetLChildIDX(idx);

    else {
        if (ph->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0)
            return GetRChildIDX(idx);
        else
            return GetLChildIDX(idx);
    }
}

void HInsert(Heap * ph, HData data) {
    int idx = ph->numOfData + 1;

    while (idx != 1) {
        if (ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0) {
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
            break;
    }

    ph->heapArr[idx] = data;
    ph->numOfData += 1;
}

HData HDelete(Heap * ph) {
    HData retData = ph->heapArr[1];
    HData lastElem = ph->heapArr[ph->numOfData];

    int parentIdx = 1;
    int childIdx;

    while (childIdx = GetHiPriChildIDX(ph, parentIdx)) {
        if (ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
            break;

        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
    }

    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}

Answer 1

在DLinkedList.c中

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;
}

因此错过了 plist->cur 为 NULL 的情况。如果将代码更改为:

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

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

应该可以正常工作。