鱼C论坛

 找回密码
 立即注册
查看: 2767|回复: 0

[技术交流] 链表的mergesort

[复制链接]
发表于 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里面增加了
  1. /*** Add this on VC6.0 */
  2. namespace std
  3. {
  4.         using ::size_t;
  5. }
复制代码
(2)在List类的方法里面增加了merge和swap还有del_front三个。
  1. class List
  2. {
  3. public:
  4.         List ();
  5.         ~List ();
  6.         void insert (int value);
  7.         List* del_front ();
  8.         void merge (List& x);
  9.         void swap (List& x);
  10.         int  size () { return _size; }
  11.         bool isEmpty() const { return !_pHead; } // conversion to bool
  12.         . . .
  13. };
复制代码
(3)将List.cc的文件名改成了List.cpp,增加了上述三个方法的实现
  1. List* List::del_front ()
  2. {
  3.         List * tmp = new List;
  4.         tmp->_pHead = _pHead;
  5.         _pHead = _pHead->Next ();
  6.         // don't delete recursively!
  7.         tmp->_pHead->SetNext(0);
  8.         tmp->_size = 1;
  9.         return tmp;
  10. }

  11. void List::swap (List& x)
  12. {
  13.         List::Link * tmp = _pHead;
  14.         _pHead = x._pHead;
  15.         x._pHead = tmp;
  16.         
  17.         int tmpsize = _size;
  18.         _size = x._size;
  19.         x._size = tmpsize;
  20. }

  21. void List::merge (List& x)
  22. {
  23.         iterator f1 = begin(); iterator l1 = end();
  24.         iterator f2 = x.begin(); iterator l2 = x.end();
  25.         
  26.         iterator prev;
  27.         while(f1 != l1 && f2 != l2)
  28.         {
  29.                 if(*f2 <= *f1)
  30.                 {
  31.                         iterator next = f2;
  32.                         ++next;
  33.                         if(!prev._pLink)
  34.                         {
  35.                                 _pHead = f2._pLink;
  36.                                 f2._pLink->SetNext (f1._pLink);
  37.                         }
  38.                         else
  39.                         {
  40.                                 prev._pLink->SetNext (f2._pLink);
  41.                                 f2._pLink->SetNext (f1._pLink);
  42.                         }
  43.                         prev = f2;
  44.                         f2 = next;
  45.                 }
  46.                 else
  47.                 {
  48.                         prev = f1;
  49.                         ++f1;
  50.                 }
  51.         }
  52.         if(f2 != l2)
  53.                 prev._pLink->SetNext (f2._pLink);
  54.         
  55.         _size += x._size; x._size = 0;
  56. }
复制代码
下面,我把更改后的全部文件都列出来,以便大家复制学习。
List.h
  1. #if !defined (LIST_H)
  2. #define LIST_H
  3. #include <new>

  4. /*** Add this on VC6.0
  5. namespace std
  6. {
  7.         using ::size_t;
  8. } */

  9. class LinkAllocator;

  10. class List
  11. {
  12. public:
  13.         List ();
  14.         ~List ();
  15.         void insert (int value);
  16.         List* del_front ();
  17.         void merge (List& x);
  18.         void swap (List& x);
  19.         int  size () { return _size; }
  20.         bool isEmpty() const { return !_pHead; } // conversion to bool
  21. public:
  22.         class Link
  23.         {
  24.         public:
  25.                 Link (Link* pNext, int value = -1)
  26.                         : _pNext (pNext), _value (value) {}
  27.                 Link *  Next () const { return _pNext; }
  28.                 void        SetNext (Link * next) { _pNext = next; }
  29.                 int     GetValue () const { return _value; }
  30.                 // allocator
  31.                 void * operator new (std::size_t size);
  32.                 void   operator delete (void * mem);
  33.                 static void Purge ();
  34.         private:
  35.                 static LinkAllocator _linkAlloc;
  36.                
  37.                 Link *  _pNext;
  38.                 int                _value;
  39.         };
  40. public:
  41.         class iterator
  42.         {
  43.                 friend class List;
  44.         public:
  45.                 void      operator =  (const iterator& it) { _pLink = it._pLink; }
  46.                 bool      operator == (const iterator& it) { return _pLink == it._pLink; }
  47.                 bool      operator != (const iterator& it) { return _pLink != it._pLink; }
  48.                 iterator& operator ++ () { _pLink = _pLink->Next (); return *this; }
  49.                 int       operator *  () const { return _pLink->GetValue (); }
  50.                
  51.                 iterator  operator + (std::size_t n)
  52.                 {
  53.                         iterator tmp = *this;
  54.                         while(n--) ++tmp;
  55.                         return tmp;
  56.                 }

  57.                 iterator (Link * p = 0)
  58.                         : _pLink (p) {}
  59.                 iterator (const iterator& it)
  60.                         : _pLink (it._pLink) {}
  61.         protected:
  62.                 Link * _pLink; // current link
  63.         };

  64.         friend class iterator;
  65.         iterator begin () { return iterator (_pHead); }
  66.         iterator end   () { return iterator (0); }
  67. private:
  68.         List::Link const * GetHead () const { return _pHead; }
  69.         
  70.         List::Link * _pHead;
  71.         int    _size;
  72. };

  73. class LinkAllocator
  74. {
  75.         enum { BlockLinks = 4 }; // small value for testing
  76.         class Block
  77.         {
  78.         public:
  79.                 Block (Block * next): _next (next) {}
  80.                 Block * Next () { return _next; }
  81.         private:
  82.                 Block * _next;
  83.         };
  84. public:
  85.         LinkAllocator () : _p (0), _blocks (0) {}
  86.         ~LinkAllocator () { Purge (); }
  87.         void Purge ();
  88.         void * NewLink ();
  89.         void Recycle (void * link);
  90. private:
  91.         List::Link  * _p;
  92.         Block * _blocks;
  93. };

  94. #endif
复制代码
List.cpp
  1. #include "List.h"
  2. #include <cassert>

  3. LinkAllocator List::Link::_linkAlloc;

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

  9. void List::Link::operator delete (void * mem)
  10. {
  11.         if (mem)
  12.                 _linkAlloc.Recycle (mem);
  13. }

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

  15. // List

  16. List::List ()
  17.         : _pHead (0), _size(0)
  18. {}

  19. List::~List ()
  20. {
  21.         while ( _pHead != 0 )
  22.         {
  23.                 Link * pLink = _pHead;
  24.                 _pHead = _pHead->Next (); // unlink pLink
  25.                 delete pLink;
  26.         }
  27. }

  28. void List::insert (int value)
  29. {
  30.         Link * pLink = new Link (_pHead, value);
  31.         _pHead = pLink;
  32.         _size++;
  33. }

  34. List* List::del_front ()
  35. {
  36.         List * tmp = new List;
  37.         tmp->_pHead = _pHead;
  38.         _pHead = _pHead->Next ();
  39.         // don't delete recursively!
  40.         tmp->_pHead->SetNext(0);
  41.         tmp->_size = 1;
  42.         return tmp;
  43. }

  44. void List::swap (List& x)
  45. {
  46.         List::Link * tmp = _pHead;
  47.         _pHead = x._pHead;
  48.         x._pHead = tmp;
  49.         
  50.         int tmpsize = _size;
  51.         _size = x._size;
  52.         x._size = tmpsize;
  53. }

  54. void List::merge (List& x)
  55. {
  56.         iterator f1 = begin(); iterator l1 = end();
  57.         iterator f2 = x.begin(); iterator l2 = x.end();
  58.         
  59.         iterator prev;
  60.         while(f1 != l1 && f2 != l2)
  61.         {
  62.                 if(*f2 <= *f1)
  63.                 {
  64.                         iterator next = f2;
  65.                         ++next;
  66.                         if(!prev._pLink)
  67.                         {
  68.                                 _pHead = f2._pLink;
  69.                                 f2._pLink->SetNext (f1._pLink);
  70.                         }
  71.                         else
  72.                         {
  73.                                 prev._pLink->SetNext (f2._pLink);
  74.                                 f2._pLink->SetNext (f1._pLink);
  75.                         }
  76.                         prev = f2;
  77.                         f2 = next;
  78.                 }
  79.                 else
  80.                 {
  81.                         prev = f1;
  82.                         ++f1;
  83.                 }
  84.         }
  85.         if(f2 != l2)
  86.                 prev._pLink->SetNext (f2._pLink);
  87.         
  88.         _size += x._size; x._size = 0;
  89. }

  90. // LinkAllocator

  91. void * LinkAllocator::NewLink ()
  92. {
  93.         if (_p == 0)
  94.         {
  95.                 // use global operator new to allocate a block of links
  96.                 char * p = ::new char [sizeof (Block) + BlockLinks * sizeof (List::Link)];
  97.                 // add it to the list of blocks
  98.                 Block * block = ::new (p) Block (_blocks);
  99.                 _blocks = block;
  100.                 // add it to the list of links
  101.                 p += sizeof (Block);
  102.                 for (int i = 0; i < BlockLinks; ++i)
  103.                 {
  104.                         List::Link * link = ::new (p) List::Link (_p);
  105.                         _p = link;
  106.                         p += sizeof (List::Link);
  107.                 }
  108.         }
  109.         void * mem = _p;
  110.         _p = _p->Next ();
  111.         return mem;
  112. }

  113. void LinkAllocator::Recycle (void * mem)
  114. {
  115.         List::Link * link = static_cast<List::Link *> (mem);
  116.         link->SetNext (_p);
  117.         _p = link;
  118. }

  119. void LinkAllocator::Purge ()
  120. {
  121.         while (_blocks != 0)
  122.         {
  123.                 // it was allocated as an array of char
  124.                 char * mem = reinterpret_cast<char *> (_blocks);
  125.                 _blocks = _blocks->Next();
  126.                 ::delete [] mem;
  127.         }
  128. }
复制代码
queue.h
  1. #if !defined (QUEUE_H)
  2. #define QUEUE_H
  3. #include <cassert>

  4. const int maxPuts=16;

  5. template<typename T>
  6. class Queue
  7. {
  8. public:
  9.         Queue();
  10.         
  11.         T    pop()
  12.         {
  13.                 assert (_getIdx<_putIdx);
  14.                 ++_getIdx;
  15.                 return _arr [(_getIdx-1) % maxPuts];
  16.         }
  17.         
  18.         void push(T x)
  19.         {
  20.                 assert (_putIdx < maxPuts + _getIdx);
  21.                 _arr [_putIdx % maxPuts] = x;
  22.                 ++_putIdx;
  23.         }
  24.         
  25.         bool empty() { return _putIdx == _getIdx; }
  26. private:
  27.         T   _arr [maxPuts];
  28.         int _putIdx;
  29.         int _getIdx;
  30. };

  31. template<typename T>
  32. Queue<T>::Queue()
  33. : _putIdx(0),
  34.   _getIdx(0)
  35. {}

  36. #endif
复制代码
main.cpp
  1. #include <iostream>
  2. #include "List.h"
  3. #include "queue.h"

  4. void mergesort(List& t)
  5. {
  6.         Queue<List *> Q;
  7.         if(t.size() < 2) return;
  8.         while(!t.isEmpty())
  9.         {
  10.                 List * tmp = t.del_front();
  11.                 Q.push(tmp);
  12.         }
  13.        
  14.         List *r, *s = Q.pop();
  15.         while(!Q.empty())
  16.         {
  17.                 Q.push(s);
  18.                 s = Q.pop();
  19.                 r = Q.pop();
  20.                 s->merge(*r);
  21.         }
  22.         t.swap(*s);
  23. }

  24. int main()
  25. {
  26.         List list;
  27.         list.insert (4);
  28.         list.insert (3);
  29.         list.insert (9);
  30.         list.insert (2);
  31.         list.insert (6);
  32.         list.insert (1);
  33.         list.insert (5);
  34.         mergesort(list);

  35.         std::cout << "List contents:\n";
  36.         for (List::iterator it = list.begin();
  37.              it != list.end();
  38.              ++it)
  39.         {
  40.                 std::cout << *it << " ";
  41.         }
  42.         std::cout << std::endl;
  43.         std::cout << list.size();
  44.         return 0;
  45. }
复制代码

输出结果
  1. 1 2 3 4 5 6 9
  2. 7
复制代码
相关问题请回复。


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表