领略C++面向工具措施设计中的抽象理论
副标题#e#
许多书在一开始就开始进修josephus问题，为了让各人前面学起来较为容易我把前面涉及到此问题的处所都存心去掉了，此刻我们已经进修过了布局体和类，所以放在这里进修大概更符合一些。
在正式开始进修之前我们先回首一下如何操作数组和布局体的方法来办理，最后我们再看一下如何操作面向工具的抽象理念举办办理此问题的措施设计，彼此比拟，找出效率最高，最容易领略，最利便维护的措施来，说明操作面向工具的抽象理念举办措施设计的长处。
josephus问题其实就是一个游戏，一群小孩围成一个圈，配置一个数，这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数，当个中一个小孩报到你配置的谁人数的时候分开谁人圈，这样一来重复报下去，直到只剩下最后一个小孩的时候谁人小孩就是胜利者，写措施来找出这个小孩。
以下是数组要领:
由于数组的限制我们必需预先假设好有几多个小孩，分开的小孩他自身配置为0来标志分开状态。
代码如下：
#include <iostream>
using namespace std;
void main()
{
const int num=10;
int interval;
int a[num];
for(int i=0; i<num; i++)
{
a[i]=i+1;
}
cout <<"please input the interval: ";
cin >>interval;
for(int i=0; i<num; i++)
{
cout <<a[i] <<",";
}
cout <<endl;
int k=1;
int p=-1;
while(1)
{
for(int j=0;j<interval;)
{
p=(p+1)%num;
if(a[p]!=0)
{
j++;
}
}
if(k==num)
{
break;
}
cout<<a[p]<<",";
a[p]=0;
k++;
}
cout <<"\nNo." <<a[p] <<" boy've won.\n";
cin.get();
cin.get();
}
就数组办理来看,措施简短但效率不高可读性也欠好，此代码没有什么出格之处主要依靠一个加1取模的方法往返到首位置，形成环链:p=(p+1)%num;。
#p#副标题#e#
以下是操作布局体的要领办理josephus问题：
当我们学过布局体后，我们相识到布局体自身的成员指针可以指向自身工具的地点的时候，我们很容易想到办理这个数学问题，用布局体来描写是再符合不外的了，用它可以很完美的描写环形链表。
代码如下：
#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轮回的终止条件的配置，假如读者没有可以或许领略好这部门留意看下面的图式辅佐进修。
布局体的解法很是重要，对付我们全面领略面向工具的措施设计的抽象问题是基本，必需看大白我们才气够举办后头常识的进修,务必当真看待。
这段代码较量前一个措施，可读性上有所增强，但仍然不太容易领略！
为了更容易进修便于领略，我们的图例是以有两个小孩围成一圈，而且配置报数的数为1的环境来建造的。
#p#分页标题#e#
上面的两种办理Josephus问题的办理步伐从代码上来看，都属于一杆子到底的解法，第二种从布局表达上优于第一种，可是这两个都属于纯粹的进程式措施设计，措施固然简短,但很难让人看懂，措施的可读性不高，在我们没有进修面向工具的编程之前，智慧的人大概会把各各步调解析出来做成由几个函数来办理问题。
思路大抵可以分为以下六个部门：
1.成立布局
2.初始化小孩总数,和数小孩的数
3.初始化链表并组成环链
4.开始通过轮回数小孩得到告捷者
5.输出告捷者
6.返回堆内存空间
从表上看这个措施为了便于阅读可以写成六个函数来别离处理惩罚这六个进程，简直，这么修改事后措施的可读性是提高了一大步，可是有缺点仍然存在，措施完全袒露在外，任何人都可以修改措施，措施中的一些措施作者不但愿利用者可以或许修改的工具袒露在外，各工具得不到任何的掩护，不能担保措施在运行中不被意外修改，对付利用者来说照旧需要具备办理Josephus问题算法的本领，一旦措施变的越来越很，,每一个参加开拓的措施员都需要通读措施的所有部门，措施完全不具备黑盒效应，给多人的协作开拓带来了很大的贫苦，险些每小我私家都做了同样的反复劳动，这种为了办理一个分枝小问题写一个函数，最后由许多个办理局部问题的函数组合成的措施我们叫做布局化措施设计，布局化编程较进程化编程对比可读性是提高了，但措施不能等闲的被支解办理一个个大问题的模块，在主函数中利用他们的时候老是这个函数挪用到谁人函数，假如你并不是这些函数的作者就很难正确利便的利用这些函数，并且措施的变量重名问题带来的困扰也是很让人头痛的……
那么面向工具的措施设计又是如何办理这些问题的呢？
面向工具的措施设计的思路是这样的：
措施 = 工具 + 工具 +工具……….
这么组合而来的
对付上面的josephus问题可以把问题支解成如下的要领举办设计(如下图所示)
由上图可以看出：
面向工具的措施设计是由类组合而成的，有类一定有类的工具，措施之间的交互主要是通过工具与工具之间的干系举办操纵的。
由于我们把josephus问题解析成了josephus类和ring类，在主函数中，用户只需要利用josephus类设计其工具明晰知道Josephus类的外部接口函数也就是操纵该工具的要领initial()就可以了，至于josephus的内部实现又是如何与Ring类举办操纵的利用者一概不需要知道，只要拿来用知道接口和接口函数是什么就可以了，这样的措施设计很好的掩护了种种成员数据的安详，主函数代码挪用极其简朴只有成立工具和挪用工具要领的操纵这两部罢了，今后类一旦需要修改，只修改类体自己就可以，而主函数不需要做任何修改，这样就很好的做到了什么人做的工作什么人处理惩罚互不斗嘴。
措施的代码如下，我把工程文件压缩了作为此帖的附件提供下载，但愿读者仔细阅读仔细推敲，真正领略面向工具oop编程的特点和意图。
主措施test4.cpp
#include <iostream>
#include "josephus.h"
using namespace std;
void main()
{
Josephus a;
a.initial();
cin.get();
cin.get();
}
josephus.h
class Josephus
{
public:
Josephus(int num=10,int interval=1)
{
Josephus::num=num;
Josephus::interval=interval;
}
void initial();
protected:
int num;
int interval;
};
josephus.cpp
#include <iostream>
#include "josephus.h"
#include "ring.h"
using namespace std;
void Josephus::initial()
{
int num,interval;
cout<<"请输入孩子总数:";
cin>>num;
if(num<2)
{
cout<<"孩子总数不能小于2,不然不能组成环链!";
return;
}
cout<<"请输入抽选号码";
cin>>interval;
if(interval<1|interval>num)
{
cout<<"请输入抽选号码不能小于1可能大于小孩总数!";
return;
}
Josephus::num=num;
Josephus::interval=interval;
Ring a(num);
a.ShowRing(num);
cout<<endl;
for(int i=1;i<num;i++)
{
a.CountInterval(interval);
a.ShowWiner_loser();
a.OutChild();
}
cout<<endl<<"胜利者是:";
a.ShowWiner_loser();
}
#p#分页标题#e#
ring.h
struct Children
{
int number;
Children *next;
};
class Ring
{
public:
Ring(int num)
{
josephus = new Children[num];
point = josephus;
for(int i=1;i<=num;i++)
{
point->number = i;
point->next = josephus + i % num;
point=point->next;
}
point = &josephus[num-1];
}
~Ring()
{
delete[] josephus;
}
void ShowRing(int num);
void CountInterval(int interval);
void OutChild();
void ShowWiner_loser();
protected:
Children *josephus;
Children *point;
Children *cut_point;
};
ring.cpp
#include <iostream>
#include "ring.h"
using namespace std;
void Ring::ShowRing(int num)
{
point=josephus;//也可以写成point=point->next;但前着效率高一点点
for(int i=1;i<=num;i++)
{
cout<<point->number<<",";
point=point->next;
}
point=&josephus[num-1];//输出事后规复point应该在的位置
}
void Ring::CountInterval(int interval)//数小孩
{
for(int i=0;i<interval;i++)
{
cut_point = point;
point = cut_point->next;
}
}
void Ring::OutChild()
{
cut_point->next = point->next;//将不要节点断离
point=cut_point;
}
void Ring::ShowWiner_loser()
{
cout<<point->number<<",";
}
措施中需要留意的小处所是在这里
class Josephus
{
public:
Josephus(int num=10,int interval=1)
{
Josephus::num=num;
Josephus::interval=interval;
}
void initial();
protected:
int num;
int interval;
};
代码中的
Josephus::num=num;
Josephus::interval=interval;
利用域区分符的目标就是为了区分成员变量和局部变量Josephus(int num=10,int interval=1)
相信读者当真读完措施当真领略后应该就可以领略面向工具措施设计的用意和长处了，切记当真推敲！
各人看到面向工具措施设计的办理步伐，大概以为它的代码太多了，会猜疑它执行的效率是否足够好，呵呵！
这里只能这么说，措施的效率不是单单看措施的是非来看的，优秀的措施应该是便于维护，干系清楚的，面向工具的措施设计其实和进程式可能是布局化措施设计的思路是不斗嘴的，在差异的处所利用差异的要领，优势互补才是正道！
