C和C++經(jīng)典面試習(xí)題(面試必備)

1、C/C+經(jīng)典面試題（面試必備）面試題 1：變量的聲明和定義有什么區(qū)別為變量分配地址和存儲(chǔ)空間的稱(chēng)為定義，不分配地址的稱(chēng)為聲明。一個(gè)變量可以在多個(gè)地方聲明，但是只在一個(gè)地方定義。加入 extern 修飾的是變量的聲明， 說(shuō)明此變量將在文件以外或在文件后面部分定義。說(shuō)明：很多時(shí)候一個(gè)變量，只是聲明不分配內(nèi)存空間，直到具體使用時(shí)才初始化，分配內(nèi)存空間，如外部變量。 面試題 2：寫(xiě)出 bool 、 int、 float、指針變量與“零值” 比較的 if 語(yǔ)句bool 型數(shù)據(jù)：if( flag )A;elseB；int 型數(shù)據(jù)：if( 0 != flag )A;elseB；指針型數(shù)：if( NULL =

2、 flag )A;elseB；float 型數(shù)據(jù)：if ( ( flag = NORM ) & ( flag = NORM ) )A； 2注意：應(yīng)特別注意在 int、指針型變量和“零值”比較的時(shí)候，把“零值”放在左邊，這樣當(dāng)把“ =”誤寫(xiě)成“ =”時(shí)，編譯器可以報(bào)錯(cuò)，否則這種邏輯錯(cuò)誤不容易發(fā)現(xiàn)，并且可能導(dǎo)致很?chē)?yán)重的后果。 面試題 3： sizeof 和 strlen 的區(qū)別sizeof 和 strlen 有以下區(qū)別：q sizeof 是一個(gè)操作符， strlen 是庫(kù)函數(shù)。q sizeof 的參數(shù)可以是數(shù)據(jù)的類(lèi)型，也可以是變量，而 strlen 只能以結(jié)尾為0的字符串作參數(shù)。q 編譯器在編譯時(shí)

3、就計(jì)算出了 sizeof 的結(jié)果。而 strlen 函數(shù)必須在運(yùn)行時(shí)才能計(jì)算出來(lái)。并且 sizeof計(jì)算的是數(shù)據(jù)類(lèi)型占內(nèi)存的大小，而 strlen 計(jì)算的是字符串實(shí)際的長(zhǎng)度。q 數(shù)組做 sizeof 的參數(shù)不退化，傳遞給 strlen 就退化為指針了。注意：有些是操作符看起來(lái)像是函數(shù)，而有些函數(shù)名看起來(lái)又像操作符，這類(lèi)容易混淆的名稱(chēng)一定要加以區(qū)分，否則遇到數(shù)組名這類(lèi)特殊數(shù)據(jù)類(lèi)型作參數(shù)時(shí)就很容易出錯(cuò)。最容易混淆為函數(shù)的操作符就是 sizeof。面試題 4： C 語(yǔ)言的關(guān)鍵字 static 和 C+ 的關(guān)鍵字 static 有什么區(qū)別在 C 中 static 用來(lái)修飾局部靜態(tài)變量和外部靜態(tài)變量、函

4、數(shù)。而 C+中除了上述功能外，還用來(lái)定義類(lèi)的成員變量和函數(shù)。即靜態(tài)成員和靜態(tài)成員函數(shù)。注意：編程時(shí) static 的記憶性，和全局性的特點(diǎn)可以讓在不同時(shí)期調(diào)用的函數(shù)進(jìn)行通信，傳遞信息，而 C+的靜態(tài)成員則可以在多個(gè)對(duì)象實(shí)例間進(jìn)行通信，傳遞信息。面試題 5： 中的 malloc 和中的 new 有什么區(qū)別malloc 和 new 有以下不同：（ 1） new、 delete 是操作符，可以重載，只能在 C+中使用。（ 2） malloc、 free 是函數(shù)，可以覆蓋， C、 C+中都可以使用。（ 3） new 可以調(diào)用對(duì)象的構(gòu)造函數(shù)，對(duì)應(yīng)的 delete 調(diào)用相應(yīng)的析構(gòu)函數(shù)。（ 4） mallo

5、c 僅僅分配內(nèi)存， free 僅僅回收內(nèi)存，并不執(zhí)行構(gòu)造和析構(gòu)函數(shù)（ 5） new、 delete 返回的是某種數(shù)據(jù)類(lèi)型指針， malloc、 free 返回的是 void 指針。注意： malloc 申請(qǐng)的內(nèi)存空間要用 free 釋放，而 new 申請(qǐng)的內(nèi)存空間要用 delete 釋放，不要混用。因?yàn)閮烧邔?shí)現(xiàn)的機(jī)理不同。 面試題 6： 寫(xiě)一個(gè)“ 標(biāo)準(zhǔn)” 宏 MIN#define min(a,b)(a)=(b)(a):(b)注意：在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用：(+*p)=(x)(+*p):(x)。p 指針就自加了兩次，違背了 MIN 的本意。3 面試題 7： 一個(gè)指針可以是

6、volatile 嗎可以，因?yàn)橹羔樅推胀ㄗ兞恳粯?，有時(shí)也有變化程序的不可控性。常見(jiàn)例：子中斷服務(wù)子程序修改一個(gè)指向一個(gè) buffer 的指針時(shí)，必須用 volatile 來(lái)修飾這個(gè)指針。說(shuō)明：指針是一種普通的變量，從訪問(wèn)上沒(méi)有什么不同于其他變量的特性。其保存的數(shù)值是個(gè)整型數(shù)據(jù)，和整型變量不同的是，這個(gè)整型數(shù)據(jù)指向的是一段內(nèi)存地址。 面試題 8： a 和&a 有什么區(qū)別請(qǐng)寫(xiě)出以下代碼的打印結(jié)果，主要目的是考察 a 和&a 的區(qū)別。#includevoid main( void )int a5=1,2,3,4,5;int *ptr=(int *)(&a+1);printf(%d,%d,*(a+1)

7、,*(ptr-1);return;輸出結(jié)果： 2， 5。注意：數(shù)組名 a 可以作數(shù)組的首地址，而&a 是數(shù)組的指針。思考，將原式的 int *ptr=(int *)(&a+1);改為 int *ptr=(int *)(a+1);時(shí)輸出結(jié)果將是什么呢 面試題 9： 簡(jiǎn)述 C、 C+程序編譯的內(nèi)存分配情況C、 C+中內(nèi)存分配方式可以分為三種：（ 1） 從靜態(tài)存儲(chǔ)區(qū)域分配：內(nèi)存在程序編譯時(shí)就已經(jīng)分配好，這塊內(nèi)存在程序的整個(gè)運(yùn)行期間都存在。 速度快、 不容易出錯(cuò)，因?yàn)橛邢到y(tǒng)會(huì)善后。 例如全局變量， static 變量等。（ 2） 在棧上分配：在執(zhí)行函數(shù)時(shí)，函數(shù)內(nèi)局部變量的存儲(chǔ)單元都在棧上創(chuàng)建，函數(shù)執(zhí)行

8、結(jié)束時(shí)這些存儲(chǔ)單元自動(dòng)被釋放。棧內(nèi)存分配運(yùn)算內(nèi)置于處理器的指令集中，效率很高，但是分配的內(nèi)存容量有限。（ 3） 從堆上分配：即動(dòng)態(tài)內(nèi)存分配。程序在運(yùn)行的時(shí)候用 malloc 或 new 申請(qǐng)任意大小的內(nèi)存，程序員自己負(fù)責(zé)在何時(shí)用 free 或 delete 釋放內(nèi)存。動(dòng)態(tài)內(nèi)存的生存期由程序員決定，使用非常靈活。 如果在堆上分配了空間，就有責(zé)任回收它，否則運(yùn)行的程序會(huì)出現(xiàn)內(nèi)存泄漏， 另外頻繁地分配和釋放不同大小的堆空間將會(huì)產(chǎn)生堆內(nèi)碎塊。一個(gè) C、 C+程序編譯時(shí)內(nèi)存分為 5 大存儲(chǔ)區(qū)：堆區(qū)、棧區(qū)、全局區(qū)、文字常量區(qū)、程序代碼區(qū)。4 面試題 10： 簡(jiǎn)述 strcpy、 sprintf 與 mem

9、cpy 的區(qū)別三者主要有以下不同之處：（ 1） 操作對(duì)象不同， strcpy 的兩個(gè)操作對(duì)象均為字符串， sprintf 的操作源對(duì)象可以是多種數(shù)據(jù)類(lèi)型，目的操作對(duì)象是字符串， memcpy 的兩個(gè)對(duì)象就是兩個(gè)任意可操作的內(nèi)存地址，并不限于何種數(shù)據(jù)類(lèi)型。（ 2） 執(zhí)行效率不同， memcpy 最高， strcpy 次之， sprintf 的效率最低。（ 3） 實(shí)現(xiàn)功能不同， strcpy 主要實(shí)現(xiàn)字符串變量間的拷貝， sprintf 主要實(shí)現(xiàn)其他數(shù)據(jù)類(lèi)型格式到字符串的轉(zhuǎn)化， memcpy 主要是內(nèi)存塊間的拷貝。說(shuō)明： strcpy、 sprintf 與 memcpy 都可以實(shí)現(xiàn)拷貝的功能，但是

10、針對(duì)的對(duì)象不同，根據(jù)實(shí)際需求，來(lái)選擇合適的函數(shù)實(shí)現(xiàn)拷貝功能。 面試題 11： 設(shè)置地址為 0x67a9 的整型變量的值為 0xaa66int *ptr;ptr = (int *)0x67a9;*ptr = 0xaa66;說(shuō)明：這道題就是強(qiáng)制類(lèi)型轉(zhuǎn)換的典型例子，無(wú)論在什么平臺(tái)地址長(zhǎng)度和整型數(shù)據(jù)的長(zhǎng)度是一樣的，即一個(gè)整型數(shù)據(jù)可以強(qiáng)制轉(zhuǎn)換成地址指針類(lèi)型，只要有意義即可。 面試題 12： 面向?qū)ο蟮娜筇卣髅嫦驅(qū)ο蟮娜筇卣魇欠庋b性、繼承性和多態(tài)性：q 封裝性：將客觀事物抽象成類(lèi)，每個(gè)類(lèi)對(duì)自身的數(shù)據(jù)和方法實(shí)行 protection（ private， protected，public）。q 繼承性：廣

11、義的繼承有三種實(shí)現(xiàn)形式： 實(shí)現(xiàn)繼承（ 使用基類(lèi)的屬性和方法而無(wú)需額外編碼的能力)、可視繼承(子窗體使用父窗體的外觀和實(shí)現(xiàn)代碼)、接口繼承(僅使用屬性和方法,實(shí)現(xiàn)滯后到子類(lèi)實(shí)現(xiàn))。q 多態(tài)性：是將父類(lèi)對(duì)象設(shè)置成為和一個(gè)或更多它的子對(duì)象相等的技術(shù)。用子類(lèi)對(duì)象給父類(lèi)對(duì)象賦值之后，父類(lèi)對(duì)象就可以根據(jù)當(dāng)前賦值給它的子對(duì)象的特性以不同的方式運(yùn)作。說(shuō)明：面向?qū)ο蟮娜齻€(gè)特征是實(shí)現(xiàn)面向?qū)ο蠹夹g(shù)的關(guān)鍵，每一個(gè)特征的相關(guān)技術(shù)都非常的復(fù)雜，程序員應(yīng)該多看、多練。 面試題 13： C+的空類(lèi)有哪些成員函數(shù)q 缺省構(gòu)造函數(shù)。q 缺省拷貝構(gòu)造函數(shù)。q 缺省析構(gòu)函數(shù)。q 缺省賦值運(yùn)算符。q 缺省取址運(yùn)算符。q 缺省取址運(yùn)算符

12、 const。注意：有些書(shū)上只是簡(jiǎn)單的介紹了前四個(gè)函數(shù)。沒(méi)有提及后面這兩個(gè)函數(shù)。但后面這兩個(gè)函數(shù)也是空類(lèi)的默認(rèn)函數(shù)。另外需要注意的是，只有當(dāng)實(shí)際使用這些函數(shù)的時(shí)候，編譯器才會(huì)去定義它們。5 面試題 14： 談?wù)勀銓?duì)拷貝構(gòu)造函數(shù)和賦值運(yùn)算符的認(rèn)識(shí)拷貝構(gòu)造函數(shù)和賦值運(yùn)算符重載有以下兩個(gè)不同之處：（ 1）拷貝構(gòu)造函數(shù)生成新的類(lèi)對(duì)象，而賦值運(yùn)算符不能。（ 2）由于拷貝構(gòu)造函數(shù)是直接構(gòu)造一個(gè)新的類(lèi)對(duì)象，所以在初始化這個(gè)對(duì)象之前不用檢驗(yàn)源對(duì)象是否和新建對(duì)象相同。而賦值運(yùn)算符則需要這個(gè)操作，另外賦值運(yùn)算中如果原來(lái)的對(duì)象中有內(nèi)存分配要先把內(nèi)存釋放掉注意：當(dāng)有類(lèi)中有指針類(lèi)型的成員變量時(shí)，一定要重寫(xiě)拷貝構(gòu)造函數(shù)和

13、賦值運(yùn)算符，不要使用默認(rèn)的。 面試題 15： 用 C+設(shè)計(jì)一個(gè)不能被繼承的類(lèi)template class Afriend T;private:A() A() ;class B : virtual public Apublic:B() B() ;class C : virtual public Bpublic:C() C() ;void main( void )B b;/C c;return;注意：構(gòu)造函數(shù)是繼承實(shí)現(xiàn)的關(guān)鍵，每次子類(lèi)對(duì)象構(gòu)造時(shí)，首先調(diào)用的是父類(lèi)的構(gòu)造函數(shù)，然后才是自己的。 面試題 16： 訪問(wèn)基類(lèi)的私有虛函數(shù)寫(xiě)出以下程序的輸出結(jié)果：#include class A 6virtua

14、l void g()cout A:g endl;private:virtual void f()cout A:f endl;class B : public Avoid g()cout B:g endl;virtual void h()cout B:h endl;typedef void( *Fun )( void );void main()B b;Fun pFun;for(int i = 0 ; i next; /記錄上次翻轉(zhuǎn)后的鏈表oldList- next = newHead; /將當(dāng)前結(jié)點(diǎn)插入到翻轉(zhuǎn)后鏈表的開(kāi)頭newHead = oldList; /遞歸處理剩余的鏈表return (

15、next=NULL ) newHead: reverse( t, newHead );說(shuō)明： 循環(huán)算法就是圖 10.2圖 10.5 的移動(dòng)過(guò)程，比較好理解和想到。遞歸算法的設(shè)計(jì)雖有一點(diǎn)難度，但是理解了循環(huán)算法，再設(shè)計(jì)遞歸算法就簡(jiǎn)單多了。面試題 21：簡(jiǎn)述隊(duì)列和棧的異同隊(duì)列和棧都是線性存儲(chǔ)結(jié)構(gòu)，但是兩者的插入和刪除數(shù)據(jù)的操作不同，隊(duì)列是“先進(jìn)先出”，棧是“后進(jìn)先出”。注意：區(qū)別棧區(qū)和堆區(qū)。堆區(qū)的存取是“順序隨意”，而棧區(qū)是“后進(jìn)先出”。棧由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類(lèi)似于數(shù)據(jù)結(jié)構(gòu)中的棧。 堆一般由程序員分配釋放， 若程序員不釋放，程序結(jié)束時(shí)可能由 OS 回

16、收。分配方式類(lèi)似于鏈表。它與本題中的堆和棧是兩回事。堆棧只是一種數(shù)據(jù)結(jié)構(gòu)，而堆區(qū)和棧區(qū)是程序的不同內(nèi)存存儲(chǔ)區(qū)域。面試題 22： 能否用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的功能結(jié)點(diǎn)結(jié)構(gòu)體：typedef struct nodeint data;node *next;node,*LinkStack;創(chuàng)建空棧：LinkStack CreateNULLStack( LinkStack &S)S = (LinkStack)malloc( sizeof( node ) ); /申請(qǐng)新結(jié)點(diǎn)if( NULL = S)printf(Fail to malloc a new node.n);9return NULL; S-dat

17、a = 0; /初始化新結(jié)點(diǎn)S-next = NULL;return S;棧的插入函數(shù)：LinkStack Push( LinkStack &S, int data)if( NULL = S) /檢驗(yàn)棧printf(There no node in stack!);return NULL;LinkStack p = NULL;p = (LinkStack)malloc( sizeof( node ) ); /申請(qǐng)新結(jié)點(diǎn)if( NULL = p)printf(Fail to malloc a new node.n);return S;if( NULL = S-next)p-next = NULL

18、;elsep-next = S-next; p-data = data; /初始化新結(jié)點(diǎn)S-next = p; /插入新結(jié)點(diǎn)return S;出棧函數(shù)：node Pop( LinkStack &S)node temp;temp.data = 0;temp.next = NULL;if( NULL = S) /檢驗(yàn)棧printf(There no node in stack!);return temp;temp = *S;10if( S-next = NULL )printf(The stack is NULL,cant pop!n);return temp;LinkStack p = S -n

19、ext; /節(jié)點(diǎn)出棧S-next = S-next-next;temp = *p;free( p );p = NULL;return temp;雙棧實(shí)現(xiàn)隊(duì)列的入隊(duì)函數(shù)：LinkStack StackToQueuPush( LinkStack &S, int data)node n;LinkStack S1 = NULL;CreateNULLStack( S1 ); /創(chuàng)建空棧while( NULL != S-next ) /S 出棧入 S1n = Pop( S );Push( S1, n.data );Push( S1, data ); /新結(jié)點(diǎn)入棧while( NULL != S1-next

20、 ) /S1 出棧入 Sn = Pop( S1 );Push( S, n.data );return S;說(shuō)明：用兩個(gè)棧能夠?qū)崿F(xiàn)一個(gè)隊(duì)列的功能，那用兩個(gè)隊(duì)列能否實(shí)現(xiàn)一個(gè)隊(duì)列的功能呢結(jié)果是否定的，因?yàn)闂Ｊ窍冗M(jìn)后出，將兩個(gè)棧連在一起，就是先進(jìn)先出。而隊(duì)列是現(xiàn)先進(jìn)先出，無(wú)論多少個(gè)連在一起都是先進(jìn)先出，而無(wú)法實(shí)現(xiàn)先進(jìn)后出。面試題 23： 計(jì)算一顆二叉樹(shù)的深度深度的計(jì)算函數(shù)：int depth(BiTree T)if(!T) return 0; /判斷當(dāng)前結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)11int d1= depth(T-lchild); /求當(dāng)前結(jié)點(diǎn)的左孩子樹(shù)的深度int d2= depth(T-rchild);

21、/求當(dāng)前結(jié)點(diǎn)的右孩子樹(shù)的深度return (d1d2d1:d2)+1;注意：根據(jù)二叉樹(shù)的結(jié)構(gòu)特點(diǎn)，很多算法都可以用遞歸算法來(lái)實(shí)現(xiàn)。 面試題 24： 編碼實(shí)現(xiàn)直接插入排序直接插入排序編程實(shí)現(xiàn)如下：#includevoid main( void )int ARRAY10 = 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 ;int i,j;for( i = 0; i 10; i+)coutARRAYi ;coutendl;for( i = 2; i = 10; i+ ) /將 ARRAY2,ARRAYn依次按序插入if(ARRAYi ARRAYi-1) /如果 ARRAYi大于一切有序的

22、數(shù)值，/ARRAYi將保持原位不動(dòng)ARRAY0 = ARRAYi; /將 ARRAY0看做是哨兵,是 ARRAYi的副本j = i - 1;do /從右向左在有序區(qū) ARRAY1 i-1中/查找 ARRAYi的插入位置ARRAYj+1 = ARRAYj; /將數(shù)值大于 ARRAYi記錄后移j- ;while( ARRAY0 ARRAYj );ARRAYj+1=ARRAY0; /ARRAYi插入到正確的位置上for( i = 0; i 10; i+)coutARRAYi ;coutendl;12注意： 所有為簡(jiǎn)化邊界條件而引入的附加結(jié)點(diǎn)（ 元素） 均可稱(chēng)為哨兵。引入哨兵后使得查找循環(huán)條件的時(shí)間大

23、約減少了一半， 對(duì)于記錄數(shù)較大的文件節(jié)約的時(shí)間就相當(dāng)可觀。類(lèi)似于排序這樣使用頻率非常高的算法，要盡可能地減少其運(yùn)行時(shí)間。所以不能把上述算法中的哨兵視為雕蟲(chóng)小技。 面試題 25： 編碼實(shí)現(xiàn)冒泡排序冒泡排序編程實(shí)現(xiàn)如下：#include #define LEN 10 /數(shù)組長(zhǎng)度void main( void )int ARRAY10 = 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 ; /待排序數(shù)組printf( n );for( int a = 0; a LEN; a+ ) /打印數(shù)組內(nèi)容printf( %d , ARRAYa );int i = 0;int j = 0;bool i

24、sChange; /設(shè)定交換標(biāo)志for( i = 1; i = i; j- ) /對(duì)當(dāng)前無(wú)序區(qū) ARRAYi.LEN自下向上掃描if( ARRAYj+1 ARRAYj ) /交換記錄ARRAY0 = ARRAYj+1; /ARRAY0不是哨兵,僅做暫存單元ARRAYj+1 = ARRAYj;ARRAYj = ARRAY0;isChange = 1; /發(fā)生了交換,故將交換標(biāo)志置為真printf( n );for( a = 0; a LEN; a+) /打印本次排序后數(shù)組內(nèi)容printf( %d , ARRAYa );if( !isChange ) /本趟排序未發(fā)生交換,提前終止算法break;

25、printf( n );return;13 面試題 26： 編碼實(shí)現(xiàn)直接選擇排序#includestdio.h#define LEN 9void main( void )int ARRAYLEN= 5, 6, 8, 2, 4, 1, 9, 3, 7 ; /待序數(shù)組printf(Before sorted:n);for( int m = 0; m LEN; m+ ) /打印排序前數(shù)組printf( %d , ARRAYm );for (int i = 1; i = LEN - 1; i+) /選擇排序int t = i - 1;int temp = 0;for (int j = i; j LEN

26、; j+)if (ARRAYj ARRAYt)t = j;if (t != (i - 1)temp = ARRAYi - 1;ARRAYi - 1 = ARRAYt;ARRAYt = temp;printf( n );printf(After sorted:n);for( i = 0; i LEN; i+ ) /打印排序后數(shù)組printf( %d , ARRAYi );printf( n );注意：在直接選擇排序中，具有相同關(guān)鍵碼的對(duì)象可能會(huì)顛倒次序，因而直接選擇排序算法是一種不穩(wěn)定的排序方法。在本例中只是例舉了簡(jiǎn)單的整形數(shù)組排序，肯定不會(huì)有什么問(wèn)題。但是在復(fù)雜的數(shù)據(jù)元素序列組合中，只是根據(jù)單

27、一的某一個(gè)關(guān)鍵值排序，直接選擇排序則不保證其穩(wěn)定性，這是直接選擇排序的一個(gè)弱點(diǎn)。 面試題 27： 編程實(shí)現(xiàn)堆排序堆排序編程實(shí)現(xiàn)：#include 14void createHeep(int ARRAY,int sPoint, int Len) /生成大根堆while( ( 2 * sPoint + 1 ) Len )int mPoint = 2 * sPoint + 1 ;if( ( 2 * sPoint + 2 ) Len )if(ARRAY 2 * sPoint + 1 ARRAY 2 * sPoint + 2 )mPoint = 2*sPoint+2;if(ARRAY sPoint =

28、0; i- ) /將 Hr0， Lenght-1建成大根堆createHeep(ARRAY, i, Len);for ( i = Len - 1; i 0; i- )int tmpData = ARRAY0; /與最后一個(gè)記錄交換ARRAY0 = ARRAYi;ARRAYi = tmpData;createHeep( ARRAY, 0, i ); /將 H.r0.i重新調(diào)整為大根堆return;int main( void )15int ARRAY = 5, 4, 7, 3, 9, 1, 6, 8, 2;printf(Before sorted:n); /打印排序前數(shù)組內(nèi)容for ( int

29、i = 0; i 9; i+ )printf(%d , ARRAYi);printf(n);heepSort( ARRAY, 9 ); /堆排序printf(After sorted:n); /打印排序后數(shù)組內(nèi)容for( i = 0; i 9; i+ )printf( %d , ARRAYi );printf( n );return 0;說(shuō)明：堆排序，雖然實(shí)現(xiàn)復(fù)雜，但是非常的實(shí)用。另外讀者可是自己設(shè)計(jì)實(shí)現(xiàn)小堆排序的算法。雖然和大堆排序的實(shí)現(xiàn)過(guò)程相似，但是卻可以加深對(duì)堆排序的記憶和理解。 面試題 28： 編程實(shí)現(xiàn)基數(shù)排序#include #include #define LEN 8typedef

30、 struct node /隊(duì)列結(jié)點(diǎn)int data;struct node * next;node,*QueueNode;typedef struct Queue /隊(duì)列QueueNode front;QueueNode rear;Queue,*QueueLink;QueueLink CreateNullQueue( QueueLink &Q) /創(chuàng)建空隊(duì)列Q = NULL;Q = ( QueueLink )malloc( sizeof( Queue ) );if( NULL = Q )printf(Fail to malloc null queue!n);return NULL;16Q-f

31、ront = ( QueueNode )malloc( sizeof( node ) );Q-rear = ( QueueNode )malloc( sizeof( node ) );if( NULL = Q-front | NULL = Q-rear )printf(Fail to malloc a new queues fornt or rear!n);return NULL; Q-rear = NULL;Q-front-next= Q-rear;return Q;int lenData( node data, int len) /計(jì)算隊(duì)列中各結(jié)點(diǎn)的數(shù)據(jù)的最大位數(shù)int m = 0;int

32、 temp = 0;int d;for( int i = 0; i 0)d /= 10;temp +;if( temp m )m = temp;temp = 0;return m;QueueLink Push( QueueLink &Q , node node ) /將數(shù)據(jù)壓入隊(duì)列QueueNode p1,p;p =( QueueNode )malloc( sizeof( node ) );if( NULL = p )printf(Fail to malloc a new node!n);return NULL;p1 = Q-front;while(p1-next != NULL)p1 = p

33、1-next; p-data = node.data;p1-next = p;p-next = Q-rear;17return NULL;node Pop( QueueLink &Q) /數(shù)據(jù)出隊(duì)列node temp;temp.data = 0;temp.next = NULL;QueueNode p;p = Q-front-next;if( p != Q-rear )temp = *p;Q-front-next = p-next;free( p );p = NULL;return temp;int IsEmpty( QueueLink Q)if( Q-front-next = Q-rear

34、)return 0;return 1;int main( void )int i = 0;int Max = 0; /記錄結(jié)點(diǎn)中數(shù)據(jù)的最大位數(shù)int d = 10;int power = 1;int k = 0;node ArrayLEN =450, NULL, 32,NULL, 781,NULL, 57 ,NULL,組 145,NULL, 613,NULL, 401,NULL, 594,NULL;/隊(duì)列結(jié)點(diǎn)數(shù)QueueLink Queue10;for( i = 0; i 10; i+)CreateNullQueue( Queuei); /初始化隊(duì)列數(shù)組for( i = 0; i LEN; i

35、+)printf(%d ,Arrayi.data);printf(n);Max = lenData( Array, LEN ); /計(jì)算數(shù)組中關(guān)鍵字的最大位數(shù)printf(%dn,Max);18for(int j = 0; j Max; j+) /按位排序if(j = 0) power = 1;else power = power *d;for(i = 0; i LEN; i+)k = Arrayi.data /power - (Arrayi.data/(power * d) * d;Push( Queuek, Arrayi );for(int l = 0, k = 0; l d; l+) /

36、排序后出隊(duì)列重入數(shù)組while( IsEmpty( Queuel ) )Arrayk+ = Pop( Queuel );for( int t = 0; t next = NULL;樹(shù)結(jié)點(diǎn)入棧函數(shù)：void push_path(pPath H, pBTree T)pPath p = H-next;pPath q = H;while( NULL != p )20q = p;p = p-next;p = ( pPath )malloc( sizeof( PATH ) ); /申請(qǐng)新結(jié)點(diǎn)p-next = NULL; /初始化新結(jié)點(diǎn)p-tree = T;q-next = p; /新結(jié)點(diǎn)入棧樹(shù)結(jié)點(diǎn)打印函數(shù)

37、：void print_path( pPath L )pPath p = L-next;while( NULL != p ) /打印當(dāng)前棧中所有數(shù)據(jù)printf(%d, , p-tree-data);p = p-next;樹(shù)結(jié)點(diǎn)出棧函數(shù)：void pop_path( pPath H )pPath p = H-next;pPath q = H;if( NULL = p ) /檢驗(yàn)當(dāng)前棧是否為空printf(Stack is null!n);return;p = p-next;while( NULL != p ) /出棧q = q-next;p = p-next;free( q-next ); /

38、釋放出棧結(jié)點(diǎn)空間q-next = NULL;判斷結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)：int IsLeaf(pBTree T)return ( T-lchild = NULL )&( T-rchild=NULL );查找符合條件的路徑：int find_path(pBTree T, int sum, pPath L)21push_path( L, T);record += T-data;if( ( record = sum ) & ( IsLeaf( T ) ) ) /打印符合條件的當(dāng)前路徑print_path( L );printf( n );if( T-lchild != NULL ) /遞歸查找當(dāng)前節(jié)點(diǎn)的

39、左孩子find_path( T-lchild, sum, L);if( T-rchild != NULL ) /遞歸查找當(dāng)前節(jié)點(diǎn)的右孩子find_path( T-rchild, sum, L);record -= T-data;pop_path(L);return 0;注意：數(shù)據(jù)結(jié)構(gòu)一定要活學(xué)活用，例如本題，把所有的結(jié)點(diǎn)都?jí)喝霔?，而不符合條件的結(jié)點(diǎn)彈出棧，很容易實(shí)現(xiàn)了有效路徑的查找。雖然用鏈表也可以實(shí)現(xiàn)，但是用棧更利于理解這個(gè)問(wèn)題，即適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)為更好的算法設(shè)計(jì)提供了有利的條件。 面試題 34： 寫(xiě)一個(gè)“標(biāo)準(zhǔn)” 宏 MIN寫(xiě)一個(gè)“標(biāo)準(zhǔn)”宏 MIN，這個(gè)宏輸入兩個(gè)參數(shù)并且返回較小的一個(gè)?！?答

40、案】#define min(a,b)(a)=(b)(a):(b)注意：在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用：(+*p)和經(jīng)常連續(xù)使用。因此這兩個(gè)操作符的返回值應(yīng)該是一個(gè)仍舊支持這兩個(gè)操作符的流引用。其他的數(shù)據(jù)類(lèi)型都無(wú)法做到這一點(diǎn)。注意：除了在賦值操作符和流操作符之外的其他的一些操作符中， 如+、 -、 *、 /等卻千萬(wàn)不能返回引用。因?yàn)檫@四個(gè)操作符的對(duì)象都是右值，因此，它們必須構(gòu)造一個(gè)對(duì)象作為返回值。 面試題 40： 簡(jiǎn)述指針常量與常量指針區(qū)別指針常量是指定義了一個(gè)指針，這個(gè)指針的值只能在定義時(shí)初始化，其他地方不能改變。常量指針是指定義了一個(gè)指針，這個(gè)指針指向一個(gè)只讀的對(duì)象，不能通過(guò)常量指針來(lái)改變這個(gè)對(duì)象的值。指針常量強(qiáng)調(diào)的是指針的不可改變性，而常量指針強(qiáng)調(diào)的是指針對(duì)其所指對(duì)象的不可改變性。注意：無(wú)論是指針常量還是常量指針，其最大的用途就是作為函數(shù)的形式參數(shù)，保證實(shí)參在被調(diào)用函數(shù)中的不可改變特性。 面試題 41： 數(shù)組