数据结构—单链表—直接插入排序

骑猪看日落 2022-08-21 13:44 203阅读 0赞

有一个带头节点的单链表L（至少有一个数据节点），设计一个程序使其元素呈递增有序排列 。

思路：

先构造一个只含有一个数据节点的有序表。然后扫描单链表L余下的节点\*p（直到p为NULL为止），在有序表中通过比较找插入\*p节点的前驱节点\*pre，然后在\*pre节点之后插入\*p节点。

#include <iostream>
    using namespace std;
    #include <malloc.h>
    typedef int ElemType;
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    } LinkList;
    void sort(LinkList *&L)
    {
        LinkList *p,*pre,*q;
        p=L->next->next;          //p指向L的第2个数据节点
        L->next->next=NULL;       //构造只含有一个数据节点的有序表
        while(p!=NULL)
        {
            q=p->next;             //q保存*p节点后继节点的指针
            pre=L;         //从有序表开头进行比较
            while(pre->next!=NULL&&pre->next->data<p->data)   //在有序表中查找*p插入的前驱节点*pre
                pre=pre->next;
            p->next=pre->next;      //将*p插入*pre之后
            pre->next=p;
            p=q;     //扫描原链表余下的节点
        }
    }
    int main()
    {
        LinkList *L=(LinkList *)malloc(sizeof(LinkList)),*p,*r;
        L->next=NULL;
        r=L;
        ElemType a[10]={3,8,2,7,1,5,3,4,6,0};
        for(int i=0;i<10;i++)
        {
            p=(LinkList *)malloc(sizeof(LinkList));
            p->data=a[i];
            r->next=p;
            r=p;
        }
        r->next=NULL;
        cout<<"排序后为："<<endl;
        sort(L);
        p=L->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/33253fa7e7f447879e0db54b261966fd.png