清華大學(xué)出版社錢(qián)能

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

2、抽象通過(guò)抽象，我們?cè)谏钪芯涂梢院雎砸恍┎槐匾募?xì)節(jié)，從而使生活更簡(jiǎn)單，程序也是這樣。例如庫(kù)函數(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ù)庫(kù)中的函數(shù)for(int i = 0;i<9;i++){cout&l

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

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

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

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

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

8、法的實(shí)現(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)化方法的實(shí)現(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)化方法的實(shí)現(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)化方法的實(shí)現(xiàn),//數(shù)m個(gè)小孩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)化方法的實(shí)現(xiàn),13.8 面向?qū)ο蠓椒ǖ膶?shí)現(xiàn),/*************************************

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

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

14、*************************/#include #include #include "ring.h"using namespace std;,13.8 面向?qū)ο蠓椒ǖ膶?shí)現(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ū)ο蠓椒ǖ膶?shí)現(xiàn),void Ring::Count(int m){for(int i = 0;inext;}},13.8 面向?qū)ο蠓椒ǖ膶?shí)現(xiàn),void Ring::PutBoy(){static

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

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

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

19、名: josex.cpp//功能 ：//時(shí)間 : /*******************************************************/#include #include "ring.h"#include "josex.h"using namespace std;,13.8 面向?qū)ο蠓椒ǖ膶?shí)現(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ū)ο蠓椒ǖ膶?shí)現(xiàn),if(mnum

21、){cerr<<"bad interval number.\n";return;}//輸入數(shù)據(jù)合法時(shí)，賦值numOfBoys = num;beginPos = begin;interval = m;},13.8 面向?qū)ο蠓椒ǖ膶?shí)現(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ū)ο蠓椒ǖ膶?shí)現(xiàn),/**************************************************///文件名: jose4.cpp