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

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(\9

return NULL; } S

->data = 0; //初始化新结点 S->next = NULL;

return S; }

栈的插入函数：

LinkStack Push( LinkStack &S, int data) {

if( NULL == S) //检验栈 {

printf(\return NULL; }

LinkStack p = NULL;

p = (LinkStack)malloc( sizeof( node ) ); //申请新结点 if( NULL == p) {

printf(\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(\return temp; }

temp = *S; 10

if( S->next == NULL ) {

printf(\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 ); //新结点入栈

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库C和C++经典面试题(面试必备)(4)在线全文阅读。