动脑学院学习总结(数据结构)

作者: 若无初见 | 来源:发表于2018-12-10 18:57 被阅读0次

冒泡排序和选择排序，适合个位数的排序

冒泡排序（Bubble Sort）

一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序简单的讲就是相邻的两个数字对比，大的数往后推。

第一轮下来已经把最大的数字9往后推到最后一位。接下来就要比较1 3 5 2 ->1 3 2 5 然后是1 3 2 所以按照这个思路再最外面加一个for循环就可以将数组排序

我们看下，这是最基本的冒泡排序写法。那么我们看下他的时间复杂度是多少？冒泡排序的时间复杂度是O(n²)。这是冒泡排序的最差时间复杂度。那么他有没有优化的方案呢？

有！我们可以假设下如果一开始的数组数据就是从小到大排序好的呢？那么真正的有效代码时间复杂度是O(n)，因为if语句根本就走不进去。我们看下代码。

选择排序

一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

先排第一次，首先将第一个数字固定然后和后面一个数字3对比如果4>3就将3的角标赋值给index,然后对换数字，以此类推，我们看下结果：

按照这样的思路，再最外层加上一个循环进行排序：

那么这个算法也有优化方案吗？有！

栈和队列

栈：只允许在表的末端进行插入和删除的线性表。基于数组存储表示的栈称为顺序栈，基于链表的存储表示的栈称为链栈

栈的存储特性可以理解成子弹压入弹夹中。先压入的子弹总数在最后才弹出。因此栈也称为先进后出(LIFO, Last In First Out) 的线性表

下面用代码表示下：采用链式栈的方式

创建结点类和栈类

入栈：将原本栈顶指向的节点交由新节点来指向，栈顶指向新加入的节点

空栈：如果栈顶和栈底指向相同，说明是空栈

遍历：栈顶指针不断向下移，直到到达栈底。为了避免影响原栈，使用临时结点指向stackTop并且随之一起移动。

出栈：将栈顶指针向下移动一位

清空栈：实际上就是不断的出栈，直到到达栈底

测试：

队列

队列：队列是限定数据存储位置的一种线性表，它允许在一端插入，再另一端删除。允许插入的一端叫队尾，允许删除的一端叫做队头。

队列基于数组的存储表示称为顺序队列。是利用一个一维数组 array[maxLength]表示存储的.并且利用了2个指针front和rear分别表示队头和队尾的位置。

如图表示：当front等于rear时，此队列不是还剩一个元素，而是空队列。

当有数据插入的时候，数据插入的位置是当前rear的位置，而rear的值就要前进一位，因为rear永远指向下一个数据的存储位置。

当数据删除的时候首先要把当前front指向位置的数据记录下来，然后front的指向位置就要+1，最后把记录的元素返回。因为front指向的位置永远都是对头元素

那么问题来了，rear永远指向下一个位置元素的存储位置，那么如果出现上图的情况不就是存储的内存溢出了吗？实际上这个溢出是”假溢出“

因为我们可以发现再数据的前面实际上还有空位置可以利用。根据这种情况，为了充分利用资源空间从而引出了循环队列

用2个公式表示

队头指针进1 ： front = (front+1)%maxLength ;

队尾指针进1 ： rear = (rear+1)%maxLength ;

如果循环队列读取元素的速度大于存入的速度，队头指针很快就赶上队尾指针，一旦front == rear 则变成空队列，反之，如果存入元素的速度大于读取的，队尾指针赶上队头指针，如果队列满就不能再添加数据了。为了区分空队列和满队列，用(rear+1)%maxLength == front来表示满队列，用 rear== front表示空队列。

同样的用代码测试一下：用顺序队列表示下

判断是否满队列：用公式rear = (rear+1)%maxLength ==front;

判断是否是空队列：用公式 rear== front

入队列：数据插入的位置是当前rear的位置，而rear的值就要前进一位，因为rear永远指向下一个数据的存储位置。

删除数据：front的指向位置就要向前一位

清空队列：

遍历队列：使用临时变量防止破坏源数据

测试一下：

顺序表

在顺序表中，最常见的操作当然是查找（搜索），插入和删除了，现在对这三种操作的复杂度进行简要的分析。

第一，搜索：

顺序表的顺序搜索算法，它的主要内容就是从顺序表的第一项开始，根据要查找的给定值x，然后在顺序表中逐次进行比较。若相等，则搜索成功，返回它的所在位置。若遍历整个表，没有值与其相等，则返回搜索失败。

一般来说，搜索算法的复杂度是根据比较次数来决定的。简要分析，如果我们要找的值在第一个表项，那么它的比较次数就是1，当然要是在第二个表项，次数就为2，依次类推，在第n个表项，比较次数就为n。好了啦，现在我们可以计算它的平均比较次数了。假定每个表项的可能性都相等，那么我们有：

Acn=1/n*Σi=1/n*(1+2+.....+n)=1/n*n*(n+1)/2=(n+1)/2;

所以平均比较次数为(n+1)/2；

第二，插入：

顺序表的插入和删除算法复杂度与其表项循环内数据移动次数直接有关，先分析插入。我们知道，顺序表中如果要在某个位置插入一个元素，就必须把那个空出来，怎么空出来呢，其实就是把它以及它后面的元素向后移动一位。那么就是这样的，如果将新表项插入至第i个表项后面，可以从后向前循环，逐个向后移动n-i个表项。最好的情形就是在表尾追加新元素。那么它的移动次数为0，相反，最坏情形是在第一个表项位置插入。那么移动次数为n。来看平均移动次数。

Amn=1/(n+1)*Σ(n-i)=1/(n+1)*((n-1)+...+1+0)=(n)/2;

第三，删除：

在删除第i个表项时，是逐个移动n-i个表项。最好的情况是在删去最后的n个表项。次数为0，最坏情况是删除第一个表项。移动个数为n-1。那么平均移动个数：

Amn=1/n*Σ(n-i)=1/n*((n-1)+...+1+0)=(n-1)/2;

原文：https://blog.csdn.net/lifestylegoingon/article/details/47903743

总结：

通过上述的分析，我们对顺序表的实现已有了比较清晰的认识，接下来看一下顺序表的执行效率问题，主要针对获取、插入、修改、删除等主要操作。前面分析过，由于顺序表内部采用了数组作为存储容器，而数组又是随机存取结构的容器，也就是说在创建数组时操作系统给数组分配的是一块连续的内存空间，数组中每个存储单元的地址都是连续的，所以在知道数组基地址后可以通过一个简单的乘法和加法运算即可计算出其他存储单元的内存地址(实际上计算机内部也就是这么做的)，这两个运算的执行时间是常数时间，因此可以认为数组的访问操作能在常数时间内完成，即顺序表的访问操作(获取和修改元素值)的时间复杂为O(1)。

对于在顺序表中插入或者删除元素，从效率上则显得不太理想了，由于插入或者删除操作是基于位置的，需要移动数组中的其他元素，所以顺序表的插入或删除操作，算法所花费的时间主要是用于移动元素，如在顺序表头部插入或删除时，效率就显得相当糟糕了。

优点

使用数组作为内部容器简单且易用

在访问元素方面效率高

数组具有内存空间局部性的特点，由于本身定义为连续的内存块，所以任何元素与其相邻的元素在物理地址上也是相邻的。

缺点

内部数组大小是静态的，在使用前必须指定大小，如果遇到容量不足时，需动态拓展内部数组的大小，会造成额外的时间和空间开销

在内部创建数组时提供的是一块连续的空间块，当规模较大时可能会无法分配数组所需要的内存空间

顺序表的插入和删除是基于位置的操作，如果需要在数组中的指定位置插入或者删除元素，可能需要移动内部数组中的其他元素，这样会造成较大的时间开销，时间复杂度为O(n)

链表

通过前面对线性顺序表的分析，我们知道当创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。鉴于这种种原因，于是链表就出场了，链表在初始化时仅需要分配一个元素的存储空间，并且插入和删除新的元素也相当便捷，同时链表在内存分配上可以是不连续的内存，也不需要做任何内存复制和重新分配的操作。

创建结点类

单链表添加：链表添加分为头部添加和其他

添加头部位置：头部结点为空所以直接将新结点赋值给头部位置

添加中间(尾部)位置：先找到要添加结点的前一个位置，新结点的next=front.next, front.next指向新结点的位置。记得判空，因为尾部的next是空

单链表删除：链表删除分为头部删除和其他

删除头部位置：删除头部位置，及它的next变成新的head.

删除中间位置：先找到要删除结点的前一个位置，该位置的next直接指向该位置next的next.

其他方法：

测试：

单链表性能分析：

由于单链表并不是随机存取结构，即使单链表在访问第一个结点时花费的时间为常数时间，但是如果需要访问第i(0<i<n)个结点，需要从头结点head开始遍历部分链表，进行i次的p=p.next操作，这点从上述的图文分析我们也可以看出，这种情况类似于前面计算顺序表需要平均移动元素的总数，因此链表也需要平均进行n2n2次的p=p.next操作，也就是说get(i)和set(i,x)的时间复杂度都为O(n)。

由于链表在插入和删除结点方面十分高效的，因此链表比较适合那些插入删除频繁的场景使用，单纯从插入操作来看，我们假设front指向的是单链表中的一个结点，此时插入front的后继结点所消耗的时间为常数时间O(1),但如果此时需要在front的前面插入一个结点或者删除结点自己时，由于front并没有前驱指针，单凭front根本无法知道前驱结点，所以必须从链表的表头遍历至front的前一个结点再执行插入或者删除操作，而这个查询操作所消耗的时间为O(n),因此在已知front结点需要插入前驱结点或者删除结点自己时，消耗的时间为O(n)。当然这种情况并不是无法解决的，后面我们要分析到的双链表就可以很好解决这个问题，双链表是每个结点都同时拥有前后继结点的链表，这样的话上面的问题就迎刃而解了。上述是从已知单链表中front结点的情况下讨论的单链表的插入删除效率。

我们可能会有个疑问，从前面单链表的插入删除的代码实现上来说，我们并不知道front结点的，每次插入和删除结点，都需要从表头开始遍历至要插入或者删除结点的前一个结点，而这个过程所花费的时间和访问结点所花费的时间是一样的，即O(n)，

也就是说从实现上来说确实单链表的插入删除操作花费时间也是O(n)，而顺序表插入和删除的时间也是O(n)，那为什么说单链表的插入和删除的效率高呢？这里我们要明白的是链表的插入和删除之所以是O(N)，是因为查询插入点所消耗的，找到插入点后插入操作消耗时间只为O(1)，而顺序表查找插入点的时间为O(1)，但要把后面的元素全部后移一位，消耗时间为O(n)。问题是大部分情况下查找所需时间比移动短多了，还有就是链表不需要连续空间也不需要扩容操作，因此即使时间复杂度都是O(n)，所以相对来说链表更适合插入删除操作。

原文：https://blog.csdn.net/javazejian/article/details/52953190

双链表

双链表的主要优点是对于任意给的结点，都可以很轻易的获取其前驱结点或者后继结点，而主要缺点是每个结点需要添加额外的next域，因此需要更多的空间开销，同时结点的插入与删除操作也将更加耗时，因为需要更多的指针指向操作。

在插入双链表时需分两种情况，一种是在插入空双链表和尾部插入，另一种是双链表的中间插入，如下图在空双链表插入值x：

原文：https://blog.csdn.net/javazejian/article/details/52953190

代码：

创建一个结点类，包含了前驱和后继以及数据域

尾部的插入：如果是空表则将新节点设置位first结点，反之添加在尾部位置。

指定位置添加：在指定位置添加需要将新结点的前驱指向front后继指向front的next。故新结点为：

接着更改front的next指向newNode，front的next指向newNode。这样原本A、B两个的连接点就断开，重新指向新的位置。

代码表示：

根据index获取结点

删除结点：删除结点包括删除尾结点，头结点以及中间结点。

测试：

二叉树的定义及其基本性质

二叉树（Binary Tree）是n(n≥0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交、分别称为左子树和右子树的子二叉树构成，二叉树也是递归定义的，在树种定义的度、层次等术语，同样适用于二叉树。

二叉树的5种表现

满二叉树和完全二叉树

一棵高度为h的满二叉树（Full Binary Tree）是具有2h−1(h≥0)2h−1(h≥0)个结点的二叉树。满二叉树的最大特点是每一层次的结点数都达到最大值，我们可以对满二叉树的结点进行连续编号并约定根结点的序号为0，从根结点开始，自上而下，每层自左向右编号。如下图所示（a）：

原文：https://blog.csdn.net/javazejian/article/details/53727333

对于二叉树的详细信息，转至原文：java数据结构与算法之双链表设计与实现

二叉树的排序

前序遍历

中序遍历

后续遍历

二叉排序树 (二叉搜索树)

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

创建一个结点类

二叉排序树的插入

事实上对于二叉查找树的插入操作的设计是比较简单，我们只要利用二叉查找树的特性（即对每个父结点，它的左子树中所有项的值小T中的值，而它的右子树中所有项的值都大于T中的值），找到只对应的插入位置即可，假如现在我们要插入data=4的结点，那么可以这样操作，沿着树查找(比较结点的数据与data的大小从而决定往左/右子树继续前行)，如果找到data(4),则什么也不做，否则将data插入到遍历的路径上的最后一个点，如下图所示：

打印数据：中序遍历可以从小到大排序（左根右）

测试一下

二叉排序树删除
对于二叉树来说，删除是一种比较麻烦的操作，因为涉及到了多种情况

① 如果要删除的结点q恰好是叶子结点，那么它可以立即被删除

② 如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）

③ 如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。

原文：https://blog.csdn.net/javazejian/article/details/53727333

查找树中的最大和最小的值：树中的最左边的结点值就是最小值，最右边的结点值就是最大值

测试：

AVL树

AVL树又称为高度平衡的二叉搜索树，一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二叉查找树(空树的高度为-1)，

用一张图说明下原文：https://blog.csdn.net/javazejian/article/details/52953190

平衡二叉树的单旋转算法与实现

从图3和图4可知，在原始AVL树插入7结点后，结点9变为失衡点，树再满足AVL性质，因此需要对9结点进行左左单旋转(即向右旋转)后，得到图4，我们发现此时并没有操作树的根结点(6)，实际上这是因为正常情况下，不必从树的根结点进行旋转，而是从插入结点处开始，向上遍历树，并更新和修复在这个路径上的每个结点的平衡及其平衡信息(高度)即可。

右右单旋转(RR)情景④分析

接着再来看看右右单旋转(RR)的情景，如下图，可以发现与左左单旋转的情况恰好是一种镜像关系，同样结点X并不能满足AVL树的性质，在这样的情景下，需要对X结点进行左旋转来修复树的平衡，如图1经左旋转后变了图2，此时X变为了根结点，W变为X的左孩子，X的左子树变为W的右子树，而树又重新恢复了平衡。如图3和图4的实例情景，原始的AVL树在12处插入结点18后，结点10就变成了失衡点，因为10的左子树和右子树的高度相差2，显然不符合AVL树性质，需要对结点10进行右右单旋转修复(向左旋转)，然后得到图4，此时树重新回到了平衡，这便是右右单旋转(RR)的修复情景。