本文是：五萬字長文:C/C++ 面試知識總結(jié)（上）的續(xù)篇

C++ 11

1. shared_ptr

2. unique_ptr

3. weak_ptr

4. auto_ptr（被 C++11 棄用）

• Class shared_ptr 實現(xiàn)共享式擁有（shared ownership）概念。多個智能指針指向相同對象，該對象和其相關(guān)資源會在 “最后一個 reference 被銷毀” 時被釋放。為了在結(jié)構(gòu)較復(fù)雜的情景中執(zhí)行上述工作，標(biāo)準(zhǔn)庫提供 weak_ptr、bad_weak_ptr 和 enable_shared_from_this 等輔助類。

• Class unique_ptr 實現(xiàn)獨(dú)占式擁有（exclusive ownership）或嚴(yán)格擁有（strict ownership）概念，保證同一時間內(nèi)只有一個智能指針可以指向該對象。你可以移交擁有權(quán)。它對于避免內(nèi)存泄漏（resource leak）——如 new 后忘記 delete ——特別有用。

shared_ptr

多個智能指針可以共享同一個對象，對象的最末一個擁有著有責(zé)任銷毀對象，并清理與該對象相關(guān)的所有資源。

• 支持定制型刪除器（custom deleter），可防范 Cross-DLL 問題（對象在動態(tài)鏈接庫（DLL）中被 new 創(chuàng)建，卻在另一個 DLL 內(nèi)被 delete 銷毀）、自動解除互斥鎖

weak_ptr

weak_ptr 允許你共享但不擁有某對象，一旦最末一個擁有該對象的智能指針失去了所有權(quán)，任何 weak_ptr 都會自動成空（empty）。因此，在 default 和 copy 構(gòu)造函數(shù)之外，weak_ptr 只提供 “接受一個 shared_ptr” 的構(gòu)造函數(shù)。

• 可打破環(huán)狀引用（cycles of references，兩個其實已經(jīng)沒有被使用的對象彼此互指，使之看似還在 “被使用” 的狀態(tài)）的問題

unique_ptr

unique_ptr 是 C++11 才開始提供的類型，是一種在異常時可以幫助避免資源泄漏的智能指針。采用獨(dú)占式擁有，意味著可以確保一個對象和其相應(yīng)的資源同一時間只被一個 pointer 擁有。一旦擁有著被銷毀或編程 empty，或開始擁有另一個對象，先前擁有的那個對象就會被銷毀，其任何相應(yīng)資源亦會被釋放。

• unique_ptr 用于取代 auto_ptr

auto_ptr

被 c++11 棄用，原因是缺乏語言特性如 “針對構(gòu)造和賦值” 的 std::move 語義，以及其他瑕疵。

auto_ptr 與 unique_ptr 比較

• auto_ptr 可以賦值拷貝，復(fù)制拷貝后所有權(quán)轉(zhuǎn)移；unqiue_ptr 無拷貝賦值語義，但實現(xiàn)了move 語義；

• auto_ptr 對象不能管理數(shù)組（析構(gòu)調(diào)用 delete），unique_ptr 可以管理數(shù)組（析構(gòu)調(diào)用 delete[] ）；

強(qiáng)制類型轉(zhuǎn)換運(yùn)算符

MSDN . 強(qiáng)制轉(zhuǎn)換運(yùn)算符：http://t.cn/E4WIt5W

static_cast

• 用于非多態(tài)類型的轉(zhuǎn)換

• 不執(zhí)行運(yùn)行時類型檢查（轉(zhuǎn)換安全性不如 dynamic_cast）

• 通常用于轉(zhuǎn)換數(shù)值數(shù)據(jù)類型（如 float -> int）

• 可以在整個類層次結(jié)構(gòu)中移動指針，子類轉(zhuǎn)化為父類安全（向上轉(zhuǎn)換），父類轉(zhuǎn)化為子類不安全（因為子類可能有不在父類的字段或方法）

向上轉(zhuǎn)換是一種隱式轉(zhuǎn)換。

dynamic_cast

• 用于多態(tài)類型的轉(zhuǎn)換

• 執(zhí)行行運(yùn)行時類型檢查

• 只適用于指針或引用

• 對不明確的指針的轉(zhuǎn)換將失?。ǚ祷?nullptr），但不引發(fā)異常

• 可以在整個類層次結(jié)構(gòu)中移動指針，包括向上轉(zhuǎn)換、向下轉(zhuǎn)換

const_cast

• 用于刪除 const、volatile 和 __unaligned 特性（如將 const int 類型轉(zhuǎn)換為 int 類型 ）

reinterpret_cast

• 用于位的簡單重新解釋

• 濫用 reinterpret_cast 運(yùn)算符可能很容易帶來風(fēng)險。 除非所需轉(zhuǎn)換本身是低級別的，否則應(yīng)使用其他強(qiáng)制轉(zhuǎn)換運(yùn)算符之一。

• 允許將任何指針轉(zhuǎn)換為任何其他指針類型（如 char* 到 int* 或 One_class* 到 Unrelated_class* 之類的轉(zhuǎn)換，但其本身并不安全）

• 也允許將任何整數(shù)類型轉(zhuǎn)換為任何指針類型以及反向轉(zhuǎn)換。

• reinterpret_cast 運(yùn)算符不能丟掉 const、volatile 或 __unaligned 特性。

• reinterpret_cast 的一個實際用途是在哈希函數(shù)中，即，通過讓兩個不同的值幾乎不以相同的索引結(jié)尾的方式將值映射到索引。

bad_cast

• 由于強(qiáng)制轉(zhuǎn)換為引用類型失敗，dynamic_cast 運(yùn)算符引發(fā) bad_cast 異常。

bad_cast 使用

try {  
    Circle& ref_circle = dynamic_cast<Circle&>(ref_shape);   
}  
catch (bad_cast b) {  
    cout << "Caught: " << b.what();  
} 

運(yùn)行時類型信息 (RTTI)

dynamic_cast

• 用于多態(tài)類型的轉(zhuǎn)換

typeid

• typeid 運(yùn)算符允許在運(yùn)行時確定對象的類型

• type_id 返回一個 type_info 對象的引用

• 如果想通過基類的指針獲得派生類的數(shù)據(jù)類型，基類必須帶有虛函數(shù)

• 只能獲取對象的實際類型

type_info

• type_info 類描述編譯器在程序中生成的類型信息。 此類的對象可以有效存儲指向類型的名稱的指針。 type_info 類還可存儲適合比較兩個類型是否相等或比較其排列順序的編碼值。 類型的編碼規(guī)則和排列順序是未指定的，并且可能因程序而異。

• 頭文件：typeinfo

typeid、type_info 使用

class Flyable                       // 能飛的
{
public:
    virtual void takeoff() = 0;     // 起飛
    virtual void land() = 0;        // 降落
};
class Bird : public Flyable         // 鳥
{
public:
    void foraging() {...}           // 覓食
    virtual void takeoff() {...}
    virtual void land() {...}
};
class Plane : public Flyable        // 飛機(jī)
{
public:
    void carry() {...}              // 運(yùn)輸
    virtual void take off() {...}
    virtual void land() {...}
};

class type_info
{
public:
    const char* name() const;
    bool operator == (const type_info & rhs) const;
    bool operator != (const type_info & rhs) const;
    int before(const type_info & rhs) const;
    virtual ~type_info();
private:
    ...
};

class doSomething(Flyable *obj)                 // 做些事情
{
    obj->takeoff();

    cout << typeid(*obj).name() << endl;        // 輸出傳入對象類型（"class Bird" or "class Plane"）

    if(typeid(*obj) == typeid(Bird))            // 判斷對象類型
    {
        Bird *bird = dynamic_cast<Bird *>(obj); // 對象轉(zhuǎn)化
        bird->foraging();
    }

    obj->land();
};

Effective C++

1. 視 C++ 為一個語言聯(lián)邦（C、Object-Oriented C++、Template C++、STL）

2. 寧可以編譯器替換預(yù)處理器（盡量以 const、enum、inline 替換 #define）

3. 盡可能使用 const

4. 確定對象被使用前已先被初始化（構(gòu)造時賦值（copy 構(gòu)造函數(shù)）比 default 構(gòu)造后賦值（copy assignment）效率高）

5. 了解 C++ 默默編寫并調(diào)用哪些函數(shù)（編譯器暗自為 class 創(chuàng)建 default 構(gòu)造函數(shù)、copy 構(gòu)造函數(shù)、copy assignment 操作符、析構(gòu)函數(shù)）

6. 若不想使用編譯器自動生成的函數(shù)，就應(yīng)該明確拒絕（將不想使用的成員函數(shù)聲明為 private，并且不予實現(xiàn)）

7. 為多態(tài)基類聲明 virtual 析構(gòu)函數(shù)（如果 class 帶有任何 virtual 函數(shù)，它就應(yīng)該擁有一個 virtual 析構(gòu)函數(shù)）

8. 別讓異常逃離析構(gòu)函數(shù)（析構(gòu)函數(shù)應(yīng)該吞下不傳播異常，或者結(jié)束程序，而不是吐出異常；如果要處理異常應(yīng)該在非析構(gòu)的普通函數(shù)處理）

9. 絕不在構(gòu)造和析構(gòu)過程中調(diào)用 virtual 函數(shù)（因為這類調(diào)用從不下降至 derived class）

10. 令 operator= 返回一個 reference to *this （用于連鎖賦值）

11. 在 operator= 中處理 “自我賦值”

12. 賦值對象時應(yīng)確保復(fù)制 “對象內(nèi)的所有成員變量” 及 “所有 base class 成分”（調(diào)用基類復(fù)制構(gòu)造函數(shù)）

13. 以對象管理資源（資源在構(gòu)造函數(shù)獲得，在析構(gòu)函數(shù)釋放，建議使用智能指針，資源取得時機(jī)便是初始化時機(jī)（Resource Acquisition Is Initialization，RAII））

14. 在資源管理類中小心 copying 行為（普遍的 RAII class copying 行為是：抑制 copying、引用計數(shù)、深度拷貝、轉(zhuǎn)移底部資源擁有權(quán)（類似 auto_ptr））

15. 在資源管理類中提供對原始資源（raw resources）的訪問（對原始資源的訪問可能經(jīng)過顯式轉(zhuǎn)換或隱式轉(zhuǎn)換，一般而言顯示轉(zhuǎn)換比較安全，隱式轉(zhuǎn)換對客戶比較方便）

16. 成對使用 new 和 delete 時要采取相同形式（new 中使用 [] 則 delete []，new 中不使用 [] 則 delete）

17. 以獨(dú)立語句將 newed 對象存儲于（置入）智能指針（如果不這樣做，可能會因為編譯器優(yōu)化，導(dǎo)致難以察覺的資源泄漏）

18. 讓接口容易被正確使用，不易被誤用（促進(jìn)正常使用的辦法：接口的一致性、內(nèi)置類型的行為兼容；阻止誤用的辦法：建立新類型，限制類型上的操作，約束對象值、消除客戶的資源管理責(zé)任）

19. 設(shè)計 class 猶如設(shè)計 type，需要考慮對象創(chuàng)建、銷毀、初始化、賦值、值傳遞、合法值、繼承關(guān)系、轉(zhuǎn)換、一般化等等。

20. 寧以 pass-by-reference-to-const 替換 pass-by-value （前者通常更高效、避免切割問題（slicing problem），但不適用于內(nèi)置類型、STL迭代器、函數(shù)對象）

21. 必須返回對象時，別妄想返回其 reference（絕不返回 pointer 或 reference 指向一個 local stack 對象，或返回 reference 指向一個 heap-allocated 對象，或返回 pointer 或 reference 指向一個 local static 對象而有可能同時需要多個這樣的對象。）

22. 將成員變量聲明為 private（為了封裝、一致性、對其讀寫精確控制等）

23. 寧以 non-member、non-friend 替換 member 函數(shù)（可增加封裝性、包裹彈性（packaging flexibility）、機(jī)能擴(kuò)充性）

24. 若所有參數(shù)（包括被this指針?biāo)傅哪莻€隱喻參數(shù)）皆須要類型轉(zhuǎn)換，請為此采用 non-member 函數(shù)

25. 考慮寫一個不拋異常的 swap 函數(shù)

26. 盡可能延后變量定義式的出現(xiàn)時間（可增加程序清晰度并改善程序效率）

27. 盡量少做轉(zhuǎn)型動作（舊式：(T)expression、T(expression)；新式：const_cast(expression)、dynamic_cast(expression)、reinterpret_cast(expression)、static_cast(expression)；盡量避免轉(zhuǎn)型、注重效率避免 dynamic_casts、盡量設(shè)計成無需轉(zhuǎn)型、可把轉(zhuǎn)型封裝成函數(shù)、寧可用新式轉(zhuǎn)型）

28. 避免使用 handles（包括 引用、指針、迭代器）指向?qū)ο髢?nèi)部（以增加封裝性、使 const 成員函數(shù)的行為更像 const、降低 “虛吊號碼牌”（dangling handles，如懸空指針等）的可能性）

29. 為 “異常安全” 而努力是值得的（異常安全函數(shù)（Exception-safe functions）即使發(fā)生異常也不會泄露資源或允許任何數(shù)據(jù)結(jié)構(gòu)敗壞，分為三種可能的保證：基本型、強(qiáng)列型、不拋異常型）

30. 透徹了解 inlining 的里里外外（inlining 在大多數(shù) C++ 程序中是編譯期的行為；inline 函數(shù)是否真正 inline，取決于編譯器；大部分編譯器拒絕太過復(fù)雜（如帶有循環(huán)或遞歸）的函數(shù) inlining，而所有對 virtual 函數(shù)的調(diào)用（除非是最平淡無奇的）也都會使 inlining 落空；inline 造成的代碼膨脹可能帶來效率損失；inline 函數(shù)無法隨著程序庫的升級而升級）

31. 將文件間的編譯依存關(guān)系降至最低（如果使用 object references 或 object pointers 可以完成任務(wù)，就不要使用 objects；如果能過夠，盡量以 class 聲明式替換 class 定義式；為聲明式和定義式提供不同的頭文件）

32. 確定你的 public 繼承塑模出 is-a（是一種）關(guān)系（適用于 base classes 身上的每一件事情一定適用于 derived classes 身上，因為每一個 derived class 對象也都是一個 base class 對象）

33. 避免遮掩繼承而來的名字（可使用 using 聲明式或轉(zhuǎn)交函數(shù)（forwarding functions）來讓被遮掩的名字再見天日）

34. 區(qū)分接口繼承和實現(xiàn)繼承（在 public 繼承之下，derived classes 總是繼承 base class 的接口；pure virtual 函數(shù)只具體指定接口繼承；非純 impure virtual 函數(shù)具體指定接口繼承及缺省實現(xiàn)繼承；non-virtual 函數(shù)具體指定接口繼承以及強(qiáng)制性實現(xiàn)繼承）

35. 考慮 virtual 函數(shù)以外的其他選擇（如 Template Method 設(shè)計模式的 non-virtual interface（NVI）手法，將 virtual 函數(shù)替換為 “函數(shù)指針成員變量”，以 tr1::function成員變量替換 virtual 函數(shù)，將繼承體系內(nèi)的 virtual 函數(shù)替換為另一個繼承體系內(nèi)的 virtual 函數(shù)）

36. 絕不重新定義繼承而來的 non-virtual 函數(shù)

37. 絕不重新定義繼承而來的缺省參數(shù)值，因為缺省參數(shù)值是靜態(tài)綁定（statically bound），而 virtual 函數(shù)卻是動態(tài)綁定（dynamically bound）

38. 通過復(fù)合塑模 has-a（有一個）或 “根據(jù)某物實現(xiàn)出”（在應(yīng)用域（application domain），復(fù)合意味 has-a（有一個）；在實現(xiàn)域（implementation domain），復(fù)合意味著 is-implemented-in-terms-of（根據(jù)某物實現(xiàn)出））

39. 明智而審慎地使用 private 繼承（private 繼承意味著 is-implemented-in-terms-of（根據(jù)某物實現(xiàn)出），盡可能使用復(fù)合，當(dāng) derived class 需要訪問 protected base class 的成員，或需要重新定義繼承而來的時候 virtual 函數(shù)，或需要 empty base 最優(yōu)化時，才使用 private 繼承）

40. 明智而審慎地使用多重繼承（多繼承比單一繼承復(fù)雜，可能導(dǎo)致新的歧義性，以及對 virtual 繼承的需要，但確有正當(dāng)用途，如 “public 繼承某個 interface class” 和 “private 繼承某個協(xié)助實現(xiàn)的 class”；virtual 繼承可解決多繼承下菱形繼承的二義性問題，但會增加大小、速度、初始化及賦值的復(fù)雜度等等成本）

41. 了解隱式接口和編譯期多態(tài)（class 和 templates 都支持接口（interfaces）和多態(tài)（polymorphism）；class 的接口是以簽名為中心的顯式的（explicit），多態(tài)則是通過 virtual 函數(shù)發(fā)生于運(yùn)行期；template 的接口是奠基于有效表達(dá)式的隱式的（implicit），多態(tài)則是通過 template 具現(xiàn)化和函數(shù)重載解析（function overloading resolution）發(fā)生于編譯期）

42. 了解 typename 的雙重意義（聲明 template 類型參數(shù)是，前綴關(guān)鍵字 class 和 typename 的意義完全相同；請使用關(guān)鍵字 typename 標(biāo)識嵌套從屬類型名稱，但不得在基類列（base class lists）或成員初值列（member initialization list）內(nèi)以它作為 basee class 修飾符）

43. 學(xué)習(xí)處理模板化基類內(nèi)的名稱（可在 derived class templates 內(nèi)通過 this-> 指涉 base class templates 內(nèi)的成員名稱，或藉由一個明白寫出的 “base class 資格修飾符” 完成）

44. 將與參數(shù)無關(guān)的代碼抽離 templates（因類型模板參數(shù)（non-type template parameters）而造成代碼膨脹往往可以通過函數(shù)參數(shù)或 class 成員變量替換 template 參數(shù)來消除；因類型參數(shù)（type parameters）而造成的代碼膨脹往往可以通過讓帶有完全相同二進(jìn)制表述（binary representations）的實現(xiàn)類型（instantiation types）共享實現(xiàn)碼）

45. 運(yùn)用成員函數(shù)模板接受所有兼容類型（請使用成員函數(shù)模板（member function templates）生成 “可接受所有兼容類型” 的函數(shù)；聲明 member templates 用于 “泛化 copy 構(gòu)造” 或 “泛化 assignment 操作” 時還需要聲明正常的 copy 構(gòu)造函數(shù)和 copy assignment 操作符）

46. 需要類型轉(zhuǎn)換時請為模板定義非成員函數(shù)（當(dāng)我們編寫一個 class template，而它所提供之 “與此 template 相關(guān)的” 函數(shù)支持 “所有參數(shù)之隱式類型轉(zhuǎn)換” 時，請將那些函數(shù)定義為 “class template 內(nèi)部的 friend 函數(shù)”）

47. 請使用 traits classes 表現(xiàn)類型信息（traits classes 通過 templates 和 “templates 特化” 使得 “類型相關(guān)信息” 在編譯期可用，通過重載技術(shù)（overloading）實現(xiàn)在編譯期對類型執(zhí)行 if…else 測試）

48. 認(rèn)識 template 元編程（模板元編程（TMP，template metaprogramming）可將工作由運(yùn)行期移往編譯期，因此得以實現(xiàn)早期錯誤偵測和更高的執(zhí)行效率；TMP 可被用來生成 “給予政策選擇組合”（based on combinations of policy choices）的客戶定制代碼，也可用來避免生成對某些特殊類型并不適合的代碼）

49. 了解 new-handler 的行為（set_new_handler 允許客戶指定一個在內(nèi)存分配無法獲得滿足時被調(diào)用的函數(shù)；nothrow new 是一個頗具局限的工具，因為它只適用于內(nèi)存分配（operator new），后繼的構(gòu)造函數(shù)調(diào)用還是可能拋出異常）

Google C++ Style Guide

英文：Google C++ Style Guide ：http://t.cn/RqhluJP

中文：C++ 風(fēng)格指南：http://t.cn/ELDTnur

Google C++ Style Guide 圖

STL

STL 索引

STL 方法含義索引：http://t.cn/E4WMXXs

STL 容器

STL 算法

STL 算法

http://t.cn/aEv0DV

數(shù)據(jù)結(jié)構(gòu)

順序結(jié)構(gòu)

順序棧（Sequence Stack）

SqStack.cpp：http://t.cn/E4WxO0b

順序棧數(shù)據(jù)結(jié)構(gòu)和圖片

typedef struct {
    ElemType *elem;
    int top;
    int size;
    int increment;
} SqSrack;

隊列（Sequence Queue）

隊列數(shù)據(jù)結(jié)構(gòu)

typedef struct {
    ElemType * elem;
    int front;
    int rear;
    int maxSize;
}SqQueue;

非循環(huán)隊列

非循環(huán)隊列圖片

SqQueue.rear++

循環(huán)隊列

循環(huán)隊列圖片

SqQueue.rear = (SqQueue.rear + 1) % SqQueue.maxSize

順序表（Sequence List）

SqList.cpp

順序表數(shù)據(jù)結(jié)構(gòu)和圖片

typedef struct {
    ElemType *elem;
    int length;
    int size;
    int increment;
} SqList;

鏈?zhǔn)浇Y(jié)構(gòu)

LinkList.cpp

LinkList_with_head.cpp

鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList; 

鏈隊列（Link Queue）

鏈隊列圖片

線性表的鏈?zhǔn)奖硎?/h4>

單鏈表（Link List）

單鏈表圖片

雙向鏈表（Du-Link-List）

雙向鏈表圖片

循環(huán)鏈表（Cir-Link-List）

循環(huán)鏈表圖片

哈希表

HashTable.cpp

概念

哈希函數(shù)：H(key): K -> D , key ∈ K

構(gòu)造方法

• 直接定址法

• 除留余數(shù)法

• 數(shù)字分析法

• 折疊法

• 平方取中法

沖突處理方法

• 鏈地址法：key 相同的用單鏈表鏈接

• 開放定址法

• 線性探測法：key 相同 -> 放到 key 的下一個位置，Hi = (H(key) + i) % m

• 二次探測法：key 相同 -> 放到 Di = 1^2, -1^2, …, ±（k)^2,(k<=m/2）

• 隨機(jī)探測法：H = (H(key) + 偽隨機(jī)數(shù)) % m

線性探測的哈希表數(shù)據(jù)結(jié)構(gòu)

線性探測的哈希表數(shù)據(jù)結(jié)構(gòu)和圖片

typedef char KeyType;

typedef struct {
    KeyType key;
}RcdType;

typedef struct {
    RcdType *rcd;
    int size;
    int count;
    bool *tag;
}HashTable;

遞歸

概念

函數(shù)直接或間接地調(diào)用自身

遞歸與分治

• 分治法

• 問題的分解

• 問題規(guī)模的分解

• 折半查找（遞歸）

• 歸并查找（遞歸）

• 快速排序（遞歸）

遞歸與迭代

• 迭代：反復(fù)利用變量舊值推出新值

• 折半查找（迭代）

• 歸并查找（迭代）

廣義表

頭尾鏈表存儲表示

廣義表的頭尾鏈表存儲表示和圖片

// 廣義表的頭尾鏈表存儲表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode {
    ElemTag tag;
    // 公共部分，用于區(qū)分原子結(jié)點和表結(jié)點
    union {
        // 原子結(jié)點和表結(jié)點的聯(lián)合部分
        AtomType atom;
        // atom 是原子結(jié)點的值域，AtomType 由用戶定義
        struct {
            struct GLNode *hp, *tp;
        } ptr;
        // ptr 是表結(jié)點的指針域，prt.hp 和 ptr.tp 分別指向表頭和表尾
    } a;
} *GList, GLNode;

擴(kuò)展線性鏈表存儲表示

擴(kuò)展線性鏈表存儲表示和圖片

// 廣義表的擴(kuò)展線性鏈表存儲表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode1 {
    ElemTag tag;
    // 公共部分，用于區(qū)分原子結(jié)點和表結(jié)點
    union {
        // 原子結(jié)點和表結(jié)點的聯(lián)合部分
        AtomType atom; // 原子結(jié)點的值域
        struct GLNode1 *hp; // 表結(jié)點的表頭指針
    } a;
    struct GLNode1 *tp;
    // 相當(dāng)于線性鏈表的 next，指向下一個元素結(jié)點
} *GList1, GLNode1;

二叉樹

BinaryTree.cpp

性質(zhì)

1. 非空二叉樹第 i 層最多 2^(i-1) 個結(jié)點 （i >= 1）

2. 深度為 k 的二叉樹最多 2^k - 1 個結(jié)點 （k >= 1）

3. 度為 0 的結(jié)點數(shù)為 n₀，度為 2 的結(jié)點數(shù)為 n₂，則 n₀ = n₂ + 1

4. 有 n 個結(jié)點的完全二叉樹深度 k = ? log₂(n) ? + 1

5. 對于含 n 個結(jié)點的完全二叉樹中編號為 i （1 <= i <= n） 的結(jié)點

6. 若 i = 1，為根，否則雙親為 ? i / 2 ?

7. 若 2i > n，則 i 結(jié)點沒有左孩子，否則孩子編號為 2i

8. 若 2i + 1 > n，則 i 結(jié)點沒有右孩子，否則孩子編號為 2i + 1

存儲結(jié)構(gòu)

二叉樹數(shù)據(jù)結(jié)構(gòu)

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

順序存儲

二叉樹順序存儲圖片

鏈?zhǔn)酱鎯?/h5>

二叉樹鏈?zhǔn)酱鎯D片

遍歷方式

• 先序遍歷

• 中序遍歷

• 后續(xù)遍歷

• 層次遍歷

分類

• 滿二叉樹

• 完全二叉樹（堆）

• 大頂堆：根 >= 左 && 根 >= 右

• 小頂堆：根 <= 左 && 根 <= 右

• 二叉查找樹（二叉排序樹）：左 < 根 < 右

• 平衡二叉樹（AVL樹）：| 左子樹樹高 - 右子樹樹高 | <= 1

• 最小失衡樹：平衡二叉樹插入新結(jié)點導(dǎo)致失衡的子樹：調(diào)整：

• LL型：根的左孩子右旋

• RR型：根的右孩子左旋

• LR型：根的左孩子左旋，再右旋

• RL型：右孩子的左子樹，先右旋，再左旋

其他樹及森林

樹的存儲結(jié)構(gòu)

• 雙親表示法

• 雙親孩子表示法

• 孩子兄弟表示法

并查集

一種不相交的子集所構(gòu)成的集合 S = {S1, S2, …, Sn}

平衡二叉樹（AVL樹）

性質(zhì)

• | 左子樹樹高 - 右子樹樹高 | <= 1

• 平衡二叉樹必定是二叉搜索樹，反之則不一定

• 最小二叉平衡樹的節(jié)點的公式：F(n)=F(n-1)+F(n-2)+1 （1 是根節(jié)點，F(xiàn)(n-1) 是左子樹的節(jié)點數(shù)量，F(xiàn)(n-2) 是右子樹的節(jié)點數(shù)量）

平衡二叉樹圖片

最小失衡樹

平衡二叉樹插入新結(jié)點導(dǎo)致失衡的子樹

調(diào)整：

• LL 型：根的左孩子右旋

• RR 型：根的右孩子左旋

• LR 型：根的左孩子左旋，再右旋

• RL 型：右孩子的左子樹，先右旋，再左旋

紅黑樹

紅黑樹的特征是什么？

1. 節(jié)點是紅色或黑色。

2. 根是黑色。

3. 所有葉子都是黑色（葉子是 NIL 節(jié)點）。

4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。）（新增節(jié)點的父節(jié)點必須相同）

5. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。（新增節(jié)點必須為紅）

調(diào)整

1. 變色

2. 左旋

3. 右旋

應(yīng)用

• 關(guān)聯(lián)數(shù)組：如 STL 中的 map、set

紅黑樹、B 樹、B+ 樹的區(qū)別？

• 紅黑樹的深度比較大，而 B 樹和 B+ 樹的深度則相對要小一些

• B+ 樹則將數(shù)據(jù)都保存在葉子節(jié)點，同時通過鏈表的形式將他們連接在一起。

B 樹（B-tree）、B+ 樹（B+-tree）

B 樹、B+ 樹圖片

image

<figcaption style="margin: 10px 0px 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; overflow-wrap: break-word !important; line-height: inherit; text-align: center; color: rgb(153, 153, 153); font-size: 0.7em;">B 樹（B-tree）、B+ 樹（B+-tree）</figcaption>

特點

• 一般化的二叉查找樹（binary search tree）

• “矮胖”，內(nèi)部（非葉子）節(jié)點可以擁有可變數(shù)量的子節(jié)點（數(shù)量范圍預(yù)先定義好）

應(yīng)用

• 大部分文件系統(tǒng)、數(shù)據(jù)庫系統(tǒng)都采用B樹、B+樹作為索引結(jié)構(gòu)

區(qū)別

• B+樹中只有葉子節(jié)點會帶有指向記錄的指針（ROWID），而B樹則所有節(jié)點都帶有，在內(nèi)部節(jié)點出現(xiàn)的索引項不會再出現(xiàn)在葉子節(jié)點中。

• B+樹中所有葉子節(jié)點都是通過指針連接在一起，而B樹不會。

B樹的優(yōu)點

對于在內(nèi)部節(jié)點的數(shù)據(jù)，可直接得到，不必根據(jù)葉子節(jié)點來定位。

B+樹的優(yōu)點

• 非葉子節(jié)點不會帶上 ROWID，這樣，一個塊中可以容納更多的索引項，一是可以降低樹的高度。二是一個內(nèi)部節(jié)點可以定位更多的葉子節(jié)點。

• 葉子節(jié)點之間通過指針來連接，范圍掃描將十分簡單，而對于B樹來說，則需要在葉子節(jié)點和內(nèi)部節(jié)點不停的往返移動。

B 樹、B+ 樹區(qū)別來自：differences-between-b-trees-and-b-trees、B樹和B+樹的區(qū)別：

http://t.cn/RrBAaZa

http://t.cn/E4WJhmZ

八叉樹

八叉樹圖片

image

八叉樹（octree），或稱八元樹，是一種用于描述三維空間（劃分空間）的樹狀數(shù)據(jù)結(jié)構(gòu)。八叉樹的每個節(jié)點表示一個正方體的體積元素，每個節(jié)點有八個子節(jié)點，這八個子節(jié)點所表示的體積元素加在一起就等于父節(jié)點的體積。一般中心點作為節(jié)點的分叉中心。

用途

• 三維計算機(jī)圖形

• 最鄰近搜索

算法

排序

http://t.cn/E4WJUGz

均按從小到大排列

• k：代表數(shù)值中的 “數(shù)位” 個數(shù)

• n：代表數(shù)據(jù)規(guī)模

• m：代表數(shù)據(jù)的最大值減最小值

• 來自：wikipedia . 排序算法

查找

圖搜索算法

其他算法

Problems

Single Problem

• Chessboard Coverage Problem（棋盤覆蓋問題）

• Knapsack Problem（背包問題）

• Neumann Neighbor Problem（馮諾依曼鄰居問題）

• Round Robin Problem（循環(huán)賽日程安排問題）

• Tubing Problem（輸油管道問題）

Leetcode Problems

• Github . haoel/leetcode

• Github . pezy/LeetCode

劍指 Offer

• Github . zhedahht/CodingInterviewChinese2

• Github . gatieme/CodingInterviews

Cracking the Coding Interview 程序員面試金典

• Github . careercup/ctci

• ?？途W(wǎng) . 程序員面試金典

?？途W(wǎng)

• 牛客網(wǎng) . 在線編程專題

操作系統(tǒng)

進(jìn)程與線程

對于有線程系統(tǒng)：

• 進(jìn)程是資源分配的獨(dú)立單位

• 線程是資源調(diào)度的獨(dú)立單位

對于無線程系統(tǒng)：

• 進(jìn)程是資源調(diào)度、分配的獨(dú)立單位

進(jìn)程之間的通信方式以及優(yōu)缺點

• 管道（PIPE）

• 優(yōu)點：簡單方便

• 缺點：

• 優(yōu)點：可以實現(xiàn)任意關(guān)系的進(jìn)程間的通信

• 缺點：

• 有名管道：一種半雙工的通信方式，它允許無親緣關(guān)系進(jìn)程間的通信

• 無名管道：一種半雙工的通信方式，只能在具有親緣關(guān)系的進(jìn)程間使用（父子進(jìn)程）

1. 局限于單向通信

2. 只能創(chuàng)建在它的進(jìn)程以及其有親緣關(guān)系的進(jìn)程之間

3. 緩沖區(qū)有限

4. 長期存于系統(tǒng)中，使用不當(dāng)容易出錯

5. 緩沖區(qū)有限

• 信號量（Semaphore）：一個計數(shù)器，可以用來控制多個線程對共享資源的訪問

• 優(yōu)點：可以同步進(jìn)程

• 缺點：信號量有限

• 信號（Signal）：一種比較復(fù)雜的通信方式，用于通知接收進(jìn)程某個事件已經(jīng)發(fā)生

• 消息隊列（Message Queue）：是消息的鏈表，存放在內(nèi)核中并由消息隊列標(biāo)識符標(biāo)識

• 優(yōu)點：可以實現(xiàn)任意進(jìn)程間的通信，并通過系統(tǒng)調(diào)用函數(shù)來實現(xiàn)消息發(fā)送和接收之間的同步，無需考慮同步問題，方便

• 缺點：信息的復(fù)制需要額外消耗 CPU 的時間，不適宜于信息量大或操作頻繁的場合

• 共享內(nèi)存（Shared Memory）：映射一段能被其他進(jìn)程所訪問的內(nèi)存，這段共享內(nèi)存由一個進(jìn)程創(chuàng)建，但多個進(jìn)程都可以訪問

• 優(yōu)點：無須復(fù)制，快捷，信息量大

• 缺點：

1. 通信是通過將共享空間緩沖區(qū)直接附加到進(jìn)程的虛擬地址空間中來實現(xiàn)的，因此進(jìn)程間的讀寫操作的同步問題

2. 利用內(nèi)存緩沖區(qū)直接交換信息，內(nèi)存的實體存在于計算機(jī)中，只能同一個計算機(jī)系統(tǒng)中的諸多進(jìn)程共享，不方便網(wǎng)絡(luò)通信

• 套接字（Socket）：可用于不同及其間的進(jìn)程通信

• 優(yōu)點：

• 缺點：需對傳輸?shù)臄?shù)據(jù)進(jìn)行解析，轉(zhuǎn)化成應(yīng)用級的數(shù)據(jù)。

1. 傳輸數(shù)據(jù)為字節(jié)級，傳輸數(shù)據(jù)可自定義，數(shù)據(jù)量小效率高

2. 傳輸數(shù)據(jù)時間短，性能高

3. 適合于客戶端和服務(wù)器端之間信息實時交互

4. 可以加密,數(shù)據(jù)安全性強(qiáng)

線程之間的通信方式

• 鎖機(jī)制：包括互斥鎖/量（mutex）、讀寫鎖（reader-writer lock）、自旋鎖（spin lock）、條件變量（condition）

• 互斥鎖/量（mutex）：提供了以排他方式防止數(shù)據(jù)結(jié)構(gòu)被并發(fā)修改的方法。

• 讀寫鎖（reader-writer lock）：允許多個線程同時讀共享數(shù)據(jù)，而對寫操作是互斥的。

• 自旋鎖（spin lock）與互斥鎖類似，都是為了保護(hù)共享資源。互斥鎖是當(dāng)資源被占用，申請者進(jìn)入睡眠狀態(tài)；而自旋鎖則循環(huán)檢測保持著是否已經(jīng)釋放鎖。

• 條件變量（condition）：可以以原子的方式阻塞進(jìn)程，直到某個特定條件為真為止。對條件的測試是在互斥鎖的保護(hù)下進(jìn)行的。條件變量始終與互斥鎖一起使用。

• 信號量機(jī)制(Semaphore)

• 無名線程信號量

• 命名線程信號量

• 信號機(jī)制(Signal)：類似進(jìn)程間的信號處理

• 屏障（barrier）：屏障允許每個線程等待，直到所有的合作線程都達(dá)到某一點，然后從該點繼續(xù)執(zhí)行。

線程間的通信目的主要是用于線程同步，所以線程沒有像進(jìn)程通信中的用于數(shù)據(jù)交換的通信機(jī)制

進(jìn)程之間的通信方式以及優(yōu)缺點來源于：進(jìn)程線程面試題總結(jié)

進(jìn)程之間私有和共享的資源

• 私有：地址空間、堆、全局變量、棧、寄存器

• 共享：代碼段，公共數(shù)據(jù)，進(jìn)程目錄，進(jìn)程 ID

線程之間私有和共享的資源

• 私有：線程棧，寄存器，程序寄存器

• 共享：堆，地址空間，全局變量，靜態(tài)變量

多進(jìn)程與多線程間的對比、優(yōu)劣與選擇

對比

優(yōu)劣

選擇

• 需要頻繁創(chuàng)建銷毀的優(yōu)先用線程

• 需要進(jìn)行大量計算的優(yōu)先使用線程

• 強(qiáng)相關(guān)的處理用線程，弱相關(guān)的處理用進(jìn)程

• 可能要擴(kuò)展到多機(jī)分布的用進(jìn)程，多核分布的用線程

• 都滿足需求的情況下，用你最熟悉、最拿手的方式

多進(jìn)程與多線程間的對比、優(yōu)劣與選擇來自：多線程還是多進(jìn)程的選擇及區(qū)別

Linux 內(nèi)核的同步方式

原因

在現(xiàn)代操作系統(tǒng)里，同一時間可能有多個內(nèi)核執(zhí)行流在執(zhí)行，因此內(nèi)核其實象多進(jìn)程多線程編程一樣也需要一些同步機(jī)制來同步各執(zhí)行單元對共享數(shù)據(jù)的訪問。尤其是在多處理器系統(tǒng)上，更需要一些同步機(jī)制來同步不同處理器上的執(zhí)行單元對共享的數(shù)據(jù)的訪問。

同步方式

• 原子操作

• 信號量（semaphore）

• 讀寫信號量（rw_semaphore）

• 自旋鎖（spinlock）

• 大內(nèi)核鎖（BKL，Big Kernel Lock）

• 讀寫鎖（rwlock）

• 大讀者鎖（brlock-Big Reader Lock）

• 讀-拷貝修改(RCU，Read-Copy Update)

• 順序鎖（seqlock）

來自：Linux 內(nèi)核的同步機(jī)制，第 1 部分、Linux 內(nèi)核的同步機(jī)制，第 2 部分

死鎖

原因

• 系統(tǒng)資源不足

• 資源分配不當(dāng)

• 進(jìn)程運(yùn)行推進(jìn)順序不合適

產(chǎn)生條件

• 互斥

• 請求和保持

• 不剝奪

• 環(huán)路

預(yù)防

• 打破互斥條件：改造獨(dú)占性資源為虛擬資源，大部分資源已無法改造。

• 打破不可搶占條件：當(dāng)一進(jìn)程占有一獨(dú)占性資源后又申請一獨(dú)占性資源而無法滿足，則退出原占有的資源。

• 打破占有且申請條件：采用資源預(yù)先分配策略，即進(jìn)程運(yùn)行前申請全部資源，滿足則運(yùn)行，不然就等待，這樣就不會占有且申請。

• 打破循環(huán)等待條件：實現(xiàn)資源有序分配策略，對所有設(shè)備實現(xiàn)分類編號，所有進(jìn)程只能采用按序號遞增的形式申請資源。

• 有序資源分配法

• 銀行家算法

文件系統(tǒng)

• Windows：FCB 表 + FAT + 位圖

• Unix：inode + 混合索引 + 成組鏈接

主機(jī)字節(jié)序與網(wǎng)絡(luò)字節(jié)序

主機(jī)字節(jié)序（CPU 字節(jié)序）

概念

主機(jī)字節(jié)序又叫 CPU 字節(jié)序，其不是由操作系統(tǒng)決定的，而是由 CPU 指令集架構(gòu)決定的。主機(jī)字節(jié)序分為兩種：

• 大端字節(jié)序（Big Endian）：高序字節(jié)存儲在低位地址，低序字節(jié)存儲在高位地址

• 小端字節(jié)序（Little Endian）：高序字節(jié)存儲在高位地址，低序字節(jié)存儲在低位地址

存儲方式

32 位整數(shù) 0x12345678 是從起始位置為 0x00 的地址開始存放，則：

大端小端圖片

[圖片上傳失敗...(image-86c73-1555590815042)]
[圖片上傳失敗...(image-d802-1555590815042)]

判斷大端小端

判斷大端小端

可以這樣判斷自己 CPU 字節(jié)序是大端還是小端：

#include <iostream>
using namespace std;

int main()
{
    int i = 0x12345678;

    if (*((char*)&i) == 0x12)
        cout << "大端" << endl;
    else    
        cout << "小端" << endl;

    return 0;
}

各架構(gòu)處理器的字節(jié)序

• x86（Intel、AMD）、MOS Technology 6502、Z80、VAX、PDP-11 等處理器為小端序；

• Motorola 6800、Motorola 68000、PowerPC 970、System/370、SPARC（除 V9 外）等處理器為大端序；

• ARM（默認(rèn)小端序）、PowerPC（除 PowerPC 970 外）、DEC Alpha、SPARC V9、MIPS、PA-RISC 及 IA64 的字節(jié)序是可配置的。

網(wǎng)絡(luò)字節(jié)序

網(wǎng)絡(luò)字節(jié)順序是 TCP/IP 中規(guī)定好的一種數(shù)據(jù)表示格式，它與具體的 CPU 類型、操作系統(tǒng)等無關(guān)，從而可以保重數(shù)據(jù)在不同主機(jī)之間傳輸時能夠被正確解釋。

網(wǎng)絡(luò)字節(jié)順序采用：大端（Big Endian）排列方式。

頁面置換算法

在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不在內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時，如果操作系統(tǒng)內(nèi)存中沒有空閑頁面，則操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。

分類

• 全局置換：在整個內(nèi)存空間置換

• 局部置換：在本進(jìn)程中進(jìn)行置換

算法

全局：

• 工作集算法

• 缺頁率置換算法

局部：

• 最佳置換算法（OPT）

• 先進(jìn)先出置換算法（FIFO）

• 最近最久未使用（LRU）算法

• 時鐘（Clock）置換算法

計算機(jī)網(wǎng)絡(luò)

計算機(jī)經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu)：

計算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu).png

各層作用及協(xié)議

物理層

• 傳輸數(shù)據(jù)的單位 ———— 比特

• 數(shù)據(jù)傳輸系統(tǒng)：源系統(tǒng)（源點、發(fā)送器） --> 傳輸系統(tǒng) --> 目的系統(tǒng)（接收器、終點）

通道：

• 單向通道（單工通道）：只有一個方向通信，沒有反方向交互，如廣播

• 雙向交替通行（半雙工通信）：通信雙方都可發(fā)消息，但不能同時發(fā)送或接收

• 雙向同時通信（全雙工通信）：通信雙方可以同時發(fā)送和接收信息

通道復(fù)用技術(shù)：

• 頻分復(fù)用（FDM，F(xiàn)requency Division Multiplexing）：不同用戶在不同頻帶，所用用戶在同樣時間占用不同帶寬資源

• 時分復(fù)用（TDM，Time Division Multiplexing）：不同用戶在同一時間段的不同時間片，所有用戶在不同時間占用同樣的頻帶寬度

• 波分復(fù)用（WDM，Wavelength Division Multiplexing）：光的頻分復(fù)用

• 碼分復(fù)用（CDM，Code Division Multiplexing）：不同用戶使用不同的碼，可以在同樣時間使用同樣頻帶通信

數(shù)據(jù)鏈路層

主要信道：

• 點對點信道

• 廣播信道

點對點信道

• 數(shù)據(jù)單元 ———— 幀

三個基本問題：

• 封裝成幀：把網(wǎng)絡(luò)層的 IP 數(shù)據(jù)報封裝成幀，SOH - 數(shù)據(jù)部分 - EOT

• 透明傳輸：不管數(shù)據(jù)部分什么字符，都能傳輸出去；可以通過字節(jié)填充方法解決（沖突字符前加轉(zhuǎn)義字符）

• 差錯檢測：降低誤碼率（BER，Bit Error Rate），廣泛使用循環(huán)冗余檢測（CRC，Cyclic Redundancy Check）

點對點協(xié)議（Point-to-Point Protocol）：

• 點對點協(xié)議（Point-to-Point Protocol）：用戶計算機(jī)和 ISP 通信時所使用的協(xié)議

廣播信道

廣播通信：

• 硬件地址（物理地址、MAC 地址）

• 單播（unicast）幀（一對一）：收到的幀的 MAC 地址與本站的硬件地址相同

• 廣播（broadcast）幀（一對全體）：發(fā)送給本局域網(wǎng)上所有站點的幀

• 多播（multicast）幀（一對多）：發(fā)送給本局域網(wǎng)上一部分站點的幀

限于文章字?jǐn)?shù)限制，更多知識點總結(jié)請看“下篇”

掃描下方二維碼，及時獲取更多互聯(lián)網(wǎng)求職面經(jīng)、java、python、爬蟲、大數(shù)據(jù)等技術(shù)，和海量資料分享：
公眾號菜鳥名企夢后臺發(fā)送“csdn”即可免費(fèi)領(lǐng)取【csdn】和【百度文庫】下載服務(wù)；
公眾號菜鳥名企夢后臺發(fā)送“資料”:即可領(lǐng)取5T精品學(xué)習(xí)資料、java面試考點和java面經(jīng)總結(jié)，以及幾十個java、大數(shù)據(jù)項目，資料很全，你想找的幾乎都有

掃碼關(guān)注，及時獲取更多精彩內(nèi)容。（博主今日頭條大數(shù)據(jù)工程師）