在结构中qsort结构数组

Question

我正在研究Kruskal算法。使用qsort函数的排序部分会创建一个奇怪的节点行为：它按权重正确排序，但会更改每个节点的父节点。当程序执行FIND-SET(X)函数时，这种行为给我一个堆栈溢出。 这里是我的代码：

#include <iostream> 

/* 
*DISJOINT 
*SETS 
*/ 
typedef struct NODE { 
    int rank; 
    int data; 
    struct NODE *parent; 
} NODE; 

//MAKE-SET(x) 
void makeSet(NODE *node) { 
    node->parent = node; 
    node->rank = 0; 
} 

//FIND-SET(x) 
NODE *findSet(NODE *node) { 
    if (node != node->parent) { 
     node->parent = findSet(node->parent); 
    } 
    return node->parent; 
} 

//LINK(x, y) 
void link(NODE *nodeX, NODE *nodeY) { 
    if (nodeX->rank > nodeY->rank) { 
     nodeY->parent = nodeX; 
    } else { 
     nodeX->parent = nodeY; 
     if (nodeX->rank == nodeY->rank) { 
      nodeY->rank += 1; 
     } 
    } 
} 

//UNION(x, y) 
void unionSet(NODE *nodeX, NODE *nodeY) { 
    link(findSet(nodeX), findSet(nodeY)); 
} 



/* 
*GRAPH 
*/ 
typedef struct EDGE { 
    NODE source; 
    NODE destination; 
    int weight; 
} EDGE; 

typedef struct GRAPH { 
    int V; //Number of vertices/nodes 
    int E; //Number of edges 
    EDGE *edge; //Array of edges 
} GRAPH; 

GRAPH *newGraph(int allocatedNumberOfVertices, int allocatedNumberOfEdges) { 
    GRAPH *graph = (GRAPH *)malloc(sizeof(GRAPH)); 
    graph->E = 0; // intial state: no edges 
    graph->V = allocatedNumberOfVertices; 
    graph->edge = (EDGE *)malloc((allocatedNumberOfEdges) * sizeof(EDGE)); 
    return graph; 
} 

void addEdge(GRAPH *graph, NODE srcNode, NODE dstNode, int weight) { 
    graph->edge[graph->E].source = srcNode; 
    graph->edge[graph->E].destination = dstNode; 
    graph->edge[graph->E].weight = weight; 
    graph->E += 1; 
} 

int compareEdges(const void *first, const void *second) { 
    const EDGE *firstEdge = (const EDGE *)first; 
    const EDGE *secondEdge = (const EDGE *)second; 

    if (firstEdge->weight == secondEdge->weight) { 
     return 0; 
    } else if (firstEdge->weight > secondEdge->weight) { 
     return 1; 
    } else { 
     return -1; 
    } 
} 

/*Kruskal's algorithm - returns an array of least weighted edges*/ 
EDGE *getMinimumSpanningTree(GRAPH *graph) { 
    int V = graph->V; 
    int E = graph->E; 
    int resultE = 0; 
    EDGE *result = (EDGE *)malloc(E * (sizeof(EDGE))); 

    //create a disjoint-set for every node 
    for (int e = 0; e < E; e++) { 
     makeSet(&(graph->edge[e].source)); 
     makeSet(&(graph->edge[e].destination)); 
    } 


    //sort edges of graph into nondecreasing order by weight 
    qsort(graph->edge, graph->E, sizeof(struct EDGE), compareEdges); 

    //finds a safe edge to add to the growing forest 
    for (int e = 0; e < E; e++) { 
     if (findSet(&(graph->edge[e].source))->data != findSet(&(graph->edge[e].destination))->data) { 
      result[resultE++] = *graph->edge; 
      unionSet(&(graph->edge[e].source), &(graph->edge[e].destination)); 
     } 
    } 

    return result; 
} 

void KruskalDemo() { 
    GRAPH *graph = newGraph(6, 9); 
    NODE node[6]; 
    for (int i = 0; i < 6; i++) { 
     node[i].data = i; 
    } 

    addEdge(graph, node[0], node[1], 3); 
    addEdge(graph, node[1], node[2], 1); 
    addEdge(graph, node[2], node[3], 1); 
    addEdge(graph, node[3], node[0], 1); 
    addEdge(graph, node[3], node[1], 3); 
    addEdge(graph, node[3], node[4], 6); 
    addEdge(graph, node[4], node[2], 5); 
    addEdge(graph, node[4], node[5], 2); 
    addEdge(graph, node[5], node[2], 4); 


    EDGE *MST = getMinimumSpanningTree(graph); 

    //we expect to have 5 vertices 
    for (int i = 0; i < 5; i++) { 
     printf("weight(%d, %d) = %d\n", MST->source.data, MST->destination.data, MST->weight); 
    } 
} 

int main() { 
    KruskalDemo(); 
    return 0; 
} 

Answer 1

我解决：问题是算法和结构边缘的领域是不是指针：

改变了这一切：

typedef struct EDGE { 
    NODE source; 
    NODE destination; 
    int weight; 
} EDGE; 

到：

typedef struct EDGE { 
    NODE *source; 
    NODE *destination; 
    int weight; 
} EDGE; 

而算法为：

for (int e = 0; e < E; e++) { 
    if (findSet(graph->edge[e].source)->data != findSet(graph->edge[e].destination)->data) { 
     result[resultE++] = graph->edge[e]; 
     unionSet(graph->edge[e].source,graph->edge[e].destination); 
    } 
}