有序链表的建立之链表排序

太过爱你忘了你带给我的痛 2022-09-26 02:19 147阅读 0赞

### 数据结构实验之链表六：有序链表的建立 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

输入N个无序的整数，建立一个有序链表，链表中的结点按照数值非降序排列，输出该有序链表。

#### Input ####

第一行输入整数个数N；  
第二行输入N个无序的整数。

#### Output ####

依次输出有序链表的结点值。

#### Example Input ####

6
    33 6 22 9 44 5

#### Example Output ####

5 6 9 22 33 44

#### Author ####

#include<stdio.h>
    #include<malloc.h>
    int n;
    struct node
    {
        int data;
        struct node *next;
    };
    
    //创建链表
    struct node *creat(int n)
    {
        struct node *tail,*p,*head;
        head=(struct node *)malloc(sizeof(struct node));
        head->next=NULL;
        tail=head;
        for(int i=0;i<n;i++)
        {
            p=(struct node *)malloc(sizeof(struct node));
            scanf("%d",&p->data);
            tail->next=p;
            p->next=NULL;
            tail=p;
        }
        return head;
    };
    
    //链表排序
    struct node *compare(struct node *head)
    {
        //法一：for循环,选择排序
        /*struct node *p,*q;
        for(p=head->next; p!=NULL; p=p->next)
        {
            for(q = p->next; q!=NULL; q=q->next)
            {
                if(p->data > q->data)
                {
                    int t = p->data;
                    p->data = q->data;
                    q->data = t;
                }
            }
        }*/
    
        //法二：while循环，选择排序
        struct node *p,*q;
        p=head->next;
        while(p)
        {
            q=p->next;
            while(q)
            {
                if(p->data>q->data)
                {
                    int t;
                    t=p->data;
                    p->data=q->data;
                    q->data=t;
                }
                q=q->next;
            }
            p=p->next;
        }
    
        //法三：
        /*struct node *p,*q;
        p=head->next;
        q=p->next;
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(p->data>q->data)
                {
                    int t=q->data;
                    q->data=p->data;
                    p->data=t;
                }
                q=q->next;
    
            }
            p=p->next;
            q=p->next;
        }*/
        return head;
    };
    
    
    //输出链表
    void put(struct node *head)
    {
        struct node *q;
        q=head->next;
        while(q!=NULL)
        {
            if(q->next==NULL)
            {
                printf("%d\n",q->data);
            }
            else
            {
                printf("%d ",q->data);
            }
            q=q->next;
        }
    }
    
    
    int main()
    {
        scanf("%d",&n);
        struct node *head1,*head2;
        head1=creat(n);
        head2=compare(head1);
        put(head2);
        return 0;
    }

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1824/pid/2121.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1824/pid/2121.html