2023年程序員面試精選

程序員經(jīng)典1雙向鏈表的查找節(jié)點(diǎn)。?考點(diǎn)：雙向鏈表的操作

出現(xiàn)頻率：★★★★?解析:

使用ｒight指針遍歷,直至找到數(shù)據(jù)為dａt(yī)a的節(jié)點(diǎn)，假如找到節(jié)點(diǎn)，返回節(jié)點(diǎn)，否則返回ＮULＬ。

1

//查找節(jié)點(diǎn),成功則返回滿足條件的節(jié)點(diǎn)指針，否則返回ＮULL?2

DbNode

*FindＮodｅ(ＤbNoｄe

*head,

int

data)

//參數(shù)１是鏈表的表頭節(jié)點(diǎn)

3

{

/／參數(shù)2是要查找的節(jié)點(diǎn)，其數(shù)據(jù)為data?４

DbＮode

*pｎoｄe

＝

ｈead;?5

6

if

(heaｄ

==

NULＬ)

//鏈表為空時(shí)返回NＵLＬ

7

{

8

rｅturn

NUＬL;

9

}

1０

1１

／＊找到數(shù)據(jù)或者到達(dá)鏈表末尾退出while循環(huán)*／

12

while

(pnode－＞riｇht

!=

NULL

&&

pnode->daｔa

！=

daｔａ）?13

{?14

pnode

=

pnode->rｉght;

/／使用right指針遍歷

15

｝?１6

１７

//沒有找到數(shù)據(jù)為ｄａt(yī)a的節(jié)點(diǎn),返回ＮULL

1８

if

(pnｏdｅ->ｒiｇht

==

ＮULL）?１９

{?2０

retｕｒn

NＵＬＬ；?21

}

22?２3

retｕｒn

pｎode;?2４

}2考點(diǎn):模板的特化的理解

出現(xiàn)頻率：★★★?解析：

模板的特化(tｅｍplate

specｉaｌizａｔioｎ)分為兩類：函數(shù)模板的特化和類模板的特化。?(1)函數(shù)模板的特化:當(dāng)函數(shù)模板需要對(duì)某些類型進(jìn)行特別解決,稱為函數(shù)模板的特化。例如：?1

bool

IsEｑual(T

t1,

T

t2)?２

{?３

retｕrｎ

t1

＝=

t2;?4

}

5?6

int

main()?7

{?8

cｈａr

str1［]

=

＂Heｌlo"；

９

ｃhar

ｓtｒ2[]

=

"Hello";?1０

ｃouｔ

<<

IsEqual(1,

1)

＜＜

endｌ;?１1

coｕt

<<

IｓEｑuaｌ（str1,

str2)

＜<

eｎdl;

/／輸出０?12

ｒetｕrn

0；?1３

}?代碼11行比較字符串是否相等。由于對(duì)于傳入的參數(shù)是cｈａr

*類型的，mａｘ函數(shù)模板只是簡(jiǎn)樸的比較了傳入?yún)?shù)的值,即兩個(gè)指針是否相等,因此這里打印0。顯然,這與我們的初衷不符。因此，mａx函數(shù)模板需要對(duì)ｃｈar

＊類型進(jìn)行特別解決，即特化：?１

ｔemplate

<>

2

bｏｏｌ

IsEqual(cｈａr*

ｔ1,

char*

t2)

//函數(shù)模板特化?３

{?4

rｅtuｒn

strｃmｐ(ｔ1,

t２)

==

０;?５

}?這樣,當(dāng)IsEquａｌ函數(shù)的參數(shù)類型為ｃhar*

時(shí),就會(huì)調(diào)用IsＥquａl特化的版本,而不會(huì)再由函數(shù)模板實(shí)例化。

（2)類模板的特化：與函數(shù)模板類似，當(dāng)類模板內(nèi)需要對(duì)某些類型進(jìn)行特別解決時(shí)，使用類模板的特化。例如:

１

tｅｍplａｔe

2

class

cｏmpare?３

{

4

pubｌｉc:

5

boｏl

ＩｓEｑｕａl(T

t1,

T

t2）?6

｛?７

ｒetｕrn

t1

==

t2;

８

}?9

};

10?11

int

maｉn（)?１2

{?１3

cｈａｒ

str1[]

=

"Helｌo＂;?1４

char

sｔｒ2[]

＝

"Ｈello";?15

comｐａrｅ

ｃ１;?1６

coｍpaｒe

ｃ２；

１７

coｕt

<<

c１.IsEｑual(1,

1）

<<

enｄｌ;

/／比較兩個(gè)int類型的參數(shù)?１8

cout

<<

ｃ2．IsEqual（str1,

str２)

＜<

ｅｎdl;

/／比較兩個(gè)ｃhar

*類型的參數(shù)?19

reｔurn

0;?2０

}這里代碼18行也是調(diào)用模板類compaｒe的IｓＥqｕａl進(jìn)行兩個(gè)字符串比較，顯然這里存在的問題和上面函數(shù)模板中的同樣,我們需要比較兩個(gè)字符串的內(nèi)容,而不是僅僅比較兩個(gè)字符指針。因此，需要使用類模板的特化:?1

templａt(yī)e<>

2

ｃlass

compare

//特化(cｈar*)?3

｛?4

ｐublic:

5

bｏol

ＩsEqｕａｌ(char*

t１,

ｃhａr＊

t2)

6

{?7

ｒｅtｕｒn

ｓtrcmp(ｔ１,

t2)

==

０;

//使用sｔrcmp比較字符串?8

}?9

｝;

注意：進(jìn)行類模板的特化時(shí),需要特化所有的成員變量及成員函數(shù)。3考點(diǎn)：雙向鏈表的操作

出現(xiàn)頻率：★★★★?解析:?與測(cè)長(zhǎng)的方法同樣,使用righｔ指針進(jìn)行遍歷。?1

／/打印整個(gè)鏈表

2

ｖoiｄ

PｒinｔList(DbNｏde

＊head)

//參數(shù)為鏈表的表頭節(jié)點(diǎn)?3

{

4

DbNｏｄe

*ｐnｏde

=

NULL；?5?６

ｉf

(head

==

NULＬ)

//ｈｅaｄ為NULL表達(dá)鏈表空?7

｛

８

retｕrｎ；

9

}?１0

ｐnodｅ=

heａｄ；?11

whｉｌe

(ｐnode

!＝

NUＬL)?１2

{?１3

ｐrintf("%d

"，

ｐｎodｅ－>datａ）;?1４

ｐnode

=

pｎｏde－>righｔ;

//使用right指針遍歷

15

}

１6

priｎtf("");

１7

｝４考點(diǎn)：類模板的實(shí)例化的理解

出現(xiàn)頻率:★★★★

1

teｍｐｌaｔe?2

clａss

Ａrray

{?３

…

４

｝;

5

void

ｆｏo(

)

6

｛?7

Arｒaｙ

arr1；?8

Array

arr4,

arr5;

9

Arraｙ

arr2,

arr３;?１0

Arrａｙ

arr6；

11

…?12

}?Ｈow

ｍany

inｓtancｅs

ｏf

ｔｈe

temｐlaｔe

ｃｌaｓs

Array

will

ｇｅｔ

instantiａt(yī)ed

inside

the

fｕnｃtion

foｏ()?A

３

B

6

C

4

D

１

解析:

模板類(tｅｍplate

claｓs)的實(shí)例個(gè)數(shù)是由類型參數(shù)的種類決定的。代碼7行和9行實(shí)例化的模板類都是Ａrｒａy，代碼8行實(shí)例化的模板類是Aｒray，代碼１0行實(shí)例化的模板類是Arrａy。一共是三個(gè)實(shí)例。?答案：

A５考點(diǎn)：雙向鏈表的操作?出現(xiàn)頻率：★★★★?解析：

為了得到雙向鏈表的長(zhǎng)度,需要使用rｉｇｈt指針進(jìn)行遍歷，直到得到NULL為止。

1

／/獲取鏈表的長(zhǎng)度?2

int

GetLｅngｔｈ(DbNode

*head)

/／參數(shù)為鏈表的表頭節(jié)點(diǎn)

3

｛?４

int

count

＝

1;

５

ＤｂＮode

*pnode

＝

ＮULL；

６?7

iｆ

（head

＝=

ＮUＬL）

//ｈｅad為NULL表達(dá)鏈表空

８

｛?９

ｒetｕrｎ

０;?１0

｝

1１

pｎode

＝

ｈead->right；

1２

whiｌe

(ｐｎｏdｅ

!＝

NULL)?13

{?1４

ｐｎode

=

pnｏde->riｇht;

//使用rｉｇht指針遍歷

15

ｃount＋＋;

１6

}

17

18

rｅｔurｎ

ｃouｎt;?19

｝?更多精彩內(nèi)容，請(qǐng)到“融智技術(shù)學(xué)苑rzcｈｉna”

使用模板有什么缺陷？如何避免？?6考點(diǎn):理解模板編程的缺陷?出現(xiàn)頻率:★★★?解析:?tｅmplatｅs（模板)是節(jié)省時(shí)間和避免代碼反復(fù)的極好方法,我們可以只輸入一個(gè)類模板，就能讓編譯器實(shí)例化所需要的很多個(gè)特定類及函數(shù)。類模板的成員函數(shù)只有被使用時(shí)才會(huì)被實(shí)例化，所以只有在每一個(gè)函數(shù)都在實(shí)際中被使用時(shí),我們才會(huì)得到這些函數(shù)。

的確這是一個(gè)很重要的技術(shù)，但是假如不小心，使用模板也許會(huì)導(dǎo)致代碼膨脹。什么是代碼膨脹?請(qǐng)看下面的例子：?1

tｅmplａt(yī)e

2

clａss

Ａ

3

{

4

publｉc:?5

voiｄ

wｏｒk(）

6

{

7

cout

<<

"ｗｏｒk()

＂

＜<

eｎdl;

8

coｕｔ

<＜

ｎum

<<

endｌ;

9

}?10

};

1１

12

int

ｍaｉn()

１３

{

14

Aｖ1;?１5

Av2;?1６

Ａv3；

17

Ａv４；

１８

v1.worｋ(）;?19

v2.wｏrk()；

20

v3.ｗｏｒk（);?21

v４.worｋ（);

22

returｎ

０;?2３

}

類模板A取得一個(gè)類型參數(shù)Ｔ，并且它尚有一個(gè)類型為int的參數(shù)，一個(gè)非類型參數(shù)（non-tyｐe

ｐaｒameter)，與類型參數(shù)相比，雖然非類型參數(shù)不是很通用，但他們是完全合法的。在本例中,由于num的不同，代碼14到17行的調(diào)用將會(huì)生成了三個(gè)A的實(shí)例,然后在18~２1行又生成了不同的函數(shù)調(diào)用。

雖然這些函數(shù)做了相同的事情(打印一個(gè)“work（）”和ｎum），但他們卻有不同的二進(jìn)制代碼。這就是所說的由于模板導(dǎo)致的代碼膨脹。也就是說，雖然源代碼看上去緊湊而整潔,但是目的代碼卻臃腫而松散，會(huì)嚴(yán)重影響程序的運(yùn)營(yíng)效率。

如何避免由于這種代碼膨脹呢？有一個(gè)原則,就是把C+＋模板中與參數(shù)無關(guān)的代碼分離出來。也就是讓與參數(shù)無關(guān)的代碼只有一份拷貝。對(duì)類模板A可以進(jìn)行如下地修改：

1

ｔemplatｅ?2

class

Base?3

｛?4

public:

5

ｖoid

ｗork(ｉｎt

nuｍ)

6

{

7

couｔ

<<

"worｋ

";?8

coｕt

＜<

num

<<

eｎdｌ；?9

｝

１0

};?11?12

templａt(yī)e?1３

class

Deｒived

:

pｕblic

Baｓe

１4

{?１5

ｐubｌiｃ：

16

ｖｏid

work()?17

{?1８

Baｓe::wｏｒk(num)；

19

}?2０

};?２1

22

inｔ

mａｉn(）

23

{?24

Deｒｉvｅdd１;?2５

Ｄｅrｉvｅdd2;

2６

Deｒiｖeｄd３;

２7?2８

ｄ１.wｏrｋ();?2９

ｄ2.ｗoｒk(）;?30

d３．woｒk（);

３1

reｔｕrn

0;?3２

}

程序中wｏrk的參數(shù)版本是在一個(gè)Ｂase類（基類)中的。與Dｅriｖed類同樣,Base類也是一個(gè)類模板,但是與Derived類不同樣的是，它參數(shù)化的僅僅是類型Ｔ,而沒有num。因此,所有持有一個(gè)給定類型的Derｉved將共享一個(gè)單一的Bａsｅ類。比如代碼24~2６行實(shí)例化的模板類都共享Bａse模板類,從而他們的成員函數(shù)都共享Ｂａsｅ模板類中的work這個(gè)單一的拷貝。

答案：

模板的缺陷：不本地使用模板會(huì)導(dǎo)致代碼膨脹,即二進(jìn)制代碼臃腫而松散，會(huì)嚴(yán)重影響程序的運(yùn)營(yíng)效率。?解決方法：把C++模板中與參數(shù)無關(guān)的代碼分離出來。７如何建立一個(gè)雙向鏈表？

考點(diǎn):雙向鏈表的操作

出現(xiàn)頻率：★★★★

解析:?雙向鏈表的定義如下:?1

tyｐeｄef

struct

DbＮｏｄe

2

{

3

int

datａ;

//節(jié)點(diǎn)數(shù)據(jù)?４

DbＮodｅ

＊lefｔ；

/／前驅(qū)節(jié)點(diǎn)指針?5

DｂNode

*rｉght;

//后繼節(jié)點(diǎn)指針?6

}

ＤbＮode；

（1)建立雙向鏈表:為方便,這里定義了三個(gè)函數(shù)：?q

CｒeateNode()根據(jù)數(shù)據(jù)來創(chuàng)建一個(gè)節(jié)點(diǎn),返回新創(chuàng)建的節(jié)點(diǎn)。?q

CreateList()函數(shù)根據(jù)一個(gè)節(jié)點(diǎn)數(shù)據(jù)創(chuàng)建鏈表的表頭，返回表頭節(jié)點(diǎn)。

q

ＡppendＮｏdｅ

()函數(shù)總在表尾插入新節(jié)點(diǎn)（其內(nèi)部調(diào)用CreaｔｅNｏde()生成節(jié)點(diǎn)），返回表頭節(jié)點(diǎn)。

1

//根據(jù)數(shù)據(jù)創(chuàng)建創(chuàng)建節(jié)點(diǎn)

2

ＤbＮodｅ

*Ｃrｅａt(yī)eNode(int

data）

3

｛?４

DbNodｅ

＊pnode

=

(ＤｂNode

*)malｌoｃ(ｓizｅoｆ(DbNode)）;

５

pnode-＞datａ

=

daｔa;

6

ｐnode->left

=

pnodｅ->ｒighｔ

=

pnode;

//創(chuàng)建新節(jié)點(diǎn)時(shí)?7

／/讓其前驅(qū)和后繼指針都指向自身?８

rｅturn

ｐｎｏde;

９}

10?11

/／創(chuàng)建鏈表?１2

DｂＮode

*ＣreaｔｅＬist(int

head)

／/參數(shù)給出表頭節(jié)點(diǎn)數(shù)據(jù)?13

{

//表頭節(jié)點(diǎn)不作為存放故意義數(shù)據(jù)的節(jié)點(diǎn)

１4

ＤbNoｄe

*ｐnｏdｅ

＝

(DｂＮode

＊）ｍａlloｃ（sizeof(DbＮode)）；

15

pnode->dａt(yī)a

＝

ｈeａd;

16

pnｏde->ｌeft

=

pnｏde－>rｉght

＝

pnode;?１7

１８

ｒeturｎ

pnodｅ;

１9

｝?2０?２１

/／插入新節(jié)點(diǎn),總是在表尾插入;

返回表頭節(jié)點(diǎn)

22

DbNｏde

*ＡｐpendNode（DｂＮoｄe

＊ｈeａｄ,

ｉnt

data)

/／參數(shù)1是鏈表的表頭節(jié)點(diǎn),

２3

{

//參數(shù)2是要插入的節(jié)點(diǎn),其數(shù)據(jù)為data

2４

DbＮode

＊nｏde

=

CreateNode(dａｔａ);

//創(chuàng)建數(shù)據(jù)為data的新節(jié)點(diǎn)

25

DbNodｅ

*p

=

heaｄ,

*ｑ;

２6

2７

ｗｈilｅ(ｐ

！=

NULL)

２8

{

２9

q

=

p;

３０

ｐ

=

p->rｉght;

31

}

32

ｑ->ｒigｈt

=

node;

33

node->lefｔ

=

ｑ;?34?3５

reｔurｎ

hｅａd;

36

}?我們可以使用其中的CrｅateLiｓt()和ＡppｅｎｄＮodｅ()來生成一個(gè)鏈表，下面是一個(gè)數(shù)據(jù)生成從0到9具有10個(gè)節(jié)點(diǎn)的循環(huán)鏈表。

1

ＤｂＮode

＊hｅad

＝

Creａt(yī)eＬist(0）;

／/生成表頭，表頭數(shù)據(jù)為0?2?3

for

（iｎt

ｉ

＝

1;

i

<

10;

ｉ+＋）?4

{

5

heaｄ

＝

ApｐｅｎdNode(ｈeａｄ,

ｉ）;

//添加9個(gè)節(jié)點(diǎn),數(shù)據(jù)為從１到9

6

}

８考點(diǎn):函數(shù)模板與類模板的基本概念和區(qū)別

出現(xiàn)頻率：★★★?解析：

(１）什么是函數(shù)模板和類模板。

函數(shù)模板是一種抽象函數(shù)定義，它代表一類同構(gòu)函數(shù)。通過用戶提供的具體參數(shù),C++編譯器在編譯時(shí)刻可以將函數(shù)模板實(shí)例化，根據(jù)同一個(gè)模板創(chuàng)建出不同的具體函數(shù),這些函數(shù)之間的不同之處重要在于函數(shù)內(nèi)部一些數(shù)據(jù)類型的不同，而由模板創(chuàng)建的函數(shù)的使用方法與一般函數(shù)的使用方法相同。函數(shù)模板的定義格式如下：?1

temｐlatｅＦｕｎｃtion_Definitiｏn

其中,Fｕｎcｔｉｏｎ_Dｅfiｎiｔion為函數(shù)定義；ＴYPE_LIＳT被稱為類型參數(shù)表,是由—系列代表類型的標(biāo)記符組成的，其間用逗號(hào)分隔,這些標(biāo)記符的通常風(fēng)格是由大寫字母組成,AＲG＿ＬISＴ稱為變量表,其中具有由逗號(hào)分隔開的多個(gè)變量說明，相稱于一般函數(shù)定義中的形式參數(shù)。前面例題中的max就是函數(shù)模板的一個(gè)例子,因此這里不再此外舉例。

C+＋提供的類模板是一種更高層次的抽象的類定義，用于使用相同代碼創(chuàng)建不同類模板的定義與函數(shù)模板的定義類似，只是把函數(shù)摸板中的函數(shù)定義部分換作類說明，并對(duì)類的成員函數(shù)進(jìn)行定義即可。在類說明中可以使用出現(xiàn)在TＹPE_LIＳT中的各個(gè)類型標(biāo)記以及出現(xiàn)在ARG_ＬIST中的各變量。?1

ｔｅmｐlate<<棋板參數(shù)表＞>?２

cｌaｓｓ<類模板名>?3

{<類模板定義體＞｝,?例如我們需要定義一個(gè)表達(dá)平面的點(diǎn)（Point）類，這個(gè)類有兩個(gè)成員變量分別表達(dá)橫坐標(biāo)和縱坐標(biāo)，并且這兩個(gè)坐標(biāo)的類型可以是iｎt、ｆｌｏat、dｏｕｂle等等類型。因此也許寫出類似Point_ｉnt_int、Pｏiｎt＿ｆloat＿int、Pｏｉｎt＿fｌoaｔ_fｌｏａｔ等這樣的類。通過類模板,我們只需要寫一個(gè)類。

1

#includｅ?２

usiｎg

ｎaｍeｓｐacｅ

std;?3

４

tｅmplate?5

cｌasｓ

Poｉnｔ_Ｔ

6

{?７

ｐubliｃ:?8

T1

a;

//成員ａ為T１類型?9

Ｔ2

b；

／／成員b為T2類型

１0

Pｏinｔ＿T()

:

a（0),

b(0)

{｝

//默認(rèn)構(gòu)造函數(shù)?1１

Ｐoｉnt＿T(Ｔ１

ta，

T2

tb)

:

a(ta),

ｂ(tb)

{}

//帶參數(shù)的構(gòu)造函數(shù)?12

Poiｎｔ＿T&

operａｔｏr=(Pｏiｎt_T

&ｐｔ)；

／/賦值函數(shù)

13

frieｎd

Ｐoiｎt_T

ｏperator

+(Ｐｏiｎt＿T

&ｐt1,

Point_Ｔ

&pt2)；

/／重載＋?１4

}；

15?16

template

１７

Pｏinｔ_Ｔ&

Ｐoｉｎt_Ｔ::operaｔor=（Poiｎt_T

＆pt)

//賦值函數(shù)

18

{?19

thｉs－>a

=

ｐt．a(chǎn)；

2０

tｈis-＞b

=

pt.ｂ;

2１

ｒetｕrn

*thiｓ;

22

}?２3

24

ｔemｐｌate?２5

Poiｎｔ＿T

operaｔor

+(Point_T

&ｐt１,

Poｉnｔ＿Ｔ

＆pt2)

//重載＋?26

{

27

Poｉnt_T

temp;

28

temp．a(chǎn)

＝

ｐt１．a(chǎn)

+

pｔ2.ａ;

//結(jié)果對(duì)象中的a和b分別為兩個(gè)參數(shù)對(duì)象的各自a和b之和?29

ｔemp．ｂ

=

pt1．b

+

pt２.ｂ;?30

ｒetｕrn

temp;?31

}?3２

3３

tempｌate?３4

ostrｅam&

ｏpｅｒaｔor

<<

(osｔream&

ｏut,

Point_T&

ｐt)

/／重載輸出流操作符

35

{?３6

oｕｔ

＜<

＂（"

<＜

pt．a(chǎn)

<＜

",

";

//輸出(ａ，

b)

3７

ｏuｔ

<＜

ｐt.ｂ

<＜

＂)＂;?3８

ｒeｔｕrｎ

oｕt;

３9

}?40?41

inｔ

main()

42

{?43

Poinｔ_T

intＰt1（1,

2）;

//T1和Ｔ2都是int?４４

Ｐoinｔ_T

inｔＰt2(3，

４);

//T1和T2都是ｉnｔ?45

Ｐoiｎt＿Ｔ

flｏaｔPｔ1（1.１f,

2.2f);

／／T1和Ｔ2都是ｆloat

４6

Ｐｏint_T

floatPt２(３.3f，

4．4f);

／/T１和T２都是ｆloａt(yī)?47

４8

Ｐoｉnt_Ｔ

inｔTotａlＰt;

49

Poinｔ_Ｔ

ｆloａｔTotalPt;?50

51

ｉntTｏtalＰt

=

inｔPt１

+

intPｔ2;

／/類型為Pｏinｔ_T的對(duì)象相加?５2

fｌｏａt(yī)TｏtaｌPt

=

ｆlｏatPt1

+

floatPｔ２;

／／類型為Ｐｏiｎｔ_T的對(duì)象相加

５3

５4

cｏuｔ

<<

intＴotalＰt

<<

endｌ;

//輸出Point＿Ｔ的對(duì)象?５5

cｏut

<＜

flｏａt(yī)TotａlPt

<<

endl;

／/輸出Ｐoint_T的對(duì)象

56?57

return

０;?58

}

Poinｔ_T類就是一個(gè)類模板，它的成員ａ和b分別為T1和Ｔ2類型，這里我們還實(shí)現(xiàn)了它的構(gòu)造函數(shù)、賦值函數(shù)、“＋”運(yùn)算符的重載以及輸出流操作符“<＜”的重載。?使用Point_T類非常方便，我們可以進(jìn)行各種類型的組合。?代碼43、44行，定義了兩個(gè)Poｉｎt_Ｔ類的對(duì)象intPt１和ｉntＰｔ2，表白這兩個(gè)對(duì)象的成員ａ和ｂ都是int類型。?代碼4５、46行,定義了兩個(gè)Point_T類的對(duì)象fｌoatＰt１和ｆlｏatＰt2，表白這兩個(gè)對(duì)象的成員ａ和ｂ都是ｆloａt(yī)類型。

代碼５1行,對(duì)intPｔ1和inｔPt2進(jìn)行對(duì)象加法，結(jié)果保存到inｔToｔalPｔ中，此過程先調(diào)用“+”函數(shù),再調(diào)用了“=”函數(shù)。

代碼５２行，與5１行類似,只是相加的對(duì)象和結(jié)果對(duì)象都是Point＿T類的對(duì)象。

代碼54、55行,輸出對(duì)象iｎtTotａlPt和floａt(yī)TotalPｔ的內(nèi)容。

可以看出，通過使用類模板Pｏｉｎt_T我們可以創(chuàng)建不同的類,大大提高了代碼的可維護(hù)性以及可重用性。

有一些概念需要區(qū)別:函數(shù)模板與模板函數(shù)，類模板和模板類是不同的意思。?函數(shù)模板的重點(diǎn)是模板，它表達(dá)的是一個(gè)模板，用來生產(chǎn)函數(shù)。例如前面例題的ｍaｘ是一個(gè)函數(shù)模板。而模板函數(shù)的重點(diǎn)是函數(shù),它表達(dá)的是由一個(gè)模板生成而來的函數(shù)。例如maｘ,max等都是模板函數(shù)。?類模板和模板類的區(qū)別與上面的類似，類模板用于生產(chǎn)類,例如Point_T就是一個(gè)類模板。而模板類是由一個(gè)模板生成而來的類，例如Ｐoiｎｔ_T和Point_T都是模板類。

(2）函數(shù)模板和類模板有什么區(qū)別。?在面試?yán)}1的程序代碼中,我們?cè)谑褂煤瘮?shù)模板max時(shí)不一定要必須指明T的類型，函數(shù)模板mａx的實(shí)例化是由編譯程序在解決函數(shù)調(diào)用時(shí)自動(dòng)完畢的,當(dāng)調(diào)用mａx(1，

２)時(shí)自動(dòng)生成實(shí)例mａｘ，而調(diào)用mａx(１.1f，

２.2f)時(shí)自動(dòng)生成實(shí)例max。當(dāng)然也可以顯示指定Ｔ的類型。

對(duì)于本例題的類模板Ｐｏinｔ_T來說,其實(shí)例化必須被顯示地指定,比如Poｉnt_T、Point_Ｔ。

答案:

函數(shù)模板是一種抽象函數(shù)定義，它代表一類同構(gòu)函數(shù)。類模板是一種更高層次的抽象的類定義。?函數(shù)模板的實(shí)例化是由編譯程序在解決函數(shù)調(diào)用時(shí)自動(dòng)完畢的,而類模板的實(shí)例化必須由程序員在程序中顯式地指定。9約瑟夫問題的解答?考點(diǎn)：循環(huán)鏈表的操作?出現(xiàn)頻率：★★★★?編號(hào)為1,２，.．．.,Ｎ的N個(gè)人按順時(shí)針方向圍坐一圈,每人持有一個(gè)密碼(正整數(shù))，一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值M,從第一個(gè)人開始按順時(shí)針方向自１開始順序報(bào)數(shù),報(bào)到M時(shí)停止報(bào)數(shù)。報(bào)M的人出列，將他的密碼作為新的Ｍ值，從他在順時(shí)針方向上的下一個(gè)人開始重新從１報(bào)數(shù),如此下去,直至所有人所有出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。?解析：

顯然當(dāng)有人退出圓圈后，報(bào)數(shù)的工作要從下一個(gè)人開始繼續(xù)，而剩下的人仍然是圍成一個(gè)圓圈的，因此可以使用循環(huán)單鏈表,由于退出圓圈的工作相應(yīng)著表中結(jié)點(diǎn)的刪除操作,對(duì)于這種刪除操作頻繁的情況,選用效率較高的鏈表結(jié)構(gòu),為了程序指針每一次都指向一個(gè)具體的代表一個(gè)人的結(jié)點(diǎn)而不需要判斷，鏈表不帶頭結(jié)點(diǎn)。所以，對(duì)于所有人圍成的圓圈所相應(yīng)的數(shù)據(jù)結(jié)構(gòu)采用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來描述。設(shè)頭指針為p，并根據(jù)具體情況移動(dòng)。

為了記錄退出的人的先后順序,采用一個(gè)順序表進(jìn)行存儲(chǔ)。程序結(jié)束后再輸出依次退出的人的編號(hào)順序。由于只記錄各個(gè)結(jié)點(diǎn)的data值就可以,所以定義一個(gè)整型一維數(shù)組。如:ｉnt

quiｔ［n]；ｎ為一個(gè)根據(jù)實(shí)際問題定義的一個(gè)足夠大的整數(shù)。

程序代碼如下：

1

#ｉｎclｕde

2

using

ｎamespaｃｅ

std；

3?4

/＊

結(jié)構(gòu)體和函數(shù)聲明

*／?５

typｅｄｅf

ｓtrｕｃt

node?6

{?7

int

data;

８

nodｅ

＊nｅxt；?9

}

node;?10?11

noｄe

*ｎode_ｃreaｔe（int

ｎ);?12

1３

//構(gòu)造節(jié)點(diǎn)數(shù)量為

n

的單向循環(huán)鏈表?14

ｎode

*

node_creatｅ（iｎt

n)?15

｛

1６

node

＊pRet

=

NULＬ;

1７?18

if

(0

!=

n）?19

{

20

int

ｎ_idx

＝

１;?２１

noｄｅ

＊p＿node

=

NULL;

２2

２3

/*

構(gòu)造

ｎ

個(gè)

node

＊/?24

p_node

=

neｗ

ｎodｅ［n];?25

if

（NULL

=＝

p＿node）

//申請(qǐng)內(nèi)存失敗,返回NULL

２6

｛

２7

rｅｔｕｒn

NＵＬL;?２8

}

29

elｓe?30

{

31

ｍemset(p_nｏde，

0,

ｎ

*

sizeoｆ(nｏde));

//初始化內(nèi)存?32

}?３3

pReｔ

=

p_node;?34

while

(n＿idx

＜

ｎ)

／/構(gòu)造循環(huán)鏈表

35

｛

/／初始化鏈表的每個(gè)節(jié)點(diǎn),從1到n?３6

p_ｎode->data

＝

n_ｉdx;

37

p_nｏdｅ->ｎｅxｔ

＝

p_ｎodｅ

＋

１;?３8

p_ｎode

＝

p＿node->ｎext；

39

n_idx++;?4０

｝

41

p_ｎoｄe-＞daｔａ

=

ｎ;?42

ｐ_ｎode－>next

=

pRet;

4３

｝

44

45

return

pReｔ;

46

}?４7?４8

ｉｎt

mａin(）?４9

{

50

node

*ｐLiｓt

=

NULL;?51

node

*pIｔer

＝

NULＬ;;?52

ｉｎｔ

n

=

20;?53

int

m

=

6;?54

5５

/*

構(gòu)造單向循環(huán)鏈表

*/?５6

pList

＝

node＿cｒeaｔe(n);?57?５8

/*

Josephuｓ

循環(huán)取數(shù)

*/?59

pIｔer

=

ｐList；?６0

ｍ

%=

n；

61

while

（pＩteｒ

!=

pIter－>ｎext)

62

{

63

int

ｉ

=

1;

64?65

/*

取到第

m-1

個(gè)節(jié)點(diǎn)

*/

66

foｒ

(;

ｉ

＜

m

-

1；

i＋+)?67

{?68

pＩｔeｒ

＝

pIｔｅｒ->ｎeｘｔ;

6９

}

7０

71

/＊

輸出第

m

個(gè)節(jié)點(diǎn)的值

*/?７2

ｐｒintf("%d

",

ｐIter－>neｘt->datａ);?73?74

/＊

從鏈表中刪除第

ｍ

個(gè)節(jié)點(diǎn)

*／

75

pIter->neｘt

=

ｐIter->ｎext->next;?７6

pＩｔｅr

=

pIter-＞neｘt;

７7

}?78

prｉnｔf（＂%d＂,

ｐIｔｅｒ－>dａt(yī)a);?79

80

/*

釋放申請(qǐng)的空間

*/?8１

deletｅ

[]pLiｓt;

82

retuｒn

0;?８3

}10舉例說明什么是泛型編程?考點(diǎn):泛型編程的基本概念?出現(xiàn)頻率:★★★

解析：?泛型編程指編寫完全一般化并可反復(fù)使用的算法，其效率與針對(duì)某特定數(shù)據(jù)類型而設(shè)計(jì)的算法相同。所謂泛型,是指具有在多種數(shù)據(jù)類型上皆可操作的含意,在C＋+中事實(shí)上就是使用模板實(shí)現(xiàn)。?舉一個(gè)簡(jiǎn)樸的例子,比如我們要比較兩個(gè)數(shù)的大小,這兩個(gè)數(shù)的類型也許是inｔ，也也許是flｏat，尚有也許是dｏuｂle。一般編程時(shí)我們也許這樣寫函數(shù)(不考慮使用宏的情況）:

1

int

ｍax(iｎｔ

a，

int

b）

／/參數(shù)和返回值都是int類型?2

{?3

reｔurn

a

>

b?

ａ:

b;?4

}

5

6

ｆloat

ｍax（flｏat

ａ,

float

ｂ)

／/參數(shù)和返回值都是float類型

7

{?８

ｒetｕrn

a

>

b?

a:

b；?９

}?１0

11

double

ｍax(doublｅ

ａ，

ｄoｕｂle

b)

//參數(shù)和返回值都是ｄｏublｅ類型?12

{

1３

retuｒn

a

>

b?

a:

ｂ;?14

}?可以看到，上面寫了3個(gè)重載函數(shù)，他們的區(qū)別僅僅只是類型(參數(shù)及返回值）不同，而函數(shù)體完全同樣。

而假如使用模板,我們可以這樣寫:?1

ｔempｌaｔe

//clａsｓ也可用tyｐename替換?2

T

ｍａｘ（T

a,

T

ｂ)

//參數(shù)和返回值都是T類型

3

{?4

return

a

>

b?

a：

ｂ;?5

}?這里的cｌａsｓ不代表對(duì)象的類，而是類型（可用tｙpenａme替換）。這樣maｘ函數(shù)的各個(gè)參數(shù)以及返回值類型都為T，對(duì)于任意類型的兩個(gè)數(shù),我們都可以調(diào)用maｘ求大小，測(cè)試代碼如下:?1

int

main()?２

{?3

coｕt

＜<

max(1,

２)

<<

eｎdl;

/／隱式調(diào)用int類型的ｍax

4

coｕｔ

<<

max(1.1f,

2.2f）

<＜

endl;

//隱式調(diào)用float類型的ｍax?5

ｃouｔ

<<

maｘ(1.1１l,

2.22l)

＜<

endl;

//隱式調(diào)用dｏuble類型的mａx?6

cｏut

<<

mａx('A＇，

'C')

<<

endl;

//隱式調(diào)用ｃhaｒ類型的ｍax?7

cout

＜＜

mａx(1,

２.０)

<<

enｄl;

//必須指定inｔ類型?8?9

return

０;?１0

}?程序執(zhí)行結(jié)果如下:?１

2?2

2.２?3

2.２2

４

Ｃ

5

2?上面的程序中對(duì)于ｉnt、float、ｄoubｌe、以及cｈar類型的都進(jìn)行了測(cè)試。這里需要注意的是第7行的測(cè)試中顯示的指定了類型為int，這是由于參數(shù)１為inｔ類型,參數(shù)2.0為doubｌe類型,此時(shí)假如不指定是使用什么類型，會(huì)產(chǎn)生編譯的模糊性，即編譯器不知道是需要調(diào)用ｉｎt版本的ｍax還是調(diào)用double版本的max函數(shù)。

此外,Ｔ作為max函數(shù)的各參數(shù)以及返回值類型,它幾乎可以是任意類型，即除了基本類型（int、flｏaｔ、char等)，還可以是類，當(dāng)然這個(gè)類需要重載“>”操作符（由于maｘ函數(shù)體使用了這個(gè)操作符）。?顯然，使用泛型編程（模板）可以極大地增長(zhǎng)了代碼的重用性。11考點(diǎn):單鏈表的操作

出現(xiàn)頻率:★★★★

已知兩個(gè)鏈表hｅad1

和hｅad２

各自有序，請(qǐng)把它們合并成一個(gè)鏈表仍然有序。使用非遞歸方法以及遞歸方法。?解析：?一方面介紹非遞歸方法。由于兩個(gè)鏈表head1

和hｅａd2都是有序的,所以我們只需要找把較短鏈表的各個(gè)元素有序的插入到較長(zhǎng)的鏈表之中就可以了。?源代碼如下：

１

ｎode＊

insert_node(node

＊head，

noｄe

*ｉtｅm)

／/head

!=

NULL

2

｛?3

ｎode

＊p

＝

ｈeaｄ；

４

noｄe

＊q

=

NULL;

//始終指向p之前的節(jié)點(diǎn)

5

6

wｈile(p->ｄatａ

＜

ｉteｍ->ｄata

＆&

p

!＝

NULL)?7

{?8

ｑ

＝

p;?9

p

＝

p-＞nｅxt;?１０

}?１1

if

(ｐ

＝=

hｅａd)

//插入到原頭節(jié)點(diǎn)之前?12

{?13

item->next

＝

ｐ；

１4

ｒｅturｎ

item；

15

}

16

/／插入到ｑ與p之間之間?17

ｑ->nｅｘt

=

iｔem;?1８

itｅm->next

=

ｐ;

19

return

heａd;

2０

｝?21?22

/＊

兩個(gè)有序鏈表進(jìn)行合并

*／?23

node＊

ｍerge(nodｅ*

head１,

ｎoｄe＊

heaｄ2)?24

｛?25

ｎode*

hｅad;

/／合并后的頭指針

26

node

*p；?27

ｎodｅ

*nextＰ;

//指向ｐ之后

28?29

if

（

hｅａd1

==

ＮULL

)

／/有一個(gè)鏈表為空的情況，直接返回另一個(gè)鏈表?30

{

31

rｅtｕrｎ

h