我正在嘗試對帶有節點的雙向鏈表進行排序以進行分配，因為這就是規范要我做的。我想基本上用排序創建一個新串列，然后分配頭部和尾部
我的程式的兩個 .h 檔案：
#ifndef SN_H
#define SN_H
#include <string>
#include <sstream>
//SortNode class implementation here
template <class T>
class SortNode
{
protected:
T value;
public:
SortNode<T> * next;
SortNode<T> * prev;
SortNode(T);
std :: string print();
T getValue();
};
#include "SortNode.cpp"
#endif
#ifndef DLL_H
#define DLL_H
#include "SortNode.h"
template <class T>
class SortList
{
private:
bool ascending;
SortNode<T> * head;
SortNode<T> * tail;
public:
SortList(bool);
void add(SortNode<T>* a) ;
SortNode<T>* remove(T val);
void setAsc(bool a);
void sort() ;
string print() ;
SortNode<T>*getHead() ;
string debug() ;
};
#include "SortList.cpp"
#endif
我試影像我描述的那樣對其進行排序，但是它陷入了一個回圈，并且不知道如何做到這一點。
這是給我帶來問題的排序功能。
template <class T>
void SortList<T> :: sort()
{
cout<<"above if "<<endl;
if (ascending == true)
{
SortNode<T> * node = head, *ptr = NULL ,*sortedh = NULL, *sortedt = NULL, *newnode = NULL;
while (node != NULL)
{
newnode = node;
if (!sortedh)
{
sortedh = node;
sortedt = node;
}
else
{
ptr = head;
while (ptr!= NULL && ptr -> getValue() < newnode -> getValue())
{
ptr = ptr -> next;
}
if (!ptr)
{
sortedt -> next = newnode;
newnode ->prev = sortedt;
sortedt = newnode;
}
else
{
if (ptr ->prev == NULL)
{
newnode -> next = ptr;
ptr -> prev =newnode;
sortedh = newnode;
}
else
{
ptr -> prev -> next = newnode;
newnode -> prev =ptr -> prev;
newnode -> next =ptr;
ptr -> prev = newnode;
}
}
}
node = node -> next;
}
}
}
任何幫助將不勝感激。
uj5u.com熱心網友回復：
代碼有錯誤。
例如，在這個代碼片段中甚至有兩個錯誤。
if (!sortedh)
{
sortedh = node;
sortedt = node;
}
else
{
ptr = head;
//...
相反，你需要寫
if (!sortedh)
{
sortedh = node;
sortedt = node;
node->next = nullptr;
}
else
{
ptr = sortedh;
//...
或者在這個 if 陳述句中
if (!ptr)
{
sortedt -> next = newnode;
newnode ->prev = sortedt;
sortedt = newnode;
}
您忘記設定指標指向的節點的下一個資料成員，newnode例如
if (!ptr)
{
sortedt -> next = newnode;
newnode ->prev = sortedt;
newnode->next = nullptr;
sortedt = newnode;
}
或者在這個 if 陳述句中
if (ptr ->prev == NULL)
{
newnode -> next = ptr;
ptr -> prev =newnode;
sortedh = newnode;
}
例如，您忘記設定指標 newnode 指向的節點的資料成員 prev
newnode -> next = ptr;
newnode->prev = ptr->prev; or newnode->prev = nullptr;
還有一個問題。指標指向的節點的資料成員next是node可以改變的。所以這個說法
node = node -> next;
可能導致指標node可以指向已處理的節點。
該函式也不設定指標head和tail.
這是一個演示程式，展示了如何定義實作插入排序方法的函式。為了簡化程式的撰寫，我對類定義做了一些小的改動。
#include <iostream>
#include <cstdlib>
#include <ctime>
//SortNode class implementation here
template <class T>
class SortNode
{
protected:
T value;
public:
SortNode *prev;
SortNode *next;
SortNode( const T &value, SortNode *prev = nullptr, SortNode *next = nullptr )
{
this->value = value;
this->prev = prev;
this->next = next;
}
const T & getValue() const
{
return value;
}
T & getValue()
{
return value;
}
};
template <class T>
class SortList
{
private:
bool ascending = true;
SortNode<T> *head = nullptr;
SortNode<T> *tail = nullptr;
public:
SortList() = default;
void add( const T &value )
{
SortNode<T> *new_node = new SortNode<T>{ value, tail, nullptr };
if (!head)
{
head = new_node;
}
else
{
tail->next = new_node;
}
tail = new_node;
}
SortNode<T> *remove( T val );
void setAsc( bool a );
void sort();
std::ostream &print( std::ostream &os = std::cout ) const
{
for (SortNode<T> *current = head; current != nullptr; current = current->next)
{
os << current->getValue() << " -> ";
}
return os << "null";
}
SortNode<T> *getHead();
};
template <class T>
void SortList<T> ::sort()
{
if (ascending)
{
SortNode<T> *node = head, *sortedh = nullptr, *sortedt = nullptr;
while (node != NULL)
{
SortNode<T> *newnode = node;
SortNode<T> *next = node->next;
if (!sortedh)
{
sortedh = node;
sortedt = node;
node->next = nullptr;
}
else
{
SortNode<T> *ptr = sortedh;
while (ptr != NULL && !( newnode->getValue() < ptr->getValue() ) )
{
ptr = ptr->next;
}
if (!ptr)
{
sortedt->next = newnode;
newnode->prev = sortedt;
newnode->next = nullptr;
sortedt = newnode;
}
else
{
if (ptr->prev == NULL)
{
newnode->next = ptr;
newnode->prev = nullptr;
ptr->prev = newnode;
sortedh = newnode;
}
else
{
ptr->prev->next = newnode;
newnode->prev = ptr->prev;
newnode->next = ptr;
ptr->prev = newnode;
}
}
}
node = next;
}
head = sortedh;
tail = sortedt;
}
}
int main()
{
SortList<int> list;
const int N = 20;
srand( ( unsigned int )time( nullptr ) );
for (int i = 0; i < N; i )
{
list.add( rand() % N );
}
list.print() << '\n';
list.sort();
list.print() << '\n';
}
程式輸出可能看起來像
17 -> 12 -> 0 -> 12 -> 8 -> 8 -> 8 -> 13 -> 4 -> 7 -> 8 -> 11 -> 7 -> 8 -> 18 -> 4 -> 16 -> 18 -> 18 -> 3 -> null
0 -> 3 -> 4 -> 4 -> 7 -> 7 -> 8 -> 8 -> 8 -> 8 -> 8 -> 11 -> 12 -> 12 -> 13 -> 16 -> 17 -> 18 -> 18 -> 18 -> null
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/524705.html