【考試向】資料結構筆記（樹及二元樹）
【考試向】資料結構筆記（樹及二元樹）歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～ 簡介（Introduction） Image Source：https://zh.wikipedia.org/zh-tw/%E6%A0%91_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84) 樹（Tree）資料結構是一種非線性資料結構，用來模擬具有階層性（Hierarchical）關係的資料。 一棵樹的基本構成由以下兩個要素組成： 節點（Node）：樹的基本組成單位，每個節點會包含資料（或鍵值），以及指向其子節點的指標。 邊（Edge / Link）：連接兩節點的線條，代表節點之間的關係，一棵有 $N$ 個節點的樹，必定會有 $N-1$ 條邊。 節點關係的術語 根節點（Root）：樹的最頂層節點，整棵樹只有一個根節點，且是唯一沒有父節點的節點。 如上圖中的節點 A 即根節點。 父節點（Parent）：若一個節點向下連接到其他節點，該節點就是那些節點的...
【計算機網路筆記】3.4 Principles of Reliable Data Transfer
【計算機網路筆記】3.4 Principles of Reliable Data TransferHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 Principles of Reliable Data Transfer（可靠資料傳輸的原理）該節定義了一個通用的可靠資料傳輸協定（rdt, reliable data transfer protocol）的「服務模型」與「實作介面」。 簡單來說，就是如何在底層網路可能會丟包、損壞資料的情況下，為上層應用程式提供一個資料保證不丟失、不損壞、按順序到達的傳輸管道。 為何需要可靠資料傳輸協定原因是我們所理想中的情形是：希望應用程式有一個可靠的通道，像在兩點之間接了一條完美的光纖，資料送進去，另一頭就完美地出來。 但現實上，底層...
【計算機網路筆記】3.3 Connectionless Transport: UDP
【計算機網路筆記】3.3 Connectionless Transport: UDPHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 回顧 UDPUDP（User Datagram Protocol，使用者資料包協定）只做了傳輸層最基本該做的事：把資料從一台電腦的某個程式，送到另一台電腦的某個程式，其他的它一概不管。 雖然 TCP 提供了可靠、有序的傳輸，但這些功能是有代價的（延遲、複雜度、連線建立時間）。 有些應用程式（如 DNS 查詢、即時語音、串流視訊）更在乎「速度」和「即時性」，對於偶爾掉幾個封包是可以容忍的，此時 TCP 的層層機制反而成了累贅，輕量級的 UDP 就派上用場了。 UDP 應用：即時影音串流、網路電話（VoIP，Voice over Inter...
【計算機網路筆記】3.2 Multiplexing and Demultiplexing
【計算機網路筆記】3.2 Multiplexing and DemultiplexingHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 簡介多工與解多工技術是一種將「主機對主機（Host-to-Host）」的傳輸服務，延伸轉化為「行程對行程（Process-to-Process）」傳輸服務的機制。 為什麼需要多工與解多工？假設有位使用者的電腦同時開著瀏覽器下載網頁、開著 FTP 傳檔案、還掛著兩個 Telnet 連線。 網路層（IP）只負責把資料包（Datagram）送到電腦（Host）門口。 在當電腦收到這個資料包時，它該如何知道這是要給瀏覽器的，還是給 FTP 的？ 此時就是傳輸層的工作了，傳輸層利用多工（Multiplexing）與解多工（Demultiple...
【計算機網路筆記】3.1 Introduction and Transport-Layer Services
【計算機網路筆記】3.1 Introduction and Transport-Layer ServicesHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 傳輸層簡介傳輸層（Transport Layer）位於應用層（Application Layer）之下，網路層（Network Layer）之上。 傳輸層的核心功能是為執行在不同主機（Host）上的應用程式行程（Application Processes）之間提供邏輯通訊（Logical Communication）。 所謂邏輯通訊：從應用程式的角度看，好像兩台主機是直接連在一起的，儘管中間隔著無數的路由器和連結。 3.1.1 Relationship Between Transport and Network ...
【計算機網路筆記】2.7 Socket Programming: Creating Network Applications
【計算機網路筆記】2.7 Socket Programming: Creating Network ApplicationsHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 複習：什麼是 Socket？ 簡單來說，Socket（插座）就是應用程式（Application）與網路（Network）之間的介面（Interface）。 Socket 的存在是為了把「網路層只做到主機對主機」提升成「傳輸層要做到行程（process）對行程」的溝通，並讓同一台主機上的許多應用程式能同時共用 TCP/UDP 而不互相搞混。 做比喻的話，行程（process）就像是房子，而 Socket 如同房子中的門。 當使用者想發訊息給別人，使用者會把訊息推出「門」（Socket）外，一旦出...
【計算機網路筆記】2.6 Video Streaming and Content Distribution Networks
【計算機網路筆記】2.6 Video Streaming and Content Distribution NetworksHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.6.1 Internet Video（網際網路視訊）在此探討的為預錄視訊串流（Streaming Stored Video）。 其運作模式是將預先錄製好的媒體（如電影、電視節目、UGC 影片）放置在伺服器上，使用者根據需求（On-demand）發送請求來觀看。 視訊本質上是連續的影像，資料量極其龐大，它是網際網路上對頻寬需求最高、對效能最敏感的應用類型之一。 其中所面臨的挑戰：如何在頻寬有限且會波動的網路環境中，傳送高位元率（High Bit Rate）的資料，並保持播放的流暢度。 術語解析 ...
【計算機網路筆記】2.5 Peer-to-Peer File Distribution
【計算機網路筆記】2.5 Peer-to-Peer File DistributionHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 P2P 架構與自我擴充性（Scalability）複習：什麼是 P2P？ 在傳統的主從式架構（Client-Server Architecture）中，伺服器必須承擔所有的上傳工作。 如果要發送一個檔案給 $N$ 個使用者，伺服器就必須把這個檔案傳送 $N$ 次，會導致伺服器的頻寬成為巨大的瓶頸。 在 P2P 架構（Peer-to-Peer Architecture）中，每一台參與的電腦被稱為 Peer（對等點）。 Peer 不僅僅是下載檔案，還會將已下載的檔案片段重新上傳給其他的 Peer。 為什麼 P2P 很重要？ 這個架構最關鍵...
【計算機網路筆記】2.4 DNS—The Internet’s Directory Service
【計算機網路筆記】2.4 DNS—The Internet’s Directory ServiceHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.4.1 Services Provided by DNS（由 DNS 提供的服務）什麼是 DNS？DNS（Domain Name System，網域名稱系統）就像是網際網路的「電話簿」，負責將人類好記的網址翻譯成電腦能理解的 IP 位址。 當在瀏覽器輸入 google.com 這種人類好記的網址時，電腦其實看不懂。 電腦需要透過 DNS 把網址翻譯成一串數字構成的 IP 位址（例如 142.250.190.46），才能正確連接到該網站的伺服器。 DNS 也是一個建立在應用層上的協定，它主要由兩部分組成： 分散式資料...
【計算機網路筆記】2.3 Electronic Mail in the Internet
【計算機網路筆記】2.3 Electronic Mail in the InternetHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 電子郵件系統的核心在於提供一種非同步（Asynchronous）的通訊方式。 什麼意思？就像傳統的郵政服務，寄信時，收件人不需要坐在家裡等，寄件人寫好信丟進郵筒，系統會負責傳遞到收件人的郵箱，對方有空時再開箱讀取。 電子郵件的出現打破了時間的限制，不需要通訊雙方同時在線（Always-on）也能交換資訊，且成本極低、速度快。 Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 147, Figure 2.14) 上圖中呈現一份網際網路郵件系統的高層...
【計算機網路筆記】2.2 The Web and HTTP
【計算機網路筆記】2.2 The Web and HTTPHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.2.1 Overview of HTTP（HTTP 的概觀）什麼是 HTTP？HTTP（HyperText Transfer Protocol），中譯「超文本傳輸協定」，是 Web 的核心應用層協定。 它定義了客戶端（Client）和伺服器（Server）之間「如何對話」的規則。 也規定了訊息的結構（語法）以及交換訊息的方式（語義）。 為什麼需要 HTTP？在 1990 年代初期，網際網路主要用於傳輸文字和文件。 為了讓這些文件（也稱為網頁，Web Pages）能在不同的電腦系統之間互相請求和傳送，需要一個通用的標準。 HTTP 即該標準，讓大家可用 Chr...
【計算機網路筆記】2.1 Principles of Network Applications
【計算機網路筆記】2.1 Principles of Network ApplicationsHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.1.1 Network Application Architectures（網路應用程式架構）在現代網路應用開發中，開發者通常會在以下兩種典範中擇一使用： 主從式架構（Client-Server Architecture） 對等式架構（Peer-to-Peer, P2P Architecture） 主從式架構（Client-Server Architecture）這是目前最常見、也最傳統的架構模式（例如 Web、Email）。 在此架構中會有永遠開啟的主機，稱之為伺服器（Server）。 伺服器會服務其他許多主機的請求...
【計算機網路筆記】1.5 Protocol Layers and Their Service Models
【計算機網路筆記】1.5 Protocol Layers and Their Service ModelsHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 1.5.1 Layered Architecture（分層架構）航空系統的比喻網際網路是一個非常複雜的系統，包含了應用程式、協定、端系統、封包交換機和各種連結層媒介。 為了理解這個複雜的系統，書中以航空系統作為比喻。 搭飛機的過程當中涉及了票務代理、行李檢查、登機口人員、機師、飛機、空中交通管制等。 若要把這個系統描述清楚，可依照「動作發生的順序」來分層： Image Source：Image Source：Computer Networking: A Top-Down Approach (8th ed., p....
【計算機網路筆記】1.4 Delay, Loss, and Throughput in Packet-Switched Networks
【計算機網路筆記】1.4 Delay, Loss, and Throughput in Packet-Switched NetworksHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 1.4.1 Overview of Delay in Packet-Switched Networks（封包交換網路中的延遲概述）該節核心概念：解釋封包從源頭（Source）經過一系列路由器（Routers）到達目的地（Destination）的過程中，為什麼會發生延遲（Delay），以及這些延遲是由哪些部分組成的。 一個封包在單一節點所經歷的延遲總和定義為四個主要部分的累加： 節點處理延遲（Nodal Processing Delay） 佇列延遲（Queuing Delay） 傳輸...
【計算機網路筆記】1.3 The Network Core
【計算機網路筆記】1.3 The Network CoreHello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 註：後來改成看第八版了，發現第七版在一些資訊蠻落後的。 1.3.1 Packet Switching（封包交換）基本概念與封包回顧 1.1若要寄一封很長的電子郵件或下載一個很大的高畫質影片，網路不會一次把整個巨大的檔案傳出去。 來源終端系統會將這些訊息切成較小的資料塊，這些資料塊被稱為封包（Packet）。 在來源與目的地終端系統之間，每個封包都會經過通訊連結（Communication Links）與封包交換（Packet Switches）設備，而封包交換設備主要有兩種類型： 路由器（router） 連結層交換器（link-layer switch） 封...