程序設(shè)計基礎(chǔ)（上）

前言

C++的常見錯誤

語法錯誤：

混淆結(jié)構(gòu)體類型與結(jié)構(gòu)體變量的區(qū)別，為一個結(jié)構(gòu)體類型賦值熊泵。不能為結(jié)構(gòu)體類型賦值瘦赫，只能為結(jié)構(gòu)體變量的各成員賦值。 混淆類類型與對象的區(qū)別梁肿，為一個類類型賦值蜓陌。不能為類類型賦值，只能為類類型的變量——對象的各成員賦值吩蔑。

調(diào)用類的無參成員函數(shù)钮热，不加小括號。函數(shù)調(diào)用的形式是：函數(shù)名（實參表）烛芬，對無參函數(shù)調(diào)用時不能缺少小括號隧期，即函數(shù)調(diào)用形式是：函數(shù)名（）。

調(diào)用構(gòu)造函數(shù)赘娄。類的構(gòu)造函數(shù)在創(chuàng)建對象時仆潮，由編譯系統(tǒng)自動調(diào)用一次。當(dāng)一個對象已經(jīng)產(chǎn)生遣臼，只能通過其它方法給對象的數(shù)據(jù)成員賦值性置，不能再次調(diào)用構(gòu)造函數(shù)來修改對象的數(shù)據(jù)成員。

邏輯錯誤：

越界暑诸、溢出蚌讼、等號與賦值混淆，分號个榕，復(fù)合語句花括號篡石，case+break，舍入誤差

C++常見問題匯總

第一章 緒論

第二章 基本數(shù)據(jù)的表示與處理

利用后綴區(qū)分二進制（B）西采，八進制（O/Q）凰萨，十進制（D）和十六進制（H）

數(shù)制轉(zhuǎn)換： 非十→十：按權(quán)展開求和

十→非十：整數(shù)部分除基取余，小數(shù)部分乘基取整

逗號表達式一次求值械馆，最后一個表達式的值就是整個逗號表達式的值

正數(shù)的補碼與原碼相同胖眷，負(fù)數(shù)的補碼等于其原碼除符號位外按位取反之后末位加一；補碼的補碼等于原碼霹崎。

（IEEE754）采用浮點數(shù)近似表示實數(shù)：?珊搀，s為數(shù)值符號稱為數(shù)符；M為數(shù)值精度稱為尾數(shù)尾菇，采用原碼表示境析，二進制規(guī)格化方法（最高有效位為1囚枪，只存儲尾數(shù)的小數(shù)部分）；指數(shù)E稱為階碼劳淆，用移碼表示

漢字編碼外碼（輸入碼）链沼、交換碼（國際碼）、機內(nèi)碼和字形碼（點陣/矢量）

邏輯表達式：短路求值

數(shù)據(jù)類型轉(zhuǎn)換：隱式轉(zhuǎn)換（自動轉(zhuǎn)換）&顯式轉(zhuǎn)換（強制轉(zhuǎn)換）

sizeof("x")的長度為2沛鸵，存儲字符串時自動加上了末尾的字符串結(jié)束標(biāo)志'\0'括勺；但對于char定義的數(shù)組，大小為數(shù)組大星疾捍；

優(yōu)先級和結(jié)合性：運算符優(yōu)先級不是運算優(yōu)先級，而是結(jié)合性優(yōu)先級蜈缤；結(jié)合性（左/右：單目/條件/賦值）

第三章 選擇與迭代

單路拾氓，雙路，嵌套底哥，多路

if...else咙鞍，switch...case...default

for，while趾徽，do...while

continue续滋；break；goto

第四章 結(jié)構(gòu)化數(shù)據(jù)

在C++中一般類型的數(shù)組訪問必須逐個元素進行孵奶，但對字符串?dāng)?shù)組來說可以整體操作疲酌。

結(jié)構(gòu)體：多屬性數(shù)據(jù)

對結(jié)構(gòu)體變量中成員的訪問只能逐個進行（成員訪問“.”），相同類型的結(jié)構(gòu)體變量之間可以整體賦值

枚舉：enum了袁。只能用枚舉常量為枚舉變量賦值朗恳，而不能用整數(shù)的值

選擇排序：

第五章 模塊化

帶默認(rèn)形參值的函數(shù)：如果有函數(shù)聲明，則應(yīng)在函數(shù)聲明處指定载绿，否則直接在函數(shù)定義中指定粥诫。

函數(shù)重載：不同的函數(shù)具有相同的函數(shù)名，根據(jù)傳遞實參在數(shù)量或類型上的不同來判斷

編譯預(yù)處理命令以#開頭崭庸，且末尾沒有分號怀浆。包括文件包含，宏定義怕享，條件編譯执赡；

• 文件包含：包含系統(tǒng)頭文件#include <文件名>包含自定義頭文件include "文件名"

• 宏定義：宏定義以#define開頭，在編譯預(yù)處理時利用指定的字符串進行宏替換函筋，無參/有參

• 條件編譯：#ifdef...[#else]...#endif&#ifndef...[#else]...#endif&#if..[#else]...#endif例子#define DEBUG #ifdef DEBUG 程序塊#endif

多文件系統(tǒng)避免重復(fù)包含沙合，例global.h

#ifndef GLOBAL
#define GLOBAL
#include "global.h"
#endif

根據(jù)變量定義的位置和方式的不同，變量的存儲類型分為全局變量跌帐，局部變量首懈，靜態(tài)全局變量和靜態(tài)局部變量芳来。作用域：作用范圍（空間）；生存期：壽命長短（時間）猜拾。全局變量：定義在所有函數(shù)之外，局部變量：在函數(shù)內(nèi)部定義的變量佣盒。初值：在定義時若沒有初始化挎袜。

函數(shù)的作用域：外部函數(shù)（extern）/靜態(tài)函數(shù)（static文件作用域）

第六章數(shù)據(jù)存儲

內(nèi)存空間：代碼區(qū)肥惭、全局?jǐn)?shù)據(jù)區(qū)盯仪、堆區(qū)（動態(tài)數(shù)據(jù)）、棧區(qū)（局部數(shù)據(jù)）蜜葱。

&取地址?*取內(nèi)容：互逆運算

指針變量的數(shù)據(jù)類型必須與其指向變量的數(shù)據(jù)類型一致全景，否則需要給出顯式的強制類型轉(zhuǎn)換

數(shù)組名相當(dāng)于指針常量

int a[4];
int *p1=a;//或int *p1=&a[0];
//對于一維數(shù)組，以下形式等價
//*(p1+i)(或*(a+i))可以寫作p1[i](或a[i])
//p1+i(或a+i)也可以寫作&p1[i](或&a[i])

二維數(shù)組的數(shù)組名是一個指向行的指針常量牵囤，指向行的指針變量int (*p)[列數(shù)]

利用new和delete進行內(nèi)存空間的動態(tài)分配和釋放堆內(nèi)存分配成功后爸黄，返回動態(tài)分配的內(nèi)存空間的首地址，保存在指針變量中揭鳞，不成功返回NULL

動態(tài)分配用于存儲多個數(shù)據(jù)元素的內(nèi)存空間new <數(shù)據(jù)類型>[<表達式>]炕贵，表達式可以是常量表達式也可以是變量表達式，用完之后需要顯式釋放delete []<指針表達式>：指針表達式為首地址野崇，若指向的堆空間只包含一個元素称开，可以省略[]

int *p,*pArray;
p=new int(3);//申請一個元素大小的內(nèi)存空間，并初始化乓梨，值為3
pArray=new int[3];//申請三個int空間
delete p;//所指向堆內(nèi)存只包含一個元素鳖轰，省略[]
delete []pArray;

二級指針：指向指針的指針，定義格式：數(shù)據(jù)類型 **變量名

指針作為函數(shù)參數(shù)：

1. 實參是一維數(shù)組的首地址扶镀，形參（int p[]或者int *p）是同類型的指針變量蕴侣；

2. 實參是變量的首地址，對應(yīng)的形參是與變量同類型的指針變量狈惫；

3. 實參是二維數(shù)組的首地址：指向行的指針變量a.<數(shù)據(jù)類型>(*<形參名>)[<行長度>]b.<數(shù)據(jù)類型><形參名>[][行長度]睛蛛；

4. 實參是字符串常量的首地址，指針變量只能用于獲取內(nèi)存空間中的數(shù)據(jù)而不能修改胧谈；

5. 實參是符號常量的首地址忆肾，對應(yīng)形參為常量指針const<數(shù)據(jù)類型>*<變量名>不能使用常量指針修改其所指向內(nèi)存空間中的數(shù)據(jù)，不能使用普通指針指向符號常量的首地址菱肖，可以通過指針常量修改內(nèi)存中的數(shù)據(jù)客冈，不能更改指針常量所指向的地址

   • 注意區(qū)分常量指針和指針常量：const<數(shù)據(jù)類型>*<變量名>&<數(shù)據(jù)類型>*const<常量名>

   • 指針常量和符號常量，在定義時需要初始化

   • 可以將一個指針同時定義為常量指針和指針常量稳强，該指針指向的內(nèi)存地址和內(nèi)存中的數(shù)據(jù)均不可修改

6. 實參是函數(shù)的首地址：函數(shù)名是一個函數(shù)指針常量场仲，可以定義函數(shù)指針變量指向函數(shù)的首地址和悦，并使用函數(shù)指針變量代替函數(shù)名進行調(diào)用；<函數(shù)類型>(*<變量名>)(<形參類型表>)渠缕，通過函數(shù)指針調(diào)用函數(shù)<函數(shù)指針>(<實參表>)或(*<函數(shù)指針>)(<實參表>)鸽素；函數(shù)指針變量可以作為形參，可以作為函數(shù)返回值（如果一個函數(shù)的返回值是指針亦鳞，該函數(shù)被稱為.指針函數(shù)）

引用：<數(shù)據(jù)類型> &<引用名>=<變量名>馍忽，建立引用時必須用已經(jīng)知道的變量名對其初始化，所引用的對象初始化后不可修改燕差，對引用的操作與對所引用對象的操作效果完全一樣遭笋。指針變量聲明引用：<數(shù)據(jù)類型> *&<引用名>=<指針變量名>。

引用主要在函數(shù)中：1. 函數(shù)的形參聲明為引用徒探；2. 函數(shù)的返回類型聲明為引用

C++程序設(shè)計基礎(chǔ)（下）

拓展學(xué)習(xí)

STL及使用示例

算法設(shè)計基本方法與策略基礎(chǔ)

C++中的string類

排序算法

第一章 面向?qū)ο蠓椒?/h2>

對象瓦呼，類，實例测暗，消息央串，封裝，繼承偷溺，多態(tài)性蹋辅，聚合和組合

類把對象的靜態(tài)特征抽象成屬性（attribute），對象的動態(tài)特征抽象成方法（method）

對象之間只能通過消息進行通信

類中的變量用來描述對象的狀態(tài)（屬性）挫掏，這些變量被稱為數(shù)據(jù)成員（或成員數(shù)據(jù)）侦另；類中的函數(shù)用來描述對象的方法（行為），這些函數(shù)被稱為成員函數(shù)（或函數(shù)成員）

定義類的一般語法格式

class<自定義類類型名>
{
 [public:]
 [<公有成員說明表>]
 [private:]
 [<私有成員說明表>]
 [protected:]
 [<保護成員說明表>]
};

在C++中尉共，對象的初始化工作是由成員函數(shù)——構(gòu)造函數(shù)完成的褒傅，該函數(shù)在創(chuàng)建一個對象時被自動調(diào)用。構(gòu)造函數(shù)可以重載袄友，以滿足對象多樣性的初始化需要殿托；

構(gòu)造函數(shù)的特點：

• 構(gòu)造函數(shù)名必須與類名相同

• 構(gòu)造函數(shù)沒有任何函數(shù)返回類型，void也不行

• 任意一個新的對象被創(chuàng)建時剧蚣，編譯系統(tǒng)都會自動調(diào)用構(gòu)造函數(shù)支竹，完成對該對象數(shù)據(jù)成員的初始化工作

• 如果在類定義時沒有給出構(gòu)造函數(shù)，系統(tǒng)會自動提供一個默認(rèn)的無參構(gòu)造函數(shù)：<類名>(){}

定義對象的過程叫做類的實例化

一個對象創(chuàng)建以后鸠按，訪問它的數(shù)據(jù)成員或調(diào)用它的成員函數(shù)礼搁，可以通過兩種方式：a. 對象名+對象成員訪問符“.”；b.對象指針+箭頭成員訪問運算符“->”目尖。面向?qū)ο蠓椒ㄖ械南C制就是通過對象或指向?qū)ο蟮闹羔樥{(diào)用成員函數(shù)來實現(xiàn)的

C++通過三個關(guān)鍵字public（公有）馒吴，private（私有）以及protected（保護）來指定類成員的訪問控制，類成員的訪問控制實現(xiàn)了類的封裝性

• 公有成員：在程序的任何地方都可以被訪問。一般將公有成員限制在成員函數(shù)上饮戳，使其作為類與外界的接口豪治，程序通過這種函數(shù)來操作該類對象；

• 私有成員：只能被該類的成員函數(shù)或該類的友元函數(shù)訪問扯罐。程序必須通過類的公有成員才能間接地訪問類的私有成員负拟，從而實現(xiàn)了對類成員的封裝

• 保護成員：被聲明為protected（保護）訪問級別的數(shù)據(jù)成員或成員函數(shù)只能在該類的內(nèi)部或其派生類類體中使用

如果沒有指明訪問級別，C++編譯系統(tǒng)默認(rèn)為私有成員（private）

析構(gòu)函數(shù)：

• 析構(gòu)函數(shù)名為：~<類名>

• 析構(gòu)函數(shù)無任何函數(shù)返回類型說明

• 析構(gòu)函數(shù)無參數(shù)歹河，所以不能被重載

• 如果在類聲明中沒有給出析構(gòu)函數(shù)齿椅，系統(tǒng)會自動給出一個默認(rèn)的析構(gòu)函數(shù)：~<類名>(){}

• 當(dāng)對象的生命周期結(jié)束或用delete釋放動態(tài)對象時，系統(tǒng)自動調(diào)用析構(gòu)函數(shù)完成對象撤銷前的處理

析構(gòu)函數(shù)的功能不僅僅局限于釋放變量上启泣，類這記者可以利用析構(gòu)函數(shù)來執(zhí)行最后一次使用類對象后所做的任何操作

拷貝構(gòu)造函數(shù)的作用是用一個已經(jīng)存在的對象來初始化一個正在創(chuàng)建的新對象∈颈玻拷貝函數(shù)的特征有：

• 拷貝構(gòu)造函數(shù)名與類名相同寥茫，形參只有一個，是對象的引用（不能重載拷貝構(gòu)造函數(shù)）矾麻∩闯埽拷貝構(gòu)造函數(shù)的原形為<類名>(<類名> &對象名)

• 拷貝構(gòu)造函數(shù)無任何函數(shù)返回類型說明

• 如果在類聲明中沒有給出拷貝構(gòu)造函數(shù)，系統(tǒng)會自動給出一個默認(rèn)的拷貝構(gòu)造函數(shù)险耀，該拷貝構(gòu)造函數(shù)只進行對象數(shù)據(jù)成員間的對位拷貝弄喘，即“淺拷貝”

• 在某些情況下，用戶必須在類定義中給出一個顯式的拷貝構(gòu)造函數(shù)甩牺，以實現(xiàn)用戶指定的用一個對象初始化另一個對象的功能蘑志，即“深拷貝”

在以下三種情況下，系統(tǒng)會自動調(diào)用拷貝構(gòu)造函數(shù)：

1. 當(dāng)使用下面的聲明語句用一個已存在的對象初始化一個新對象時：<類名><新對象名>(<已存在對象名>)或<類名><新對象名>=<已存在對象名>

2. 對象作為實參贬派，在函數(shù)調(diào)用開始進行實參和形參結(jié)合時

3. 如果函數(shù)的返回值是類的對象急但，在函數(shù)調(diào)用完成返回時，系統(tǒng)自動調(diào)用拷貝構(gòu)造函數(shù)搞乏，用return后面的已知對象來初始化一個臨時新對象波桩；

淺拷貝中兩個指針指向同一個內(nèi)存空間，析構(gòu)時會造成內(nèi)存泄漏请敦，new 淺拷貝和深拷貝的區(qū)別镐躲？

類聲明與類實現(xiàn)分離：

類聲明：（.h）描述了類的結(jié)構(gòu)，包括類的所有數(shù)據(jù)成員侍筛，函數(shù)成員和友元

類實現(xiàn)：（.cpp）定義了成員函數(shù)的具體功能

在類的實現(xiàn)文件中萤皂，成員函數(shù)的定義形式：

<函數(shù)類型><類名>::<函數(shù)名>(<形參數(shù)表>)
{
 函數(shù)體
}

其中，“::”是作用域運算符勾笆，表示所定義的函數(shù)屬于哪個類

類的靜態(tài)成員的特點：

• 靜態(tài)成員屬于類敌蚜，不屬于任何對象

• 靜態(tài)成員函數(shù)不能訪問一般的數(shù)據(jù)成員，它只能訪問靜態(tài)數(shù)據(jù)成員窝爪，也只能調(diào)用其他的靜態(tài)成員函數(shù)

• 無論對象是否存在弛车，類的一個靜態(tài)數(shù)據(jù)成員都只有一個齐媒，存于公用內(nèi)存中，可被該類的所有對象共享

在創(chuàng)建對象時纷跛，會為對象的數(shù)據(jù)成員分配內(nèi)存空間喻括，但不會為該類的靜態(tài)數(shù)據(jù)成員分配存儲空間。所以贫奠，類設(shè)計者需要在類外對該類的靜態(tài)數(shù)據(jù)成員進行定義唬血，以獲得內(nèi)存空間。靜態(tài)數(shù)據(jù)成員的定義形式：<類名><類名>::<靜態(tài)數(shù)據(jù)成員名>[=<初值>]

a. 程序中唤崭，對靜態(tài)數(shù)據(jù)成員的聲明在類內(nèi)進行拷恨，對一個靜態(tài)數(shù)據(jù)成員的定義和初始化必須在類外進行，且只能出現(xiàn)一次

b. 靜態(tài)數(shù)據(jù)成員定義時前面不要加關(guān)鍵字static

c. 在多文件結(jié)構(gòu)中谢肾，靜態(tài)數(shù)據(jù)成員定義和初始化最恰當(dāng)?shù)牡胤酵笾叮菍⑺旁陬惖膶崿F(xiàn)文件中

如果類的成員函數(shù)聲明時被static修飾，他就是靜態(tài)成員函數(shù)芦疏。靜態(tài)成員函數(shù)是類中為外界提供的訪問私有靜態(tài)數(shù)據(jù)成員的接口冕杠。靜態(tài)成員函數(shù)不能訪問非靜態(tài)數(shù)據(jù)成員

類的公有靜態(tài)成員函數(shù)的訪問形式：<類名>::<靜態(tài)成員函數(shù)名>([實參])或<對象名>.<靜態(tài)成員函數(shù)名>([實參])或<對象指針>-><靜態(tài)成員函數(shù)名>([實參])

常量數(shù)據(jù)成員，const酸茴，在定義對象時通過構(gòu)造函數(shù)的成員初始化列表獲得初值（區(qū)別于符號常量在聲明時賦初值）分预，一旦對象被創(chuàng)建，常量數(shù)據(jù)成員的值不可修改

常量成員函數(shù)：有權(quán)讀取對象的數(shù)據(jù)成員薪捍，無權(quán)修改對象數(shù)據(jù)成員的值笼痹。聲明形式：<類型說明符><函數(shù)名>(<參數(shù)表>)const（const放在函數(shù)聲明的尾部，在類外定義時也要加上const）

this指針隱含于非靜態(tài)成員函數(shù)酪穿，為類指針類型的形參与倡，一般隱式使用，需要顯式使用的情況：a. 非靜態(tài)成員函數(shù)的形參名與對象的數(shù)據(jù)成員名相同時昆稿；b. 非靜態(tài)成員函數(shù)返回的是對象本身或?qū)ο蟮刂返臅r候

友元提供了一個一般函數(shù)與類的成員之間纺座、不同類的成員之間進行數(shù)據(jù)共享的機制

1. 友元函數(shù)：將普通函數(shù)聲明為友元函數(shù)：friend<數(shù)據(jù)類型><友元函數(shù)名>(參數(shù)表);

2. 友元成員：將一個類的成員函數(shù)聲明為另一個類的友元函數(shù)：friend<類型><含有友元成員的類名>::<友元成員名>(參數(shù)表);

3. 友類：將一個類聲明為另一個類的友類：friend <友類名>;或friend class <友類名>;

友元不可傳遞，類的友員函數(shù)不是本類的成員函數(shù)溉潭，訪問本類的成員時等同于一般的外部函數(shù)净响，使用對象名來訪問。

類的對象成員：

1. 一個類的對象是另一個類的成員喳瓣；

2. 一個類的成員函數(shù)是另一個類的友元馋贤；

3. 一個類定義在另一個類的說明中，即類嵌套畏陕；

4. 一個類作為另一個類的派生類配乓。

對象成員的聲明：類名<對象成員名表>；初始化調(diào)用構(gòu)造函數(shù)完成：<對象成員1>(<初值表>)[,...,<對象成員n>(<初值表>)]

自定義類的運算符重載：

1. 除了類屬運算符“.”，成員指針運算符“.*”犹芹，作用域運算符“::”崎页，sizeof運算符和三目運算符“?:”5中運算符外，其他的運算符都可以重載

2. 運算符重載限制在C++語言中已有的運算符范圍內(nèi)的允許重載的運算符之中腰埂，不能創(chuàng)建新的運算符

3. 運算符重載實質(zhì)上是函數(shù)重載飒焦，編譯程序?qū)\算符重載的選擇遵循函數(shù)重載的選擇原則

4. 重載之后的運算符不能改變運算符的優(yōu)先級和結(jié)合性，也不能改變運算符操作數(shù)的個數(shù)及語法結(jié)構(gòu)

5. 運算符重載是針對新類型數(shù)據(jù)的實際需要對原有運算符進行的適當(dāng)?shù)母脑煊炝剌d的功能應(yīng)當(dāng)與原有功能相類似

對于自定義類的運算符重載函數(shù)牺荠，大部分運算符可以將其定義為類的成員函數(shù)，也可以將其定義為類的非成員函數(shù)驴一，而非成員函數(shù)一般采用友元函數(shù)形式

成員函數(shù)形式的運算符函數(shù)定義的一般形式：（參數(shù)-1休雌，隱含this）

<返回類型說明符>operator<運算符符號>(<參數(shù)表>)
{
 <函數(shù)體>
}

類友元形式的運算符重載：類非成員函數(shù)形式的運算符重載函數(shù)一般采用友元函數(shù)，運算符重載為類的友元函數(shù)肝断，需要在類內(nèi)進行聲明挑辆，形式：friend<函數(shù)類型>operator<運算符>(<參數(shù)表>);，無隱含this孝情，所有操作數(shù)用過函數(shù)的形參進行傳遞，函數(shù)的參數(shù)與操作數(shù)自左至右一一對應(yīng)

重載為類的成員函數(shù)or友元函數(shù)規(guī)則：

1. 單目運算符→類的成員函數(shù)洒嗤；雙目運算符-→類的友元函數(shù)

2. 只能重載為類的成員函數(shù)的雙目運算符：=箫荡、()、[]渔隶、->

3. 若一個運算符的操作需要修改對象的姿態(tài)羔挡，重載為成員函數(shù)

4. 若運算符所需的操作數(shù)（尤其是第一個操作數(shù)）希望有隱式類型轉(zhuǎn)換，只能選用友元函數(shù)

5. 的運算符函數(shù)是一個成員函數(shù)時间唉，最左邊的操作數(shù)必須是運算符類的一個類對象（或?qū)υ擃悓ο蟮囊茫┙首啤Ｈ绻筮叺牟僮鲾?shù)必須是一個不同類的對象，或者是一個內(nèi)部類型的對象呈野，改運算符函數(shù)只能作為一個友元函數(shù)來實現(xiàn)

6. 當(dāng)需要重載運算符具有可交換性時低矮，選擇重載為友元函數(shù)

第二章 繼承與多態(tài)

派生類（子類）&基類（父類）

派生類會繼承基類中定義的所有屬性和方法，派生類也能夠在派生類中定義派生類特有的屬性和方法

定義派生類的語法：

class 派生類名:繼承方式 基類名
{
 派生類成員聲明;
};

繼承方式包括：public（公有繼承）被冒，protected（保護繼承）军掂，private（私有繼承）

派生類不能直接訪問從基類繼承下來的私有成員

在定義派生類時终议，可以指定的繼承方式為public（公有繼承），protected（保護繼承），private（私有繼承穴张，缺省方式）

派生類中函數(shù)重定義

派生類構(gòu)造函數(shù)的作用：主要是對派生類中新添加的數(shù)據(jù)成員做初始化工作细燎；在創(chuàng)建派生類對象，執(zhí)行派生類構(gòu)造函數(shù)時陆馁，系統(tǒng)會自動調(diào)用基類的構(gòu)造函數(shù)來對基類中定義的數(shù)據(jù)成員進行初始化

派生類析構(gòu)函數(shù)的作用：主要是清除派生類中新添加的數(shù)據(jù)成員找颓，釋放它們所占據(jù)的系統(tǒng)資源；在銷毀派生類對象叮贩、執(zhí)行派生類析構(gòu)函數(shù)是击狮，系統(tǒng)會自動調(diào)用積累的自構(gòu)函數(shù)來釋放基類中數(shù)據(jù)成員所占據(jù)的系統(tǒng)資源

派生類中構(gòu)造函數(shù)的定義：派生類名（形參列表）：基類名（實參列表）{ 派生類中數(shù)據(jù)成員的初始化}；無參：派生類名（形參列表）{ 派生類中數(shù)據(jù)成員的初始化}等價于派生類名（形參列表）：Person（）{ 派生類中數(shù)據(jù)成員的初始化}

派生類中析構(gòu)函數(shù)的定義形式與基類完全相同

C++基類中益老，不能被派生類繼承的有構(gòu)造函數(shù)和析構(gòu)函數(shù)彪蓬。

多繼承：

class 派生類名:繼承方式 基類名1,繼承方式 基類名2,...,繼承方式 基類名n,
{
 派生類成員聲明;
};

按繼承順序構(gòu)造，析構(gòu)函數(shù)的調(diào)用順序總是與構(gòu)造函數(shù)的調(diào)用順序相反

二義性：在定義派生類時捺萌，可以通過虛擬繼承方式將基類聲明為虛基類档冬。虛基類中的成員在類的繼承關(guān)系中只會被繼承一次，從而解決多重繼承中的二義性問題桃纯。virtual酷誓，最后需要顯式調(diào)用虛基類的構(gòu)造函數(shù)進行初始化

類型兼容是多態(tài)性的前提，指的是在基類對象可以出現(xiàn)的任何地方态坦，都可以用公有派生類的對象來替代：1. 可以用派生類對象為基類對象賦值盐数；2. 可以用派生類對象初始化基類引用；3. 可以用派生類對象地址為基類指針賦值

用派生類對象替代基類對象進行賦值操作后伞梯，通過基類對象玫氢、基類對象引用和基類指針只能訪問派生類從基類繼承的成員

通過類型兼容，對于基類及其公有派生類的對象谜诫，可以使用相同的函數(shù)統(tǒng)一進行處理漾峡。這種能夠根據(jù)指針或引用所表示的對象的實際類型來調(diào)用該對象所屬類的函數(shù)，而不是每次都調(diào)用基類中函數(shù)的特性喻旷，就是多態(tài)性

先期綁定（靜態(tài)綁定）&后期綁定（動態(tài)綁定）

C++通過虛函數(shù)實現(xiàn)“動態(tài)綁定”計數(shù)生逸。虛函數(shù)的聲明方法是在基類的函數(shù)聲明前或函數(shù)定義的函數(shù)頭前（無函數(shù)聲明時）加上virtual關(guān)鍵字，虛函數(shù)可以被繼承

只有使用基類的指針或引用調(diào)用虛函數(shù)時才能實現(xiàn)多態(tài)性且预。如果使用對象調(diào)用虛函數(shù)牺陶，則不具有多態(tài)性，必然是調(diào)用該對象所屬類的成員函數(shù)

抽象類：不能實例化辣之，唯一用途是為其他類提供合適的基類

純虛函數(shù)是在聲明時初始化為0的虛函數(shù)掰伸，一個類如果是抽象類，則該類至少有一個成員函數(shù)是純虛函數(shù)怀估，定義：virtual <函數(shù)類型>純虛函數(shù)名(<形參類型表>)=0

第三章 輸入輸出流

in.getline(字符數(shù)組名或字符型指針,字符個數(shù)n,終止標(biāo)識符)

“EOF”（end of file）文件結(jié)束符對應(yīng)于鍵盤組合鍵“Ctrl+Z”

打開文件使用文件流類的成員函數(shù)open（）狮鸭，函數(shù)原型為void open(const char* filename, int mode);

可以用位或運算符“|”連接以上屬性

一般將純文本內(nèi)容存儲在文本文件中，將數(shù)值型數(shù)據(jù)或含有數(shù)值結(jié)構(gòu)體數(shù)據(jù)存儲在二進制文件中

is_open()檢查文件是否打開成功催跪，返回一個bool锁蠕，為真表示打開成功，為假表示打開失敗懊蒸，close()關(guān)閉

輸出流類提供了用于輸出一個數(shù)據(jù)塊的成員函數(shù)write()，輸出流對象可以調(diào)用這個函數(shù)實現(xiàn)向輸出設(shè)備輸出指定個數(shù)的多個字符的操作舌仍，其有兩個參數(shù)通危，調(diào)用格式為：out.write(字符型指針铸豁，字節(jié)數(shù)a)相對應(yīng)的有read()，read()能夠讀取空白字符节芥，讀取指定個數(shù)字符而不是字符串框沟，最后不會自動加字符串結(jié)束符'\0'

文件的隨機讀寫seekg()&seekp()

istream&seekg(long offset,seek_dir origin=ios::beg);
ostream&seekp(long offset,seek_dir origin=ios::beg);

函數(shù)的功能是文件指針從參照位置origin開始移動offset個字節(jié)，取值為正表示向后（文件尾部）移動文件指針增炭，seek_dir為枚舉類型忍燥，有ios::beg：文件首隙姿；ios::cur：文件指針當(dāng)前位置；ios::end：文件尾三個枚舉常量

第四章 模板

模板就是參數(shù)化的函數(shù)或類队丝，面板式將數(shù)據(jù)類型作為參數(shù)欲鹏，根據(jù)數(shù)據(jù)類型參數(shù)產(chǎn)生函數(shù)和類的機制框杜，分為函數(shù)模板和類模板，模板是泛化編程的主要方法之一

模板關(guān)鍵字：template；模板參數(shù)：typename

實例化的函數(shù)模板稱為模板函數(shù)结缚，函數(shù)模板的實例化是在函數(shù)調(diào)用的時候由編譯器完成的

函數(shù)重載：可執(zhí)行不同代碼软棺；函數(shù)模板：相同代碼，處理數(shù)據(jù)類型不同

當(dāng)函數(shù)模板與一般函數(shù)同名時喘落，遵循：

• 一個函數(shù)調(diào)用首先尋找參數(shù)完全匹配一致的一般函數(shù)揖盘，如果找到就調(diào)用它

• 尋找一個函數(shù)模板，使其實例化憾股，生成一個匹配的模板函數(shù)箕慧，然后調(diào)用該模板函數(shù)

類模板的實例化需要在程序中顯式地指定

第五章 概論

數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。

數(shù)據(jù)的邏輯結(jié)構(gòu)&數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）&數(shù)據(jù)結(jié)構(gòu)的操作及實現(xiàn)

通常把數(shù)據(jù)元素之間的股有關(guān)系用前驅(qū)和后繼來描述

二元關(guān)系/圖形表示

邏輯結(jié)構(gòu)：

線性結(jié)構(gòu)：1. 有且僅有一個沒有前驅(qū)的節(jié)點斩熊，通常將該節(jié)點稱為根節(jié)點伐庭；2. 除了根節(jié)點沒有前驅(qū)，最后一個節(jié)點沒有后繼外霸株，其他每一個節(jié)點都有一個前驅(qū)和一個后繼；3. 線性結(jié)構(gòu)在插入或刪除任何一個節(jié)點后還是線性結(jié)構(gòu)

非線性結(jié)構(gòu)：一個節(jié)點可能有多個前驅(qū)和后繼：1. 樹狀結(jié)構(gòu)：一對多 2. 網(wǎng)狀結(jié)構(gòu)：關(guān)系任意集乔；3. 集合結(jié)構(gòu)：沒有關(guān)系

順序存儲結(jié)構(gòu)（緊湊存儲結(jié)構(gòu)）去件；鏈?zhǔn)酱鎯Y(jié)構(gòu)（頻繁插入刪除）；索引存儲結(jié)構(gòu)（索引表）尤溜；散列存儲結(jié)構(gòu)

基本操作：創(chuàng)建/清除/插入/刪除/訪問/更新/查找/排序

數(shù)據(jù)的操作.png

第六章 線性表

抽象數(shù)據(jù)類型（Abstract Data Type汗唱，ADT）

線性表的順序存儲結(jié)構(gòu)（順序表）特點：1. 線性表中所有元素所占的存儲空間是連續(xù)的哩罪；2. 線性表的邏輯順序與物理順序一致肥印；3. 數(shù)組中的每一個元素的位置可以用公式來確定

類模板的聲明和實現(xiàn)要放在同一個頭文件中

鏈?zhǔn)酱鎯Y(jié)構(gòu)：存儲節(jié)點=數(shù)據(jù)域＋指針域

頭文件：便于代碼復(fù)用

空表：循環(huán)列表head->next==head绝葡；單向鏈表：head->next==NULL

第七章 棧和隊列

棧（Stack）和隊列（Queue）：操作受限的線性表

棧：插入和操作都只能在標(biāo)的同一端藏畅，棧頂（表尾）：Top；棧底（表頭）：Bottom愉阎。當(dāng)棧中沒有元素時稱為空棧榜旦；插入元素——進棧（入棧）：push；刪除元素——退棧（出棧）：pop澡屡。先進后出（FILO）&后進先出（LIFO）下推表咐旧。上溢（Overflow）&下溢（Underflow）。順序棧&鏈接棧

隊列：入隊&出隊室埋；隊尾（rear）&隊頭（front）伊约；先進先出（FIFO）&后進后出（LILO）

順序隊列：頭指針指向隊頭元素，尾指針指向隊尾元素的下一個位置

循環(huán)隊列：避免假上溢front=(front+1)%(MaxSize)&rear=(rear+1)%(MaxSize)

判斷“空”或“滿”：1. 少用一個元素空間(rear+1)%(MaxSize)==front為滿腌逢，rear時鐘指向空閑元素空間疹尾；2. 采用計數(shù)器記錄隊列實際長度纳本，size==0為空腋颠。

第八章 樹和二叉樹

樹是由n（n≥0）個結(jié)點組成的有限集T，當(dāng)n=0時巾腕，稱為空樹；當(dāng)n＞0時叁鉴，滿足：1. 有且僅有一個沒有前驅(qū)的結(jié)點佛寿，該節(jié)點稱為樹的根節(jié)點；2. 將根節(jié)點去除后常侣，其余結(jié)點可分為m（m≥0）個互不相交的自己T1弹渔、T2肢专、...、Tm胆绊，其中每個子集Ti（i=1欧募，2，...种冬，m又是一棵樹娱两，并稱其為根的子樹）金吗。

表示方法：樹型圖、嵌套集合表示法旱物、凹入表表示法卫袒、廣義表表示法

一個結(jié)點后繼的數(shù)目稱為該結(jié)點的度，樹中各結(jié)點的最大值稱為樹的度宝穗；樹中各結(jié)點的層的最大值稱為樹的深度逮矛；從一個結(jié)點到其后繼結(jié)點之間的連線稱為一個分支，從一個結(jié)點X到另一個結(jié)點Y所經(jīng)歷的所有分支構(gòu)成結(jié)點X到結(jié)點Y的路徑膜蠢，一條路徑上的分支數(shù)目稱為路徑長度莉兰，從樹的根結(jié)點到其他各個結(jié)點的路徑長度之和稱為樹的路徑長度；樹中度為0的結(jié)點稱為葉子結(jié)點（或終端結(jié)點）杉辙，度不為0的結(jié)點稱為分支結(jié)點（或非終端結(jié)點）捶朵，除根結(jié)點以外的分支結(jié)點也成為內(nèi)部結(jié)點综看；在樹中，一個結(jié)點的后繼結(jié)點稱為該結(jié)點的孩子舞吭，相應(yīng)地析珊，一個結(jié)點的前驅(qū)結(jié)點稱為該結(jié)點的雙親；同一雙親的孩子結(jié)點之前互稱為兄弟惧浴，不同雙親但在同一層的結(jié)點之前互稱為堂兄弟衷旅；從樹的根結(jié)點到某一個結(jié)點X的路徑上經(jīng)歷的所有結(jié)點（包括根節(jié)點但不包括結(jié)點X）稱為結(jié)點X的祖先纵朋，以某一結(jié)點X為根的子樹上的所有非根節(jié)點（即除結(jié)點X外）稱為結(jié)點X的子孫；對于樹中任一結(jié)點九串，如果其各棵子樹的相對次序被用來表示數(shù)據(jù)之間的關(guān)系寺鸥，即交換子樹位置會改變樹所表示的內(nèi)容胆建，則稱該樹為有序樹，否則稱為無序樹扑馁；m（m≥0）棵互不相交的樹的集合就構(gòu)成了森林凉驻；

二叉樹的定義.png

二叉樹是每個結(jié)點的度小于等于2的有序樹

順序編號法：自上而下自左至右

滿二叉樹是指除了最后一層的結(jié)點為葉子結(jié)點外其他結(jié)點都有左涝登、右兩棵子樹的二叉樹；完全二叉樹是指其結(jié)點與相同深度的滿二叉樹中的結(jié)點編號完全一致的二叉樹趟济；對于深度為k的完全二叉樹咽笼，其前k-1層與深度為k的滿二叉樹的前k-1層完全一致剑刑，只是在第k層上有可能缺少右邊若干個結(jié)點。滿二叉樹必然是完全二叉樹层宫，而完全二叉樹不一定是滿二叉樹其监。

二叉樹的基本性質(zhì)：

1. 在二叉樹的第i層上至多有?個結(jié)點

2. 深度為k的二叉樹至多有?個結(jié)點

3. 在二叉樹中抖苦，若度為0的結(jié)點（即葉子結(jié)點）數(shù)為?，度為2的結(jié)點數(shù)為?贮庞，則?

   • 結(jié)點總數(shù)：入?究西；出：?

4. 具有n個結(jié)點的完全二叉樹其深度為?（其中?表示不大于?的最大整數(shù)）

5. 對于采用順序編號的完全二叉樹

   1. 若一個分支節(jié)點的編號為i，則其左子樹的根節(jié)點（即左孩子結(jié)點）編號為2i遮斥，右子樹的根節(jié)點（即有孩子結(jié)點）編號為2i+1

   2. 若一個非根節(jié)點的編號為i术吗，則其雙親節(jié)點的編號為?（其中?表示不大于i/2的最大整數(shù)）

二叉樹的順序表示適用于完全二叉樹而不適用于非完全二叉樹（空間利用效率較低）

二叉樹的鏈?zhǔn)奖硎荆憾骀湵肀硎痉椒?code>leftchild+data+rightchild；三叉鏈表表示leftchild+data+parent+rightchild

二叉樹的遍歷隧魄，就是按照某種規(guī)則依次訪問二叉樹中的每個結(jié)點隘蝎，且每個結(jié)點僅被訪問一次嘱么。根據(jù)節(jié)點訪問順序上的不同，有四種常用的遍歷方式：先序遍歷辉川、中序遍歷拴测、后序遍歷和逐層遍歷

在先序中序和后序遍歷時均先訪問左子樹后訪問右子樹集索，遍歷方式以根的先后為準(zhǔn)

二叉樹的中序遍歷二叉鏈表的實現(xiàn)既可采用非遞歸方式，也可采用遞歸方式妆距。 根據(jù)二叉樹的先序遍歷序列可以確定二叉樹的根結(jié)點函匕，根據(jù)二叉樹的中序遍歷序列并不能確定二叉樹的根結(jié)點，已知一棵二叉樹的先序遍歷序列和中序遍歷序列可以唯一地構(gòu)造出該二叉樹中剩。

二叉排序樹结啼，又稱二叉查找樹屈芜，它或者是一棵空樹朴译，或者是具有如下性質(zhì)的二叉樹：

• 若它的左子樹非空眠寿，則左子樹上所有結(jié)點的值均小于根結(jié)點的值

• 若它的右子樹非空红选，則右子樹上所有結(jié)點的值均大于根結(jié)點的值

• 左喇肋、右子樹也分別是二叉排序樹

其中序遍歷有序

平衡二叉查找樹

哈夫曼樹（最優(yōu)二叉樹）：具有最短帶權(quán)路徑長度

第九章 圖

頂點V（G）和E（G）

有向圖：有向邊<弧>&無向圖：無向邊(邊)

無向圖中與頂點?相關(guān)聯(lián)的邊的數(shù)目稱為頂點?的度迹辐；有向圖中頂點?的入度和出度之和為有向圖的度

路徑明吩，一條路徑中邊的數(shù)目稱為路徑長度在一條路徑中，若一個頂點至多只經(jīng)過一次低葫，則該路徑稱為簡單路徑仍律；若組成路徑的頂點序列中第一個頂點與最后一個頂點相同水泉，則該路徑稱為回路（或環(huán)），簡單回路/簡單環(huán)钢拧；若任意兩個頂點都是連通的：連通圖炕横，單向連通/強連通份殿，子圖/連通分量/強連通分量極大連通子圖，極大指向連通子圖或強連通子圖中再添加一個頂點呻此，該子圖就不再連通或強連通腔寡；權(quán)/帶權(quán)圖；生成樹/最小生成樹：只有連通圖才有生成樹忿磅，邊上的權(quán)最小的生成樹稱為最小生成樹

圖的表示：鄰接矩陣葱她、鄰接壓縮表和鄰接鏈表

廣度優(yōu)先算法：逐層遍歷；深度優(yōu)先算法：先序遍歷