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