链式直接插入排序

拼搏现实的明天。 2022-07-16 13:40 129阅读 0赞

2016年7月27日18:13:11
        假设用户数据为:[22,6,17,8]
        数据的存贮:pHead->[22]->[6]->[17]->[8]
    
        链式存贮结构来保存待排序的数据,首先创建一个链表,将待排序的所有元素存贮到链表中去,将待排序的链表分为两部分
        :有序子集和待排序子集,初始时有序子集中没有元素,令pSort->pNext = NULL,指针pCur指向待排序的链表节点,遍历待排序的子集
    
        如果有序子集为空,那么将pTemp = pCur;pCur = pCur->pNext;然后将pTemp所指向的结点插入到有序子集中pSort->pNext = pTemp;
        pTemp->pNext = NULL;
        如果有序子集不为空,那么设置一个qCur指针来遍历有序子集,从前往后遍历,初始时pCur = pSort->pNext,将pTemp所指向的结点中数据
        与pCur所指向的结点进行比较,
            1>如果比第一个小,就说明它比后面的一定小,它就是最小的,直接插入到第一个的前面,那么要插入到qCur所指向结点的前面,那么
            就应该在设置一个指针让其指向qCur前面的那个结点,这样才能确保将元素进行插入.
            2>如果比qCur所指向的元素大,就说明该元素应该放在qCur所指向元素的后面元素的某个位置,就pCur = pCur->pNext,如果发现小于
            pCur就直接执行1操作,
            __________________________________________________________________________________________________________________
            注意:如果pTemp所指向的元素比pCur指向的元素相等,为了保证排序的稳定性,那么它应该放在后面,即执行和大于相同的操作;
            __________________________________________________________________________________________________________________
            3>如果pTemp所指向的元素比有序表中的最后一个元素还要大,那么直接插入有序表的尾部,
            4>当待排序的元素遍历完毕的时候,该算法就执行完毕了;

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #define len 100
    #define random(x) (rand()%x)
    
    //链表节点的结构体类型
    typedef struct node
    {
        int data;
        struct node * pNext;
    }linkList;
    
    //函数前置声明
    void initLinkList(linkList ** pHead);//链表的初始化
    void traverseLinkList(linkList * pHead);//链表的遍历
    linkList * createLinkList(linkList * pHead);//链表的创建
    void insertSort(linkList * pHead);//单链表的直接插入排序
    
    //单链表的初始化
    void initLinkList(linkList ** pHead)
    {
        *pHead = (linkList * )malloc(sizeof(linkList));
        if(!(*pHead))
        {
            printf("动态内存分配失败!\n");
            exit(-1);
        }
        (*pHead)->pNext = NULL;
        return;
    }
    
    //单链表的遍历
    void traverseLinkList(linkList * pHead)
    {
        linkList * pCur;
        pCur = pHead->pNext;
        if(!pCur)
        {
            printf("链表为空!\n");
            return;
        }
        while(pCur)
        {
            printf("%-5d",pCur->data);
            pCur = pCur->pNext;
        }
        return;
    }
    
    //单链表的创建
    linkList * createLinkList(linkList * pHead)
    {
        int i;
        linkList * pNew;
        linkList * pTail;
        pTail = pHead;
        pHead->data = 0;
        for(i = 0;i<len;i++)
        {
            pNew = (linkList * )malloc(sizeof(linkList));
            if(!pNew)
            {
                printf("动态内存分配失败!\n");
                exit(-1);
            }
            pNew->data = random(1000);
            pNew->pNext = NULL;
            /*if(!pTail) { pTail->pNext = pNew; pTail = pNew; } else { pTail->pNext = pNew; pTail = pNew; }*/
            pTail->pNext = pNew;
            pTail = pNew;
            pHead->data ++;
        }
        return pHead;
    }
    
    
    //单链表的直接插入排序
    void insertSort(linkList * pHead)
    {
        //定义变量
        linkList * pCur ,* pPrev;
        linkList * qCur ,* qPrev;
        //处理前的初始状态
        pPrev = pHead;
        pCur = pHead->pNext;
        qCur = pCur->pNext;
        pCur->pNext = NULL;
        //遍历未排序子集
        while( qCur )
        {
            pPrev = pHead;
            pCur = pPrev->pNext;
            //确定合适的插入位置
            while( pCur )
            {
                if(qCur->data<pCur->data)
                {
    
                    /* qPrev->pNext = pCur; pPrev->pNext = qPrev; */
                    break;
                }
                else 
                {
                    pPrev = pCur;
                    pCur = pCur->pNext;
                }
            }
            //插入元素前的准备动作
            qPrev = qCur;
            qCur = qCur->pNext;
            /* if(NULL == pCur) { qPrev->pNext = NULL; pPrev->pNext = qPrev; } else { qPrev->pNext = pCur; pPrev->pNext = qPrev; } */
            //插入相应的到之前的查找的的位置
            qPrev->pNext = pCur;
            pPrev->pNext = qPrev;
        }
        return ;
    }
    
    //主函数
    int main(void)
    {
        linkList * pHead;
        initLinkList(&pHead);
        pHead = createLinkList(pHead);
        printf("随机产生的数据为:\n");
        traverseLinkList(pHead);
        printf("\n");
        insertSort(pHead);
        printf("排序后的数据为:\n");
        traverseLinkList(pHead);
        printf("\n");
        return 0;
    }