|
= 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 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< 12
注意：所有为简化边界条件而引入的附加结点（元素）均可称为哨兵。引入哨兵后使得查找循环条件的时间大约减少了一半，对于记录数较大的文件节约的时间就相当可观。类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技。
面试题25：编码实现冒泡排序
冒泡排序编程实现如下： #include #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
|