Question

c和c++中如何对链表进行排序呢

我一直搞不懂链表的排序，自己写的算法老是出问题，希望哪位高手给我写个相关算法，最好加上详细的注释，最后再做画龙点睛般的说明！！不胜感激！！

Answer 1

你说的链表是什么链表？
单链表、循环链表、双向链表？
其实没什么难的，主要是指针指来指去容易糊涂
你可以找本数据结构的书，找到上面的链表操作，在草稿纸上画个图，就明白了。
链表插入排序的算法：
备注：key 为链表节点的关键码； link为节点的链接指针
getKey（） 取当前节点的关键码
getLink（）取当前节点的链接指针
setKey（） 给当前节点的关键码重新赋值
setLink（）给当前节点的指针重新赋值
int LinkInsertSort （） ｛
list.Vector[0].setKey(MaxNum);
list.Vector[0].setLink(1);
list.Vector[1].setLink(0);//初始化，形成只有头节点的循环链表
for(int i=2;i<=list.CurrentSize.i++)//向一个有序的链表中插入一个节点，需要对链表进行检索，currentsize为当前链表长度；
{
int current=list.Vector[0].getLink();//current 指向当前节点
int pre = 0;//pre指向current的前驱
while (list.Vector[current].getKey()<= List.Vector[i].getKey())//查找插入位置
{
pre = current;current = list.Vector[current].getLink(); // 每查找完一个节点，pre要跟上current，current要指向下一个节点。
}//以下操作是节点i插入pre 与 current之间
List.Vector[i].setLink(current);//将节点i的后继指针指向current
list.Vector[pre].setLink(i);// 将current的前一节点的后继指针指向i }
｝

Answer 2

template<class T>
Chain<T>Chain<T>::Merge(Chain<T>&C)const{
Chain<T> p;
ChainIterator<T> l1,l2;
T x1,x2;
x1=l1.Initialize(*this);
x2=l2.Initialize(C);
while(x1&&x2){
if(x1>x2){
p.InsertAtHead(x2);
x2=l2.Next();
cout<<p<<endl;
}
else{
p.InsertAtHead(x1);
x1=l1.Next();
cout<<p<<endl;
}
}
cout<<p<<endl;
while(x1){
p.InsertAtHead(x1);
x1=l1.Next();
}
while(x2){
p.InsertAtHead(x2);
x2=l2.Next();
}

}
用遍历器很方便

Answer 3

看别人写的程序，那是别人的想法，还不如你把你自己写的程序发出来，我给你找找问题。

我百度Hi常在线，有什么问题可以直接问我。