SDUT-2121_数据结构实验之链表六：有序链表的建立

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

第一行输入整数个数N；

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

Output

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

Sample Input

6

33 6 22 9 44 5

Sample Output

5 6 9 22 33 44

Hint

不得使用数组！

链表的插入操作，找到链表中第一大于或等于x的节点，将x插入该节点之前就好，注意考虑链表中没有大于x的节点的时候。

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

typedef struct node

{

    int data;

    struct node *next;

}link;

link *newlink()

{

    link *t;

    t = (link*)malloc(sizeof(link));

    t->next = NULL;

    return t;

}

link *insert(link *head,int x)

{

    link *p,*q,*r;

    r = newlink();

    r->data = x;

    p = head;

    while(p->next)

    {

        q = p->next;

        if(q->data>=x)

        {

            r->next = p->next;

            p->next = r;

            return head;

        }

        p = p->next;

    }

    r->next = p->next;

    p->next = r;

    return head;

}

void show(link *head)

{

    link *p;

    p = head->next;

    while(p)

    {

        if(p->next==NULL)

            printf("%d\n",p->data);

        else

            printf("%d ",p->data);

        p = p->next;

    }

}

int main()

{

    link *head;

    int n,i,x;

    scanf("%d",&n);

    head = newlink();

    for(i=0;i<n;i++)

    {

        scanf("%d",&x);

        head = insert(head,x);

    }

    show(head);

    return 0;

}

巴特西