对链接列表模板进行冒泡排序

Question

我正在尝试对链接列表进行排序。我在 const 方面遇到问题。它不会让我分配给一个 const 变量，而这正是它应该做的。但是，我不知道如何解决这个问题？ 如果我能得到任何帮助，我将不胜感激。

这些都在一个头文件中，排序函数也是，我会尝试将其拉出来，以便很容易找到：

void LinkedList<T>::BubleSort()
{

T temp;
ListElement<T>* cur = head;

    const ListElement<T>* forward = head->Next();


while(cur)
{
    while(forward)
    {

        if(cur->Datum() > forward->Datum())
        {

                  temp = cur->Datum();
                  cur->Datum() = forward->Datum();
                  forward->Datum() = temp;
        }
    }
}

}

我得到的错误

错误 C3892：“cur”：无法分配给 const 变量 编译类模板成员函数“void LinkedList::BubleSort(void)”时 请参阅正在编译的类模板实例化“LinkedList”的参考

当然如果它是 const 我不能这样做，我只是不知道如何解决这个问题。

这是包含所有信息和排序函数的头文件：

#include  <typeinfo>

template <class T>
class LinkedList;

template <class T>
class ListElement
{
T datum;
ListElement* next;

ListElement (T const&, ListElement*);
public:
T const& Datum () const;
ListElement const* Next () const;

friend class    LinkedList<T>;  
};

template <class T>
class LinkedList
{
ListElement<T>* head;
ListElement<T>* tail;
public:
LinkedList ();
~LinkedList ();

LinkedList (LinkedList const&);
LinkedList& operator = (LinkedList const&);

ListElement<T> const* Head () const;
ListElement<T> const* Tail () const;
bool IsEmpty () const;
T const& First () const;
T const& Last () const;

void BubleSort();
void Prepend (T const&);
void Append (T const&);
void Extract (T const&);
void Purge ();
void InsertAfter (ListElement<T> const*, T const&);
void InsertBefore (ListElement<T> const*, T const&);
};

template <class T>
ListElement<T>::ListElement (
T const& _datum, ListElement<T>* _next) :
datum (_datum), next (_next)
{}

template <class T>
T const& ListElement<T>::Datum () const
{ return datum; }

template <class T>
ListElement<T> const* ListElement<T>::Next () const
{ return next; }



template <class T>
LinkedList<T>::LinkedList () :
head (0),
tail (0)
{}


template <class T>
void LinkedList<T>::Purge ()
{
while (head != 0)
{
ListElement<T>* const tmp = head;
head = head->next;
delete tmp;
}
tail = 0;
}

template <class T>
LinkedList<T>::~LinkedList ()
{ Purge (); }



template <class T>
ListElement<T> const* LinkedList<T>::Head () const
{ return head; }

template <class T>
ListElement<T> const* LinkedList<T>::Tail () const
{ return tail; }

template <class T>
bool LinkedList<T>::IsEmpty () const
{ return head == 0; }



template <class T>
T const& LinkedList<T>::First () const
{
if (head == 0)
    throw std::domain_error ("list is empty");
return head->datum;
}

template <class T>
T const& LinkedList<T>::Last () const
{
if (tail == 0)
    throw std::domain_error ("list is empty");
return tail->datum;
}
/**********************************************/

template <class T>

void LinkedList<T>::BubleSort()
{

T temp;
ListElement<T>* cur = head;
;
const ListElement<T>* forward = head->Next();


while(cur)
{
    while(forward)
    {

        if(cur->Datum() > forward->Datum())
        {

          temp = cur->Datum();
          cur->Datum() = forward->Datum();
          forward->Datum() = temp;
        }
    }
}

}

template <class T>
void LinkedList<T>::Prepend (T const& item)
{
ListElement<T>* const tmp = new ListElement<T> (item, head);
if (head == 0)
tail = tmp;
head = tmp;
}



template <class T>
void LinkedList<T>::Append (T const& item)
{
ListElement<T>* const tmp = new ListElement<T> (item, 0);
if (head == 0)
head = tmp;
else
tail->next = tmp;
tail = tmp;
}



template <class T>
LinkedList<T>::LinkedList (LinkedList<T> const& linkedList) :
head (0),
tail (0)
{
ListElement<T> const* ptr;
for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
Append (ptr->datum);
}

template <class T>
LinkedList<T>& LinkedList<T>::operator = (
LinkedList<T> const& linkedList)
{
if (&linkedList != this)
{
Purge ();
ListElement<T> const* ptr;
for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
    Append (ptr->datum);
}
return *this;
}



template <class T>
void LinkedList<T>::Extract (T const& item)
{
ListElement<T>* ptr = head;
ListElement<T>* prevPtr = 0;
while (ptr != 0 && ptr->datum != item)
{
prevPtr = ptr;
ptr = ptr->next;
}
if (ptr == 0)

    throw std::invalid_argument ("item not found");

if (ptr == head)
head = ptr->next;
else
prevPtr->next = ptr->next;
if (ptr == tail)
tail = prevPtr;
delete ptr;
}




template <class T>
void LinkedList<T>::InsertAfter (
ListElement<T> const* arg, T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if (ptr == 0)
{

}
throw std::invalid_argument ("invalid position");
ListElement<T>* tmp = new ListElement<T> (item, ptr->next);
ptr->next = tmp;
if (tail == ptr)
{

}
tail = tmp;
}

template <class T>
void LinkedList<T>::InsertBefore (
ListElement<T> const* arg, T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if (ptr == 0)
{

}
throw std::invalid_argument ("invalid position");
ListElement<T>* const tmp = new ListElement<T> (item, ptr);
if (head == ptr)
{

}
head = tmp;
else
{
ListElement<T>* prevPtr = head;
while (prevPtr != 0 && prevPtr->next != ptr)
    prevPtr = prevPtr->next;
if (prevPtr == 0)
{

}
throw std::invalid_argument ("invalid position");
prevPtr->next = tmp;
}
}

Answer 1

对列表进行排序是一个非常量操作；你不能仅使用 const 访问器来做到这一点。通常的解决方案是使用 const 和非常量变量重载访问器：

ListElement const* Next() const { return next; }
ListElement* Next() { return next; }

您可以对 LinkedList 类中的访问器函数执行相同的操作（当然，除非您想让列表不可变）。

Answer 2

...此外，您编写 Datum() 返回 const 引用，但随后您使用 Datum() 调用作为“cur->Datum() =forward->Datum() 中的左值” ;”。当左侧的内容不可变时，该分配将如何进行？

另外，您可以将forward声明为指向常量ListElement的指针，然后在赋值的LHS上使用forward：“forward->Datum() = temp;”。你可能实际上总是希望在两个 while() 中forward == cur->Next() 。 （即总是更新以指向接下来的内容。）所以它不能是 const。

考虑到您似乎想要使用的可变性数量，您确实必须重新考虑 const 的使用。