使用數組對C++中的鏈表進行排序以對其數據進行排序

我試圖通過將每個節點的數據複製到一個數組中來排序列表。然後，在對數組進行排序的代碼之後，我試圖將數組元素中的值複製到每個節點的列表列表中。這是甚至可能的，我試圖研究的問題不能找到一個直線是或否。我不想從cstdlib中使用qsort，這個崩潰，我想知道是否有辦法使這項工作。 Insight深表讚賞。使用數組對C++中的鏈表進行排序以對其數據進行排序

template <typename NODETYPE> 
void List<NODETYPE>::sort(){ 
ListNode<NODETYPE>* currentPtr = firstPtr; 
    int N = sizeOfList(); 
    NODETYPE a[N]; 
    int l = 0; 
    int r = 0; 
    int i,j,min,imin,tmp; 

    while(currentPtr != NULL){ 
     a[l] = currentPtr->data; 
     currentPtr = currentPtr ->nextPtr; 
     l++; 
    } 

for (i=0;i<N-1;i++) 
{ 
    imin=i; 
    min=a[i]; 
    for (j=i+1;j<N;j++) 
     if (a[j]<min) 
     { 
      min=a[j]; 
      imin=j; 
     } 

    tmp=a[imin]; 
    a[imin]=a[i]; 
    a[i]=tmp; 
} 


    for (int y = 0; y < N-1; y++){ 
     currentPtr->data = a[y]; 
     currentPtr = currentPtr->nextPtr; 
    } 
    lastPtr->data = a[N];

}

來源

2016-09-17 programmerintraining

*這是甚至可能的* - 確定這是可能的 - 這是窮人的排序鏈表的方式，但它的工作原理。然而這個：'int N = sizeOfList（）; NODETYPE a [N];'是無效的C++，因爲不能使用變量聲明數組作爲項目的數量。 – PaulMcKenzie

'NODETYPE a [N]'不是標準的C++，它是一些編譯器的擴展。請注意，如果清單很大，這將導致您的堆棧被吹走。考慮使用'std :: vector'來代替。你可能也想看看'std :: swap'。 – kfsone

另外，您的'List'類是否有一個公共接口，允許外部用戶更改List的數據？如果不是，則需要編寫一個，因爲如果沒有辦法更改數據，則無用。外部世界是否有辦法從頭到尾遍歷列表？我再次問這個，因爲沒有它就沒用了。有了這兩個函數，只需利用已經寫好的內容，就可以輕鬆地對列表進行「排序」。 – PaulMcKenzie

首先，使用std::sort，而不是你的人工分揀代碼。 qsort()崩潰的原因是因爲它是一個對C++類一無所知的C庫函數。 std::sort()將能夠正確排序你的數組。

除此之外，代碼中有多個錯誤會在排序後執行。當前的代碼執行以下操作：

for (int y = 0; y < N-1; y++){ 
    currentPtr->data = a[y]; 
    currentPtr = currentPtr->nextPtr; 
} 
lastPtr->data = a[N];

這裏的問題是，currentPtr已經使用，排序前，在列表中行走，在這一點上是NULL。如果你只是試着discussing your code with your rubber duck，你的橡皮鴨會告訴你的。

因此，第一次迭代會導致空指針解引用和崩潰。

你只需要：

重置currentPtr回listPtr。
您可以去掉列表中最後一個元素的特殊框。它完成沒有用處。此外，這是錯誤的：
```
lastPtr->data = a[N]; 
```

由於a有N元素，最後一個元素是a[N-1]，這將流失數組的結束，導致不確定的行爲。

就像我說，可以完全除去這一點，並簡單地遍歷整個範圍：

for (int y = 0; y < N; y++){

最後，似乎使用gcc的可變長度數組擴展，這是不便攜的。而不是聲明

NODETYPE a[N];

，你應該簡單地用一個向量：

std::vector<NODETYPE> a; 

a.reserve(n);

...然後push_back()每一個值，在隨後的循環。

如果你不想使用std::vector，你可以暫時將new這個數組，然後delete它之後。

來源

2016-09-17 00:50:15

使用數組對C++中的鏈表進行排序以對其數據進行排序

回答

相關問題