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

重點(diǎn)回顧

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

Q & A

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

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

?char? 類型的長(zhǎng)度是 1 byte 嗎？

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