前端-計算機基礎

前端-計算機基礎一、網(wǎng)絡#1UDP面向報文UDP是一個面向報文（報文可以理解為一段段的數(shù)據(jù)）的協(xié)議。意思就是UDP只是報文的搬運工,不會對報文進行任何拆分和拼接操作具體來說在發(fā)送端，應用層將數(shù)據(jù)傳遞給傳輸層的UDP協(xié)議，UDP只會給數(shù)據(jù)增加一個UDP頭標識下是UDP協(xié)議，然后就傳遞給網(wǎng)絡層了在接收端，網(wǎng)絡層將數(shù)據(jù)傳遞給傳輸層，UDP只去除IP報文頭就傳遞給應用層，不會任何拼接操作不可靠性UDP是無連接的，也就是說通信不需要建立和斷開連接。UDP也是不可靠的。協(xié)議收到什么數(shù)據(jù)就傳遞什么數(shù)據(jù)，并且也不會備份數(shù)據(jù),對方能不能收到是不關心的UDP沒有擁塞控制，一直會以恒定的速度發(fā)送數(shù)據(jù)。即使網(wǎng)絡條件不好，也不會對發(fā)送速率進行調整。這樣實現(xiàn)的弊端就是在網(wǎng)絡條件不好的情況下可能會導致丟包，但是優(yōu)點也很明顯，在某些實時性要求高的場景（比如電話會議）就需要使用UDP而不是TCP高效?因為UDP沒有TCP那么復雜，需要保證數(shù)據(jù)不丟失且有序到達。所以UDP的頭部開銷小，只有八字節(jié)，相比TCP的至少二十字節(jié)要少得多，在傳輸數(shù)據(jù)報文時是很高效的UDPHeader頭部包含了以下幾個數(shù)據(jù)兩個十六位的端口號，分別為源端口（可選字段）和目標端口整個數(shù)據(jù)報文的長度整個數(shù)據(jù)報文的檢驗和（IPv4可選字段），該字段用于發(fā)現(xiàn)頭部信息和數(shù)據(jù)中的錯誤傳輸方式UDP不止支持一對一的傳輸方式，同樣支持一對多，多對多，多對一的方式，也就是說UDP提供了單播，多播，廣播的功能#2TCP2.1頭部TCP頭部比UDP頭部復雜的多TCPHeader對于TCP頭部來說，以下幾個字段是很重要的Sequencenumber,這個序號保證了TCP傳輸?shù)膱笪亩际怯行虻模瑢Χ丝梢酝ㄟ^序號順序的拼接報文AcknowledgementNumber,這個序號表示數(shù)據(jù)接收端期望接收的下一個字節(jié)的編號是多少，同時也表示上一個序號的數(shù)據(jù)已經(jīng)收到WindowSize,窗口大小，表示還能接收多少字節(jié)的數(shù)據(jù)，用于流量控制標識符URG=1:該字段為一表示本數(shù)據(jù)報的數(shù)據(jù)部分包含緊急信息，是一個高優(yōu)先級數(shù)據(jù)報文，此時緊急指針有效。緊急數(shù)據(jù)一定位于當前數(shù)據(jù)包數(shù)據(jù)部分的最前面，緊急指針標明了緊急數(shù)據(jù)的尾部。ACK=1:該字段為一表示確認號字段有效。此外，TCP還規(guī)定在連接建立后傳送的所有報文段都必須把ACK置為一PSH=1：該字段為一表示接收端應該立即將數(shù)據(jù)push給應用層，而不是等到緩沖區(qū)滿后再提交。RST=1:該字段為一表示當前TCP連接出現(xiàn)嚴重問題，可能需要重新建立TCP連接，也可以用于拒絕非法的報文段和拒絕連接請求。SYN=1:當SYN=1,ACK=0時，表示當前報文段是一個連接請求報文。當SYN=1,ACK=1時，表示當前報文段是一個同意建立連接的應答報文。FIN=1:該字段為一表示此報文段是一個釋放連接的請求報文

2.2狀態(tài)機HTTP是無連接的，所以作為下層的TCP協(xié)議也是無連接的，雖然看似TCP將兩端連接了起來，但是其實只是兩端共同維護了一個狀態(tài)■■■Aunusualevent><cbem/receivefpalhAservef/senderpath(Start)LISTEN/-CONNECT6YN(Step1ofthe3handshake)CLOSE/-CLOSE/-(Step2ofthe3-way-handshake)SYN/SYN+ACKRECEIVEDDataexchangeoccurs■■■Aunusualevent><cbem/receivefpalhAservef/senderpath(Start)LISTEN/-CONNECT6YN(Step1ofthe3handshake)CLOSE/-CLOSE/-(Step2ofthe3-way-handshake)SYN/SYN+ACKRECEIVEDDataexchangeoccursLISTENSEND/SYNSYN/SYN+ACK(simultaneousopen)SYN

SENTESTABLISHED(Step3ofthe3-way-handshake)SYN+ACK/ACKCLOS日臼NCLOS日臼NCLOS日FINFIN/ACKAN/ACKFINWAIT1]RN+ACK/ACKACKAFINWAIT2FIN/ACKActiveCLOSECLOSINGACK/-=AN/ACKFINWAIT1]RN+ACK/ACKACKAFINWAIT2FIN/ACKActiveCLOSECLOSINGACK/-=TIMEWAITTimeout(Gobacktostart)[CLOSEDTCP的狀態(tài)機是很復雜的，并且與建立斷開連接時的握手息息相關，接下來就來詳細描述下兩種握手。在這之前需要了解一個重要的性能指標RTTo該指標表示發(fā)送端發(fā)送數(shù)據(jù)到接收到對端數(shù)據(jù)所需的往返時間建立連接三次握手ClientServerClient在TCP協(xié)議中，主動發(fā)起請求的一端為客戶端，被動連接的一端稱為服務端。不管是客戶端還是服務端，TCP連接建立完后都能發(fā)送和接收數(shù)據(jù)，所以TCP也是一個全雙工的協(xié)議。起初，兩端都為CLOSED狀態(tài)。在通信開始前，雙方都會創(chuàng)建TCB。服務器創(chuàng)建完TCB后遍進入LISTEN狀態(tài)，此時開始等待客戶端發(fā)送數(shù)據(jù)第一次握手客戶端向服務端發(fā)送連接請求報文段。該報文段中包含自身的數(shù)據(jù)通訊初始序號。請求發(fā)送后，客戶端便進入SYN-SENT狀態(tài)，x表示客戶端的數(shù)據(jù)通信初始序號。第二次握手服務端收到連接請求報文段后，如果同意連接，則會發(fā)送一個應答，該應答中也會包含自身的數(shù)據(jù)通訊初始序號，發(fā)送完成后便進入SYN-RECEIVED狀態(tài)。第三次握手當客戶端收到連接同意的應答后，還要向服務端發(fā)送一個確認報文。客戶端發(fā)完這個報文段后便進入ESTABLISHED狀態(tài)，服務端收到這個應答后也進入ESTABLISHED狀態(tài)，此時連接建立成功。PS:第三次握手可以包含數(shù)據(jù)，通過TCP快速打開（TFO）技術。其實只要涉及到握手的協(xié)議，都可以使用類似TFO的方式，客戶端和服務端存儲相同cookie,下次握手時發(fā)出cookie達到減少RTT的目的你是否有疑惑明明兩次握手就可以建立起連接，為什么還需要第三次應答？因為這是為了防止失效的連接請求報文段被服務端接收，從而產生錯誤

可以想象如下場景。客戶端發(fā)送了一個連接請求A,但是因為網(wǎng)絡原因造成了超時，這時TCP會啟動超時重傳的機制再次發(fā)送一個連接請求B。此時請求順利到達服務端，服務端應答完就建立了請求。如果連接請求A在兩端關閉后終于抵達了服務端，那么這時服務端會認為客戶端又需要建立TCP連接，從而應答了該請求并進入ESTABLISHED狀態(tài)。此時客戶端其實是CLOSED狀態(tài)，那么就會導致服務端一直等待，造成資源的浪費PS:在建立連接中，任意一端掉線，TCP都會重發(fā)SYN包，一般會重試五次，在建立連接中可能會遇到SYNFLOOD攻擊。遇到這種情況你可以選擇調低重試次數(shù)或者干脆在不能處理的情況下拒絕請求斷開鏈接四次握手InitiatorReceiverESTABLISHEDconnectionCLOSE_WAITpassivecloseLAST_ACKCLOSED第一次握手若客戶端A認為數(shù)據(jù)發(fā)送完成，則它需要向服務端B發(fā)送連接釋放請求.第二次握手B收到連接釋放請求后，會告訴應用層要釋放TCP鏈接。然后會發(fā)送ACK包，并進入CLOSE_WAIT狀態(tài)，表示A到B的連接已經(jīng)釋放，不接收A發(fā)的數(shù)據(jù)了。但是因為TCP連接時雙向的，后以B仍舊可以發(fā)送數(shù)據(jù)給A。第三次握手B如果此時還有沒發(fā)完的數(shù)據(jù)會繼續(xù)發(fā)送，完畢后會向A發(fā)送連接釋放請求，然后B便進入LASTACK狀態(tài)。PS：通過延遲確認的技術（通常有時間限制，否則對方會誤認為需要重傳），可以將第二次和第三次握手合并，延遲ACK包的發(fā)送。第四次握手A收到釋放請求后，向B發(fā)送確認應答，此時A進入TIME-WAIT狀態(tài)。該狀態(tài)會持續(xù)2MSL（最大段生存期，指報文段在網(wǎng)絡中生存的時間，超時會被拋棄）時間，若該時間段內沒有B的重發(fā)請求的話，就進入CLOSED狀態(tài)。當B收到確認應答后，也便進入CLOSED狀態(tài)。為什么A要進入TIME-WAIT狀態(tài)，等待2MSL時間后才進入CLOSED狀態(tài)？為了保證B能收到A的確認應答。若A發(fā)完確認應答后直接進入CLOSED狀態(tài)，如果確認應答因為網(wǎng)絡問題一直沒有到達，那么會造成B不能正常關閉3HTTPHTTP協(xié)議是個無狀態(tài)協(xié)議，不會保存狀態(tài)Post和Get的區(qū)另ljGet請求能緩存，Post不能Post相對Get安全一點點，因為Get請求都包含在URL里，且會被瀏覽器保存歷史紀錄，Post不會，但是在抓包的情況下都是一樣的。Post可以通過requestbody來傳輸比Get更多的數(shù)據(jù)，Get沒有這個技術URL有長度限制，會影響Get請求，但是這個長度限制是瀏覽器規(guī)定的，不是RFC規(guī)定的Post支持更多的編碼類型且不對數(shù)據(jù)類型限制常見狀態(tài)碼2XX成功2000K,表示從客戶端發(fā)來的請求在服務器端被正確處理204Nocontent,表示請求成功，但響應報文不含實體的主體部分205ResetContent,表示請求成功，但響應報文不含實體的主體部分，但是與204響應不同在于要求請求方重置內容206PartialContent,進行范圍請求3XX重定向301movedpermanently,永久性重定向，表示資源已被分配了新的URL302found,臨時性重定向，表示資源臨時被分配了新的URL303seeother,表示資源存在著另一個URL,應使用GET方法丁香獲取資源304notmodified,表示服務器允許訪問資源，但因發(fā)生請求未滿足條件的情況307temporaryredirect,臨時重定向，和302含義類似，但是期望客戶端保持請求方法不變向新的地址發(fā)出請求4XX客戶端錯誤400badrequest,請求報文存在語法錯誤401unauthorized,表示發(fā)送的請求需要有通過HTTP認證的認證信息403forbidden,表示對請求資源的訪問被服務器拒絕404notfound,表示在服務器上沒有找到請求的資源5XX服務器錯誤500internalsevererror,表示服務器端在執(zhí)行請求時發(fā)生了錯誤501NotImplemented,表示服務器不支持當前請求所需要的某個功能503serviceunavailable,表明服務器暫時處于超負載或正在停機維護，無法處理請求3.3HTTP首部通用字段作用Cache-Control控制緩存的行為Connection瀏覽器想要優(yōu)先使用的連接類型，比如keep-aliveDate創(chuàng)建報文時間Pragma報文指令Via代理服務器相關信息Transfer-Encoding傳輸編碼方式Upgrade要求客戶端升級協(xié)議Warning在內容中可能存在錯誤請求字段作用Accept能正確接收的媒體類型Accept-Charset能正確接收的字符集Accept-Encoding能正確接收的編碼格式列表Accept-Language能正確接收的語言列表Expect期待服務端的指定行為From請求方郵箱地址Host服務器的域名If-Match兩端資源標記比較

If-Modified-SinceIf-None-MatchUser-AgentMax-ForwardsProxy-AuthorizationRangeRefererTE響應字段Accept-RangesAgeETagLocationProxy-AuthenticateServerWWW-Authenticate實體字段AllowContent-EncodingContent-LanguageContent-LengthContent-Location本地資源未修改返回304（比較時間）本地資源未修改返回304（比較標記）客戶端信息限制可被代理及網(wǎng)關轉發(fā)的次數(shù)向代理服務器發(fā)送驗證信息請求某個內容的一部分表示瀏覽器所訪問的前一個頁面?zhèn)鬏斁幋a方式作用是否支持某些種類的范圍資源在代理緩存中存在的時間資源標識客戶端重定向到某個URL向代理服務器發(fā)送驗證信息服務器名字獲取資源需要的驗證信息作用資源的正確請求方式內容的編碼格式內容使用的語言requestbody長度返回數(shù)據(jù)的備用地址Content-MD5Base64加密格式的內容MD5檢驗值Content-RangeContent-TypeExpiresLast_modified內容的位置范圍內容的媒體類型內容的過期時間內容的最后修改時間#4DNSDNS的作用就是通過域名查詢到具體的IP.因為IP存在數(shù)字和英文的組合（IPv6）,很不利于人類記憶，所以就出現(xiàn)了域名。你可以把域名看成是某個IP的別名，DNS就是去查詢這個別名的真正名稱是什么在TCP握手之前就已經(jīng)進行了DNS查詢，這個查詢是操作系統(tǒng)自己做的。當你在瀏覽器中想訪問時，會進行一下操作操作系統(tǒng)會首先在本地緩存中查詢沒有的話會去系統(tǒng)配置的DNS服務器中查詢如果這時候還沒得話，會直接去DNS根服務器查詢，這一步查詢會找出負責com這個一級域名的服務器然后去該服務器查詢google這個二級域名接下來三級域名的查詢其實是我們配置的，你可以給WWW這個域名配置一個IP,然后還可以給別的三級域名配置一個IP以上介紹的是DNS迭代查詢，還有種是遞歸查詢，區(qū)別就是前者是由客戶端去做請求，后者是由系統(tǒng)配置的DNS服務器做請求，得到結果后將數(shù)據(jù)返回給客戶端。二、數(shù)據(jù)結構2.1棧概念棧是一個線性結構，在計算機中是一個相當常見的數(shù)據(jù)結構。棧的特點是只能在某一端添加或刪除數(shù)據(jù)，遵循先進后出的原則實現(xiàn)每種數(shù)據(jù)結構都可以用很多種方式來實現(xiàn)，其實可以把?？闯墒菙?shù)組的一個子集，所以這里使用數(shù)組來實現(xiàn)classStack{constructor(){this.stack=[]}push(item){this.stack.push(item)}pop(){this.stack.pop()}peek(){returnthis.stack[this.getCount()-1]}getCount(){returnthis.stack.length)一isEmpty(){returnthis.getCount()===0)一}應用匹配括號，可以通過棧的特性來完成varisValid=function(s){letmap={'('：-1,1),：1,'['：-2,']'：2,-3,3)letstack=[]for(leti=0;i<s.length;i++){if(map[s[i]]<0){stack.push(s[i])}else{letlast=stack.pop()if(map[last]+map[s[i]]!=0)returnfalse}'')if(stack.length>0)returnfalsereturntrue}；#2.2隊列概念隊列一個線性結構，特點是在某一端添加數(shù)據(jù)，在另一端刪除數(shù)據(jù)，遵循先進先出的原則實現(xiàn)這里會講解兩種實現(xiàn)隊列的方式，分別是單鏈隊列和循環(huán)隊列? 單鏈隊列classQueue{constructor(){this.queue=[]}enQueue(item){this,queue.push(item)}deQueue(){returnthis.queue.shift()}getHeader(){returnthis.queue[0]}getLength(){returnthis.queue.length}一isEmpty(){returnthis.getLength()===0}「‘)因為單鏈隊列在出隊操作的時候需要0(n)的時間復雜度，所以引入了循環(huán)隊列。循環(huán)隊列的出隊操作平均是0(1)的時間復雜度? 循環(huán)隊列classSqQueue{constructor(length){this.queue=newArray(length+1)//隊頭this.first=0//隊尾this.last=0//當前隊列大小this.size=0}enQueue(item){//判斷隊尾+1是否為隊頭//如果是就代表需要擴容數(shù)組//%this.queue.length是為了防止數(shù)組越界if(this.first===(this.last+1)%this.queue.length){this.resize(this.getLength()*2+1)}一一this.queue[this.last]=itemthis.size++this.last=(this.last+1)%this.queue.length)一deQueue(){if(this.isEmpty()){throwError('Queueisempty'))letr=this.queue[this.first]this.queue[this.first]=nullthis.first=(this.first+1)%this.queue.lengththis,size--//判斷當前隊列大小是否過小//為了保證不浪費空間，在隊列空間等于總長度四分之一時//且不為2時縮小總長度為當前的一半if(this.size===this.getLength()/4&&this.getLength()/2!==0){this.resize(this.getLength()/2)}..一returnr)getHeader(){if(this.isEmptyO){throwError('Queueisempty*))returnthis.queue[this.first]}getLength(){returnthis.queue.length-1)isEmpty(){returnthis.first===this.last}resize(length){letq=newArray(length)for(leti=0;i<length;i++){q[i]=this.queue[(i+this.first)%this.queue.length]}this.queue=qthis.first=0this.last=this.size))#2.3鏈表概念鏈表是一個線性結構，同時也是一個天然的遞歸結構。鏈表結構可以充分利用計算機內存空間，實現(xiàn)靈活的內存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域,空間開銷比較大實現(xiàn)? 單向鏈表classNode{constructor(v,next){this.value=vthis.next=next})classLinkList{constructor(){//鏈表長度this.size=0//虛擬頭部this.dummyNode=newNode(null,null)}find(header,index,currentindex){if(index===currentindex)returnheaderreturnthis.find(header.next,index,currentindex+1)addNode(v,index){this.checkindex(index)//當往鏈表末尾插入時，prev.next為空//其他情況時，因為要插入節(jié)點，所以插入的節(jié)點//的next應該是prev.next//然后設置prev.next為插入的節(jié)點letprev=this.find(this.dummyNode,index,0)prev.next=newNode(v,prev.next)this.size++returnprev.next}insertNodeCv,index){returnthis.addNode(Vjindex))addToFirst(v){returnthis.addNode(v,0)}addToLast(v){returnthis?addNode(v,this.size)}removeNode(index,isLast){this.checkindex(index)index=isLast?index-1:indexletprev=this.find(this.dummyNodejindex,0)letnode=prev.nextprev.next=node.nextnode.next=nullthis,size-returnnode}removeFirstNode(){returnthis.removeNode(O))removeLastNode(){returnthis.removeNode(this.size,true)}checkindex(index){if(index<0||index>this.size)throwError(1Indexerror')}getNode(index){this.checkindex(index)if(this.isEmpty())returnreturnthis.find(this.dummyNode,index,0).next}isEmpty(){returnthis.size===0}getSize(){returnthis.size#2.4樹二叉樹樹擁有很多種結構，二叉樹是樹中最常用的結構，同時也是一個天然的遞歸結構。二叉樹擁有一個根節(jié)點，每個節(jié)點至多擁有兩個子節(jié)點，分別為：左節(jié)點和右節(jié)點。樹的最底部節(jié)點稱之為葉節(jié)點，當一顆樹的葉數(shù)量數(shù)量為滿時，該樹可以稱之為滿二叉樹二分搜索樹二分搜索樹也是二叉樹，擁有二叉樹的特性。但是區(qū)別在于二分搜索樹每個節(jié)點的值都比他的左子樹的值大，比右子樹的值小這種存儲方式很適合于數(shù)據(jù)搜索。如下圖所示，當需要查找6的時候，因為需要查找的值比根節(jié)點的值大，所以只需要在根節(jié)點的右子樹上尋找，大大提高了搜索效率5實現(xiàn)classNode{constructor(value){this.value=valuethis.left=nullthis.right=null)}classBST{constructor(){this.root=nullthis.size=0)getSize(){returnthis.size)isEmpty(){returnthis.size===0)addNode(v){this.root=this._addChild(this.root,v)//添加節(jié)點時，需要比較添加的節(jié)點值和當前//節(jié)點值的大小_addChild(nodeJv){if(!node){this.size++returnnewNode(v)}if(node.value>v){node.left=this._addChild(node.left,v)}elseif(node.value<v){node.right=this._addChild(node.right,v)}一一「returnnode以上是最基本的二分搜索樹實現(xiàn)，接下來實現(xiàn)樹的遍歷。對于樹的遍歷來說，有三種遍歷方法，分別是先序遍歷、中序遍歷、后序遍歷。三種遍歷的區(qū)別在于何時訪問節(jié)點。在遍歷樹的過程中，每個節(jié)點都會遍歷三次，分別是遍歷到自己，遍歷左子樹和遍歷右子樹。如果需要實現(xiàn)先序遍歷，那么只需要第一次遍歷到節(jié)點時進行操作即可//先序遍歷可用于打印樹的結構//先序遍歷先訪問根節(jié)點，然后訪問左節(jié)點，最后訪問右節(jié)點。preTraversal(){this._pre(this.root)}"_pre(node){'if(node){console.log(node.value)this._pre(node.left)this._pre(node.right)))//中序遍歷可用于排序//對于BST來說，中序遍歷可以實現(xiàn)一次遍歷就//得到有序的值//中序遍歷表示先訪問左節(jié)點，然后訪問根節(jié)點，最后訪問右節(jié)點。midTraversal(){this._mid(this,root)}一_mid(node){if(node){this._mid(node.left)console.log(node.value)this._mid(node.right)))//后序遍歷可用于先操作子節(jié)點//再操作父節(jié)點的場景//后序遍歷表示先訪問左節(jié)點，然后訪問右節(jié)點，最后訪問根節(jié)點。backTraversal(){this._back(this.root)}一_back(node){-if(node){this._back(node.left)this._back(node.right)console.log(node.value)以上的這幾種遍歷都可以稱之為深度遍歷，對應的還有種遍歷叫做廣度遍歷，也就是一層層地遍歷樹。對于廣度遍歷來說，我們需要利用之前講過的隊列結構來完成breadthTraversal(){if(ithis.root)returnnullletq=newQueue()//將根節(jié)點入隊q,enQueue(this.root)//循環(huán)判斷隊列是否為空，為空//代表樹遍歷完畢while(!q.isEmpty()){//將隊首出隊，判斷是否有左右子樹//有的話，就先左后右入隊letn=q.deQueue()console.log(n.value)if(n.left)q.enQueue(n.left)if(n.right)q.enQueue(n.right)}}接下來先介紹如何在樹中尋找最小值或最大數(shù)。因為二分搜索樹的特性，所以最小值一定在根節(jié)點的最左邊，最大值相反getMin(){returnthis.__getMin(this.root).value}一_getMin(node){if(inode.left)returnnodereturnthis._getMin(node.left)}一^getMax(){returnthis._getMax(this.root).value}一_getMax(node){if(!node.right)returnnodereturnthis.__getMin(node.right)向上取整和向下取整，這兩個操作是相反的，所以代碼也是類似的，這里只介紹如何向下取整。既然是向下取整，那么根據(jù)二分搜索樹的特性，值一定在根節(jié)點的左側。只需要一直遍歷左子樹直到當前節(jié)點的值不再大于等于需要的值，然后判斷節(jié)點是否還擁有右子樹。如果有的話，繼續(xù)上面的遞歸判斷floor(v){letnode=this._floor(this.root^v)returnnode?node.value:null}_floor(node,v){if(!node)returnnullif(node.value===v)returnv//如果當前節(jié)點值還比需要的值大，就繼續(xù)遞歸if(node.value>v){returnthis._floon(node.leftv)}//判斷當前節(jié)點是否擁有右子樹letright=this.__floon(node.right,v)if(right)returnrightreturnnode}排名，這是用于獲取給定值的排名或者排名第幾的節(jié)點的值，這兩個操作也是相反的，所以這個只介紹如何獲取排名第幾的節(jié)點的值。對于這個操作而言，我們需要略微的改造點代碼，讓每個節(jié)點擁有一個size屬性。該屬性表示該節(jié)點下有多少子節(jié)點(包含自身)classNode{constructor(value){this.value=valuethis.left=nullthis.right=null//修改代碼this.size=1)}//新增代碼_getSize(node){returnnode?node.size:0}_addChild(nodeJv){if(inode){returnnewNode(v))if(node.value>v){//修改代碼node.size++node.left=this._addChild(node.left,v)}elseif(node.value<v){//修改代碼node.size++node.right=this._addChild(node.right,v)returnnode)select(k){letnode=this._select(this.rootk)returnnode?node.value:null}_select(nodejk){if(inode)returnnull//先獲取左子樹下有幾個節(jié)點letsize=node.left?node.left.size:0//判斷size是否大于k//如果大于k,代表所需要的節(jié)點在左節(jié)點if(size>k)returnthis._select(node.left,k)//如果小于k,代表所需要的節(jié)點在右節(jié)點//注意這里需要重新計算k,減去根節(jié)點除了右子樹的節(jié)點數(shù)量if(size<k)returnthis._select(node.right,k-size-1)returnnode)接下來講解的是二分搜索樹中最難實現(xiàn)的部分：刪除節(jié)點。因為對于刪除節(jié)點來說，會存在以下幾種情況需要刪除的節(jié)點沒有子樹需要刪除的節(jié)點只有一條子樹需要刪除的節(jié)點有左右兩條樹對于前兩種情況很好解決，但是第三種情況就有難度了，所以先來實現(xiàn)相對簡單的操作：刪除最小節(jié)點，對于刪除最小節(jié)點來說，是不存在第三種情況的，刪除最大節(jié)點操作是和刪除最小節(jié)點相反的，所以這里也就不再贅述delectMin(){this.root=this._delectMin(this.root)console.log(this.root)}_delectMin(node){//一直遞歸左子樹//如果左子樹為空，就判斷節(jié)點是否擁有右子樹//有右子樹的話就把需要刪除的節(jié)點替換為右子樹if((node!=null)&!node.left)returnnode.rightnode.left=this._delectMin(node.left)//最后需要重新維濟下節(jié)點的'size'node.size=this._getSize(node.left)+this._getSize(node.right)+1returnnode}最后講解的就是如何刪除任意節(jié)點了。對于這個操作，T.Hibbard在1962年提出了解決這個難題的辦法，也就是如何解決第三種情況。?當遇到這種情況時，需要取出當前節(jié)點的后繼節(jié)點(也就是當前節(jié)點右子樹的最小節(jié)點)來替換需要刪除的節(jié)點。然后將需要刪除節(jié)點的左子樹賦值給后繼結點，右子樹刪除后繼結點后賦值給他。你如果對于這個解決辦法有疑問的話，可以這樣考慮。因為二分搜索樹的特性,父節(jié)點一定比所有左子節(jié)點大，比所有右子節(jié)點小。那么當需要刪除父節(jié)點時,勢必需要拿出一個比父節(jié)點大的節(jié)點來替換父節(jié)點。這個節(jié)點肯定不存在于左子樹，必然存在于右子樹。然后又需要保持父節(jié)點都是比右子節(jié)點小的，那么就可以取出右子樹中最小的那個節(jié)點來替換父節(jié)點delect(v){this.root=this._delect(this.rootv)}一_delect(nodejv){if(!node)returnnull//尋找的節(jié)點比當前節(jié)點小，去左子樹找if(node.value<v){node.right=this._delect(node.right,v)}elseif(node.value>v){//尋找的節(jié)點比當前節(jié)點大，去右子樹找node.left=this._delect(node.left,v)}else{//進入這個條件說明己經(jīng)找到節(jié)點//先判斷節(jié)點是否擁有擁有左右子樹中的一個//是的話，將子樹返回出去，這里和'_delectMin'的操作一樣if(!node.left)returnnode.rightif(!node.right)returnnode.left//進入這里，代表節(jié)點擁有左右子樹//先取出當前節(jié)點的后繼結點，也就是取當前節(jié)點右子樹的最小值letmin=this._getMin(node.right)//取出最小值后，刪除最小值//然后把刪除節(jié)點后的子樹賦值給最小值節(jié)點min.right=this._delectMin(node.right)//左子樹不動min.left=node.leftnode=min}//維護sizenode.size=this._getSize(node.left)+this._getSize(node.right)+1returnnode}2.5堆概念?堆通常是一個可以被看做一棵樹的數(shù)組對象。?堆的實現(xiàn)通過構造二叉堆，實為二叉樹的一種。這種數(shù)據(jù)結構具有以下性質。

任意節(jié)點小于（或大于）它的所有子節(jié)點堆總是一棵完全樹。即除了最底層,其他層的節(jié)點都被元素填滿，且最底層從左到右填入。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。優(yōu)先隊列也完全可以用堆來實現(xiàn)，操作是一模一樣的。實現(xiàn)大根堆堆的每個節(jié)點的左邊子節(jié)點索引是i*2+1,右邊是i*2+2,父節(jié)點是（i-1）/2。? 堆有兩個核心的操作，分別是shiftUp和shiftDown。前者用于添加元素，后者用于刪除根節(jié)點。shiftUp的核心思路是一路將節(jié)點與父節(jié)點對比大小，如果比父節(jié)點大，就和父節(jié)點交換位置。?? S—StoiE?@?。-黑瞄一Jr)swimup、?? S—StoiE?@?。-黑瞄一Jr)swimup、removethemaximum /^\ .(TJ!"—krytortmovt????-嗑六石、—violatesheaporder?%<7$ --removenode市Yr；????classMaxHeap{constructor(){this.heap=[]}size(){returnthis.heap.length)一w2?3w???Heapoperationssinkdownempty(){returnthis.size()==0}add(item){this,heap.push(item)this._shiftllp(this.size()-1)}一removeMax(){this._shiftDown(0)}一getParentlndex(k){returnparselnt((k-1)/2)}getLeftlndex(k){returnk*2+1)_shiftllp(k){一//如果當前節(jié)點比父節(jié)點大，就交換while(this.heap[k]>this.heap[this.getParentIndex(k)]){this._swap(k,this.getParentIndex(k))//將素引變成父節(jié)點k=this.getParentindex(k))一)_shiftDown(k){//交換首位并刪除末尾this?_swap(k,this.size()-1)this.heap.splice(this.size()-1,1)//判斷節(jié)點是否有左孩子，因為二叉堆的特性，有右必有左while(this.getLeftIndex(k)<this.size()){letj=this.getLeftlndex(k)//判斷是否有右孩子，并且右孩子是否大于左孩子if(j+1<this.size()&&this.heap[j+1]>this.heap[j])j++//判斷父節(jié)點是否已經(jīng)比子節(jié)點都大if(this.heap[k]>=this.heap[j])breakthis._swap(kJj)k=j)}_swap(left,right){letrightvalue=this.heap[right]this.heap[right]=this.heap[left]this.heap[left]=rightvalue#三、算法3.1時間復雜度通常使用最差的時間復雜度來衡量一個算法的好壞。常數(shù)時間0(1)代表這個操作和數(shù)據(jù)量沒關系，是一個固定時間的操作，比如說四則運算。對于一個算法來說，可能會計算出如下操作次數(shù)aN+1,N代表數(shù)據(jù)量。那么該算法的時間復雜度就是0(N)。因為我們在計算時間復雜度的時候，數(shù)據(jù)量通常是非常大的，這時候低階項和常數(shù)項可以忽略不計。當然可能會出現(xiàn)兩個算法都是0(N)的時間復雜度，那么對比兩個算法的好壞就要通過對比低階項和常數(shù)項了3.2位運算位運算在算法中很有用，速度可以比四則運算快很多。在學習位運算之前應該知道十進制如何轉二進制，二進制如何轉十進制。這里說明下簡單的計算方式十進制33可以看成是32+1,并且33應該是六位二進制的(因為33近似32,而32是2的五次方，所以是六位)，那么十進制33就是100001,只要是2的次方，那么就是1否則都為0那么二進制100001同理，首位是27,末位是2A0,相加得出33左移"10<<1//->20左移就是將二進制全部往左移動，1。在二進制中表示為101。，左移一位后變成10100，轉換為十進制也就是20,所以基本可以把左移看成以下公式a*(2人b)算數(shù)右移>>10>>1//->5算數(shù)右移就是將二進制全部往右移動并去除多余的右邊，10在二進制中表示為右移一位后變成轉換為十進制也就是5,所以基本可以把右移看成以下公式intv=a/(2Ab)右移很好用，比如可以用在二分算法中取中間值13>>1//->6按位操作?按位與每一位都為1,結果才為18&7//->0//1000&0111->0000->0?按位或其中一位為1,結果就是18|7//->15//1000|0111->1111->15?按位異或每一位都不同，結果才為18A7//->158A8//->0//1000A0111->1111->15//1000A1000->0000->0面試題：兩個數(shù)不使用四則運算得出和這道題中可以按位異或，因為按位異或就是不進位加法，8八8=0如果進位了，就是16了，所以我們只需要將兩個數(shù)進行異或操作，然后進位。那么也就是說兩個二進制都是1的位置，左邊應該有一個進位1,所以可以得出以下公式a+b=(aAb)+((a&b)?1),然后通過迭代的方式模擬加法functionsum(a,b){if(a==0)returnbif(b==0)returnaletnewA=aAbletnewB=(a&b)<<1returnsum(newAjnewB)}#3.3排序冒泡排序冒泡排序的原理如下，從第一個元素開始，把當前元素和下一個索引元素進行比較。如果當前元素大，那么就交換位置，重復操作直到比較到最后一個元素，那么此時最后一個元素就是該數(shù)組中最大的數(shù)。下一輪重復以上操作，但是此時最后一個元素已經(jīng)是最大數(shù)了，所以不需要再比較最后一個元素，只需要比較到length-1的位置

以下是實現(xiàn)該算法的代碼functionbubble(array){checkArray(array);for(leti=array.length-1;i>0;i--){〃從0到'length-1'遍歷for(letj=0;j<i;j++){if(array[j]>array[j+1])swap(array,j,j+1)))returnarray;該算法的操作次數(shù)是一個等差數(shù)列n+(n-1)+(n-2)+1,去掉常數(shù)項以后得出時間復雜度是0(n*n)插入排序入排序的原理如下。第一個元素默認是已排序元素，取出下一個元素和當前元素比較，如果當前元素大就交換位置。那么此時第一個元素就是當前的最小數(shù)，所以下次取出操作從第三個元素開始，向前對比，重復之前的操作

以下是實現(xiàn)該算法的代碼3626以下是實現(xiàn)該算法的代碼3626functioninsertion(array){checkArray(array);for(leti=1;i<array.length;i++){for(letj=i-1;j>=0&&array[j]>array[j+1];j--)swap(array,j,j+1)；)returnarray;}該算法的操作次數(shù)是一個等差數(shù)列n+(n-1)+(n-2)+1,去掉常數(shù)項以后得出時間復雜度是0(n*n)選擇排序選擇排序的原理如下。遍歷數(shù)組，設置最小值的索引為0,如果取出的值比當前最小值小，就替換最小值索引，遍歷完成后，將第一個元素和最小值索引上的值交換。如上操作后，第一個元素就是數(shù)組中的最小值，下次遍歷就可以從索引1開始重復上述操作

381536381536以下是實現(xiàn)該算法的代碼functionselection(array){checkArray(array);for(leti=0;i<array.length-1;i++){letminindex=i;for(letj=i+1;j<array.length;j++){minindex=array［j］<array［minlndex］?j:minindex;)一swap(array,i,minindex);}returnarray;)該算法的操作次數(shù)是一個等差數(shù)列n+(n-1)+(n-2)+1,去掉常數(shù)項以后得出時間復雜度是0(n*n)歸并排序歸并排序的原理如下。遞歸的將數(shù)組兩兩分開直到最多包含兩個元素，然后將數(shù)組排序合并，最終合并為排序好的數(shù)組。假設我有一組數(shù)組［3,1,2,8,9,7,6］,中間數(shù)索引是3,先排序數(shù)組［3,1,2,8］.在這個左邊數(shù)組上，繼續(xù)拆分直到變成數(shù)組包含兩個元素(如果數(shù)組長度是奇數(shù)的話，會有一個拆分數(shù)組只包含一個元素)。然后排序數(shù)組［3,1］和［2,8］,然后再排序數(shù)組［1,3,2,8］,這樣左邊數(shù)組就排序完成，然后按照以上思路排序右邊數(shù)組，最后將數(shù)組［1,2,3,8］和［6,7,9］排序

以下是實現(xiàn)該算法的代碼functionsort(array){checkArray(array);mergeSort(array,0,array.length-1);returnarray;}functionmergeSort(array,left,right){//左右索引相同說明已經(jīng)只有一個數(shù)if(left===right)return;//尊同于'left+(right-left)/2'//相比'(left+right)/2'來說更加安全，不會溢出//使用位運算是因為位運算比四則運算快letmid=parselnt(left+((right-left)>>1));mergeSort(array.,left,mid);mergeSort(array,mid+1,right);lethelp=[];leti=0;letpl=left;letp2=mid+1;while(pl<=mid&&p2<=right){help[i++]=array[pl]<array[p2]?array[pl++]:array[p2++];)'while(pl<=mid){help[i++]=array[pl++];}while(p2<=right){help[i++]=array[p2++];for(leti=0;i<help.length;i++){array[left+i]=help[i];)returnarray;}以上算法使用了遞歸的思想。遞歸的本質就是壓棧，每遞歸執(zhí)行一次函數(shù)，就將該函數(shù)的信息(比如參數(shù)，內部的變量，執(zhí)行到的行數(shù))壓棧，直到遇到終止條件，然后出棧并繼續(xù)執(zhí)行函數(shù)。對于以上遞歸函數(shù)的調用軌跡如下mergeSort(data,0,6)//mid=3mergeSort(data,0,3)//mid=1mergeSort(data,0,1)//mid=0mergeSortCdata,0,0)//遇到終止，回退到上一步mergeSort(data,1,1)//遇到終止，回退到上一步//排序pl=0,p2=mid+1=1//回退到'mergeSort(data,0,3)'執(zhí)行下一個遞歸mergeSort(2,3)//mid=2mergeSort(3,3)//遇到終止，回退到上一步//排序pl=2,p2=mid+1=3//回退到'mergeSort(data,0,3)'執(zhí)行合并邏輯//排序pl=p2=mid+1=2//執(zhí)行完畢回退//左邊數(shù)組排序完畢，右邊也是如上軌跡該算法的操作次數(shù)是可以這樣計算：遞歸了兩次，每次數(shù)據(jù)量是數(shù)組的一半，并且最后把整個數(shù)組迭代了一次，所以得出表達式2T(N/2)+T(N)(T代表時間，N代表數(shù)據(jù)量)。根據(jù)該表達式可以套用該公式得出時間復雜度為0(N*logN)快排

快排的原理如下。隨機選取一個數(shù)組中的值作為基準值，從左至右取值與基準值對比大小。比基準值小的放數(shù)組左邊，大的放右邊，對比完成后將基準值和第一個比基準值大的值交換位置。然后將數(shù)組以基準值的位置分為兩部分，繼續(xù)遞歸以上操作。以下是實現(xiàn)該算法的代碼functionsort(array){checkArray(array);quicksort(array,0,array.length-1);returnarray;}functionquicksort(arrayleft,right){if(left<right){swap(array,,right)//隨機取值，然后和末尾交換，這樣做比固定取一個位置的復雜度略低letindexs=part(array,parseInt(Math.random()*(right-left+1))+left,right);quicksort(arrayleft,indexs[0]);quickSortCarray^indexs[l]+1,right);}}functionpart(array,left,right){letless=left-1;letmore=right;while(left<more){if(array[left]<array[right]){//當前值比基準值小，'less'和'left'都加一++less;++left;}elseif(array[left]>array[right]){〃當前值比基準值大，將當前值和右邊的值交換//并且不改變'left',因為當前換過來的值還沒有判斷過大小swap(array,--more,left);}else{//和基準值相同，只移動下標left++;))//將基準值和比基準值大的第一個值交換位置//這樣數(shù)組就變成'[比基準值小，基準值，比基準值大]'swap(array,right,more);return[less,more];)該算法的復雜度和歸并排序是相同的，但是額外空間復雜度比歸并排序少，只需O(logN),并且相比歸并排序來說，所需的常數(shù)時間也更少面試題SortColors：該題目來自LeetCode,題目需要我們將[2,2,1,0]排序成[0,0,1,1,2,2],這個問題就可以使用三路快排的思想vansortcolors=function(nums){letleft=-1;letright=nums.length;leti=0;//下標如果遇到right,說明已經(jīng)排序完成while(i<right){if(nums[i]==0){swap(nums,i++,++left);}elseif(nums[i]==1){i++；}else{swap(nums,i,--right);)))；#3.4鏈表反轉單向鏈表該題目來自LeetCode,題目需要將一個單向鏈表反轉。思路很簡單，使用三個變量分別表示當前節(jié)點和當前節(jié)點的前后節(jié)點，雖然這題很簡單，但是卻是一道面試?？碱}vanreverseList=function(head){//判斷下變量邊界問題if(!head||!head.next)returnhead//初始設置為空，因為第一個節(jié)點反轉后就是尾部，尾部節(jié)點指向nullletpre=nullletcurrent=headletnext//判斷當前節(jié)點是否為空//不為空就先獲取當前節(jié)點的下一節(jié)點//然后把當前節(jié)點的next設為上一個節(jié)點//然后把current設為下一個節(jié)點，pre設為當前節(jié)點while(current){next=current.nextcurrent.next=prepre=currentcurrent=next)returnpre};3.5樹二叉樹的先序，中序，后序遍歷先序遍歷表示先訪問根節(jié)點，然后訪問左節(jié)點，最后訪問右節(jié)點。?中序遍歷表示先訪問左節(jié)點，然后訪問根節(jié)點，最后訪問右節(jié)點。后序遍歷表示先訪問左節(jié)點，然后訪問右節(jié)點，最后訪問根節(jié)點遞歸實現(xiàn)遞歸實現(xiàn)相當簡單，代碼如下functionTreeNode(val){this.val=val;this.left=this.right=null;}一vartraversal=function(root){if(root){//先序console.log(root);traversal(root,left);//中序//console.log(root);traversal(root.right);//后序//console.log(root);}}；對于遞歸的實現(xiàn)來說，只需要理解每個節(jié)點都會被訪問三次就明白為什么這樣實現(xiàn)了非遞歸實現(xiàn)非遞歸實現(xiàn)使用了棧的結構，通過