程序员面试闯关（二）：数据结构考点与细节分析

2016-08-24 本文已影响469人 androidjp

上一篇文章程序员面试闯关（一）：字符串匹配+排序+查找列举说明了各种常见的排序算法等算法基础，这里，主要分析下数据结构相关的基础和注意点。

一、线性表

1. 数组（顺序存储结构）

效率分析

查找：O(1)【数组的存储是连续内存空间】
插入和删除：
- 最好情况：O(1)
  ①插入到最后一个位置 ②删除最后一个元素
- 最坏情况：O(n)
  ①插入到第一个位置 ②删除第一个元素
- 平均情况：O((n-1)/2) = O(n)

整体分析：
- 适合：存数据，取数据【无须为了表示表中元素之间的逻辑关系而增加额外的存储空间，可以快速地存取表中任一位置的元素】
- 不适合：插入和删除数据【需要频繁移动元素】

2. 链表（链式存储结构）

头指针与头结点的异同：

头指针：
- 是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
- 头指针具有标识作用，所以常用它来冠以链表的名字
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
头结点：
- 头结点是为了操作的统一和方便而设定的，放在第一个元素的结点之前，其数据域一般无意义（一般用于存放链表的长度）
- 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一。
- 头结点不一定是链表的必要元素。

效率分析

查找：O(n)
插入和删除：O(1)

优势：

相比于数组：数组需要预先分配存储空间，容易造成空间浪费和溢出。而单链表不需要分配空间，元素个数也不受限制。

细分

单链表：就是上述这种，内存空间分配不连续。
静态链表：【就是为了给没有指针的语言设计的方案
】用数组去模拟链表，内存空间。具体实现：设计一个结构体，创建一个结构体数组，这个数组很长，足够你用了，然后，用两个结构体实例，一个作为数组头，一个作为数组尾，用于说明实际的数组长度：
```
typedef struct{
  ElemType data;
  int cur; //表示下一个元素的下标（一般会指向它下一个位置，如果是末尾，则指向‘0’）
}
```
- 优点：要插入或删除元素，只需要先在数组末尾添加这个元素，然后，修改这个元素的cur和插入点元素的cur即可。避免了元素移位的复杂过程。
- 缺点：表长度难以确定的问题；失去了数组的随机存取快的特性。
循环链表
双向链表

二、栈和队列

1. 栈

概念：栈是限定仅在表尾进行插入和删除操作的线性表。

结构：

顺序结构（一个栈）：

typedef struct{
  int data[MAXSIZE];
  int top;   //表示栈顶下标（-1表示：栈空）
}Stack

顺序结构（两个栈共享空间）：

typedef struct{
  int data[MAXSIZE];
  int topA;   //表示栈A的栈顶下标（-1表示：栈空）
  int topB;   //表示栈B的栈顶下标（MAXSIZE 表示：栈空）
}DoubleStack

链式结构：

typedef struct StackNode{///栈元素
  int data;
  struct StackNode *next; 
}StackNode , *LinkStackPtr;

typedef struct LinkStack{//链栈
  LinkStackPtr top;///指向栈顶的指针
  int count;//栈大小（0表示：空栈）
}LinkStack;

2. 队列

概念：队列是只允许一端进行插入操作，另一端进行删除操作的线性表。

循环队列：

目的：为了解决存储空间的循环利用的问题。

性质：

队列满的条件是：(rear+1)%QueueSize == front 【其中‘rear’表示队尾，‘font’表示队头】
结构如下：

typedef struct{
  int data[MAXSIZE];
  int front;  //头指针（初始化为：0）
  int rear;  //尾指针（初始化为：0，队列不空，就指向队列最后一个元素的下一个位置）
}

操作：

入队：

Q->rear = (Q->rear + 1)%MAXSIZE;

出队：

Q->front = (Q->front + 1)%MAXSIZE;

链队列：

结构：

typedef struct QNode{
  int data;
  struct QNode *next;
}QNode , *QueuePtr;

typedef struct{
  QueuePtr front, rear; /*队头，队尾指针*/
}

三、树

1. 各种概念重温

结点层次（Level）：根为第一层，根的孩子为第二层。
其双亲在同一层的结点互为堂兄弟。
森林：m（m>=0）课互不相交的树的集合。

2. 一般树的存储结构

双亲表示法【缺点：找父亲O(1),找孩子O(n)】
其实是对象数组（包含其父结点的下标）

typedef struct PTNode{
  int data;
  int parent;//父结点的下标，‘-1’表示没有父结点，本身是根结点
}
typedef struct{
  PTNode nodes[100];  //结点数组
  int r, n;  //根位置 ， 结点数
}

孩子表示法【缺点：①找父亲O(n),找孩子O(1) ②要加孩子，结构需要改，遍历更加复杂】
其实是将n个结点用一个长度为n的结点数组装起来，每个结点的子结点用一条属于这个结点的单链表来表示，如果是叶子结点，那么则没有子链表，它的firstchild为null。
```
typedef struct CTNode{  ///孩子结点
  int child;
  struct CTNode *next;
} *ChildPtr;
typedef struct{    ////表头结构
  int data;
  ChildPtr firstchild;
} CTBox;
typedef struct{   /////树结构
  CTBox nodes[100]; //结点数组
  int r,n;  ///根位置和结点数
}
```
孩子兄弟表示法【缺点，还是难找到父结点，如果要改，需要加多一个指针】
一个结构体，两个指针（一个纵向，一个横向），相当于他的“长子”和“二弟”。
```
typedef struct CSNode{
  int data;
  struct CSNode *firstChild;///它的第一个孩子结点
  struct CSNode *rightChild;///它本身的兄弟结点
}
```

3. 二叉树

相关概念：
- 斜树：所有结点都在左子树称为左斜树；所有结点都在右子树称为右斜树。
- 完全二叉树的特点：
  1. 叶子结点只能在最下两层。
  2. 最下层叶子一定集中在左部连续位置。
  3. 如果结点度数为1，此结点必定只有左子树。
  4. 同样结点数的二叉树，完全二叉树的深度最小。
- 二叉树的性质：
  1. 在二叉树的第i层上至多有2^(i-1)个结点
  2. 深度为k的二叉树至多有2^k -1个结点
  3. 任意一颗二叉树，n2（度数为2的结点） = n0（度数为0的结点）-1
  4. 树的边数（也叫：分支线总数）和结点数的关系：边数 = n-1 = n1+2*n2
  5. 具有n个结点的完全二叉树的深度为
    表示：不大于logn的最大整数+1
  6. 如果放在一个数组中，那么，父子结点之间的下标关系如下：
二叉树相关操作
线索二叉树
- 定义：因为二叉链表只能知道某个结点的左右孩子结点的地址，而不知道它在遍历时的一个‘前驱’和‘后继’结点是谁。于是，将原来的结点结构中的左右孩子成员，在判断为null的情况下，变为这个结点的前驱和后继结点。这样，一来充分利用了空间，二来方便了我们查找某个结点的前驱和后继结点。
- 结构：
```
typedef enum {LInk , Thread} PointerTag; //Link == 0 表示指向左右孩子，Thread==1 表示指向前驱和后继结点
typedef struct BiThrNode{
  int data; //数据
  struct BiThrNode *lchild , *rchild;//左右孩子指针（或者前驱后继结点）
  PointerTag LTag;  //左标志
  PointerTag RTag;  //右标志
} BiThrNode, *BiThrTree;
```
- 中序遍历示例
- 意义
  如果实际中所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是不错选择。
二叉树、数、森林之间的转换
1. 树转二叉树：
2. 森林转二叉树：
3. 二叉树转树：
4. 二叉树转森林：
哈夫曼树
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。【带权路径长度WPL最小的二叉树，称作赫夫曼树】

四、图

1. 定义：G(V【顶点集合】, E【边的集合】)

2. 相关概念

完全图：任意两个点之间有边的图
简单图：无重复的边或顶点到自身的边
度：顶点的边数

3. 图的存储结构

邻接矩阵
- 存储方式：用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中的边或弧的信息。
- 优势：
  1. 容易判断两个顶点是否有边
  2. 要知道某个顶点的度，其实就是这个顶点vi 在邻接矩阵中的第i行（或第i列）的元素之和。
  3. 求顶点vi的所有邻接点，只需要遍历矩阵第i行。
- 图解（无向连通图为例）：
邻接表
- 存储方式：用两个对象结构，一个来表示顶点，另一个则表示该顶点的邻接顶点权值信息。每个顶点对象，都是一个链表的表头结点，他后面接着的是他的所有邻接顶点的信息列表。如下图，表示每一个顶点的链表结构模型。
  
  每一个顶点的邻接表

邻接矩阵和邻接表的比较：

当图中结点数目较小且边较多时，采用邻接矩阵效率更高。
当节点数目远大且边的数目远小于相同结点的完全图的边数时，采用邻接表存储结构更有效率。

五、二叉树和图的各个常考方法代码汇总（代码可直接复制运行）

1. 二叉树各个方法

package basic.tree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * 二叉树
 * Created by androidjp on 16/8/17.
 */
public class BiTree {
    public String data;
    public BiTree left;
    public BiTree right;

    public static Scanner scanner = new Scanner(System.in);

    /**
     * 以 先序遍历 的顺序进行元素插入
     *
     * @return 创建好的二叉树
     */
    public static BiTree createTree() {
        String s = scanner.next();
        char ch = s.charAt(0);
        if (ch == '#') {
            return null;
        }
        BiTree root = new BiTree();
        root.data = s;
        root.left = null;
        root.right = null;

        //递归进行插入
        root.left = createTree();
        root.right = createTree();

        return root;
    }

    /**
     * 先序遍历二叉树
     *
     * @param tree
     */
    public static void preTraverse(BiTree tree) {
        if (tree == null)
            return;
        System.out.print(tree.data + " ");
        preTraverse(tree.left);
        preTraverse(tree.right);

    }

    /**
     * 中序遍历二叉树
     *
     * @param tree
     */
    public static void orderTraverse(BiTree tree) {
        if (tree == null)
            return;
        orderTraverse(tree.left);
        System.out.print(tree.data +" ");
        orderTraverse(tree.right);

    }

    /**
     * 后序遍历二叉树
     *
     * @param tree
     */
    public static void postTraverse(BiTree tree) {
        if (tree == null)
            return;
        postTraverse(tree.left);
        postTraverse(tree.right);
        System.out.print(tree.data + " ");
    }

    /**
     * 二叉树的深度优先遍历
     * 【二叉树不同于图,图需要标记元素是否已经被遍历过,因为可能存在环,而树则不用考虑环的问题,于是少了判断这一步】
     * 使用栈 遍历
     *
     * @param tree
     */
    public static void depthFirstTraverse(BiTree tree) {
        Stack<BiTree> stack = new Stack<>();
        stack.push(tree);
        while (!stack.empty()) {
            tree = stack.peek();
            System.out.print(tree.data + " ");
            stack.pop();
            //注意 元素入栈先后顺序: right -> left
            if (tree.right!= null){
                stack.push(tree.right);
            }
            if (tree.left != null) {
                stack.push(tree.left);
            }
        }
    }

    /**
     * 广度优先遍历(也称为:层次遍历)
     * 利用队列
     * @param tree
     */
    public static void breadFirstTraverse(BiTree tree){
        Queue<BiTree> queue = new ArrayDeque<>();
        queue.add(tree);
        while(!queue.isEmpty()){
            tree = queue.poll();
            System.out.print(tree.data + " ");
            if (tree.left!=null){
                queue.add(tree.left);
            }
            if (tree.right!=null){
                queue.add(tree.right);
            }
        }
    }


    public static void main(String[] args) {
        BiTree tree = new BiTree();
        ///(根节点 -> 左孩子 -> 右孩子)创建二叉树,如输入: 1 2a 3a # 4b # # 3b # # 2b # #
        tree = createTree();
        BiTree ptr = tree;

        //先序遍历
        preTraverse(ptr);
        System.out.println();

        //中序遍历
        ptr = tree;
        orderTraverse(ptr);
        System.out.println();

        //后序遍历
        ptr = tree;
        postTraverse(ptr);
        System.out.println();

        //深度优先遍历
        ptr = tree;
        depthFirstTraverse(ptr);
        System.out.println();

        //广度优先遍历
        ptr = tree;
        breadFirstTraverse(ptr);
        System.out.println();
    }
}

2. 图的广度和深度优先比遍历（邻接矩阵表示权值）

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 使用邻接矩阵来表示'边'的图结构
 * Created by androidjp on 16/9/8.
 */
public class MyGraph<V> {
    private ArrayList<V> vertexList;//点集合
    private int[][] edges; //邻接矩阵表示的边集合
    private int numOfEdges; //边数

    public MyGraph(int num){
        vertexList  = new ArrayList(num);
        edges = new int[num][num];
        numOfEdges = 0;
    }

    ///边数
    public int getNumOfEdges(){
        return this.numOfEdges;
    }

    ///结点数
    public int getNumOfVertex(){
        return this.vertexList.size();
    }

    //获取第i个结点
    public V getVertex(int i){
        return this.vertexList.get(i);
    }

    //获取i、j两个结点之间的权值
    public int getWeight(int i, int j){
        return this.edges[i][j];
    }

    //插入结点
    public void insertVertex(V vertex) {
        vertexList.add(vertexList.size(),vertex);
    }

    //插入结点
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2]=weight;
        numOfEdges++;
    }

    //删除结点
    public void deleteEdge(int v1,int v2) {
        edges[v1][v2]=0;
        numOfEdges--;
    }

    //得到第一个邻接结点的下标
    public int getFirstNeighbor(int index) {
        for(int j=0;j<vertexList.size();j++) {
            if (edges[index][j]>0) {
                return j;
            }
        }
        return -1;
    }

    //根据前一个邻接结点的下标来取得下一个邻接结点
    public int getNextNeighbor(int v1,int v2) {
        for (int j=v2+1;j<vertexList.size();j++) {
            if (edges[v1][j]>0) {
                return j;
            }
        }
        return -1;
    }

    //私有函数，深度优先遍历
    private void depthFirstSearch(boolean[] isVisited,int  i) {
        //首先访问该结点，在控制台打印出来
        System.out.print(getVertex(i)+"  ");
        //置该结点为已访问
        isVisited[i]=true;

        int w=getFirstNeighbor(i);
        while (w!=-1) {
            if (!isVisited[w]) {
                depthFirstSearch(isVisited,w);
            }
            w=getNextNeighbor(i, w);
        }
    }

    //对外公开函数，深度优先遍历，与其同名私有函数属于方法重载
    public void depthFirstSearch() {
        boolean[] isVisited = new boolean[getNumOfVertex()];
        for(int i=0;i<isVisited.length;i++)
            isVisited[i] = false;

        for(int i=0;i<getNumOfVertex();i++) {
            //因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。
            if (!isVisited[i]) {
                depthFirstSearch(isVisited,i);
            }
        }
    }

    //私有函数，广度优先遍历
    private void broadFirstSearch(boolean[] isVisited,int i) {
        int u,w;
        LinkedList queue=new LinkedList();

        //访问结点i
        System.out.print(getVertex(i)+"  ");
        isVisited[i]=true;
        //结点入队列
        queue.addLast(i);
        while (!queue.isEmpty()) {
            u=((Integer)queue.removeFirst()).intValue();
            w=getFirstNeighbor(u);
            while(w!=-1) {
                if(!isVisited[w]) {
                    //访问该结点
                    System.out.print(getVertex(w)+"  ");
                    //标记已被访问
                    isVisited[w]=true;
                    //入队列
                    queue.addLast(w);
                }
                //寻找下一个邻接结点
                w=getNextNeighbor(u, w);
            }
        }
    }

    //对外公开函数，广度优先遍历
    public void broadFirstSearch() {
        boolean[] isVisited = new boolean[getNumOfVertex()];
        for(int i=0;i<isVisited.length;i++)
            isVisited[i] = false;
        for(int i=0;i<getNumOfVertex();i++) {
            if(!isVisited[i]) {
                broadFirstSearch(isVisited, i);
            }
        }
    }



    public static void main(String args[]) {
        int n = 8, e = 9;//分别代表结点个数和边的数目
        String labels[] = {"1", "2", "3", "4", "5", "6", "7", "8"};//结点的标识
        MyGraph<String> graph = new MyGraph<String>(n);
        for (String label : labels) {
            graph.insertVertex(label);//插入结点
        }
        //插入九条边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);
        graph.insertEdge(1, 0, 1);
        graph.insertEdge(2, 0, 1);
        graph.insertEdge(3, 1, 1);
        graph.insertEdge(4, 1, 1);
        graph.insertEdge(7, 3, 1);
        graph.insertEdge(7, 4, 1);
        graph.insertEdge(6, 2, 1);
        graph.insertEdge(5, 2, 1);
        graph.insertEdge(6, 5, 1);

        System.out.println("深度优先搜索序列为：");
        graph.depthFirstSearch();
        System.out.println();
        System.out.println("广度优先搜索序列为：");
        graph.broadFirstSearch();
    }
}

程序员面试闯关（二）：数据结构考点与细节分析

一、线性表

1. 数组（顺序存储结构）

2. 链表（链式存储结构）

二、栈和队列

1. 栈

2. 队列

三、树

1. 各种概念重温

2. 一般树的存储结构

3. 二叉树

四、图

1. 定义：G(V【顶点集合】, E【边的集合】)

2. 相关概念

3. 图的存储结构

五、二叉树和图的各个常考方法代码汇总（代码可直接复制运行）

1. 二叉树各个方法

2. 图的广度和深度优先比遍历（邻接矩阵表示权值）

猜你喜欢

热点阅读