C++ 链表实现及排序功能：增删查改、排序

#include using namespace std;

// 实现链表增删查改 template class Linklist { template friend ostream &operator<<(ostream &out, Linklist &ra);

private: T m_data; Linklist *m_next;

public: Linklist(T data = 0); ~Linklist(); void List_add(T const &ra); void List_del(T &ra); T *List_find(T &ra); void List_change(T &ra, T &rb); };

template Linklist::Linklist(T data) { m_data = data; m_next = NULL; }

template Linklist::~Linklist() { delete m_next; }

template void Linklist::List_add(T const &ra) { Linklist *newl = new Linklist(ra); if (this->m_next == NULL) { this->m_next = newl; return; } if (ra <= this->m_data) { newl->m_next = this->m_next; this->m_next = newl; return; } Linklist *prev = this; Linklist *cur = this->m_next; while (cur != NULL && ra > cur->m_data) { prev = cur; cur = cur->m_next; } newl->m_next = cur; prev->m_next = newl; }

template void Linklist::List_del(T &ra) { Linklist *cur = this; while (cur->m_next != NULL) { if (cur->m_next->m_data == ra) { Linklist *temp = cur->m_next; cur->m_next = cur->m_next->m_next; delete temp; return; } cur = cur->m_next; } }

template T *Linklist::List_find(T &ra) { Linklist *cur = this; while (cur != NULL) { if (cur->m_data == ra) { return &(cur->m_data); } cur = cur->m_next; } return NULL; }

template void Linklist::List_change(T &ra, T &rb) { Linklist *cur = this; while (cur != NULL) { if (cur->m_data == ra) { cur->m_data = rb; return; } cur = cur->m_next; } }

template ostream &operator<<(ostream &out, Linklist &ra) { Linklist *cur = &ra; while (cur != NULL) { out << cur->m_data << ' '; cur = cur->m_next; } return out; }

// 使用示例 int main() { Linklist mylist; mylist.List_add(5); mylist.List_add(3); mylist.List_add(7); mylist.List_add(2); mylist.List_add(8); cout << mylist << endl; // 输出：2 3 5 7 8 return 0; }

// 为了实现链表的按数据域内容排序功能，可以在添加新节点时，将节点插入到正确的位置上。 // 可以修改List_add函数来实现排序链表的功能，具体步骤如下： // 1. 创建一个新节点newl，并将要添加的数据赋值给新节点的数据域。 // 2. 如果链表为空，将新节点设置为头节点，并结束函数。 // 3. 如果新节点的数据小于等于头节点的数据，将新节点插入到头节点之前，并将新节点的m_next指向原来的头节点，然后将新节点设置为头节点，并结束函数。 // 4. 创建两个指针prev和cur，分别指向头节点和头节点的下一个节点。 // 5. 遍历链表，直到找到一个节点的数据大于新节点的数据，或者到达链表末尾。 // 6. 将新节点插入到prev和cur之间，并将新节点的m_next指向cur。 // 7. 如果到达链表末尾，将新节点插入到链表末尾。 // 8. 结束函数。 // // 下面是修改后的代码： // // cpp // template <class T> // void Linklist<T>::List_add(T const &ra) // { // Linklist<T> *newl = new Linklist<T>(ra); // if (this->m_next == NULL) // { // this->m_next = newl; // return; // } // if (ra <= this->m_data) // { // newl->m_next = this->m_next; // this->m_next = newl; // return; // } // Linklist<T> *prev = this; // Linklist<T> *cur = this->m_next; // while (cur != NULL && ra > cur->m_data) // { // prev = cur; // cur = cur->m_next; // } // newl->m_next = cur; // prev->m_next = newl; // } // // // 使用示例： // // cpp // int main() // { // Linklist<int> mylist; // mylist.List_add(5); // mylist.List_add(3); // mylist.List_add(7); // mylist.List_add(2); // mylist.List_add(8); // cout << mylist << endl; // 输出：2 3 5 7 8 // return 0; // } // // // 注意：在这个示例中，我们假设链表的数据类型是int，并且使用小于等于运算符来比较节点的数据大小。如果链表的数据类型是自定义的类或结构体，需要重载小于等于运算符来比较数据的大小。