C和C++经典面试题(面试必备).docx

C和C++经典面试题(面试必备)
C和C++经典面试题(面试必备)

编辑整理：

尊敬的读者朋友们：
这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（C和C++经典面试题(面试必备)）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为C和C++经典面试题(面试必备)的全部内容。

C/C++经典面试题(面试必备）

面试题 1：变量的声明和定义有什么区别
为变量分配地址和存储空间的称为定义，不分配地址的称为声明。一个变量可以在多个地方声明，
但是只在一个地方定义。加入 extern 修饰的是变量的声明， 说明此变量将在文件以外或在文件后面部分
定义.
说明：很多时候一个变量,只是声明不分配内存空间，直到具体使用时才初始化,分配内存空间,
如外部变量. 面试题 2：写出 bool 、 int、 float、指针变量与“零值” 比较的 if 语句
bool 型数据：
if( flag )
｛
A;
｝
else
{
B；
｝
int 型数据：
if（ 0 ！= flag ）
{
A;
}
else
｛
B；
｝
指针型数：
if（ NULL == flag )
{
A;
｝
else
{
B；
｝
float 型数据：
if （ （ flag 〉= NORM ) &＆ ( flag 〈= NORM ) ）
｛
A；
} 2
注意:应特别注意在 int、指针型变量和“零值”比较的时候，把“零值"放在左边，这样当把“ ==”
误写成“ =”时，编译器可以报错，否则这种逻辑错误不容易发现，并且可能导致很严重的后果。 面试题 3： sizeof 和 strlen 的区别
sizeof 和 strlen 有以下区别：
q sizeof 是一个操作符， strlen 是库函数。
q sizeof 的参数可以是数据的类型，也可以是变量，而 strlen 只能以结尾为‘\0‘的字符串作参数。
q 编译器在编译时就计算出了 sizeof 的结果。而 strlen 函数必须在运行时才能计算出来。并且 sizeof
计算的是数据类型占内存的大小，而 strlen 计算的是字符串实际的长度。
q 数组做 sizeof 的参数不退化，传递给 strlen 就退化为指针了.
注意：有些是操作符看起来像是函数，而有些函数名看起来又像操作符，这类容易混淆的名称一定
要加以区分，否则遇到数组名这类特殊数据类型作参数时就很容易出错。最容易混淆为函数的操作符就
是 sizeof。
面试题 4: C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在 C 中 static 用来修饰局部静态变量和外部静态变量、函数。而 C++中除了上述功能外，还用来定
义类的成员变量和函数。即静态成员和静态成员函数。
注意:编程时 static 的记忆性，和全局性的特点可以让在不同时期调用的函数进行通信,传递信息,
而 C++的静态成员则可以在多个对象实例间进行通信,传递信息.
面试题 5： Ｃ中的 malloc 和Ｃ＋＋中的 new 有什么区别
malloc 和 new 有以下不同：
( 1） new、 delete 是操作符，可以重载，只能在 C++中使用.
（ 2） malloc、 free 是函数，可以覆盖， C、 C++中都可以使用。
（ 3) new 可以调用对象的构造函数，对应的 delete 调用相应的析构函数.
( 4） malloc 仅仅分配内存， free 仅仅回收内存，并不执行构造和析构函数
（ 5) new、 delete 返回的是某种数据类型指针， malloc、 free 返回的是 void 指针.
注意： malloc 申请的内存空间要用 free 释放，而 new 申请的内存空间要用 delete 释放,不要混用。
因为两者实现的机理不同。 面试题 6： 写一个“ 标准” 宏 MIN
#define min(a,b）(（a）<=(b)?(a）:(b）)
注意：在调用时一定要注意这个宏定义的副作用，如下调用:
((++＊p)<=(x)？(++＊p）：(x）.
p 指针就自加了两次，违背了 MIN 的本意。
3 面试题 7： 一个指针可以是 volatile 吗
可以，因为指针和普通变量一样，有时也有变化程序的不可控性。常见例:子中断服务子程序修改
一个指向一个 buffer 的指针时，必须用 volatile 来修饰这个指针.
说明:指针是一种普通的变量，从访问上没有什么不同于其他变量的特性.其保存的数值是个整型
数据，和整型变量不同的是,这个整型数据指向的是一段内存地址。 面试题 8: a 和＆a 有什么区别
请写出以下代码的打印结果，主要目的是考察 a 和&a 的区别。
#include<stdio。h>
void main( void ）
｛
int a[5]=｛1，2,3,4,5};
int ＊ptr=(int *）（＆a+1）;
printf(”％d，％d"，＊(a+1），＊(ptr—1))；
return；
}
输出结果： 2， 5.
注意：数组名 a 可以作数组的首地址，而&a 是数组的指针.思考，将原式的 int *ptr=（int *）（&a+1);
改为 int ＊ptr=（int *)(a+1);时输出结果将是什么呢？ 面试题 9： 简述 C、 C++程序编译的内存分配情况
C、 C++中内存分配方式可以分为三种:
（ 1） 从静态存储区域分配：
内存在程序编译时就已经分配好，这块内存在程序的整个运行期间都存在。 速度快、 不容易出错，
因为有系统会善后。 例如全局变量, static 变量等。
（ 2） 在栈上分配：
在执行函数时，函数内局部变量的存储单元都在栈上创建,函数执行结束时这些存储单元自动被释
放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
（ 3) 从堆上分配：
即动态内存分配。程序在运行的时候用 malloc 或 new 申请任意大小的内存，程序员自己负责在何
时用 free 或 delete 释放内存。动态内存的生存期由程序员决定，使用非常灵活。 如果在堆上分配了空间,
就有责任回收它，否则运行的程序会出现内存泄漏， 另外频繁地分配和释放不同大小的堆空间将会产生
堆内碎块.
一个 C、 C++程序编译时内存分为 5 大存储区：堆区、栈区、全局区、文字常量区、程序代码区.
4 面试题 10： 简述 strcpy、 sprintf 与 memcpy 的区别
三者主要有以下不同之处：
（ 1） 操作对象不同， strcpy 的两个操作对象均为字符串， sprintf 的操作源对象可以是多种数据类型,
目的操作对象是字符串， memcpy 的两个对象就是两个任意可操作的内存地址，并不限于何种数据类型。
（ 2） 执行效率不同， memcpy 最高， strcpy 次之, sprintf 的效率最低。
（ 3） 实现功能不同， strcpy 主要实现字符串变量间的拷贝， sprintf 主要实现其他数据类型格式到字
符串的转化， memcpy 主要是内存块间的拷贝。
说明： strcpy、 sprintf 与 memcpy 都可以实现拷贝的功能，但是针对的对象不同，根据实际需求，来
选择合适的函数实现拷贝功能。 面试题 11： 设置地址为 0x67a9 的整型变量的值为 0xaa66
int *ptr；
ptr = (int ＊）0x67a9;
＊ptr = 0xaa66；
说明：这道题就是强制类型转换的典型例子,无论在什么平台地址长度和整型数据的长度是一样的，
即一个整型数据可以强制转换成地址指针类型,只要有意义即可。 面试题 12: 面向对象的三大特征
面向对象的三大特征是封装性、继承性和多态性：
q 封装性：将客观事物抽象成类，每个类对自身的数据和方法实行 protection（ private, protected，
public)。
q 继承性：广义的继承有三种实现形式: 实现继承（ 使用基类的属性和方法而无需额外编码的能力)、可
视继承(子窗体使用父窗体的外观和实现代码)、接口继承（仅使用属性和方法,实现滞后到子类实现）。
q 多态性：是将父类对象设置成为和一个或更多它的子对象相等的技术.用子类对象给父类对象赋值
之后，父类对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。
说明：面向对象的三个特征是实现面向对象技术的关键，每一个特征的相关技术都非常的复杂,程
序员应该多看、多练. 面试题 13： C++的空类有哪些成员函数
q 缺省构造函数.
q 缺省拷贝构造函数。
q 缺省析构函数.
q 缺省赋值运算符。
q 缺省取址运算符。
q 缺省取址运算符 const。
注意：有些书上只是简单的介绍了前四个函数.没有提及后面这两个函数.但后面这两个函数也是
空类的默认函数。另外需要注意的是，只有当实际使用这些函数的时候,编译器才会去定义它们.
5 面试题 14： 谈谈你对拷贝构造函数和赋值运算符的认识
拷贝构造函数和赋值运算符重载有以下两个不同之处：
（ 1)拷贝构造函数生成新的类对象，而赋值运算符不能.
（ 2）由于拷贝构造函数是直接构造一个新的类对象,所以在初始化这个对象之前不用检验源对象
是否和新建对象相同。而赋值运算符则需要这个操作,另外赋值运算中如果原来的对象中有内存分配要
先把内存释放掉
注意：当有类中有指针类型的成员变量时，一定要重写拷贝构造函数和赋值运算符,不要使用默认
的. 面试题 15： 用 C++设计一个不能被继承的类
template 〈typename T> class A
{
friend T;
private:
A(） ｛}
~A() ｛}
};
class B : virtual public A<B〉
{
public:
B() {｝
~B（） ｛｝
｝；
class C : virtual public B
{
public：
C(） ｛｝
～C（） ｛｝
｝；
void main( void ）
{
B b；
//C c;
return；
｝
注意:构造函数是继承实现的关键,每次子类对象构造时，首先调用的是父类的构造函数,然后才
是自己的. 面试题 16： 访问基类的私有虚函数
写出以下程序的输出结果：
#include 〈iostream。h〉
class A
｛ 6
virtual void g(）
｛
cout 〈< ”A：:g” 〈< endl；
｝
private：
virtual void f(）
{
cout 〈〈 ”A:：f" 〈< endl；
}
}；
class B : public A
｛
void 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 < 3； i++)
{
pFun = ( Fun )*（ ( int* ) ＊ ( int＊ ）（ &b ） + i ）；
pFun（)；
}
｝
输出结果：
B:：g
A::f
B：：h
注意：本题主要考察了面试者对虚函数的理解程度。一个对虚函数不了解的人很难正确的做出本题。
在学习面向对象的多态性时一定要深刻理解虚函数表的工作原理. 面试题 17： 简述类成员函数的重写、重载和隐藏的区别
（ 1）重写和重载主要有以下几点不同。
q 范围的区别：被重写的和重写的函数在两个类中,而重载和被重载的函数在同一个类中。
q 参数的区别:被重写函数和重写函数的参数列表一定相同，而被重载函数和重载函数的参数列表一
定不同。
q virtual 的区别:重写的基类中被重写的函数必须要有 virtual 修饰，而重载函数和被重载函数可以被
7
virtual 修饰，也可以没有。
（ 2）隐藏和重写、重载有以下几点不同。
q 与重载的范围不同：和重写一样，隐藏函数和被隐藏函数不在同一个类中。
q 参数的区别：隐藏函数和被隐藏的函数的参数列表可以相同，也可不同，但是函数名肯定要相同。
当参数不相同时，无论基类中的参数是否被 virtual 修饰，基类的函数都是被隐藏,而不是被重写.
说明：虽然重载和覆盖都是实现多态的基础，但是两者实现的技术完全不相同，达到的目的也是完
全不同的,覆盖是动态态绑定的多态，而重载是静态绑定的多态。 面试题 18: 简述多态实现的原理
编译器发现一个类中有虚函数， 便会立即为此类生成虚函数表 vtable。 虚函数表的各表项为指向对
应虚函数的指针.编译器还会在此类中隐含插入一个指针 vptr（对 vc 编译器来说，它插在类的第一个位
置上） 指向虚函数表. 调用此类的构造函数时，在类的构造函数中，编译器会隐含执行 vptr 与 vtable 的
关联代码，将 vptr 指向对应的 vtable， 将类与此类的 vtable 联系了起来。 另外在调用类的构造函数时,
指向基础类的指针此时已经变成指向具体的类的 this 指针,这样依靠此 this 指针即可得到正确的 vtable，。
如此才能真正与函数体进行连接,这就是动态联编，实现多态的基本原理。
注意：一定要区分虚函数，纯虚函数、虚拟继承的关系和区别。牢记虚函数实现原理,因为多态
C++面试的重要考点之一，而虚函数是实现多态的基础。
面试题 19： 链表和数组有什么区别
数组和链表有以下几点不同：
（ 1）存储形式: 数组是一块连续的空间，声明时就要确定长度。 链表是一块可不连续的动态空间,
长度可变,每个结点要保存相邻结点指针.
（ 2）数据查找： 数组的线性查找速度快, 查找操作直接使用偏移地址。 链表需要按顺序检索结点，
效率低。
（ 3)数据插入或删除： 链表可以快速插入和删除结点， 而数组则可能需要大量数据移动。
（ 4）越界问题： 链表不存在越界问题，数组有越界问题。
说明：在选择数组或链表数据结构时，一定要根据实际需要进行选择。数组便于查询，链表便于插
入删除。数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间.
面试题 20： 怎样把一个单链表反序
( 1） 反转一个链表.循环算法。
List reverse(List n)
｛
if（！n) //判断链表是否为空,为空即退出。
{
return n；
｝
list cur = n.next； //保存头结点的下个结点
list pre = n; //保存头结点
list tmp；
8
pre。next = null； //头结点的指针指空，转换后变尾结点
while ( NULL != cur.next ) //循环直到 cur.next 为空
{
tmp = cur; //实现如图 10.3—图 10.5 所示
tmp.next = pre
pre = tmp;
cur = cur.next；
｝
return tmp; //f 返回头指针
｝
（ 2） 反转一个链表。递归算法.
List *reverse（ List *oldList， List *newHead = NULL )
{
List *next = oldList-〉 next; //记录上次翻转后的链表
oldList-〉 next = newHead； //将当前结点插入到翻转后链表的开头
newHead = oldList; //递归处理剩余的链表
return ( next==NULL ）？ newHead: reverse( t， newHead ）；
}
说明： 循环算法就是图 10。2—图 10。5 的移动过程，比较好理解和想到。递归算法的设计虽有一点难
度，但是理解了循环算法，再设计递归算法就简单多了。
面试题 21:简述队列和栈的异同
队列和栈都是线性存储结构，但是两者的插入和删除数据的操作不同，队列是“先进先出",栈是
“后进先出”。
注意:区别栈区和堆区。堆区的存取是“顺序随意”，而栈区是“后进先出".栈由编译器自动分
配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。 堆一般由程序员
分配释放， 若程序员不释放,程序结束时可能由 OS 回收。分配方式类似于链表。
它与本题中的堆和栈是两回事。堆栈只是一种数据结构，而堆区和栈区是程序的不同内存存储区域。
面试题 22: 能否用两个栈实现一个队列的功能
结点结构体:
typedef struct node
｛
int data；
node *next；
｝node，＊LinkStack;
创建空栈：
LinkStack CreateNULLStack( LinkStack &S)
{
S = (LinkStack)malloc（ sizeof（ node ） ）； //申请新结点
if（ NULL == S）
｛
printf("Fail to malloc a new node.\n");
9
return NULL;
｝ S
—〉data = 0; //初始化新结点
S-〉next = NULL;
return S;
}
栈的插入函数：
LinkStack Push（ LinkStack ＆S， int data)
｛
if（ NULL == S） //检验栈
{
printf（”There no node in stack!");
return NULL;
}
LinkStack p = NULL;
p = (LinkStack）malloc（ sizeof（ node ) ); //申请新结点
if( NULL == p)
{
printf（”Fail to malloc a new node。\n”);
return S;
｝
if（ NULL == S->next）
｛
p->next = NULL;
｝
else
{
p->next = S—>next;
} p
—>data = data； //初始化新结点
S—>next = p； //插入新结点
return S；
}
出栈函数:
node Pop( LinkStack &S）
{
node temp;
temp。data = 0；
temp.next = NULL;
if( NULL == S） //检验栈
{
printf("There no node in stack!"）;
return temp;
｝
temp = ＊S；
10
if( S-〉next == NULL )
{
printf("The stack is NULL，can't pop！\n”）;
return temp;
}
LinkStack p = S -〉next; //节点出栈
S->next = S-〉next->next;
temp = ＊p；
free( p ）;
p = NULL;
return temp;
｝
双栈实现队列的入队函数：
LinkStack StackToQueuPush（ LinkStack &S, int data）
{
node n；
LinkStack S1 = NULL；
CreateNULLStack（ S1 ); //创建空栈
while( NULL ！= S—>next ) //S 出栈入 S1
{
n = Pop( S ）；
Push（ S1, n。data ）；
｝
Push( S1， data ）; //新结点入栈
while（ NULL != S1-〉next ） //S1 出栈入 S
{
n = Pop( S1 ）；
Push( S， n.data ）;
}
return S；
｝
说明：用两个栈能够实现一个队列的功能，那用两个队列能否实现一个队列的功能呢?结果是否定
的，因为栈是先进后出，将两个栈连在一起，就是先进先出。而队列是现先进先出，无论多少个连在一
起都是先进先出,而无法实现先进后出.
面试题 23： 计算一颗二叉树的深度
深度的计算函数:
int depth（BiTree T）
｛
if(!T） return 0； //判断当前结点是否为叶子结点
11
int d1= depth(T—〉lchild）； //求当前结点的左孩子树的深度
int d2= depth（T—〉rchild）； //求当前结点的右孩子树的深度
return （d1〉d2?d1：d2）+1；
}
注意：根据二叉树的结构特点,很多算法都可以用递归算法来实现。 面试题 24： 编码实现直接插入排序
直接插入排序编程实现如下：
#include<iostream。h>
void main( void )
｛
int ARRAY［10] = ｛ 0， 6， 3， 2, 7， 5, 4， 9, 1, 8 ｝;
int i,j；
for( i = 0； i < 10； i++)
｛
cout〈<ARRAY［i］〈〈" ”;
｝
cout<<endl；
for（ i = 2; i <= 10； i++ ) //将 ARRAY[2],…,ARRAY[n］依次按序插入
{
if(ARRAY［i] 〈 ARRAY[i—1]) //如果 ARRAY[i]大于一切有序的数值，
//ARRAY［i］将保持原位不动
｛
ARRAY［0］ = ARRAY［i］； //将 ARRAY[0]看做是哨兵，是 ARRAY［i]的副本
j = i — 1;
do｛ //从右向左在有序区 ARRAY［1．． i—1］中
//查找 ARRAY［i]的插入位置
ARRAY［j+1］ = ARRAY[j］; //将数值大于 ARRAY［i］记录后移
j—— ;
｝while（ ARRAY［0] 〈 ARRAY[j］ );
ARRAY［j+1]=ARRAY［0]； //ARRAY［i］插入到正确的位置上
}
｝
for( i = 0; i 〈 10; i++)
｛
cout<〈ARRAY[i］〈<” ”；
｝
cout〈<endl；
}
12
注意： 所有为简化边界条件而引入的附加结点（ 元素） 均可称为哨兵。引入哨兵后使得查找循环条
件的时间大约减少了一半， 对于记录数较大的文件节约的时间就相当可观。类似于排序这样使用频率非
常高的算法，要尽可能地减少其运行时间.所以不能把上述算法中的哨兵视为雕虫小技. 面试题 25： 编码实现冒泡排序
冒泡排序编程实现如下:
＃include <stdio。h>
＃define LEN 10 //数组长度
void main（ void )
｛
int ARRAY[10] = ｛ 0, 6， 3, 2， 7, 5, 4， 9, 1， 8 ｝； //待排序数组
printf（ ”\n” )；
for（ int a = 0; a < LEN； a++ ) //打印数组内容
{
printf( ”%d "， ARRAY[a］ ）；
}
int i = 0；
int j = 0;
bool isChange; //设定交换标志
for（ i = 1; i 〈 LEN; i++ ）
{ //最多做 LEN-1 趟排序
isChange = 0; //本趟排序开始前,交换标志应为假
for( j = LEN-1； j >= i; j—- ） //对当前无序区 ARRAY[i.。LEN]自下向上扫描
｛
if（ ARRAY［j+1] < ARRAY［j］ )
{ //交换记录
ARRAY［0] = ARRAY［j+1]； //ARRAY[0]不是哨兵，仅做暂存单元
ARRAY[j+1］ = ARRAY［j］;
ARRAY［j］ = ARRAY[0］；
isChange = 1； //发生了交换,故将交换标志置为真
}
｝
printf( "\n" )；
for( a = 0; a 〈 LEN; a++） //打印本次排序后数组内容
{
printf( "%d "， ARRAY［a］ )；
｝
if（ ！isChange ) //本趟排序未发生交换，提前终止算法
{
break；
｝
｝
printf( ”\n” ）；
return；
}
13 面试题 26: 编码实现直接选择排序
#include”stdio.h"
#define LEN 9
void main( void )
｛
int ARRAY［LEN]=｛ 5， 6， 8， 2, 4, 1， 9， 3， 7 ｝; //待序数组
printf（"Before sorted:\n");
for（ int m = 0； m < LEN； m++ ) //打印排序前数组
{
printf（ ”％d ", ARRAY［m] );
｝
for (int i = 1; i <= LEN — 1； i++） //选择排序
{
int t = i - 1；
int temp = 0；
for (int j = i; j 〈 LEN; j++）
｛
if (ARRAY[j］ < ARRAY[t]）
{
t = j；
｝
}
if (t != (i — 1））
｛
temp = ARRAY[i - 1];
ARRAY［i — 1] = ARRAY[t］;
ARRAY［t］ = temp；
｝
}
printf( "\n" );
printf(”After sorted:\n”）；
for（ i = 0; i 〈 LEN； i++ ) //打印排序后数组
｛
printf( ”％d ”， ARRAY［i] );
}
printf( "\n" );
｝
注意:在直接选择排序中，具有相同关键码的对象可能会颠倒次序，因而直接选择排序算法是一种
不稳定的排序方法。在本例中只是例举了简单的整形数组排序，肯定不会有什么问题.但是在复杂的数
据元素序列组合中，只是根据单一的某一个关键值排序，直接选择排序则不保证其稳定性，这是直接选
择排序的一个弱点。 面试题 27： 编程实现堆排序
堆排序编程实现:
#include <stdio。h〉
14
void 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 ］ < ARRAY［ mPoint ]） //堆被破坏，需要重新调整
{
int tmpData= ARRAY［ sPoint ］; //交换 sPoint 与 mPoint 的数据
ARRAY[ sPoint ］ = ARRAY［ mPoint ];
ARRAY[ mPoint ］ = tmpData；
sPoint = mPoint ；
｝
else
{
break； //堆未破坏，不再需要调整
}
｝
return;
｝
void heepSort( int ARRAY［］， int Len ) //堆排序
｛
int i=0；
for ( i = （ Len / 2 - 1 )； i >= 0； i-- ） //将 Hr［0， Lenght—1]建成大根堆
｛
createHeep（ARRAY, i， Len);
}
for （ i = Len — 1； i > 0； i-— ）
{
int tmpData = ARRAY[0]； //与最后一个记录交换
ARRAY［0］ = ARRAY［i］；
ARRAY[i] = tmpData；
createHeep( ARRAY, 0， i ）； //将 H。r［0。。i]重新调整为大根堆
｝
return;
}
int main( void )
15
{
int ARRAY［] =｛ 5, 4， 7， 3， 9, 1， 6， 8, 2}；
printf（"Before sorted:\n"）； //打印排序前数组内容
for ( int i = 0； i 〈 9； i++ ）
｛
printf（”％d "， ARRAY［i]）;
}
printf（”\n");
heepSort( ARRAY， 9 )； //堆排序
printf（"After sorted:\n")； //打印排序后数组内容
for( i = 0； i 〈 9； i++ )
｛
printf( ”%d ”, ARRAY［i］ ）;
}
printf（ "\n” )；
return 0；
}
说明：堆排序,虽然实现复杂,但是非常的实用。另外读者可是自己设计实现小堆排序的算法。虽
然和大堆排序的实现过程相似,但是却可以加深对堆排序的记忆和理解。 面试题 28： 编程实现基数排序
#include <stdio。h〉
＃include 〈malloc.h〉
＃define LEN 8
typedef struct node //队列结点
｛
int data;
struct node * next;
｝node，*QueueNode;
typedef struct Queue //队列
{
QueueNode front；
QueueNode rear;
｝Queue，*QueueLink；
QueueLink CreateNullQueue( QueueLink ＆Q) //创建空队列
{
Q = NULL;
Q = ( QueueLink ）malloc( sizeof( Queue ） ）;
if( NULL == Q ）
{
printf(”Fail to malloc null queue!\n");
return NULL;
｝
16
Q—>front = （ QueueNode )malloc（ sizeof( node ) );
Q—〉rear = ( QueueNode ）malloc( sizeof（ node ) ）；
if（ NULL == Q-〉front || NULL == Q->rear )
{
printf（"Fail to malloc a new queue's fornt or rear!\n"）;
return NULL;
｝ Q
—〉rear = NULL;
Q—〉front—>next= Q->rear;
return Q;
｝
int lenData（ node data［］, int len) //计算队列中各结点的数据的最大位数
{
int m = 0;
int temp = 0;
int d；
for（ int i = 0； i 〈 len； i++）
{
d = data[i］.data;
while（ d 〉 0）
｛
d /= 10；
temp ++；
｝
if（ temp > m )
{
m = temp;
}
temp = 0；
}
return m；
}
QueueLink Push( QueueLink ＆Q , node node ） //将数据压入队列
｛
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 = p1—>next;
｝ p
-〉data = node。data；
p1—>next = p；
p—〉next = Q-〉rear;
17
return NULL;
}
node Pop( QueueLink ＆Q) //数据出队列
{
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 )
｛
return 0；
}
return 1；
｝
int main（ void )
{
int i = 0;
int Max = 0; //记录结点中数据的最大位数
int d = 10；
int power = 1；
int k = 0;
node Array［LEN］ ={｛450, NULL｝, ｛32,NULL｝, { 781,NULL｝, ｛ 57 ,NULL｝,组
{ 145,NULL}，｛ 613，NULL｝，｛ 401，NULL}，｛ 594,NULL}｝；
//队列结点数
QueueLink Queue［10];
for( i = 0； i 〈 10; i++)
｛
CreateNullQueue（ Queue[i])； //初始化队列数组
｝
for( i = 0； i 〈 LEN; i++）
{
printf(”％d "，Array［i].data）；
}
printf(”\n”);
Max = lenData（ Array, LEN ）； //计算数组中关键字的最大位数
printf("%d\n"，Max);
18
for(int j = 0; j < Max； j++） //按位排序
｛
if(j == 0） power = 1；
else power = power ＊d;
for(i = 0； i < LEN; i++)
{
k = Array[i］。data /power