暴风影音笔试总结-2013年

我用的迭代的方式，用一个栈来存储字符串，先将中序遍历入栈。然后对前序遍历的每个字符，与栈顶比较，若栈顶为长度为1的字符串，直接输出，这是后续的一个字符了。如果当前先序字符与栈顶相同，则看下一个前序字符。如果栈顶字符串长度不为1，则先出栈，然后用先序字符入栈，再用先序字符将刚出站的字符串分成两个字串，右子树入栈，左子树入栈。重复以上步骤直到先序字符串遍历完。然后将栈中剩余元素输出即得到后续遍历字符串。代码如下：

// 树的遍历.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Tree(char* str1, char* str2, char*& str3);
int _tmain(int argc, _TCHAR* argv[])
{
      char* str1="abdgcefh";
      char* str2="dgbaechf" ;
      char* str3 =NULL;
      Tree(str1,str2,str3);
      printf("%s\n",str3);
      return 0;
}

void Tree(char* str1, char* str2, char*& str3)
{

      char* m_stack[100];
      int top=0,index=0;
      char* str=NULL;
      str3 = (char*) malloc(strlen(str1));
      m_stack[top]=(char*) malloc(strlen(str1));
      strcpy(m_stack[top],str2);
      for(unsigned int i=0;i<strlen(str1);)
      {
      
            str = m_stack[top--];
            if(strlen(str)==1)
            {

                  str3[index++]=str[0];
                  if(str1[i] == str[0])
                  i++;
            }else
            {
                  int flag =0;
                  int j=0;
                  for(j=0;j<strlen(str);j++)
                  {
                        if(str[j] == str1[i])
                        {
                              flag=1;
                              break;
                        }
                  }
                  //先入栈
                  m_stack[++top]=(char*)malloc(2);
                  m_stack[top][0]=str1[i];
                  m_stack[top][1]='\0';
                  i++;
                  if(flag ==1)
                  {

            
                        if (j < strlen(str)-1)
                        {
                              m_stack[++top]=(char*) malloc(strlen(str)-j);
                              strcpy(m_stack[top],str+j+1);
                        }
                        if(j>0)
                        {
                              str[j]='\0';
                              m_stack[++top]=(char*) malloc(j);
                              strcpy(m_stack[top],str);
                        }
                  }
            }
      }
      while (top>-1)
      {
            str3[index++] = m_stack[top--][0];
      }
      str3[index]='\0';
}

还有一个题目是关于sizeof运算符的

void GetSize(char str[])
{
      void* p = malloc(15);
      printf("%d\n%d",sizeof(str),sizeof(p));
}


int _tmain(int argc, _TCHAR* argv[])
{
      //printf("sizeof(StructDef)=%d\n",sizeof(StructDef));
      char * str="hello.";
      //char temp[9]="hello.";
      GetSize(str);
      //printf("%d\n",sizeof(temp));
      return 0;
}

问输出是多少，这个地方我理解错误了，sizeof是编译时确定的！而不是运行时确定的，所以除了某个类实例之外，其他情况都是对变量类型的字节数的确定。

sizeof("hello.") 和题目中的值会不一样，因为字符串常量在编译时确定，而sizeof(str)实际上就是数组指针的字节数，这个题目的答案应该是4,4

今天看了一下阿里的面试题，其中问到hash_map和map的区别，以及实现方式。

区别就是一个存的是哈希之后的键和值，存储和访问等都是线性的。

hash_map是基于hash_table实现的，而map是基于红黑树实现的。