// 此代码仅供个人学习之用
SingleLinkedList
// SingleLinkedList.h
#ifndef SINGLELINKEDLIST_H_H
#define SINGLELINKEDLIST_H_H
template<class T> class ListNode;
template<class T> class List
{
public:
List() : _first(0),_back(0)
{}
~List();
bool insert(T,int); // 安值和位置插入
bool push_back(T); // 接在链表队尾之后
bool push_front(T);// 插在链表头之前
bool remove(int index); // 按索引删除值
void remove_front(); // 从头部移出
void print_list(); // 输出链表
bool is_empty()
{ return _first==0; }
void reverse(); // 反转链表
int get_length();
List& operator + (List& );
private:
ListNode<T> * _first,* _back;
bool is_index(int index); // 索引是否合法
};
template<class T> class ListNode
{
friend class List<T>;
public:
ListNode( T t) : data(t), next(0)
{}
private:
T data;
ListNode * next; // 下一结点的指针
};
#endif
// SingleLinkedList.cpp
#ifndef SINGLELINKLIST_CPP
#define SINGLELINKLIST_CPP
#include "SingleLinkedList.h"
#include <iostream>
using std::cout;
using std::endl;
template<class T> bool List<T>::push_back(T t)
{
ListNode<T> * temp = new ListNode<T>( t );
if( !temp )
return false;
if( is_empty() )
{
_first = _back = temp;
return true;
}
_back->next = temp;
_back = temp;
return true;
}
template<class T> bool List<T>::push_front(T t)
{
ListNode<T> * temp = new ListNode<T>( t );
if( !temp )
return false;
if( is_empty() )
{
_first = _back = temp;
return true;
}
temp->next = _first;
_first = temp;
return true;
}
template<class T> bool List<T>::insert(T t,int index)
{
if( is_empty() && index==0 )
{
push_back(t);
return true;
}
int i = get_length();
if(index<0 || index>= i )
{
cout << "下标越界" << endl;
return false;
}
if( index == 0 || index == (i-1) )
{
push_front(t);
return true;
}
ListNode<T> * new_node,*temp ;
new_node= new ListNode<T>( t );
if( !new_node )
return false;
// 插入在temp的后面
temp = _first;
while (index--)
temp = temp->next;
new_node->next = temp->next;
temp->next = new_node;
return true;
}
template<class T> int List<T>::get_length()
{
int len = 0;
ListNode<T> * temp = _first;
while( temp != 0 )
{
++len;
temp = temp->next;
}
return len;
}
template<class T> void List<T>::reverse()
{
//if( is_empty() )
// return;
ListNode<T> * temp = _first;
_first = _back;
_back = temp;
ListNode<T> * ft, * bc;
ft = 0; // 前结点
bc = temp ; // 后结点
while( temp != 0 )
{
temp = bc->next;
bc->next = ft;
ft = bc;
bc = temp;
}
}
template<class T> void List<T>::remove_front()
{
if( is_empty() )
return;
ListNode<T> * temp = _first->next;
delete _first;
_first = temp;
}
template<class T> bool List<T>::remove(int index)
{
if( is_index( index ) == false)
return false;
if ( 0 == index )
{
remove_front();
return true;
}
ListNode<T> * temp = _first;
ListNode<T> * ft;
do
{
ft = temp;
temp = temp->next;
}while( --index);
// 删除最后一个结点
if ( index == (get_length() -1) )
{
delete _back;
_back = ft;
_back->next = 0;
return true;
}
// 删除普通结点
ft->next = temp->next;
delete temp;
return true;
}
template<class T> List<T>::~List()
{
if( ! is_empty() )
{
while( _first != 0)
{
_back = _first->next;
delete _first;
_first = _back;
}
}
}
template<class T> void List<T>::print_list()
{
if( is_empty() )
{
cout << "list is empty" << endl;
return ;
}
ListNode<T> * temp = _first;
while( temp != 0 )
{
cout << temp->data <<" " ;
temp = temp->next;
}
cout << endl;
}
template<class T> bool List<T>::is_index(int index)
{
if( is_empty() )
return false;
if( index<0 || (index >=get_length()) )
return false;
return true;
}
#endif
模板循环链表解决josephus问题
// CircleList.h
#ifndef CIRCLELIST_H_H
#define CIRCLELIST_H_H
template<class T> class CircleList;
template<class T> class CirListNode
{
friend class CircleList<T>;
public:
CirListNode(T d = 0) : data(d), next(0)
{}
private:
T data;
CirListNode * next;
};
template<class T> class CircleList
{
public:
CircleList()
: first(0),last(0),current(0),front(0)
{}
bool is_empty()
{ return first ==0;}
void insert(T d);
void remove(); // 移出当前结点
void next() // 移动到下一结点
{ front =current;current = current->next;}
T getData()
{ return current->data; }
private:
CirListNode<T> * first, * current, * last,* front;
};
#endif
// CircleList.cpp
#include "CircleList.h"
template<class T> void CircleList<T>::insert(T d)
{
if( is_empty() )
{
first = last = current = new CirListNode<T>( d );
current->next = first;
return;
}
CirListNode<T> * temp = new CirListNode<T>( d );
temp->next = current->next;
current->next = temp;
current = temp;
}
template<class T> void CircleList<T>::remove()
{
if ( front == 0 )
return;
front->next = current->next;
delete current;
current = front->next;
}
//main.cpp
#include <iostream>
#include "CircleList.h"
#include "CircleList.cpp"
using namespace std;
template<class T> void Josephus ( int n, int m ,CircleList<T> & clist ) ;
void main ( )
{
CircleList<int> clist;
int n, m;
cout << "Enter the Number of Contestants?";
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i);
//形成约瑟夫环
//clist.Josephus (n, m);
Josephus( n, m, clist);//解决约瑟夫问题
}
// n 小孩数量,m 步长
template<class T> void Josephus ( int n, int m ,CircleList<T> & clist )
{
for ( int i=0; i<n-i; i++ )
{//执行n-1次
for ( int j=0; j<m-1; j++ )
clist.next();
cout << "Delete person "
<< clist.getData()<< endl; //数m-1个人
clist.remove();//删去
}
cout << "No."<< clist.getData() << " boy win/n";
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////