[关闭]
@qiezhian 2014-06-27T11:26:51.000000Z 字数 9121 阅读 1455

剑指offer——数据结构基础

算法

大多数面试题都是围绕数组、字符串、链表、树、栈、队列等几种最常见的数据结构展开的。因为高级数据结构实现复杂，很难在段时间内完全写出代码，而这些简单的数据结构是基础却可以解决很多复杂的问题，所以面试官更愿意考察这些基础结构。

数组

二维数组查找：在一个二维数组中，每一行按从左至右的递增顺序排序，每一列都按从上到下顺序递增排列。完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。
容易想到二分查找。但是从矩阵（二维数组）的右下角开始取点的话，需要分3种情况来分析查找的过程。这一题的创新思维在于要从矩阵边上取点，则每次只需分2种情况进行查找，也就实现了二分查找。

  1. #include <iostream>
  2. using namespace std;
  4. int FindinMatrix( int* m, int rows, int cols, int element );
  6. int main()
  7. {
  8.     int m[]=
  9.     {
  10.         1,2,3,4,
  11.         2,3,4,5,
  12.         3,4,5,6,
  13.         4,5,6,7,
  14.     };
  15.     int element = 8;
  16.     if( FindinMatrix( m ,4,4, element ) )
  17.         cout<< " search success, element " << element << " is in matrix !"<<endl;
  18.     else
  19.         cout<< " search failed, element " << element<< " is not in matrix !"<<endl;
  20.     return 0;
  21. }
  22. int FindinMatrix( int* matrix, int rows, int cols, int element )
  23. {
  24.     int col, row;
  25.     row = 0;
  26.     col = cols-1;
  27.     while( row <= rows-1 && col >= 0 )
  28.     {
  29.         if( matrix[row*cols+col] == element )
  30.             return 1;
  31.         else if( matrix[row*cols+col] >= element )
  32.             col--;
  33.         else 
  34.             row++;
  35.     }
  36.     return 0;
  37. }

字符串

字符串替换：实现一个函数，把字符串中的每个空格替换成"%20"。
将一个空格字符替换为"%20",会使得字符串变长，会覆盖后面的字符。因此需要从后往前替换，首先需要计算空格个数，以正确的计算替换后字符串长度。

  1. /*
  2. Filename: ReplaceString.c
  3. Function: replace the space ' ' with '%20' in string
  4. Details:
  5. */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  10. void ReplaceString( char *str, int length );
  12. int main()
  13. {
  14.     char str[30] = "I'm so happy!";
  15.     printf( "original string:%s\n ", str );
  16.     ReplaceString( str, 30 );
  17.     printf( "replaced string:%s\n", str );
  18.     return 0;
  19. }
  20. /* length 是str拥有的实际内存大小，单位字节 */ 
  21. void ReplaceString( char *str, int length )
  22. {
  23.     int original_length = strlen( str );
  24.     int new_length;
  25.     int i=0;
  26.     int j;
  27.     int space_num=0;
  28.     while( str[i] != '\0' )
  29.         if( str[i++]== ' ' )
  30.             space_num++;
  31.     new_length = 2*space_num + original_length;
  32.     if( new_length >= length )
  33.     {
  34.         printf("string's memory not enough!");
  35.         return;
  36.     }
  37.     i = original_length;
  38.     j = new_length;
  39.     while( i>=0 && j>=0 )
  40.         if( str[i]==' ' )
  41.         {
  42.             str[j--] = '0';
  43.             str[j--] = '2';
  44.             str[j--] = '%';
  45.             i--;
  46.         }
  47.         else
  48.         {
  49.             str[j--] = str[i--];
  50.         }
  51. }

链表

从尾到头打印链表：反序输出是典型的“后进先出”，容易想到递归和栈结构。用栈结构需要多Θ(N)的空间，正序遍历链表时将节点顺序压入栈中，然后从栈中依次弹出节点并打印，即为反序。用递归方法则是在打印本节点之前先打印下一个节点，代码简单清晰，但是对于链表过长时，递归调用时间过长且易因递归调用过多产生栈溢出。下面代码中stack结构定义stack.h在其他文中有完整实现。

  1. /*
  2. Filename: PrintListReversingly.cpp
  3. Function: print list reversingly
  4. Details:
  5. */
  6. #include <iostream>
  7. #include "stack.hpp"
  8. struct ListNode
  9. {
  10.     int mElement;
  11.     ListNode *pNext;
  12. };
  13. ListNode* BuildList( ListNode *list );
  14. void PrintListNormally( ListNode *list );
  15. void PrintListReversingly( ListNode *list );
  16. void PrintListReversingly2( ListNode *list );
  17. int main( )
  18. {
  19.     int i=0;
  20.     ListNode *list = NULL;
  21.     list = BuildList( list );
  22.     if( list==NULL )
  23.         return 0;
  24.     PrintListNormally( list );
  25.     PrintListReversingly( list );
  26.     PrintListReversingly2( list );
  27. }
  29. ListNode*  BuildList( ListNode *list )
  30. {
  31.     if( list==NULL )
  32.         list = new ListNode;
  33.     int i=0;
  34.     ListNode *head, *tmp;
  35.     head = list;
  36.     for( i=1; i<25; i++)
  37.     {
  38.         tmp = new ListNode;
  39.         if( tmp == NULL )
  40.             return NULL;
  41.         tmp->mElement = i;
  42.         head->pNext = tmp;
  43.         head = head->pNext;
  44.     }
  45.     return list;
  46. }
  47. void PrintListNormally( ListNode *list )
  48. {
  49.     cout<<"print list normally"<<endl;
  50.     ListNode *p = list;
  51.     while( p!= NULL )
  52.     {
  53.         cout<< p->mElement <<endl;
  54.         p = p->pNext;
  55.     }
  56. }
  57. void PrintListReversingly( ListNode *list )
  58. {
  59.     cout<<"Print List Reversingly Iteratively"<<endl;
  60.     if( list->pNext!=NULL )
  61.         PrintListReversingly( list->pNext );
  62.     cout<< list->mElement <<endl;
  63. }
  64. void PrintListReversingly2( ListNode *list )
  65. {
  66.     cout<<"Print List Reversingly using struct stack"<<endl;
  67.     MyStack<ListNode*> stack;
  68.     ListNode *p = list;
  69.     while( p!=NULL )
  70.     {
  71.         stack.Push( p );
  72.         p = p->pNext;
  73.     }
  74.     while( !stack.IsEmpty() )
  75.         cout<< stack.Pop()->mElement <<endl;
  76. }

树

树的操作涉及大量的指针，因此与树有关的面试题都不太容易，而树中常考的莫过于二叉树，这是重中之重。
重建二叉树：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中不含重复数字。
在二叉树前序遍历中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值正好处于序列的中间，其左边为左子树的值集合，其右边为右子树的值集合。因此重建二叉树步骤为：先重建根节点，再重建根节点的左儿子，再重建根节点的右儿子。程序为递归实现。

  1. /*
  2. Filename: ReconstructBinTree.cpp
  3. Function: 给出某二叉树的前序及中序遍历结果，重建该二叉树
  4. Details:
  5. */
  6. #include <iostream>
  7. using namespace std;
  8. struct BinTreeNode
  9. {
  10.     int m_Element;
  11.     BinTreeNode* m_pLeft;
  12.     BinTreeNode* m_pRight;
  13. };
  14. void PrintTreePreOrderly( BinTreeNode* root );
  15. void PrintTreeMidOrderly( BinTreeNode* root );
  16. BinTreeNode* Reconstruct( int* pre, int* mid, int length );
  17. BinTreeNode* ReconstructCore( int* pre, int* mid, int pre_start,
  18.         int pre_end, int mid_start, int mid_end);
  19. int FindIndex( int *a, int start, int length, int element );
  20. int main( )
  21. {
  22.     int Pre[]={1,2,4,7,3,5,6,8};
  23.     int Mid[]={4,7,2,1,5,3,8,6};
  24.     int size = sizeof( Pre )/sizeof( int );
  25.     int i;
  26.     cout<<"Tree preorderly print: " << endl;
  27.     for( i=0; i<size; i++ )
  28.         cout<< Pre[i];
  29.     cout<<endl;
  30.     cout<<"Tree midorderly print: " << endl;
  31.     for( i=0; i<size; i++ )
  32.         cout<< Mid[i];
  33.     cout<<endl;
  34.     BinTreeNode* root = Reconstruct( Pre, Mid, size );
  35.     if( root==NULL )
  36.         cout<<" Reconstruct failed!"<< endl;
  37.     cout<<"Reconstructed tree preorderly print: " << endl;
  38.     PrintTreePreOrderly( root );
  39.     cout<<" Reconstructed tree midorderly print: " << endl;
  40.     PrintTreeMidOrderly( root );
  41.     return 0;
  42. }
  44. BinTreeNode* Reconstruct( int* pre, int* mid, int length )
  45. {
  46.     return ReconstructCore( pre, mid, 0, length-1, 0, length-1 );
  47. }
  48. BinTreeNode* ReconstructCore( int* pre, int* mid, int pre_start, 
  49.         int pre_end, int mid_start, int mid_end)
  50. {
  51.     if( pre_end - pre_start != mid_end - mid_start 
  52.             || pre_end < pre_start || mid_end < mid_start )
  53.         return NULL;
  54.     BinTreeNode* node = NULL ;
  55.     node = new BinTreeNode;
  56.     node->m_Element = pre[pre_start];
  57.     if( pre_end > pre_start )
  58.     {
  59.         int index = FindIndex( mid , mid_start, 
  60.                 mid_end-mid_start+1, pre[pre_start] );
  61.         if( index!= -1 )
  62.         {
  63.             node->m_pLeft = ReconstructCore( pre, 
  64.                 mid,pre_start+1,pre_start+index,
  65.                 mid_start, mid_start+index-1 );
  66.             node->m_pRight = ReconstructCore( pre, 
  67.                 mid, pre_start+index+1, pre_end, 
  68.                 mid_start+index+1, mid_end );
  69.         }
  70.     }
  71.     return node;
  72. }
  74. int FindIndex( int* a, int start,  int length, int element )
  75. {
  76.     if( a==NULL || length<=0 )
  77.         return -1;
  78.     int i=start;
  79.     for( ; i<start+length; i++)
  80.         if( element == a[i] )
  81.             return ( i-start );
  82.     return -1;
  83. }
  85. void PrintTreePreOrderly( BinTreeNode *root )
  86. {
  87.     if( !root )
  88.         return;
  89.     cout<< root->m_Element << endl;
  90.     PrintTreePreOrderly( root->m_pLeft );
  91.     PrintTreePreOrderly( root->m_pRight );
  92. }
  94. void PrintTreeMidOrderly( BinTreeNode *root )
  95. {
  96.     if( !root )
  97.         return;
  98.     PrintTreeMidOrderly( root->m_pLeft );
  99.     cout<< root->m_Element << endl;
  100.     PrintTreeMidOrderly( root->m_pRight );
  101. }

栈

用两个栈实现队列

队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
栈的特点是“先进后出”，在计算机领域被广泛应用，而队列是“先进先出”，二者针锋相对，但却互相联系。

  1. /*
  2. Filename: CQueue.hpp
  3. Function: implement simple version of struct "queue" using two "stack"s.
  4. Details: please check IsEmpty() function before call deleteHead() function
  5. */
  6. #include <iostream>
  7. #include "stack.hpp"
  8. using namespace std;
  10. template<typename T> 
  11. class CQueue
  12. {
  13. public:
  14.     CQueue();
  15.     ~CQueue();
  17.     void appendTail( const T& node );
  18.     T deleteHead( );
  19.     bool IsEmpty( );
  21. private:
  22.     MyStack<T> stack_in;
  23.     MyStack<T> stack_out;
  24. };
  25. template<typename T>
  26. CQueue<T>::CQueue( )
  27. {
  28. }
  29. template<typename T>
  30. CQueue<T>::~CQueue( )
  31. {
  32. }
  33. template<typename T>
  34. bool CQueue<T>::IsEmpty( )
  35. {
  36.     return ( stack_in.IsEmpty() && stack_out.IsEmpty() );
  37. }
  38. template<typename T>
  39. void CQueue<T>::appendTail( const T& node )
  40. {
  41.     stack_in.Push( node );
  42. }
  43. template<typename T>
  44. T CQueue<T>::deleteHead( )
  45. {
  46.     if( stack_out.IsEmpty() )
  47.         while( !stack_in.IsEmpty() )
  48.             stack_out.Push( stack_in.Pop() );
  49.     return stack_out.Pop();
  50. }

包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素min函数。在该栈中，调用min、push、pop等函数的时间复杂度均为Θ(1)。
分析： 光用一个成员变量来记录最小元素是不够的，当最小元素弹出时，下一个最小元素是多少？要找出其最小元素就不可能在Θ(1)时间办到。只能用空间换取时间效率。添加一个辅助栈，每当push一个元素，辅助栈均push此时最小元素，每pop一个元素，辅助栈也pop一个元素即可。

  1. /*
  2. Filename: StackWithMin.hpp
  3. Function: implement a version of "stack" with min() function in O(1) time
  4. Details: 
  5. */
  6. #include "stack.hpp"
  8. template<typename T>
  9. class StackWithMin
  10. {
  11. public:
  12.     StackWithMin();
  13.     ~StackWithMin();
  15.     void Push( const T& node );
  16.     T Pop( );
  17.     bool IsEmpty();
  18.     T Min();
  19. private:
  20.     MyStack<T> stack_data;
  21.     MyStack<T> stack_min;
  22. };
  24. template<typename T>
  25. StackWithMin<T>::StackWithMin()
  26. {
  27. }
  28. template<typename T>
  29. StackWithMin<T>::~StackWithMin()
  30. {
  31. }
  32. template<typename T>
  33. void StackWithMin<T>::Push( const T& node )
  34. {
  35.     if( stack_min.IsEmpty() )
  36.         stack_min.Push( node );
  37.     else
  38.     {
  39.         if( node > stack_min.Top() )
  40.             stack_min.Push( stack_min.Top() );
  41.         else
  42.             stack_min.Push( node );
  43.     }
  44.     stack_data.Push( node );
  45. }
  46. template<typename T>
  47. T StackWithMin<T>::Pop( )
  48. {
  49.     stack_min.Pop();
  50.     return stack_data.Pop();
  51. }
  52. template<typename T>
  53. T StackWithMin<T>::Min()
  54. {
  55.     return stack_min.Top();
  56. }
  57. template<typename T>
  58. bool StackWithMin<T>::IsEmpty()
  59. {
  60.     return ( stack_data.IsEmpty() );
  61. }

栈的压入、弹出序列分析

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是一个合法的弹出序列，但是序列4、3、5、1、2就不可能是该栈的弹出序列。
分析： 比较直观的思路是用栈来模拟压入弹出过程。假设压入序列为I，弹出序列为O，i和j分别是I和O的索引。则按一下三步走：
1.如果I[i]==O[j]，则说明此元素入栈后直接又出栈，直接略过，i++;j++;
2.否则将O[j]和栈顶元素比较，相等说明此元素此时需弹出，则j++且栈弹出一个元素；不相等则栈压入I[i++];
3.最后判断栈是否为空，不为空则说明该弹出序列不合法。

  1. #include <iostream>
  2. #include "stack.hpp"
  3. using namespace std;
  5. bool IsPopOrder( int* push_order, int* pop_order, int length );
  7. int main( )
  8. {
  9.     int push_order[]={ 2,4,6,8,10,9,7,5,3,1 };
  10.     int pop_order[]={ 6,4,2,9,10,8,3,7,1,5 };
  11.     int size = sizeof( push_order )/sizeof( int );
  12.     if( IsPopOrder( push_order, pop_order, size ) )
  13.         cout<< "pop order is right!"<<endl;
  14.     else
  15.         cout<< "pop order is wrong!"<<endl;
  16.     return 0;
  17. }
  19. bool IsPopOrder( int* push_order, int* pop_order, int length )
  20. {
  21.     if( push_order==NULL || pop_order==NULL || length<=0 )
  22.         return false;
  23.     MyStack<int> mystack;
  24.     int i=0, j=0;
  25.     while( i<length && j<length )
  26.     {
  27.         if( push_order[i] == pop_order[j] )
  28.         {
  29.             i++; j++;
  30.         }
  31.         else
  32.         {
  33.             if( !mystack.IsEmpty() && pop_order[j] == mystack.Top() )
  34.             {
  35.                 j++;
  36.                 mystack.Pop();
  37.             }
  38.             else
  39.             {
  40.                 mystack.Push( push_order[i++] );
  41.             }
  42.         }
  43.     }
  44.     while( !mystack.IsEmpty() && mystack.Top() == pop_order[j] )
  45.     {
  46.         mystack.Pop(); j++;
  47.     }
  48.     return ( mystack.IsEmpty() );
  49. }

队列

从上往下打印二叉树（层序遍历）

题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到又的顺序打印。
分析：这是树的一种遍历方法，称为层序遍历。本题看似考查树的知识，实际上用的却是优先队列结构。方法如下：从队列头部取出最早进入队列的结点（根结点），当每一次打印一个结点的时候，如果该结点有子结点，则把子结点放入队列的末尾，并弹出打印过的结点，再取下一个结点进行打印。重复前面的动作，直至队列中所有的结点都被打印出来为止。

  1. template<typename T>
  2. void PrintTreeHierarchically( BinTreeNode<T>* root )
  3. {
  4.     if( root==NULL )
  5.         return;
  6.     CQueue<BinTreeNode<T>*>  queue;
  7.     BinTreeNode<T>* pTree = root;
  8.     queue.Push( pTree );
  9.     while( !queue.IsEmpty() )
  10.     {
  11.         pTree = queue.Pop();
  12.         cout<< pTree->m_nElement <<endl;
  13.         if( pTree->m_pLeft != NULL )
  14.             queue.Push( pTree->m_pLeft );
  15.         if( pTree->m_pRight != NULL )
  16.             queue.Push( pTree->m_pRight );
  17.     }
  18. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注