单链表的排序

不念不忘少年蓝@ 2022-05-26 02:47 197阅读 0赞

#include <iostream>
    #include <malloc.h>
    using namespace std;
    typedef struct Node{
        int value;
        struct Node *next;
    }node;
    node *Link_head; 
    void Create_Link(){
        Link_head = (node *)malloc(sizeof(node));
        node *pnew,*p=Link_head;
        Link_head->next=NULL;
        int i;
        for(i=1;i<=10;i++){
            pnew=(node*)malloc(sizeof(node));   
            pnew->value=i;
            p->next=pnew;
            p=pnew;
        }
        p->next=NULL;//创建带头结点的单向链表 
    }
    void BubbleSort(node *head){
        int i,t;
        node *p=head->next;//统计实际存储数字的结点数目 
        while(p){
            i++;
            p=p->next;
        }
        head->value=i;//把统计的结点数放进头结点里 
        if(i==1) return;//如果只有一个就不用排序了！ 
        else if(i==2){
            p=head->next;
            t=head->value;
            head->value=p->value;//如果有两个直接比较再一换 
            p->value=t;
        }
        else{
            node *Pre,*Cur,*Next,*LastSwap=NULL,*Temp;
            while(LastSwap!=head->next){
                for(Pre=head,Cur=head->next,Next=Cur->next;Next!=LastSwap;Pre=Pre->next,Cur=Cur->next,Next=Next->next){
                    if(Cur->value<Next->value){
                        Cur->next=Next->next;
                        Pre->next=Next;
                        Next->next=Cur;
                        Temp=Cur;
                        Cur=Next;
                        Next=Temp;
                    }
                }
                LastSwap=Cur;//更新循环界限，防止对已经排序的部分操作 
            }
        }
    
    
    }
    int main(){
        Create_Link();
        node *p=Link_head->next;
        while(p){
            cout<<p->value<<' ';
            p=p->next;
        }
        BubbleSort(Link_head);
        p=Link_head->next;
        cout<<endl;
        while(p){
            cout<<p->value<<' ';
            p=p->next;
        }
    }