C++數(shù)據(jù)結(jié)構(gòu) 小結(jié)

重點回顧

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

Q & A

為什么哈希表同時包含線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)？

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

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

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