6.5 k个已排好序链表合并为一个排序链表

1 建立链表（带哨兵位的）
2 建立最小堆方法
3 合并已排好序的k个链表

typedef int DataType;
//建立链表
class Link
{
private:
    struct Node
    {
        DataType data;
        Node *next;
    };
    Node *head; //哨兵位
public:
    Link()
    {
        Init();
    }
    ~Link()
    {
        Delete();
    }
    void Init()
    {
        head = new Node;
        head->next = NULL;
    }
    void Delete()
    {
        for (Node *p = head; p != NULL;)
        {
            Node *pTemp = p->next;
            delete p;
            p = pTemp;
        }
        head = NULL;
    }
    bool Empty()
    {
        return head->next == NULL;
    }
    void Print()
    {
        for (Node *p = head->next; p != NULL; p = p->next)
        {
            cout << p->data << endl;
        }
    }
    //顺序插入 考虑两种情况 1.空表 2.当插入值是最大值的时候
    void SortInsert(DataType data)
    {
        Node *p = head;
        do 
        {
            if (p->next == NULL || p->next->data > data)
            {
                Node *pNew = new Node;
                pNew->data = data;
                pNew->next = p->next;
                p->next = pNew;

                return;
            }
            p = p->next;
        } while (true);
    }
    //使用数组初始化列表
    void ArrayInsert(DataType array[], int size)
    {
        for (int i=0; i<size; ++i)
        {
            SortInsert(array[i]);
        }
    }
    //尾插法直接插入
    void Insert(DataType data)
    {
        Node *p = head;
        while(p->next != NULL)
        {
            p = p->next;
        }

        Node *pNew = new Node;
        pNew->data = data;
        pNew->next = NULL;
        p->next = pNew;
    }
    //去掉首结点并返回首结点的值
    int ExtractDate()
    {
        if (! Empty())
        {
            DataType data = head->next->data;
            Node *p = head->next;
            Node *pFirst = p->next;

            delete p;
            p = NULL;

            head->next = pFirst; 
            return data;
        }
        return -1;
    }
    int GetData()
    {
        if (!Empty())
        {
            return head->next->data;
        }
    }
    bool Find(const DataType data)
    {
        for (Node *p = head->next; p != NULL; p = p->next)
        {
            if (p->data == data)
            {
                return true;
            }
        }
        return false;
    }
    void Swap(Link &p)   //交换两个链表主要是交换 head
    {
        if (head != p.head)
        {
            Node *tmp = head->next;
            head->next = p.head->next;
            p.head->next = tmp;
        }
    }
};
//保持最小堆性质 参数inode为内部结点 注意结点从1开始，数组从0开始
void MinHeapify(int array[], int size, int inode)
{
    int least= inode;                //父结点
    int left = inode*2;                //左子结点
    int right = inode*2+1;            //右子结点

    if (left <= size && array[left-1] < array[least-1])
    {
        least = left;
    }
    if (right <= size && array[right-1] < array[least-1])
    {
        least = right;
    }

    if (least != inode)                    //父结点小于 左子结点 或者 右子结点
    {
        int temp = array[inode-1];            //子结点值与父结点值交换
        array[inode-1] = array[least-1];
        array[least-1] = temp;

        MinHeapify(array, size, least);      //再次验证被交换的值的子结点是否满足 最小堆性质
    }
}
//建立最小堆 使每一个父结点小于子结点
void BuildMinHeap(int array[],int size)
{
    for(int i=size/2; i>0; --i)     //最多有 size/2 个内部结点
    {
        MinHeapify(array, size, i);
    }
}
//k个已排好序的链表合并为一个链表
//pLink 链表数组的地址, linkSize链表数组的大小, array 数组的地址, count数组的大小
void SortLink(Link *pLink, int linkSize, Link *link)
{
    int *pArray = new int[linkSize]; //动态分配k个大小的数组
    for (int i=0; i<linkSize; ++i)    //从k个链表中取首结点的值
    {
        pArray[i] = pLink[i].GetData();
    }

    int j=0;
    do 
    {
        BuildMinHeap(pArray,linkSize); //构造最小堆，即每个父结点小于或等于子结点，根结点为最小值
        for (j=0; j<linkSize; ++j)
        {
            if(pLink[j].Find(pArray[0]))   //寻找最小值来自于哪一个链表
            {
                link->Insert(pLink[j].ExtractDate());  //去掉并返回链表的的值（更新链表）
                break;
            }
        }
        if (!pLink[j].Empty())  //确保取出值的链表不为空
        {
            pArray[0] = pLink[j].GetData();   //更新数组
        }
        else 
        {
            pArray[0] = pArray[linkSize-1];  
            pLink[j].Swap(pLink[linkSize-1]);  //交换两个链表
            --linkSize;
        }
    } while (linkSize != 0);

    delete [] pArray;
}
void main()
{
    //检测是否有内存泄露 需要加头文件#include <crtdbg.h>
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

    Link k[5];

    int Array[5][5] = { {21, 12, 11, 10, 1}, 
                        {22, 17, 16, 7, 2},
                        {23, 18, 13, 8, 3},
                        {24, 19, 14, 9, 4},
                        {25, 20, 15, 6, 5}};

    for (int i=0; i<5; ++i)
    {
        k[i].ArrayInsert(Array[i],sizeof(Array[i])/sizeof(Array[i][0]));
    }
    //for (int i=0; i<5; ++i)
    //{
    //    k[i].Print();
    //}

    Link link;

    SortLink(k, sizeof(k)/sizeof(k[0]), &link);

    link.Print();

    system("pause");
}

 （转载请注明作者和出处^_*  Seven++ http://www.cnblogs.com/sevenPP/  ）