大学课程数据结构与算法复习

傷城~ 2022-12-03 13:16 207阅读 0赞

# 参考链接 #

[数据结构之数组和链表的区别][Link 1]

[算法的时间与空间复杂度][Link 2]

# 1、前言 #

数据结构与算法是计算机专业必修的一门课

在工作中，免不了要面对一些复杂的业务逻辑，可能有多种方法实现，每种方式的运行效率也可能都不一样，好的数据结构与算法能提升效率，具体体现在时间和空间上

比如，现在有一万个人，要找出姓名叫张三的人，最简单的方式是从头到尾遍历，如果张三是最后一位，则要遍历10000次

如果按字母首字母去查找的话，则首先在10000个人当中找到首字母为Z的人，假如是100个人，那最快的情况也只用遍历100次

这个就是数据结构与算法最简单的例子

为什么要学数据结构与算法？

*  锻炼思维和问题处理能力
 *  提高代码效率
 *  大厂面试必备

学习路线图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0phc21pbmV4amY_size_16_color_FFFFFF_t_70][]

# 2、数组和链表的区别 #

数组特点：

*  用一块连续的内存存储：空间利用率低，内存要求比较高
 *  查询简单，增加和删除困难：从头部插入（后面所有元素向后搬移）和删除（后面所有元素向前搬移）效率低
 *  按索引随机访问效率高，为O(1)，从数组首地址向后偏移即可
 *  数组的大小是固定的，不能进行动态扩展

链表特点：

*  由一系列结点组成，结点可以动态生成
 *  结点包括两部分：数据和指向下一个结点的指针
 *  查询慢，插入删除快
 *  占用不连续空间（不能随机访问，只能从头到尾遍历），空间利用率高

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0phc21pbmV4amY_size_16_color_FFFFFF_t_70 1][]

# 3、栈 #

栈其实是一种受限的线性数据结构，遵循先进后出

术语：

*  栈顶
 *  栈底
 *  入栈
 *  出栈

栈结构的方法：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push()</td> 
   <td>入栈操作</td> 
  </tr> 
  <tr> 
   <td>pop()</td> 
   <td>出栈操作</td> 
  </tr> 
  <tr> 
   <td>getTopElement()</td> 
   <td>返回栈顶的元素，但不会移除栈顶的元素</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>查看栈是否为空</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回栈内元素的个数</td> 
  </tr> 
  <tr> 
   <td>toString()</td> 
   <td>以字符串的形式展示栈内的所有元素</td> 
  </tr> 
 </tbody> 
</table>

典型的栈的应用场景：

![在这里插入图片描述][2020072110210531.png]

public class Test {
        private static Stack<Integer> stack = new Stack<Integer>();
    
        /**
         * 将十进制n数转化为m进制数
         */
        public static void fun(int n,int m){
            int a = n/m;
            int b = n%m;
            stack.push(b);
            if(a!=0){
                fun(a,m);
            }else{
                String s = "";
                int l = stack.size();
                for (int i = 0; i < l; i++) {
                    s+=String.valueOf(stack.pop());
                }
                System.out.println(s);
    
            }
        }
        
        public static void main(String[] args) {
            fun(17,2);
        }
    }

# 4、队列 #

队列也是一种受限的线性数据结构，遵循先进先出的原则

优先级队列：不遵循先进先出，优先级高的元素，在插入队列的时候可能会排在前面

# 5、链表 #

单向链表

双向链表

# 6、哈希表 #

**哈希表的由来：**

对于数组，如果已知下标i,那么查询一个元素就很快。但是如果不知道下标i,只知道元素的值，那么需要从头开始遍历数组，直到找到这个元素位置

为了解决数组的不足，引入了哈希表，哈希表在很多编程语言中都有实现

将一个值经过哈希函数计算后，再取模，会得到一个下标，好的哈希函数会使哈希冲突的几率很小

**哈希冲突的解决方法：**

*  拉链法（链地址法）
 *  开放地址法（可以理解为，当冲突时，寻找一个空白位置进行插入）
 *  线性探测法：从前往后查找，但是如果发生聚集现象（即从前往后查找时，连续好几个位置都不是空白的），则查找下一个空白位置就很慢
 *  二次探测：为了解决线性探测的聚集现象，主要做法是：依次移动index+1^2,index+2^2,index+3^2,...个位置，直到找到空白位置
 *  再哈希法

# 7、树结构 #

树结构是平日里我们常见的一种数据结构，例如家族族谱、公司管理层级结构图等，这样的数据结构的存在一定有一定的道理

树是一种非线性数据结构

## **7.1、树结构的优点：** ##

*  空间利用率比较高
 *  可以非常快速地查找到最大值和最小值

## 7.2、树结构术语 ##

<table> 
 <thead> 
  <tr> 
   <th>术语名</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>结点</td> 
   <td>树中的数据元素</td> 
  </tr> 
  <tr> 
   <td>结点的度</td> 
   <td>结点拥有的子树个数</td> 
  </tr> 
  <tr> 
   <td>叶子结点</td> 
   <td>度为0的结点</td> 
  </tr> 
  <tr> 
   <td>分支结点</td> 
   <td>度大于0的结点</td> 
  </tr> 
  <tr> 
   <td>父节点</td> 
   <td>衍生出其它结点的结点为这些结点的父结点</td> 
  </tr> 
  <tr> 
   <td>子结点</td> 
   <td>被某个结点衍生出来的结点为该结点的子结点</td> 
  </tr> 
  <tr> 
   <td>兄弟结点</td> 
   <td>具有同一个父节点的所有结点为兄弟结点</td> 
  </tr> 
  <tr> 
   <td>结点的层次</td> 
   <td>设定根结点所在层次为1，其它结点层次为其父节点层次+1</td> 
  </tr> 
  <tr> 
   <td>树的深度</td> 
   <td>树的所有结点中的最大层次为该树的深度</td> 
  </tr> 
  <tr> 
   <td>路径</td> 
   <td>从某个结点沿着树的层级关系到达另一个结点之间的路线</td> 
  </tr> 
  <tr> 
   <td>路径长度</td> 
   <td>路径上的结点个数 -1</td> 
  </tr> 
 </tbody> 
</table>

## 7.3、二叉树 ##

**二叉树的定义：** 树结构中每个结点最多只有两个子结点，即任何一个结点的度都小于等于 `2`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center]

### 7.3.1、完美二叉树（满二叉树） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 7.3.2、完全二叉树 ###

完全二叉树要满足以下两个条件：

*  除了最后一层外，其它各层的结点个数都达到最大个数
 *  最后一层的结点集中在左侧，且结点连续，只有右侧部分可以缺失结点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 2]

### 7.3.3、二叉树特性 ###

第i层结点个数最大为2^(i-1)个，i>=1

深度为k的二叉树总结点个数最大为2^k-1，k>=1

[Link 1]: https://blog.csdn.net/Jasminexjf/article/details/88847127
[Link 2]: https://zhuanlan.zhihu.com/p/50479555
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70]: /images/20221123/00b6e2b18cf1464eb8e49b43ec8b3064.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0phc21pbmV4amY_size_16_color_FFFFFF_t_70]: /images/20221123/5fa048514e7340dab52f87a2831785b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0phc21pbmV4amY_size_16_color_FFFFFF_t_70 1]: /images/20221123/c07beb5db6644a46b773db6b27d0c08a.png
[2020072110210531.png]: /images/20221123/623fb813fbb847028ea0b80b8a321610.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1754bab4f7084f2f97dd6b0280b65090.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/b7f49f05c11e4548976756fef5a266c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/baaa27aa323749e794e3a3d76ad9479d.png