摘要: 有一個二維數(shù)組，0表示路，-1表示墻，求其中任意兩點的最短路徑。
我們先看，怎么求一條路徑：求兩點路徑是一個數(shù)據(jù)結(jié)構(gòu)上的典型的迷宮問題，很多數(shù)據(jù)結(jié)構(gòu)的書上都有介紹，解決辦法如下：
從一點開始出發(fā)，向四個方向查找，每走一步，把走過的點的值+1(即本節(jié)點值+1)，防止重復(fù)行走，并把走過的點壓入堆棧(表示路徑)，如果遇到墻、或者已走過的點則不能前進，如果前方已經(jīng)無路可走，則返回，路徑退棧，這樣遞歸調(diào)...
當(dāng)時在網(wǎng)上找了一下答案，基本上都是1層大循環(huán)套4層小循環(huán)還實現(xiàn)的，感覺不夠優(yōu)雅。最近翻了一下數(shù)據(jù)結(jié)構(gòu)的書，看到迷宮問題受到了一點啟發(fā)，感覺同樣是實現(xiàn)這個功能，如下代碼要優(yōu)雅一些：
一年半之前，我遇到一個問題：把一堆數(shù)平均分成N份，保證每一份的和接近于所有數(shù)之和除以N，不要求平分以后的每份數(shù)據(jù)個數(shù)相等。這是有現(xiàn)實的程序設(shè)計需求的，當(dāng)時是3份。首先想到要先進行排序，再依次從已排序的數(shù)列中抽取，如何進行抽取方法有很多，我大概想了3種左右，感覺要拿一些數(shù)據(jù)去測試一下這幾種方法哪一種可以逼近最優(yōu)解。
當(dāng)時經(jīng)理要求算法一定能夠得出最優(yōu)解，但測試多組數(shù)據(jù)，沒有發(fā)現(xiàn)哪一種實現(xiàn)能得到最優(yōu)解。后來翻了一下
，忽然想到，原來這個是一個典型貪婪算法問題，這個問題沒有最優(yōu)解，用貪婪算法來解決這個問題可以讓每一次結(jié)果逼近最優(yōu)。實現(xiàn)如下(注：代碼是我今天寫的)：
字符是各種文字和符號的總稱，包括各國家文字、標(biāo)點符號、圖形符號、數(shù)字等。字符集是多個字符的集合，字符集種類較多，每個字符集包含的字符個數(shù)不同，常見字符集名稱：ASCII字符集、GB2312字符集、BIG5字符集、 GB 18030字符集、Unicode字符集等。計算機要準(zhǔn)確的處理各種字符集文字，需要進行字符編碼，以便計算機能夠識別和存儲各種文字。
中文文字?jǐn)?shù)目大，而且還分為簡體中文和繁體中文兩種不同書寫規(guī)則的文字，而計算機最初是按英語單字節(jié)字符設(shè)計的，因此，對中文字符進行編碼，是中文信息交流的技術(shù)基礎(chǔ)。本文將按照字符集的時間順序討論幾種典型的字符集，選取幾種代表性的中文字符集，研究歷史由來、特點、技術(shù)特征。
漢字編碼范圍
名稱 第一字節(jié) 第二字節(jié)
GB2312 0xB0-0xF7(176-247) 0xA0-0xFE（160-254）
GBK 0x81-0xFE（129-254） 0x40-0xFE（64-254）
Big5 0x81-0xFE（129-255） 0x40-0x7E（64-126）
0xA1－0xFE（161-254）
ASCII 字符集
1．名稱的由來
ASCII（American Standard Code for Information Interchange，美國信息互換標(biāo)準(zhǔn)代碼）是基于羅馬字母表的一套電腦編碼系統(tǒng)。
2．特點
它主要用于顯示現(xiàn)代英語和其他西歐語言。它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)，并等同于國際標(biāo)準(zhǔn)ISO 646。
3．包含內(nèi)容
控制字符：回車鍵、退格、換行鍵等。
可顯示字符：英文大小寫字符、阿拉伯?dāng)?shù)字和西文符號
4．技術(shù)特征
7位（bits）表示一個字符，共128字符
5．ASCII擴展字符集
7位編碼的字符集只能支持128個字符，為了表示更多的歐洲常用字符對ASCII進行了擴展，ASCII擴展字符集使用8位（bits）表示一個字符，共256字符。
ASCII擴展字符集比ASCII字符集擴充出來的符號包括表格符號、計算符號、希臘字母和特殊的拉丁符號。
GB2312 字符集
1．名稱的由來
GB2312又稱為GB2312-80字符集，全稱為《信息交換用漢字編碼字符集·基本集》，由原中國國家標(biāo)準(zhǔn)總局發(fā)布，1981年5月1日實施。
2．特點
GB2312是中國國家標(biāo)準(zhǔn)的簡體中文字符集。它所收錄的漢字已經(jīng)覆蓋99.75%的使用頻率，基本滿足了漢字的計算機處理需要。在中國大陸和新加坡獲廣泛使用。
3．包含內(nèi)容
GB2312收錄簡化漢字及一般符號、序號、數(shù)字、拉丁字母、日文假名、希臘字母、俄文字母、漢語拼音符號、漢語注音字母，共 7445 個圖形字符。其中包括6763個漢字，其中一級漢字3755個，二級漢字3008個；包括拉丁字母、希臘字母、日文平假名及片假名字母、俄語西里爾字母在內(nèi)的682個全角字符。
4．技術(shù)特征
（1）分區(qū)表示：
GB2312中對所收漢字進行了“分區(qū)”處理，每區(qū)含有94個漢字/符號。這種表示方式也稱為區(qū)位碼。
各區(qū)包含的字符如下：01-09區(qū)為特殊符號；16-55區(qū)為一級漢字，按拼音排序；56-87區(qū)為二級漢字，按部首/筆畫排序；10-15區(qū)及88-94區(qū)則未有編碼。
（2）雙字節(jié)表示
兩個字節(jié)中前面的字節(jié)為第一字節(jié)，后面的字節(jié)為第二字節(jié)。習(xí)慣上稱第一字節(jié)為“高字節(jié)” ，而稱第二字節(jié)為“低字節(jié)”。
“高位字節(jié)”使用了0xA1-0xF7 (把01-87區(qū)(88-94區(qū)未有編碼)的區(qū)號加上0xA0)，“低位字節(jié)”使用了0xA1-0xFE (把01-94加上0xA0)。
5．編碼舉例
以GB2312字符集的第一個漢字“啊”字為例，它的區(qū)號16，位號01，則區(qū)位碼是1601，在大多數(shù)計算機程序中，高字節(jié)和低字節(jié)分別加0xA0得到程序的漢字處理編碼0xB0A1。計算公式是：0xB0=0xA0+16, 0xA1=0xA0+1。
GBK 字符集
1．名稱的由來
GBK是GB2312的擴展，是向上兼容的，因此GB2312中的漢字的編碼與GBK中漢字的相同。另外，GBK中還包含繁體字的編碼，它與Big5編碼之間的關(guān)系我還沒有弄明白，好像是不一致的。
2. 特點
GBK中每個漢字仍然包含兩個字節(jié)，第一個字節(jié)的范圍是0x81-0xFE（即129-254），第二個字節(jié)的范圍是0x40-0xFE（即64-254）。GBK中有碼位23940個，包含漢字21003個。
BIG5 字符集
1．名稱的由來
又稱大五碼或五大碼，1984年由臺灣財團法人信息工業(yè)策進會和五間軟件公司宏碁 (Acer)、神通 (MiTAC)、佳佳、零壹 (Zero One)、大眾 (FIC)創(chuàng)立，故稱大五碼。
Big5碼的產(chǎn)生，是因為當(dāng)時臺灣不同廠商各自推出不同的編碼，如倚天碼、IBM PS55、王安碼等，彼此不能兼容；另一方面，臺灣政府當(dāng)時尚未推出官方的漢字編碼，而中國大陸的GB2312編碼亦未有收錄繁體中文字。
2．特點
Big5字符集共收錄13,053個中文字，該字符集在中國臺灣使用。耐人尋味的是該字符集重復(fù)地收錄了兩個相同的字：“兀”(0xA461及0xC94A)、“嗀”(0xDCD1及0xDDFC)。
3．字符編碼方法
Big5碼使用了雙字節(jié)儲存方法，以兩個字節(jié)來編碼一個字。第一個字節(jié)稱為“高位字節(jié)”，第二個字節(jié)稱為“低位字節(jié)”。高位字節(jié)的編碼范圍0xA1-0xF9，低位字節(jié)的編碼范圍0x40-0x7E及0xA1-0xFE。
各編碼范圍對應(yīng)的字符類型如下：0xA140-0xA3BF為標(biāo)點符號、希臘字母及特殊符號，另外于0xA259-0xA261，存放了雙音節(jié)度量衡單位用字：兙兛兞兝兡兣嗧瓩糎；0xA440-0xC67E為常用漢字，先按筆劃再按部首排序；0xC940-0xF9D5為次常用漢字，亦是先按筆劃再按部首排序。
4．Big5 的局限性
盡管Big5碼內(nèi)包含一萬多個字符，但是沒有考慮社會上流通的人名、地名用字、方言用字、化學(xué)及生物科等用字，沒有包含日文平假名及片假名字母。
例如臺灣視“著”為“著”的異體字，故沒有收錄“著”字。康熙字典中的一些部首用字(如“亠”、“疒”、“辵”、“癶”等)、常見的人名用字(如“堃”、“煊”、“栢”、“喆”等) 也沒有收錄到Big5之中。
GB18030 字符集
1．名稱的由來
GB 18030的全稱是GB18030-2000《信息交換用漢字編碼字符集基本集的擴充》，是我國政府于2000年3月17日發(fā)布的新的漢字編碼國家標(biāo)準(zhǔn)，2001年8月31日后在中國市場上發(fā)布的軟件必須符合本標(biāo)準(zhǔn)
2．特點
GB 18030字符集標(biāo)準(zhǔn)的出臺經(jīng)過廣泛參與和論證，來自國內(nèi)外知名信息技術(shù)行業(yè)的公司，信息產(chǎn)業(yè)部和原國家質(zhì)量技術(shù)監(jiān)督局聯(lián)合實施。
GB 18030字符集標(biāo)準(zhǔn)解決漢字、日文假名、朝鮮語和中國少數(shù)民族文字組成的大字符集計算機編碼問題。該標(biāo)準(zhǔn)的字符總編碼空間超過150萬個編碼位，收錄了27484個漢字，覆蓋中文、日文、朝鮮語和中國少數(shù)民族文字。滿足中國大陸、香港、臺灣、日本和韓國等東亞地區(qū)信息交換多文種、大字量、多用途、統(tǒng)一編碼格式的要求。并且與Unicode 3.0版本兼容，填補Unicode擴展字符字匯“統(tǒng)一漢字?jǐn)U展A”的內(nèi)容。并且與以前的國家字符編碼標(biāo)準(zhǔn)（GB2312，GB13000.1）兼容。
3．編碼方法
GB 18030標(biāo)準(zhǔn)采用單字節(jié)、雙字節(jié)和四字節(jié)三種方式對字符編碼。單字節(jié)部分使用0×00至0×7F碼(對應(yīng)于ASCII碼的相應(yīng)碼)。雙字節(jié)部分，首字節(jié)碼從0×81至0×FE，尾字節(jié)碼位分別是0×40至0×7E和0×80至0×FE。四字節(jié)部分采用GB/T 11383未采用的0×30到0×39作為對雙字節(jié)編碼擴充的后綴，這樣擴充的四字節(jié)編碼，其范圍為0×81308130到0×FE39FE39。其中第一、三個字節(jié)編碼碼位均為0×81至0×FE，第二、四個字節(jié)編碼碼位均為0×30至0×39。
4．包含的內(nèi)容
雙字節(jié)部分收錄內(nèi)容主要包括GB13000.1全部CJK漢字20902個、有關(guān)標(biāo)點符號、表意文字描述符13個、增補的漢字和部首/構(gòu)件80個、雙字節(jié)編碼的歐元符號等。 四字節(jié)部分收錄了上述雙字節(jié)字符之外的，包括CJK統(tǒng)一漢字?jǐn)U充A在內(nèi)的GB 13000.1中的全部字符。
對漢字進行hash
為了處理漢字的方便，在查找漢字的時候，我們通常會用到hash的方法，那怎么來確定一個漢字位置呢？這就和每種編碼的排列有關(guān)了，這里主要給出一種hash函數(shù)的策略。
對于GB2312編碼，設(shè)輸入的漢字為GBword，我們可以采用公式(C1-176)*94 + (C2-161)確定GBindex。其中，C1表示第一字節(jié)，C2表示第二字節(jié)。具體如下：
GBindex = ((unsigned char)GBword.at(0)-176)*94 + (unsigned char)GBword.at(1) - 161;
之所以用unsigned char類型，是因為char是一個字節(jié)，如果用unsigend int，因為int是4個字節(jié)的，所以會造成擴展，導(dǎo)致錯誤。
對于GBK編碼，設(shè)輸入的漢字為GBKword，則可以采用公式 index=(ch1-0x81)*190+(ch2-0x40)-(ch2/128)，其中ch1是第一字節(jié)，ch2是第二字節(jié)。
具體的，
GBKindex = ((unsigned char)GBKword[0]-129)*190 +
((unsigned char)GBKword[1]-64) - (unsigned char)GBKword[1]/128;
怎樣判斷一個漢字的是什么編碼
直接根據(jù)漢字的編碼范圍判斷，對于GB2312和GBK可用下面兩個程序?qū)崿F(xiàn)。
1、判斷是否是GB2312
bool isGBCode(const string& strIn)
{
unsigned char ch1;
unsigned char ch2;
if (strIn.size() >= 2)
{
ch1 = (unsigned char)strIn.at(0);
ch2 = (unsigned char)strIn.at(1);
if (ch1>=176 && ch1<=247 && ch2>=160 && ch2<=254)
return true;
else return false;
}
else return false;
}
2、判斷是否是GBK編碼
bool isGBKCode(const string& strIn)
{
unsigned char ch1;
unsigned char ch2;
if (strIn.size() >= 2)
{
ch1 = (unsigned char)strIn.at(0);
ch2 = (unsigned char)strIn.at(1);
if (ch1>=129 && ch1<=254 && ch2>=64 && ch2<=254)
return true;
else return false;
}
else return false;
}
3、對于Big5
它的范圍為：高字節(jié)從0xA0到0xFE，低字節(jié)從0x40到0x7E，和0xA1到0xFE兩部分。判斷一個漢字是否是BIG5編碼，可以如上對字符的編碼范圍判斷即可。如何定位呢？那么也想象所有編碼排列為一個二維坐標(biāo)，縱坐標(biāo)是高字節(jié)，橫坐標(biāo)是低字節(jié)。這樣一行上的漢字個數(shù)：(0x7E-0x40+1)+(0xFE-0xA1+1)＝157。那么定位算法分兩塊，為:
if 0x40<=ch2<=0x7E: #is big5 char
index=((ch1-0xA1)*157+(ch2-0x40))*2
elif 0xA1<=ch2<=0xFE: #is big5 char
index=((ch1-0xA1)*157+(ch2-0xA1+63))*2
對于第二塊，計算偏移量時因為有兩塊數(shù)值，所以在計算后面一段值時，不要忘了前面還有一段值。0x7E-0x40+1=63。
如果判斷一個字符是西文字符還是中文字符
大家知道西文字符主要是指ASCII碼，它用一個字節(jié)表示。且這個字符轉(zhuǎn)換成數(shù)字之后，該數(shù)字是大于0的，而漢字是兩個字節(jié)的，第一個字節(jié)的轉(zhuǎn)化為數(shù)字之后應(yīng)該是小于0的，因此可以根據(jù)每個字節(jié)轉(zhuǎn)化為數(shù)字之后是否小于0，判斷它是否是漢字。
例如，設(shè)輸入字為strin，則，
If (strin.at(0) < 0)
cout << ”是漢字” << endl;
else cout << ”不是漢字” << endl;
編碼表
Unicode字符集
1．名稱的由來
Unicode字符集編碼是Universal Multiple-Octet Coded Character Set 通用多八位編碼字符集的簡稱，是由一個名為 Unicode 學(xué)術(shù)學(xué)會(Unicode Consortium)的機構(gòu)制訂的字符編碼系統(tǒng)，支持現(xiàn)今世界各種不同語言的書面文本的交換、處理及顯示。該編碼于1990年開始研發(fā)，1994年正式公布，最新版本是2005年3月31日的Unicode 4.1.0。
2．特征
Unicode是一種在計算機上使用的字符編碼。它為每種語言中的每個字符設(shè)定了統(tǒng)一并且唯一的二進制編碼，以滿足跨語言、跨平臺進行文本轉(zhuǎn)換、處理的要求。
3．編碼方法
Unicode 標(biāo)準(zhǔn)始終使用十六進制數(shù)字，而且在書寫時在前面加上前綴“U+”，例如字母“A”的編碼為 004116 和字符“?”的編碼為 20AC16。所以“A”的編碼書寫為“U+0041”。
4．UTF-8 編碼
UTF-8是Unicode的其中一個使用方式。 UTF是 Unicode Translation Format，即把Unicode轉(zhuǎn)做某種格式的意思。
UTF-8便于不同的計算機之間使用網(wǎng)絡(luò)傳輸不同語言和編碼的文字，使得雙字節(jié)的Unicode能夠在現(xiàn)存的處理單字節(jié)的系統(tǒng)上正確傳輸。
UTF-8使用可變長度字節(jié)來儲存 Unicode字符，例如ASCII字母繼續(xù)使用1字節(jié)儲存，重音文字、希臘字母或西里爾字母等使用2字節(jié)來儲存，而常用的漢字就要使用3字節(jié)。輔助平面字符則使用4字節(jié)。
5．UTF-16 和 UTF-32 編碼
UTF-32、UTF-16 和 UTF-8 是 Unicode 標(biāo)準(zhǔn)的編碼字符集的字符編碼方案，UTF-16 使用一個或兩個未分配的 16 位代碼單元的序列對 Unicode 代碼點進行編碼；UTF-32 即將每一個 Unicode 代碼點表示為相同值的 32 位整數(shù)