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

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

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

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

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ù)备蚓。換句話說课蔬，結(jié)構(gòu)化的數(shù)據(jù)可以由簡單的數(shù)據(jù)組成。將某人的聯(lián)系地址想象一個(gè)結(jié)構(gòu)化的數(shù)據(jù)郊尝，那么在這個(gè)結(jié)構(gòu)中可能有若干個(gè)項(xiàng)目二跋，它們都是一些簡單的基本數(shù)據(jù)。例如流昏，居住地的門牌號(hào)扎即，然后是所在街道的名字、城市的名字况凉、省份的名稱和郵政編碼谚鄙、

C++中的STL

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

標(biāo)準(zhǔn)模板庫體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic programming）,并引入了諸多新的名字，比如像需求（requirements)跟啤、概念（concept）诽表、模型（model）、容器（container）和迭代器（iterator）等隅肥。這些都是支持泛型思想的概念竿奏，泛型思想也是一種軟件的復(fù)用技術(shù)，這看起來與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ù)铣卡、適配器和空間配置器链韭。下面主要對3大主體進(jìn)行一個(gè)概要介紹。

1.容器
在實(shí)際的開發(fā)過程中算行，數(shù)據(jù)結(jié)構(gòu)本身的重要性不會(huì)遜于操作與數(shù)據(jù)結(jié)構(gòu)的算法的重要性梧油，當(dāng)程序中存在著對時(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ù)都一對 iterator：(first,last), 用來指出容器內(nèi)一個(gè)范圍內(nèi)的元素
• 每個(gè)算法的聲明中，都表現(xiàn)出它所需要的最低層次的iterator 類型枷恕。
• 大部分算法都可以用仿函數(shù)（function object党晋，又稱 functor）來更改準(zhǔn)則。

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

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

3.迭代器
迭代器起初是設(shè)計(jì)模式中的一種酿联，意思是提供一種方法，按順序訪問某個(gè)容器所含的各個(gè)元素夺巩，而無需暴露該容器的內(nèi)部表述方法贞让。這也是軟件設(shè)計(jì)的一個(gè)基本原則，也就是說通過引進(jìn)一個(gè)間接層來簡化所有問題的解決柳譬。在STL中喳张，迭代器被用來將算法和容器聯(lián)系起來，起到某種粘合作用征绎。容器提供迭代器蹲姐，而算法使用迭代器。幾乎STL提供的所有算法都是通過迭代器存取元素序列進(jìn)行工作的人柿，每一個(gè)容器都定義了其本身所專有的迭代器柴墩，用以存取容器中的元素。迭代器能夠使容器與算法不干擾地相互發(fā)展凫岖，最后又能無間隙地粘合起來江咳。特別地，迭代器還重載了*哥放、++歼指、==、甥雕！=踩身、=等運(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í)對象提供機(jī)制情臭。

指針和數(shù)組

數(shù)組是最簡單的省撑、最基本的線性數(shù)據(jù)結(jié)構(gòu)，它可以被認(rèn)為是程序設(shè)計(jì)語言提供的一種已經(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)存管理以及指針方面的內(nèi)容鸿摇，而且指針和數(shù)組之間還具有非常緊密的聯(lián)系。）

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

馮-諾依曼結(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ù)）。換句話說润梯，CPU執(zhí)行的機(jī)器碼通過各內(nèi)存位置的唯一編號(hào)來操作這些內(nèi)存中的數(shù)據(jù)邮破，這些編號(hào)就是所謂的內(nèi)存地址，而編譯器的工作過程就是將程序中的變量和操作翻譯成對內(nèi)存地址進(jìn)行操作的機(jī)器語言仆救。所以抒和，在最終的機(jī)器碼里其實(shí)是不存在變量名或變量類型的。

簡單來說彤蔽，內(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ī)中也提供了對于一個(gè)數(shù)據(jù)的“直接訪問”和“間接訪問” 卖哎。通過變量來訪問數(shù)據(jù)就是間接的訪問方式，通過地址來訪問數(shù)據(jù)就是直接的訪問方式删性。

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

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

對于上例中的指針類型p,如果有操作p++,那么對于指針變量p自加1意味著什么呢译仗？因?yàn)閜是一個(gè)int型指針，因此p++操作意味著將指針p移動(dòng)4個(gè)字節(jié)（假設(shè)一個(gè)int型變量占據(jù)4字節(jié)的空間）官觅∽菥可見正確地定義指針類型是非常重要的。指針是變量的地址休涤，這個(gè)地址的獲得必須通過一個(gè)已經(jīng)被分配了存儲(chǔ)空間的變量來完成咱圆，變量的地址只能通過指針運(yùn)算符*或取地址符&來獲得，而不能直接指定一個(gè)具體的地址功氨。另外序苏，對于&*p 和 *&p的區(qū)別。因?yàn)?和&具有相同的優(yōu)先級捷凄，按照從右向左的方向結(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)簡單，操作方便桶错，但也致使程序的可伸縮性大大降低航唆。因?yàn)樵诤芏嗟那闆r下，程序員無法預(yù)先確定要使用多大的數(shù)組院刁。為了解決這樣的問題糯钙，就需要使用動(dòng)態(tài)內(nèi)存分配。所謂動(dòng)態(tài)內(nèi)存分配就是指在程序執(zhí)行的過程中動(dòng)態(tài)地分配或者回收存儲(chǔ)空間的分配內(nèi)存的方法退腥。由于動(dòng)態(tài)分配不需要預(yù)先分配存儲(chǔ)空間超营，而且分配的空間還可以根據(jù)程序的需要擴(kuò)大或縮小，因此它能夠有效地克服靜態(tài)內(nèi)存分配所帶來的種種弊病阅虫。

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

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

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

1.內(nèi)存泄漏
在分配了一塊內(nèi)存空間之后塑娇，如果不再需要這些數(shù)據(jù)就應(yīng)當(dāng)考慮將其釋放。而如果程序員沒有將其釋放劫侧，那么這塊空間將隨同程序運(yùn)行而一直存在埋酬。對于一個(gè)需要運(yùn)行較長時(shí)間的計(jì)算機(jī)程序而言，如果它只是一味地分配而不進(jìn)行回收烧栋，那么最終系統(tǒng)資源無疑將被耗盡写妥。于是程序在這個(gè)過程中將被運(yùn)行得越來越慢，最終系統(tǒng)陷入癱瘓审姓。在計(jì)算機(jī)中有很多程序要運(yùn)行很長時(shí)間珍特，操作系統(tǒng)實(shí)際上就是一個(gè)"死循環(huán)"。還有很多網(wǎng)絡(luò)服務(wù)程序也會(huì)運(yùn)行很長時(shí)間魔吐。比如一個(gè)圖像處理程序扎筒，它打開的圖片文件可能有幾百字節(jié)莱找，也有可能是幾百兆，如果內(nè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語句經(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;

對于 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)體的一些域并沒有釋放，
例如 name 和 address 都被分配了空間拢蛋，但它們沒有釋放桦他。這里要注意結(jié)構(gòu)體被釋放并不表示它的域也被釋放了！

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

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

下面是可能發(fā)生重復(fù)釋放的情況，首先看一個(gè)例子碳默，下面的例子對同一空間進(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;

程序最開始開辟了一塊內(nèi)存內(nèi)存空間用來存儲(chǔ)一些整型數(shù)據(jù)育灸，并在最后將這些數(shù)據(jù)釋放。但是在程序運(yùn)行過程中調(diào)用一個(gè)函數(shù)“Twice_Free(X);”昵宇，在這個(gè)函數(shù)中x被釋放過了一次磅崭，因此程序發(fā)生了重復(fù)釋放。因?yàn)樵诤芏嗲闆r下瓦哎，指針可能發(fā)生了傳遞砸喻，而傳遞的僅僅是地址，也就是說在一個(gè)程序中可能存在多個(gè)指針同時(shí)指向一塊內(nèi)存空間蒋譬，對于其中任何一個(gè)指針的釋放都會(huì)對這塊空間進(jìn)行回收割岛。但由于其他指針貌似并沒有回收，于是粗心的人就會(huì)畫蛇添足地進(jìn)行重復(fù)釋放犯助⊙⑵幔可以舉一個(gè)更極端的例子來說明這種現(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ū)域，無需釋放3次瞬哼，僅僅釋放其中一次就可以達(dá)到目的。程序訪問一段已經(jīng)被釋放了的內(nèi)存空間可能引起很多危險(xiǎn)坐慰。因?yàn)橐坏﹥?nèi)存塊被釋放，它其中的數(shù)據(jù)就有可能被應(yīng)用程序或堆分配管理器修改赞咙。恰恰在修改之后，這塊被占用的內(nèi)存再次被其他的數(shù)據(jù)塊訪問到糟港，后果就不堪設(shè)想了。一方面你所讀到的程序其實(shí)是無用的着逐，應(yīng)用了這些沒有任何意義的數(shù)據(jù)之后整個(gè)系統(tǒng)的運(yùn)作都有可能受到影響，更糟的情況是你對這個(gè)塊進(jìn)行了寫操作耸别，也就是說你改寫了本不該屬于你的數(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í)候面哼，僅對其中之一賦NULL魔策，并不能從根本上預(yù)防錯(cuò)誤的發(fā)生河胎。總之政敢，務(wù)必保證被分配的內(nèi)存塊僅被釋放一次吭历，保證已經(jīng)被釋放了的指針不會(huì)再次使用晌区。如果這個(gè)指針曾經(jīng)被復(fù)制了通贞，就必須保證當(dāng)它所指向的內(nèi)存區(qū)域被釋放之后，所以的副本都不應(yīng)當(dāng)被使用昌罩。

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

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

那么問題是：壞指針從哪來呢蕾总？一個(gè)不可忽視的根源就是沒有被很好初始化的數(shù)據(jù)琅捏。假設(shè)你聲明了一個(gè)本地指針但忘記了初始化它午绳，因?yàn)樽兞渴潜粌?chǔ)存在棧里的，而椑唬可能充滿了那些來自先前活動(dòng)記錄的數(shù)據(jù)，恰巧這些數(shù)據(jù)沒有被丟棄蠢甲，那么指針就可能帶有它們的值据忘。

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

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

第一個(gè)常見的情況是數(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ù)組越界訪問更為隱蔽罚渐。原意是對兩個(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ò)誤在于程序沒有為 string 分配足夠的空間犁享，用于指示新字符串長度的參數(shù)應(yīng)該是 len +1,這樣才給結(jié)束符留下了一個(gè)字節(jié)炊昆。

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

另一個(gè)可能的錯(cuò)誤是構(gòu)造一個(gè)指向運(yùn)行時(shí)棧中某值的指針渣聚，并將這個(gè)指針返回給函數(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ù)乘法問題：（或許是我想復(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;
}

可見指針p中存放著數(shù)組a的第一個(gè)元素a[0]處的地址，數(shù)組a的地址&a和數(shù)組名a的值都與首元素a[0]處的地址相同序六。*p的內(nèi)容就是首元素a[0]的值蚤吹。p+offset就是a[offset]的地址距辆，或者說將指針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)算。

需要說明的是享言，最后一點(diǎn)將指針運(yùn)算和數(shù)組名a聯(lián)系了起來览露。但兩者并不能完全等同視之，即并非所有的運(yùn)算都一樣命锄。特別地脐恩，可以通過指針運(yùn)算來改變指針變量的值（也就是使指針向上或者向下移動(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)就對應(yīng)一維數(shù)組中的B[(m+1)(n+1)-1].

基于上面的認(rèn)識(shí)瀑罗，可以編寫一個(gè)簡單的示例小程序如下：（遍歷二維數(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ù)組的語法形式斩祭，一維數(shù)組其實(shí)是一個(gè)連續(xù)存儲(chǔ)的線性表乡话，而由于高維數(shù)組都可以轉(zhuǎn)化成對應(yīng)的一維數(shù)組蚊伞，所以從這個(gè)角度來說吮铭，數(shù)組就是一個(gè)連續(xù)存儲(chǔ)的線性表。

C++中的字符串

字符串是n個(gè)字符的有限序列癞揉，其中n>=0溺欧，例如"Hello World!" 姐刁。這些字符在內(nèi)存中按順序逐個(gè)存放，并以結(jié)束符"\0"結(jié)尾壁拉。
string 類的操作符：
== 是用來判斷字符串s 和字符串t 是否相等
!= 是用來判斷字符串s 和字符串t 是否不相等
（其實(shí)弃理，我更想知道痘昌，字符串的小于炬转、大于是怎么比較的扼劈，應(yīng)該是從第一個(gè)字母開始，然后如果第一個(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開始的n個(gè)字符挺物，并將該新字符串返回。
unsigned int find(const basic_string& str)const;
該函數(shù)的作用是查找子字符串str在本字符串中第一次出現(xiàn)的位置砚著。
unsigned int length()const;
該函數(shù)的作用是獲得本字符串的長度赖草。
void swap(string& str);
該函數(shù)的作用是將本字符串與字符串str進(jìn)行交換秧骑。

文本的精確匹配

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