第2章
面试需要的基础知识
面试官谈基础知识
“C++的基础知识,如面向对象的特性、构造函数、析构函数、动态绑定等,能够反映出应聘者是否善于把握问题本质,有没有耐心深入一个问题。另外还有常用的设计模式、UML图等,这些都能体现应聘者是否有软件工程方面的经验。”
——王海波(Autodesk,软件工程师)
“对基础知识的考查我特别重视C++中对内存的使用管理。我觉得内存管理是C++程序员特别要注意的,因为内存的使用和管理会影响程序的效率和稳定性。”
——蓝诚(Autodesk,软件工程师)
“基础知识反映了一个人的基本能力和基础素质,是以后工作中最核心的能力要求。我一般考查:(1)数据结构和算法;(2)编程能力;(3)部分数学知识,如概率;(4)问题的分析和推理能力。”
——张晓禹(百度,技术经理)
“我比较重视四块基础知识:(1)编程基本功(特别喜欢字符串处理这一类的问题);(2)并发控制;(3)算法、复杂度;(4)语言的基本概念。”
——张珺(百度,高级软件工程师)
“我会考查编程基础、计算机系统基础知识、算法以及设计能力。这些是一个软件工程师的最基本的东西,这些方面表现出色的人,我们一般认为是有发展潜力的。”
——韩伟东(盛大,高级研究员)
“(1)对OS的理解程度。这些知识对于工作中常遇到的内存管理、文件操作、程序性能、多线程、程序安全等有重要帮助。对于OS理解比较深入的人对于偏底层的工作上手一般比较快。(2)对于一门编程语言的掌握程度。一个热爱编程的人应该会对某种语言有比较深入的了解。通常这样的人对于新的编程语言上手也比较快,而且理解比较深入。(3)常用的算法和数据结构。不了解这些的程序员基本只能写写‘Hello World’。”
——陈黎明(微软,SDE II)
编程语言
程序员写代码总是基于某一种编程语言,因此技术面试的时候直接或者间接都会涉及至少一种编程语言。在面试的过程中,面试官要么直接问语言的语法,要么让应聘者用一种编程语言写代码解决一个问题,通过写出的代码来判断应聘者对他使用的语言的掌握程度。现在流行的编程语言很多,不同公司开发用的语言也不尽相同。做底层开发比如经常写驱动的人更习惯用C,Linux下有很多程序员用C++开发应用程序,基于Windows的C#项目已经越来越多,跨平台开发的程序员则可能更喜欢Java,随着苹果iPad、iPhone的热销已经有很多程序员投向了Objective C的阵营,同时还有很多人喜欢用脚本语言如Perl、Python开发短小精致的小应用软件。因此,不同公司面试的时候对编程语言的要求也有所不同。每一种编程语言都可以写出一本大部头的书籍,本书限于篇幅不可能面面俱到。本书中所有代码都用C/C++/C#实现,下面简要介绍一些C++/C#常见的面试题。
2.2.1 C++
国内绝大部分高校都开设C++的课程,因此绝大部分程序员都学过C++,于是C++成了各公司面试的首选编程语言。包括Autodesk在内的很多公司在面试的时候会有大量的C++的语法题,其他公司虽然不直接面试C++的语法,但面试题要求用C++实现算法。因此总的说来,应聘者不管去什么公司求职,都应该在一定程度上掌握C++。
通常语言面试有3种类型。第一种类型是面试官直接询问应聘者对C++概念的理解。这种类型的问题,面试官特别喜欢了解应聘者对C++关键字的理解程度。例如:在C++中,有哪4个与类型转换相关的关键字?这些关键字各有什么特点,应该在什么场合下使用?
在这种类型的题目中,sizeof是经常被问到的一个概念。比如下面的面试片段,就反复出现在各公司的技术面试中。
面试官:定义一个空的类型,里面没有任何成员变量和成员函数。对该类型求sizeof,得到的结果是多少?
应聘者:答案是1。
面试官:为什么不是0?
应聘者:空类型的实例中不包含任何信息,本来求sizeof应该是0,但是当我们声明该类型的实例的时候,它必须在内存中占有一定的空间,否则无法使用这些实例。至于占用多少内存,由编译器决定。Visual Studio中每个空类型的实例占用1字节的空间。
面试官:如果在该类型中添加一个构造函数和析构函数,再对该类型求sizeof,得到的结果又是多少?
应聘者:和前面一样,还是1。调用构造函数和析构函数只需要知道函数的地址即可,而这些函数的地址只与类型相关,而与类型的实例无关,编译器也不会因为这两个函数而在实例内添加任何额外的信息。
面试官:那如果把析构函数标记为虚函数呢?
应聘者:C++的编译器一旦发现一个类型中有虚拟函数,就会为该类型生成虚函数表,并在该类型的每一个实例中添加一个指向虚函数表的指针。在32位的机器上,一个指针占4字节的空间,因此求sizeof得到4;如果是64位的机器,一个指针占8字节的空间,因此求sizeof则得到8。
面试C/C++的第二种题型就是面试官拿出事先准备好的代码,让应聘者分析代码的运行结果。这种题型选择的代码通常包含比较复杂微妙的语言特性,这要求应聘者对C++考点有着透彻的理解。即使应聘者对考点有一点点模糊,那么最终他得到的结果和实际运行的结果可能就会差距甚远。
比如面试官递给应聘者一张有如下代码的A4打印纸要求他分析编译运行的结果,并提供3个选项:A.编译错误;B.编译成功,运行时程序崩溃;C.编译运行正常,输出10。
class A
{
private:
int value;
public:
A(int n) { value = n; }
A(A other) { value = other.value; }
void Print() { std::cout << value << std::endl; }
};
int _tmain(int argc, _TCHAR* argv[])
{
A a = 10;
A b = a;
b.Print();
return 0;
}
在上述代码中,复制构造函数A(A other)传入的参数是A的一个实例。由于是传值参数,我们把形参复制到实参会调用复制构造函数。因此如果允许复制构造函数传值,就会在复制构造函数内调用复制构造函数,就会形成永无休止的递归调用从而导致栈溢出。因此C++的标准不允许复制构造函数传值参数,在Visual Studio和GCC中,都将编译出错。要解决这个问题,我们可以把构造函数修改为A(const A& other),也就是把传值参数改成常量引用。
第三种题型就是要求应聘者写代码定义一个类型或者实现类型中的成员函数。让应聘者写代码的难度自然比让应聘者分析代码要高不少,因为能想明白的未必就能写得清楚。很多考查C++语法的代码题围绕在构造函数、析构函数及运算符重载。比如面试题1“赋值运算符函数”就是一个例子。
为了让大家能顺利地通过C++面试,更重要的是能更好地学习掌握C++这门编程语言,这里推荐几本C++的书,大家可以根据自己的具体情况选择阅读的顺序:
《Effective C++》。这本书很适合在面试之前突击C++。这本书列举了使用C++经常出现的问题及解决这些问题的技巧。该书中提到的问题也是面试官很喜欢问的问题。
《C++ Primer》。读完这本书,就会对C++的语法有全面的了解。
《Inside C++ Object Model》。这本书有助于我们深入了解C++对象的内部。读懂这本书后很多C++难题,比如前面的sizeof的问题、虚函数的调用机制等,都会变得很容易。
《The C++ Programming Language》。如果是想全面深入掌握C++,没有哪本书比这本书更适合的了。
面试题1:赋值运算符函数
题目:如下为类型CMyString的声明,请为该类型添加赋值运算符函数。
class CMyString
{
public:
CMyString(char* pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
private:
char* m_pData;
};
当面试官要求应聘者定义一个赋值运算符函数时,他会在检查应聘者写出的代码时关注如下几点:
是否把返回值的类型声明为该类型的引用,并在函数结束前返回实例自身的引用(即*this)。只有返回一个引用,才可以允许连续赋值。否则如果函数的返回值是void,应用该赋值运算符将不能做连续赋值。假设有3个CMyString的对象:str1、str2和str3,在程序中语句str1=str2=str3将不能通过编译。
是否把传入的参数的类型声明为常量引用。如果传入的参数不是引用而是实例,那么从形参到实参会调用一次复制构造函数。把参数声明为引用可以避免这样的无谓消耗,能提高代码的效率。同时,我们在赋值运算符函数内不会改变传入的实例的状态,因此应该为传入的引用参数加上const关键字。
是否释放实例自身已有的内存。如果我们忘记在分配新内存之前释放自身已有的空间,程序将出现内存泄露。
是否判断传入的参数和当前的实例(*this)是不是同一个实例。如果是同一个,则不进行赋值操作,直接返回。如果事先不判断就进行赋值,那么在释放实例自身的内存的时候就会导致严重的问题:当*this和传入的参数是同一个实例时,那么一旦释放了自身的内存,传入的参数的内存也同时被释放了,因此再也找不到需要赋值的内容了。
经典的解法,适用于初级程序员
当我们完整地考虑了上述4个方面之后,我们可以写出如下的代码:
CMyString& CMyString::operator =(const CMyString &str)
{
if(this == &str)
return *this;
delete []m_pData;
m_pData = NULL;
m_pData = new char[strlen(str.m_pData) + 1];
strcpy(m_pData, str.m_pData);
return *this;
}
这是一般C++教材上提供的参考代码。如果接受面试的是应届毕业生或者C++初级程序员,能全面地考虑到前面四点并完整地写出代码,面试官可能会让他通过这轮面试。但如果面试的是C++高级程序员,面试官可能会提出更高的要求。
考虑异常安全性的解法,高级程序员必备
在前面的函数中,我们在分配内存之前先用delete释放了实例m_pData的内存。如果此时内存不足导致new char抛出异常,m_pData将是一个空指针,这样非常容易导致程序崩溃。也就是说一旦在赋值运算符函数内部抛出一个异常,CMyString的实例不再保持有效的状态,这就违背了异常安全性(Exception Safety)原则。
要想在赋值运算符函数中实现异常安全性,我们有两种方法。一个简单的办法是我们先用new分配新内容再用delete释放已有的内容。这样只在分配内容成功之后再释放原来的内容,也就是当分配内存失败时我们能确保CMyString的实例不会被修改。我们还有一个更好的办法是先创建一个临时实例,再交换临时实例和原来的实例。下面是这种思路的参考代码:
CMyString& CMyString::operator =(const CMyString &str)
{
if(this != &str)
{
CMyString strTemp(str);
char* pTemp = strTemp.m_pData;
strTemp.m_pData = m_pData;
m_pData = pTemp;
}
return *this;
}
在这个函数中,我们先创建一个临时实例strTemp,接着把strTemp.m_pData和实例自身的m_pData做交换。由于strTemp是一个局部变量,但程序运行到if的外面时也就出了该变量的作用域,就会自动调用strTemp的析构函数,把strTemp.m_pData所指向的内存释放掉。由于strTemp.m_pData指向的内存就是实例之前m_pData的内存,这就相当于自动调用析构函数释放实例的内存。
在新的代码中,我们在CMyString的构造函数里用new分配内存。如果由于内存不足抛出诸如bad_alloc等异常,我们还没有修改原来实例的状态,因此实例的状态还是有效的,这也就保证了异常安全性。
如果应聘者在面试的时候能够考虑到这个层面,面试官就会觉得他对代码的异常安全性有很深的理解,那么他自然也就能通过这轮面试了。
源代码:
本题完整的源代码详见01_AssignmentOperator项目。
测试用例:
把一个CMyString的实例赋值给另外一个实例。
把一个CMyString的实例赋值给它自己。
连续赋值。
本题考点:
考查对C++的基础语法的理解,如运算符函数、常量引用等。
考查对内存泄露的理解。
对高级C++程序员,面试官还将考查应聘者对代码异常安全性的理解。
2.2.2 C#
C#是微软在推出新的开发平台.NET时同步推出的编程语言。由于Windows至今仍然是用户最多的操作系统,而.NET又是微软近年来力推的开发平台,因此C#无论在桌面软件还是网络应用的开发上都有着广泛的应用,所以我们也不难理解为什么现在很多基于Windows系统开发的公司都会要求应聘者掌握C#。
C#可以看成是一门以C++为基础发展起来的一种托管语言,因此它的很多关键字甚至语法都和C++很类似。对一个学习过C++编程的程序员而言,他用不了多长时间学习就能用C#来开发软件。然而我们也要清醒地认识到,虽然学习C#与C++相同或者类似的部分很容易,但要掌握并区分两者不同的地方却不是一件很容易的事情。面试官总是喜欢深究我们模棱两可的地方以考查我们是不是真的理解了,因此我们要着重注意C#与C++不同的语法特点。下面的面试片段就是一个例子:
面试官:C++中可以用struct和class来定义类型。这两种类型有什么区别?
应聘者:如果没有标明成员函数或者成员变量的访问权限级别,在struct中默认的是public,而在class中默认的是private。
面试官:那在C#中呢?
应聘者:C#和C++不一样。在C#中如果没有标明成员函数或者成员变量的访问权限级别,struct和class中都是private的。struct和class的区别是struct定义的是值类型,值类型的实例在栈上分配内存;而class定义的是引用类型,引用类型的实例在堆上分配内存。
在C#中,每个类型中和C++一样,都有构造函数。但和C++不同的是,我们在C#中可以为类型定义一个Finalizer和Dispose方法以释放资源。Finalizer方法虽然写法与C++的析构函数看起来一样,都是后面跟类型名字,但与C++析构函数的调用时机是确定的不同,C#的Finalizer是在运行时(CLR)做垃圾回收时才会被调用,它的调用时机是由运行时决定的,因此对程序员来说是不确定的。另外,在C#中可以为类型定义一个特殊的构造函数:静态构造函数。这个函数的特点是在类型第一次被使用之前由运行时自动调用,而且保证只调用一次。关于静态构造函数,我们有很多有意思的面试题,比如运行下面的C#代码,输出的结果是什么?
class A
{
public A(string text)
{
Console.WriteLine(text);
}
}
class B
{
static A a1 = new A("a1");
A a2 = new A("a2");
static B()
{
a1 = new A("a3");
}
public B()
{
a2 = new A("a4");
}
}
class Program
{
static void Main(string[] args)
{
B b = new B();
}
}
在调用类型B的代码之前先执行B的静态构造函数。静态构造函数先初始化类型的静态变量,再执行函数体内的语句。因此先打印a1再打印a3。接下来执行B b = new B(),即调用B的普通构造函数。构造函数先初始化成员变量,再执行函数体内的语句,因此先后打印出a2、a4。因此运行上面的代码,得到的结果将是打印出4行,分别是a1、a3、a2、a4。
我们除了要关注C#和C++不同的知识点之外,还要格外关注C#一些特有的功能,比如反射、应用程序域(AppDomain)等。这些概念还相互关联,要花很多时间学习研究才能透彻地理解它们。下面的代码就是一段关于反射和应用程序域的代码,运行它得到的结果是什么?
[Serializable]
internal class A : MarshalByRefObject
{
public static int Number;
public void SetNumber(int value)
{
Number = value;
}
}
[Serializable]
internal class B
{
public static int Number;
public void SetNumber(int value)
{
Number = value;
}
}
class Program
{
static void Main(string[] args)
{
String assambly = Assembly.GetEntryAssembly().FullName;
AppDomain domain = AppDomain.CreateDomain("NewDomain");
A.Number = 10;
String nameOfA = typeof(A).FullName;
A a = domain.CreateInstanceAndUnwrap(assambly, nameOfA) as A;
a.SetNumber(20);
Console.WriteLine("Number in class A is {0}", A.Number);
B.Number = 10;
String nameOfB = typeof(B).FullName;
B b = domain.CreateInstanceAndUnwrap(assambly, nameOfB) as B;
b.SetNumber(20);
Console.WriteLine("Number in class B is {0}", B.Number);
}
}
上述C#代码先创建一个名为NewDomain的应用程序域,并在该域中利用反射机制创建类型A的一个实例和类型B的一个实例。我们注意到类型A是继承自MarshalByRefObject,而B不是。虽然这两个类型的结构一样,但由于基类不同而导致在跨越应用程序域的边界时表现出的行为将大不相同。
先考虑A的情况。由于A继承自MarshalByRefObject,那么a实际上只是在默认的域中的一个代理实例(Proxy),它指向位于NewDomain域中的A的一个实例。当调用a的方法SetNumber时,是在NewDomain域中调用该方法,它将修改NewDomain域中静态变量A.Number的值并设为20。由于静态变量在每个应用程序域中都有一份独立的拷贝,修改NewDomain域中的静态变量A.Number对默认域中的静态变量A.Number没有任何影响。由于Console.WriteLine是在默认的应用程序域中输出A.Number,因此输出仍然是10。
接着讨论B。由于B只是从Object继承而来的类型,它的实例穿越应用程序域的边界时,将会完整地复制实例。因此在上述代码中,我们尽管试图在NewDomain域中生成B的实例,但会把实例b复制到默认的应用程序域。此时调用方法b.SetNumber也是在缺省的应用程序域上进行,它将修改默认的域上的A.Number并设为20。再在默认的域上调用Console.WriteLine时,它将输出20。
下面推荐两本C#相关的书籍,以方便大家应对C#面试并学习好C#。
《Professional C#》。这本书最大的特点是在附录中有几章专门写给已经有其他语言(如VB、C++和Java)经验的程序员,它详细讲述了C#和其他语言的区别,看了这几章之后就不会把C#和之前掌握的语言相混淆。
Jeffrey Richter的《CLR Via C#》。该书不仅深入地介绍了C#语言,同时对CLR及.NET做了全面的剖析。如果能够读懂这本书,那么我们就能深入理解装箱卸箱、垃圾回收、反射等概念,知其然的同时也能知其所以然,通过C#相关的面试自然也就不难了。
面试题2:实现Singleton模式
题目:设计一个类,我们只能生成该类的一个实例。
只能生成一个实例的类是实现了Singleton(单例)模式的类型。由于设计模式在面向对象程序设计中起着举足轻重的作用,在面试过程中很多公司都喜欢问一些与设计模式相关的问题。在常用的模式中,Singleton是唯一一个能够用短短几十行代码完整实现的模式。因此,写一个Singleton的类型是一个很常见的面试题。
不好的解法一:只适用于单线程环境
由于要求只能生成一个实例,因此我们必须把构造函数设为私有函数以禁止他人创建实例。我们可以定义一个静态的实例,在需要的时候创建该实例。下面定义类型Singleton1就是基于这个思路的实现:
public sealed class Singleton1
{
private Singleton1()
{
}
private static Singleton1 instance = null;
public static Singleton1 Instance
{
get
{
if (instance == null)
instance = new Singleton1();
return instance;
}
}
}
上述代码在Singleton的静态属性Instance中,只有在instance为null的时候才创建一个实例以避免重复创建。同时我们把构造函数定义为私有函数,这样就能确保只创建一个实例。
不好的解法二:虽然在多线程环境中能工作但效率不高
解法一中的代码在单线程的时候工作正常,但在多线程的情况下就有问题了。设想如果两个线程同时运行到判断instance是否为null的if语句,并且instance的确没有创建时,那么两个线程都会创建一个实例,此时类型Singleton1就不再满足单例模式的要求了。为了保证在多线程环境下我们还是只能得到类型的一个实例,需要加上一个同步锁。把Singleton1稍做修改得到了如下代码:
public sealed class Singleton2
{
private Singleton2()
{
}
private static readonly object syncObj = new object();
private static Singleton2 instance = null;
public static Singleton2 Instance
{
get
{
lock (syncObj)
{
if (instance == null)
instance = new Singleton2();
}
return instance;
}
}
}
我们还是假设有两个线程同时想创建一个实例。由于在一个时刻只有一个线程能得到同步锁,当第一个线程加上锁时,第二个线程只能等待。当第一个线程发现实例还没有创建时,它创建出一个实例。接着第一个线程释放同步锁,此时第二个线程可以加上同步锁,并运行接下来的代码。这个时候由于实例已经被第一个线程创建出来了,第二个线程就不会重复创建实例了,这样就保证了我们在多线程环境中也只能得到一个实例。
但是类型Singleton2还不是很完美。我们每次通过属性Instance得到Singleton2的实例,都会试图加上一个同步锁,而加锁是一个非常耗时的操作,在没有必要的时候我们应该尽量避免。
可行的解法:加同步锁前后两次判断实例是否已存在
我们只是在实例还没有创建之前需要加锁操作,以保证只有一个线程创建出实例。而当实例已经创建之后,我们已经不需要再做加锁操作了。于是我们可以把解法二中的代码再做进一步的改进:
public sealed class Singleton3
{
private Singleton3()
{
}
private static object syncObj = new object();
private static Singleton3 instance = null;
public static Singleton3 Instance
{
get
{
if (instance == null)
{
lock (syncObj)
{
if (instance == null)
instance = new Singleton3();
}
}
return instance;
}
}
}
Singleton3中只有当instance为null即没有创建时,需要加锁操作。当instance已经创建出来之后,则无须加锁。因为只在第一次的时候instance为null,因此只在第一次试图创建实例的时候需要加锁。这样Singleton3的时间效率比Singleton2要好很多。
Singleton3用加锁机制来确保在多线程环境下只创建一个实例,并且用两个if判断来提高效率。这样的代码实现起来比较复杂,容易出错,我们还有更加优秀的解法。
强烈推荐的解法一:利用静态构造函数
C#的语法中有一个函数能够确保只调用一次,那就是静态构造函数,我们可以利用C#这个特性实现单例模式如下:
public sealed class Singleton4
{
private Singleton4()
{
}
private static Singleton4 instance = new Singleton4();
public static Singleton4 Instance
{
get
{
return instance;
}
}
}
Singleton4的实现代码非常简洁。我们在初始化静态变量instance的时候创建一个实例。由于C#是在调用静态构造函数时初始化静态变量,.NET运行时能够确保只调用一次静态构造函数,这样我们就能够保证只初始化一次instance。
C#中调用静态构造函数的时机不是由程序员掌控的,而是当.NET运行时发现第一次使用一个类型的时候自动调用该类型的静态构造函数。因此在Singleton4中,实例instance并不是第一次调用属性Singleton4.Instance的时候创建,而是在第一次用到Singleton4的时候就会被创建。假设我们在Singleton4中添加一个静态方法,调用该静态函数是不需要创建一个实例的,但如果按照Singleton4的方式实现单例模式,则仍然会过早地创建实例,从而降低内存的使用效率。
强烈推荐的解法二:实现按需创建实例
最后的一个实现Singleton5则很好地解决了Singleton4中的实例创建时机过早的问题:
public sealed class Singleton5
{
Singleton5()
{
}
public static Singleton5 Instance
{
get
{
return Nested.instance;
}
}
class Nested
{
static Nested()
{
}
internal static readonly Singleton5 instance = new Singleton5();
}
}
在上述Singleton5的代码中,我们在内部定义了一个私有类型Nested。当第一次用到这个嵌套类型的时候,会调用静态构造函数创建Singleton5的实例instance。类型Nested只在属性Singleton5.Instance中被用到,由于其私有属性他人无法使用Nested类型。因此当我们第一次试图通过属性Singleton5.Instance得到Singleton5的实例时,会自动调用Nested的静态构造函数创建实例instance。如果我们不调用属性Singleton5.Instance,那么就不会触发.NET运行时调用Nested,也不会创建实例,这样就真正做到了按需创建。
解法比较
在前面的5种实现单例模式的方法中,第一种方法在多线程环境中不能正常工作,第二种模式虽然能在多线程环境中正常工作但时间效率很低,都不是面试官期待的解法。在第三种方法中我们通过两次判断一次加锁确保在多线程环境能高效率地工作。第四种方法利用C#的静态构造函数的特性,确保只创建一个实例。第五种方法利用私有嵌套类型的特性,做到只在真正需要的时候才会创建实例,提高空间使用效率。如果在面试中给出第四种或者第五种解法,毫无疑问会得到面试官的青睐。
源代码:
本题完整的源代码详见02_Singleton项目。
本题考点:
考查对单例(Singleton)模式的理解。
考查对C#的基础语法的理解,如静态构造函数等。
考查对多线程编程的理解。
本题扩展:
在前面的代码中,5种单例模式的实现把类型标记为sealed,表示它们不能作为其他类型的基类。现在我们要求定义一个表示总统的类型President,可以从该类型继承出FrenchPresident和AmericanPresident等类型。这些派生类型都只能产生一个实例。请问该如何设计实现这些类型?
数据结构
数据结构一直是技术面试的重点,大多数面试题都是围绕着数组、字符串、链表、树、栈及队列这几种常见的数据结构展开的,因此每一个应聘者都要熟练掌握这几种数据结构。
数组和字符串是两种最基本的数据结构,它们用连续内存分别存储数字和字符。链表和树是面试中出现频率最高的数据结构。由于操作链表和树需要操作大量的指针,应聘者在解决相关问题的时候一定要留意代码的鲁棒性,否则容易出现程序崩溃的问题。栈是一个与递归紧密相关的数据结构,同样队列也与广度优先遍历算法紧密相关。深刻理解这两种数据结构能帮助我们解决很多算法问题。
2.3.1 数组
数组可以说是最简单的一种数据结构,它占据一块连续的内存并按照顺序存储数据。创建数组时,我们需要首先指定数组的容量大小,然后根据大小分配内存。即使我们只在数组中存储一个数字,也需要为所有的数据预先分配内存。因此数组的空间效率不是很好,经常会有空闲的区域没有得到充分利用。
由于数组中的内存是连续的,于是可以根据下标在O(1)时间读/写任何元素,因此它的时间效率是很高的。我们可以根据数组时间效率高的优点,用数组来实现简单的哈希表:把数组的下标设为哈希表的键值(Key),而把数组中的每一个数字设为哈希表的值(Value),这样每一个下标及数组中该下标对应的数字就组成了一个键值-值的配对。有了这样的哈希表,我们就可以在O(1)实现查找,从而可以快速高效地解决很多问题。面试题35“第一个只出现一次的字母”就是一个很好的例子。
为了解决数组空间效率不高的问题,人们又设计实现了多种动态数组,比如C++的STL中的vector。为了避免浪费,我们先为数组开辟较小的空间,然后往数组中添加数据。当数据的数目超过数组的容量时,我们再重新分配一块更大的空间(STL的vector每次扩充容量时,新的容量都是前一次的两倍),把之前的数据复制到新的数组中,再把之前的内存释放,这样就能减少内存的浪费。但我们也注意到每一次扩充数组容量时都有大量的额外操作,这对时间性能有负面影响,因此使用动态数组时要尽量减少改变数组容量大小的次数。
在C/C++中,数组和指针是相互关联又有区别的两个概念。当我们声明一个数组时,其数组的名字也是一个指针,该指针指向数组的第一个元素。我们可以用一个指针来访问数组。但值得注意的是,C/C++没有记录数组的大小,因此用指针访问数组中的元素时,程序员要确保没有超出数组的边界。下面通过一个例子来了解数组和指针的区别。运行下面的代码,请问输出是什么?
int GetSize(int data[])
{
return sizeof(data);
}
int _tmain(int argc, _TCHAR* argv[])
{
int data1[] = {1, 2, 3, 4, 5};
int size1 = sizeof(data1);
int* data2 = data1;
int size2 = sizeof(data2);
int size3 = GetSize(data1);
printf("%d, %d, %d", size1, size2, size3);
}
答案是输出“20, 4, 4”。data1是一个数组,sizeof(data1)是求数组的大小。这个数组包含5个整数,每个整数占4字节,因此总共是20字节。data2声明为指针,尽管它指向了数组data1的第一个数字,但它的本质仍然是一个指针。在32位系统上,对任意指针求sizeof,得到的结果都是4。在C/C++中,当数组作为函数的参数进行传递时,数组就自动退化为同类型的指针。因此尽管函数GetSize的参数data被声明为数组,但它会退化为指针,size3的结果仍然是4。
面试题3:二维数组中的查找
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
在分析这个问题的时候,很多应聘者都会把二维数组画成矩形,然后从数组中选取一个数字,分3种情况来分析查找的过程。当数组中选取的数字刚好和要查找的数字相等时,就结束查找过程。如果选取的数字小于要查找的数字,那么根据数组排序的规则,要查找的数字应该在当前选取的位置的右边或者下边(如图2.1(a)所示)。同样,如果选取的数字大于要查找的数字,那么要查找的数字应该在当前选取的位置的上边或者左边(如图2.1(b)所示)。
图2.1 二维数组中的查找