链表的有序集合

深藏阁楼爱情的钟 2022-08-10 06:12 169阅读 0赞

## 链表的有序集合 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

集合有一个重要的特性：互异性，即集合中任意两个元素都是不同的，互异性使得集合中的元素没有重复。给你 n 个包含重复数字的无序正整数序列，建立一个有序链表，链表中的结点按照数值非降序排列且不包含重复元素，输出该有序链表。

## 输入 ##

输入包含多组测试数据，对于每组测试数据：

输入的第一行为一个正整数 n(1 ≤ n ≤ 100)，

第二行为 n 个正整数 b1，b2，...，bn(0 ≤ bi ≤ 230)。

## 输出 ##

对于每组测试数据，按照非降序输出链表的节点值。

## 示例输入 ##

1
    2
    2
    1 1
    6
    6 3 5 2 2 3

## 示例输出 ##

2
    1
    2 3 5 6

## 提示 ##

## 来源 ##

qinchuan

## 示例程序 ##

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