单链表的应用3（链表排序输出）

柔光的暖阳◎ 2022-07-26 00:13 160阅读 0赞

设head是带头结点的单链表的头指针，试写算法，按递增次序输出单链表中各结点的数据元素，并释放结点所占用的存储空间。要求不允许用数组作为辅助空间。

采用直接排序的方法，只借助于一个链表节点的空间，把链表按表内元素从小到大的顺序排好之后，按顺序输出即可。

代码实现：

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    
    using namespace std;
    typedef struct node
    {
        int data;
        struct node*next;
    } Linklist;
    
    Linklist* Create()
    {
        Linklist *head;
        head=(Linklist*)malloc(sizeof(Linklist));
        if(head!=NULL)
        {
            head->next=NULL;
            return head;
        }
        else
            return NULL;
    }
    
    int InSert(Linklist *head,int e)
    {
        Linklist *p;
        Linklist *q=head;
        p=(Linklist*)malloc(sizeof(Linklist));
        if(p!=NULL)
        {
            p->data=e;
            p->next=NULL;
            while(q->next!=NULL)
            {
                q=q->next;
            }
            q->next=p;
            return 1;
        }
        return 0;
    }
    
    void SortLink(Linklist *head)
    {
        Linklist temp;
        Linklist * p,*q,*min;
        for(p=head->next; p->next!=NULL; p=p->next)
        {
            min=p;
            for(q=p->next; q!=NULL; q=q->next)
                if(q->data < min->data)
                    min=q;
            if(min!=p)      //交换结点的数据域内容，指针内容没变。
            {
                temp.data=p->data;
    
                p->data=min->data;
    
                min->data=temp.data;
            }
        }
    }
    
    void Output(Linklist *head)
    {
        Linklist *p;
        p=head->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    
    void FreeLink(Linklist *head)
    {
        Linklist *p,*q;
        p=head;
        q=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            free(q);
        }
    }
    
    int main()
    {
        struct node *head;
        int n;
        int e,flag=0;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==-1)
                break;
            else
            {
                head=Create();
                if(head!=NULL)
                {
                    for(int i=0; i<n; i++)
                    {
                        scanf("%d",&e);
                        flag=InSert(head,e);
                        if(flag==0)
                        {
                            cout<<" Insert Fail "<<endl;
                            break;
                        }
                    }
                    if(flag==1)
                    {
                        SortLink(head);
                        Output(head);
                    }
                    if(flag==0)
                    {
                        cout<<" Insert Fail "<<endl;
                        break;
                    }
                    FreeLink(head);
                }
                else
                {
                    cout<<" Memory Full"<<endl;
                }
            }
        }
        return 0;
    }