【数据结构】——-线性表分析(顺序表与链表的对比)

1）线性表的长度可以动态改变，而JAVA数组的长度是固定的。2）线性表可以插入元素，而数组无法插入元素。之所以线性表比数组强大的原因是，顺序结构的线性表可以说是包装过的数组，自然会提供更多额外的方法来简化操作。JAVA的List接口就代表了线性表，它的两种实现分别为：ArrayList和LinkedList。

【数据结构】链表

线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以下不足：线性表的链式存储（单链表）的实现单向循环链表的实现

【数据结构】散列表哈希表hash table

给定一个键，该算法计算出一个索引，该索引代表了entry的地址。当需要插入一个新的键值对时，首先从hash对应的位置开始检查buckets，直到发现一个没有被占用的位置。哈希表的操作时间等于查找t(桶所在位置的时间加上列表的操作时间。

【数据结构】链接列表 Linked list

链接列表链接列表是数据元素的线性集合，但是并不会按照线性的顺序存取数据。链接列表在反向遍历时也会有困难。种类单向链接列表包含两个字段：一个整数值和指向下一个节点的链接的单向链接列表如下图：双向链表包含三个字段：一个整数值，一个指向下一个节点的链接和返回到前一个节点的链接循环链表其他链表等；

【数据结构】排序算法——快速排序

快速排排序是效率非常高的排序算法之一。然后再通过此方法堆这两部分数据分别进行快速排序，整个排序过程可以递归实现。优化快速排序时间复杂度一般为O，最坏为O(N*N)，快速排序的性能取决于递归树的深度，在最优的情况下，递归树深度为logN，最坏的情况下，递归深度为N。

陈越《数据结构》第五讲 树下

如何根据结点不同的查找频率构造更有效的搜索树？,wn}，存在不同构的两棵哈夫曼树。例如：对一组权值{1,2,3,3}，可构成：不同构的两棵哈夫曼树。可以用树结构表示集合；采用数组存储形式。

【数据结构】---线性表

线性表是数据结构中最简单、最基本和最重要的结构形式之一，前来总结一下，先上思维导图：主要是线性表的两种存储结构，分别形成了顺序表和链表，这两种存储结构各有其优缺点，不再重复介绍，下面详细介绍少这两种存储结构下的常用操作及其算法的时间复杂度。

【数据结构】[NOIP2013]火柴排队

题目要最小化a[i]-b[i]也就是说a序列第k大的元素必须和序列b中第kk大的元素位置必须一样那么我们我们可以把ab离散化问题将转化为b序列要交换几次可以令其等于a假设我们现在有离散化后的序列a={4,3,1,2}b={1,2,4}我们令q[a[i]]=b[i]相当于以a[i]为关键字对序列b[i]排序若序列a与序列b相等那么此时q[a[i]]应该等于a[i]的也就是q[i]=i那么也就是说如果

【数据结构】：红黑树RB Tree

红黑树是近似平衡的二叉搜索树。红黑树的性质:1，每个节点不是红色就是黑色2，根节点必须是黑色3，没有连续的红节点4，每条路径上黑色节点数目相等红黑树保证最长路径不超过最短路径的两倍。