模版快拍

╰半橙微兮° 2022-07-26 11:25 153阅读 0赞

template<typename T>  
    struct Node  
    {  
        T m_Data;  
        Node * m_pNext;  
    };  
    template<typename T>  
    void ListQuickSort(Node<T> * pHead, Node<T> * pEnd/*尾结点可以为空*/)  
    {  
        T Key;  
        T Tmp;  
        Node<T> * pLow = NULL;  
        Node<T> * pHigh = NULL;  
        if (!pHead)  
            return ;  
        if (pHead == pEnd)  
            return;  
        pLow = pHead;  
        pHigh = pHead->m_pNext;  
        Key = pHead->m_Data;  
        while (pHigh != pEnd)  
        {  
            if (pHigh->m_Data < Key)  
            {  
                pLow = pLow->m_pNext;  
                Tmp = pLow->m_Data;  
                pLow->m_Data = pHigh->m_Data;  
                pHigh->m_Data = Tmp;  
            }  
            pHigh = pHigh->m_pNext;  
        }  
        Tmp = pHead->m_Data;  
        pHead->m_Data = pLow->m_Data;  
        pLow->m_Data = Tmp;  
        ListQuickSort(pHead, pLow);  
        ListQuickSort(pLow->m_pNext, pEnd);  
    }

#include <time.h>  
    #include <iostream>  
    using namespace std;  
    void main()  
    {  
        int i = 0;  
        Node<int> * pInt = NULL;  
        Node<int> * pNewNode = NULL;  
        Node<int> * pCurNode = NULL;  
        srand(time(NULL));  
        for (i = 0; i < 10; i++)  
        {  
            pNewNode = new Node<int>;  
            if (pNewNode == NULL)  
            {  
                while (pInt)  
                {  
                    pCurNode = pInt;  
                    pInt = pInt->m_pNext;  
                    delete pCurNode;  
                }  
                pInt = NULL;  
                return;  
            }  
            pNewNode->m_Data = rand() % 100;  
            pNewNode->m_pNext = pInt;  
            pInt = pNewNode;  
        }  
        cout << "排序前:" << endl;  
        pCurNode = pInt;  
        while (pCurNode)  
        {  
            cout << pCurNode->m_Data << '\t';  
            pCurNode = pCurNode->m_pNext;  
        }  
        cout << endl;  
        ListQuickSort<int>(pInt, NULL);  
        cout << "排序后:" << endl;  
        pCurNode = pInt;  
        while (pCurNode)  
        {  
            cout << pCurNode->m_Data << '\t';  
            pCurNode = pCurNode->m_pNext;  
        }  
        cout << endl;  
        while (pInt)  
        {  
            pCurNode = pInt;  
            pInt = pInt->m_pNext;  
            delete pCurNode;  
        }  
        pInt = NULL;  
        _CrtDumpMemoryLeaks();  
        system("pause");  
        return;  
    }