C++數據結構 小結

重點回顧

• 數據結構可以從邏輯結構和物理結構兩個角度進行分類。邏輯結構描述了數據元素之間的邏輯關系，而物理結構描述了數據在計算機內存中的存儲方式。
• 常見的邏輯結構包括線性、樹狀和網狀等。通常我們根據邏輯結構將數據結構分為線性（數組、鏈表、棧、隊列）和非線性（樹、圖、堆）兩種。哈希表的實現(xiàn)可能同時包含線性和非線性結構。
• 當程序運行時，數據被存儲在計算機內存中。每個內存空間都擁有對應的內存地址，程序通過這些內存地址訪問數據。
• 物理結構主要分為連續(xù)空間存儲（數組）和離散空間存儲（鏈表）。所有數據結構都是由數組、鏈表或兩者的組合實現(xiàn)的。
• 計算機中的基本數據類型包括整數 ?byte?、?short?、?int?、?long? ，浮點數 ?float?、?double? ，字符 ?char? 和布爾 ?boolean? 。它們的取值范圍取決于占用空間大小和表示方式。
• 原碼、反碼和補碼是在計算機中編碼數字的三種方法，它們之間是可以相互轉換的。整數的原碼的最高位是符號位，其余位是數字的值。
• 整數在計算機中是以補碼的形式存儲的。在補碼表示下，計算機可以對正數和負數的加法一視同仁，不需要為減法操作單獨設計特殊的硬件電路，并且不存在正負零歧義的問題。
• 浮點數的編碼由 1 位符號位、8 位指數位和 23 位分數位構成。由于存在指數位，浮點數的取值范圍遠大于整數，代價是犧牲了精度。
• ASCII 碼是最早出現(xiàn)的英文字符集，長度為 1 字節(jié)，共收錄 127 個字符。GBK 字符集是常用的中文字符集，共收錄兩萬多個漢字。Unicode 致力于提供一個完整的字符集標準，收錄世界內各種語言的字符，從而解決由于字符編碼方法不一致而導致的亂碼問題。
• UTF-8 是最受歡迎的 Unicode 編碼方法，通用性非常好。它是一種變長的編碼方法，具有很好的擴展性，有效提升了存儲空間的使用效率。UTF-16 和 UTF-32 是等長的編碼方法。在編碼中文時，UTF-16 比 UTF-8 的占用空間更小。Java 和 C# 等編程語言默認使用 UTF-16 編碼。

Q & A

為什么哈希表同時包含線性數據結構和非線性數據結構？

哈希表底層是數組，而為了解決哈希沖突，我們可能會使用“鏈式地址”（后續(xù)哈希表章節(jié)會講）。在拉鏈法中，數組中每個地址（桶）指向一個鏈表；當這個鏈表長度超過一定閾值時，又可能被轉化為樹（通常為紅黑樹）。因此，哈希表可能同時包含線性（數組、鏈表）和非線性（樹）數據結構。

?char? 類型的長度是 1 byte 嗎？

?char? 類型的長度由編程語言采用的編碼方法決定。例如，Java、JS、TS、C# 都采用 UTF-16 編碼（保存 Unicode 碼點），因此 char 類型的長度為 2 bytes 。