链表

    链表的结点内容：

        数据域

        指针域（存储下一个结点的地址）

    操作链表时所需：

        头指针

        链表长度

        尾指针（为了尾部插入方便）

     链表的操作：

        链表的获取：

            通过下标获取，循环遍历下标，从头结点开始，当在下标的前一个时range(index)，其指向的下一个结点就是要获取的。

        链表的插入：

            有四种情况：

                空链表

                插入头部

                插入尾部

                插入中间

                注：在插入之后，链表的长度相应的要加 1

           链表的删除：

                有三种情况：

                       删除头结点

                        删除尾结点

                        删除中间结点

                        注：在删除之前要先判断是否为空，在删除一个节点之后，链表的长度要减 1

数组和链表被看作是数据存储的物理结构

栈和队列

    栈：

        最早进入的元素存放的位置是栈底，最后进入的元素存放的位置叫栈顶。

        用数组和链表都可以实现。

        栈的操作：

            入栈：

                将新元素从栈顶一侧放入，新元素的位置就是新的栈顶。

            出栈：

                栈顶元素出栈，出栈元素的前一个元素将成为新的栈顶。

    队列：

        队列的出口端叫队头，队列的入口端叫队尾。

        用数组和链表都可实现。

        队列的操作：

            入队：

                将新元素从队尾放入，新元素的下一个位置将会成为新的队尾。

            出队：

                把元素从队头移出，出队元素的后一个元素会成为新的队头。

    循环队列：

        目的：维持队列容量的恒定。

        判断队满：

            （队尾下标+1）%数组长度 = 队尾下标

树和二叉树

    树：

        属性：

            根节点

            叶子节点

            子树

    二叉树：

        树的每个节点最多有2个结点。

        两种形式：

            满二叉树

            完全二叉树

        物理存储结构：

            链式存储结构

                每个节点包含3部分

                    存储数据的data变量

                    指向左孩子的left指针

                    指向右孩子的right指针

            数组

                按照层级顺序把二叉树的结点放到数组中对应的位置上。

                假设父节点的下标是parent，左孩子的下标是 2*parent+1，

                右孩子的下表是2*parent+2。

            应用

               查找

                    若左不为空，左子树所有结点的值均小于根节点的值；

                    若右不为空，右子树所有结点的值均大于根节点的值；

                    左子树、右子树都是二叉查找树。 

                维持相对顺序

                    读者自行了解。

        遍历

            从结点之间的位置关系解读来看

                前序遍历

                中序遍历

                后序遍历

                    实现上来说，可以使用递归方式，非递归方式需要使用栈来解决。

                层级遍历

                    借助数据结构队列来实现。

            从宏观角度来看

                深度优先遍历（前三种）

                广度优先遍历（后一种）

    二叉堆

        两种形式   

            最大堆

                任何一个父节点的值，都大于或等于它左孩子或右孩子结点的值。

            最小堆

                任何一个父节点的值，都小于或等于它左孩子或右孩子结点的值。

            根结点叫作堆顶。

            最大堆的堆顶是整个堆中的最大元素；最小堆堆顶是整个堆中的最小元素。

        自我调整

            插入结点

                插入位置是二叉树的最后一个位置

            删除结点

                删除根结点的时候，将堆的最后一个结点临时补充到堆顶的位置。

            构建二叉堆

                就是把一个武勋的完全二叉树调整为二叉堆

    优先队列

        两种情况

            最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队

            最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

排序算法

    冒泡算法

        是一种基础的交换排序，也是稳定排序。

        原理

            把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置。

        优化1

            针对的是，在完成排序循环之前，数据已经完成了排序，但是还在继续循环。

            加一个标志位，若序列有交换，说明序列无序，若没有交换，说明序列已经有序，直接跳出大循环。

        优化2

            针对的是，在一个序列中，一部分有序，一部分无序

            在加标志位的基础上，区分有序和无序区。在每一轮排序后，记录下最后一次交换的位置，该位置即为无序数列的边界。

    鸡尾酒排序

        这种排序解决的问题是，例如 2,3,4,5,6,7,8,1这样的数列排序

        原理

            排序过程像钟摆一样，第1轮从左到右，第2轮从右到左，依次类推。

        代码实现（只是说明）

            和冒泡法一样，区别在于在打循环下，有两个小循环。

    快速排序法

        原理

            在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆分成两个部分。

            这种思路叫分治法。

        操作过程

            基准元素的选择

                随机选择一个元素作为基准元素，并让基准元素和数列首元素交换位置。

            元素交换

                双边循环

                    设置两个指针left和right，指向数列的最左和最右连个元素。

                    if right >= pivot 则指针向左移动，else right指针停止，切换到left指针。

                单边循环

                    选定基准元素，设置一个mark指针指向数列的起始位置，这个指针代表小于基准元素的区域边界。

                    若遍历到的元素大于基准元素，继续往后遍历；

                    若遍历到的元素小于基准元素；

                    1.把mark指针右移1位

                    2.最新遍历到的元素和mark指针所在位置的元素交换位置

    堆排序

         步骤

            1.把无序数组构建成二叉树，需要从小到大排序，则构建成最大堆，需要从大到小排序，则构建成最小堆；

            2.循环删除堆顶的元素，替换到二叉堆的末尾，调整堆产生新的堆顶

    计数排序

        原理

            使用下标用来排序。以数列元素值为数组下标，将相应的元素放入到对应的下标的地方。

        优化1

            不再是以最大值作为统计数组的长度，而是以数列 最大值-最小值+1 作为统计数组的长度。

        优化2

            从统计数组的第2个元素开始，每一个元素都加上前面所有元素之和。目的是让统计数组存储的元素值，等于相应整数的最终排序位置的序号。

    桶排序

        原理

            1.创建桶，确定每一个 桶的区间范围（创建桶的数量等于原始数列的元素数量（其中一种方法）），区间跨度 = （最大值 - 最小值） / （桶的数量-1）

            2.遍历原始数列，把元素对号入座放入桶中

            3.对每个桶内的元素分别进行排序

            4.遍历所有桶，输出所有元素