淺析C基礎(chǔ)知識(shí)

1、淺析C 基礎(chǔ)知識(shí)淺析C 基礎(chǔ)知識(shí)1一、C/C+基礎(chǔ)知識(shí)31. C/C+內(nèi)存管理32.小端存儲(chǔ)和大端存儲(chǔ)43.C+的指針使用44.運(yùn)算符優(yōu)先級(jí)45.二維數(shù)組的動(dòng)態(tài)申請(qǐng)56.extern "C"聲明的作用57.指針和引用的區(qū)別，指針和數(shù)組的區(qū)別,const與define的區(qū)別58.如何判定程序是由C/C+編譯器編譯出來的？59.const的作用，static的作用510.變量字節(jié)對(duì)齊：為了加快內(nèi)存尋址的效率，在C+內(nèi)存管理時(shí)一般選取的是4字節(jié)對(duì)齊511.const與指針612.操作符重載613.函數(shù)調(diào)用傳值與傳引用714.volatile與C/C+的四種cast函數(shù)7

2、15.C+ 類的實(shí)例化如果沒有參數(shù)是不需要括號(hào)的，否者就是調(diào)用函數(shù)并且返回對(duì)應(yīng)的對(duì)象716.const修飾函數(shù)時(shí)，標(biāo)志該函數(shù)不會(huì)修改this指針的內(nèi)容817.const可以重載，這是基于編譯器編譯時(shí)對(duì)函數(shù)進(jìn)行重命名實(shí)現(xiàn)的818.override(覆蓋), overload（重載）, polymorphism（多態(tài)）819.const char* a, char const*, char*const的區(qū)別820.typename和class的區(qū)別8二、面向?qū)ο蠛虲+特性描述91.面向?qū)ο笕齻€(gè)基本特征92.多態(tài)93.什么是純虛函數(shù)和純虛類94.什么是虛函數(shù)95.運(yùn)行時(shí)綁定和虛函數(shù)表96.空類的大小

3、不是零97.深拷貝與淺拷貝108.只要在基類中使用了virtual關(guān)鍵字，那么派生類中無(wú)論是否添加virtual，都可以實(shí)現(xiàn)多態(tài)109.虛擬析構(gòu)函數(shù)1010.public,protected, private權(quán)限1011.可重入函數(shù)（多線程安全），即該函數(shù)可以被中斷，就意味著它除了自己棧上的變量以外不依賴任何環(huán)境1012.操作系統(tǒng)內(nèi)存管理有堆式管理、頁(yè)式管理、段式管理和段頁(yè)式管理1013.C+四種CAST操作符1014.shared_ptr是一個(gè)包含引用計(jì)數(shù)的智能指針12三、基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)編程知識(shí)131.數(shù)組13排序13具體的每種排序算法的實(shí)現(xiàn)14字符串處理程序16鏈表處理 

4、0;19二叉樹處理19其他21四、STL基礎(chǔ)知識(shí)211.STL212.STL容器簡(jiǎn)介213. list使用224. stack使用225. vector使用226. Map/HashMap使用22五、多線程和網(wǎng)絡(luò)編程231.原子鎖 自旋鎖 信號(hào)量 互斥鎖232.C+多線程和多進(jìn)程233.TCP三次握手過程244.socket編程基礎(chǔ)245. 短連接和長(zhǎng)連接246. 多線程編程基礎(chǔ)247. TCP與UDP的區(qū)別258. OSI7層模型259. C+實(shí)現(xiàn)單例模式2510. C+異常處理2611. 多線程編程2612. SQL注入26六、C+ 語(yǔ)言新特性26七、其他計(jì)算機(jī)基礎(chǔ)知識(shí)26參考文獻(xiàn)：261

5、.進(jìn)程內(nèi)存空間262.原子操作、信號(hào)量、自旋鎖、互斥鎖263.二叉樹面試題目274. 多線程同步方法275.OSI 7層模型276. C+四種CAST277. 數(shù)據(jù)庫(kù)存儲(chǔ)過程介紹278.C+ 11的新特性- auto的使用279. Boost總結(jié)匯總27來源：極客頭條    最近想對(duì)C+的面試題目進(jìn)行一下更加具體的整理。其實(shí)認(rèn)真思考一下C+程序員的面試，我們可以發(fā)現(xiàn)對(duì)程序員的能力的考察總是萬(wàn)變不離其中，這些基礎(chǔ)知識(shí)主要分為五部分：一、C/C+基礎(chǔ)知識(shí)二、C/C+的一些特性，如面向?qū)ο螅瑑?nèi)存管理 三、基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)編程的知識(shí)。 四、stl的一些基礎(chǔ)知識(shí)。五、網(wǎng)絡(luò)編程

6、、多線程的知識(shí)、異常處理基礎(chǔ)知識(shí)    本文試圖覆蓋C/C+面試的每一個(gè)知識(shí)點(diǎn)，所以對(duì)每個(gè)知識(shí)點(diǎn)介紹的并不深入。本文適合已經(jīng)對(duì)一下具體知識(shí)有所了解的人，我對(duì)每個(gè)點(diǎn)都有粗略的講解，如果想深入理解請(qǐng)閱讀相關(guān)具體知識(shí)。一、 C/C+的基礎(chǔ)知識(shí)：包括指針、字符串處理、內(nèi)存管理。二、面向?qū)ο蠡A(chǔ)知識(shí)：包括多態(tài)、繼承、封裝。 多態(tài)的實(shí)現(xiàn)方式？多態(tài)的好處？三、基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)面試：數(shù)組、鏈表、字符串操作、二叉樹。這里要說的話就說的很多了，具體的有使用一些數(shù)據(jù)結(jié)構(gòu)包括stl list, vector, map, hashmap, set。四、stl的一些基礎(chǔ)知識(shí)。五、網(wǎng)絡(luò)編程、多線程和異常處

7、理的基礎(chǔ)知識(shí)。六、C+ 語(yǔ)言新特性。七、其他計(jì)算機(jī)基礎(chǔ)。一、C/C+基礎(chǔ)知識(shí)1. C/C+內(nèi)存管理C/C+的內(nèi)存分為：堆、棧、自由數(shù)據(jù)區(qū)、靜態(tài)數(shù)據(jù)區(qū)和常量數(shù)據(jù)區(qū)。棧： 函數(shù)執(zhí)行時(shí)，函數(shù)內(nèi)部的局部變量在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束棧的存儲(chǔ)空間被自動(dòng)釋放。堆：就是那些new分配的內(nèi)存塊，需要程序員調(diào)用delete釋放掉。自由數(shù)據(jù)區(qū)：就是那些調(diào)用malloc的內(nèi)存塊，需要程序員調(diào)用free釋放掉。全局存儲(chǔ)區(qū)：全局變量和靜態(tài)變量被存放到同一塊存儲(chǔ)區(qū)域。靜態(tài)存儲(chǔ)區(qū)：這里存放常量，不允許修改。堆和棧的區(qū)別：a.管理方式不同：堆需要程序員手動(dòng)維護(hù)。 b.棧的存儲(chǔ)空間遠(yuǎn)小于堆。堆幾乎不受限制。 c.生長(zhǎng)方

8、式不同。棧是從高地址空間向低地址空間生長(zhǎng)，堆是從低地址空間向高地址空間生長(zhǎng)。 d.效率不同：棧要遠(yuǎn)快于堆。new和delete的區(qū)別：new和delete是C+的函數(shù)會(huì)調(diào)用，構(gòu)造函數(shù)和析構(gòu)函數(shù)。而malloc和delete只是分配對(duì)應(yīng)的存儲(chǔ)空間。注意問題： 1. 意外處理：內(nèi)存申請(qǐng)失敗處理。2.內(nèi)存泄漏：申請(qǐng)的地址空間一定要釋放。 3.野指針：避免指針未賦值使用，一定要初始化。給出一個(gè)圖吧，關(guān)于內(nèi)存空間的分配的： 左邊的是UNIX/LINUX系統(tǒng)的執(zhí)行文件，右邊是對(duì)應(yīng)進(jìn)程邏輯地址空間的劃分情況。     2.小端存儲(chǔ)和大端存儲(chǔ)小段：高位存在高地址上；大端

9、：低位存在高地址上。判定代碼：unsigned short test = 0x1234;if( *(unsigned char *)&test=0x12 )/return Big_Edian;/高位在低地址空間 大端存儲(chǔ)3.C+的指針使用a. 指針數(shù)組 與 數(shù)組指針： 注意的結(jié)合優(yōu)先級(jí)比*要高。那么int *p3；我們就得到了一個(gè)數(shù)組，數(shù)組的每個(gè)元素是int *的。而int (*p)3;/我們就得到了一個(gè)指針，指向的是一個(gè)長(zhǎng)度為3的一維數(shù)組。b. 函數(shù)指針：例如對(duì)函數(shù)：int funcA(int a,int b); 

10、 我們可以定義一個(gè)指針指向這個(gè)函數(shù)：int (*func)(int,int);  func=funcA;c. ptr+; 指針ptr的值加上了sizeof(ptr); 4.運(yùn)算符優(yōu)先級(jí)a. 比較?？嫉木褪?+和-與*、&、.的優(yōu)先級(jí)對(duì)比；注意正確的優(yōu)先級(jí)是：.  >  +  >  -  >  *  >  &5.二維數(shù)組的動(dòng)態(tài)申請(qǐng)int *a=new int *10;for(i=0;i<10;i+)ai=new int10;6.ex

11、tern "C"聲明的作用C+中引用C語(yǔ)言的函數(shù)和變量需要使用extern "C"來進(jìn)行修飾。因?yàn)镃+為了支持多態(tài)，函數(shù)和變量命名的方式和C不同，因此如果一個(gè)模塊的函數(shù)和變量需要被其他模塊使用，就需要使用extern "C"來修飾。該修飾制定編譯器變量和函數(shù)是按照C語(yǔ)言方式進(jìn)行鏈接的。7.指針和引用的區(qū)別，指針和數(shù)組的區(qū)別,const與define的區(qū)別指針和引用的區(qū)別：引用可以看作是變量的別名，不可以指向其他的地址，不能為空。指針和數(shù)組的區(qū)別：指針可以指向其他地址，使用sizeof計(jì)算時(shí)兩者的結(jié)果不同。onst與指針的區(qū)別：cons

12、t定義的變量有類型，而define只是編譯器的簡(jiǎn)單替換。8.如何判定程序是由C/C+編譯器編譯出來的？#ifdef _cplusplus#else#endif9.const的作用，static的作用 a. const 指定變量不可修改。b. static 指定變量存在靜態(tài)數(shù)據(jù)區(qū)，并且只初始化一次。10.變量字節(jié)對(duì)齊：為了加快內(nèi)存尋址的效率，在C+內(nèi)存管理時(shí)一般選取的是4字節(jié)對(duì)齊如下變量占用8個(gè)字節(jié)：struct Nodeint a,char b;11.const與指針char * const p; /指針不可改char const *p; /指針指向的對(duì)象不可修改12.操作符重載C/

13、C+ 里大多數(shù)運(yùn)算符都可以在 C+ 中被重載。C 的運(yùn)算符中只有 . 和 ?:（以及sizeof，技術(shù)上可以看作一個(gè)運(yùn)算符）不可以被重載。C+ 增加了一些自己的運(yùn)算符，除了 : 和 .* 外，大多數(shù)都可以被重載。a. 單目操作符：Point &Point: operator+();/+a;Point &Point: operator+(int);/a+b. 雙目操作符：Point &Point: operator+=(Point b)/ +=源代碼如下：1. class Point 

14、0;2. public:  3.     int x;  4.     int y;  5. public:  6.     void Print()  7.         cout<<"x="<<this->x<

15、;<endl;  8.         cout<<"y="<<this->y<<endl;  9.       10.     Point()  11.         x=0;  12.

16、        y=0;  13.       14.     Point(const Point &a)  15.         x=a.x;  16.         

17、;y=a.y;  17.       18.     Point(int x,int y)  19.         this->x=x;  20.         this->y=y;  21.   

18、60;   22.     Point& operator+=(Point b);  23.     Point& operator+();  24.     Point& operator+(int);  25. ;  26. Point& Point:operator+=(Point

19、 b)  27.     x += b.x;  28.     y += b.y;  29.     return *this;  30.   31.   32. Point& Point:operator+()  33.    &

20、#160;this->x+;  34.     this->y+;  35.     return *this;  36.   37. Point& Point:operator+(int)  38.     Point a(*this);  39.     this-

21、>x+;  40.     this->y+;  41.     return a;  42.   43. int main()  44.     Point *a=new Point(1,2);  45.     Point *b=new Poi

22、nt(3,4);  46.     Point c(10,20);  47.     *a+=c;  48.     a->Print();  49.     +c;  50.     c.Print();  51.     

23、;c+;  52.     c.Print();  53.     return 0;  54.   13.函數(shù)調(diào)用傳值與傳引用傳值不會(huì)修改傳入?yún)?shù)的值，而傳引用會(huì)修改傳入?yún)?shù)的值。14.volatile與C/C+的四種cast函數(shù)volatile修飾的變量，編譯器不會(huì)做優(yōu)化，每次都是到內(nèi)存中去讀取或者寫入修改。C+有四種cast函數(shù)：static_cast,dynamic_cast,const_cast,volatile_c

24、ast。15.C+ 類的實(shí)例化如果沒有參數(shù)是不需要括號(hào)的，否者就是調(diào)用函數(shù)并且返回對(duì)應(yīng)的對(duì)象例如如下代碼就會(huì)報(bào)錯(cuò)：1. struct Test  2.   3.     Test(int )    4.     Test()    5.     void fun()    6. ;

25、0; 7.   8. int main(void)  9.   10.     Test a(1);  11.     a.fun();  12.     Test b;  13.     b.fun();  14.    

26、60;return 0;  15.   16.const修飾函數(shù)時(shí)，標(biāo)志該函數(shù)不會(huì)修改this指針的內(nèi)容C+ 里面的const修飾函數(shù)時(shí)，標(biāo)志該函數(shù)不會(huì)修改this指針的內(nèi)容，而且const不能修飾非類內(nèi)部的函數(shù)。17.const可以重載，這是基于編譯器編譯時(shí)對(duì)函數(shù)進(jìn)行重命名實(shí)現(xiàn)的例如f( int a), f(const int a)是兩個(gè)不同的函數(shù)了。18.override(覆蓋), overload（重載）, polymorphism（多態(tài)）19.const char* a, char const*, char*const的區(qū)別const

27、char * pa;/一個(gè)指向const類型的指針char * const pc;/const修飾的指針20.typename和class的區(qū)別在模版中使用時(shí)，class與typename可以替換。在嵌套依賴類型中，可以聲明typename后面的字符串為類型名，而不是變量。例如：1. class MyArray /暫時(shí)還不是很懂，就先睡覺了。  2.    3. public：  4. typedef int LengthType;  5. .  

28、;6.   7.   8. template<class T>  9. void MyMethod( T myarr )   10.    11. typedef typename T:LengthType LengthType;   12. LengthType length = myarr.GetLength; 

29、  13.  二、面向?qū)ο蠛虲+特性描述1.面向?qū)ο笕齻€(gè)基本特征繼承、多態(tài)和封裝。2.多態(tài)多態(tài)是面向?qū)ο罄^承和封裝的第三個(gè)重要特征，它在運(yùn)行時(shí)通過派生類和虛函數(shù)來實(shí)現(xiàn)，基類和派生類使用同樣的函數(shù)名，完成不同的操作和實(shí)現(xiàn)相隔離的另一類接口。多態(tài)提高了代碼的隱藏細(xì)節(jié)實(shí)現(xiàn)了代碼復(fù)用。3.什么是純虛函數(shù)和純虛類有些情況下基類不能對(duì)虛函數(shù)有效的實(shí)現(xiàn)，我們可以把它聲明為純虛函數(shù)。此時(shí)基類也無(wú)法生成對(duì)象。4.什么是虛函數(shù)虛函數(shù)是類內(nèi)部使用virtual修飾的，訪問權(quán)限是public的，并且非靜態(tài)成員函數(shù)。虛函數(shù)是為了實(shí)現(xiàn)動(dòng)態(tài)連接，定義了虛函數(shù)以后對(duì)基類和派生類的虛函數(shù)以同樣形式

30、定義，當(dāng)程序發(fā)現(xiàn)virtual虛函數(shù)以后會(huì)自動(dòng)的將其作為動(dòng)態(tài)鏈接來處理。純虛函數(shù)在繼承類實(shí)現(xiàn)時(shí)，需要全部實(shí)現(xiàn)。如public virtual function f()=0;注：下列函數(shù)不能被聲明為虛函數(shù)：普通函數(shù)（非成員函數(shù)）；靜態(tài)成員函數(shù)；內(nèi)聯(lián)成員函數(shù)；構(gòu)造函數(shù)；友元函數(shù)。5.運(yùn)行時(shí)綁定和虛函數(shù)表動(dòng)態(tài)綁定：綁定的對(duì)象是動(dòng)態(tài)類型，其特性依賴于對(duì)象的動(dòng)態(tài)特性。虛函數(shù)表： C+的多態(tài)是通過動(dòng)態(tài)綁定和虛函數(shù)表來實(shí)現(xiàn)的。這是虛函數(shù)的地址表，存儲(chǔ)著函數(shù)在內(nèi)存的地址。一般類的對(duì)象實(shí)例地址就是虛函數(shù)表。有虛函數(shù)覆蓋時(shí)，虛函數(shù)的地址存儲(chǔ)的是被覆蓋的子類的函數(shù)的地址。其實(shí)知道虛函數(shù)表了，我們就可以通過操作指針的

31、方式訪問一些額外的數(shù)據(jù)（當(dāng)然如果直接寫成代碼會(huì)編譯不通過的）。對(duì)于基類指針指向派生類時(shí)：我們可以通過內(nèi)存訪問派生類未覆蓋基類的函數(shù)，訪問基類的非public函數(shù)。6.空類的大小不是零因?yàn)闉榱舜_保兩個(gè)實(shí)例在內(nèi)存中的地址空間不同。如下，A的大小為1，B因?yàn)橛刑摵瘮?shù)表的大小為4.class A;class B:public virtual A; 多重繼承的大小也是1，如下：                              class

32、 Father1; class Father2;class Child:Father1, Father2;7.深拷貝與淺拷貝C+會(huì)有一個(gè)默認(rèn)的拷貝構(gòu)造函數(shù)，將某類的變量全部賦值到新的類中?？墒沁@種情況有兩個(gè)例外：(1) . 類的默認(rèn)構(gòu)造函數(shù)做了一些額外的事情，比如使用靜態(tài)數(shù)據(jù)統(tǒng)計(jì)類被初始化的次數(shù)（此時(shí)淺拷貝也無(wú)法解決問題，需要額外的修改拷貝構(gòu)造函數(shù)）。 (2). 類內(nèi)部有動(dòng)態(tài)成員：此時(shí)發(fā)生拷貝時(shí)就需要對(duì)類內(nèi)部的動(dòng)態(tài)成員重新申請(qǐng)內(nèi)存空間，然后將動(dòng)態(tài)變量的值拷貝過來。8.只要在基類中使用了virtual關(guān)鍵字，那么派生類中無(wú)論是否添加virtual，都可以實(shí)現(xiàn)多態(tài)9.虛擬析構(gòu)函數(shù)在使用基類指針指向

33、派生類時(shí)，如果沒有定義虛擬析構(gòu)函數(shù)那么派生類的析構(gòu)函數(shù)不會(huì)被調(diào)用，動(dòng)態(tài)數(shù)據(jù)也不會(huì)被釋放。構(gòu)造函數(shù)和析構(gòu)函數(shù)的調(diào)用順序?yàn)椋合然悩?gòu)造函數(shù)，再派生類構(gòu)造函數(shù)。析構(gòu)時(shí)，先派生類析構(gòu)函數(shù)，再基類析構(gòu)函數(shù)。10.public,protected, private權(quán)限privated：類成員函數(shù)、友元函數(shù)。 protected：派生類、類成員函數(shù)、友元函數(shù)。public：所有11.可重入函數(shù)（多線程安全），即該函數(shù)可以被中斷，就意味著它除了自己棧上的變量以外不依賴任何環(huán)境12.操作系統(tǒng)內(nèi)存管理有堆式管理、頁(yè)式管理、段式管理和段頁(yè)式管理堆式管理：把內(nèi)存分為一大塊一大塊的，所需程序片段不在主村時(shí)就分配一塊主存

34、程序，把程序片段load入主存。頁(yè)式管理：把主頁(yè)分為一頁(yè)一頁(yè)的，每一頁(yè)的空間都比塊小很多。段式管理：把主存分為一段一段的，每一段的空間比一頁(yè)一頁(yè)的空間小很多。段頁(yè)式管理。 13.C+四種CAST操作符C/C+的強(qiáng)制轉(zhuǎn)換風(fēng)格如下： (T) expression或 T(expression) 函數(shù)風(fēng)格。C+定義了四種轉(zhuǎn)換符： reinterpret_cast、tatic_cast、dynamic_cast和const_cast，目的在于控制類之間的類型轉(zhuǎn)換。reinterpreter_cast <type-id> (expression) 能夠?qū)崿F(xiàn)非相關(guān)類型之間的轉(zhuǎn)換，但只是

35、復(fù)制原的數(shù)據(jù)到目的地址，可能包含無(wú)用值，且不可移植。如：double d=reinterpret_cast<double &>(n);                   const_cast<type-id> expression: 修改const或volatile屬性、消除對(duì)象的常量屬性。   static_cast<type-id> ex

36、pression: 父子類之間轉(zhuǎn)換、空指針->目標(biāo)指針、任何類型轉(zhuǎn)化為void類型、任意類型轉(zhuǎn)換。dynamic_cast<type-id> expression: 是唯一不能用舊風(fēng)格執(zhí)行的強(qiáng)制轉(zhuǎn)換。用于多態(tài)類型的任意隱式類型轉(zhuǎn)換及相反的過程。基類指針轉(zhuǎn)化為派生類時(shí)，基類需要有虛函數(shù)（否則編譯報(bào)錯(cuò))。相對(duì)于static_cast，增加了安全檢驗(yàn)。1. /結(jié)論:父指針指向子對(duì)象地址，不用強(qiáng)轉(zhuǎn)，即可。  2. /基類沒有虛函數(shù)時(shí)，只有static_cast可以編譯通過?；愑刑摵瘮?shù)時(shí)dynamic_cast也可以編譯通過。  3. clas

37、s Base  4.   5. public:  6. Base()a1=1;  7. virtual void test()  8. int a1;  9. ;  10. class Derive:public Base  11.   12. public:  13. Derive()a2=2;  14. int&#

38、160;a2;  15. ;  16. int main(int argc, char *argv)  17.   18. Base *pb;  19. Derive *pd;  20. Base b;  21. Derive d;  22. cout <<"&b:"<<&b<<

39、;endl;  23. cout<<"&d:"<<&d<<endl;  24.   25. pb=&d;  26. cout<<_LINE_<<"pb:"<<pb<<endl;  27. pb=static_cast<Base*>(&d);  28. cout<<_LINE_<<&quo

40、t;pb:"<<pb<<endl;  29. pb=dynamic_cast<Base*>(&d);  30. cout<<_LINE_<<"pb:"<<pb<<endl;  31.   32. /pd=&b;/error  33. /cout<<_LINE_<<"pd:"<<pd<<endl;

41、60; 34. pd=static_cast<Derive*>(&b);  35. cout<<_LINE_<<"pd:"<<pd<<endl;  36. pd=dynamic_cast<Derive*>(&b);/error  37. cout<<_LINE_<<"pd:"<<pd<<endl;  38.   

42、39. return 0;  40.   14.shared_ptr是一個(gè)包含引用計(jì)數(shù)的智能指針?biāo)囊糜?jì)數(shù)是安全且無(wú)鎖的，但內(nèi)存對(duì)象的讀寫不是，因?yàn)閟hared_ptr有兩個(gè)數(shù)據(jù)成員，讀寫操作不能原子化。shared_ptr的線程安全級(jí)別和內(nèi)建類型、標(biāo)準(zhǔn)庫(kù)容器、string一樣。shared_ptr實(shí)體可以被兩個(gè)線程同時(shí)寫入。如果要從多個(gè)線程同時(shí)讀寫一個(gè)shared_ptr對(duì)象，那么需要加鎖。使用示例如下：1. #include "boost/shared_ptr.hpp"  2. #incl

43、ude <cassert>  3. #include <stdlib.h>  4. #include <iostream>  5. #include "boost/make_shared.hpp"  6. using namespace std;  7. class shared        

44、;                            /一個(gè)擁有shared_ptr的類    8.   9. private:  10.         

45、boost:shared_ptr<int> p;                          /shared_ptr成員變量    11. public:  12.        &

46、#160;shared(boost:shared_ptr<int> p_):p(p_)          /構(gòu)造函數(shù)初始化shared_ptr        13.         void print()        

47、60;                       /輸出shared_ptr的引用計(jì)數(shù)和指向的值        14.           15.    &#

48、160;            cout << "count:" << p.use_count() << " v=" <<*p << endl;  16.         

49、0; 17. ;  18. void print_func(boost:shared_ptr<int> p)                               /使用shared_ptr作為函數(shù)參數(shù) 

50、0;  19.   20.         /同樣輸出shared_ptr的引用計(jì)數(shù)和指向的值        21.         cout << "count:" << p.use_count() <<

51、0;" v=" <<*p << endl;  22.   23. void f()  24.   25.         typedef vector<boost:shared_ptr<int> > vs;    /一個(gè)持有shared_ptr的標(biāo)準(zhǔn)容

52、器類型        26.         vs v(10);                              

53、60;/聲明一個(gè)擁有10個(gè)元素的容器，元素被初始化為空指針         27.         int i = 0;  28.         for (vs:iterator pos = v.begin(); pos != 

54、v.end(); +pos)  29.           30.                 (*pos) = boost:make_shared<int>(+i);     /使用工廠函數(shù)賦值  &#

55、160;         31.                 cout << *(*pos) << ", "            

56、/輸出值        32.           33.         cout << endl;  34.         boost:shared_ptr<int> p 

57、;= v9;  35.         *p = 100;  36.         cout << *v9 << endl;  37.   38. int main()  39.   40.   

58、;      boost:shared_ptr<int> p(new int(100);  41.         shared s1(p);  42.         s1.print();  43.       &

59、#160; shared s2(p);                        /構(gòu)造兩個(gè)自定義類         44.         s1.print();&

60、#160; 45.         s2.print();  46.         *p = 20;                        

61、            /修改shared_ptr所指的值        47.         print_func(p);  48.         s1.print();  49.  

62、 50.         f();  51.   52.   53. /對(duì)應(yīng)于shared_ptr的是<span style="font-family: Arial, Helvetica, sans-serif;">static_pointer_cast 和 dynamic_pointer_cast，它的用法和static_cast、dynamic_cas

63、t很像。</span>  三、基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)編程知識(shí)其實(shí)我理解作為面試來說，一般會(huì)面時(shí)應(yīng)聘者的基礎(chǔ)知識(shí)，如果對(duì)于過于復(fù)雜的圖程序，動(dòng)態(tài)規(guī)劃一般不太適合。而對(duì)于數(shù)組、鏈表、二叉樹、字符串處理的考察，既能考察出應(yīng)聘者的基礎(chǔ)知識(shí)、代碼風(fēng)格、命名書寫規(guī)范，又能考察出應(yīng)聘者的代碼是否包含bug。而比較深入的一些題目一般只作為腦筋急轉(zhuǎn)彎或者給出思路，博主在此提醒各位，面試時(shí)準(zhǔn)確性更加重要，如果一時(shí)想不出來，可以首先給出一個(gè)效率較低的實(shí)現(xiàn)，然后再一步步優(yōu)化（注意邊界條件，小心謹(jǐn)慎測(cè)試）。下面分析一下對(duì)于數(shù)組、鏈表、二叉樹和字符串處理的常考題目：1. 數(shù)組：一般到了數(shù)組就會(huì)考察

64、排序（穩(wěn)定性、平均、最好、最差時(shí)間復(fù)雜度/內(nèi)存使用、不同情況下那種最快）、二分的特性。2. 鏈表：鏈表的插入，逆序，判斷鏈表相交，找到鏈表交點(diǎn)，鏈表的刪除。3. 二叉樹：二叉樹的深度、前序/中序/后序遍歷、二叉樹的葉子數(shù)目、二叉樹的節(jié)點(diǎn)數(shù)目、二叉樹的層次遍歷。4. 字符串的處理：atoi，itoa，字符串替換、字符串的查找。再次特意提醒一下，字符串處理設(shè)計(jì)指針的處理所以指針的內(nèi)存訪問控制，需要使用更多的注意，比如參數(shù)為空，內(nèi)存申請(qǐng)失敗，返回值控制，指針加減。   1.數(shù)組排序各種排序算法的對(duì)比如下圖所示 。排序法平均時(shí)間最差情形穩(wěn)定度額外空間備注冒泡O(n2)O(

65、n2)穩(wěn)定O(1)n小時(shí)較好交換O(n2)O(n2)不穩(wěn)定O(1)n小時(shí)較好選擇O(n2)O(n2)不穩(wěn)定O(1)n小時(shí)較好插入O(n2)O(n2)穩(wěn)定O(1)大部分已排序時(shí)較好基數(shù)O(logRB)O(logRB)穩(wěn)定O(n)B是真數(shù)(0-9)，R是基數(shù)(個(gè)十百)ShellO(nlogn)O(ns) 1<s<2不穩(wěn)定O(1)s是所選分組快速O(nlogn)O(n2)不穩(wěn)定O(nlogn)n大時(shí)較好歸并O(nlogn)O(nlogn)穩(wěn)定O(1)n大時(shí)較好堆O(nlogn)O(nlogn)不穩(wěn)定O(1)n大時(shí)較好具體的每種排序算法的實(shí)現(xiàn)a) 快速排序?qū)崿F(xiàn)：1. int pa

66、rtition(int a,int low,int high)  2.     int data=alow,tem;  3.     int i=low+1,j=low+1;  4.   5.     while(j<=high)  6.        

67、 if(aj>data)  7.             j+;  8.         else  9.             tem=ai;  10.   &

68、#160;         ai=aj;  11.             aj=tem;  12.             i+;  13.      

69、60;      j+;  14.           15.       16.     alow=ai-1;  17.     ai-1=data;  18.     return i-

70、1;  19.   20.   21.   22.   23. void qsort1(int a,int low,int high)  24.     if(low>=high)  25.         return;  26.    &#

71、160;int mid=partition(a,low,high);  27.     if(mid-1>low)  28.         qsort1(a,low,mid-1);  29.     if(high>mid+1)  30.         

72、qsort1(a,mid+1,high);  31.   32.   b) 堆排序?qū)崿F(xiàn)：1. void HeapModify(int a, int i, int length)  2.     int j=-1;  3.     if( i*2+1 < length )  4. &#

73、160;       if( ai*2+1>ai)  5.             j=i*2+1;  6.           7.       8.    &#

74、160;if( i*2 +2 < length)  9.         if( ai*2 +2 > ai && a2*i+2 > a2*i+1)  10.               

75、  j=i*2+2;  11.           12.       13.   14.     if( j> 0)  15.         int tem;  16.  

76、;       tem=ai;  17.         ai=aj;  18.         aj=tem;  19.         HeapModify(a,j,length);  20.  

77、     21.   22. void Heap_sort(int a,int length)  23.     int i,tem;  24.     for(i=length/2;i>=0;i-)  25.         HeapModify(a,i,len

78、gth);  26.       27.   28.     for(i=0;i<length-1;i+)  29.         tem=a0;  30.         a0=alength-1-i;  31.  &#

79、160;      alength-1-i=tem;  32.         HeapModify(a,0,length-i-1);  33.       34.   c ) 最大子數(shù)組求和：1. int atoi1(char *str)  2.    &#

80、160;assert(str!=NULL);  3.     int result=0,pos=1;  4.     if(*str='-')  5.         pos=-1;  6.         str+;  7.

81、60;     8.     while(*str!='0')  9.         assert(*str<='9'&&*str>='0');  10.         result=result*10+*str-'0&#

82、39;  11.         str+;  12.       13.     return result*pos;  14.   15.   字符串處理程序a). atoi實(shí)現(xiàn)：1. int atoi1(char *str)  2.   

83、60; assert(str!=NULL);  3.     int result=0,pos=1;  4.     if(*str='-')  5.         pos=-1;  6.         str+;  7

84、.       8.     while(*str!='0')  9.         assert(*str<='9'&&*str>='0');  10.         result=result*10+*str-

85、9;0'  11.         str+;  12.       13.     return result*pos;  14.   15.   b). itoa實(shí)現(xiàn)：1. char *itoa1(int num,int k)  2.  

86、   char data="0123456789ABCDEF"  3.     bool pos=true;  4.     int count=1,tem;  5.     int num1=num;  6.     if(num<0)  7

87、.         num=-num;  8.         pos=false;  9.         count+;  10.       11.     while(num>0)

88、60; 12.         num=num/k;  13.         count=count+1;  14.       15.     char *result=new charcount;  16.    

89、 char *presult=result,*pstr;  17.     if(pos=false)  18.         *presult+='-'  19.       20.     pstr=presult;  21.   22.

90、     while(num1>0)  23.         *presult+=datanum1%k;  24.         num1=num1/k;  25.       26.     *presult-='0&#

91、39;  27.     while(pstr<presult)  28.         tem=*pstr;  29.         *pstr=*presult;  30.         *presult=tem; 

92、; 31.         *presult-;  32.         *pstr+;  33.       34.   35.     return result;  36.  c). 將字符串空格替換為目的串的實(shí)現(xiàn)：1.

93、char * Replace_Str(char * str, char * target)  2.     assert(str!=NULL&&target!=NULL);  3.     char *pstr=str;  4.     int count=0;  5.   

94、;  while(*pstr!='0')  6.         if(*pstr=' ')  7.             count+;  8.           9. &

95、#160;  pstr+;  10.   11. char * result=new charsizeof(str)+count*strlen(target);  12. char *presult=result;  13. for(pstr=str;pstr!='0'pstr+)  14.     if(*pstr!=' ')  15

96、.         *presult=*pstr;  16.       17.     else  18.         char *ptarget=target;  19.        

97、60;while(*ptarget!='0')  20.             *presult+=*ptarget+;  21.           22.       23.   24. *presult='0' 

98、; 25. return result;  d). strcpy實(shí)現(xiàn)：1. void strcpy1(char * source, char * dest)  2.     assert(source!=NULL&&dest!=NULL);  3.     char * psource=source, *pdest=dest;

99、60; 4.     while(*psource!='0')  5.         *pdest+=*psource+;  6.       7.     *pdest='0'  8.   e). 查找目的串第一次出現(xiàn)位置（最快的肯定是KMPO(M+N)

100、），或者查找目的串在源串中的出現(xiàn)次數(shù)：1. <span style="font-size:14px;">int Find_Str(const char* source,const char* target) /查找目的串在源串中出現(xiàn)的位置，最弱的方法  2.     assert(source!=NULL&&target!=NULL);  3.   4.   

101、  int i,j,i1;  5.     int len_source=strlen(source),len_target=strlen(target);  6.   7.     for(i=0;i<len_source;i+)  8.         i1=i;  9.  &#

102、160;      for(j=0;sourcei1=targetj&&j<len_target;i1+,j+);  10.         if(j=len_target)  11.             return i;  12. 

103、0;     13.     return -1;  14. </span>  f). memcopy實(shí)現(xiàn)：1. void *memcpy1(void * dest, const void * source, size_t num)/注意需要考慮內(nèi)存重疊的部分，特別的dest在source數(shù)據(jù)區(qū)間內(nèi)部時(shí)候的處理  2.  &#

104、160;  assert(dest!=NULL&&source!=NULL);  3.     int i;  4.     byte *psource=(byte *) source;  5.     byte *pdest=(byte *) dest;  6.   7.     if(pdest>psource&&pdest<psource+num)  8.         for(i=num-1;i&g