理解c++面向对象程序设计中的抽象理论

以下是利用结构体的方法解决josephus问题：

当我们学过结构体后，我们了解到结构体自身的成员指针可以指向自身对象的地址的时候，我们很容易想到解决这个数学问题，用结构体来描述是再合适不过的了，用它可以很完美的描述环形链表。

代码如下:


//程序作者:管宁 
//站点:www.cndev-lab.com 
//所有稿件均有版权,如要转载,请务必著名出处和作者 

#include <iostream> 
#include <string> 
using namespace std; 

struct Children 
{ 
int number; 
Children *next; 
}; 

void show(Children *point,int num)//环链输出函数 
{ 
for(int i=1;i<=num;i++) 
{ 
cout<<point->number<<","; 
point = point->next; 
} 
} 

void main() 
{ 
int num;//孩子总数 
int interval;//抽选号码 
cout<<"请输入孩子总数:"; 
cin>>num; 
cout<<"请输入抽选号码:"; 
cin>>interval; 

Children *josephus = new Children[num];//设置圈的起点指针,并动态开辟堆空间用于存储数据 

Children *point = josephus;//用于初化链表的指针,起始地址与josephus指针相同 

for(int i=1;i<=num;i++) 
{ 
point -> number = i; 
point -> next = josephus + i % num;//利用+1取模的方式设置节点的next指针,当到最后的时候自动指向到第一个,形成环链 
point = point->next;//将位置移到下一饿节点也就是下一个小孩的位置 
} 

show(point,num); 

Children *cut_point; 
point=&josephus[num-1];//把起始指针设置在最后一个节点,当进入循环的时候就会从0开始,这样就好让不需要的节点脱离 
int k=0;//故意设置一个k观察while循环了多少次 
while(point->next!=point)//通过循环不断的寻找需要放弃的节点 
{ 
k++; 
for(int i = 0;i<interval;i++)//找需要放弃的节点位置 
{ 
cut_point=point;//存储截断位置指针 
point=cut_point->next;//将point的指针移动到放弃的节点位置,此处也和while循环终止条件有关系 
} 
cut_point->next=point->next;//将截断出的next指针设置成放弃处节点的next指针,使放弃处节点也就是不需要的节点脱离 
cout<<"k:"<<k<<endl; 
} 
cout<<"\n最后的赢家:"<<endl<<point->number<<endl<<point<<endl<<point->next<<endl; 
delete[] josephus; 
cin.get(); 
cin.get(); 
}

此代码较为难以理解的部分就是while循环的终止条件的设置，如果读者没有能够理解好这部分注意看下面的图式帮助学习。

结构体的解法非常重要，对于我们全面理解面向对象的程序设计的抽象问题是基础，必须看明白我们才能够进行后面知识的学习,务必认真对待。

这段代码比较前一个程序，可读性上有所加强，但仍然不太容易理解！

落叶秋客 [返回首页]