什么是软件的基础? 万年不变的公式: 数据结构 + 算法 = 软件设计. 走过了 11 年的计算机生涯, 还记得, 那时第二年, 在那本白色的, 还有点蓝色的教科书上面, 首次接触到了这个公式, 从此, 就再也没放手. 遥想当年, c++ 没学好, 很是头疼那本书中的这个结构那个结构, 链表是啥? 还有, 递归怎么去想? 好吧, 那一年玩魔兽去了, 根本也没想多少, 科是一定挂了的. 兜兜转转这些年, 从考研死扣了严蔚敏, 到后来入手了 Java, 从这个框架转站了那个框架, 从学校到公司, 从一个公司又到另一个公司, 大理石的算法与数据结构已经刷 2 遍, 橙色 Java 算法接触宝典算法也是看了一遍, 就连c++11 primer都从头到尾看了一遍. 记得研三看 primer 的时候, 边看就边想: 特么的 C++ 就这么个语法, 当年怎么就学不进去, 没学好呢? 相当悔恨. 同理, 再数据结构上面也是一样. 如果再让我来一遍, 特么绝壁完爆期末考试. 可是, 人生已经回不去了. 人就是这样, 往往失去了, 才懂得珍惜. 对于数据结构的情感, 我一直是这种内心情景, 这次也算是描述清了.
一, 学习数据结构的意义
你要走技术路线, 不是混吃等死的话, 上升必须要有个好的数据结构功底
锻炼思维
所有底层框架和系统的基础, 不要被整天的 api 调用和 crud 所迷惑
算法的基础
不要说工作中碰不到, 我在前前后后的两个工作中都碰到了. 碰到了, 你不会和你会, 效率是不一样的!
想走业务线, 管理线, 老板线, 我党线, 人生赢家线, 产品线等请无视上面 BB, 下面的也不用看了!
最后安利一句: 技术就是苦逼, 借用网易游戏宣传片中的一句话: 用职业, 生意, 市场定义游戏的人, 永远不懂得热爱的意义. 扪心自问: 你热爱技术吗?
整个数据结构的过程, 大概是这样的: 先理解概念, 甚至可以看一遍实现, 然后自己不看源码自己实现一遍. 这个文章我主要介绍一下各个结构主要的注意点, 具体的实现, 我会上传 github, 链接再文末发出来.
对于算法部分, 我们主要使用大名鼎鼎的 https://leetcode-cn.com/problemset/all/ 进行跟踪与学习. 本文会涉及到几个, 不过不多, 以为会慢慢的补全, 也会继续出文章解说, 大家也可以一起刷题, 然后放上来.
另外, 针对多线程的考虑, 本文暂不涉及, 要涉及这一点, 可能不适合数据结构的入门与深入, 咱们要一步步来.
二, 链表, 栈
对链表和栈的抽象主要是下面的接口:
- public interface List<E> {
- int size();
- void resize(int resizeNum);
- boolean isEmpty();
- boolean isContained(E e);
- void addFirst(E e);
- void addLast(E e);
- void add(int index, E e);
- void remove(E e);
- E get(int index);
- int find(E e);
- }
重点要注意点在于:
链表的存储结果, 可以有两种: 数组和链式
链表可以进行任意节点的插入, 删除, 访问
栈的插入必须要在第一个元素前进行插入(栈顶), 删除也只能删除最上面的(出栈), 正所谓的先进后出(LIFO)
注意对 resize 的实现, 考虑好扩容的时机
链表 (数组) 具体的实现类为: struct.impl.ArrayList
链表 (链式) 具体的实现类为: struct.impl.LinkedList
三, 队列
对于队列的抽闲接口如下:
- public interface Queue<E> {
- int size();
- boolean isEmpty();
- void enQueue(E e);
- E deQueue();
- void resize(int num);
- }
重点的注意点在于:
我们实现的是循环队列, 使用数组进行存储
有两个指向收尾的 index 标示指针: first,last
队列空的情况为: first==last, 队列为满的情况为:
(last+1)%size==first
队列的入队是将元素放到队尾, 出队是将队头的元素出队, 这就是(FIFO)
主要实现类为: struct.impl.ArrayQueue
四, 优先队列(堆, 重点)
对于堆的抽象接口如下:
- public interface Queue<E> {
- int size();
- boolean isEmpty();
- void enQueue(E e);
- E deQueue();
- void resize(int num);
- }
实现重点在:
注意堆的概念: 一个树的树顶一定大于 (小于) 两个孩子, 所以整个树, root 就是最大 (最小) 的值
堆是一个完全二叉树, 所以我们可以使用数组进行实现, 按照层序遍历的序号, 对应数组的具体 index
实现难点在于删除与插入
插入: 放到整个数组的最后一个元素里面, 然后执行上浮 (shiftUp) 操作
删除: 将最后一个元素与 root 交换, 然后针对最新 root 元素进行下沉 (shiftDown) 操作
我们使用 root 编号为 0,root 的两个孩子节点编号为 1,2, 以此类推
获取当前 index 的孩子节点的操作为: index *2+1,index*2+2
获取当前 index 的父亲节点操作为:(index-1)/2
实现类为: struct.impl.PriorityQueue
五, 二叉搜索树(BST)
基本实现接口为:
- public class BST<E extends Comparable<E>> {
- public void addValue(E value);
- public E findMin();
- public E findMax();
- public E deleteMin();
- public E deleteMax() ;
- public void deleteNode(E value);
- public void inOrder();
- public void levelOrder();
- }
注意点在于:
搜索树是一颗完全二叉树
所有非叶子节点的数值, 都大于左孩子, 都小于右孩子
主要注意删除最小值和删除最大值操作, 因为可能涉及到删除节点孩子的保存问题
删除任意节点操作是重点, 麻蛋, 被头条考了, 让我写
实现类为: struct.impl.BST
六, 二叉平衡树(AVL)
基本实现接口为:
- public class BST<E extends Comparable<E>> {
- public void addValue(E value);
- public E findMin();
- public E findMax();
- public E deleteMin();
- public E deleteMax() ;
- public void deleteNode(E value);
- public void inOrder();
- public void levelOrder();
- }
注意点:
AVL 本身是一个 BST
AVL 对 BST 的优化点在于: 所有节点的左右子树的高度差, 不大于 1, 防止 BST 退化成链表的问题
重点来了, 思考好左旋右旋: 如果是左左的情况, 要进行右旋; 如果是右右的情况, 要进行左旋; 如果是左右的情况, 要进行先左旋再右旋; 如果是右左的情况, 要进行先右旋再左旋
下面是四种不平衡情况的图例: 1: 左左; 2: 左右; 3: 右左; 4: 右右
具体的实现代码为: struct.impl.AVL
七, 结尾
我的上传地址是: https://github.com/JCAndWHTForPro/AlgorithmAndDataStruct
来源: https://www.cnblogs.com/1024Community/p/9000710.html