链表的mergesort
本帖最后由 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);
intsize () { 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);
intsize () { 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 (); }
iteratoroperator + (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;
};
#endifList.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 ;
// 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 = x;
++_putIdx;
}
bool empty() { return _putIdx == _getIdx; }
private:
T _arr ;
int _putIdx;
int _getIdx;
};
template<typename T>
Queue<T>::Queue()
: _putIdx(0),
_getIdx(0)
{}
#endifmain.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相关问题请回复。
页:
[1]