posts - 30,  comments - 28,  trackbacks - 0

     很经典的"转圈数数踢人"问题,老早以前做的东西
     这里是我的解法,利用STL里的List构建Ring List
     头文件:
  //:This part is partly from Bruce Eckel's source code .
// thought he don't hear of me at all ^_^
// Making a "ring" data structure from the STL
#ifndef RING_H
#define RING_H

#include<iterator>
#include<list>
using namespace std;

template <class Type> class Ring{
 list<Type> lst;
public:


 class iterator;
 friend class iterator;
 class iterator :public std::iterator<std::bidirectional_iterator_tag,Type,ptrdiff_t>{
  typename list<Type>::iterator it;
  list<Type>* r;

 public:
  iterator(list<Type>&lst,const typename list<Type>::iterator& i):it(i),r(&lst){}

  bool operator==(const iterator& x)const{
   return it==x.it;
  }

  bool operator!=(const iterator& x)const{
   return!(*this==x);
  }

  typename list<Type>::reference operator*()const{
   return *it;
  }

  iterator& operator++(){
   ++it;
   if(it==r->end())
    it=r->begin();
   return *this;
  }

  iterator operator++(int){
   iterator tmp=*this;
   ++*this;
   return tmp;
  }

  iterator &operator--(){
   if(it==r->begin())
    it=r->end();
   --it;
   return *this;
  }
  iterator operator--(int){
   iterator tmp=*this;
   --*this;
   return tmp;
  }

  iterator insert(const Type& x){
   return iterator(*r,r->insert(it,x));
  }
  
  //I have to recognize that the iterator is not so smart as
  //we expected .If the element in the list is erased ,the
  //iterator will be lost and point to a null.The shortage of
  //the stupid iterator will been seen the the Josephus.cpp
  //we have to use a template variable to storage the next iterator
  //of the deleting iterator.If not ,the programe will be nightmare
  iterator erase(){
   return iterator(*r,r->erase(it));
  }

 };

 void push_back(const Type& x){lst.push_back(x);}

 iterator begin(){return iterator(lst,lst.begin());}

 int size(){return lst.size();}

};
#endif

实现文件:
//:Using circle list to solve Josephus problem
//:version 1.01
//:author Murainwood 12/3/2006
#include<iostream>
#include"Ring.h"

void  main(){

 //enter the number of people and the index

 int n,m;
 cout<<"Enter the Number of Contestants?";
 cin>>n>>m;
   
 
    Ring<int> ring;
 for(int i=1;i<=n;i++) ring.push_back(i);

 //determine the iterator
 //it is reasonable  to declare two iterator

    Ring<int>::iterator tmp=ring.begin();
 Ring<int>::iterator it=tmp;
 
 //without the iterator tmp ,if we erase the it
 //the it will lost ,so the loop can not  work

 for(int index=0;index<n-1;index++){
   it=tmp;
  for(int j=0;j<m-1;j++){it++;tmp++;}
   tmp++;
      cout<<"Delete person"<<*it<<endl;
   it.erase();
   
 }
 it=ring.begin();
 cout<<"The result is person"<<*it<<endl;
}

//:finished

     这个Ring List有很高的效率和安全性,并且通用性也比较好
     这里也发现个问题,就是STL里的Iterator 还不够"聪明",这也是为什么我会在程序里多加个迭代器:tmp,
因为如果我调用了it.erase();那么这个迭代器就丢失了,程序也就无非运行下去.
     这样我们很容易地想,如果调用了it.erase()后,指针不是丢失,而是指向下一个元素该多好啊!
     很遗憾,现阶段标准STL库里的List没有这个功能.猜想是因为List的物理存储结构的缘故,如果让他的迭代器变得如我们想像得那么"聪明",那么花费可能会有些大.
    还没有验证过boost库,不知道那里的迭代器是否会更人性化些
     有时间研究一下相关的STL源码,写一个"聪明些"的迭代器.

posted on 2006-04-18 00:10 murainwood 阅读(640) 评论(0)  编辑  收藏 所属分类: C++&C

只有注册用户登录后才能发表评论。


网站导航:
 
<2006年4月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

如果真的给你一片天,你敢不敢要?

常用链接

留言簿(3)

随笔分类

随笔档案

相册

搜索

  •  

最新评论

阅读排行榜

评论排行榜