我一直在嘗試在不使用交換節點的情況下解決單鏈表中的選擇排序。使用臨時串列來存盤節點并為當前串列分配一個新串列
//my addlastnode function
void AddLastNODE(LIST &mylist, NODE *p)
{
//Check the list is empty or not
if(isEmpty(mylist))
mylist.pHead = mylist.pTail = p;
else
mylist.pTail->pNext = p;
mylist.pTail = p;
}
void selectionSort(LIST &mylist)
{
//Initialize a temp list to store nodes
LIST mylisttemp;
IntList(mylisttemp);
//Create node
NODE *p;
NODE *i;
//Create min node
NODE *min;
//Check if list is empty or has one node
if(mylist.pHead == mylist.pTail)
return;
//Traverse the list till the last node
for(p=mylist.pHead; p->pNext!=NULL && p!=NULL; p = p->pNext)
{
min=p;
for(i=p->pNext; i!=NULL;i=i->pNext)
{
////Find the smallest data in list
if(i->data < min->data)
min=i;
}
////Add the smallest to a new list
AddLastNODE(mylisttemp, min);
}
//Fill the current list to the new list
if(!isEmpty(mylisttemp))
mylist = mylisttemp;
}
uj5u.com熱心網友回復：
您的代碼不會減少您從中選擇節點的串列：應從中洗掉所選節點。要實作這一點，您需要參考所選節點之前的節點，以便您可以重新連接串列以排除所選節點。
您的AddLastNODE函式中還有一個小問題：它不會強制尾節點將 null 作為pNext指標。當使用仍然具有非空pNext指標的節點呼叫該函式時，這可能是導致錯誤的原因。其次，縮進在else塊周圍關閉。在這種情況下它不會導致錯誤，但最好避免混淆：
void AddLastNODE(LIST &mylist, NODE *p)
{
if(isEmpty(mylist))
mylist.pHead = p;
else
mylist.pTail->pNext = p;
mylist.pTail = p; // indentation!
p->pNext = nullptr; // <--- better safe than sorry!
}
然后到主要演算法。在尋找具有最小值的節點時，使用先前的節點參考是非常乏味的。當您暫時使輸入串列回圈時，它會有所幫助：
void selectionSort(LIST &mylist) {
if (mylist.pHead == mylist.pTail) return;
// Make list temporarily cyclic
mylist.pTail->pNext = mylist.pHead;
LIST mytemplist;
IntList(mytemplist);
while (mylist.pHead != mylist.pTail) {
// Select node:
NODE * beforemin = mylist.pTail;
for (NODE * prev = mylist.pHead; prev != mylist.pTail; prev = prev->pNext) {
if (prev->pNext->data < beforemin->pNext->data) {
beforemin = prev;
}
}
NODE * min = beforemin->pNext;
// Extract selected node:
if (min == mylist.pTail) mylist.pTail = beforemin;
if (min == mylist.pHead) mylist.pHead = min->pNext;
beforemin->pNext = min->pNext;
// And insert it:
AddLastNODE(mytemplist, min);
}
// Move last remaining node
AddLastNODE(mytemplist, mylist.pHead);
// Copy back
mylist = mytemplist;
}
附帶說明：您甚至可能希望始終保持串列回圈。這將意味著您可能擁有的其他函式中的一些更改，因為那時將沒有pNext指標為空。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/335271.html
上一篇：C中的for回圈沒有執行