数据结构复习

内容预览:
  • 人就是这样,往往失去了,才懂得珍惜~
  • 碰到了,你不会和你会,效率是不一样的! 想走业务线、管理线、老板线、...~
  • 本文会涉及到几个,不过不多,以为会慢慢的补全,也会继续出文章解说,...~

什么是软件的基础?万年不变的公式:数据结构+算法=软件设计。走过了11年的计算机生涯,还记得,那时第二年,在那本白色的,还有点蓝色的教科书上面,首次接触到了这个公式,从此,就再也没放手。遥想当年,c++没学好,很是头疼那本书中的这个结构那个结构,链表是啥?还有,递归怎么去想?好吧,那一年玩魔兽去了,根本也没想多少,科是一定挂了的。兜兜转转这些年,从考研死扣了严蔚敏,到后来入手了Java,从这个框架转站了那个框架,从学校到公司,从一个公司又到另一个公司,大理石的《算法与数据结构》已经刷2遍,橙色Java算法接触宝典《算法》也是看了一遍,就连《c++11 primer》都从头到尾看了一遍。记得研三看primer的时候,边看就边想:特么的C++就这么个语法,当年怎么就学不进去,没学好呢?相当悔恨。同理,再《数据结构》上面也是一样。如果再让我来一遍,特么绝壁完爆期末考试。可是,人生已经回不去了。人就是这样,往往失去了,才懂得珍惜。对于《数据结构》的情感,我一直是这种内心情景,这次也算是描述清了。

一、学习数据结构的意义

  1. 你要走技术路线,不是混吃等死的话,上升必须要有个好的数据结构功底
  2. 锻炼思维
  3. 所有底层框架和系统的基础,不要被整天的api调用和crud所迷惑
  4. 算法的基础
  5. 不要说工作中碰不到,我在前前后后的两个工作中都碰到了。碰到了,你不会和你会,效率是不一样的!
  6. 想走业务线、管理线、老板线、我党线、人生赢家线、产品线等请无视上面BB,下面的也不用看了!
  7. 最后安利一句:技术就是苦逼,借用网易游戏宣传片中的一句话:用职业、生意、市场定义游戏的人,永远不懂得热爱的意义。扪心自问:你热爱技术吗?

整个数据结构的过程,大概是这样的:先理解概念,甚至可以看一遍实现,然后自己不看源码自己实现一遍。这个文章我主要介绍一下各个结构主要的注意点,具体的实现,我会上传github,链接再文末发出来。

对于算法部分,我们主要使用大名鼎鼎的leetcode进行跟踪与学习。本文会涉及到几个,不过不多,以为会慢慢的补全,也会继续出文章解说,大家也可以一起刷题,然后放上来。

另外,针对多线程的考虑,本文暂不涉及,要涉及这一点,可能不适合数据结构的入门与深入,咱们要一步步来。

二、链表、栈

对链表和栈的抽象主要是下面的接口:

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);
}

重点要注意点在于:

  1. 链表的存储结果,可以有两种:数组和链式
  2. 链表可以进行任意节点的插入、删除、访问
  3. 栈的插入必须要在第一个元素前进行插入(栈顶),删除也只能删除最上面的(出栈),正所谓的先进后出(LIFO)
  4. 注意对resize的实现,考虑好扩容的时机

  1. 链表(数组)具体的实现类为:struct.impl.ArrayList
  2. 链表(链式)具体的实现类为:struct.impl.LinkedList

三、 队列

对于队列的抽闲接口如下:

public interface Queue<E> {

int size();

boolean isEmpty();

void enQueue(E e);

E deQueue();

void resize(int num);
}

重点的注意点在于:

  1. 我们实现的是循环队列,使用数组进行存储
  2. 有两个指向收尾的index标示指针:first,last
  3. 队列空的情况为:first==last,队列为满的情况为:(last+1)%size==first
  4. 队列的入队是将元素放到队尾,出队是将队头的元素出队,这就是(FIFO)

主要实现类为:struct.impl.ArrayQueue

四、优先队列(堆,重点)

对于堆的抽象接口如下:

public interface Queue<E> {

int size();

boolean isEmpty();

void enQueue(E e);

E deQueue();

void resize(int num);
}

实现重点在:

  1. 注意堆的概念:一个树的树顶一定大于(小于)两个孩子,所以整个树,root就是最大(最小)的值
  2. 堆是一个完全二叉树,所以我们可以使用数组进行实现,按照层序遍历的序号,对应数组的具体index
  3. 实现难点在于删除与插入

  • 插入:放到整个数组的最后一个元素里面,然后执行上浮(shiftUp)操作
  • 删除:将最后一个元素与root交换,然后针对最新root元素进行下沉(shiftDown)操作

  1. 我们使用root编号为0,root的两个孩子节点编号为1、2,以此类推
  2. 获取当前index的孩子节点的操作为:index *2+1、index*2+2
  3. 获取当前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();


}

注意点在于:

  1. 搜索树是一颗完全二叉树
  2. 所有非叶子节点的数值,都大于左孩子,都小于右孩子
  3. 主要注意删除最小值和删除最大值操作,因为可能涉及到删除节点孩子的保存问题
  4. 删除任意节点操作是重点,麻蛋,被头条考了,让我写

实现类为: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();


}

注意点:

  1. AVL本身是一个BST
  2. AVL对BST的优化点在于:所有节点的左右子树的高度差,不大于1,防止BST退化成链表的问题
  3. 重点来了,思考好左旋右旋:如果是左左的情况,要进行右旋;如果是右右的情况,要进行左旋;如果是左右的情况,要进行先左旋再右旋;如果是右左的情况,要进行先右旋再左旋
  4. 下面是四种不平衡情况的图例:1:左左;2:左右;3:右左;4:右右

具体的实现代码为:struct.impl.AVL

七、结尾

我的上传地址是:AlgorithmAndDataStruct

以上就是:数据结构复习 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论