第 13 章_面向对象程序设计(冯)

1、C + C + 程序设计教程程序设计教程( (修订版修订版) )第十三章第十三章 面向对象程序设计面向对象程序设计Object-Oriented Programming(OOP)2第十三章第十三章 面向对象程序设计面向对象程序设计w 抽象抽象w 分类分类w 设计和效率设计和效率w 讨论讨论Josephus问题问题w 结构化方法的实现结构化方法的实现w 面向对象方法的实现面向对象方法的实现w 程序维护程序维护31、抽象、抽象w 抽象抽象和具体一一对应和具体一一对应w 就如微波炉，只有在制造时才精心设计微波炉的的各种就如微波炉，只有在制造时才精心设计微波炉的的各种功能，将各种功能封装在微波炉内，并

2、留下控制面板作功能，将各种功能封装在微波炉内，并留下控制面板作为接口为接口w 使用微波炉时，只需通过操作控制面板就能使用其所有使用微波炉时，只需通过操作控制面板就能使用其所有功能，而不需知道微波炉内部的机制功能，而不需知道微波炉内部的机制w 这就是抽象这就是抽象w 通过抽象，我们在生活中就可以忽略一些不必要的细节，通过抽象，我们在生活中就可以忽略一些不必要的细节，从而使生活更简单，从而使生活更简单，w 程序也是这样。例如库函数程序也是这样。例如库函数“algorithm” 里面封装了里面封装了很多关于算法的函数，我们只需使用而不用了解内部情很多关于算法的函数，我们只需使用而不用了解内部情况况4

3、1、抽象、抽象#include#includeusing namespace std;int main()int a = 4,2,3,1,7,5,9,6,7;sort(a,a+9);/algorithm函数库中的函数函数库中的函数for(int i = 0;i9;i+)coutaiendl;输出结果：输出结果：52、分类、分类w 把把sort函数封装在函数封装在algorithm中，而不是其他类库中，中，而不是其他类库中，是因为他们是同一类函数。是因为他们是同一类函数。w 能把同一类事物的信息封装在一个类中，而且能剔能把同一类事物的信息封装在一个类中，而且能剔除无关信息，这就是除无关信息，这就

4、是分类分类。w 分类准确才能使抽象有意义，才能组成更有效的数分类准确才能使抽象有意义，才能组成更有效的数据结构据结构63、设计和效率、设计和效率w 编程方式有编程方式有2种：种：n面向对象编程面向对象编程n结构化编程结构化编程w 1、小型的，不需要经常升级改动的项目，用结构化、小型的，不需要经常升级改动的项目，用结构化编程，可以发挥最大效率，如做算法题（编程，可以发挥最大效率，如做算法题（ACM、ICPC）w 2、大型项目就要求用面向对象编程、大型项目就要求用面向对象编程w 绝对代码行少，不意味着程序的效率高绝对代码行少，不意味着程序的效率高w 面向对象的程序设计虽然在代码的绝对行数上要比面向

5、对象的程序设计虽然在代码的绝对行数上要比过程化程序设计多，但是代码的效率更高，而且维过程化程序设计多，但是代码的效率更高，而且维护起来更加容易。护起来更加容易。 74、Josephus问题问题w 一群小孩（一群小孩（n个）围成一圈，任意假定一个数个）围成一圈，任意假定一个数m，从第从第1个小孩起，顺时针方向数，每数到第个小孩起，顺时针方向数，每数到第m个个小孩时，该小孩便离开，最后，剩下的小孩为胜小孩时，该小孩便离开，最后，剩下的小孩为胜利者。利者。 8过程化方法过程化方法w 方法一：利用数组来存储方法一：利用数组来存储w 设设n=9,m=31 2 3 4 5 6 7 8 90 1 2 3 4

6、 5 6 7 8数组下标数组下标小孩小孩编号编号 W 7 1 4 6 2 8 5 3小孩离开小孩离开的顺序的顺序取模运算：下标取模运算：下标%小孩数小孩数使得下标超界时能够回指使得下标超界时能够回指9算法描述算法描述w （1）输入小孩数，数数间隔等）输入小孩数，数数间隔等w （2）建立小孩数组，给小孩编号）建立小孩数组，给小孩编号w （3）首先输出参加的小孩编号；）首先输出参加的小孩编号；w （4）数小孩的过程）数小孩的过程l沿数组搜索没有离开的小孩，当数到第沿数组搜索没有离开的小孩，当数到第m个没有离开的个没有离开的小孩时停止小孩时停止l如果只剩一个小孩，则停止，否则继续如果只剩一个小孩，则

7、停止，否则继续l输出该小孩编号，置该小孩为离开状态输出该小孩编号，置该小孩为离开状态l记数离开小孩的个数记数离开小孩的个数w （5）输出胜利者）输出胜利者10#includevoid main() const int num=10; int interval，anum; for(int i=0;inum;i+) ai=i+1; coutinterval; for(i=0;inum;i+) coutai ; coutendl; int k=1; i= -1; while(1) for(int j=0;jinterval;) i=(i+1)%num; if(ai!=0) j+; if(k=num)

8、 break; coutai ; ai=0; k+; coutendlNo.ai boyve won.next = pCur-next; free(pCur );删除元素删除元素:i-1nextinexti+1 next16结构化方法的实现结构化方法的实现/*/文件名文件名:jose3.cpp/功能功能 ： Josephus 问题解法三问题解法三/*/#include #include using namespace std;struct Joseint code;Jose *next;17/全局变量全局变量int n;/小孩数小孩数int begin; /开始位置开始位置int m;/数小孩

9、间隔数小孩间隔Jose *pivot; /链表哨兵链表哨兵Jose *pCur;/当前节点指针当前节点指针/函数声明函数声明int assign(); /赋初值，返回赋初值，返回1成功，返回成功，返回0失败失败void initial(Jose *pBoys);/初始化环链表初始化环链表void count(int m);/数数m个小孩个小孩void process();/处理所有未获胜小孩处理所有未获胜小孩18/主函数主函数int main() if(!assign() coutThe program failed.n;return 0;Jose *pJose = new Josen;/分配

10、结构数组分配结构数组initial(pJose);count(:begin);process();coutnthe winner is codeendl;delete pJose;19/赋初值赋初值int assign() int number,start,count;coutnumberstartcount;if(number2)cerrbad number of boysn; return 0; if(start0)cerrbad begin position.n; return 0; if(countnumber)cerrbad interval number.n; return 0;

11、n = number;:begin = start -1;m = count;return 1;20/链表初始化链表初始化void initial(Jose *pJose) int lineCount = 0;Jose *px = pJose;for(int i = 1;inext = pJose+i%n;px-code = i;px = px-next;if(lineCount + %10) = 0)coutendl;coutsetw(4)i;coutendl;pCur = pJose+n-1;21void count(int m) /数数m个小孩个小孩 for(int i =0;inext

12、; /处理获胜者决出之前的所有小孩处理获胜者决出之前的所有小孩void process() int l = 0;for(int i =1;in-1;i+)count(m);if(l + % 10) = 0) coutendl;coutsetw(4)code;pivot-next = pCur-next;pCur = pivot;224、讨论、讨论Josephus问题问题w 结构化程序设计方法按功能分割问题。结构化程序设计方法按功能分割问题。w 面向对象程序设计按对象分割问题面向对象程序设计按对象分割问题23面向对象方法面向对象方法w 一群小孩（一群小孩（n个）围成一圈，任意假定一个数个）围成一

13、圈，任意假定一个数m，从第从第1个小孩起，顺时针方向数，每数到第个小孩起，顺时针方向数，每数到第m个小个小孩时，该小孩便离开，最后，剩下的小孩为胜利孩时，该小孩便离开，最后，剩下的小孩为胜利者。者。小孩，小孩数，数数间隔，数数，胜利者，小小孩，小孩数，数数间隔，数数，胜利者，小孩离开，循环链表孩离开，循环链表24类描述类描述Jose成员函数：成员函数： 构造函数构造函数 问题初始化问题初始化 /进行数据校验进行数据校验 求获胜者求获胜者数据成员：数据成员： 小孩数小孩数 开始位置开始位置 数数间隔数数间隔；25类描述类描述ring成员函数：成员函数： 构造函数构造函数 数小孩数小孩 /沿链表搜

14、索沿链表搜索 输出当前位置的小孩输出当前位置的小孩 /输出当前位置输出当前位置 当前位置小孩脱链当前位置小孩脱链 /删除当前节点删除当前节点 析构函数析构函数数据成员：数据成员： 开始位置指针开始位置指针 当前指针当前指针 前驱结点指针前驱结点指针；26面向对象方法的实现面向对象方法的实现/*/文件名文件名: ring.h/*/struct Boy int code;Boy *next;class Ringpublic:Ring(int n);void Count(int m);/数数m个小孩个小孩void PutBoy();/输出小孩当前的编号输出小孩当前的编号void ClearBoy()

15、;Ring();protected:Boy *pBegin,*pivot,*pCurrent;27/文件名文件名: ring.cpp/*/#include #include #include ring.husing namespace std;Ring:Ring(int n)pBegin = new Boyn;/分配小孩结构数组分配小孩结构数组pCurrent = pBegin;for(int i = 1;inext)pCurrent-next=pBegin+i%n;pCurrent-code = i;PutBoy();coutendl;pCurrent =&pBeginn-1;28void

16、Ring:Count(int m) for(int i = 0;inext;void Ring:PutBoy() static int numInLine;if(numInLine + %10 = 0)coutendl;coutsetw(4)code;29void Ring:ClearBoy() pivot-next = pCurrent-next;pCurrent=pivot;Ring:Ring() delete pBegin;30/*/文件名文件名: josex.h/*/class Josepublic:Jose(int boys = 10,int begin = 1,int m = 3)

17、 numOfBoys =boys;beginPos =begin;interval = m;void Initial();void GetWinner();protected:int numOfBoys;int beginPos;int interval;31/文件名文件名: josex.cpp/*/#include #include ring.h#include josex.husing namespace std;void Jose:Initial() int num,begin,m; cinnumbeginm; /此处省略判断此处省略判断num、begin、m有效性的语句有效性的语句 /输入数据合法时，赋值输入数据合法时，赋值 numOfBoys=num; beginPos=begin; interval=m;32void Jose:GetWinner()Ring x(numOfBoys);x.Count(beginPos);cout”now output the le