清華大學出版社錢能

1、清華大學出版社 錢 能,講師：曹曉麗,第十三章 面向?qū)ο蟪绦蛟O(shè)計,主講教師：曹曉麗,第十三章 面向?qū)ο蟪绦蛟O(shè)計,抽象分類設(shè)計和效率討論Josephus問題結(jié)構(gòu)化方法的實現(xiàn)面向?qū)ο蠓椒ǖ膶崿F(xiàn)程序維護,13.1 抽象,抽象和具體一一對應就如微波爐，只有在制造時才精心設(shè)計微波爐的的各種功能，將各種功能封裝在微波爐內(nèi)，并留下控制面板作為接口使用微波爐時，只需通過操作控制面板就能使用其所有功能，而不需知道微波爐內(nèi)部的機制這就是

2、抽象通過抽象，我們在生活中就可以忽略一些不必要的細節(jié)，從而使生活更簡單，程序也是這樣。例如庫函數(shù)“algorithm” 里面封裝了很多關(guān)于算法的函數(shù)，我們只需使用而不用了解內(nèi)部情況,#include#includeint main(){int a[] = {4,2,3,1,7,5,9,6,7};sort(a,a+9);//algorithm函數(shù)庫中的函數(shù)for(int i = 0;i<9;i++){cout&l

3、t;<a[i]<<endl;}},輸出結(jié)果：,13.1 抽象,13.2 分類,把sort函數(shù)封裝在algorithm中，而不是其他類庫中，是因為他們是同一類函數(shù)。能把同一類事物的信息封裝在一個類中，而且能剔除無關(guān)信息，這就是分類。分類準確才能使抽象有意義，才能組成更有效的數(shù)據(jù)結(jié)構(gòu),13.3 設(shè)計和效率,編程方式有2種：面向?qū)ο缶幊探Y(jié)構(gòu)化編程小型的，不需要經(jīng)常升級改動的項目，用結(jié)構(gòu)化編程，可以發(fā)揮最大效率，

4、如做算法題（ACM、ICPC）大型項目就要求用面向?qū)ο缶幊?13.4 討論Josephus問題,//Josephus問題解答建立小孩結(jié)構(gòu)類型初始化小孩數(shù)，開始位置，數(shù)小孩個數(shù)分配小孩結(jié)構(gòu)數(shù)組for 初始化結(jié)構(gòu)數(shù)組（構(gòu)成環(huán)鏈）掛接下一個數(shù)組元素小孩編號輸出編號endfor,轉(zhuǎn)到開始位置while(小孩數(shù)多于一個)數(shù)小孩個數(shù)（一個循環(huán)）出列小孩將該校還從環(huán)鏈中刪除endwhile輸出得勝者返還結(jié)構(gòu)

5、數(shù)組空間,13.4 討論Josephus問題,結(jié)構(gòu)化程序設(shè)計方法按功能分割問題。面向?qū)ο蟪绦蛟O(shè)計按對象分割問題,13.4 討論Josephus問題,13.6 結(jié)構(gòu)化方法的實現(xiàn),/*******************************************************///文件名:jose3.cpp//功能 ： Josephus 問題解法三//時間 : /************************

6、*******************************/#include #include using namespace std;struct Jose{int code;Jose *next;};,//全局變量int n;//小孩數(shù)int begin; //開始位置int m;//數(shù)小孩間隔Jose *pivot; //鏈表哨兵Jose *pCur;//當前節(jié)點指針//函數(shù)聲明int

7、assign(); //賦初值，返回1成功，返回0失敗void initial(Jose *pBoys);//初始化環(huán)鏈表void count(int m);//數(shù)m個小孩void process();//處理所有未獲勝小孩,13.6 結(jié)構(gòu)化方法的實現(xiàn),//主函數(shù)int main(){if(!assign()){coutcode<<endl;delete[] pJose;},13.6 結(jié)構(gòu)化方

8、法的實現(xiàn),//賦初值int assign(){int number,start,count;cout>number>>start>>count;if(number<2){cerr<<"bad number of boys\n";return 0;},13.6 結(jié)構(gòu)化方法的實現(xiàn),if(startnumber){cerr<

9、;<"bad interval number.\n";return 0;}n = number;::begin = start -1;m = count;return 1;},13.6 結(jié)構(gòu)化方法的實現(xiàn),//鏈表初始化void initial(Jose *pJose){int lineCount = 0;Jose *px = pJose;for(int i = 1;in

10、ext = pJose+i%n;px->code = i;px = px->next;if((lineCount ++ %10) == 0)cout<<endl;cout<<setw(4)<<i;}cout<<endl;pCur = pJose+n-1;},13.6 結(jié)構(gòu)化方法的實現(xiàn),//數(shù)m個小孩void count(int

11、 m){for(int i =0;inext;}}//處理獲勝者決出之前的所有小孩void process(){int l = 0;for(int i =1;icode;pivot->next = pCur->next;pCur = pivot;}},13.6 結(jié)構(gòu)化方法的實現(xiàn),13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),/*************************************

12、****************///文件名: ring.h//功能 ：//時間 : /*****************************************************/struct Boy{int code;Boy *next;};,class Ring {public:Ring(int n);void Count(int m);//數(shù)m個小孩void PutBoy();

13、//輸出小孩當前的編號void ClearBoy();~Ring();protected:Boy *pBegin,*pivot,*pCurrent;};,13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),/*******************************************************///文件名: ring.cpp//功能 ：//時間 : /******************************

14、*************************/#include #include #include "ring.h"using namespace std;,13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),Ring::Ring(int n){pBegin = new Boy[n];//分配小孩結(jié)構(gòu)數(shù)組pCurrent = pBegin;for(int i = 1;inext){pCurrent->

15、;next=pBegin+i%n;pCurrent->code = i;PutBoy();}cout<<endl;pCurrent =&pBegin[n-1];},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),void Ring::Count(int m){for(int i = 0;inext;}},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),void Ring::PutBoy(){static

16、 int numInLine;if(numInLine ++ %10 == 0)coutcode;},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),void Ring::ClearBoy(){pivot->next = pCurrent->next;pCurrent=pivot;}Ring::~Ring(){delete[] pBegin;},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),/****************

17、***************************************///文件名: josex.h//功能 ：//時間 : /*******************************************************/class Jose{public:Jose(int boys = 10,int begin = 1,int m = 3){numOfBoys =boys;beg

18、inPos =begin;interval = m;},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),void Initial();void GetWinner();protected:int numOfBoys;int beginPos;int interval;};,13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),/*******************************************************///文件

19、名: josex.cpp//功能 ：//時間 : /*******************************************************/#include #include "ring.h"#include "josex.h"using namespace std;,13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),void Jose::Initial(){int num,

20、begin,m;cout>num>>begin>>m;if(num<2){cerr<<"bad number of boys.\n";return;}if(begin<0){cerr<<"bad beginning position.\n";return;},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),if(mnum

21、){cerr<<"bad interval number.\n";return;}//輸入數(shù)據(jù)合法時，賦值numOfBoys = num;beginPos = begin;interval = m;},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),void Jose::GetWinner(){Ring x(numOfBoys);x.Count(beginPos);for(int i =

22、 1;i<numOfBoys;i++){x.Count(interval);x.PutBoy();x.ClearBoy();}cout<<"\nthe winner is ";x.PutBoy();},13.8 面向?qū)ο蠓椒ǖ膶崿F(xiàn),/**************************************************///文件名: jose4.cpp