Question

c++中如何根据链表中的一组数据,来排序链表的信息

c++中如何根据链表中的一组数据,来排序链表的信息

Answer 1

排序的方法多种多样，比如冒泡排序，选择排序，插入排序等等。
如果你要比较的那一项是内部数据，就直接比较，如果是你自定义的类型，你就重载一下运算符。
对于整个链表的排序，你就遍历链表，跟用指针给数组排序原理是一样的，只不过把指针的自增改成p = p->next

追问

兄台有没有代码能让我认识一下呢？

追答

#include <iostream>
#include <string>
using namespace std;
struct Stu
{
int id;
string name;
Stu *next;
};
template <class T>
void swap_fun(T &t1, T &t2)
{
T temp = t1;
t1 = t2;
t2 = temp;
}
void sort(Stu *head) //冒泡排序链表 
{
Stu *i = head, *j = nullptr;
while(i != j)
{
while(i->next != j)
{
if(i->id > i->next->id)
{
swap_fun(i->id, i->next->id);
swap_fun(i->name, i->next->name);
}
i = i->next;
}
j = i;
i = head;
}
}
int main()
{
Stu *head = nullptr, *next = nullptr, *temp = nullptr;
while(1) //建立单链表 
{

int id = 0;
string name;
cin >> id;
if(0 == id)
break;
cin >> name;
temp = new Stu;
temp->id = id;
temp->name = name;
temp->next = nullptr;
if(!head)
{
head = temp;
next = temp;
}
else
{
next->next = temp;
next = temp;
}
}
sort(head); //调用函数排序 
while(head != nullptr) //输出单链表 
{
cout << head->id << '\t' << head->name << endl;
Stu *temp = head;
head = head->next;
delete temp; //释放节点 
}

return 0;
}

其实STL库里有一个<list>头文件中定义的模板类list，它是一个双向链表 。如果真要使用链表，不建议自己去建立，可以直接使用list类。它本身有排序的成员函数sort，也可以使用<algorithm>头文件中定义的函数sort排序，总之就不用你自己写sort函数

Answer 2

念都念不懂你说的这是啥

追问

就是用c++创立了一个含有若干数据域的单向链表，如何按照其中的一个数据的大小，对整个链表进行排序？

追答

struct node{int a;int n; .....}; // 存有数据域的结构体

bool  operator<(node one,node two);  结构体的 operator<运算符定义；

list <node> lstl;  //STL 容器链表 

lstl.push_back(node)  //存入数据

sort(lstl.begin(),lstl.end()); //调用 sort 排序就行了

#include <iostream>
#include<algorithm>
#include <list>
#include <iterator>
using namespace std;
struct node{
    string name;
    int a;
    int n;
};

bool  operator<(node one,node two){
return one.n<two.n;

}
void fun(node no){
    cout.width(10);

    cout<<left<<no.name<<' '<<no.a<<' '<<no.n<<endl;
}

int main()
{
    node a1={"zhangsan",10,17};
    node a2={"lisi",13,14};
    node a3={"wangwu",15,20};
list <node> lst;
lst.push_back(a1);
lst.push_back(a2);
lst.push_back(a3);
lst.sort();
for_each(lst.begin(),lst.end(),fun);
return 0;
}