数据结构考前总结

数据结构重点

• Java 和 Cpp 代码可以互相调用，cpp 指针对应Java的引用，灵活转换就可以

• 最短路径算法会考。这个意思是不是说，可能会考察编程？（感觉大概率会考dijkstra算法）

• 汉诺塔，可能会考一个选择题

  • 代码要看清楚，以及求一个递推式

    // A B C
    // 递归的想法，先把 n - 1 层放到B上，最后一层放到C，然后 n - 1 层放到C上
    public static void moveDisks(int n, char fromTower, char toTower, char otherTower){
        // 
        if(n == 1) System.out.println("move " + n + " from " + fromTower + " to " + toTower);
        else{
            moveDisks(n-1, fromTower, otherTower, toTower);
            // 移动单个
            System.out.println("move " + n + " from " + fromTower + " to " + toTower);
            moveDisks(n-1, otherTower, toTower, fromTower);
        }
        // n 相当于盘子的编号，也对应着盘子的大小关系
    }
    

    其实这里得到了递推式：$F(n)=2\ast F(n-1)+1$

1. 概述

• 看看递归，是一种思想，感觉像是在暗示考 给出先序遍历和中序遍历，求出来一棵树
• 看看分治，是一种思想，可能对应归并排序？快速排序？

2. 算法分析

• 复杂度基本概念记得东西不考

• 大O表示法，时间复杂度空间复杂度，（复杂度的分析？原理？）小o不会考，theta omega 有可能
  可能出简答题

  大O表示的是上界， Omega 表示的是下界， Theta 表示的是上下界都确定

  • 将一些排序算法，等等常见算法的时间和空间复杂度记住

• 分治思想， 最大子序列之和

• 秩排序，反复强调，可能代码

  • 代码在后面已经给出

3. 链表，栈，列表

• 线性表，树，图 三个一定都会有

• 单链表考的概率很高，栈和队列概率小一些，数组考的概率比较小

• 双向链表好像不考，约瑟夫问题不考，多项式不考, 没说循环链表不考

• 排序算法一定要看，基数排序
  一定要按照从低位到高位来看，循环着做先分拆再合并
  基数排序是稳定的

  课件中没有给出代码，像是会考简答题，就是从低位到高位，每次分到桶里形成链表，然后再把每个桶合并

• 作业里面的一些练习？

  • 交换链表中元素的位置

    ListNode swap(ListNode key, int key1, int key2){
        // 找到1前后的位置，找到2前后的位置，然后交换？
    }
    

  • 求两个有序链表的交集

  • 求两个有序链表的并集

  • 用非递归方法将链表进行反转

    // 一次性看三个...
    public ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;
        while(current != null){
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
    // 1 - 2 - 3 - 4
    

3.1 栈 和 队列

• 经常会被考到，不会出太难
• 两个栈 头对头 不会考
• 队列有可能不考
• 2010考研题，难度不会超过考研题
• 感觉这里的循环队列还是很容易考到的，
  还有就是p个数组移动的方法‘

4. 树

• 前面的概念一定不会考，不会考什么是度数等等，但是

  • 什么是树的度数？二叉树的度数一定是2吗？
    Degree of an elememts(nodes): the number of children it has.
    Degree of a tree: the maximum of its element degrees
    也就是说，度数看的是二叉树中度数最大的节点的度数，但是二叉树也可能度数为1

• 满二叉树，完全二叉树

  • 分别指的是每一层都是满的/前面都是n-1层都是满的，最后一层从左往右排布

• 前序，中序，后序的递归算法；
  非递归算法有可能考

  • 下面到tree PPT复习非递归算法，非常复杂

• 先序中序构建二叉树！！， make Tree函数？

• 后缀表达式应该不考

• 线索树；就考选择题， 也可能考代码题

  • 线索树的构建，线索树的遍历

  • 线索树可以分成先序线索树，中序线索树，后序线索树，他们的类定义都是一样的

    class BinaryNode{
        int lTag, rTag, data; // tag取值为1的时候，就代表 左节点存放的是对应的前驱/右节点对应的是后继 
        BinaryNode left;
        BinaryNode right;
    }
    

    所以说，从做题的角度上来看，只需要把序列画出来，然后每个节点看是不是缺失左子树或右子树，补上即可

  • 2013考过一道题，除了要求理解成员变量也要求理解遍历，而且PPT中有关于中序遍历线索树的构造方法，遍历方法

    • 中序遍历线索树的遍历：

      1. 找出first节点，因为是左 - 中 - 右，所以尽可能往左找就可以

      2. 找出next，如果rtag=1，可以直接看后继，如果rtag=0，表示有右子树，就先到右子树，然后尽可能往左找（自己已经是左 - 中 - 右的中间部分了，下一步是右）

         BinaryNode first(BinaryNode root){
             while(root.lTag == 0) root = root.left;
             // 要记得确定左边是左子树
             // 在线索树之中，只有2个节点的会有null的子节点，第一个元素的前驱，最后一个元素的后继
         }
         
         BinaryNode next(BinaryNode current){
             if(current.rTag == 1) return current.right;
             else {
                 current = current.right; // 右子树的最左边，甚至可以用first
                 while(current.lTag == 0) current = current.left;
                 return current;
             }
         }
         

    • 中序线索树的构建：
      非常类似与中序遍历一棵树，但是要记录前驱和后继方便操作
      在PPT上给出的是非递归方法，感觉不应该考这么难，这里做简单理解

• 广义表不要看

• 双亲表示 并查集，左子女右兄弟

  • 树和森林之间的互相转化？
  • 树可以转化成二叉树，对树进行先根就相当于对二叉树进行先序， 对树进行后根就相当于对二叉树进行中序
  • 森林的先根遍历就是二叉树先序，森林的中根就是二叉树的中序，森林的后根就是二叉树的后序
  • 这里有可能容易出错，建议有时间多画几次

• 霍夫曼树肯定要看的，经常要考

  • 要先进行排序，然后每次挑出最小的

  • 霍夫曼树的叶子有 n 个，非叶子就有 n - 1个；

  • 外路径长度最小…，而且还有额外的要求：这个要求是优先选取外节点，尽量让路径长度最短

    那这么说是不是每次看到相同权重，都要优先放高度小的？

    还有，可以用设计的哈夫曼树，进行译码和编码，例如左边0右边1

4.1. 搜索树

• 一般会考AVL树，包含了普通二叉搜索树； 二叉搜索树有可能编程题

• 判断是不是一棵二叉搜索树

  • 忽然想到的一点：如果只是判断左右节点是不够的必须要判断左边的最大和右边的最小，举个例子是 2 左边是 1， 1 右边是 100

• AVL树的编程题…

  // 递归做插入，递归做删除
  // 旋转操作...
  

• AVL树， 对数关系， 类似斐波那契数列，

• B树考不考，不记得

• 二分法搜索的判定树

5. 散列表

• 时不时会考，最容易考到开放地址线性探测，二次探测不考，成功搜索的比较次数？
  • 闭地址法， 开地址法
• 双散列和再散列，链表，看一看，不难，可能考选择
  什么是再散列？？

6. 优先队列

• 上滤，下滤，堆排序，O(n)建堆
• 后面的例子不大会考

7. 并查集

• 概率比较低

8. 图

• 一定要考的
• 前面概念不用记住
• 最短路径要考？那是简答还是代码
• 邻接矩阵邻接表 仔细看看
• 图的遍历要看一下
  • 可以判断一个图是不是连通的
• 最小生成树 - 最短路径 - AOV AOE 也要看

template<NameType,DistType> void Graph<NameType,DistType> :: 
DFS(int v, visited[])
    { 
    // 为什么不判断是不是走过了？？
    cout<<GetValue(v)<<"\n";
    visited[v]=1;
    int w=GetFirstNeighbor(v);
    while (w!=-1){ 
        if(!visited[w]) DFS(w,visited);
    	w=GetNextNeighbor(v,w);
    }
}

9 排序

• 一定要看，秩排序，基数排序，还有各种排序。
• 折半插入排序，不考
• 希尔排序，不考（有一年考了）
• 快速排序很容易考
• 锦标赛排序，不考
• 直接选择排序，堆排序一定要看
• 归并排序要看

对于编程题来说，看清楚变量名称， 成员名称

编程复习

最大子序列之和，分治法

// 给定一个序列，
// 要么在中间左侧，要么在中间右侧，要么在包含中间
int arrMaxSum(int []arr, int l, int r){
    if(l > r){
        return 0;
    }else if(l == r){
        return arr[l]>0 : arr[l] ? 0;
    }
    int mid = (l + r) / 2;
    int lMaxSum = arrMaxSum(arr, l, mid);
    int rMaxSum = arrMaxSum(arr, mid + 1, r);
    // ### ### ###
    // 向左生成局部最大子序列
    // 向右生成局部最大子序列
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for(int i = mid; i >= l;i++){
        leftBorderSum += arr[i];
        if(leftBorderSum > maxLeftBorderSum){
            maxLeftBorderSum = leftBorderSum;
        }
    } // 得到左侧
    //同理右侧
    return max3(lMaxSum, rMaxSum, maxLeftBorderSum + maxRightBorderSum);
}

秩排序

// 首先是互相之间比较，得出秩
void rank(int arr[], int r[], int len){
    // ### 注意初始化rank
    for(int i = 0;i < n;i++) r[i] = 0;
    for(int i = 0; i < n;i++){
        for(int j = i + 1;j < n; j++){
            if(arr[i] > arr[j]){
                arr[i]++;
            }else{
                arr[j]++;
            }// 这样是默认后面的大？放在后面，感觉稳定
        }
    }
}
void  rankSort(int arr[], int n){
    int []r = new int [n];
    rank(arr, r, n);
    for(int i = 0;i < n;i++){
        while(r[i] != i){
            int temp = r[i];
            swap(arr[i], arr[temp]);
            swap(r[i], r[temp]);
        }
    }
}

基数排序 radix sort

// 基数排序
// 给定一长串链表？然后去做这样？
// 课件中没有给出代码，像是会考简答题

给定先序和中序，构造二叉树

public static TreeNode create(String preOrder, String inOrder){
        if(preOrder == null || preOrder.isEmpty()){
            return null;
        }

        char rootData = preOrder.charAt(0);
        int rootIndexForInorder = 0;
        for(rootIndexForInorder = 0; rootIndexForInorder < inOrder.length(); rootIndexForInorder++){
            if(inOrder.charAt(rootIndexForInorder) == rootData){
                break;
            }
        }
        // 1 len1 len2
        // len1 1 len2
        TreeNode root = new TreeNode(rootData);
        int len1 = rootIndexForInorder;
        int len2 = inOrder.length() - len1 - 1;
        root.left = create(preOrder.substring(1, len1 + 1), inOrder.substring(0, len1));
        root.right = create(preOrder.substring(len1 + 1), inOrder.substring(len1 + 1));
        return root;
}

上滤，下滤，堆排序

public int heap[];
int currentSize = 10;
// 假如说是最大堆，大的往上跑
// 实现上滤算法
public void percUp(n){
    int parent = n / 2;
   	int child = n;
    int temp = heap[n];
    while(parent > 0){
       	if(heap[parent] < heap[child]) {
            heap[child] = heap[parent]; 
            parent /=2; child /=2;
        }
        else break;
    }
    // 注意， 这里是child... parent可能已经不符合标准，或者退出的时候没初始化的是原来的父亲，现在的孩子
    heap[child] = temp;
}

public void percDown(int n){
    int parent = n;
    int child = 2 * n;
    int temp = heap[parent];
    while(child <= currentSize){
        // 
        if(child + 1 <= currentSize && heap[child + 1] > heap[child]) child++;
        if(heap[child] > heap[parent]){
            heap[parent] = heap[child];
        }else{
            break; // 一定要记得退出...
        }
        parent = child;
        child *= 2;
    }
    // 这里容易分不清，是在什么地方需要移动...?
    heap[parent] = temp;
}

public int[] heapSort(){
    initHeap();
    // 排序过程中，每次都取出，放到最后面去...
    
}

public int[] initHeap(){
    for(int i = n / 2;i > 0;i--){
        percDown(i);
    }
}

判断是不是一棵二叉搜索树

递归求链表均值

递归判断是不是二叉搜索树

判断无向图是不是一棵树