Вставка данных в двойной связанный список и сортировка данных
Я хотел бы вставить данные отсортированным способом в отсортированный связанный список. Я могу вставить данные, но они не отсортированы. Может кто-нибудь помочь мне в том, что я делаю неправильно?
Вот моя функция:
typename SortedList<T>::iterator SortedList<T>::insert(const T& data) {if (data < front_->data_) {
Node* n = new Node(data, front_, nullptr);
//if empty
if (front_ == nullptr) {
//make back pt to node
back_ = n;
}
else {
//make front's previous point to node
front_->prev_ = n;
}
//make front point at node
front_ = n;
return SortedList<T>::iterator(n);
}
else {
Node* nn = new Node(data, nullptr, back_);
//if empty
if (front_ == nullptr) {
//make front_ pt to node
front_ = nn;
}
else {
//make back's next point to node
back_->next_ = nn;
}
//make back point at node
back_ = nn;
return SortedList<T>::iterator(nn);
}
И вот мой класс
class SortedList{
struct Node {
T data_;
Node* next_;
Node* prev_;
Node(const T& data = T{}, Node* nx = nullptr, Node* pr = nullptr) {
data_ = data;
next_ = nx;
prev_ = pr;
}
};
Node* front_;
Node* back_;
int sizelist;
}
Решение
Вы не проверяете front_ за nullptr до доступа front_->data,
Но что более важно, вы не пытаетесь вставить данные в какую-либо сортированную позицию. Вы вставляете только в самом начале или в самом конце списка. Чтобы вставить в середину, вы должны просмотреть список в поисках правильного места для вставки.
Попробуйте что-то более похожее на это:
class SortedList{
struct Node {
T data_;
Node* prev_;
Node* next_;
Node(const T& data = T{}, Node* pr = nullptr, Node* nx = nullptr)
: data_(data), prev_(pr), next_(nx)
{
}
};
Node* front_;
Node* back_;
int size_;
...
iterator insert(const T& data);
};
typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
Node *nn = front_;
while ((nn) && (data >= nn->data_)) {
nn = nn->next_;
}
Node *n = new Node(data);
if (nn)
{
n->prev_ = nn->prev_;
n->next_ = nn;
if (nn->prev_) nn->prev_->next = n;
nn->prev = n;
}
else
{
n->prev_ = back_;
if (back_) back_->next_ = n;
back_ = n;
}
if (front_ == nn) front_ = n;
++size_;
return iterator(n);
}
Другие решения
Я не видел ни одного кода, который ищет в списке, чтобы найти, куда вставить элемент. Вы не указали количество ожидаемых элементов; производительность линейной вставки в отсортированный список в среднем равна O (n / 2), что приводит к выводу, что в целом у вас будет O (n ^ 2/2) [это n-квадрат более 2], что недопустимо если п, скажем, 10000 и не имеет значения, если п < 10. Я столкнулся с этой проблемой 20 лет назад при n> 200, на 8088. Существует решение, которое приблизительно равно O (log2 (n)), но, не зная n, я не хочу тратить время на объяснение этого, если это не актуально.
Ваш код указывает на отсутствие ясности в вашем мышлении.
Вам приходится иметь дело со следующими случаями:
- Список пуст.
- Новые данные меньше значений всех элементов в списке.
- Новые данные больше, чем значения всех элементов в списке.
- Новые данные находятся между самым низким и самым высоким значениями элементов в списке.
Кроме того, использование вами «prev» и «next» кажется мне немного странным. Когда я думаю о двусвязном списке, я думаю о нем как:
front -> next -> next -> next -> nullptr
nullptr <- prev <- prev <- prev <- back
Вы, кажется, используете:
front -> prev -> prev -> prev -> nullptr
nullptr <- next <- next <- next <- back
Мой ответ соответствует тому, что я думаю, вы используете, вторая версия. Если это неверно, использование «next» и «prev» необходимо обновить в нескольких местах.
Случай 1
Добавьте следующее в начале вашей функции:
if ( front_ == nullptr )
{
Node* n = new Node(data, nullptr, nullptr);
front_ = n;
back_ = n;
return SortedList<T>::iterator(n);
}
Дело 2
Тебе нужно:
if ( data < front_->data_ )
{
Node* n = new Node(data, front_, nullptr);
front_->prev_ = n;
return SortedList<T>::iterator(n);
}
Дело 3
Тебе нужно:
if ( data > back_->data_ )
{
Node* n = new Node(data, nullptr, back_);
back_->next_ = n;
return SortedList<T>::iterator(n);
}
Дело 4
Тебе нужно:
// Find the place where to insert the new Node.
Node* iter = front_;
for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );
// Insert the new Node.
Node* prev = iter->prev_
Node* n = new Node(data, iter, prev);
prev->next_ = n;
iter->prev_ = n;
return SortedList<T>::iterator(n);
Собираем это вместе:
typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
// Case 1
if ( front_ == nullptr )
{
Node* n = new Node(data, nullptr, nullptr);
front_ = n;
back_ = n;
return SortedList<T>::iterator(n);
}
// Case 2
if ( data < front_->data_ )
{
Node* n = new Node(data, front_, nullptr);
front_->prev_ = n;
return SortedList<T>::iterator(n);
}
// Case 3
if ( data > back_->data_ )
{
Node* n = new Node(data, nullptr, back_);
back_->next_ = n;
return SortedList<T>::iterator(n);
}
// Case 4
// Find the place where to insert the new Node.
Node* iter = front_;
for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );
// Insert the new Node.
Node* prev = iter->prev_
Node* n = new Node(data, iter, prev);
prev->next_ = n;
iter->prev_ = n;
return SortedList<T>::iterator(n);
}