小贝子编程

C语言 调试错误:克鲁斯卡尔算法，ADT



学习ADT，C语言图形的初学者。

这是调试捕获的代码。调试结果为 plist->cur was 0xCDCDCDCD 。(来自DLinkedList.c( 而Debug程序说，上层代码在这些调用序列上出现错误。

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

我不明白为什么这是错误。 你能帮我找到这个代码的问题吗？这对我非常有帮助。克鲁斯卡尔的总代码在此行下。

谢谢

附言这些代码在名为"使用C研究ADT的数据结构简介"的书中。

文件名-> ALEdge.h/ALGraphKruskal.h/ArrayBaseStack.h/DLinkedList.h/PriorityQueue.h/UsefulHeap.h/ALGraphKruskal.c/ArrayBaseStack.c/DLinkedList.c/KruskalMain.c/PriorityQueue.c/UsefulHeap.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__

[有用堆.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);
}

[有用堆]

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

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

它应该可以正常工作。

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium