從數(shù)據(jù)到算法

數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

任何問(wèn)題解決方案都不可能脫離數(shù)據(jù)結(jié)構(gòu)而單獨(dú)存在。所謂數(shù)據(jù)類型就是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。一般而言，數(shù)據(jù)類型可分為原子型和結(jié)構(gòu)型。在程序設(shè)計(jì)語(yǔ)言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算。這些已經(jīng)事先定義好的數(shù)據(jù)類型就是所謂的原子型。經(jīng)過(guò)數(shù)據(jù)類型規(guī)定后的若干有序0和1的組合就在計(jì)算機(jī)中呈現(xiàn)出一定的意義。最初的表現(xiàn)形式就是原子型數(shù)據(jù)類型。而在某些時(shí)候，一旦需要引入某種新的數(shù)據(jù)類型時(shí)，總是借助編程語(yǔ)言所提供的原子型數(shù)據(jù)類型來(lái)描述或定義新數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，這也就是所謂的結(jié)構(gòu)型。換句話說(shuō)，原子型數(shù)據(jù)經(jīng)過(guò)一定規(guī)則重組后即可形成結(jié)構(gòu)型數(shù)據(jù)。

原子數(shù)據(jù)類型：
這里需要注意的一些問(wèn)題是：

char(signed char) -128 ~ 127;
unsigned char 0 ~ 255
short(signed short) -32768 ~ 32767
unsigned short 0 ~ 65535

僅有原子型數(shù)據(jù)仍然是不夠的。將原子型數(shù)據(jù)按照一定規(guī)則重組，就可以形成結(jié)構(gòu)型數(shù)據(jù)。換句話說(shuō)，結(jié)構(gòu)化的數(shù)據(jù)可以由簡(jiǎn)單的數(shù)據(jù)組成。將某人的聯(lián)系地址想象一個(gè)結(jié)構(gòu)化的數(shù)據(jù)，那么在這個(gè)結(jié)構(gòu)中可能有若干個(gè)項(xiàng)目，它們都是一些簡(jiǎn)單的基本數(shù)據(jù)。例如，居住地的門牌號(hào)，然后是所在街道的名字、城市的名字、省份的名稱和郵政編碼、

C++中的STL

標(biāo)準(zhǔn)模板庫(kù)（STL）是C++中的一個(gè)重要特性，也是本書介紹的重點(diǎn)內(nèi)容之一。STL是一個(gè)具有工業(yè)強(qiáng)度的、高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)中，是 ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。

標(biāo)準(zhǔn)模板庫(kù)體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic programming）,并引入了諸多新的名字，比如像需求（requirements)、概念（concept）、模型（model）、容器（container）和迭代器（iterator）等。這些都是支持泛型思想的概念，泛型思想也是一種軟件的復(fù)用技術(shù)，這看起來(lái)與C++的特性是如此相合。

STL 構(gòu)成

STL 的構(gòu)成可以概括為：3大主體、6大組件、13個(gè)頭文件。所謂13個(gè)頭文件是指在C++標(biāo)準(zhǔn)中，STL被組織為下面的13個(gè)頭文件，包括："algorithm"、"deque"、"functional"、"iterator"、"vector"、"list"、"map"、"memory"、"numeric"、"queue"、"set"、"stack" 和 "utility"。這些頭文件包含了全部的代碼，而這些代碼從廣義上講可以被分成3大類：container（容器）、algorithm（算法）和iterator（迭代器），且?guī)缀跛械拇a都采用模板類和模板函數(shù)地方式，顯然這有利于代碼的重用。這3類也就是STL的3大主體。事實(shí)上如果細(xì)致地考慮STL的組成，它應(yīng)當(dāng)包括6個(gè)組件，除了前面比較重要的3大主體以外，還包括：仿函數(shù)、適配器和空間配置器。下面主要對(duì)3大主體進(jìn)行一個(gè)概要介紹。

1.容器
在實(shí)際的開(kāi)發(fā)過(guò)程中，數(shù)據(jù)結(jié)構(gòu)本身的重要性不會(huì)遜于操作與數(shù)據(jù)結(jié)構(gòu)的算法的重要性，當(dāng)程序中存在著對(duì)時(shí)間要求很高的部分時(shí)，數(shù)據(jù)結(jié)構(gòu)的選擇就顯得更加重要。這一點(diǎn)在很多算法題目的解答時(shí)表現(xiàn)得尤為明顯。容器部分主要由頭文件 "vector"、"list"、"deque"、"set"、"map"、"stack"和"queue" 組成，其中提供的容器主要包括：

• 向量（vector)
• 鏈表（list）
• 棧（stack）
• 隊(duì)列（queue）
• 優(yōu)先隊(duì)列（priority_queue）
• 雙向隊(duì)列（deque）
• 集合（set）
• 多重集合（multiset）
• 映射（map）
• 多重映射（multimap）

2.算法
算法時(shí)STL的一個(gè)重要組成部分，STL中大約包含了70個(gè)通用算法，用于控制各種容器，同時(shí)也可以操縱內(nèi)建數(shù)組。所有這些操作都是在保證執(zhí)行效率的前提下進(jìn)行的，且所有算法都遵循所謂的泛型算法通則，即

• 所有算法的前兩個(gè)參數(shù)都一對(duì) iterator：(first,last), 用來(lái)指出容器內(nèi)一個(gè)范圍內(nèi)的元素
• 每個(gè)算法的聲明中，都表現(xiàn)出它所需要的最低層次的iterator 類型。
• 大部分算法都可以用仿函數(shù)（function object，又稱 functor）來(lái)更改準(zhǔn)則。

STL利用模板機(jī)制提供了相當(dāng)多的有用算法，其中常用的包括比較、交換、查找、遍歷、復(fù)制、修改、移除、反轉(zhuǎn)、排序、合并等。如此，在熟悉了STL之后，許多代碼都可以被大大簡(jiǎn)化，只需要通過(guò)調(diào)用一兩個(gè)算法模板，就可以完成所需要的功能并大大地提升效率。

STL中的算法部分主要由頭文件 "algorithm"、"numeric" 和 "functional" 組成。頭文件"algorithm" 是所有STL頭文件中最大的一個(gè)，也是 STL 中算法部分的主體。它由很多模板函數(shù)組成，可以認(rèn)為每個(gè)函數(shù)在很大程度上都是獨(dú)立的。"algorithm"囊括的算法包括查找、交換和排序等。"numeric"體積很小，只包含幾個(gè)在序列上面進(jìn)行簡(jiǎn)單數(shù)學(xué)運(yùn)算的模板函數(shù)，包括加法和乘法在序列上的一些操作。"functional"中則定義了一些模板類，用以聲明函數(shù)對(duì)象。

3.迭代器
迭代器起初是設(shè)計(jì)模式中的一種，意思是提供一種方法，按順序訪問(wèn)某個(gè)容器所含的各個(gè)元素，而無(wú)需暴露該容器的內(nèi)部表述方法。這也是軟件設(shè)計(jì)的一個(gè)基本原則，也就是說(shuō)通過(guò)引進(jìn)一個(gè)間接層來(lái)簡(jiǎn)化所有問(wèn)題的解決。在STL中，迭代器被用來(lái)將算法和容器聯(lián)系起來(lái)，起到某種粘合作用。容器提供迭代器，而算法使用迭代器。幾乎STL提供的所有算法都是通過(guò)迭代器存取元素序列進(jìn)行工作的，每一個(gè)容器都定義了其本身所專有的迭代器，用以存取容器中的元素。迭代器能夠使容器與算法不干擾地相互發(fā)展，最后又能無(wú)間隙地粘合起來(lái)。特別地，迭代器還重載了*、++、==、！=、=等運(yùn)算符，用以操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

迭代器部分主要由頭文件"utility"、"iterator" 和 "memory"組成。其中，utility 是一個(gè)很小的頭文件，它包括了貫穿使用在 STL 中的幾個(gè)模板的聲明，"iterator" 中提供了迭代器使用的許多方法，可以認(rèn)為是迭代器部分的主體。"memory" 則以不同尋常的方式為容器中的元素分配存儲(chǔ)空間，同時(shí)也為某些算法執(zhí)行期間產(chǎn)生的臨時(shí)對(duì)象提供機(jī)制。

指針和數(shù)組

數(shù)組是最簡(jiǎn)單的、最基本的線性數(shù)據(jù)結(jié)構(gòu)，它可以被認(rèn)為是程序設(shè)計(jì)語(yǔ)言提供的一種已經(jīng)封裝好了的數(shù)據(jù)結(jié)構(gòu)。此外，許多數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)也是以數(shù)組為基礎(chǔ)的（例如順序棧以及循環(huán)隊(duì)列）。還有另外一種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法則以鏈表為基礎(chǔ)（例如鏈?zhǔn)綏Ｒ约版準(zhǔn)疥?duì)列）。

（這里面涉及了關(guān)于動(dòng)態(tài)內(nèi)存管理以及指針?lè)矫娴膬?nèi)容，而且指針和數(shù)組之間還具有非常緊密的聯(lián)系。）

指針提供了對(duì)內(nèi)存進(jìn)行進(jìn)行直接操作的手段，這使得C/C++語(yǔ)言靈活而強(qiáng)大，但是在某種程度上也增大了風(fēng)險(xiǎn)。內(nèi)存錯(cuò)誤往往導(dǎo)致嚴(yán)重的后果卻難以察覺(jué)。

馮-諾依曼結(jié)構(gòu)的一個(gè)核心理論要點(diǎn)就是將程序指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器合并在一起，即所謂的“程序存儲(chǔ)”。依據(jù)這一原理，程序的數(shù)據(jù)和指令都存在內(nèi)存中。從物理意義上講，內(nèi)存就是一塊具有存儲(chǔ)功能的半導(dǎo)體材料。任何需要被計(jì)算機(jī)執(zhí)行的程序（包括指令和數(shù)據(jù)），都要先從外部存儲(chǔ)器（包括硬盤、光盤等）調(diào)入內(nèi)存后才能被執(zhí)行。內(nèi)存中同時(shí)持有很多數(shù)據(jù)，當(dāng)前需要哪個(gè)數(shù)據(jù)，CPU都會(huì)從內(nèi)存中精確地找到它然后再讓其參與運(yùn)算。

內(nèi)存采取了同樣的管理方法，首先內(nèi)存被劃分為許許多多個(gè)很小的存儲(chǔ)單元，然后這些存儲(chǔ)單元被編上了號(hào)，由于內(nèi)存中的存儲(chǔ)單元太多，所以這些編號(hào)往往是一個(gè)非常大的整數(shù)，例如 0x0019F878（這是一個(gè)十六進(jìn)制表示的大整數(shù)）。換句話說(shuō)，CPU執(zhí)行的機(jī)器碼通過(guò)各內(nèi)存位置的唯一編號(hào)來(lái)操作這些內(nèi)存中的數(shù)據(jù)，這些編號(hào)就是所謂的內(nèi)存地址，而編譯器的工作過(guò)程就是將程序中的變量和操作翻譯成對(duì)內(nèi)存地址進(jìn)行操作的機(jī)器語(yǔ)言。所以，在最終的機(jī)器碼里其實(shí)是不存在變量名或變量類型的。

簡(jiǎn)單來(lái)說(shuō)，內(nèi)存就是一段連續(xù)的存儲(chǔ)空間，內(nèi)存被均等地分為多個(gè)存儲(chǔ)單元，每個(gè)單元都成為一個(gè)內(nèi)存單元。數(shù)據(jù)在內(nèi)存中按一定的順序連續(xù)存放。為了便于管理，系統(tǒng)給每個(gè)內(nèi)存單元都編了一個(gè)號(hào)，成為內(nèi)存地址。每個(gè)內(nèi)存單元的地址都是一個(gè)很大的整數(shù)，例如：0x0019F878。計(jì)算機(jī)中也提供了對(duì)于一個(gè)數(shù)據(jù)的“直接訪問(wèn)”和“間接訪問(wèn)” 。通過(guò)變量來(lái)訪問(wèn)數(shù)據(jù)就是間接的訪問(wèn)方式，通過(guò)地址來(lái)訪問(wèn)數(shù)據(jù)就是直接的訪問(wèn)方式。

在C++中，一個(gè)變量的地址成為該變量的“指針”。指針也是一種數(shù)據(jù)，它當(dāng)然也可以被存在一個(gè)內(nèi)存單元中。如果定義一個(gè)變量專門用來(lái)存放另一個(gè)變量的地址，則它就是一個(gè)指針變量。即用來(lái)存儲(chǔ)指針的變量，就稱為指針變量。指針變量的值就是指針。

int a,b,c; 相對(duì)于類型而言，可以認(rèn)為和變量名結(jié)合的關(guān)系更緊密些，所以上述定義的結(jié)果是a是一個(gè)指針變量，而b和c都是int性變量！如果想將a、b和c都定義成指針型變量則只能采取如下的方式。
int *a;
int *b;
int *c;

對(duì)于上例中的指針類型p,如果有操作p++,那么對(duì)于指針變量p自加1意味著什么呢？因?yàn)閜是一個(gè)int型指針，因此p++操作意味著將指針p移動(dòng)4個(gè)字節(jié)（假設(shè)一個(gè)int型變量占據(jù)4字節(jié)的空間）?？梢?jiàn)正確地定義指針類型是非常重要的。指針是變量的地址，這個(gè)地址的獲得必須通過(guò)一個(gè)已經(jīng)被分配了存儲(chǔ)空間的變量來(lái)完成，變量的地址只能通過(guò)指針運(yùn)算符*或取地址符&來(lái)獲得，而不能直接指定一個(gè)具體的地址。另外，對(duì)于&*p 和 *&p的區(qū)別。因?yàn)?和&具有相同的優(yōu)先級(jí)，按照從右向左的方向結(jié)合。

動(dòng)態(tài)內(nèi)存管理
數(shù)組在定義時(shí)，系統(tǒng)會(huì)為其分配固定大小的內(nèi)存空間，這被稱為是靜態(tài)內(nèi)存分配。靜態(tài)內(nèi)存分配的好處在實(shí)現(xiàn)簡(jiǎn)單，操作方便，但也致使程序的可伸縮性大大降低。因?yàn)樵诤芏嗟那闆r下，程序員無(wú)法預(yù)先確定要使用多大的數(shù)組。為了解決這樣的問(wèn)題，就需要使用動(dòng)態(tài)內(nèi)存分配。所謂動(dòng)態(tài)內(nèi)存分配就是指在程序執(zhí)行的過(guò)程中動(dòng)態(tài)地分配或者回收存儲(chǔ)空間的分配內(nèi)存的方法。由于動(dòng)態(tài)分配不需要預(yù)先分配存儲(chǔ)空間，而且分配的空間還可以根據(jù)程序的需要擴(kuò)大或縮小，因此它能夠有效地克服靜態(tài)內(nèi)存分配所帶來(lái)的種種弊病。

創(chuàng)建一個(gè)新的類對(duì)象時(shí)，通常需要完成的工作包括：首先，為對(duì)象分配內(nèi)存；其次調(diào)用構(gòu)造函數(shù)來(lái)初始化那塊內(nèi)存。程序員應(yīng)當(dāng)保證初始化過(guò)程正確進(jìn)行，這一點(diǎn)非常重要，因?yàn)槌跏蓟膯?wèn)題是程序出錯(cuò)的主要原因之一。

在C++中，程序員可以利用關(guān)鍵字new和delete來(lái)實(shí)現(xiàn)內(nèi)存空間的動(dòng)態(tài)管理，new可以根據(jù)具體對(duì)象的不同而自動(dòng)開(kāi)辟合適的內(nèi)存空間，而delete則負(fù)責(zé)回收由new開(kāi)辟的內(nèi)存空間，它們幫助程序在運(yùn)行時(shí)從堆中分配存儲(chǔ)單元。為普通的變量申請(qǐng)內(nèi)存空間，可以使用下面的語(yǔ)法規(guī)則:
float * p = new float(3.14)
在C++里同樣可以使用new來(lái)為一個(gè)數(shù)組分配內(nèi)存空間，并相應(yīng)地使用delete來(lái)將其釋放。其具體語(yǔ)法如下例所示：
Point * pt = new Point[100];
上述代碼使用new 在堆上創(chuàng)建了一個(gè)含有100個(gè)對(duì)象的數(shù)組，并把返回的指針賦給了指針變量pt。這樣就在堆上為100個(gè)Point對(duì)象分配了足夠的內(nèi)存并為每一個(gè)對(duì)象調(diào)用了構(gòu)造函數(shù)。那如何將這個(gè)數(shù)組所占據(jù)的空間釋放呢？
delete pt 這就表示把數(shù)組中的第一個(gè)對(duì)象釋放了，也就僅僅只是為第一個(gè)對(duì)象調(diào)用了析構(gòu)函數(shù)，而另外99個(gè)析構(gòu)函數(shù)沒(méi)有進(jìn)行，所以這是錯(cuò)誤的語(yǔ)句。正確的語(yǔ)句應(yīng)當(dāng)采取下面這樣的語(yǔ)句來(lái)實(shí)現(xiàn)：
delete [] pt;
空的方括號(hào)告訴編譯器產(chǎn)生從數(shù)組創(chuàng)建時(shí)存放的地方取回?cái)?shù)組中對(duì)象數(shù)量的代碼，并為數(shù)組的所有對(duì)象調(diào)用析構(gòu)函數(shù)。

避免內(nèi)存錯(cuò)誤
內(nèi)存管理上的錯(cuò)誤是用C/C++語(yǔ)言進(jìn)行程序設(shè)計(jì)時(shí)最可怕的一類錯(cuò)誤，它的危險(xiǎn)首先原自它的不易察覺(jué)性，另一方面不得不承認(rèn)這種錯(cuò)誤的結(jié)果也常常是非常致命的。通常的內(nèi)存錯(cuò)誤被歸結(jié)為以下4點(diǎn)：內(nèi)存泄漏、重復(fù)釋放、壞指針問(wèn)題和超量寫內(nèi)存。

1.內(nèi)存泄漏
在分配了一塊內(nèi)存空間之后，如果不再需要這些數(shù)據(jù)就應(yīng)當(dāng)考慮將其釋放。而如果程序員沒(méi)有將其釋放，那么這塊空間將隨同程序運(yùn)行而一直存在。對(duì)于一個(gè)需要運(yùn)行較長(zhǎng)時(shí)間的計(jì)算機(jī)程序而言，如果它只是一味地分配而不進(jìn)行回收，那么最終系統(tǒng)資源無(wú)疑將被耗盡。于是程序在這個(gè)過(guò)程中將被運(yùn)行得越來(lái)越慢，最終系統(tǒng)陷入癱瘓。在計(jì)算機(jī)中有很多程序要運(yùn)行很長(zhǎng)時(shí)間，操作系統(tǒng)實(shí)際上就是一個(gè)"死循環(huán)"。還有很多網(wǎng)絡(luò)服務(wù)程序也會(huì)運(yùn)行很長(zhǎng)時(shí)間。比如一個(gè)圖像處理程序，它打開(kāi)的圖片文件可能有幾百字節(jié)，也有可能是幾百兆，如果內(nèi)存僅僅是分配而忘記了回收，或是沒(méi)有得到很好的回收，那么內(nèi)存資源就好像一個(gè)漏了的水箱中的水不斷地泄漏，直到最終耗盡為止----這就是所謂的內(nèi)存泄漏。

內(nèi)存的泄漏通常是由回收失敗導(dǎo)致的，例如下面的這個(gè)例子，被分配的內(nèi)存在函數(shù)的最后一行進(jìn)行了釋放，但當(dāng)執(zhí)行到"if(End()) return;" 處時(shí)，函數(shù)如果滿足結(jié)束條件就會(huì)直接返回，于是發(fā)生了回收失敗。異常、錯(cuò)誤和其他各種throw和catch語(yǔ)句經(jīng)常是導(dǎo)致內(nèi)存泄漏的原因。

void Memory_Leak()
{
     int * list = new int[100];
     ... ...
     if (End()) return;
     ... ...
     delete[] list;
}

還有一種可能引起內(nèi)存泄漏的原因是忘記了釋放一個(gè)數(shù)據(jù)結(jié)構(gòu)的某些部分。例如定義以下結(jié)構(gòu)。

typedef struct{
    char *name;
    int number;
    int age;
    char *address;
    int phonel
} Student;

對(duì)于 Student 這個(gè)結(jié)構(gòu)的擔(dān)憂一個(gè)相關(guān)函數(shù)如下：

void Memory_Leak()
{
     Student* s;
     s= new Student;
     s->name = new char[100];
     ... ...
     s->address = new char[50];
     ... ...
     delete s;
}

上面的例子中，一個(gè) Student 結(jié)構(gòu)體被分配了內(nèi)存并在程序結(jié)束的時(shí)候內(nèi)存空間得以釋放，但這個(gè)結(jié)構(gòu)體的一些域并沒(méi)有釋放，
例如 name 和 address 都被分配了空間，但它們沒(méi)有釋放。這里要注意結(jié)構(gòu)體被釋放并不表示它的域也被釋放了！

2、重復(fù)釋放
分配內(nèi)存必須釋放，而且每次分配僅能對(duì)應(yīng)一次釋放。如果釋放一個(gè)根本不存在的指針，亦或?qū)τ谝粋€(gè)指針重復(fù)釋放都會(huì)引起不必要的麻煩。要是釋放函數(shù)能夠自動(dòng)檢查將要被釋放的空間是否已經(jīng)被釋放過(guò)了該有多好，然后并不是所有的存儲(chǔ)分配器都留用足夠的空間來(lái)記錄那些內(nèi)存塊的釋放和分配狀態(tài)。何況內(nèi)存分配的效率對(duì)于整個(gè)程序的運(yùn)行表現(xiàn)影響巨大，如果在運(yùn)行時(shí)反復(fù)進(jìn)行檢查勢(shì)必導(dǎo)致程序效率大幅降低。當(dāng)然，如果這個(gè)釋放函數(shù)并不是經(jīng)常被調(diào)用，而且出于程序的安全性和可讀性考慮可以試著寫一個(gè)防止重復(fù)釋放的小函數(shù)，如下定義了一個(gè)宏，它可以用來(lái)避免重復(fù)釋放。

#define SAFE_DELETE(P)
{
 if((p)!=NULL)
 {
    delete (p);
    (p) = NULL;
 }
}

下面是可能發(fā)生重復(fù)釋放的情況，首先看一個(gè)例子，下面的例子對(duì)同一空間進(jìn)行了重復(fù)釋放。

void Twice_Free(x)
{
   ... ...
   delete[] x;
}

int main(int argc, char** argv)
{
     int *x = new int[10];
     ... ...
     Twice_Free(x);
     ... ...
     delete[] x;
     return 0;

程序最開(kāi)始開(kāi)辟了一塊內(nèi)存內(nèi)存空間用來(lái)存儲(chǔ)一些整型數(shù)據(jù)，并在最后將這些數(shù)據(jù)釋放。但是在程序運(yùn)行過(guò)程中調(diào)用一個(gè)函數(shù)“Twice_Free(X);”，在這個(gè)函數(shù)中x被釋放過(guò)了一次，因此程序發(fā)生了重復(fù)釋放。因?yàn)樵诤芏嗲闆r下，指針可能發(fā)生了傳遞，而傳遞的僅僅是地址，也就是說(shuō)在一個(gè)程序中可能存在多個(gè)指針同時(shí)指向一塊內(nèi)存空間，對(duì)于其中任何一個(gè)指針的釋放都會(huì)對(duì)這塊空間進(jìn)行回收。但由于其他指針貌似并沒(méi)有回收，于是粗心的人就會(huì)畫蛇添足地進(jìn)行重復(fù)釋放?？梢耘e一個(gè)更極端的例子來(lái)說(shuō)明這種現(xiàn)象。

BYTE* temp_buffer1 = new BYTE[100];
... ...
BYTE* temp_buffer2 = temp_buffer1;
... ...
BYTE* temp_buffer3 = temp_buffer2;
... ...
delete [] temp_buffer1;
delete [] temp_buffer2;
delete [] temp_buffer3;

事實(shí)上，temp_buffer1、temp_buffer2和temp_buffer3 都指向同一塊內(nèi)存區(qū)域，無(wú)需釋放3次，僅僅釋放其中一次就可以達(dá)到目的。程序訪問(wèn)一段已經(jīng)被釋放了的內(nèi)存空間可能引起很多危險(xiǎn)。因?yàn)橐坏﹥?nèi)存塊被釋放，它其中的數(shù)據(jù)就有可能被應(yīng)用程序或堆分配管理器修改。恰恰在修改之后，這塊被占用的內(nèi)存再次被其他的數(shù)據(jù)塊訪問(wèn)到，后果就不堪設(shè)想了。一方面你所讀到的程序其實(shí)是無(wú)用的，應(yīng)用了這些沒(méi)有任何意義的數(shù)據(jù)之后整個(gè)系統(tǒng)的運(yùn)作都有可能受到影響，更糟的情況是你對(duì)這個(gè)塊進(jìn)行了寫操作，也就是說(shuō)你改寫了本不該屬于你的數(shù)據(jù)，結(jié)果程序就崩潰了！下面給出了一個(gè)小例子，在這個(gè)例子中程序引用了一個(gè)已經(jīng)被釋放了的指針。

void Twice_Free(x)
{
     ... ...
     delete[] x;
}

int main(int argc, char** argv){
     int *x = new int[10];
     ... ...
     Twice_Free(x);
     ... ...
     Function(x); // 錯(cuò)誤！
     ... ...
     return 0;
}

一種避免上述錯(cuò)誤發(fā)生的方法是當(dāng)一個(gè)指針被釋放時(shí)，就隨即將其賦值為NULL,前面的宏定義里這樣做了。但如果該指針同時(shí)存在多份副本的時(shí)候，僅對(duì)其中之一賦NULL，并不能從根本上預(yù)防錯(cuò)誤的發(fā)生?？傊?，務(wù)必保證被分配的內(nèi)存塊僅被釋放一次，保證已經(jīng)被釋放了的指針不會(huì)再次使用。如果這個(gè)指針曾經(jīng)被復(fù)制了，就必須保證當(dāng)它所指向的內(nèi)存區(qū)域被釋放之后，所以的副本都不應(yīng)當(dāng)被使用。

3、壞指針問(wèn)題
內(nèi)存管理方面的錯(cuò)誤最主要是由壞指針問(wèn)題所導(dǎo)致的，壞指針是一類問(wèn)題的總稱，它可能是由很多原因引起的。如果一個(gè)指針沒(méi)有按預(yù)期指向應(yīng)當(dāng)指向的位置，那么當(dāng)廢棄這個(gè)指針時(shí)，一個(gè)通常的錯(cuò)誤就發(fā)生了。

在這種情況下，最樂(lè)觀的結(jié)果是指針終止于一些無(wú)效的內(nèi)存空間。當(dāng)發(fā)生這種情況時(shí)，程序經(jīng)常會(huì)被立即終止。而可能發(fā)生的最糟糕的情況是一些隨機(jī)的內(nèi)存位置被修改了，但程序卻繼續(xù)運(yùn)行下去。最終程序沒(méi)有一點(diǎn)征兆地奔潰了，導(dǎo)致程序奔潰的數(shù)據(jù)看似與問(wèn)題毫不相關(guān)，因?yàn)槌绦虿恢缽暮螘r(shí)起就開(kāi)始使用錯(cuò)誤的數(shù)據(jù)了！這樣一來(lái)，要想查出問(wèn)題到底出在哪是非常不容易的。

那么問(wèn)題是：壞指針從哪來(lái)呢？一個(gè)不可忽視的根源就是沒(méi)有被很好初始化的數(shù)據(jù)。假設(shè)你聲明了一個(gè)本地指針但忘記了初始化它，因?yàn)樽兞渴潜粌?chǔ)存在棧里的，而?？赡艹錆M了那些來(lái)自先前活動(dòng)記錄的數(shù)據(jù)，恰巧這些數(shù)據(jù)沒(méi)有被丟棄，那么指針就可能帶有它們的值。

由堆來(lái)分配的對(duì)象存在同樣的初始化問(wèn)題。C++能夠通過(guò)初始化函數(shù)來(lái)幫助避免這些問(wèn)題，當(dāng)一個(gè)類的實(shí)例被創(chuàng)建后，初始化函數(shù)會(huì)被自動(dòng)調(diào)用，無(wú)論是在堆上還是在棧上。寫初始化函數(shù)是一個(gè)非常好的習(xí)慣，它確實(shí)非常有效。如果不知道正確的初始值，那么就將指針賦值為NULL，那么它將不會(huì)指向任何數(shù)據(jù)。大部分環(huán)境下，NULL是一個(gè)無(wú)效的地址，因此任何嘗試讀取數(shù)據(jù)的行為都會(huì)被立即中止。于是這些錯(cuò)誤將相對(duì)比較容易定位和修正。

4、超量寫內(nèi)存
有時(shí)盡管指針被正確地初始化了，但程序員卻不正確地進(jìn)行了指針運(yùn)算或者錯(cuò)誤的內(nèi)存地址操作，這同樣會(huì)引起內(nèi)存管理上的錯(cuò)誤。

第一個(gè)常見(jiàn)的情況是數(shù)組越界；另一個(gè)可能的錯(cuò)誤是分配了不足的內(nèi)存，這種錯(cuò)誤可能有很多情況：

#define array_size 10
int *a = new int[array_size];
... ...
int *b = new int[array_size];
... ...
memcpy(b,a,array_size); // 這個(gè)錯(cuò)誤可能較數(shù)組越界訪問(wèn)更為隱蔽。原意是對(duì)兩個(gè)整型數(shù)組進(jìn)行復(fù)制，但上面的代碼僅僅復(fù)制了其中array_size個(gè)字節(jié)，而事實(shí)上程序要完成既定任務(wù)，用于指示內(nèi)存空間大小的參數(shù)應(yīng)該為array_size*sizeof(int)個(gè)字節(jié)。

再舉一個(gè)分配空間不足的例子。有時(shí)程序員會(huì)因?yàn)榇中亩涀址詈笮枰粋€(gè)結(jié)束符"\0",如果忘記了這一點(diǎn)就有可能引起錯(cuò)誤，考慮下面一段代碼：

char *new_string(char *s)
{
    int len = strlen(s);
    char *new_s = new char[len];
    strcpy(new_s,s);
    return new_s;
}

上述例子中的錯(cuò)誤在于程序沒(méi)有為 string 分配足夠的空間，用于指示新字符串長(zhǎng)度的參數(shù)應(yīng)該是 len +1,這樣才給結(jié)束符留下了一個(gè)字節(jié)。

操作符的優(yōu)先權(quán)也是迷惑程序員并誘使他們犯錯(cuò)的一個(gè)常見(jiàn)因素，在本章前面關(guān)于指針運(yùn)算的介紹中強(qiáng)調(diào)過(guò)這一點(diǎn)，不慎地使用*和++（或--）,都有可能導(dǎo)致超量寫內(nèi)存。

另一個(gè)可能的錯(cuò)誤是構(gòu)造一個(gè)指向運(yùn)行時(shí)棧中某值的指針，并將這個(gè)指針?lè)祷亟o函數(shù)調(diào)用者，例如：

int *p()
{
   int i=0;
   return &i;

盡管函數(shù)返回了一個(gè)指向零值整型的指針，但由于該整型變量位于一個(gè)活動(dòng)記錄中，而這個(gè)記錄在函數(shù)返回時(shí)就會(huì)被刪除。因此這個(gè)指針指向的內(nèi)容隨時(shí)會(huì)變成任何一個(gè)值，這完全取決于下一個(gè)使用它的函數(shù)如何操作它。

大整數(shù)乘法問(wèn)題：（或許是我想復(fù)雜了）

#include <iostream>
#include <memory.h>
#define SIZE 14
using namespace std;

// 返回位數(shù)為 size1+size2
int* multi(int* num1,int size1, int* num2, int size2)
{
    int size = size1 + size2;
    int* ret = new int[size];
    int i=0;
    memset(ret,0,sizeof(int)*size);
    for(i=0;i<size2;++i){
       int k = i;
       for(int j=0;j<size1;++j)
          ret[k++] += num2[i] * num1[j];
    }
    
    for(i=0;i<size;++i){
       if(ret[i]>=10)
       {
           ret[i+1]+=ret[i]/10;
           ret[i]%=10;
       }
    }
    return ret;
}

int main(int argc, char** argv){
     int num1[SIZE]={1,2,3,4,5,6,7,8,9,1,1,1,1,1}; //第1個(gè)大整數(shù) 11111987654321
     int num2[SIZE]={1,1,1,2,2,2,3,3,3,4,4,4,5,5}; //第2個(gè)大整數(shù) 55444333222111
     int* ret = multi(num1,SIZE,num2,SIZE);
     for(int i=SIZE*2-1;i>=0;i--) cout<< ret[i];
     delete[] ret;
     return 0;

關(guān)于數(shù)組的引用

#include<iostream>
using namespace std;
int main(int argc,char* argv[]){
     int a[10] = {0,1,2,3,4,5,6,7,8,9};
     int *p;
     p= &a[0];
     cout<<a[0]<<endl;
     cout<<&a[0]<<endl;
     cout<<&a<<endl;
     cout<<a<<endl;
     cout<<p<<endl;
     cout<< *p<<endl;
     return 0;
}

可見(jiàn)指針p中存放著數(shù)組a的第一個(gè)元素a[0]處的地址，數(shù)組a的地址&a和數(shù)組名a的值都與首元素a[0]處的地址相同。*p的內(nèi)容就是首元素a[0]的值。p+offset就是a[offset]的地址，或者說(shuō)將指針p移動(dòng)偏移量offset后，它就指向數(shù)組a中的第offset個(gè)元素。

#include<iostream>
using namespace std;
int main(int argc, char* argv[]){
     int a[10] = {0,1,2,3,4,5,6,7,8,9};
     int *p;
     p = &a[0];
     cout<< *(p++)<<endl;
     p = &a[0];
     cout<< *p++<<endl;
     p = &a[0];
     cout<< *(++p)<<endl;
     return 0;
}

• (*p)++ 表示p所指向的內(nèi)容加1，在上例中，若p=&a[0]且a[0]=0,則(*p)++=1;
• 如果p當(dāng)前指向數(shù)組a中的第i個(gè)元素，那么有如下結(jié)論：
  *(--p)與a[--i]的作用相同，p先自減，再做*運(yùn)算；
  *(p--)與a[i--]的作用相同，先進(jìn)行p運(yùn)算，p再自減；
  *(++p)與a[++i]的作用相同，p先自加，再做運(yùn)算。

需要說(shuō)明的是，最后一點(diǎn)將指針運(yùn)算和數(shù)組名a聯(lián)系了起來(lái)。但兩者并不能完全等同視之，即并非所有的運(yùn)算都一樣。特別地，可以通過(guò)指針運(yùn)算來(lái)改變指針變量的值（也就是使指針向上或者向下移動(dòng)），但是不能將同樣的操作運(yùn)用于a，即不存在a++之類的運(yùn)算。只是因?yàn)閍表示的是數(shù)組首元素的地址，它是一個(gè)指針常量，所包含的值在程序運(yùn)行時(shí)是不能被改變的。這相當(dāng)于"int i=0;i++;" 是可行的，但"int i=1++;" 則是錯(cuò)誤的。這里定義一個(gè)二維數(shù)組a[3][3],則這個(gè)二維數(shù)組中各項(xiàng)在內(nèi)存中的排序?yàn)閍00,a01,a02,a10,a11,a12,a20,a21,a22。可以試圖將其推廣到更加復(fù)雜和通用的情況下，例如，有一個(gè)二維數(shù)組b[M][N]，若將其轉(zhuǎn)化成一個(gè)一維數(shù)組B[MN],那么原二維數(shù)組中的b[m][n]項(xiàng)就對(duì)應(yīng)一維數(shù)組中的B[(m+1)(n+1)-1].

基于上面的認(rèn)識(shí)，可以編寫一個(gè)簡(jiǎn)單的示例小程序如下：（遍歷二維數(shù)組的正確方式）

#include<iostream>
using namespace std;
int main(int argc,char* argv[]){
     int a[3][3] = {0,1,2,3,4,5,6,7,8};
     int *p;
     p=&a[0][0];
     for(int i=0;i<9;i++) cout<<*p++<<endl;
     return 0;
}

數(shù)組的抽象數(shù)據(jù)類型

前面的介紹多偏重于數(shù)組的語(yǔ)法形式，一維數(shù)組其實(shí)是一個(gè)連續(xù)存儲(chǔ)的線性表，而由于高維數(shù)組都可以轉(zhuǎn)化成對(duì)應(yīng)的一維數(shù)組，所以從這個(gè)角度來(lái)說(shuō)，數(shù)組就是一個(gè)連續(xù)存儲(chǔ)的線性表。

C++中的字符串

字符串是n個(gè)字符的有限序列，其中n>=0，例如"Hello World!" 。這些字符在內(nèi)存中按順序逐個(gè)存放，并以結(jié)束符"\0"結(jié)尾。
string 類的操作符：
== 是用來(lái)判斷字符串s 和字符串t 是否相等
!= 是用來(lái)判斷字符串s 和字符串t 是否不相等
（其實(shí)，我更想知道，字符串的小于、大于是怎么比較的，應(yīng)該是從第一個(gè)字母開(kāi)始，然后如果第一個(gè)字母是相等的，那么就接著比較第二個(gè)字母了，如果第二個(gè)字母是相等的，那么就接著比較第三個(gè)字母這樣。）
string append(const chars); 該函數(shù)的作用是將字符串s追加到本字符串的末尾。
string assign(const chars); 該函數(shù)的作用是將字符串s賦給本字符串。
int compare(const string& str) const; 該函數(shù)的作用是比較兩個(gè)字符串是否相同。
string& insert(unsigned int p0,const char *s); 該函數(shù)的作用是將字符串s插入到本字符串p0位置之前。
string substr(unsigned int pos,unsigned int n)const; 該函數(shù)的作用是取出本字符串中位置pos開(kāi)始的n個(gè)字符，并將該新字符串返回。
unsigned int find(const basic_string& str)const;
該函數(shù)的作用是查找子字符串str在本字符串中第一次出現(xiàn)的位置。
unsigned int length()const;
該函數(shù)的作用是獲得本字符串的長(zhǎng)度。
void swap(string& str);
該函數(shù)的作用是將本字符串與字符串str進(jìn)行交換。

文本的精確匹配

字符串是一種線性表，它在計(jì)算機(jī)應(yīng)用系統(tǒng)（如文本編輯、情報(bào)檢索、拼寫檢查、互聯(lián)網(wǎng)搜索引擎和自然語(yǔ)言翻譯等）中有著廣泛的應(yīng)用。模式匹配是指在目標(biāo)文本串T（to,t1,t2,t3,...,tn-1)中檢索子串P(p0,p1,p2,p3,...,pm-1)的過(guò)程，其中P成為模式（Pattern）。若能夠在T中找到子串P，則稱為匹配成功，否則匹配失敗。