類(lèi)的公共數(shù)據(jù)成員可以使用直接成員訪問(wèn)運(yùn)算符 . 實(shí)現(xiàn)

創(chuàng)建對(duì)象： 類(lèi)名稱(chēng) 對(duì)象 （如 Name A）

• 類(lèi)對(duì)象

對(duì)象有三個(gè)訪問(wèn)修飾符：public, private, protected，默認(rèn)訪問(wèn)修飾符是private。

• 構(gòu)造函數(shù)（默認(rèn)是無(wú)參構(gòu)造函數(shù)）

在每次創(chuàng)建類(lèi)的新對(duì)象時(shí)執(zhí)行

構(gòu)造函數(shù)的名稱(chēng)和類(lèi)的名稱(chēng)是完全相同的，并且不會(huì)返回任何類(lèi)型，也不會(huì)返回void。

• 一般構(gòu)造函數(shù)：構(gòu)造函數(shù)可以帶參數(shù)，用于為某些成員變量設(shè)置初始值，一個(gè)類(lèi)可以有多個(gè)一般構(gòu)造函數(shù)，前提是參數(shù)的個(gè)數(shù)或者類(lèi)型不同
• 拷貝構(gòu)造函數(shù)：函數(shù)參數(shù)為對(duì)象本身的引用（在創(chuàng)建對(duì)象時(shí)使用同一類(lèi)中之前創(chuàng)建的對(duì)象來(lái)初始化新創(chuàng)建的對(duì)象）
  使用場(chǎng)景：通過(guò)使用另一個(gè)同類(lèi)型的對(duì)象（本類(lèi)型的一個(gè)引用變量）來(lái)初始化新創(chuàng)建的對(duì)象，為深拷貝??

• 類(lèi)型轉(zhuǎn)換構(gòu)造函數(shù)：一般構(gòu)造函數(shù)的一種，根據(jù)一個(gè)指定類(lèi)的對(duì)象創(chuàng)造一個(gè)本類(lèi)的對(duì)象（不允許默認(rèn)轉(zhuǎn)換的話，提前聲明explict）
• 執(zhí)行順序：已知存在多態(tài)，與析構(gòu)順序相反

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

類(lèi)似于構(gòu)造函數(shù)，在每次刪除所創(chuàng)建的對(duì)象時(shí)執(zhí)行

析構(gòu)函數(shù)的名稱(chēng)和類(lèi)名稱(chēng)完全相同，只是在前面加了一個(gè)波浪號(hào)(~)作為前綴, 它也不會(huì)返回任何值，也不能帶有任何參數(shù)。析構(gòu)函數(shù)有助于在調(diào)出程序(如關(guān)閉文件，釋放資源等)前釋放資源

• 執(zhí)行順序：已知存在多態(tài)，與構(gòu)造順序相反

• 友元函數(shù)

友元函數(shù)定義在類(lèi)的外部，其特點(diǎn)是有權(quán)訪問(wèn)類(lèi)的所有私有(private)成員和保護(hù)(protected)成員。友元既可以是一個(gè)函數(shù)又可以是一個(gè)類(lèi)。友元類(lèi)中，整個(gè)類(lèi)及其所有的成員都是友元。定義友元函數(shù)需要在函數(shù)原型前使用關(guān)鍵字friend。

• 內(nèi)聯(lián)函數(shù)

通常與類(lèi)一起使用。定義內(nèi)聯(lián)函數(shù)需要在函數(shù)名的前面加關(guān)鍵字 inline，與宏類(lèi)似，但更高級(jí)。

特點(diǎn)：編譯器在編譯時(shí)會(huì)把函數(shù)的代碼副本放置在每個(gè)調(diào)用該函數(shù)的地方。在類(lèi)中定義的函數(shù)都是內(nèi)聯(lián)函數(shù)，可以不使用inline限定。

5.類(lèi)的三大特性

• 封裝：把對(duì)象的屬性和動(dòng)作封裝成抽象的類(lèi)

封裝性是通過(guò)訪問(wèn)控制來(lái)實(shí)現(xiàn)的（public，protected，默認(rèn)模式private）

• 繼承：讓某個(gè)類(lèi)的對(duì)象可以獲得另一個(gè)類(lèi)的對(duì)象的屬性（多態(tài)的前提）

繼承性是實(shí)現(xiàn)軟件可重用性的一種手段，即A類(lèi)被B類(lèi)繼承，A類(lèi)為父類(lèi)，B類(lèi)為子類(lèi)，B類(lèi)繼承A類(lèi)的所有public和protected成員數(shù)據(jù)和成員函數(shù)

！子類(lèi)可以重新定義父類(lèi)某些屬性，重寫(xiě)父類(lèi)的某些方法，即覆蓋父類(lèi)的某些屬性和方法，使其獲得與父類(lèi)不同的功能（重寫(xiě) override）

• 多態(tài)：不同對(duì)象對(duì)同一個(gè)信息產(chǎn)生不同的行為（同一個(gè)接口，不同實(shí)現(xiàn)）

動(dòng)態(tài)多態(tài)：基于封裝和繼承的實(shí)現(xiàn)，多個(gè)子類(lèi)對(duì)繼承于一個(gè)父類(lèi)的虛函數(shù)進(jìn)行重寫(xiě)
靜態(tài)多態(tài)：在同一個(gè)作用域?qū)瘮?shù)進(jìn)行重載(函數(shù)名相同，函數(shù)參數(shù)列表不同) / 對(duì)函數(shù)進(jìn)行模板化，忽略數(shù)據(jù)類(lèi)型強(qiáng)調(diào)數(shù)據(jù)操作

體現(xiàn)：父類(lèi)引用或指針指向子類(lèi)對(duì)象 / 父類(lèi)的引用或指針可以接受子類(lèi)對(duì)象

前提：存在父類(lèi)與子類(lèi)的繼承關(guān)系/父類(lèi)中必須有虛函數(shù)/子類(lèi)必須重寫(xiě)父類(lèi)的虛函數(shù)/父類(lèi)引用或指針指向子類(lèi)對(duì)象

6.虛函數(shù)

• 虛函數(shù)：在基類(lèi)的函數(shù)前加virtual關(guān)鍵字，并在一個(gè)或多個(gè)派生類(lèi)中重新定義的成員函數(shù)，實(shí)現(xiàn)同一個(gè)接口不同的實(shí)現(xiàn)，即多態(tài)
• 作用：實(shí)現(xiàn)動(dòng)態(tài)聯(lián)編 /?實(shí)現(xiàn)統(tǒng)一接口但不同執(zhí)行過(guò)程

• 虛函數(shù)主要通過(guò)虛函數(shù)表來(lái)實(shí)現(xiàn)，其保存該類(lèi)中虛函數(shù)的地址，并且為派生類(lèi)對(duì)象生成一個(gè)虛函數(shù)指針，指向該類(lèi)型的虛函數(shù)表（可解決繼承、覆蓋的問(wèn)題，虛函數(shù)表就像一個(gè)地圖一樣，可指明實(shí)際所應(yīng)該調(diào)用的函數(shù)）
  每一個(gè)有虛函數(shù)的類(lèi)都有一個(gè)虛函數(shù)表，虛函數(shù)是整個(gè)類(lèi)所共有的，虛函數(shù)表存儲(chǔ)在對(duì)象內(nèi)存最開(kāi)始的位置。如果子類(lèi)繼承了多個(gè)父類(lèi)，并且父類(lèi)有虛函數(shù)，則子類(lèi)要存儲(chǔ)多個(gè)虛函數(shù)指針。如圖所示，如果繼承了n個(gè)父類(lèi)，并且每個(gè)父類(lèi)都有虛函數(shù)，那子類(lèi)會(huì)有n個(gè)虛函數(shù)表指針。

• 聯(lián)編：將函數(shù)名和函數(shù)體的程序連接到一起
  靜態(tài)聯(lián)編（靜態(tài)綁定，早綁定） ：在編譯的時(shí)候就確定了函數(shù)的地址（效率高）

  動(dòng)態(tài)聯(lián)編（動(dòng)態(tài)綁定，晚綁定） ：首先取對(duì)象的首地址，再解引用取到虛函數(shù)表的首地址，再加上偏移量才能找到要調(diào)的虛函數(shù)

• 虛函數(shù)的意義：

  1、同一個(gè)類(lèi)的多個(gè)對(duì)象的虛函數(shù)表是同一個(gè)，可以節(jié)省空間

  2、一個(gè)類(lèi)自己的虛函數(shù)和繼承的虛函數(shù)還有重寫(xiě)父類(lèi)的虛函數(shù)都會(huì)存在自己的虛函數(shù)表

  3、虛函數(shù)表本質(zhì)是一個(gè)地圖導(dǎo)航，可以告訴想要操作子類(lèi)的父類(lèi)指針到底該使用哪個(gè)函數(shù)

• 析構(gòu)函數(shù)為什么是虛函數(shù)：在用基類(lèi)操作派生類(lèi)時(shí)，為了防止執(zhí)行基類(lèi)的析構(gòu)函數(shù)，不執(zhí)行派生類(lèi)的析構(gòu)函數(shù)。因?yàn)檫@樣的刪除只能夠刪除基類(lèi)對(duì)象，而不能刪除子類(lèi)對(duì)象，會(huì)造成內(nèi)存泄漏
• 構(gòu)造函數(shù)為什么不是虛函數(shù)：創(chuàng)建一個(gè)對(duì)象需要知道對(duì)象的完成信息，虛函數(shù)調(diào)用僅需要函數(shù)的接口，不需要知道對(duì)象的具體類(lèi)型，因此不能實(shí)例化。
• 純虛函數(shù)：在成員函數(shù)的形參后面加 = 0 （virtual 函數(shù)類(lèi)型 函數(shù)名 （參數(shù)表列） = 0）1、為了讓派生類(lèi)只繼承函數(shù)的接口，不能實(shí)例化

  2、一個(gè)基類(lèi)包含一個(gè)以上純虛函數(shù)，就是抽象基類(lèi)。抽象基類(lèi)不能也沒(méi)必要定義對(duì)象。?
  3、在類(lèi)的層次結(jié)構(gòu)中，頂層或最上面幾層可以是抽象基類(lèi)。抽象基類(lèi)體現(xiàn)了本類(lèi)族中各類(lèi)的共性，把各類(lèi)中共有的成員函數(shù)集中在抽象基類(lèi)中聲明。?

  4、抽象基類(lèi)是本類(lèi)族的共公共接口，即就是從同一基類(lèi)中派生出的多個(gè)類(lèi)有同一接口

• 總結(jié)

7.深拷貝&淺拷貝

• 淺拷貝：系統(tǒng)默認(rèn)的拷貝函數(shù)
• 深拷貝：在堆內(nèi)存中另外申請(qǐng)空間來(lái)存儲(chǔ)數(shù)據(jù)

當(dāng)數(shù)據(jù)成員中有指針時(shí)，必須用深拷貝，否則會(huì)造成野指針等空間泄露的問(wèn)題。

8.強(qiáng)制轉(zhuǎn)換

• static_cast：靜態(tài)轉(zhuǎn)換。主要執(zhí)行非多態(tài)的轉(zhuǎn)換操作。
• dynamic_cast：動(dòng)態(tài)轉(zhuǎn)換。專(zhuān)門(mén)用于派生類(lèi)之間的轉(zhuǎn)換操作。

靜態(tài)轉(zhuǎn)換中，上行轉(zhuǎn)換（子類(lèi)->父類(lèi)）安全，下行轉(zhuǎn)換（父類(lèi)->子類(lèi)）不安全，因?yàn)楫?dāng)類(lèi)型不一致時(shí)，轉(zhuǎn)換的是錯(cuò)誤意義的指針，容易造成非法訪問(wèn)等現(xiàn)象。

動(dòng)態(tài)轉(zhuǎn)換會(huì)檢查轉(zhuǎn)換類(lèi)型，可以實(shí)現(xiàn)下行轉(zhuǎn)換（父類(lèi)->子類(lèi)）轉(zhuǎn)換

• const_cast：常量轉(zhuǎn)換。用于const屬性的轉(zhuǎn)換。
• reinterpret_cast：強(qiáng)制轉(zhuǎn)換（高危操作，慎用！！！）。從底層對(duì)數(shù)據(jù)進(jìn)行重新解釋，肆無(wú)忌憚的轉(zhuǎn)換。

9.內(nèi)存泄漏

• 申請(qǐng)了一塊內(nèi)存空間，使用完畢后沒(méi)有釋放
• 使用智能指針可以有效避免內(nèi)存泄漏

10.C++11的新特性

• 空指針nullptr：替代NULL(0)，類(lèi)型為nullptr_t，隱式轉(zhuǎn)換為任何指針或成員指針的類(lèi)型
• Lambda表達(dá)式：類(lèi)似匿名函數(shù)（需要函數(shù)體，不需要函數(shù)名），可以理解為簡(jiǎn)易版函數(shù)
  基本格式：?[捕獲方式] (參數(shù))?->?返回值類(lèi)型 {函數(shù)體}（可以忽略返回類(lèi)型，lambda自動(dòng)推斷出返回類(lèi)型）
  [ ]：閉包形式(closure type)，即定義一個(gè)lambda表達(dá)式后，編譯器會(huì)自動(dòng)生成一個(gè)重載()運(yùn)算符的匿名類(lèi)。優(yōu)勢(shì)在于可以通過(guò)傳值或引用的方式捕獲其封裝作用域內(nèi)的變量（即捕獲方式中存在的變量）
  捕獲方式：

• 右值引用：從右值中直接拿數(shù)據(jù)初始化或修改左值，不需要重新構(gòu)造左值后在析構(gòu)右值
  如：int a(左值) = hanshu(B);（右值）
• 常量表達(dá)式泛化：變量初始化后，可以以常量使用。
  如：int n = 5; int arr[n];
• 初始化列表：{變量1,...,變量n}。 如int a{1};
• 類(lèi)型推導(dǎo)：auto關(guān)鍵字和decltype關(guān)鍵字
  auto：靜態(tài)推導(dǎo)出任意類(lèi)型
• decltype：不對(duì)表達(dá)式進(jìn)行求值，就可以獲取其類(lèi)型
• 構(gòu)造函數(shù)委托：在同一個(gè)類(lèi)中，一個(gè)構(gòu)造函數(shù)可以調(diào)用另一個(gè)構(gòu)造函數(shù)
• final和override：final禁止虛函數(shù)被重寫(xiě)或禁止類(lèi)被繼承 / override重寫(xiě)虛函數(shù)
• 哈希表：設(shè)置哈希函數(shù)F，輸入一個(gè)key，通過(guò)哈希函數(shù)F制造獨(dú)一無(wú)二的key1，然后找到存在哈希表key1對(duì)應(yīng)的val。

11.STL容器

序列式容器：元素在容器中的位置順序存儲(chǔ)和訪問(wèn)（array/vector/list/deque）

vector：高效的隨機(jī)存取

list：大量的插入和刪除

deque：即要求高效的隨機(jī)存取，有需要數(shù)據(jù)兩端的插入和刪除

vector：連續(xù)空間的容器

• 迭代器：數(shù)據(jù)的頭(start)、數(shù)據(jù)的尾(finish)和數(shù)組的尾(end)
• 屬性獲取：
  1、begin() = 數(shù)據(jù)的頭(start)、end() = 數(shù)據(jù)的尾(finish)
  2、front() = *start、back() = *(finish-1)
  3、size() = 數(shù)組元素的個(gè)數(shù)? ?max_size() = 數(shù)組最大能存儲(chǔ)的元素個(gè)數(shù)? capacity() = 數(shù)組的實(shí)際大小(容量)
  4、empty() = 判斷vector是否為空
• 數(shù)據(jù)操作：
  1、push_back()：首先檢查是否還有備用空間，有，則調(diào)用迭代器finish，向尾部插入元素。沒(méi)有，則擴(kuò)充空間(復(fù)制2倍大小的vector ->復(fù)制數(shù)據(jù) -> 釋放原空間)，再向其尾部插入元素。
  2、pop_back()：放棄尾部元素
  3、erase(iterator first, iterator last)：刪除first到last之間的元素，實(shí)際上是將last后面的元素向前移動(dòng)
  4、insert()：插入元素。實(shí)際分為三種情況，
  備用空間夠且插入點(diǎn)后面的元素多于新增元素：先構(gòu)造出finish-n的空間在后面 -> 將插入點(diǎn)后的元素拷貝到備用空間 -> 從插入元素位置插入新值；
  備用空間夠且插入點(diǎn)后面的元素少于等于新增元素：先判斷是否還有備用空間 -> 在finish后構(gòu)造一個(gè)元素finish1 -> 將原先插入點(diǎn)后的元素移到finish1后 -> 在插入元素位置插入新值；
  備用空間不夠：先復(fù)制兩倍大小的vector -> 分段拷貝元素（插入點(diǎn)前、插入點(diǎn)后） -> 填充新值；
• 優(yōu)缺點(diǎn)：在頻率較高的插入和刪除時(shí)盡量不使用
  1、優(yōu)點(diǎn)：在內(nèi)存的一段連續(xù)空間中操作，動(dòng)態(tài)擴(kuò)容 / 隨機(jī)訪問(wèn)，支持下標(biāo)訪問(wèn)?/ 節(jié)省空間
  2、缺點(diǎn)：?插入刪除元素的時(shí)間復(fù)雜度為O(n) / 只能在末端進(jìn)行push和pop / 長(zhǎng)度太長(zhǎng)后，需要重新分配、拷貝和釋放空間??????

list：雙向鏈表

• 數(shù)據(jù)結(jié)構(gòu)：存儲(chǔ)了前后指針的雙向鏈表
• 屬性獲取：
  1、begin() = 返回指向頭的指針? end() = 返回最后一個(gè)元素的后一個(gè)地址
  2、rbegin() = 返回最后一個(gè)地址? ? rend() = 返回第一個(gè)地址
  3、empty() = 是否為空鏈表
  4、size() = 鏈表長(zhǎng)度 max_size() = 鏈表最大長(zhǎng)度
  5、front() = 第一個(gè)元素的值? back() = 最后一個(gè)元素的值
• 數(shù)據(jù)操作：list是循環(huán)的雙向鏈表，必須確認(rèn)是在頭或者尾進(jìn)行刪除或插入（插入是在指定位置前一個(gè)地址進(jìn)行插入的）
  內(nèi)部提供transfer()函數(shù)，將某連續(xù)范圍的元素遷移到某個(gè)指定位置之前
  1、push_front()：在頭插入? ? push_back()：在尾插入
  2、pop_front()：在頭刪除? ? pop_back()：在尾刪除
  3、erase()：先保留前驅(qū)和后繼節(jié)點(diǎn)，刪除后，再調(diào)整指針位置
  4、splice()：將兩個(gè)鏈表合并，調(diào)用transfer()函數(shù)
  5、merge()：將傳入的list鏈表x與原鏈表按從小到大合并到原鏈表中（前提是兩個(gè)鏈表已經(jīng)是排序過(guò)的，調(diào)用的也是transfer()函數(shù)）
  6、reverse()：鏈表反轉(zhuǎn)，將每個(gè)元素一個(gè)一個(gè)插入到begin之前
  7、sort()：排序，調(diào)用的是merge()函數(shù)
  8、賦值：原鏈表大（復(fù)制完后刪除原鏈表多余的元素）、原鏈表小（復(fù)制完后將被復(fù)制鏈表的剩余元素插入到原鏈表中）
  9、resize()：重新修改list大小，如果原鏈表長(zhǎng)度大于新長(zhǎng)度，則刪除后面多余的節(jié)點(diǎn)
  10、clear()：清除所有節(jié)點(diǎn)（遍歷每個(gè)節(jié)點(diǎn)，析構(gòu)并釋放）
  11、remove()：清除指定值的元素（遍歷每個(gè)節(jié)點(diǎn)，找到就刪除）
  12、unique()：清除數(shù)值相同的連續(xù)元素（連續(xù)且相同）
• 優(yōu)缺點(diǎn)：
  1、優(yōu)點(diǎn)：不適合連續(xù)內(nèi)存完成動(dòng)態(tài)操作 / 在內(nèi)部方便進(jìn)行插入和刪除?/ 兩端push和pop
  2、缺點(diǎn)：不支持隨機(jī)訪問(wèn) / 相對(duì)于vector內(nèi)存多

deque：雙向隊(duì)列（list+vector ≈ deque）

• 元素操作：finish是指向最后一個(gè)元素的后一個(gè)地址，但first是指向第一個(gè)元素的地址
  1、push_back()：先執(zhí)行構(gòu)造再移動(dòng)節(jié)點(diǎn)
  2、push_front()：先移動(dòng)節(jié)點(diǎn)再進(jìn)行構(gòu)造
• 優(yōu)缺點(diǎn)：
  1、優(yōu)點(diǎn)：隨機(jī)訪問(wèn)方便，支持下標(biāo)和at() / 在內(nèi)部方便進(jìn)行插入和刪除操作 / 兩端進(jìn)行push和pop??
  2、缺點(diǎn)：采用分段連續(xù)空間，占用內(nèi)存多

關(guān)聯(lián)式容器：通過(guò)鍵值(key)存儲(chǔ)和讀取元素

紅黑樹(shù)：set/map/multiset/multimap

哈希表：unordered_set/unordered_map/unordered_multiset/unordered_multimap

帶unordered = 無(wú)序，帶multi = 允許鍵(key)重復(fù)

insert_equal：允許鍵值重復(fù)

insert_unique：不允許鍵值重復(fù)

set：所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序

• 元素就是鍵值(key)，不允許有兩個(gè)元素具有相同的key
• 不允許通過(guò)迭代器改變set的元素值
• 元素操作：

  1、begin()：返回set容器的第一個(gè)元素

  2、end()：返回set容器的最后一個(gè)元素

  3、clear()：刪除set容器中的所有的元素

  4、empty()：判斷set容器是否為空

  5、max_size()：返回set容器可能包含的元素最大個(gè)數(shù)

  6、size()：返回當(dāng)前set容器中的元素個(gè)數(shù)

  7、rbegin：返回的值和end()相同

  8、rend()：返回的值和rbegin()相同
  9、count()：用來(lái)查找set中某個(gè)key出現(xiàn)的次數(shù)，即判斷某一key是否出現(xiàn)過(guò)
  10、equal_range()?：返回一對(duì)迭代器（pair），分別表示第一個(gè)大于或等于給定key的元素和第一個(gè)大于給定key的元素，如果返回失敗則返回end()

  11、erase(iterator) ：刪除迭代器iterator指向的值

  erase(first,second)：刪除迭代器first和second之間的值

  erase(key_value)：刪除鍵值key的值
  12、find() ：返回給定key的迭代器，沒(méi)找到則返回end()

  13、insert(key_value)：將key插入到set中?，返回值是pair<set<int>::iterator,bool>，bool標(biāo)志著插入是否成功，而iterator代表插入的位置，若key已經(jīng)在set中，則iterator表示的key在set中的位置。

  inset(first,second)：將迭代器first到second之間的元素插入到set中

  14、lower_bound(key_value)?：返回第一個(gè)大于等于key的迭代器

  15、upper_bound(key_value)：返回最后一個(gè)大于等于key的迭代器

multiset與set完全一致，除了允許key重復(fù)

unordered_set基于哈希表，是關(guān)鍵字和key相同的容器

map：以pair為基礎(chǔ)的關(guān)聯(lián)容器?= key?+ value

multimap允許key重復(fù)，且不支持[]運(yùn)算符

unordered_map基于哈希表

12.排序算法

• 冒泡排序：選擇相鄰的元素A/B，如果A>B，則交換。從0-n -> 1-n -> 2-n -> ... -> n-1-n進(jìn)行循環(huán) void BubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) { // 相鄰元素比較int temp = arr[j]; arr[j] = arr[j + 1];arr[j + 1] = temp; //交換兩個(gè)元素}}} }
• 選擇排序：分為已排序和未排序區(qū)間。遍歷未排序區(qū)間找到最小元素，將其放到已排序區(qū)間。同時(shí)由于亂序了，選擇排序是不穩(wěn)定的（相同大小的元素在排序后順序可能會(huì)改變）。
• 插入排序：同樣分為已排序和未排序區(qū)間。對(duì)未排序區(qū)間的每一個(gè)元素，將其插入到已排序區(qū)間的合適位置。 void SelectSort(int arr[], int n) {int i, j, min; //min = 最小元素int t = 1;for (i = 0; i < m - 1; i++) { //共有m個(gè)元素，只需要比m-1次min = i;for (j = i + 1; j < m; j++) {if (arr[j] < arr[min])min = j; //下標(biāo)變化，一直是比較后目前最小的數(shù)的下標(biāo)}if (min != i) { //如果最小數(shù)下標(biāo)改變了，進(jìn)行數(shù)的交換t = arr[min];arr[min] = arr[i];arr[i] = t;}} }void InsertSort(int arr[], int n) {int i, j;int low, high, mid; // 對(duì)已排序空間進(jìn)行二分法進(jìn)行查找for (i = 2; i <= n; i++) {arr[0] = arr[i];low = 1;high = i - 1;while (low <= high) {mid = (low + high) / 2;if (A[mid] > A[0])high = mid - 1;elselow = mid + 1; }for (j = i - 1; j >= low; j--)A[j + 1] = A[j];A[low] = A[0];} }
• 歸并排序：分治算法。
  1、首先遞歸地將數(shù)組分成兩段（如果數(shù)組長(zhǎng)度是奇數(shù)時(shí)，則一半長(zhǎng)一半短），直到分成長(zhǎng)度為1的 n 個(gè)數(shù)列，即n個(gè)數(shù)
  2、將數(shù)列兩兩合并，每次合并時(shí)進(jìn)行比較和排序，直到完成排序 void MergeSort(int arr[], int left, int right) {if (left == right)return;int mid = left + (right - left) / 2;MergeSort(arr, left, mid); //左側(cè)排序MergeSort(arr, mid + 1, right); //右側(cè)排序int *help = new int[right - left + 1]; //開(kāi)辟一個(gè)新的數(shù)組空間O(N)int i = 0;int p1 = left; //左側(cè)的指針int p2 = mid + 1; //右側(cè)的指針while (p1 <= mid && p2 <= right) //數(shù)組的左側(cè)和右側(cè)的元素不斷進(jìn)行對(duì)比，較小的元素賦值進(jìn)數(shù)組help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];while (p2 <= right) //將兩側(cè)剩余的較大的元素全部賦值進(jìn)去help[i++] = arr[p2++];while (p1 <= mid) //和上一個(gè)while循環(huán)一樣，這兩個(gè)while循環(huán)只能發(fā)生一個(gè)help[i++] = arr[p1++];for (int i = 0; i < right - left + 1; i++) //將help數(shù)組賦值給arr數(shù)組arr[left + i] = help[i];delete[] help; // c++需要手動(dòng)刪除,進(jìn)行內(nèi)存管理 }
• 快速排序：是目前最快的排序算法
  找到一個(gè)參照對(duì)象，比這個(gè)參照對(duì)象小的排左邊，比這個(gè)參照對(duì)象大的排右邊。對(duì)兩部分遞歸快速排序，直到有序。
  選擇左端（Left），右端（Right），中間值（Center）的中值為參照對(duì)象，效率最好 void QuickSort(int arr[], int left, int right) {if (right >= left + 3) //至少存在3個(gè)值{int center = (left + right) / 2;if (arr[left] > arr[center])std::swap(arr[left], arr[center]);if (arr[left] > arr[right])std::swap(arr[left], arr[right]);if (arr[center] > arr[right])std::swap(arr[center], arr[right]);std::swap(arr[center], arr[right - 1]);int pivot = arr[right - 1]; //確定找到參照對(duì)象auto i = left;auto j = right - 1;while (true) {while (arr[++i] < pivot);while (arr[--j] > pivot);if (i < j) //與參照對(duì)象進(jìn)行比較std::swap(arr[i], arr[j]); elsebreak;}std::swap(arr[i], arr[right - 1]);QuickSort(arr, left, i - 1); //分別對(duì)兩個(gè)子序列遞歸QuickSort(arr, i + 1, right);}elseInsertSort(arr, right - left + 1); //若小于3個(gè)值，直接插入排序 }
• ???堆排序：利用“堆”數(shù)據(jù)結(jié)構(gòu)（子節(jié)點(diǎn)的key總小于父節(jié)點(diǎn)——大堆頂）進(jìn)行排序，同樣可以用小堆頂進(jìn)行排序（子節(jié)點(diǎn)的key總大于父節(jié)點(diǎn)）
  1、通過(guò)數(shù)組創(chuàng)建堆，輸出堆頂元素（最大/小）
  2、以最后一個(gè)元素代替堆頂，重新生成堆，輸出堆頂元素（第二大/小）
  3、遞歸，直到堆的大小=1 void HeapGenerate(int arr[], int i, int length) //堆生成 { int leftChild = 2 * i + 1; //定義左右子節(jié)點(diǎn)int rightChild = 2 * i + 2;int max = i; //初始化，假設(shè)左右孩子的雙親節(jié)點(diǎn)就是最大值if (leftChild < length && arr[leftChild] > arr[max])max = leftChild;if (rightChild < length && arr[rightChild] > arr[max])max = rightChild;if (max != i) { //若最大值不是雙親節(jié)點(diǎn)，則交換值std::swap(arr[max], arr[i]);HeapGenerate(arr, max, length); //遞歸，使其子樹(shù)也為堆} } void HeapSort(int arr[], int length) //堆排序 { for (int i = length / 2 - 1; i >= 0; i--) //從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向上遍歷，建立堆HeapGenerate(arr, i, length);for (int j = length - 1; j > 0; j--) { //調(diào)整堆 ，此處不需要j=0std::swap(arr[0], arr[j]);HeapGenerate(arr, 0, j); //因?yàn)槊拷粨Q一次之后，就把最大值拿出(不再參與調(diào)整堆)，第三個(gè)參數(shù)應(yīng)該寫(xiě)j而不是length} }
• 希爾排序：將比較的元素分為幾個(gè)區(qū)域，提升插入排序的性能
• 計(jì)數(shù)排序：待排序的數(shù)作為計(jì)數(shù)數(shù)組的下標(biāo)，統(tǒng)計(jì)每個(gè)數(shù)字的個(gè)數(shù)，然后輸出（僅針對(duì)一定范圍內(nèi)的整數(shù)）
• 桶排序：把整型數(shù)組分到有限數(shù)量的桶里，再對(duì)每個(gè)桶進(jìn)行排序
• 基數(shù)排序：需要位比較，進(jìn)行多次桶排序

2、其他知識(shí)點(diǎn)

• C++內(nèi)存分配情況：棧（編譯器管理，局部變量和函數(shù)參數(shù)）/堆（程序員管理，new/malloc/delete/free）/全局（靜態(tài)）存儲(chǔ)區(qū)（全局變量和靜態(tài)變量）/常量存儲(chǔ)區(qū)（常量）/代碼區(qū)
  棧由編譯器管理，自動(dòng)分配空間，程序出錯(cuò)經(jīng)常為數(shù)據(jù)出棧；
  堆由程序員管理，手動(dòng)分配空間（malloc/free/new/delete），內(nèi)存泄漏常發(fā)生在此。
• static：修飾局部變量（修改生命周期，為靜態(tài)變量）/修飾全局變量（修改作用域范圍，僅本文件可見(jiàn)）/修飾函數(shù)（同修飾全局變量）/修飾類(lèi)函數(shù)（該函數(shù)屬于一個(gè)類(lèi)而不屬于此類(lèi)的任何特定對(duì)象）/修飾類(lèi)變量（該變量在存儲(chǔ)空間僅有一個(gè)副本，！類(lèi)內(nèi)聲明類(lèi)外定義！）
• 重載：overload，具有不同參數(shù)列表的同名函數(shù)
• 重寫(xiě)：override，子類(lèi)中重定義父類(lèi)中除函數(shù)體外完全相同的虛函數(shù)
• 重定義（隱藏）：子類(lèi)中重定義父類(lèi)中相同名字的非虛函數(shù)
• malloc/free：庫(kù)函數(shù)。malloc（分配未初始化的內(nèi)存空間）/free（回收內(nèi)存空間）
• new/delete：操作符。new（malloc -> 構(gòu)造函數(shù)）/ delete （析構(gòu)函數(shù) -> free）
• 內(nèi)存對(duì)齊：CPU是個(gè)字節(jié)為單位來(lái)存取內(nèi)存，將所有對(duì)象的最小公倍數(shù)設(shè)置為內(nèi)存存取粒度，以下是32位編譯器的內(nèi)存大小：
  char(1)/short(2)/int(4)/指針(4)/float(4)/long(4)/double(8)/long long(8)
  內(nèi)存對(duì)齊之后，CPU的內(nèi)存訪問(wèn)速度大大提升。
• 二叉樹(shù)：二叉樹(shù)、二叉搜索樹(shù)、平衡二叉樹(shù)、高度平衡二叉樹(shù)（AVL）

• 紅黑樹(shù)：每個(gè)節(jié)點(diǎn)是紅/黑、根節(jié)點(diǎn)為黑、葉子節(jié)點(diǎn)（最低的節(jié)點(diǎn)）為黑、每層節(jié)點(diǎn)紅黑交替、任意一結(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含數(shù)量相同的黑節(jié)點(diǎn)。

3、算法題

可以參考我的另一篇博客：算法教程，里面有很詳細(xì)的說(shuō)明。

四、邏輯綜合面試

1.邏輯綜合知識(shí)詳解

2.開(kāi)源邏輯綜合ABC

https://github.com/berkeley-abc/abc

讀取一個(gè)門(mén)級(jí)網(wǎng)表（例如AIG），進(jìn)行優(yōu)化，映射后輸出帶單元庫(kù)信息的門(mén)級(jí)網(wǎng)表

術(shù)語(yǔ)：

• AIG（AND-Inverter-Graph，與非圖）：ABC的基本數(shù)據(jù)結(jié)構(gòu)

• BLIF: Berkeley Logic Interchange Format, a format traditionally used by SIS, VIS, and MVSIS to represent logic networks, Berkeley邏輯交換格式，是SIS、VIS和MVSIS用來(lái)表示邏輯網(wǎng)絡(luò)的一種傳統(tǒng)格式

• BDD: Binary Decision Diagram, a canonical graph-based representation of Boolean functions, 二元決策圖，布爾函數(shù)的一種基于規(guī)范圖的表示

• CEC: Combinational equivalence checking, 組合等價(jià)性檢查

• BAF: Binary Aig Format, 二進(jìn)制AIG格式

• CI: Primary input and latch outputs

• CO: Primary output and latch inputs

• FRAIG: (a) Functionally Reduced AIG and (b) AIG package with on-the-fly detection of functionally equivalent AIG nodes, 功能簡(jiǎn)化AIG和功能等效AIG節(jié)點(diǎn)動(dòng)態(tài)檢測(cè)的AIG包

• FRAIGing: Transforming an AIG into a Functionally Reduced AIG (using the FRAIG package)

• IWLS: International Workshop on Logic and Synthesis, and annual research-oriented workshop

• LI: Latch input

• LO: Latch output

• LUT: Look-up table, a programmable logic component that can implement an arbitrary Boolean function up to a fixed number of inputs

• PI: Primary input

• PO: Primary output

• SAT: Boolean satisfiability

• SEC: Sequential equivalence checking

• SOP: Sum-Of-Products, a non-canonical representation of Boolean functions

• TFI: Transitive fanin

• TFO: Transitive fanout

• CNF:?conjunctive normal form

概念：

• CUT：割集
• boolean-matching（布爾匹配）：對(duì)于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)或?qū)τ诿總€(gè)CUT，從庫(kù)中選擇一個(gè)適當(dāng)?shù)拈T(mén)
• MFFC(maximum fanout free cone，最大扇出自由錐)：一個(gè)節(jié)點(diǎn)n的MFFC是指該節(jié)點(diǎn)n的扇入CONE的一個(gè)子集，該子集中包含了一些節(jié)點(diǎn)，這些節(jié)點(diǎn)滿足的條件是每一條經(jīng)過(guò)這些節(jié)點(diǎn)到最終輸出PO的路徑都需要經(jīng)過(guò)該節(jié)點(diǎn)n，這樣一個(gè)FI CONE的子集才能被稱(chēng)作為MFFC

• structural hashing：結(jié)構(gòu)化哈希，確保所有常量都被傳播，消除冗余項(xiàng)
• NPN class：NPN類(lèi)。N(Negative，輸入取反)-P(Permutation，對(duì)輸入進(jìn)行置換)-N(Negative，對(duì)輸出取反)，若已知一個(gè)函數(shù)，經(jīng)過(guò)以上三種操作得到的全部函數(shù)可以分為一個(gè)NPN類(lèi)
• choice：“記住”在綜合流中看到的每個(gè)網(wǎng)絡(luò)，并在工藝映射過(guò)程中選擇每個(gè)網(wǎng)絡(luò)中最好的部分

組合邏輯優(yōu)化指令(Command)：

• rewrite：一種快速的貪婪算法，通過(guò)迭代選擇一個(gè)節(jié)點(diǎn)上的AIG子圖，并用更小的預(yù)先計(jì)算的子圖替換它們，以最小化AIG節(jié)點(diǎn)的數(shù)量，同時(shí)保留節(jié)點(diǎn)的功能。
• refactor：對(duì)使用10-20個(gè)輸入的邏輯錐進(jìn)行折疊和重構(gòu)
• resubstitution ：對(duì)于當(dāng)前節(jié)點(diǎn)，重新使用網(wǎng)絡(luò)中已經(jīng)出現(xiàn)過(guò)的節(jié)點(diǎn)進(jìn)行表示（真值值相同），如果在某些方面，例如節(jié)點(diǎn)數(shù)或者depth取得更好的效果，就會(huì)被接受。
• balance：得到的AIG是通過(guò)對(duì)原始AIG中包含的多輸入和門(mén)進(jìn)行代數(shù)平衡得到的。根據(jù)拓?fù)漤樞蜻M(jìn)行平衡，選擇每個(gè)多輸入與門(mén)的最小延遲樹(shù)分解。平衡考慮了主要輸入的到達(dá)時(shí)間
• multi：將兩輸入aig改為多輸入與門(mén)
• strash：使用結(jié)構(gòu)化哈希將初始SOP邏輯網(wǎng)絡(luò)轉(zhuǎn)換為AIG
• renode：根據(jù)AIG重新創(chuàng)建SOP

時(shí)序邏輯優(yōu)化指令：

時(shí)序綜合通過(guò)修改當(dāng)前網(wǎng)絡(luò)的邏輯以及存儲(chǔ)元素(鎖存器或觸發(fā)器)來(lái)變換當(dāng)前網(wǎng)絡(luò)。

與原始網(wǎng)絡(luò)相比，得到的網(wǎng)絡(luò)可能具有不同的狀態(tài)編碼和可達(dá)狀態(tài)空間，但這兩個(gè)網(wǎng)絡(luò)是時(shí)序等效的(即從初始狀態(tài)開(kāi)始，對(duì)于相同的輸入向量序列，它們產(chǎn)生相同的輸出向量序列)

• retiming：保持網(wǎng)絡(luò)結(jié)構(gòu)不變，但移動(dòng)鎖存器，使得每個(gè)PI/PO路徑和每個(gè)循環(huán)上的鎖存器數(shù)量不變。更復(fù)雜的時(shí)序變換會(huì)修改鎖存器的邏輯結(jié)構(gòu)和位置。集成時(shí)序優(yōu)化在時(shí)序變換中占有特殊的位置，它通過(guò)一系列簡(jiǎn)單的局部變換，如局部重構(gòu)和retiming，就能使電路的延時(shí)達(dá)到全局最優(yōu)。
• if -s：集成時(shí)序優(yōu)化命令，通過(guò)探索邏輯綜合過(guò)程中看到的所有邏輯結(jié)構(gòu)的組合空間、所有可能的工藝映射和所有可能的retiming，來(lái)查找電路的最小延遲
• cycle：模擬隨機(jī)輸入的順序網(wǎng)絡(luò)，并更新其當(dāng)前狀態(tài)
• init：重置當(dāng)前網(wǎng)絡(luò)所有鎖存器的初始狀態(tài)(請(qǐng)注意一個(gè)有用的命令print_latch，可用于查看當(dāng)前網(wǎng)絡(luò)中所有鎖存器的初始狀態(tài))
• retime

  • 在不增加寄存器個(gè)數(shù)的前提下，通過(guò)改變寄存器的位置來(lái)優(yōu)化關(guān)鍵路徑

  • 實(shí)現(xiàn)多種類(lèi)型的retiming:最前向、最后向、最小寄存器、啟發(fā)式最小延遲

  • 當(dāng)電路從時(shí)序AIG轉(zhuǎn)換為邏輯網(wǎng)絡(luò)時(shí)，鎖存器在扇出梗之間得到最佳共享。將重定時(shí)后的初始狀態(tài)計(jì)算歸結(jié)為SAT問(wèn)題，利用MiniSat算法進(jìn)行求解

五、簡(jiǎn)歷制作

可以參考這個(gè)視頻制作CV，

超級(jí)簡(jiǎn)歷

總結(jié)

校招面試是一個(gè)很玄妙的東西，原因有二：

1.你很難在有限的時(shí)間內(nèi)，將你所有的能力表達(dá)出來(lái)

2.面試官很難在有限的時(shí)間內(nèi)，充分了解你的能力

因此，適當(dāng)?shù)陌b和準(zhǔn)備會(huì)大大提高自己面試成功的概率，這里并不是強(qiáng)調(diào)我們要進(jìn)行“詐騙”，而是盡可能的展現(xiàn)自己的實(shí)力，畢竟面試都沒(méi)通過(guò)，連被“拆穿”的可能都沒(méi)有！

本文主要結(jié)合作者自己的親身經(jīng)歷，給出EDA前端軟件開(kāi)發(fā)面試必備的一些知識(shí)，所以，不論你是剛畢業(yè)，剛培訓(xùn)完，或者是想去大廠，都可以浪費(fèi)幾分鐘，看看我對(duì)面試這件事的心得。

所以說(shuō)，程序員技術(shù)能力是一切的前提，不論你是剛要找工作，還是要面試大廠，如果失敗太多次，你一定要先找自己的問(wèn)題，沉下心來(lái)，多學(xué)習(xí)，等到實(shí)力夠了，屬于你的“大廠”自然會(huì)給你發(fā)來(lái)offer。

最后，祝大家都能找到一個(gè)nice的領(lǐng)導(dǎo)，心儀的公司，迎娶白富美！

總結(jié)

以上是生活随笔為你收集整理的《EDA前端软件开发工程师面试指南》的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。