求高手解析一个面向C++的数据结构题~
#include<iostream>
using namespace std;
template<class T> class list;
template<class T> class listnode{
friend class list<T>;
public:
listnode(){link = NULL;}
listnode(const T& item){data=item; link=NULL;}
listnode<T> *nextnode( ) { return link ;}
private:
T data;
listnode<T> * link;
};
template<class T> class list{
public:
list( ){ first=last= new listnode<T>( ); }
~list( ){}
void lastinsert ( T x);
listnode<T>* search(T x);
bool insert(int i, T x);
bool remove(int i, T x);
void circlist(){last->link=first->link;}
void josephus(list<T>&js,int n,int m);
void print();
private:
listnode<T> *first, *last;
};
template<class T> void list<T>::lastinsert( T x){
listnode<T> * p=new listnode<T>( x);
last = last -> link = p;
}
template<class T> listnode<T> * list<T>::search( T x)
{
listnode<T> * p=first->link;
while(p!=NULL)
if(p->data==x)break;
else p=p->link;
return p;
}
template<class T> bool list<T>::remove(int i, T x)
{
listnode<T>*del,*p;
if(i<=1){del=first;first=first->link;}
else{
p=first;
for(int k=1;k<i;k++)
if(p==NULL)break;
else p=p->link;
if(p==NULL||p->link==NULL)
{cout<<"无效删除!\n";return 0;}
del=p->link;
p->link=del->link;
}
x=del->data;delete del;
return true;
}
template<class T> bool list<T>::insert(int i, T x)
{
if(first==NULL||i==0){
listnode<T>*newnode=new listnode<T>(x);
if(newnode==NULL){cout<<"error!\n";return 0;}
newnode->link=first;first=newnode;
}
else{
listnode<T>*p=first;
for(int k=1;k<i;k++)
if(p==NULL)break;
else p=p->link;
if(p==NULL){cout<<"无效插入！\n";return 0;}
else{
listnode<T>*newnode=new listnode<T>(x);
if(newnode==NULL){cout<<"error!\n";return 0;}
newnode->link=p->link;
p->link=newnode;
}
}
return true;
}
template<class T> void list<T>::print(){
listnode<T> * p =first->link;
while(p != NULL)
{
cout<< p->data<<" ";
p = p->link;
}
cout<<endl;
}
template<class T> void list<T>::josephus(list<T>&js, int n,int m)
{
int i,j;
listnode<T> *p=first->link,*p1=NULL;
for(i=0;i<n-1;i++)
{
for(j=1;j<m;j++)
{
p1=p;
if (p->link != NULL)
p = p->link;
else
{
p = first->link;
}
}
cout<<p->data<<endl;
p1->link=p->link;
delete p;
p=p1->link;
if (p == NULL)
{
p = first->link;
}
if (p == p1)
{
cout<<"剩下"<<p1->data<<endl;
}
}
}
int main()
{
list<char> a;
int k, c,d;
cout << "人数及间隔" << endl;
cin >> c >> d;
for( k=1;k<=c;k++)
a.insert(k,'A' - 1 + k);
a.print();
a.josephus(a,c,d);
system("pause");
return 0;
}
答案：
//著名的约瑟夫问题的代码
#include<iostream>
using namespace std;
template<class T> class list; //定义一个类模板，templete这个定义模板
template<class T> class listnode{
friend class list<T>; //声明list是listmode的友元类，这样listmode类就可以访问list中私有成员什么的啦
public:
listnode(){link = NULL;} //构造函数
listnode(const T& item){data=item; link=NULL;}//当实例化时如果赋初值了就用这个构造函数，否则用上面那个构造函数
listnode<T> *nextnode( ) { return link ;}
private:
T data; //节点的数据部分
listnode<T> * link;//节点的指针部分，指向下一个数的
};
//////说明
template<class T> class list{
public:
list( ){ first=last= new listnode<T>( ); } //first和last都是第一个构造函数的，是没有data的，底下要用
~list( ){}//析构
void lastinsert ( T x);
///listnode<T>* search(T x);//各种函数，在底下实现
bool insert(int i, T x);//插入一个数
bool remove(int i, T x);//删除一个数
void circlist(){last->link=first->link;}//让链表形成一个环
void josephus(list<T>&js,int n,int m);
void print();//输出
private:
listnode<T> *first, *last;//定义头指针和尾指针
};
//////////函数体在类外实现
template<class T> void list<T>::lastinsert( T x){
listnode<T> * p=new listnode<T>( x);
last = last -> link = p;
}
//////////搜索下一个链头，这个就不用解释了吧，一个一个的试验，如果data不对，再看下一个节点
template<class T> listnode<T> * list<T>::search( T x)
{
listnode<T> * p=first->link;
while(p!=NULL)
if(p->data==x)break;
else p=p->link;
return p;
}
//////////删除节点,这里都懂的吧
template<class T> bool list<T>::remove(int i, T x)
{
listnode<T>*del,*p;
if(i<=1){del=first;first=first->link;}
else{
p=first;
for(int k=1;k<i;k++)
if(p==NULL)break;
else p=p->link;
if(p==NULL||p->link==NULL)
{cout<<"无效删除!\n";return 0;}
del=p->link;
p->link=del->link;
}
x=del->data;delete del;
return true;
}
/////////////插入节点的函数
template<class T> bool list<T>::insert(int i, T x)//i表示为第几个数据
{
if(first==NULL||i==0){
listnode<T>*newnode=new listnode<T>(x);//调用的是带初值的构造函数
if(newnode==NULL){cout<<"error!\n";return 0;}
newnode->link=first;//带头的链表，用的是前插法
first=newnode;//前插法吧
}
else{
listnode<T>*p=first;
for(int k=1;k<i;k++)
if(p==NULL)break;
else p=p->link;//这上面几行代码是保证p地址什么的都是肯定存在的
if(p==NULL)
{cout<<"无效插入！\n";return 0;}//说明first没有插入成功
else{
listnode<T>*newnode=new listnode<T>(x);
if(newnode==NULL){cout<<"error!\n";return 0;}
newnode->link=p->link;//把first下一个节点，让newnode也可以找到
p->link=newnode;//把first的指针就指向了新的节点，以前的节点newnode可以找到
}
}
return true;
}
//////////////
template<class T> void list<T>::print(){
listnode<T> * p =first->link;
while(p != NULL)//循环输出data数据哈
{
cout<< p->data<<" ";
p = p->link;
}
cout<<endl;
}
/////////////
template<class T> void list<T>::josephus(list<T>&js, int n,int m)
{
int i,j;
listnode<T> *p=first->link,*p1=NULL;//因为first本身是没有data的，只是一个空的头节点，所以是first的下一个节点
for(i=0;i<n-1;i++)
{
for(j=1;j<m;j++)
{
p1=p;
if (p->link != NULL)
p = p->link;//循环的去找那个节点，比如，你说间隔2，那么它就一直找，给你找到第2个数字
else
{
p = first->link;//这里是可能间隔比较大，超过了总人数的话【迟早会发生的】，就循环回去，再从头开始找啊找
}
}
cout<<p->data<<endl;//输出要删除的节点所有的数据
p1->link=p->link;
delete p;
p=p1->link;
if (p == NULL)
{
p = first->link;
}
if (p == p1)
{
cout<<"剩下"<<p1->data<<endl;
}
}
}
////////主函数
int main()
{
list<char> a; //定义为字符类型的
int k, c,d;
cout << "人数及间隔" << endl;
cin >> c >> d;
for( k=1;k<=c;k++)
a.insert(k,'A' - 1 + k);//输入几个字符，字符本身是可以是数字，所以可以相加减的
a.print();
a.josephus(a,c,d);
system("pause");//system函数是用来执行一条dos命令或运行一个外部程序，pause是暂停，并等待用户按键,也可不用
return 0;
}
上一个：求用C++语言创建链表的程序
下一个：c++要怎样学，才好啊!!!!!!
