面向?qū)ο蟮娜齻€(gè)基本特征和概念

1、面向?qū)ο蟮娜齻€(gè)基本特征(講解)面向?qū)ο蟮娜齻€(gè)基本特征是：封裝、繼承、多態(tài)。面向?qū)﹀杌咎卣鞣庋b封裝最好理解了。封裝是面向?qū)ο蟮奶卣髦唬菍?duì)象和類概念的主要特性。封裝，也就是把客觀事物封裝成抽象的類，并且類可以把自己的數(shù)據(jù)和方法只讓可信的類 或者對(duì)象操作，對(duì)不可信的進(jìn)行信息隱藏。繼承面向?qū)ο缶幊?OOP)語(yǔ)言的一個(gè)主要功能就是“繼承”。繼承是指這樣一種能力：它可以 使用現(xiàn)有類的所有功能，并在無(wú)需重新編寫原來(lái)的類的情況下對(duì)這些功能進(jìn)行擴(kuò)展。通過(guò)繼承創(chuàng)建的新類稱為“子類”或“派生類”。被繼承的類稱為“基類”、“父類”或“超類”。繼承的過(guò)程，就是從一般到特殊的過(guò)程。要實(shí)現(xiàn)繼承，可以通過(guò)"繼

2、承"( Inheritance )和"組合"(Composition )來(lái)實(shí)現(xiàn)。在某些OOP語(yǔ)言中，一個(gè)子類可以繼承多個(gè)基類。但是一般情況下，一個(gè)子類只能有一個(gè) 基類，要實(shí)現(xiàn)多重繼承，可以通過(guò)多級(jí)繼承來(lái)實(shí)現(xiàn)。繼承概念的實(shí)現(xiàn)方式有三類：實(shí)現(xiàn)繼承、接口繼承和可視繼承。?實(shí)現(xiàn)繼承是指使用基類的屬性和方法而無(wú)需額外編碼的能力；?接口繼承是指僅使用屬性和方法的名稱、但是子類必須提供實(shí)現(xiàn)的能力；?可視繼承是指子窗體(類)使用基窗體(類)的外觀和實(shí)現(xiàn)代碼的能力。在考慮使用繼承時(shí)，有一點(diǎn)需要注意，那就是兩個(gè)類之間的關(guān)系應(yīng)該是“屬于”關(guān)系。例如，Employee是一個(gè)人，Manag

3、er也是一個(gè)人，因此這兩個(gè)類都可以繼承Person 類。但是Leg類卻不能繼承Person 類，因?yàn)橥炔⒉皇且粋€(gè)人。抽象類僅定義將由子類創(chuàng)建的一般屬性和方法，創(chuàng)建抽象類時(shí)，請(qǐng)使用關(guān)鍵字Interface而不是Class。OO#發(fā)范式大致為：劃分對(duì)象抽象類-將類組織成為層次化結(jié)構(gòu)（繼承和合成）用類與實(shí)例進(jìn)行設(shè)計(jì)和實(shí)現(xiàn)幾個(gè)階段。多態(tài)多態(tài)性（polymorphisn ）是允許你將父對(duì)象設(shè)置成為和一個(gè)或更多的他的子對(duì)象相等的技 術(shù)，賦值之后，父對(duì)象就可以根據(jù)當(dāng)前賦值給它的子對(duì)象的特性以不同的方式運(yùn)作。簡(jiǎn)單的說(shuō)， 就是一句話：允許將子類類型的指針賦值給父類類型的指針。實(shí)現(xiàn)多態(tài)，有二種方式，覆蓋，重載。覆

4、蓋，是指子類重新定義父類的虛函數(shù)的做法。重載，是指允許存在多個(gè)同名函數(shù)，而這些函數(shù)的參數(shù)表不同（或許參數(shù)個(gè)數(shù)不同，或許 參數(shù)類型不同，或許兩者都不同）。其實(shí)，重載的概念并不屬于“面向?qū)ο缶幊獭?，重載的實(shí)現(xiàn)是：編譯器根據(jù)函數(shù)不同的參數(shù)表，對(duì)同名函數(shù)的名稱做修飾，然后這些同名函數(shù)就成了不同的函數(shù)（至少對(duì)于編譯器來(lái)說(shuō)是這樣的）。如，有兩個(gè)同名函數(shù)：function func（p:integer）:integer;和 functionfunc（p:string）:integer; 。那么編譯器做過(guò)修飾后的函數(shù)名稱可能是這樣的：int_func、str_func o對(duì)于這兩個(gè)函數(shù)的調(diào)用，在編譯器間就已經(jīng)

5、確定了，是靜態(tài)的（記?。菏庆o態(tài)）。也 就是說(shuō)，它們的地址在編譯期就綁定了（早綁定），因此，重載和多態(tài)無(wú)關(guān)！真正和多態(tài)相關(guān)的 是“覆蓋”。當(dāng)子類重新定義了父類的虛函數(shù)后，父類指針根據(jù)賦給它的不同的子類指針，動(dòng)態(tài)（記?。菏莿?dòng)態(tài)?。┑恼{(diào)用屬于子類的該函數(shù)，這樣的函數(shù)調(diào)用在編譯期間是無(wú)法確定的（調(diào)用 的子類的虛函數(shù)的地址無(wú)法給出）。因此，這樣的函數(shù)地址是在運(yùn)行期綁定的（晚邦定）。結(jié)論就是：重載只是一種語(yǔ)言特性，與多態(tài)無(wú)關(guān)，與面向?qū)ο笠矡o(wú)關(guān)！引用一句Bruce Eckel的話:“不要犯傻，如果它不是晚邦定，它就不是多態(tài)。”那么，多態(tài)的作用是什么呢？我們知道，封裝可以隱藏實(shí)現(xiàn)細(xì)節(jié)，使得代碼模塊化；繼承可以

6、擴(kuò)展已存在的代碼模塊（類）；它們的目的都是為了一一代碼重用。而多態(tài)則是為了實(shí)現(xiàn)另個(gè)目的一一接口重用！多態(tài)的作用，就是為了類在繼承和派生的時(shí)候，保證使用“家譜”中任 一類的實(shí)例的某一屬性時(shí)的正確調(diào)用。概念講解泛化(Generalization )圖表1泛化在上圖中，空心的三角表示繼承關(guān)系(類繼承)，在UML的術(shù)語(yǔ)中，這種關(guān)系 被稱 為泛化(Generalization ) 。 Person(人)是 基類，Teacher( 教 師)、Student( 學(xué)生)、 Guest(來(lái)賓)是子類。若在邏輯上B是A的“一種”，并且 A的所有功能和屬性對(duì)B而言都有意義，則允許B繼承A的功能和屬性。例如，教 師是

7、人，Teacher 是Person 的"一種"(a kind of )。那么類 Teacher 可以從類Person派生(繼承)。如果A是基類，B是A的派生類，那么 B將繼承A的數(shù)據(jù)和函數(shù)。如果類A和類B毫不相關(guān)，不可以為了使B的功能更多些而讓B繼承A的功能和屬性。若在邏輯上B是A的“一種" (a kind of )，則允許B繼承A的功能和屬性。聚合(組合)圖表2組合若在邏輯上 A是B的“一部分” (a part of )，則不允許 B從A派生，而是要用 A和其它 東西組合出Bo例如，眼(Eye)、鼻(Nose)、口 ( Mouth)、耳(Ear)是頭(Head)

8、的一部分，所以類 Head應(yīng)該由類Eye、Nose、Mouth、Ear組合而成，不是派生(繼承)而成。聚合的類型分為無(wú)、共享 (聚合)、復(fù)合(組合)三類。聚 合(aggregation ) o 圖表3共享上面圖中，有一個(gè)菱形(空心)表示聚合(aggregation )(聚合類型為共享)， 聚合的意義表示has-a關(guān)系。聚合是一種相對(duì)松散的關(guān)系，聚合類B不需要對(duì)被聚 合的類A負(fù)責(zé)。組 合(composition )ChssAChs+ft-圖表4復(fù)合這幅圖與上面的唯一區(qū)別是菱形為實(shí)心的，它代表了 一種更為堅(jiān)固的關(guān)系組 合(composition )(聚合類型為復(fù)合)。組 合表示的關(guān)系也是has-a

9、 ,不過(guò)在這里， A的生命期受B控制。即A會(huì)隨著B(niǎo)的創(chuàng)建而創(chuàng)建，隨B的消亡而消亡。依 賴(Dependency)圖表5依賴這里B與A的關(guān)系只是一種依賴(Dependency) 關(guān)系，這種關(guān)系表明，如果類被修改， 那么類B會(huì)受到影響。什么是面向?qū)ο?，和面向過(guò)程的區(qū)別是什么最佳答案面向過(guò)程就是分析出解決問(wèn)題所需要的步驟，然后用函數(shù)把這些步驟一步一步實(shí)現(xiàn)，使用的時(shí)候一個(gè)一個(gè)依次調(diào)用就可以了。面向?qū)ο笫前褬?gòu)成問(wèn)題事務(wù)分解成各個(gè)對(duì)象，建立對(duì)象的目的不是為了完成一個(gè)步驟，而是為了描敘某個(gè)事物在整個(gè)解決問(wèn)題的步驟中的行為。例如五子棋，面向過(guò)程的設(shè)計(jì)思路就是首先分析問(wèn)題的步驟： 1、開(kāi)始游戲， 2 、黑子先走

10、， 3 、繪制畫面， 4 、判斷輸贏，5 、輪到白子，6 、繪制畫面，7 、判斷輸贏， 8 、 返回步驟 2 ， 9 、 輸出最后結(jié)果。 把上面每個(gè)步驟用分別的函數(shù)來(lái)實(shí)現(xiàn)，問(wèn)題就解決了。而面向?qū)ο蟮脑O(shè)計(jì)則是從另外的思路來(lái)解決問(wèn)題。 整個(gè)五子棋可以分為 1 、 黑白雙方，這兩方的行為是一模一樣的， 2 、棋盤系統(tǒng)，負(fù)責(zé)繪制畫面， 3 、規(guī)則系統(tǒng)，負(fù)責(zé)判定諸如犯規(guī)、輸贏等。第一類對(duì)象（玩家對(duì)象）負(fù)責(zé)接受用戶輸入，并告知第二類對(duì)象（棋盤對(duì)象）棋子布局的變化，棋盤對(duì)象接收到了棋子的 i 變化就要負(fù)責(zé)在屏幕上面顯示出這種變化， 同時(shí)利用第三類對(duì)象 （規(guī)則系統(tǒng)） 來(lái)對(duì)棋局進(jìn)行判定?？梢悦黠@地看出， 面向?qū)?/p>

11、象是以功能來(lái)劃分問(wèn)題， 而不是步驟。 同樣是繪制棋局，這樣的行為在面向過(guò)程的設(shè)計(jì)中分散在了總多步驟中， 很可能出現(xiàn)不同的繪制版本， 因?yàn)橥ǔＴO(shè)計(jì)人員會(huì)考慮到實(shí)際情況進(jìn)行各種各樣的簡(jiǎn)化。 而面向?qū)ο蟮脑O(shè)計(jì)中，繪圖只可能在棋盤對(duì)象中出現(xiàn)，從而保證了繪圖的統(tǒng)一。功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計(jì)的可擴(kuò)展性。 比如我要加入悔棋的功能， 如果要改動(dòng)面向過(guò)程的設(shè)計(jì)， 那么從輸入到判斷到顯示這一連串的步驟都要改動(dòng)， 甚至步驟之間的循序都要進(jìn)行大規(guī)模調(diào)整。 如果是面向?qū)ο蟮脑挘?只用改動(dòng)棋盤對(duì)象就行了， 棋盤系統(tǒng)保存了黑白雙方的棋譜， 簡(jiǎn)單回溯就可以了， 而顯示和規(guī)則判斷則不用顧及， 同時(shí)整個(gè)對(duì)對(duì)象功能的調(diào)用順序

12、都沒(méi)有變化， 改動(dòng)只是局部的。再比如我要把這個(gè)五子棋游戲改為圍棋游戲， 如果你是面向過(guò)程設(shè)計(jì)， 那么五子棋的規(guī)則就分布在了你的程序的每一個(gè)角落， 要改動(dòng)還不如重寫。 但是如果你當(dāng)初就是面向?qū)ο蟮脑O(shè)計(jì)， 那么你只用改動(dòng)規(guī)則對(duì)象就可以了， 五子棋和圍棋的區(qū)別不就是規(guī)則嗎？（當(dāng)然棋盤大小好像也不一樣，但是你會(huì)覺(jué)得這是一個(gè)難題嗎？直接在棋盤對(duì)象中進(jìn)行一番小改動(dòng)就可以了。 ） 而下棋的大致步驟從面向?qū)ο蟮慕嵌葋?lái)看沒(méi)有任何變化。當(dāng)然， 要達(dá)到改動(dòng)只是局部的需要設(shè)計(jì)的人有足夠的經(jīng)驗(yàn)， 使用對(duì)象不能保證你的程序就是面向?qū)ο螅?初學(xué)者或者很蹩腳的程序員很可能以面向?qū)ο笾摱忻嫦蜻^(guò)程之實(shí)， 這樣設(shè)計(jì)出來(lái)的所謂面

13、向?qū)ο蟮某绦蚝茈y有良好的可移植性和可擴(kuò)展性。111111111111111111111111111111111111111111111111111111111111111111111111111111一、 什么是遞歸很多 數(shù)據(jù)結(jié)構(gòu) 的定義都是根據(jù)遞歸性質(zhì)來(lái)進(jìn)行定義的， 是因?yàn)檫@些結(jié)構(gòu)固有的性質(zhì)。遞歸是指某個(gè) 函數(shù) 直接或間接的調(diào)用自身。問(wèn)題的求解過(guò)程就是劃分成許多相同性質(zhì)的子問(wèn)題的求解，而小問(wèn)題的求解過(guò)程可以很容易的求出，這些子問(wèn)題的解就構(gòu)成里原問(wèn)題的解了。二、遞歸的幾個(gè)特點(diǎn)1 . 遞歸式，就是如何將原問(wèn)題劃分成子問(wèn)題。2 .遞歸出口，遞歸終止的條件，即最小子問(wèn)題的求解，可以允許多個(gè)出口。3

14、.界函數(shù)，問(wèn)題規(guī)模變化的 函數(shù) ，它保證遞歸的規(guī)模向出口條件靠攏三、遞歸的運(yùn)做機(jī)制很明顯，很多問(wèn)題本身固有的性質(zhì)就決定此類問(wèn)題是遞歸定義，所以遞歸程序很直接算法程序結(jié)構(gòu)清晰、思路明了。但是遞歸的執(zhí)行過(guò)程卻很讓人費(fèi)解，這也是讓很多人難理解遞歸的原因之一。由于遞歸調(diào)用是對(duì) 函數(shù) 自身的調(diào)用，在一次調(diào)用沒(méi)有結(jié)束之前又開(kāi)始了另外一次調(diào)用，按照作用域的規(guī)定， 函數(shù) 在執(zhí)行終止之前是不能收回所占用的空間，必須保存下來(lái)，這也就意味著每一次的調(diào)用都要把分配的相應(yīng)空間保存起來(lái)。為了更好管理這些空間，系統(tǒng)內(nèi)部設(shè)置一個(gè)棧，用于存放每次 函數(shù) 調(diào)用與返回所需的各種數(shù)據(jù)，其中主要包括 函數(shù) 的調(diào)用結(jié)束的返回地址，返回值

15、，參數(shù)和局部變量等。其過(guò)程大致如下：1 . 計(jì)算當(dāng)前 函數(shù)的實(shí)參的值2 .分配空間，并將首地址壓棧，保護(hù)現(xiàn)場(chǎng)3 .轉(zhuǎn)到函數(shù) 體，執(zhí)行各語(yǔ)句，此前部分會(huì)重復(fù)發(fā)生（遞歸調(diào)用）4 .直到出口，從棧頂取出相應(yīng)數(shù)據(jù)，包括，返回地址，返回值等等，收回空間，恢復(fù)現(xiàn)場(chǎng)，轉(zhuǎn)到上一層的調(diào)用位置繼續(xù)執(zhí)行本次調(diào)用未完成的語(yǔ)句。四、引入非遞歸從用戶使用角度來(lái)說(shuō)， 遞歸真的很簡(jiǎn)便， 對(duì)程序宏觀上容易理解。 遞歸程序的時(shí)間復(fù)雜度雖然可以根據(jù)T(n尸T(n-1)*f(n)遞歸求出，其中f(n)是遞歸式的執(zhí)行時(shí)間復(fù)雜度，一般來(lái)說(shuō)，時(shí)間復(fù)雜度和對(duì)應(yīng)的非遞歸差不多， 但是遞歸的效率是相當(dāng)?shù)偷乃饕l(fā)費(fèi)在反復(fù)的進(jìn)棧出棧， 各種中斷等

16、機(jī)制上(具體的可以參考 操作系統(tǒng) )更有甚者，在遞歸求解過(guò)程中， 某些解會(huì)重復(fù)的求好幾次，這是不能容忍的，這些也是引入非遞歸機(jī)制的原因之一。五、遞歸轉(zhuǎn)非遞歸的兩種方法1. 一般根據(jù)是否需要回朔可以把遞歸分成簡(jiǎn)單遞歸和復(fù)雜遞歸， 簡(jiǎn)單遞歸一般就是根據(jù)遞歸式來(lái)找出遞推公式(這也就引申出分治思想和動(dòng)態(tài)規(guī)劃) 。而復(fù)雜遞歸一般就是模擬系統(tǒng)處理遞歸的機(jī)制，使用?；蜿?duì)列等 數(shù)據(jù)結(jié)構(gòu) 保存回朔點(diǎn)來(lái)求解。六、幾個(gè)簡(jiǎn)單的例子1 . 求解階乘階乘的定義就是n!=n*(n-1)! 0!=1 1!=1根據(jù)定義我們很容易就想到遞歸方法,做法如下int Fact(int n)if(n=0) return 1; / 遞歸出

17、口return n*Fact(n-1) /n*Fact(n-1) 就是遞歸式，其中 n-1 就是界 函數(shù)2 .再看 Fibonacci 的例子定義：某項(xiàng)的值等于前兩項(xiàng)的和，其中第一和第二項(xiàng)為 1 。根據(jù)定義我們很容易寫出程序，這里就不寫出來(lái)了，當(dāng)我們用筆劃幾下的時(shí)候我們是否會(huì)發(fā)現(xiàn)有很多解是重復(fù)求出的。舉個(gè)例子要求F(5)F(5)=F(4)+F(3);F(4)=F(3)+F(2);F(3)=F(2)+F(1);其中F(3)求解2次。這顯然就是時(shí)間的浪費(fèi)。下面我們用遞推技術(shù)來(lái)轉(zhuǎn)化成非遞歸從例子可以發(fā)現(xiàn)我們可以倒過(guò)來(lái)求解，即從底到頂把F(n)之前要計(jì)算的東西保存下來(lái)。程序就是：int Fibona(int n)int p1=1,p2=1;/int a100=0;/a1=1,a2=1;for(int i=3;i<=n;i+)/從三開(kāi)始就可以了，后面的 return 包括 1， 2 兩種情況int r=p1;/遞推，可以使用數(shù)組全部保存p1=p2;p2+=r;/a =ai-1+ai-2return p2;/return an;3 .帶回朔的復(fù)雜遞歸：具體例子參照二叉樹(shù)的遍歷程序。url= /url舉個(gè)簡(jiǎn)單點(diǎn)的：求解按照中點(diǎn)優(yōu)先的順序遍歷線形表按照定義，當(dāng)然是想到先輸出求解的線形表中點(diǎn)值，再輸出左部分，然后右部分。部分代碼如下：void Mid_O