2023屆C/C++軟體開發工程師校招面試常問知識點複盤Part 6

- - - - 41、DHCP協定(動态主機配置協定)
      - 42、STL中的allocate、deallocate
      - 43、虛函數表、虛函數表指針
      - 子類和父類的虛函數表是獨立的嗎？
      - 44、左值與右值的相關内容
      - 45、二叉堆的實作
      - 1、二叉堆
        
        2、利用二叉堆實作優先級隊列
        
        3、利用二叉堆實作堆排序

41、DHCP協定(動态主機配置協定)

DHCP協定是應用層協定,使用運輸層協定UDP提供的服務

DHCP服務端的端口是
UDP 67 DHCP用戶端的端口是 UDP 68

DHCP協定的工作過程以及一個沒有IP位址的計算機如何通過網絡中的DHCP伺服器動态地配置IP

前提條件：區域網路中存在DHCP伺服器,或存在DHCP中繼代理,計算機開機後自動運作DHCP用戶端軟體

①DHCP客戶主動尋找DHCP伺服器:DHCP DISCOVER

DHCP客戶通過廣播的方式(目的位址: 255.255.255.255 源位址 0.0.0.0 目的端口: 67 )發送DHCP發現封包,用于尋找DHCP伺服器;

因為端口為67,是以隻有DHCP伺服器會響應該發現封包,其他主機則丢棄該封包; DHCP伺服器收到封包後會封包層層解析會得到用戶端MAC,封包的事務ID等資訊,然後跟根據用戶端MAC查詢本地是否有已經配置好的網絡配置資訊

如果存在,就在 DHCP OFFER 封包中回複,如果不存在就以預設的方式生成配置資訊然後在 DHCP OFFER 封包中回複

②DHCP伺服器發送配置資訊提供封包:DHCP OFFER

DHCP伺服器通過廣播的方式(目的位址: 255.255.255.255 源位址 DHCP伺服器自己的IP位址 目的端口: 68 )發送 DHCP OFFER 封包.

因為端口為68,是以隻有運作了DHCP客戶的主機才會接收該封包,然後對封包進行解析可以獲得事務ID,由此判斷是否是發給自己的封包,如果不是則丢棄.

在 DHCP OFFER 封包中提供配置資訊有 IP位址 子網路遮罩 位址租期 預設網關 DNS伺服器 等

如果網絡中存在多個DHCP伺服器,用戶端有可能獲得多個 DHCP OFFER 封包,通常DHCP客戶會選擇先到的那個,然後給DHCP伺服器發送DHCP請求封包

③DHCP客戶發送DHCP請求封包:DHCP REQUEST

DHCP客戶通過廣播的方式(目的位址: 255.255.255.255 源位址 0.0.0.0 目的端口: 67 )發送 DHCP REQUEST 封包.

廣播發送是因為這樣就不用為每一個DHCP伺服器單點傳播發送自己的選擇情況,源位址為 0.0.0.0 是因為DHCP客戶目前還沒有設定自己的IP位址

DHCP REQUEST 封包中有 事務ID DHCP客戶的MAC位址 接收的租約中的IP位址 提供此租約的DHCP伺服器的IP位址 ,DHCP伺服器收到該封包後就可以知道自己的offer是否被選擇了

然後DHCP伺服器給DHCP客戶發送确認封包

④被選擇OFFER的DHCP伺服器給DHCP客戶發送确認封包:DHCP ACK

DHCP伺服器通過廣播方式(目的位址: 255.255.255.255 源位址 DHCP伺服器自己的IP位址 目的端口: 68 )發送确認封包.

之後在DHCP客戶收到DHCP ACK封包後就可以使用租用的IP位址等網絡配置資訊,然後與網絡中的其他主機進行通信了

然後就是正常的使用和通信了…

⑤DHCP客戶的續約階段(目的IP: DHCP伺服器的IP位址 源IP位址: 租用的IP位址 端口: 67 )

a) 0.5倍租用期時：DHCP用戶端主動續約,發送 DHCP REQUEST 封包,然後DHCP的響應有三種情況

情況1: DHCP伺服器同意續約,發送 DHCP ACK 封包,于是DHCP用戶端有了新的租期

情況2: DHCP伺服器不同意續約,發送 DHCP NACK 否認封包,于是DHCP用戶端立刻放棄目前的IP位址等配置資訊,然後重新執行上述的第①步

情況3: DHCP伺服器未響應,則繼續使用之前的IP位址配置資訊,等待0.875倍租用期的到來

b) 0.875倍租用期時：重複0.5倍租用期的動作,如果DHCP伺服器還是未響應,那麼等待租期用盡

c) 租期用盡時：立即放棄目前的IP位址等配置資訊,然後重新執行第①步

⑥DHCP客戶在租期内可以随時終止DHCP伺服器所提供的租用期:DHCP RELEASE

此時的是以廣播方式(目的位址:
255.255.255.255 源位址 0.0.0.0 目的端口: 67 )發送 DHCP RELEASE 封包

42、STL中的allocate、deallocate

STL中的記憶體空間配置設定有兩級：第一級配置器和第二級配置器

首先第一個問題：
為什麼需要兩級空間配置器？
①頻繁的在堆上申請釋放記憶體，會造成大量的記憶體碎片；

②調用malloc和free等申請釋放記憶體會使得空間添加許多附加資訊，降低了空間的使用率；

其次第二個問題： 二級空間配置器與一級空間配置器之間的協調合作關系？
①二級空間配置器負責小塊記憶體的申請，一般是小于等于128位元組；STL預設選擇二級空間配置器，如果申請的空間大于128位元組再去使用一級配置器

②一級空間配置器負責較大記憶體的申請，一般是大于128位元組；

第三個問題： 二級空間配置 使用一個數組存放8~128共16個大小的區塊連結清單，維護了16個 free-list
。

1、第一級配置器直接使用的是malloc、free、relloc函數

2、第二級配置器則是根據請求區塊的大小，大于128位元組，調用一級配置器；小于等于128位元組，則不使用一級配置器；

3、
allocate() 是空間配置函數，先判斷請求的區塊大小，大于128位元組就去調用一級配置器；小于等于128位元組就去檢查 free-list 是否有可用區塊，有的話直接拿來用；沒有的話就要為 free-list
申請記憶體空間

4、
dellocate() 是空間釋放函數，先判斷空間大小，大于128位元組就去調用一級配置器；小于等于128自己就去尋找對應的 free-list 然後釋放記憶體

43、虛函數表、虛函數表指針

C++中的虛函數的作用主要是實作多态的作用；而所謂多态則是當父類指針指向子類的時候，使用該指針調用同一個函數會因為指向的子類不同而表現出多種形态
虛函數的實作機制：
虛函數機制的實作主要依靠編譯器：
1. 如果一個類存在虛函數，那麼該類就會存在一個對應的虛函數表（一般是放在常量區），這裡簡稱為 虛表 ，這個 虛表 中儲存的是該類的虛函數的函數位址
  - 虛函數表的存在與類有關
2. 由該類執行個體化的一個對象，在對象存儲空間的頭部是虛函數表指針，簡稱 vptr ； vptr 指向了該類的虛函數表，虛函數表中存放的是該類的虛函數位址，然後有了虛函數位址就可以找到虛函數，進行執行了。(虛函數存放在代碼區)
3. 一般情況下在虛函數表中存放的虛函數會依照聲明順序存放
如果子類 Derive 繼承了父類 Base ：（假設父類、子類都有虛函數）
1. 子類 Dreive 也會有屬于自己的虛函數表，在虛函數表中父類虛函數在前，子類虛函數在後；注意這是虛函數表（一般存放在常量區）
2. 子類對象記憶體空間的頭部就是虛函數表指針，指向了他自己擁有的虛函數表
3. 如果子類重寫了父類的虛函數，那麼被重寫的虛函數的位址在 子類的虛函數表 中将被替換成子類新寫的函數（這一條特性決定，假如父類指針指向了子類的對象，可以實作多态效果）
  
  2023屆C/C++軟體開發工程師校招面試常問知識點複盤Part 6
4. 對于沒有被重寫的父類虛函數，在子類虛函數表和父類虛函數表中的函數指針一樣，相當于複刻，但不是同一個
如果子類 Derive 繼承了多個父類 Base1 、 Base2 、 Base3
1. 子類擁有自己的虛函數表，如果繼承了多個父類，将會擁有多個自己的虛函數表；
2. 子類對象的頭部是指向虛函數表的指針，如果有多個父類，将會有多個虛函數表指針，指向子類擁有的多個虛函數表
3. 對于子類自己新定義的虛函數，這些虛函數位址會存放在第一個虛函數表中
4. 如果子類重寫了父類虛函數，重寫的是哪一個父類的虛函數，就會在對應的虛函數表中修改相應的函數位址
  
  2023屆C/C++軟體開發工程師校招面試常問知識點複盤Part 6
關于初始化時機：
- 虛函數表在編譯時，編譯器就會建立好。虛函數表存在常量區，虛函數存在代碼區；
- 虛函數表指針是對象的一部分，在對象構造時進行初始化；虛函數和虛函數表屬于類，是以在編譯時就會建立好。
- 我們經常說的編譯器會去調用某個函數balabala（我覺得這個表述有點誤導人）。我認為其想表達的意思是：編譯器在将源檔案編譯成二進制檔案過程中在遇到建立一個對象的代碼時，會自動地生成調用構造函數的二進制代碼，也即所謂的編譯器調用…
子類和父類的虛函數表是獨立的嗎？
答：
1. 不管子類是否擁有自己新建立的虛函數以及是否重寫父類的虛函數，子類都擁有自己的虛函數表；
2. 因為假如子類重寫虛函數或者新定義虛函數時，就會改變虛函數表的内容，如果和父類共享虛函數表，那麼父類不就無法調用自己的虛函數了嗎？

44、左值與右值的相關内容

左值與右值

一般在等号的左邊，可以進行取位址的就是左值；

一般在沒有位址的臨時值、将亡值、字面值就是右值；

左值引用與右值引用

：

左值引用：可以指向左值，但是不能指向右值的是左值引用

原因： 因為左值引用相當于是變量的别名，是以左值引用應該有修改變量的能力，但是右值沒有位址，是以無法被修改，是以左值引用也就無法指向右值

但是 const 左值引用 不對右值進行修改，是以 const 左值引用 可以指向右值，例如 const int& ref_left_a = 5; ,

在vector的push_back(const int& val)—vec.push_back(5)就用到了左值引用指向右值

右值引用： && ，可以指向右值，但是不能指向左值，有了右值引用之後，就可以通過右值引用去修改右值

為什麼右值引用指向了一個右值，就可以修改其值了呢？

因為右值引用指向右值的過程本質上是将一個右值提升為一個左值，然後定義一個右值引用通過move函數，指向一個左值。

右值引用通過move函數指向一個左值後，就可以修改這個左值。

2023屆C/C++軟體開發工程師校招面試常問知識點複盤Part 6

右值引用如何指向左值？

答：使用move()函數可以将一個左值轉換成右值，可以讓右值引用指向一個左值；這也是為什麼右值引用可以修改右值。

左值引用和右值引用本身是左值！

隻要是聲明出來的左值引用和右值引用本身也是左值！

但是作為函數傳回值的右值引用是右值

是以右值引用既可能是左值（直接聲明：
int && ref b = 5; ）也可能是右值（函數傳回右值： std::move(a) 的傳回值）

總之

1、左值引用隻能指向左值，但是加了const的左值引用可以指向右值

2、右值引用可以直接指向右值，也可以借助move()函數指向左值

3、作為函數參數的右值引用，更加靈活：根據上述的第二條，就可以接收左右值，同時也能修改傳進來參數，按照第一條，雖然可以使用const接收右值，但是不能修改。

右值引用和move的應用場景

主要是在STL和自定義類中實作移動語義，避免拷貝

注意：是不是可以提供一個
移動構造函數 ，把被拷貝者的資料移動過來，被拷貝者後邊就不要了，這樣就可以避免深拷貝了

場景1：
用于實作移動構造函數，将被拷貝者的資料直接移動過來

①在沒有右值引用時的拷貝構造時，用的是const的左值引用
const type& val ：這樣既可以接收左值也可以接收右值。

使用左值引用，在參數傳遞進函數時因為使用了引用，是以避免了一次傳參時的值拷貝。但是在對象内部進行深拷貝時，還不可避免的要進行拷貝操作。

那如果某一個值已經是不再需要的，在上述的拷貝操作就是一件重複的操作，如果可以将被拷貝的資料直接轉移給新的對象擁有。那麼這個僅剩的一次拷貝操作也可以避免了，由此也就提高了效率。但是若還是使用const的左值引用就無法實作了，因為有 const 的，是以就無法對該左值引用進行修改，也就無法實作安全的将被拷貝的資料直接轉移給新的對象。

②此時右值引用就排上用場了：因為移動構造函數的參數是右值引用 type&& val ，是以該函數可以接收右值和左值（接收左值時使用 move() 函數将左值轉變成右值）

如此以來，就可以在函數内部修改這個左值了。因為當右值引用指向左值時，右值引用可以修改左值的内容。

如果參數是一個右值，右值引用指向該右值，對一個将亡值進行移動語義也是符合邏輯和文法的，并且使用右值引用引用了一個将亡值後該右值引用也是可以修改的

場景2： 在類似vector中的 push_back() 與 empalce_back() 函數中，會有右值引用參數的重載，在使用時主動使用 move()
函數會觸發移動語義

這種情況可以減少拷貝，直接将将亡對象的内容移動至容器中：
vector<string> vec;
string a = "hello";
// 直接push_back()左值
vec.push_back(a);  // a不變
vec.push_back(move(a)); // 觸發了移動語義，将a中的内容“移動”到了容器内部，a将變成一個空字元串

// 也可以直接填右值
vec.push_back("hello");
           
此外 智能指針unique_ptr 僅有移動構造函數，隻能移動對象内部的所有權，不能拷貝 場景3： 就是forward()函數中，但是這個不常用，是以也不太了解

45、二叉堆的實作

1、二叉堆

二叉堆本質是完全二叉樹，并且存放在數組之中
是以存儲在數組中的二叉堆有如下性質：
如果在數組中 idx = 0 的位置存放 root ，那麼父節點的索引與左右子節點的關系如下：
- 父節點為 i ，左子節點 2i + 1 右子節點 2i+2
如果在數組中 idx = 1 的位置存放 root ，那麼父節點的索引與左右子節點的關系如下：
- 父節點為 i ，左子節點 2i 右子節點 2i+1
2023屆C/C++軟體開發工程師校招面試常問知識點複盤Part 6
最大堆（大頂堆）：每個節點都大于他的兩個子節點
最小堆（小頂堆）：每個節點都小于他的兩個子節點

2、利用二叉堆實作優先級隊列

其實所謂的優先級隊列，就是一個二叉堆。
既然是隊列自然是要實作一些基本的函數：

1、構造

2、入隊列
push() 3、出隊列（擷取隊首元素，并彈出該元素） get_pop_front() 4、 size() 5、是否為空 empty()
其實想要實作上述的功能有兩個函數非常重要，也即節點的 上浮swim() 和 下沉sink() ，這兩個函數是二叉堆的精髓所在！

Show Me Code！

class PriorityQueue {
private:
	int* m_pArray;
    int m_length;
    int m_cap;
    
    // 節點上浮--大頂堆
    void swim_max(int idx){
        while(idx > 1 && m_pArray[idx] > m_pArray[idx / 2]) { // 目前節點大于父節點
            int temp = m_pArray[idx];						  // 交換
            m_pArray[idx] = m_pArray[idx / 2];
            m_pArray[idx / 2] = temp;
            
            idx = idx / 2;	 								  // 節點更新
        }
    }
    
    // 節點上浮--小頂堆
    void swim_small(int idx){
    	while(idx > 1 && m_pArray[idx] < m_pArray[idx / 2]) {
            int temp = m_pArray[idx];
            m_pArray[idx] = m_pArray[idx / 2];
            m_pArray[idx / 2] = temp;
            
            idx = idx / 2;
        }
    }
    
    // 節點下沉--大頂堆
    void sink_max(int idx){
        while(2 * idx <= m_length) {
            int l = 2 * idx;// 左節點
            if(l < m_length && m_pArray[l] < m_pArray[l + 1]) // 求左右節點的最大值(大頂堆)/最小值(小頂堆)
                l++;
            if(m_pArray[l] < m_pArray[idx])		// 如果已經滿足的條件--那麼break; 下沉結束
                break;
            
            int temp = m_pArray[idx];			// 交換
            m_pArray[idx] = m_pArray[l];
            m_pArray[l] = temp;
            
            idx = l;							// idx = l; 更新idx
        }
    }
    
    // 節點下沉--小頂堆
    void sink_max(int idx){
        while(2 * idx <= m_length) {
            int l = 2 * idx;
            if(l < m_length && m_pArray[l] > m_pArray[l + 1])
                l++;
            if(m_pArray[l] > m_pArray[idx])
                break;
            
            int temp = m_pArray[idx];
            m_pArray[idx] = m_pArray[l];
            m_pArray[l] = temp;
            
            idx = l;
        }
    }
public:
    // 構造,參數N表示隊列或二叉堆的最大容量
    PriorityQueue(int N) {
        m_pArray = new int[N + 1]; // 因為從數組的下标1開始存節點的
        m_length = 0;
        m_cap = N;
    }
    
    // 析構
    ~PriorityQueue() {
        delete []m_pArray;
        m_pArray = nullptr;
        m_length = 0;
        m_cap = 0;
    }
    
    int size() {
        return m_length;
    }
    
    bool empty() {
        return m_length == 0;
    }
    
    // 入隊--大頂堆
    void push(int ele) {
        if(m_length >= m_cap) return;
        m_pArray[++m_length] = ele;
        swim_max(m_length);
        // 或者小頂堆時用 swim_min(m_length); 
    }
    
    // 出隊--大頂堆
    int get_pop_front() {
        int ret = m_pArray[1];
        m_pArray[1] = m_pArray[m_length--];// 将最後的值交換到root節點
        m_pArray[m_length + 1] = 0;			// 尾部置空
        sink_max(1);
        // 或者小頂堆時用 sink_min(1);
        
        return ret;
    }
};

3、利用二叉堆實作堆排序

對于使用二叉堆進行堆排序，完全可以使用上述的優先級隊列
在排序算法函數内，建立一個優先級隊列也即二叉堆，然後将所有的數組元素添加到堆（隊列）中
然後再從優先級隊列依次取出每一個元素，放到原始數組中
傳回原始數組即可

對于大頂堆，就做降序排序；對于小頂堆，就做升序排序；

void headSort(vector<int> &nums){
    PriorityQueue PQ(nums.size() + 1);  // PQ是一個局部變量
    //PriorityQueue* pPQ = new PQ(nums.size() + 1);
    for(auto it : nums) PQ.push(it);
    for(auto & it : nums)  it = PQ.get_pop_front();
    
    // delete pPQ;
}

2023屆C/C++軟體開發工程師校招面試常問知識點複盤Part 6

目錄

41、DHCP協定(動态主機配置協定)

42、STL中的allocate、deallocate

43、虛函數表、虛函數表指針

44、左值與右值的相關内容

45、二叉堆的實作

繼續閱讀

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

測試理論面試題

[轉]九大排序算法——C語言實作及詳解

C++實作簡單順序表

軟體測試面試題整理

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

結構體：typedef與struct的差別

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

軟體測試工程師跳槽：收到面試電話後，我會做的事。

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希