구조체에서 Qsort()가 작동하지 않습니다.

Question

현재 그래프에 일부 알고리즘을 구현 중입니다. 구조체를 사용하여 그래프의 모든 가장자리에 대한 정보 (소스 버텍스, 대상 버텍스 및 가중치)를 유지합니다.

다음

typedef struct edge { 
    int data[3]; //src, dest, weight 
} edge_t, *edge_p; 

내가 변수 포인터를 만들고 n 그래프에서 가장자리의 숫자입니다 n 구조체를위한 메모리를 할당 :

edge_p localEdges = (edge_p)malloc(n*sizeof(edge_t)); 

이

나는 나의 구조체는 다음과 같이 선언 그런 다음 구조체 localEdges을 동일한 유형의 다른 구조체 allEdges의 값으로 채 웁니다.

for (int i = 0; i < num_edges; i++) { 
    localEdges[i].data[0] = allEdges[i].data[0]; 
    localEdges[i].data[1] = allEdges[i].data[1]; 
    localEdges[i].data[2] = allEdges[i].data[2]; 
} 

그리고 나서 데이터 [2] 필드의 오름차순으로 (오름차순 가장자리 무게로) localEdges의 내용을 정렬해야합니다. 내 비교 기능은 이것이다 : 그러나

qsort(localEdges, n, sizeof(edge_t), myComp); 

, 즉 작동하지 않습니다

int myComp (const void *a, const void *b) 
{ 
    const edge_t * ptr_a = (const edge_t *)a; 
    const edge_t * ptr_b = (const edge_t *)b; 
    return ptr_b->data[2] < ptr_a->data[2]; 
} 

그리고 함수에 대한 호출은 다음과 같다. 처리 된 localEdges 배열에 일부 데이터가 잘못 배치되었습니다. 예를 들면 :

localEdges[0].data[2] = 1 
localEdges[1].data[2] = 2 
localEdges[2].data[2] = 1 
localEdges[3].data[2] = 2 
localEdges[4].data[2] = 3 
localEdges[5].data[2] = 3 
localEdges[6].data[2] = 4 

그것이 있어야 할 때 :

localEdges[0].data[2] = 1 
localEdges[1].data[2] = 1 
localEdges[2].data[2] = 2 
localEdges[3].data[2] = 2 
localEdges[4].data[2] = 3 
localEdges[5].data[2] = 3 
localEdges[6].data[2] = 4 

내가 포인터 뭔가가있는 것 같아요,하지만 난 그들과 함께 꽤 확신 아니에요.

제안 사항? 도와 주시면 감사하겠습니다. 표준 C에서

Answer 1

을 함수를 정의 : 귀하의 비교 함수가 잘못된 것입니다. a qsort() manual 인용 : 첫번째 인수가 제 2보다 작거나, 같거나 더 큰 것으로 간주되는 경우

비교 함수는 0이 아닌 정수, 이하 동일, 이상의 반환해야한다. 두 멤버가 equal로 비교되면 정렬 된 배열에서의 순서는 정의되지 않습니다.

따라서 0을 반환하면 두 요소가 동일하게 간주됩니다. *ptr_b의 값이 *ptr_a에 비해 큰 경우

return ptr_b->data[2] < ptr_a->data[2]; 

이 줄 은 수익을 0 않습니다.

올바른 방법은 다음과 같이이해야 할 일 :

int myComp (const void *a, const void *b) 
{ 
    const edge_t * ptr_a = (const edge_t *)a; 
    const edge_t * ptr_b = (const edge_t *)b; 
    if (ptr_a->data[2] < ptr_b->data[2]) return -1; 
    if (ptr_a->data[2] > ptr_b->data[2]) return 1; 
    return 0; 
} 

Answer 2

(7.22.5.2를 qsort 함수)

3 어레이의 내용들은 비교 함수 따라 오름차순으로 정렬은 두 불려 비교 예에 의해 지적 비교되는 객체를 가리키는 인수. 함수는 보다 작거나 같거나 큰 정수를 반환해야합니다. 첫 번째 인수는 각각 또는 두 번째 인수보다 큰 것으로 간주됩니다.

따라서 다음과 같은 방법을 예를 들어 짧은에서

int myComp (const void *a, const void *b) 
{ 
    const edge_t * ptr_a = (const edge_t *)a; 
    const edge_t * ptr_b = (const edge_t *)b; 

    return (ptr_b->data[2] < ptr_a->data[2]) - (ptr_a->data[2] < ptr_b->data[2]); 
} 

Answer 3

그것은 당신의 비교 자 함수를 잘못 구현 된 것 같다. -`edges_t` 선언

int myComp (const void *a, const void *b) 
{ 
    const edge_t * ptr_a = (const edge_t *)a; 
    const edge_t * ptr_b = (const edge_t *)b; 
    return (ptr_b->data[2] < ptr_a->data[2]) ? -1 : 
     (ptr_b->data[2] > ptr_a->data[2]) ? 1 : 0; 
}