链表的mergesort

andalousie · 发表于 2014-3-1 09:35:42

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 andalousie 于 2014-3-1 09:49 编辑

不久前，我曾经发布了一篇文章，《来，大家看一个单链表~ 推荐，因为内存分配方式很独特哦~ 》亲，你看了吗？如果看了，那么我基于那篇文章中的链表来添加mergesort需要的方法。
由于一些考虑，我不再使用g++编译器，转而使用Visual C++ 6.0，所以增加了与vc兼容的代码。
(1)由于vc没有定义size_t类型在标准命名空间里面，于是就在List.h里面增加了

/*** Add this on VC6.0 */
namespace std
{
        using ::size_t;
}

(2)在List类的方法里面增加了merge和swap还有del_front三个。

class List
{
public:
        List ();
        ~List ();
        void insert (int value);
        List* del_front ();
        void merge (List& x);
        void swap (List& x);
        int  size () { return _size; }
        bool isEmpty() const { return !_pHead; } // conversion to bool
        . . .
};

(3)将List.cc的文件名改成了List.cpp，增加了上述三个方法的实现

List* List::del_front ()
{
        List * tmp = new List;
        tmp->_pHead = _pHead;
        _pHead = _pHead->Next ();
        // don't delete recursively!
        tmp->_pHead->SetNext(0);
        tmp->_size = 1;
        return tmp;
}

void List::swap (List& x)
{
        List::Link * tmp = _pHead;
        _pHead = x._pHead;
        x._pHead = tmp;
        
        int tmpsize = _size;
        _size = x._size;
        x._size = tmpsize;
}

void List::merge (List& x)
{
        iterator f1 = begin(); iterator l1 = end();
        iterator f2 = x.begin(); iterator l2 = x.end();
        
        iterator prev;
        while(f1 != l1 && f2 != l2)
        {
                if(*f2 <= *f1)
                {
                        iterator next = f2;
                        ++next;
                        if(!prev._pLink)
                        {
                                _pHead = f2._pLink;
                                f2._pLink->SetNext (f1._pLink);
                        }
                        else
                        {
                                prev._pLink->SetNext (f2._pLink);
                                f2._pLink->SetNext (f1._pLink);
                        }
                        prev = f2;
                        f2 = next;
                }
                else
                {
                        prev = f1;
                        ++f1;
                }
        }
        if(f2 != l2)
                prev._pLink->SetNext (f2._pLink);
        
        _size += x._size; x._size = 0;
}

下面，我把更改后的全部文件都列出来，以便大家复制学习。
List.h

#if !defined (LIST_H)
#define LIST_H
#include <new>

/*** Add this on VC6.0
namespace std
{
        using ::size_t;
} */

class LinkAllocator;

class List
{
public:
        List ();
        ~List ();
        void insert (int value);
        List* del_front ();
        void merge (List& x);
        void swap (List& x);
        int  size () { return _size; }
        bool isEmpty() const { return !_pHead; } // conversion to bool
public:
        class Link
        {
        public:
                Link (Link* pNext, int value = -1) 
                        : _pNext (pNext), _value (value) {}
                Link *  Next () const { return _pNext; }
                void        SetNext (Link * next) { _pNext = next; }
                int     GetValue () const { return _value; }
                // allocator
                void * operator new (std::size_t size);
                void   operator delete (void * mem);
                static void Purge ();
        private:
                static LinkAllocator _linkAlloc;
                
                Link *  _pNext;
                int                _value;
        };
public:
        class iterator
        {
                friend class List;
        public:
                void      operator =  (const iterator& it) { _pLink = it._pLink; }
                bool      operator == (const iterator& it) { return _pLink == it._pLink; }
                bool      operator != (const iterator& it) { return _pLink != it._pLink; }
                iterator& operator ++ () { _pLink = _pLink->Next (); return *this; }
                int       operator *  () const { return _pLink->GetValue (); }
                
                iterator  operator + (std::size_t n)
                {
                        iterator tmp = *this;
                        while(n--) ++tmp;
                        return tmp;
                }

                iterator (Link * p = 0)
                        : _pLink (p) {}
                iterator (const iterator& it)
                        : _pLink (it._pLink) {}
        protected:
                Link * _pLink; // current link
        };

        friend class iterator;
        iterator begin () { return iterator (_pHead); }
        iterator end   () { return iterator (0); }
private:
        List::Link const * GetHead () const { return _pHead; }
        
        List::Link * _pHead;
        int    _size;
};

class LinkAllocator
{
        enum { BlockLinks = 4 }; // small value for testing
        class Block
        {
        public:
                Block (Block * next): _next (next) {}
                Block * Next () { return _next; }
        private:
                Block * _next;
        };
public:
        LinkAllocator () : _p (0), _blocks (0) {}
        ~LinkAllocator () { Purge (); }
        void Purge ();
        void * NewLink ();
        void Recycle (void * link);
private:
        List::Link  * _p;
        Block * _blocks;
};

#endif

List.cpp

#include "List.h"
#include <cassert>

LinkAllocator List::Link::_linkAlloc;

void * List::Link::operator new (std::size_t size)
{
        assert (size == sizeof (Link));
        return _linkAlloc.NewLink ();
}

void List::Link::operator delete (void * mem)
{
        if (mem)
                _linkAlloc.Recycle (mem);
}

void List::Link::Purge () { _linkAlloc.Purge (); }

// List

List::List ()
        : _pHead (0), _size(0)
{}

List::~List ()
{
        while ( _pHead != 0 )
        {
                Link * pLink = _pHead;
                _pHead = _pHead->Next (); // unlink pLink
                delete pLink;
        }
}

void List::insert (int value)
{
        Link * pLink = new Link (_pHead, value);
        _pHead = pLink;
        _size++;
}

List* List::del_front ()
{
        List * tmp = new List;
        tmp->_pHead = _pHead;
        _pHead = _pHead->Next ();
        // don't delete recursively!
        tmp->_pHead->SetNext(0);
        tmp->_size = 1;
        return tmp;
}

void List::swap (List& x)
{
        List::Link * tmp = _pHead;
        _pHead = x._pHead;
        x._pHead = tmp;
        
        int tmpsize = _size;
        _size = x._size;
        x._size = tmpsize;
}

void List::merge (List& x)
{
        iterator f1 = begin(); iterator l1 = end();
        iterator f2 = x.begin(); iterator l2 = x.end();
        
        iterator prev;
        while(f1 != l1 && f2 != l2)
        {
                if(*f2 <= *f1)
                {
                        iterator next = f2;
                        ++next;
                        if(!prev._pLink)
                        {
                                _pHead = f2._pLink;
                                f2._pLink->SetNext (f1._pLink);
                        }
                        else
                        {
                                prev._pLink->SetNext (f2._pLink);
                                f2._pLink->SetNext (f1._pLink);
                        }
                        prev = f2;
                        f2 = next;
                }
                else
                {
                        prev = f1;
                        ++f1;
                }
        }
        if(f2 != l2)
                prev._pLink->SetNext (f2._pLink);
        
        _size += x._size; x._size = 0;
}

// LinkAllocator

void * LinkAllocator::NewLink ()
{
        if (_p == 0)
        {
                // use global operator new to allocate a block of links
                char * p = ::new char [sizeof (Block) + BlockLinks * sizeof (List::Link)];
                // add it to the list of blocks
                Block * block = ::new (p) Block (_blocks);
                _blocks = block;
                // add it to the list of links
                p += sizeof (Block);
                for (int i = 0; i < BlockLinks; ++i)
                {
                        List::Link * link = ::new (p) List::Link (_p);
                        _p = link;
                        p += sizeof (List::Link);
                }
        }
        void * mem = _p;
        _p = _p->Next ();
        return mem;
}

void LinkAllocator::Recycle (void * mem)
{
        List::Link * link = static_cast<List::Link *> (mem);
        link->SetNext (_p);
        _p = link;
}

void LinkAllocator::Purge ()
{
        while (_blocks != 0)
        {
                // it was allocated as an array of char
                char * mem = reinterpret_cast<char *> (_blocks);
                _blocks = _blocks->Next();
                ::delete [] mem;
        }
}

queue.h

#if !defined (QUEUE_H)
#define QUEUE_H
#include <cassert>

const int maxPuts=16;

template<typename T>
class Queue
{
public:
        Queue();
        
        T    pop()
        {
                assert (_getIdx<_putIdx);
                ++_getIdx;
                return _arr [(_getIdx-1) % maxPuts];
        }
        
        void push(T x)
        {
                assert (_putIdx < maxPuts + _getIdx);
                _arr [_putIdx % maxPuts] = x;
                ++_putIdx;
        }
        
        bool empty() { return _putIdx == _getIdx; }
private:
        T   _arr [maxPuts];
        int _putIdx;
        int _getIdx;
};

template<typename T>
Queue<T>::Queue()
: _putIdx(0),
  _getIdx(0)
{}

#endif

main.cpp

#include <iostream>
#include "List.h"
#include "queue.h"

void mergesort(List& t)
{
        Queue<List *> Q;
        if(t.size() < 2) return;
        while(!t.isEmpty())
        {
                List * tmp = t.del_front();
                Q.push(tmp);
        }
        
        List *r, *s = Q.pop();
        while(!Q.empty())
        {
                Q.push(s);
                s = Q.pop();
                r = Q.pop();
                s->merge(*r);
        }
        t.swap(*s);
}

int main()
{
        List list;
        list.insert (4);
        list.insert (3);
        list.insert (9);
        list.insert (2);
        list.insert (6);
        list.insert (1);
        list.insert (5);
        mergesort(list);

        std::cout << "List contents:\n";
        for (List::iterator it = list.begin();
             it != list.end();
             ++it)
        {
                std::cout << *it << " ";
        }
        std::cout << std::endl;
        std::cout << list.size();
        return 0;
}

输出结果

1 2 3 4 5 6 9
7

账号		自动登录	找回密码
密码			立即注册

[技术交流] 链表的mergesort

马上注册，结交更多好友，享用更多功能^_^