2023年程序员面试精选

程序员经典1双向链表的查找节点。ﻫ考点：双向链表的操作

出现频率：★★★★ﻫ解析:

使用ｒight指针遍历,直至找到数据为dａta的节点，假如找到节点，返回节点，否则返回ＮULＬ。

1

//查找节点,成功则返回满足条件的节点指针，否则返回ＮULLﻫ2

DbNode

*FindＮodｅ(ＤbNoｄe

*head,

int

data)

//参数１是链表的表头节点

3

{

/／参数2是要查找的节点，其数据为dataﻫ４

DbＮode

*pｎoｄe

＝

ｈead;ﻫ5

6

if

(heaｄ

==

NULＬ)

//链表为空时返回NＵLＬ

7

{

8

rｅturn

NUＬL;

9

}

1０

1１

／＊找到数据或者到达链表末尾退出while循环*／

12

while

(pnode－＞riｇht

!=

NULL

&&

pnode->daｔa

！=

daｔａ）ﻫ13

{ﻫ14

pnode

=

pnode->rｉght;

/／使用right指针遍历

15

｝ﻫ１6

１７

//没有找到数据为ｄａta的节点,返回ＮULL

1８

if

(pnｏdｅ->ｒiｇht

==

ＮULL）ﻫ１９

{ﻫ2０

retｕｒn

NＵＬＬ；ﻫ21

}

22ﻫ２3

retｕｒn

pｎode;ﻫ2４

}2考点:模板的特化的理解

出现频率：★★★ﻫ解析：

模板的特化(tｅｍplate

specｉaｌizａｔioｎ)分为两类：函数模板的特化和类模板的特化。ﻫ(1)函数模板的特化:当函数模板需要对某些类型进行特别解决,称为函数模板的特化。例如：ﻫ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行比较字符串是否相等。由于对于传入的参数是cｈａr

*类型的，mａｘ函数模板只是简朴的比较了传入参数的值,即两个指针是否相等,因此这里打印0。显然,这与我们的初衷不符。因此，mａx函数模板需要对ｃｈar

＊类型进行特别解决，即特化：ﻫ１

ｔemplate

<>

2

bｏｏｌ

IsEqual(cｈａr*

ｔ1,

char*

t2)

//函数模板特化ﻫ３

{ﻫ4

rｅtuｒn

strｃmｐ(ｔ1,

t２)

==

０;ﻫ５

}ﻫ这样,当IsEquａｌ函数的参数类型为ｃhar*

时,就会调用IsＥquａl特化的版本,而不会再由函数模板实例化。

（2)类模板的特化：与函数模板类似，当类模板内需要对某些类型进行特别解决时，使用类模板的特化。例如:

１

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ｄｌ;

/／比较两个int类型的参数ﻫ１8

cout

<<

ｃ2．IsEqual（str1,

str２)

＜<

ｅｎdl;

/／比较两个ｃhar

*类型的参数ﻫ19

reｔurn

0;ﻫ2０

}这里代码18行也是调用模板类compaｒe的IｓＥqｕａl进行两个字符串比较，显然这里存在的问题和上面函数模板中的同样,我们需要比较两个字符串的内容,而不是仅仅比较两个字符指针。因此，需要使用类模板的特化:ﻫ1

templａte<>

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

｝;

注意：进行类模板的特化时,需要特化所有的成员变量及成员函数。3考点：双向链表的操作

出现频率：★★★★ﻫ解析:ﻫ与测长的方法同样,使用righｔ指针进行遍历。ﻫ1

／/打印整个链表

2

ｖoiｄ

PｒinｔList(DbNｏde

＊head)

//参数为链表的表头节点ﻫ3

{

4

DbNｏｄe

*ｐnｏde

=

NULL；ﻫ5ﻫ６

ｉf

(head

==

NULＬ)

//ｈｅaｄ为NULL表达链表空ﻫ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

｝４考点：类模板的实例化的理解

出现频率:★★★★

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ａted

inside

the

fｕnｃtion

foｏ()ﻫA

３

B

6

C

4

D

１

解析:

模板类(tｅｍplate

claｓs)的实例个数是由类型参数的种类决定的。代码7行和9行实例化的模板类都是Ａrｒａy，代码8行实例化的模板类是Aｒray，代码１0行实例化的模板类是Arrａy。一共是三个实例。ﻫ答案：

A５考点：双向链表的操作ﻫ出现频率：★★★★ﻫ解析：

为了得到双向链表的长度,需要使用rｉｇｈt指针进行遍历，直到得到NULL为止。

1

／/获取链表的长度ﻫ2

int

GetLｅngｔｈ(DbNode

*head)

/／参数为链表的表头节点

3

｛ﻫ４

int

count

＝

1;

５

ＤｂＮode

*pnode

＝

ＮULL；

６ﻫ7

iｆ

（head

＝=

ＮUＬL）

//ｈｅad为NULL表达链表空

８

｛ﻫ９

ｒ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

｝ﻫ更多精彩内容，请到“融智技术学苑rzcｈｉna”

使用模板有什么缺陷？如何避免？ﻫ6考点:理解模板编程的缺陷ﻫ出现频率:★★★ﻫ解析:ﻫtｅmplatｅs（模板)是节省时间和避免代码反复的极好方法,我们可以只输入一个类模板，就能让编译器实例化所需要的很多个特定类及函数。类模板的成员函数只有被使用时才会被实例化，所以只有在每一个函数都在实际中被使用时,我们才会得到这些函数。

的确这是一个很重要的技术，但是假如不小心，使用模板也许会导致代码膨胀。什么是代码膨胀?请看下面的例子：ﻫ1

tｅmplａte

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取得一个类型参数Ｔ，并且它尚有一个类型为int的参数，一个非类型参数（non-tyｐe

ｐaｒameter)，与类型参数相比，虽然非类型参数不是很通用，但他们是完全合法的。在本例中,由于num的不同，代码14到17行的调用将会生成了三个A的实例,然后在18~２1行又生成了不同的函数调用。

虽然这些函数做了相同的事情(打印一个“work（）”和ｎum），但他们却有不同的二进制代码。这就是所说的由于模板导致的代码膨胀。也就是说，虽然源代码看上去紧凑而整洁,但是目的代码却臃肿而松散，会严重影响程序的运营效率。

如何避免由于这种代码膨胀呢？有一个原则,就是把C+＋模板中与参数无关的代码分离出来。也就是让与参数无关的代码只有一份拷贝。对类模板A可以进行如下地修改：

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ａteﻫ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的参数版本是在一个Ｂase类（基类)中的。与Dｅriｖed类同样,Base类也是一个类模板,但是与Derived类不同样的是，它参数化的仅仅是类型Ｔ,而没有num。因此,所有持有一个给定类型的Derｉved将共享一个单一的Bａsｅ类。比如代码24~2６行实例化的模板类都共享Bａse模板类,从而他们的成员函数都共享Ｂａsｅ模板类中的work这个单一的拷贝。

答案：

模板的缺陷：不本地使用模板会导致代码膨胀,即二进制代码臃肿而松散，会严重影响程序的运营效率。ﻫ解决方法：把C++模板中与参数无关的代码分离出来。７如何建立一个双向链表？

考点:双向链表的操作

出现频率：★★★★

解析:ﻫ双向链表的定义如下:ﻫ1

tyｐeｄef

struct

DbＮｏｄe

2

{

3

int

datａ;

//节点数据ﻫ４

DbＮodｅ

＊lefｔ；

/／前驱节点指针ﻫ5

DｂNode

*rｉght;

//后继节点指针ﻫ6

}

ＤbＮode；

（1)建立双向链表:为方便,这里定义了三个函数：ﻫq

CｒeateNode()根据数据来创建一个节点,返回新创建的节点。ﻫq

CreateList()函数根据一个节点数据创建链表的表头，返回表头节点。

q

ＡppendＮｏdｅ

()函数总在表尾插入新节点（其内部调用CreaｔｅNｏde()生成节点），返回表头节点。

1

//根据数据创建创建节点

2

ＤbＮodｅ

*ＣrｅａteNode(int

data）

3

｛ﻫ４

DbNodｅ

＊pnode

=

(ＤｂNode

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

５

pnode-＞datａ

=

daｔa;

6

ｐnode->left

=

pnodｅ->ｒighｔ

=

pnode;

//创建新节点时ﻫ7

／/让其前驱和后继指针都指向自身ﻫ８

rｅturn

ｐｎｏde;

９}

10ﻫ11

/／创建链表ﻫ１2

DｂＮode

*ＣreaｔｅＬist(int

head)

／/参数给出表头节点数据ﻫ13

{

//表头节点不作为存放故意义数据的节点

１4

ＤbNoｄe

*ｐnｏdｅ

＝

(DｂＮode

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

15

pnode->dａta

＝

ｈeａd;

16

pnｏde->ｌeft

=

pnｏde－>rｉght

＝

pnode;ﻫ１7

１８

ｒeturｎ

pnodｅ;

１9

｝ﻫ2０ﻫ２１

/／插入新节点,总是在表尾插入;

返回表头节点

22

DbNｏde

*ＡｐpendNode（DｂＮoｄe

＊ｈeａｄ,

ｉnt

data)

/／参数1是链表的表头节点,

２3

{

//参数2是要插入的节点,其数据为data

2４

DbＮode

＊nｏde

=

CreateNode(dａｔａ);

//创建数据为data的新节点

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ｅ()来生成一个链表，下面是一个数据生成从0到9具有10个节点的循环链表。

1

ＤｂＮode

＊hｅad

＝

CreａteＬist(0）;

／/生成表头，表头数据为0ﻫ2ﻫ3

for

（iｎt

ｉ

＝

1;

i

<

10;

ｉ+＋）ﻫ4

{

5

heaｄ

＝

ApｐｅｎdNode(ｈeａｄ,

ｉ）;

//添加9个节点,数据为从１到9

6

}

８考点:函数模板与类模板的基本概念和区别

出现频率：★★★ﻫ解析：

(１）什么是函数模板和类模板。

函数模板是一种抽象函数定义，它代表一类同构函数。通过用户提供的具体参数,C++编译器在编译时刻可以将函数模板实例化，根据同一个模板创建出不同的具体函数,这些函数之间的不同之处重要在于函数内部一些数据类型的不同，而由模板创建的函数的使用方法与一般函数的使用方法相同。函数模板的定义格式如下：ﻫ1

temｐlatｅＦｕｎｃtion_Definitiｏn

其中,Fｕｎcｔｉｏｎ_Dｅfiｎiｔion为函数定义；ＴYPE_LIＳT被称为类型参数表,是由—系列代表类型的标记符组成的，其间用逗号分隔,这些标记符的通常风格是由大写字母组成,AＲG＿ＬISＴ称为变量表,其中具有由逗号分隔开的多个变量说明，相称于一般函数定义中的形式参数。前面例题中的max就是函数模板的一个例子,因此这里不再此外举例。

C+＋提供的类模板是一种更高层次的抽象的类定义，用于使用相同代码创建不同类模板的定义与函数模板的定义类似，只是把函数摸板中的函数定义部分换作类说明，并对类的成员函数进行定义即可。在类说明中可以使用出现在TＹPE_LIＳT中的各个类型标记以及出现在ARG_ＬIST中的各变量。ﻫ1

ｔｅmｐlate<<棋板参数表＞>ﻫ２

cｌaｓｓ<类模板名>ﻫ3

{<类模板定义体＞｝,ﻫ例如我们需要定义一个表达平面的点（Point）类，这个类有两个成员变量分别表达横坐标和纵坐标，并且这两个坐标的类型可以是iｎt、ｆｌｏat、dｏｕｂle等等类型。因此也许写出类似Point_ｉnt_int、Pｏiｎt＿ｆloat＿int、Pｏｉｎt＿fｌoaｔ_fｌｏａｔ等这样的类。通过类模板,我们只需要写一个类。

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)

{｝

//默认构造函数ﻫ1１

Ｐoｉnt＿T(Ｔ１

ta，

T2

tb)

:

a(ta),

ｂ(tb)

{}

//带参数的构造函数ﻫ12

Poiｎｔ＿T&

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

&ｐｔ)；

／/赋值函数

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)

//赋值函数

18

{ﻫ19

thｉs－>a

=

ｐt．a；

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

＝

ｐt１．a

+

pｔ2.ａ;

//结果对象中的a和b分别为两个参数对象的各自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

<＜

",

";

//输出(ａ，

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ﻫ47

４8

Ｐoｉnt_Ｔ

inｔTotａlＰt;

49

Poinｔ_Ｔ

ｆloａｔTotalPt;ﻫ50

51

ｉntTｏtalＰt

=

inｔPt１

+

intPｔ2;

／/类型为Pｏinｔ_T的对象相加ﻫ５2

fｌｏａtTｏtaｌPt

=

ｆlｏatPt1

+

floatPｔ２;

／／类型为Ｐｏiｎｔ_T的对象相加

５3

５4

cｏuｔ

<<

intＴotalＰt

<<

endｌ;

//输出Point＿Ｔ的对象ﻫ５5

cｏut

<＜

flｏａtTotａlPt

<<

endl;

／/输出Ｐoint_T的对象

56ﻫ57

return

０;ﻫ58

}

Poinｔ_T类就是一个类模板，它的成员ａ和b分别为T1和Ｔ2类型，这里我们还实现了它的构造函数、赋值函数、“＋”运算符的重载以及输出流操作符“<＜”的重载。ﻫ使用Point_T类非常方便，我们可以进行各种类型的组合。ﻫ代码43、44行，定义了两个Poｉｎt_Ｔ类的对象intPt１和ｉntＰｔ2，表白这两个对象的成员ａ和ｂ都是int类型。ﻫ代码4５、46行,定义了两个Point_T类的对象fｌoatＰt１和ｆlｏatＰt2，表白这两个对象的成员ａ和ｂ都是ｆloａt类型。

代码５1行,对intPｔ1和inｔPt2进行对象加法，结果保存到inｔToｔalPｔ中，此过程先调用“+”函数,再调用了“=”函数。

代码５２行，与5１行类似,只是相加的对象和结果对象都是Point＿T类的对象。

代码54、55行,输出对象iｎtTotａlPt和floａtTotalPｔ的内容。

可以看出，通过使用类模板Pｏｉｎt_T我们可以创建不同的类,大大提高了代码的可维护性以及可重用性。

有一些概念需要区别:函数模板与模板函数，类模板和模板类是不同的意思。ﻫ函数模板的重点是模板，它表达的是一个模板，用来生产函数。例如前面例题的ｍaｘ是一个函数模板。而模板函数的重点是函数,它表达的是由一个模板生成而来的函数。例如maｘ,max等都是模板函数。ﻫ类模板和模板类的区别与上面的类似，类模板用于生产类,例如Point_T就是一个类模板。而模板类是由一个模板生成而来的类，例如Ｐoiｎｔ_T和Point_T都是模板类。

(2）函数模板和类模板有什么区别。ﻫ在面试例题1的程序代码中,我们在使用函数模板max时不一定要必须指明T的类型，函数模板mａx的实例化是由编译程序在解决函数调用时自动完毕的,当调用mａx(1，

２)时自动生成实例mａｘ，而调用mａx(１.1f，

２.2f)时自动生成实例max。当然也可以显示指定Ｔ的类型。

对于本例题的类模板Ｐｏinｔ_T来说,其实例化必须被显示地指定,比如Poｉnt_T、Point_Ｔ。

答案:

函数模板是一种抽象函数定义，它代表一类同构函数。类模板是一种更高层次的抽象的类定义。ﻫ函数模板的实例化是由编译程序在解决函数调用时自动完毕的,而类模板的实例化必须由程序员在程序中显式地指定。9约瑟夫问题的解答ﻫ考点：循环链表的操作ﻫ出现频率：★★★★ﻫ编号为1,２，.．．.,Ｎ的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值M,从第一个人开始按顺时针方向自１开始顺序报数,报到M时停止报数。报M的人出列，将他的密码作为新的Ｍ值，从他在顺时针方向上的下一个人开始重新从１报数,如此下去,直至所有人所有出列为止。试设计一个程序求出出列顺序。ﻫ解析：

显然当有人退出圆圈后，报数的工作要从下一个人开始继续，而剩下的人仍然是围成一个圆圈的，因此可以使用循环单链表,由于退出圆圈的工作相应着表中结点的删除操作,对于这种删除操作频繁的情况,选用效率较高的链表结构,为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所相应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。

为了记录退出的人的先后顺序,采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的data值就可以,所以定义一个整型一维数组。如:ｉnt

quiｔ［n]；ｎ为一个根据实际问题定义的一个足够大的整数。

程序代码如下：

1

#ｉｎclｕde

2

using

ｎamespaｃｅ

std；

3ﻫ4

/＊

结构体和函数声明

*／ﻫ５

typｅｄｅf

ｓtrｕｃt

nodeﻫ6

{ﻫ7

int

data;

８

nodｅ

＊nｅxt；ﻫ9

}

node;ﻫ10ﻫ11

noｄe

*ｎode_ｃreaｔe（int

ｎ);ﻫ12

1３

//构造节点数量为

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

/*

构造

ｎ

个

node

＊/ﻫ24

p_node

=

neｗ

ｎodｅ［n];ﻫ25

if

（NULL

=＝

p＿node）

//申请内存失败,返回NULL

２6

｛

２7

rｅｔｕｒn

NＵＬL;ﻫ２8

}

29

elｓeﻫ30

{

31

ｍemset(p_nｏde，

0,

ｎ

*

sizeoｆ(nｏde));

//初始化内存ﻫ32

}ﻫ３3

pReｔ

=

p_node;ﻫ34

while

(n＿idx

＜

ｎ)

／/构造循环链表

35

｛

/／初始化链表的每个节点,从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５

/*

构造单向循环链表

*/ﻫ５6

pList

＝

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

/*

Josephuｓ

循环取数

*/ﻫ59

pIｔer

=

ｐList；ﻫ６0

ｍ

%=

n；

61

while

（pＩteｒ

!=

pIter－>ｎext)

62

{

63

int

ｉ

=

1;

64ﻫ65

/*

取到第

m-1

个节点

*/

66

foｒ

(;

ｉ

＜

m

-

1；

i＋+)ﻫ67

{ﻫ68

pＩｔeｒ

＝

pIｔｅｒ->ｎeｘｔ;

6９

}

7０

71

/＊

输出第

m

个节点的值

*/ﻫ７2

ｐｒintf("%d

",

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

/＊

从链表中删除第

ｍ

个节点

*／

75

pIter->neｘt

=

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

pＩｔｅr

=

pIter-＞neｘt;

７7

}ﻫ78

prｉnｔf（＂%d＂,

ｐIｔｅｒ－>dａta);ﻫ79

80

/*

释放申请的空间

*/ﻫ8１

deletｅ

[]pLiｓt;

82

retuｒn

0;ﻫ８3

}10举例说明什么是泛型编程ﻫ考点:泛型编程的基本概念ﻫ出现频率:★★★

解析：ﻫ泛型编程指编写完全一般化并可反复使用的算法，其效率与针对某特定数据类型而设计的算法相同。所谓泛型,是指具有在多种数据类型上皆可操作的含意,在C＋+中事实上就是使用模板实现。ﻫ举一个简朴的例子,比如我们要比较两个数的大小,这两个数的类型也许是inｔ，也也许是flｏat，尚有也许是dｏuｂle。一般编程时我们也许这样写函数(不考虑使用宏的情况）:

1

int

ｍax(iｎｔ

a，

int

b）

／/参数和返回值都是int类型ﻫ2

{ﻫ3

reｔurn

a

>

b?

ａ:

b;ﻫ4

}

5

6

ｆloat

ｍax（flｏat

ａ,

float

ｂ)

／/参数和返回值都是float类型

7

{ﻫ８

ｒetｕrn

a

>

b?

a:

b；ﻫ９

}ﻫ１0

11

double

ｍax(doublｅ

ａ，

ｄoｕｂle

b)

//参数和返回值都是ｄｏublｅ类型ﻫ12

{

1３

retuｒn

a

>

b?

a:

ｂ;ﻫ14

}ﻫ可以看到，上面写了3个重载函数，他们的区别仅仅只是类型(参数及返回值）不同，而函数体完全同样。

而假如使用模板,我们可以这样写:ﻫ1

ｔempｌaｔe

//clａsｓ也可用tyｐename替换ﻫ2

T

ｍａｘ（T

a,

T

ｂ)

//参数和返回值都是T类型

3

{ﻫ4

return

a

>

b?

a：

ｂ;ﻫ5

}ﻫ这里的cｌａsｓ不代表对象的类，而是类型（可用tｙpenａme替换）。这样maｘ函数的各个参数以及返回值类型都为T，对于任意类型的两个数,我们都可以调用maｘ求大小，测试代码如下:ﻫ1

int

main()ﻫ２

{ﻫ3

coｕt

＜<

max(1,

２)

<<

eｎdl;

/／隐式调用int类型的ｍax

4

coｕｔ

<<

max(1.1f,

2.2f）

<＜

endl;

//隐式调用float类型的ｍaxﻫ5

ｃouｔ

<<

maｘ(1.1１l,

2.22l)

＜<

endl;

//隐式调用dｏuble类型的mａxﻫ6

cｏut

<<

mａx('A＇，

'C')

<<

endl;

//隐式调用ｃhaｒ类型的ｍaxﻫ7

cout

＜＜

mａx(1,

２.０)

<<

enｄl;

//必须指定inｔ类型ﻫ8ﻫ9

return

０;ﻫ１0

}ﻫ程序执行结果如下:ﻫ１

2ﻫ2

2.２ﻫ3

2.２2

４

Ｃ

5

2ﻫ上面的程序中对于ｉnt、float、ｄoubｌe、以及cｈar类型的都进行了测试。这里需要注意的是第7行的测试中显示的指定了类型为int，这是由于参数１为inｔ类型,参数2.0为doubｌe类型,此时假如不指定是使用什么类型，会产生编译的模糊性，即编译器不知道是需要调用ｉｎt版本的ｍax还是调用double版本的max函数。

此外,Ｔ作为max函数的各参数以及返回值类型,它几乎可以是任意类型，即除了基本类型（int、flｏaｔ、char等)，还可以是类，当然这个类需要重载“>”操作符（由于maｘ函数体使用了这个操作符）。ﻫ显然，使用泛型编程（模板）可以极大地增长了代码的重用性。11考点:单链表的操作

出现频率:★★★★

已知两个链表hｅad1

和hｅad２

各自有序，请把它们合并成一个链表仍然有序。使用非递归方法以及递归方法。ﻫ解析：ﻫ一方面介绍非递归方法。由于两个链表head1

和hｅａd2都是有序的,所以我们只需要找把较短链表的各个元素有序的插入到较长的链表之中就可以了。ﻫ源代码如下：

１

ｎode＊

insert_node(node

＊head，

noｄe

*ｉtｅm)

／/head

!=

NULL

2

｛ﻫ3

ｎode

＊p

＝

ｈeaｄ；

４

noｄe

＊q

=

NULL;

//始终指向p之前的节点

5

6

wｈile(p->ｄatａ

＜

ｉteｍ->ｄata

＆&

p

!＝

NULL)ﻫ7

{ﻫ8

ｑ

＝

p;ﻫ9

p

＝

p-＞nｅxt;ﻫ１０

}ﻫ１1

if

(ｐ

＝=

hｅａd)

//插入到原头节点之前ﻫ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

/＊

两个有序链表进行合并

*／ﻫ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

)

／/有一个链表为空的情况，直接返回另一个链表ﻫ30

{

31

rｅtｕrｎ

h