时间戳

首页 > 解决方案 > 对单链表进行排序时出现运行时错误

c++ - 对单链表进行排序时出现运行时错误

问题描述

我编写了一个链表（针对数据类型 int）实现。似乎工作正常，除非我尝试以这样一种方式对列表进行排序，即所有奇数元素都应该排在所有偶数元素之后，并保留偶数和奇数的原始顺序。

在 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;
    }
}

主要：

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;
}

标签： c++sortinginfinite-loopsingly-linked-list

解决方案

考虑一个示例输入oddevenSort a(1)->b(2) ->c(3)->null

  1. 在第 1 次迭代t中，指向新节点，并使用附加在列表末尾的 a(1)数据创建，如.1b(2)->c(3)->d(1)->null
  2. 在第 2 次迭代t中将指向节点b(2)，并且列表上没有进行任何更改。
  3. 在第 3 次迭代t将指向节点，新节点将使用附加在列表末尾的 c(3)数据创建，如.3b(2)->d(1)->e(3)->null
  4. 第 4 次迭代t将指向d(1)在列表末尾创建新节点的节点。迭代以递归方式进行，而不会破坏循环。

每次您都不需要删除和创建新节点。您可以分离偶数和奇数节点并制作最终列表。

这是更新的片段

template<class T>
void SLL<T>::oddevenSort()
{
    SLL_Node <T>tempOddHeader;
    SLL_Node <T> *tempOddPtr = &tempOddHeader;
    SLL_Node <T> tempEvenHeader;
    SLL_Node <T> *tempEvenPtr = &tempEvenHeader;

    SLL_Node<T>* t = head;
    tempOddHeader.next = nullptr;
    tempEvenHeader.next = nullptr;

    while(t)
    {
        if (((t->info) % 2) != 0) {
            //append to the odd list
            tempOddPtr->next = t;
            tempOddPtr = tempOddPtr->next;
            t = t->next;
            tempOddPtr->next = nullptr;
        }
        else {
            //append to the even list
            tempEvenPtr->next = t;
            tempEvenPtr = tempEvenPtr->next;
            t = t->next;
            tempEvenPtr->next = nullptr;
        }
    }

    tempEvenPtr->next = tempOddHeader.next;
    head = tempEvenHeader.next;
    tail = tempOddPtr;
}

推荐阅读