淺析C基礎知識

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

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

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

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

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

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

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

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

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

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

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

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

13、C+ 里大多數(shù)運算符都可以在 C+ 中被重載。C 的運算符中只有 . 和 ?:（以及sizeof，技術上可以看作一個運算符）不可以被重載。C+ 增加了一些自己的運算符，除了 : 和 .* 外，大多數(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ù)調用傳值與傳引用傳值不會修改傳入?yún)?shù)的值，而傳引用會修改傳入?yún)?shù)的值。14.volatile與C/C+的四種cast函數(shù)volatile修飾的變量，編譯器不會做優(yōu)化，每次都是到內存中去讀取或者寫入修改。C+有四種cast函數(shù)：static_cast,dynamic_cast,const_cast,volatile_c

24、ast。15.C+ 類的實例化如果沒有參數(shù)是不需要括號的，否者就是調用函數(shù)并且返回對應的對象例如如下代碼就會報錯：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ù)不會修改this指針的內容C+ 里面的const修飾函數(shù)時，標志該函數(shù)不會修改this指針的內容，而且const不能修飾非類內部的函數(shù)。17.const可以重載，這是基于編譯器編譯時對函數(shù)進行重命名實現(xiàn)的例如f( int a), f(const int a)是兩個不同的函數(shù)了。18.override(覆蓋), overload（重載）, polymorphism（多態(tài)）19.const char* a, char const*, char*const的區(qū)別const

27、char * pa;/一個指向const類型的指針char * const pc;/const修飾的指針20.typename和class的區(qū)別在模版中使用時，class與typename可以替換。在嵌套依賴類型中，可以聲明typename后面的字符串為類型名，而不是變量。例如：1. class MyArray /暫時還不是很懂，就先睡覺了。  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.  二、面向對象和C+特性描述1.面向對象三個基本特征繼承、多態(tài)和封裝。2.多態(tài)多態(tài)是面向對象繼承和封裝的第三個重要特征，它在運行時通過派生類和虛函數(shù)來實現(xiàn)，基類和派生類使用同樣的函數(shù)名，完成不同的操作和實現(xiàn)相隔離的另一類接口。多態(tài)提高了代碼的隱藏細節(jié)實現(xiàn)了代碼復用。3.什么是純虛函數(shù)和純虛類有些情況下基類不能對虛函數(shù)有效的實現(xiàn)，我們可以把它聲明為純虛函數(shù)。此時基類也無法生成對象。4.什么是虛函數(shù)虛函數(shù)是類內部使用virtual修飾的，訪問權限是public的，并且非靜態(tài)成員函數(shù)。虛函數(shù)是為了實現(xiàn)動態(tài)連接，定義了虛函數(shù)以后對基類和派生類的虛函數(shù)以同樣形式

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

31、方式訪問一些額外的數(shù)據(jù)（當然如果直接寫成代碼會編譯不通過的）。對于基類指針指向派生類時：我們可以通過內存訪問派生類未覆蓋基類的函數(shù)，訪問基類的非public函數(shù)。6.空類的大小不是零因為為了確保兩個實例在內存中的地址空間不同。如下，A的大小為1，B因為有虛函數(shù)表的大小為4.class A;class B:public virtual A; 多重繼承的大小也是1，如下：                              class

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

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

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

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

36、pression: 父子類之間轉換、空指針->目標指針、任何類型轉化為void類型、任意類型轉換。dynamic_cast<type-id> expression: 是唯一不能用舊風格執(zhí)行的強制轉換。用于多態(tài)類型的任意隱式類型轉換及相反的過程。基類指針轉化為派生類時，基類需要有虛函數(shù)（否則編譯報錯)。相對于static_cast，增加了安全檢驗。1. /結論:父指針指向子對象地址，不用強轉，即可。  2. /基類沒有虛函數(shù)時，只有static_cast可以編譯通過?；愑刑摵瘮?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是一個包含引用計數(shù)的智能指針它的引用計數(shù)是安全且無鎖的，但內存對象的讀寫不是，因為shared_ptr有兩個數(shù)據(jù)成員，讀寫操作不能原子化。shared_ptr的線程安全級別和內建類型、標準庫容器、string一樣。shared_ptr實體可以被兩個線程同時寫入。如果要從多個線程同時讀寫一個shared_ptr對象，那么需要加鎖。使用示例如下：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、;                            /一個擁有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_)          /構造函數(shù)初始化shared_ptr        13.         void print()        

47、60;                       /輸出shared_ptr的引用計數(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的引用計數(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;    /一個持有shared_ptr的標準容

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

53、60;/聲明一個擁有10個元素的容器，元素被初始化為空指針         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);                        /構造兩個自定義類         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. /對應于shared_ptr的是<span style="font-family: Arial, Helvetica, sans-serif;">static_pointer_cast 和 dynamic_pointer_cast，它的用法和static_cast、dynamic_cas

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

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

65、n2)穩(wěn)定O(1)n小時較好交換O(n2)O(n2)不穩(wěn)定O(1)n小時較好選擇O(n2)O(n2)不穩(wěn)定O(1)n小時較好插入O(n2)O(n2)穩(wěn)定O(1)大部分已排序時較好基數(shù)O(logRB)O(logRB)穩(wěn)定O(n)B是真數(shù)(0-9)，R是基數(shù)(個十百)ShellO(nlogn)O(ns) 1<s<2不穩(wěn)定O(1)s是所選分組快速O(nlogn)O(n2)不穩(wěn)定O(nlogn)n大時較好歸并O(nlogn)O(nlogn)穩(wěn)定O(1)n大時較好堆O(nlogn)O(nlogn)不穩(wěn)定O(1)n大時較好具體的每種排序算法的實現(xiàn)a) 快速排序實現(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) 堆排序實現(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實現(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實現(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). 將字符串空格替換為目的串的實現(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實現(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實現(xiàn)：1. void *memcpy1(void * dest, const void * source, size_t num)/注意需要考慮內存重疊的部分，特別的dest在source數(shù)據(jù)區(qū)間內部時候的處理  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