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

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

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define LISTSIZE 1000
#define LISTMAX 100
typedef int Elemtype;
typedef struct LNode //定义单链表结点类型
{
Elemtype data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
LinkList CreatList1(LinkList &L)
{//从表头到表尾逆向建链表,每次均在头结点之后插入元素
int x,t; //设元素类型为整形
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
L->next = NULL;//初始化空链表
LNode *s,*r=L; //r未表尾指针
scanf("%d",&t); //输入结点值
while(t--) //输入9999表示循环结束
{
scanf("%d",&x);
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next=L->next;
L->next = s;//将新结点插入表中，L为头指针

}//while循环结束
return L;
}
LinkList sorting(LinkList &head)
{
LNode *p,*q;
int t;

for( p = head->next;p!=NULL;p=p->next)
{
for(q=p->next;q!=NULL;q=q->next)
{
if(p->data>q->data)
{
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
return head;
}
void display(struct LNode *head)
{
LNode *p;
p = head->next;
while(p!=NULL)
{
if(p->next==NULL)
{
printf("%d\n",p->data);
}
else
{
printf("%d ",p->data);
}
p=p->next;
}
}

int main()
{
LNode *L;
L = CreatList1(L);
sorting(L);
display(L);
return 0;
}

解法二

#include <stdio.h>
#include <malloc.h>
int main()
{
    int n,i;
    scanf("%d",&n);
    struct node
    {
        int data;
        struct node *next;
    };
    struct node * head,* tail,* p;
    head=(struct node *)malloc(sizeof(struct node));
    head->next=NULL;
    for (i=0; i<n; i++)
    {
        p=(struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->data);
        tail=head;
        while(tail->next!=NULL)
        {
            if (tail->next->data>p->data)
                break;
            tail=tail->next;
        }
        p->next=tail->next;
        tail->next=p;
    }
    p=head->next;
    while(p!=NULL)
    {
        if(p->next==NULL)
            printf("%d\n",p->data);
        else
            printf("%d ",p->data);
        p=p->next;
    }
    return 0;
}