Question

请问哪位高手知道:使用C++语言如何写一个"运用链表来排序"的函数？谢谢啦！

Answer 1

//这是我写的一个链表排序的程序 看能不能帮助你
#include<iostream>
using namespace std;
struct student
{
int num;
student* link;
};
typedef student* Ptr;

int main()
{
int x;
Ptr head=NULL,p=NULL,q=NULL,qHead=NULL,head0=NULL;

cout<<"input a list of number ,end with nonpositive numbers\n"; //输入一组数据 以负数结束
cin>>x;

while(x>=0)
{
p=new student; //前插法建立链表 我相信你要的是排序算法
p->num=x;
p->link=NULL; //你可以以另一种方式建立的
p->link=head;
head=p;
cin>>x;
}

p=head;
while(p!=NULL)
{
cout<<p->num<<' '; //以前插法建立链表 那么它的数据顺序
p=p->link; //和你输入的相反 以另一种方式可以和你输入的相同
}
while(head!=NULL)
{
qHead=head;
head=head->link;
p=head0;
while(p!=NULL&&p->num<qHead->num)
{
q=p;
p=p->link;
}
if(head0==NULL)
{
head0=qHead;
qHead->link=NULL;
}
else
{

if(p==head0&&p->num>=qHead->num)
{
head0=qHead;
qHead->link=p;

}
else
{
q->link=qHead;
qHead->link=p;

}

}
}
p=head0;
cout<<"have ordered\n";
while(p!=NULL)
{
cout<<p->num<<' '; //输出排序后结果
p=p->link;
}
return 0;
}
/*while(x>=0)
{
p=new person; //以这种方式建立的话 链表数据的顺序和你的输入顺序相同
p->num=x;
p->link=NULL;
if(head==NULL)
{
head=p;
q=head;
}
else
{q->link=p;
q=q->link;
}
cin>>x;
}
q->link=NULL;
*/

Answer 2

你可以按一个数值来进行，首先，先建一个链表，将你要的数值填入，然后按照每个节点排序，可以用冒泡法排序，其实就是比较那个节点的数值的大小排序，和数组的排序其实并没有差别