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

C ++ 程序设计教程(修订版) 第十三章 面向对象程序设计 第十三章 面向对象程序设计 抽象 分类 设计和效率 讨论Josephus问题 结构化方法的实现 面向对象方法的实现 程序维护 1、抽象 抽象和具体一一对应 就如微波炉，只有在制造时才精心设计微波炉的的各种功能，将各种功能封装在微波炉内，并留下控制面板作为接口 使用微波炉时，只需通过操作控制面板就能使用其所有功能，而不需知道微波炉内部的机制 这就是抽象 通过抽象，我们在生活中就可以忽略一些不必要的细节，从而使生活更简单， 程序也是这样。例如库函数“algorithm” 里面封装了很多关于算法的函数，我们只需使用而不用了解内部情况 1、抽象 #includealgorithm #includeiostream using 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++) { couta[i]endl; } } 2、分类 把sort函数封装在algorithm中，而不是其他类库中，是因为他们是同一类函数。 能把同一类事物的信息封装在一个类中，而且能剔除无关信息，这就是分类。 分类准确才能使抽象有意义，才能组成更有效的数据结构 3、设计和效率 编程方式有2种： 面向对象编程 结构化编程 1、小型的，不需要经常升级改动的项目，用结构化编程，可以发挥最大效率，如做算法题（ACM、ICPC） 2、大型项目就要求用面向对象编程 绝对代码行少，不意味着程序的效率高 面向对象的程序设计虽然在代码的绝对行数上要比过程化程序设计多，但是代码的效率更高，而且维护起来更加容易。 4、Josephus问题 一群小孩（n个）围成一圈，任意假定一个数m，从第1个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便离开，最后，剩下的小孩为胜利者。 过程化方法 方法一：利用数组来存储 设n=9,m=3 算法描述 （1）输入小孩数，数数间隔等 （2）建立小孩数组，给小孩编号 （3）首先输出参加的小孩编号； （4）数小孩的过程 沿数组有哪些信誉好的足球投注网站没有离开的小孩，当数到第m个没有离开的小孩时停止 如果只剩一个小孩，则停止，否则继续 输出该小孩编号，置该小孩为离开状态 记数离开小孩的个数 （5）输出胜利者 #includeiostream.h void main() { const int num=10; int interval，a[num]; for(int i=0;inum;i++) a[i]=i+1; coutPlease input the interval:; cininterval; for(i=0;inum;i++) couta[i] ; coutendl; int k=1; i= -1; while(1) { for(int j=0;jinterval;){ i=(i+1)%num; if(a[i]!=0) j++; } if(k==num) break; couta[i] ; a[i]=0; k++; } coutendlNo.a[i] boyve won.endl; } 优点：代码少，过程清晰。 缺点：效率低，因为每次数小孩，都要遍历整个数组，当数组规模很大时，非常浪费时间和空间，而且后期维护不易，不易进行程序功能的扩展。 4、讨论Josephus问题 //Josephus问题解答 建立小孩结构类型 初始化小孩数，开始位置，数小孩个数 分配小孩结构数组 for 初始化结构数组（构成环链） 挂接下一个数组元素 小孩编号 输出编号 endfor 4、讨论Josephus问题 转到开始位置 while(小孩数多于一个) 数小孩个数（一个循环） 出列小孩 将该小孩从环链中删除 endwhile 输出得胜者 返还结构数组空间 更好的过程化方法 利用循环链表 pCur 是指向当前结点的指针，*pCur表示当前结点, pivot是指向当前结点前驱结点的指针，*pivot表示* pCur的前驱结点 删除*pCur结点的语句序列为： pivot-next = pCur-next; free(pCur ); 结构化方法的实现 /****************************************************