今天看了看C++中模板的概念，按照教程写了一个简单的链表模板：
//*********************
//** listtmp.h **
//*********************
#ifndef LIST
#define LIST
#include
<iostream>
template
<class T> class List{
public:
List();
void Add(T&);
void Remove(T&);
T* Find(T&);
T* Current();
void Restart();
void Next();
void PrintList();
~List();
protected:
struct Node{
Node* pNext;
T* pT;
};
Node *pFirst; //链首结点指针
Node *pCurpos; //当前节点
};
template
<class T> List<T>::List()
{
pFirst = 0;
pCurpos = 0;
}
template
<class T> T* List<T>::Current()
{
if(pCurpos)
return pCurpos->pT;
return 0;
}
template
<class T> void List<T>::Restart()
{
if(pFirst)
pCurpos = pFirst;
else
pCurpos = 0;
}
template
<class T> void List<T>::Next()
{
if(pCurpos)
pCurpos = pCurpos->pNext;
}
template
<class T> void List<T>::Add(T& t)
{
Node* temp = new Node;
temp->pT =&t;
temp->pNext = pFirst;
pFirst = temp;
}
template
<class T> void List<T>::Remove(T& t)
{
Node *q = 0; //待删结点
if(*(pFirst->pT)==t) //T类中==须有定义
{
q = pFirst;
pFirst = pFirst->pNext; //待删结点在链首时的脱链
}
else
{
for(Node* p=pFirst; p->pNext; p=p->pNext)
{ //顺链查找
if(*(p->pNext->pT)==t)
{
q = p->pNext;
p->pNext = q->pNext;
break;
}
}
}
if(q)
{
delete q->pT;
delete q;
}
}
template
<class T> T* List<T>::Find(T& t)
{
for(Node* p=pFirst; p; p=p->pNext)
if(*(p->pT)==t)
return p->pT;return 0;
}
template
<class T> void List<T>::PrintList()
{
for(Node* p=pFirst; p; p=p->pNext)
cout <<*(p->pT)<<" "; //须有T的友元处理T对象输出
cout <<endl;
}
template
<class T> List<T>::~List()
{
Node* p;
while(p = pFirst){
pFirst = pFirst->pNext;
delete p->pT;
delete p;
}
pFirst = 0;
}#endif
并且创建了一个josephus问题的解决方案：
//******************************
//** Josephus问题解法六 **
//** jose6.cpp **
//******************************
#include <iostream>
#include "listtmp.h"
#include <iomanip>
using namespace std;void Display(int);
void Step(int m);
void Init(int);
List
<int> josephus; //创建单向链表模板类的全局对象
void main()
{
int n=9999, s=274, m=291; //随取三个合理的整数
//int* ap=
Init(n);
Step(s);
for(int i=1; i<n; i++){
Step(m);
int* tmp = josephus.Current();
Display(*tmp);
Step(1);//josephus.Next();
josephus.Remove(*tmp);
}
cout <<"\nThe winner is "<<*josephus.Current() << endl;
//delete[]ap;
}//以下是构造链表，初始化结点编号的函数
void Init(int n)
{
//int* a = new int[n];
for(int i=0; i<n; i++)
{
//a[i] = n - i;
Display(i+1);
josephus.Add(*new int(n - i));
}
Display ( -1 );
josephus.Restart(); //初始化迭代算子
//return a;
}//以下是显示一个结点编号的函数
void Display(int n)
{
static int k;
if(n<0){
k = 0;
cout <<endl;
return;
}
cout <<setw(5) <<n;
if (!(++k%10))
cout <<endl;
}//以下是要将指针从当前位置挪到往下数第m个结点的位置
void Step(int m)
{
for(int i=0; i<m; i++){
josephus.Next();
if(!josephus.Current()) //模拟环链表操作
josephus.Restart();
}
}
深入学习C++基础知识。。。。
