Qsort（）在結構上不起作用

我目前在圖上實現了一些算法，我使用一個結構來保存關於圖中每條邊的信息：它的源頂點，它的目標頂點和它的權重。Qsort（）在結構上不起作用

我有結構中聲明如下：

然後我創建變量指針和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]; 
}

然後我需要按localEdges的內容按數據[2]字段的升序排序（按邊緣權重上升）。我比較功能是這樣的：

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

和呼叫的功能如下：

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

然而，這是行不通的。已處理的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

我想有一些與指針，但我不與他們相當有信心。

有什麼建議嗎？我會欣賞你的幫助。

來源

2017-10-20 Indie_Cube

'常量edges_t * ptr_a' < - 其中'edges_t'聲明？我只看到'edge_t'。順便說一句，最好不要爲你自己的類型使用'_t'後綴，它被POSIX保留用於未來的擴展。 –

用'return ptr_a-> data [2] - ptr_b-> data [2];'替換'return ptr_b-> data [2] < ptr_a-> data [2];'。 –

我假設'n == num_edges'？ –

簡而言之：你比較函數是錯誤的。援引a qsort() manual：

比較函數必須返回一個整數比小於零，等於，或大於，如果第一自變量被認爲是比上述第二分別小於，等於，或更大。如果兩個成員比較相等，則它們在已排序數組中的順序是未定義的。

所以，如果你要返回0，這兩個元素被認爲是相等的。

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

此行確實回報0如果*ptr_b值比*ptr_a更大。

正確的方式做到這一點如下：

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

來源

2017-10-20 14:45:36

從C標準（7.22.5.2的qsort函數）

3數組的內容被分類到根據到一個比較函數升序指向COMPAR，這被稱爲與 2指向被比較對象的論據。 如果第一個參數被認爲分別小於，等於到或大於第二個，函數應返回小於，等於或大於零的整數。

這樣定義的函數，例如下面的方式

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

來源

2017-10-20 14:45:17

看來你比較器功能被錯誤地執行。它永遠不會返回負的結果，只是布爾值（比較運算）轉換爲0和1。你能不能嘗試類似的東西：

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

來源

2017-10-20 14:47:19

Qsort（）在結構上不起作用

回答

相關問題