建立按元素值递增的有序单链表

Question

设计一个算法，建立按元素值（设线性表元素为非负整数）递增的有序单链表。（数据输入次序任意）

Answer 1

有两种方式，一是输入数据后先建立链表，然后排序；二是在插入的时候直接排序。
方法一（建立链表后再排序）：

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct link_node 
{
    int data;
    struct link_node* next;
}node,*linklist;

linklist createList()
{
    linklist L;
    linklist n,p;
    char ch;
    L = (linklist)malloc(sizeof(node));
    if (L == NULL)
    {
        printf("error");
        return 0;
    }

    
    p = L;
    printf("请输入数字，并以回车结束：\n"); 

    while(1)
    {
        n = (linklist)malloc(sizeof(node));
        scanf("%d",&n->data);
        n->next = NULL;
        p->next = n;
        p = n;
        if( (ch=getchar()) == '\n') break;
    }
    return L;
}

void print(linklist head)
{
    linklist p;
    p = head->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

//排序
void BubbleSort(linklist List)
{
    node * p, * q, * tail;

    tail = NULL;

    while((List->next->next) != tail)
    {
        p = List;
        q = List->next;
        while(q->next != tail)
        {
            if( q->data > q->next->data )
            {
                p->next = q->next;
                q->next = q->next->next;
                p->next->next = q;
                q = p->next;
            }
            q = q->next;
            p = p->next;
        }
        tail = q;
    }
}


//释放内存
void release(linklist head)
{
    linklist p;
    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
}


int main()
{
    linklist head = createList();
    printf("链表信息：");
    print(head);

    BubbleSort(head);
    printf("排序后：");
    print(head);
    release(head);
    return 0;
}

方法二（输入时直接排序）：

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct link_node 
{
    int data;
    struct link_node* next;
}node,*linklist;

linklist createList()
{
    linklist L;
    linklist n,p,front;
    char ch;
    L = (linklist)malloc(sizeof(node));
    L->next = NULL;
    if (L == NULL)
    {
        printf("error");
        return 0;
    }
    
    printf("请输入数字，并以回车结束：\n"); 

    while(1)
    {
        n = (linklist)malloc(sizeof(node));
        scanf("%d",&n->data);
        n->next = NULL;

        front = L;
        p = front->next;
        while(p)
        {
            if(p->data > n->data)
            {
                front->next = n;
                n->next = p;
                break;
            }else
            {
                front = p;
                p = p->next;
            }
        }
        if(p==NULL)
        {
            front->next = n;
        }
        if( (ch=getchar()) == '\n') break;
    }
    return L;
}

void print(linklist head)
{
    linklist p;
    p = head->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}


//释放内存
void release(linklist head)
{
    linklist p;
    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
}


int main()
{
    linklist head = createList();
    printf("链表信息：");
    print(head);
    release(head);
    return 0;
}