|
不是所有的排序算法都可以用单链表来实现，比如快速排序和堆排序，由于单链表不具有随机访问的特性，所以也受限制
本题中的简单选择排序，在单链表中实现的思路：每次遍历链表中的剩余部分，每一趟将剩余部分中最大结点插到表头，最后即可得一条由小到大的单链表，思路很简单，具体还得落实到代码上，你会了，不代表你的手也会了
#include
using namespace std;
typedef struct Node{
int val;
Node*next;
}Node,*ListNode;
void build(ListNode &L)//尾插法
{
L=(Node*)malloc(sizeof(Node));
int x;
cin>>x;
Node*p=L;
while(x!=999){
Node*q=(Node*)malloc(sizeof(Node));
q->next=nullptr;
q->val=x;
p->next=q;
p=q;
cin>>x;
}
}
void visit(ListNode&L)
{
ListNode p=L->next;
while(p){
coutnext;
}
if(s==h){
h=h->next; //最大结点在原链表前端
}
else r->next=s->next; //将最大结点在原链表中删除
s->next=L; //结点s插入结果链前端
L=s;
}
}
int main()
{
ListNode L;
build(L);
visit(L);
selectsort(L);
visit(L);
return 0;
}
|