抽象与分类
什么是抽象?
面向对象编程设计的优点?
面向对象程序设计基于两个原则：
抽象
分类
抽象是对具体对象（问题）进行概括，抽出这一类对象的公共性质并加以描述的过程。
- 先注意问题的本质及描述，其次是实现过程或细节。
- 数据抽象：描述某类对象的属性或状态（对象相互区别的物理量）
- 代码抽象：描述某类对象的共有的行为特征或具有的功能。
抽象的实现：通过类的声明。
什么是分类
- 层层分类，使概念逐渐细化，即具体化。相反，归类的结果，便是逐步抽象的过程。
- 在面向对象的程序设计中，对象被分成类。类又是层层分解的，这些类与子类的关系可以被规格化地描述。
- 描述了类，再描述其子类，就可以只描述其增加的部分。
- 所有子类层次上的编程，都只需在已有的类的基础上进行。
设计与效率
面向对象程序设计比结构化程序
- 对于大部分问题来说能够产生出更加有效的程序
- 可读性更好
- 可维护性好
结构化方法分析
Josephus 问题
- 初始化小孩数，开始位置，数小孩数；
- 初始化环链表(采用链表数据结构来解)；
- 数小孩；
- 处理未获胜的小孩。分解之后，主程序描述变得短小了：
Josephus问题解答
- 建立结构
- 初始化小孩数，开始位置，数小孩个数
- 初始化环链表(采用链表数据结构来解)
- 转到开始位置(一个循环)
- 处理未获胜的小孩
- 输出得胜者
- 返还结构数组空间
#include <iostream>
#include<stdlib.h>
using namespace std;
typedef struct Node
{
int data;
struct Node *next;
}Node,*List;
class Ring//环链表
{
private:
List First;
int Count;
int Current;
//List Begin;
public:
void Print();
void Clear(){};
void Creatlist(int n,int m,int z);
void Pivot();
};
void Ring::Creatlist(int n,int m,int z)
{
List p;
int i;
First=(Node*)malloc(sizeof(Node));
if(!First)
{
cout<<"memory allocation error!\n";
return ;
}
First->data=1; First->next=First;
for(i=n;i>1;--i)
{
p=(Node*)malloc(sizeof(Node));
if(!p)
{
cout<<"memory allocation error!\n";
return;
}
p->data=i; p->next=First->next; First->next=p;
}
Count = n;
Current = m;
if(z<1)return;
for(int j = 0;j<z;j++)
{
First=First->next;
}
}
void Ring::Print()
{
List p=First;
do
{
cout<<p->data<<" ";
p=p->next;
}while(p!=First);
cout<<endl;
}
void Ring::Pivot()
{
Node* p=First,*pre=NULL;
int i,j;
for(i=0;i<Count-1;++i)
{
for(j=1;j<Current;++j)
{
pre=p;
p=p->next;
}
cout<<"出列的人是"<<p->data<<endl;
pre->next=p->next; free(p);
p=pre->next;
}
cout<<"The winner is "<<p->data<<endl;
}
class Josephus
{
private:
int Boynumber;//孩子数量
int Beginpos;//开始位置
int Inteval;//间隔
Ring Head;
public:
void Inital();//初始化
void Getwinner();//获得胜利者
void Output();
};
void Josephus::Inital()
{
cout<<"Input the Boynumber , Inteval and Beginpos:";
cin>>Boynumber>>Inteval>>Beginpos;
if(Inteval < 2)Inteval = 2;
Head.Creatlist(Boynumber,Inteval,Beginpos);
}
void Josephus::Getwinner()
{
Head.Pivot();
}
void Josephus::Output()
{
Head.Print();
}
int main()
{
Josephus jose;
jose.Inital();
jose.Output();
jose.Getwinner();
return 0;
}
