排序单链表时发生运行时错误

Question

我已经写了一个链表（针对数据类型为int的实现）。当我尝试以所有奇怪的方式对列表进行排序时，似乎工作正常[[except元素应排在所有偶数之后，并保留偶数和奇数的原始顺序。

[在MS Visual Studio中调试时，我发现在oddevenSort()函数中，for循环似乎无限进行……好像tail->next未被更新为nullptr。我似乎无法理解错误所在的逻辑。

#include<iostream>

template<class T>
class SLL_Node
{
public:
    T info;
    SLL_Node* next;
    SLL_Node();
    SLL_Node(T el, SLL_Node<T>* n = nullptr);

};

template<class T>
class SLL
{
private:
    SLL_Node<T>* head, * tail;
    size_t size;
public:
    SLL();
    ~SLL();
    bool isEmpty() const;
    size_t get_size() const;
    void add_to_head(T el);
    void add_to_tail(T el);
    void delete_at(size_t); //delete at a certain index. Index starting from 1. Throws an error //message if index out of bounds or list empty. 

    void display()const; //the logic is for mostly primitive data types and not user defined data //types (including classes)
    void oddevenSort();
};

template<class T>
bool SLL<T>::isEmpty() const
{
    if (tail == nullptr)
        return true;
    else
        return false;
}

template<class T>
SLL_Node<T>::SLL_Node() : next{ nullptr }
{}

template<class T>
SLL_Node<T>::SLL_Node(T el, SLL_Node<T>* n) : info{ el }, next{ n }
{}

template<class T>
SLL<T>::SLL()
{
    size = 0;
    head = tail = nullptr;
}

template<class T>
void SLL<T>::add_to_tail(T el)
{
    ++size;
    if (!isEmpty())
    {
        tail->next = new SLL_Node<T>(el);
        tail = tail->next;
    }
    else
        head = tail = new SLL_Node<T>(el);
}

template<class T>
void SLL<T>::add_to_head(T el)
{
    head = new SLL_Node<T>(el, head);
    if (tail == nullptr) //if empty
    {
        tail = head;
    }
    ++size;
}

template<class T>
void SLL<T>::display()const
{
    std::cout << '\n';
    for (SLL_Node<T>* tmp{ head }; tmp != nullptr; tmp = tmp->next)
    {
        std::cout << tmp->info << "->";
    }
    std::cout << "NULL\n";
}

template<class T>
void SLL<T>::delete_at(size_t index)
{


    if (index >= 1 && index <= size) //bound checking 
    {
        if (!isEmpty()) //we dont need is empty since size takes care of that but still adding it for clarity
        {

            if (head == tail && index == 1) //if list only has one node and we delete head node
            {
                delete head;
                head = tail = nullptr;
            }

            //otherwise if list more than one node

            else if (index == 1) //if deleting head node
            {
                SLL_Node<T>* tmp{ head };
                head = head->next;
                delete tmp;
                tmp = nullptr;
            }

            else //deleting other nodes
            {
                SLL_Node<T>* tmp{ head->next }, * pred{ head };
                for (size_t i{ 2 }; i < index; ++i)
                {
                    tmp = tmp->next;
                    pred = pred->next;
                }
                pred->next = tmp->next;
                if (tmp == tail)
                {
                    tail = pred;
                }
                delete tmp;
                tmp = nullptr;
            }

        }
    }

    else
    {
        std::cout<<"\nError! Either the list is empty or the index entered is out of bounds!\n";
    }
}

template<class T>
void SLL<T>::oddevenSort()
{
    SLL_Node<T>* t=head;
    size_t count{1};
    for (; t != nullptr; t = t->next)
    {
        if (((t->info) % 2) != 0)
        {
        add_to_tail(t->info);
        delete_at(count);

        }
        ++count;
    }
}

main

：

int main()
{
    SLL<int> a;
    a.add_to_head(1);
    a.add_to_head(2);
    a.add_to_tail(3);
    a.add_to_tail(4);
    a.add_to_head(6);
    a.add_to_tail(7);
    a.add_to_head(5);
    a.display();
    //a.oddevenSort();
    a.display();
    return 0;
}

Answer 1

很明显，列表连续附加了奇数并转到下一个。

考虑简单的例子，1->2->null在第二次迭代中将变为2->1->null，并且t指向1，它将变为2->1->1，并在删除2->1->null之后