基本数据结构

数据结构是面试中常问的一个知识点，它是计算机中用于存储，操作数据的方式。常用的有线性表，树，图等。虽然我作为一个Java工程师对数据结构的使用着实不多，但这也是大学中学过的重要知识点，这里就在这总结以下，万一以后面试时被问到也可以扯一点。

线性表

线性表是是常用的数据结构之一，这里要介绍的是数组和链表。这两个是用的最多的线性结构，被广泛用于各种语言，如Java中的集合底层便是由数组和链表组成。

数组

在存储大量数据时数组时被用到最多的数据结构，对这个东西大家应该都比较熟悉，这里就不做赘述了。

链表

虽然数组已经很好地满足我们存储大量数据的要求，但是在某些情况下它显然不能是我们满意。比如，如果我们需要经常插入和删除表中的数据时，使用数组的话将非常耗时。同时，数组必须在内存中开辟一个连续的存储空间，对内存的利用率显然不高，这时候我们就可以使用链表。

链表优于数组的地方在于它可以将零散的内存空间利用起来，只要这块空间足以存储连标点额一个节点即可。如果把数组比作一根铁棒的话，那么链表就是链条，它的使用要比数组更加灵活，但是它也因此失去了数组随机存取的优点。

链表构建

链表（这里主要说单链表）有一个个节点组成，节点由数据域和指针域组成。数据域中存储的就是链表中需要存储的数据，指针域存储的是指向下一个节点的指针（如果是双向链表则还有一个指向前一个节点的指针）。

链表有两种样式，一种是所有的节点都是相同的结构，既存储数据也存储指针；但常用的是另一种的方式，即单独创建一个头节点，这个节点的数据域为空只有一个指向下一个节点的指针，这种方式的好处是便于在头结点处插入节点（即头插法,当然尾插法也是可以的）。

构建链表主要由两种方式：头插法和尾插法。头插法即是在头结点处插入节点，尾插法是在尾部插入节点。下面是链表构建的两种方式的伪代码。

节点结构

typedef struct LNode{
  ElemType data;
  struct *next;
}LNode,*LinkList;

头插法

void CreateList(LinkList &L,int n){
  //逆位序输入n个元素的值，建立带表头结点的单链表L
  L=（LinkList）malloc (sizeof (LNode));   //创建头结点
  L->next = Null;
  for(i=n,i>0;--i){
    p = (LinkList) malloc (sizeof (LNode));   //生成新节点
    scanf(&p->data);
    p->next = L->next;
    L->next = p;
  }
}

尾插法

void CreateList(LinkList &L,int n){
  //尾插法构建链表
  L=（LinkList）malloc (sizeof (LNode));   //创建头结点
  L->next = Null;
  r=L;
  for(i=n,i>0;--i){
    p = (LinkList) malloc (sizeof (LNode));   //生成新节点
    scanf(&p->data);
    r->next = p;
    r = p;
    r->next = Null;
  }
}

链表插入

int ListInsert(LinkList &L,int i,ElemType e){
  //在带头结点的单链表的第i个元素前插入元素
  p=L;
  j=0;
  while (p && j < i-1){
    p = p->next;
    ++j;
  }   //找到第i-1个节点
  if(!p || j >i-1){
    return 0;
  }
  s = (LinkList) malloc (sizeof (LNode));
  s->data = e;
  s-next = p->next;
  p->next = s;
  return 1;
}

链表删除

int ListInsert(LinkList &L,int i,ElemType e){
  //在带头结点的单链表中，删除第i个元素并由e返回其值
  p=L;
  j=0;
  while (p && j < i-1){
    p = p->next;
    ++j;
  }   //找到第i-1个节点
  if(!（p->next） || j >i-1){
    return 0;
  }
  s = p->next;
  p->next = s->next;
  e = s->data;
  return 1;
}

链表合并

void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc){
  //已知单链表La和Lb按值非递减排列，归并得到的单链表Lc也按值非递减排列
  pa = La->next;
  pb = Lb->next;
  Lc = pc = La;   //用La的头结点作为Lc的头结点
  while(pa && pb){
    if(pa->data <= pb->data){
      pc->next = pa;
      pc = pa;
      pa = pa->next;
    }
    else{
      pc->next = pb;
      pc = pb;
      pb = pb->next;
    }
  }
  pc->next = pa ? pa : pb;  //插入剩余段
  free(Lb);  //释放Lb的头结点
}

链表反转(该算法即是将一个原有的链表采用头插法的方式生成另一个链表)

void ReverseList(LinkList &L){

    p = L->next;             /*p为原链表的当前处理节点*/
    L->next = NULL;          /*逆置单链表初始为空*/

    while(p != NULL){        /*当原链表未处理完*/
        q = p->next;         /*q指针保留原链表当前处理节点的下一个节点*/
        p->next = L->next;   /*将当前处理节点p插入到逆置L的表头*/
        L->next = p;
        p = q;               /*p指向下一个待插入的节点*/
    }
}

树

树形结构是一种常用的非线性数据结构，其中以树和二叉树最为常用。下面介绍的就是二叉树的遍历与求深度，这两个是面试中最常用的问题。

树的遍历

先序遍历

void preOrder(BiTree T){
   if(T)
   {
     printf("%d",T->data);
     preOrder(T->lchild);
     preOrder(T->rchild);
   }
}

中序遍历

void preOrder(BiTree T){
   if(T)
   {
     preOrder(T->lchild);
     printf("%d",T->data);
     preOrder(T->rchild);
   }
}

后序遍历

void preOrder(BiTree T){
   if(T)
   {
     preOrder(T->lchild);
     preOrder(T->rchild);
     printf("%d",T->data);
   }
}

求树的深度

求二叉树的深度有递归和非递归两种方式，递归方式简单但是效率不高。

递归求解

int FindTreeDeep(BinTree BT){
     int deep=0;
     if(BT){
         int lchilddeep=FindTreeDeep(BT->lchild);
         int rchilddeep=FindTreeDeep(BT->rchild);
         deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
     }
     return deep;
}

非递归求解

int TreeDeep(BinTree BT ){
      int treedeep=0;
      stack S;
      stack tag;
      BinTree p=BT;
      while(p!=NULL&&!isEmpty(S)){
          while(p!=NULL){
              push(S,p);
              push(tag,0);
             p=p->lchild;
         }
         if(Top(tag)==1){
             deeptree=deeptree>S.length?deeptree:S.length;
             pop(S);
             pop(tag);
             p=NULL;
         }else{
             p=Top(S);
             p=p->rchild;
             pop(tag);
             push(tag,1);
         }
     }
     return deeptree;
 }

图

图是一种比线性表和树更复杂的数据结构，它的任意两个节点之间都可能相关联。它和树一样都有自己的专业术语，如顶点，边，弧等（这些专业术语和前面的树一样就不介绍了）。图既然如此复杂那么如何存储它呢？常用的有数组，邻接表，十字链表，邻接多重表等，这里也不一一介绍了，这里主要介绍一下图的遍历与最小生成树

图的遍历

深度优先搜索–递归

void DFS(MGraph G,int v)      //深度优先搜索
{
    int i;
    printf("%d ",v);          //访问结点v
    visited[v]=true;
    for(i=0;i<G.n;i++)       //访问与v相邻的未被访问过的结点
    {
        if(G.edges[v][i]!=0&&visited[i]==false)
        {
            DFS(G,i);
        }
    }
}

深度优先搜索–非递归

void DFS1(MGraph G,int v)   //非递归实现
{
    stack<int> s;
    printf("%d ",v);        //访问初始结点
    visited[v]=true;
    s.push(v);              //入栈
    while(!s.empty())
    {
        int i,j;
        i=s.top();          //取栈顶顶点
        for(j=0;j<G.n;j++)  //访问与顶点i相邻的顶点
        {
            if(G.edges[i][j]!=0&&visited[j]==false)
            {
                printf("%d ",j);     //访问
                visited[j]=true;
                s.push(j);           //访问完后入栈
                break;               //找到一个相邻未访问的顶点，访问之后则跳出循环
            }
        }
        if(j==G.n)                   //如果与i相邻的顶点都被访问过，则将顶点i出栈
            s.pop();
    }
}

广度优先搜索

void BFS(MGraph G,int v)      //广度优先搜索
{
    queue<int> Q;             //STL模板中的queue
    printf("%d ",v);
    visited[v]=true;
    Q.push(v);
    while(!Q.empty())
    {
        int i,j;
        i=Q.front();         //取队首顶点
        Q.pop();
        for(j=0;j<G.n;j++)   //广度遍历
        {
            if(G.edges[i][j]!=0&&visited[j]==false)
            {
                printf("%d ",j);
                visited[j]=true;
                Q.push(j);
            }
        }
    }
}

图的最小生成树

求图的最小生成树的算法著名的是普里姆算法（加点法）和克鲁斯卡尔算法（加边法，用于求边稀疏的图）。

普里姆算法（加点法）

克鲁斯卡尔算法（加边法）

总结

这里主要介绍的是基本数据结构中面试常会遇到的算法，而在这些数据结构本身的介绍并不全面，比如队列和栈就没介绍，树的完全二叉树，B树，红黑树和它的很多其他概念，还有图的连通性，最短路径等均没有介绍，读者如果对这些感兴趣可以在网上搜索或者查阅相关的书籍资料。