編碼
##ASCLL碼
ASCII碼（American Standard Code for Information Interchange，美國信息交換標準代碼）是一種基于拉丁字母的字符編碼方案，主要用于表示文本數據。ASCII碼包含128個字符（0-127），包括控制字符（如換行、回車等）和可打印字符（如字母、數字、標點符號等）。在C++中，字符和字符串的處理是基礎編程的一個重要部分。下面是C++中與ASCII碼相關的一些詳細內容。
ASCII字符和編碼
以下是部分常用的ASCII字符及其對應的十進制和十六進制表示：
| 字符 | 十進制 | 十六進制 | 字符 | 十進制 | 十六進制 |
|---|---|---|---|---|---|
| ‘A’ | 65 | 0x41 | ‘a’ | 97 | 0x61 |
| ‘B’ | 66 | 0x42 | ‘b’ | 98 | 0x62 |
| ‘Z’ | 90 | 0x5A | ‘z’ | 122 | 0x7A |
| … | … | … | … | … | … |
| ‘0’ | 48 | 0x30 | ‘9’ | 57 | 0x39 |
| ’ ’ | 32 | 0x20 | ‘!’ | 33 | 0x21 |
| ‘\n’ | 10 | 0x0A | ‘\r’ | 13 | 0x0D |
在C++中使用ASCII碼
字符到ASCII碼轉換
可以使用C++的int強制轉換操作符將字符轉換為對應的ASCII碼值：
#include <iostream>
using namespace std;int main() {char ch = 'A';int asciiValue = (int)ch;cout << "ASCII value of " << ch << " is " << asciiValue << endl;return 0;
}
ASCII碼到字符轉換
同樣地，可以使用char強制轉換操作符將整數（ASCII碼值）轉換為對應的字符：
#include <iostream>
using namespace std;int main() {int asciiValue = 65;char ch = (char)asciiValue;cout << "Character for ASCII value " << asciiValue << " is " << ch << endl;return 0;
}
使用字符函數
C++標準庫提供了一些字符處理函數，可以直接操作ASCII碼：
isalpha(int c): 判斷字符是否為字母。isdigit(int c): 判斷字符是否為數字。isupper(int c): 判斷字符是否為大寫字母。islower(int c): 判斷字符是否為小寫字母。toupper(int c): 將字符轉換為大寫。tolower(int c): 將字符轉換為小寫。
#include <iostream>
#include <cctype>
using namespace std;int main() {char ch = 'a';if (isalpha(ch)) {cout << ch << " is a letter." << endl;}if (isdigit(ch)) {cout << ch << " is a digit." << endl;}cout << "Uppercase of " << ch << " is " << (char)toupper(ch) << endl;cout << "Lowercase of " << ch << " is " << (char)tolower(ch) << endl;return 0;
}
示例程序
下面是一個示例程序，展示如何遍歷字符串并打印每個字符的ASCII碼值：
#include <iostream>
#include <string>
using namespace std;int main() {string str = "Hello, World!";for (char ch : str) {cout << "Character: " << ch << ", ASCII: " << (int)ch << endl;}return 0;
}
這個程序會輸出每個字符及其對應的ASCII碼值。
通過這些方法和示例，你可以在C++程序中有效地使用和處理ASCII碼。
##格雷碼
格雷碼（Gray code），又稱格雷數碼或反射二進制碼（Reflected Binary Code），是一種二進制數字編碼系統，其中連續的兩個數值僅有一個位元的差異。它的特點是在轉換相鄰的數值時，只會有一個位元發生改變，這種性質使得格雷碼在許多應用中特別有用，例如減少誤碼率、減少機械震動以及數字信號處理等領域。
與普通的二進制碼相比，格雷碼的優點在于減少了數值之間由于位元變化而引起的誤解。這種碼的名稱來自發明者法蘭克·格雷（Frank Gray），他于1947年發明了這種編碼系統。
以下是格雷碼的幾個關鍵特點和應用：
特點：
- 最小變化：相鄰的兩個格雷碼數值之間只有一位二進制位不同，這減少了變化時可能產生的錯誤。
- 對稱性：格雷碼序列是對稱的，比如 3 位的格雷碼序列是自反的。
- 無權碼：格雷碼不像標準二進制碼那樣每一位有明確的權值，它的每一位之間的關系更復雜。
生成方法：
有兩種主要的方法生成格雷碼：反射法和二進制轉換法。
反射法：
- 從一位的格雷碼開始：0, 1。
- 每次通過反射生成下一個位數的格雷碼：
- 將現有的格雷碼序列按原順序排列，并在每個數前面加上0。
- 再將現有的格雷碼序列按反序排列，并在每個數前面加上1。
例如，生成三位格雷碼：
- 一位格雷碼：0, 1
- 二位格雷碼：00, 01, 11, 10
- 三位格雷碼：000, 001, 011, 010, 110, 111, 101, 100
二進制轉換法：
給定一個普通的二進制數，可以將其轉換為格雷碼：
- 保留二進制數的最高位。
- 從最高位開始，將每一位與其前一位進行異或操作，結果即為格雷碼。
例如，將二進制數 1011 轉換為格雷碼：
- 保留最高位：1
- 第二位與第一位異或：1 ⊕ 0 = 1
- 第三位與第二位異或：0 ⊕ 1 = 1
- 第四位與第三位異或：1 ⊕ 0 = 1
所以，1011 的格雷碼為 1110。
應用：
- 模擬數字信號轉換：在模數轉換器中，格雷碼可以減少由于多位同時變化引起的錯誤。
- 機械編碼器：格雷碼在旋轉編碼器中很有用，因為它能確保在機械運動過程中每次只有一位變化，減少誤差。
- 錯誤檢測和糾正：格雷碼由于其最小變化特性，常用于錯誤檢測和糾正領域。
通過上述特性和應用，格雷碼在數字系統設計、編碼理論以及一些特定的硬件實現中都發揮了重要作用。
##哈夫曼編碼
哈夫曼編碼是一種高效的無損數據壓縮算法，通過使用不同長度的二進制編碼來表示不同頻率的字符。以下是哈夫曼編碼的詳細步驟：
1. 統計字符頻率
首先，統計待壓縮數據中每個字符出現的頻率。例如，假設我們要壓縮的字符串是 ABRACADABRA，我們可以得到如下字符頻率：
- A: 5
- B: 2
- R: 2
- C: 1
- D: 1
2. 構建優先隊列
將每個字符和其頻率作為一個節點，并將這些節點放入一個優先隊列（最小堆），優先隊列根據頻率排序。初始狀態下，每個節點都是一棵單節點的樹。
3. 構建哈夫曼樹
通過以下步驟構建哈夫曼樹：
- 從優先隊列中取出兩個頻率最小的節點（樹）。
- 創建一個新節點，其頻率是這兩個節點頻率之和。
- 將這兩個節點作為新節點的子節點，新節點的頻率是這兩個節點頻率之和。
- 將新節點插入優先隊列。
- 重復上述步驟，直到優先隊列中只剩下一個節點。這個節點就是哈夫曼樹的根節點。
以 ABRACADABRA 為例，構建哈夫曼樹的過程如下：
- 初始節點: [A: 5, B: 2, R: 2, C: 1, D: 1]
- 第一次合并: [A: 5, B: 2, R: 2, CD: 2] （C 和 D 合并）
- 第二次合并: [A: 5, BR: 4, CD: 2] （B 和 R 合并）
- 第三次合并: [A: 5, BRC: 6] （CD 和 BR 合并）
- 第四次合并: [ABRC: 11] （A 和 BRC 合并）
4. 生成哈夫曼編碼
從根節點開始，為左子節點分配0，為右子節點分配1。這樣，每個葉子節點（字符）從根節點到葉子節點路徑上的0和1串聯起來就構成了該字符的哈夫曼編碼。
以構建的哈夫曼樹為例：
- A: 0
- B: 101
- R: 100
- C: 110
- D: 111
5. 編碼
將原始數據中的每個字符用其對應的哈夫曼編碼替換。例如，字符串 ABRACADABRA 可以編碼為：
A B R A C A D A B R A
0 101 100 0 110 0 111 0 101 100 0
編碼后的二進制串為：0101100011010001110100110100。
6. 解碼
解碼時，根據哈夫曼樹，從根節點開始讀取編碼，遇到0則向左，遇到1則向右，直到到達葉子節點，從葉子節點得到一個字符，然后返回根節點繼續解碼下一個字符。這樣可以準確地將編碼的二進制串還原為原始字符串。
通過上述過程，哈夫曼編碼利用字符的頻率信息生成了高效的二進制編碼，實現了無損數據壓縮。
7. 應用
1. 文件壓縮
哈夫曼編碼是很多文件壓縮算法的核心組件，例如ZIP、GZIP、7z等。通過對文件中字符的頻率進行分析，哈夫曼編碼可以生成最優的編碼表，減少文件的存儲空間。
2. 圖像壓縮
在圖像壓縮中，特別是無損壓縮格式如PNG，哈夫曼編碼被用于壓縮圖像中的像素數據。它通過減少圖像數據的冗余，提高存儲和傳輸的效率。
3. 視頻壓縮
在視頻壓縮格式中，如MPEG和H.264，哈夫曼編碼用于對視頻數據進行無損壓縮。它在減少視頻文件大小的同時，保持高質量的視頻輸出。
4. 音頻壓縮
在音頻壓縮中，哈夫曼編碼用于無損音頻格式（如FLAC）和有損音頻格式（如MP3）。通過對音頻樣本數據進行編碼，減少音頻文件的大小。
5. 數據傳輸
在數據傳輸過程中，哈夫曼編碼被用來減少數據包的大小，提高傳輸效率。它在網絡通信協議中也有所應用，特別是在帶寬有限的環境中。
6. 編譯器設計
哈夫曼編碼在編譯器設計中用于優化符號表和編碼。它可以通過對程序中出現頻率高的符號進行壓縮，減少編譯結果的大小。
7. 信息檢索
在信息檢索系統中，哈夫曼編碼用于壓縮索引文件和倒排索引，提高查詢效率和減少存儲空間。
8. DNA序列壓縮
在生物信息學中，哈夫曼編碼用于壓縮DNA序列數據。由于DNA序列中存在大量重復數據，哈夫曼編碼可以有效減少序列的存儲空間。
--學習記錄之迭代器與生成器（上）)
