[[376872]]

 本系列將按照類別對(duì)題目進(jìn)行分類整理，重要的地方標(biāo)上星星，這樣有利于大家打下堅(jiān)實(shí)的基礎(chǔ)。

第三章網(wǎng)絡(luò)編程

1 、TCP、UDP的區(qū)別

TCP---傳輸控制協(xié)議,提供的是面向連接、可靠的字節(jié)流服務(wù)。當(dāng)客戶和服務(wù)器彼此交換數(shù)據(jù)前，必須先在雙方之間建立一個(gè)TCP連接，之后才能傳輸數(shù)據(jù)。

UDP---用戶數(shù)據(jù)報(bào)協(xié)議，是一個(gè)簡(jiǎn)單的面向數(shù)據(jù)報(bào)的運(yùn)輸層協(xié)議。UDP不提供可靠性，它只是把應(yīng)用程序傳給IP層的數(shù)據(jù)報(bào)發(fā)送出去，但是并不能保證它們能到達(dá)目的地。

1)TCP是面向連接的，UDP是面向無(wú)連接的

2)UDP程序結(jié)構(gòu)較簡(jiǎn)單

3)TCP是面向字節(jié)流的，UDP是基于數(shù)據(jù)報(bào)的

4)TCP保證數(shù)據(jù)正確性，UDP可能丟包

5)TCP保證數(shù)據(jù)順序到達(dá)，UDP不保證

2 、TCP、UDP的優(yōu)缺點(diǎn)

TCP優(yōu)點(diǎn)：可靠穩(wěn)定

TCP的可靠體現(xiàn)在TCP在傳輸數(shù)據(jù)之前，會(huì)有三次握手來(lái)建立連接，而且在數(shù)據(jù)傳遞時(shí)，有確認(rèn)、窗口、重傳、擁塞控制機(jī)制，在數(shù)據(jù)傳完之后，還會(huì)斷開(kāi)來(lái)連接用來(lái)節(jié)約系統(tǒng)資源。

TCP缺點(diǎn)：慢，效率低，占用系統(tǒng)資源高，易被攻擊

在傳遞數(shù)據(jù)之前要先建立連接，這會(huì)消耗時(shí)間，而且在數(shù)據(jù)傳遞時(shí)，確認(rèn)機(jī)制、重傳機(jī)制、擁塞機(jī)制等都會(huì)消耗大量時(shí)間，而且要在每臺(tái)設(shè)備上維護(hù)所有的傳輸連接。然而，每個(gè)連接都會(huì)占用系統(tǒng)的CPU，內(nèi)存等硬件資源。因?yàn)門(mén)CP有確認(rèn)機(jī)制、三次握手機(jī)制，這些也導(dǎo)致TCP容易被利用，實(shí)現(xiàn)DOS、DDOS、CC等攻擊。

UDP優(yōu)點(diǎn)：快，比TCP稍安全

UDP沒(méi)有TCP擁有的各種機(jī)制，是一種無(wú)狀態(tài)的傳輸協(xié)議，所以傳輸數(shù)據(jù)非?？?，沒(méi)有TCP的這些機(jī)制，被攻擊利用的機(jī)會(huì)就少一些，但是也無(wú)法避免被攻擊。

UDP缺點(diǎn)：不可靠，不穩(wěn)定

因?yàn)闆](méi)有TCP的這些機(jī)制，UDP在傳輸數(shù)據(jù)時(shí)，如果網(wǎng)絡(luò)質(zhì)量不好，就會(huì)很容易丟包，造成數(shù)據(jù)的缺失。

3 、TCP UDP適用場(chǎng)景

TCP：傳輸一些對(duì)信號(hào)完整性，信號(hào)質(zhì)量有要求的信息。

UDP：對(duì)網(wǎng)絡(luò)通訊質(zhì)量要求不高時(shí)，要求網(wǎng)絡(luò)通訊速度要快的場(chǎng)景。

4、 TCP為什么是可靠連接?

因?yàn)閠cp傳輸?shù)臄?shù)據(jù)滿足3大條件，不丟失，不重復(fù)，按順序到達(dá)。

5、OSI典型網(wǎng)絡(luò)模型，簡(jiǎn)單說(shuō)說(shuō)有哪些

6、三次握手、四次揮手

三次握手

1、TCP服務(wù)器進(jìn)程先創(chuàng)建傳輸控制塊TCB，時(shí)刻準(zhǔn)備接受客戶進(jìn)程的連接請(qǐng)求，此時(shí)服務(wù)器就進(jìn)入了LISTEN(監(jiān)聽(tīng))狀態(tài);

2、TCP客戶進(jìn)程也是先創(chuàng)建傳輸控制塊TCB，然后向服務(wù)器發(fā)出連接請(qǐng)求報(bào)文，這是報(bào)文首部中的同部位SYN=1，同時(shí)選擇一個(gè)初始序列號(hào) seq=x ，此時(shí)，TCP客戶端進(jìn)程進(jìn)入了 SYN-SENT(同步已發(fā)送狀態(tài))狀態(tài)。TCP規(guī)定，SYN報(bào)文段(SYN=1的報(bào)文段)不能攜帶數(shù)據(jù)，但需要消耗掉一個(gè)序號(hào)。

3、TCP服務(wù)器收到請(qǐng)求報(bào)文后，如果同意連接，則發(fā)出確認(rèn)報(bào)文。確認(rèn)報(bào)文中應(yīng)該 ACK=1，SYN=1，確認(rèn)號(hào)是ack=x+1，同時(shí)也要為自己初始化一個(gè)序列號(hào) seq=y，此時(shí)，TCP服務(wù)器進(jìn)程進(jìn)入了SYN-RCVD(同步收到)狀態(tài)。這個(gè)報(bào)文也不能攜帶數(shù)據(jù)，但是同樣要消耗一個(gè)序號(hào)。

4、TCP客戶進(jìn)程收到確認(rèn)后，還要向服務(wù)器給出確認(rèn)。確認(rèn)報(bào)文的ACK=1，ack=y+1，自己的序列號(hào)seq=x+1，此時(shí)，TCP連接建立，客戶端進(jìn)入ESTABLISHED(已建立連接)狀態(tài)。TCP規(guī)定，ACK報(bào)文段可以攜帶數(shù)據(jù)，但是如果不攜帶數(shù)據(jù)則不消耗序號(hào)。

5、當(dāng)服務(wù)器收到客戶端的確認(rèn)后也進(jìn)入ESTABLISHED狀態(tài)，此后雙方就可以開(kāi)始通信了。

四次揮手

1、客戶端進(jìn)程發(fā)出連接釋放報(bào)文，并且停止發(fā)送數(shù)據(jù)。釋放數(shù)據(jù)報(bào)文首部，F(xiàn)IN=1，其序列號(hào)為seq=u(等于前面已經(jīng)傳送過(guò)來(lái)的數(shù)據(jù)的最后一個(gè)字節(jié)的序號(hào)加1)，此時(shí)，客戶端進(jìn)入FIN-WAIT-1(終止等待1)狀態(tài)。TCP規(guī)定，F(xiàn)IN報(bào)文段即使不攜帶數(shù)據(jù)，也要消耗一個(gè)序號(hào)。

2、服務(wù)器收到連接釋放報(bào)文，發(fā)出確認(rèn)報(bào)文，ACK=1，ack=u+1，并且?guī)献约旱男蛄刑?hào)seq=v，此時(shí)，服務(wù)端就進(jìn)入了CLOSE-WAIT(關(guān)閉等待)狀態(tài)。TCP服務(wù)器通知高層的應(yīng)用進(jìn)程，客戶端向服務(wù)器的方向就釋放了，這時(shí)候處于半關(guān)閉狀態(tài)，即客戶端已經(jīng)沒(méi)有數(shù)據(jù)要發(fā)送了，但是服務(wù)器若發(fā)送數(shù)據(jù)，客戶端依然要接受。這個(gè)狀態(tài)還要持續(xù)一段時(shí)間，也就是整個(gè)CLOSE-WAIT狀態(tài)持續(xù)的時(shí)間。

3、客戶端收到服務(wù)器的確認(rèn)請(qǐng)求后，此時(shí)，客戶端就進(jìn)入FIN-WAIT-2(終止等待2)狀態(tài)，等待服務(wù)器發(fā)送連接釋放報(bào)文(在這之前還需要接受服務(wù)器發(fā)送的最后的數(shù)據(jù))。

4、服務(wù)器將最后的數(shù)據(jù)發(fā)送完畢后，就向客戶端發(fā)送連接釋放報(bào)文，F(xiàn)IN=1，ack=u+1，由于在半關(guān)閉狀態(tài)，服務(wù)器很可能又發(fā)送了一些數(shù)據(jù)，假定此時(shí)的序列號(hào)為seq=w，此時(shí)，服務(wù)器就進(jìn)入了LAST-ACK(最后確認(rèn))狀態(tài)，等待客戶端的確認(rèn)。

5、客戶端收到服務(wù)器的連接釋放報(bào)文后，必須發(fā)出確認(rèn)，ACK=1，ack=w+1，而自己的序列號(hào)是seq=u+1，此時(shí)，客戶端就進(jìn)入了TIME-WAIT(時(shí)間等待)狀態(tài)。注意此時(shí)TCP連接還沒(méi)有釋放，必須經(jīng)過(guò)2∗ *∗MSL(最長(zhǎng)報(bào)文段壽命)的時(shí)間后，當(dāng)客戶端撤銷相應(yīng)的TCB后，才進(jìn)入CLOSED狀態(tài)。

6、服務(wù)器只要收到了客戶端發(fā)出的確認(rèn)，立即進(jìn)入CLOSED狀態(tài)。同樣，撤銷TCB后，就結(jié)束了這次的TCP連接。可以看到，服務(wù)器結(jié)束TCP連接的時(shí)間要比客戶端早一些。

第四章常見(jiàn)算法

十種常見(jiàn)排序算法可以分為兩大類：

非線性時(shí)間比較類排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此稱為非線性時(shí)間比較類排序。

線性時(shí)間非比較類排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此稱為線性時(shí)間非比較類排序。

算法優(yōu)劣評(píng)價(jià)術(shù)語(yǔ)

穩(wěn)定性:

穩(wěn)定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面;

不穩(wěn)定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能會(huì)出現(xiàn)在 b 的后面;

排序方式:

內(nèi)排序：所有排序操作都在內(nèi)存中完成，占用常數(shù)內(nèi)存，不占用額外內(nèi)存。

外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤(pán)中，而排序通過(guò)磁盤(pán)和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行，占用額外內(nèi)存。

復(fù)雜度:

時(shí)間復(fù)雜度: 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。

空間復(fù)雜度: 運(yùn)行完一個(gè)程序所需內(nèi)存的大小。

至于各種算法的原理以及代碼實(shí)現(xiàn)，由于太多并且比較復(fù)雜，不在本文列出。但推薦兩本入門(mén)的書(shū)：《啊哈!算法》、《大話數(shù)據(jù)結(jié)構(gòu)》。電子版我會(huì)發(fā)在交流群里。

排序算法很多，嵌入式要求的不會(huì)太多，你會(huì)冒泡排序、快速排序、插入排序就可以解決很多問(wèn)題。難的比如動(dòng)態(tài)規(guī)劃問(wèn)題，圖的路徑問(wèn)題，嵌入式考的比較少，純軟才會(huì)考這些。(大公司和獨(dú)角獸公司考的會(huì)相對(duì)難一些)