数据结构

基本概念

1. 相互之间存在一种或多种特定关系的数据元素的集合。
2. 按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。
3. 数据逻辑结构，数据存储结构，数据的运算称为数据结构三要素。

分类

逻辑结构

• 数据元素间抽象化的相互关系简称为逻辑结构。 与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。

1.线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。
2.非线性存储：每个结点可以有不止一个直接前驱和直接后继。

存储结构

• 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

1. 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2. 链接存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。
3. 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。其优点是检索速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
4. 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。其优点是检索、增加和删除结点的操作都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

判断

• 当一个结构，如数组、链表、树、图，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构；
• 相反，当此结构在原有基础上加上了某种限定，使得其在物理结构中只有一种定义，那么这个结构就属于物理（存储）结构；

数据的运算

施加在数据上的运算包括运算的定义和实现。
运算的定义是针对逻辑结构的，指出运算的功能；
运算的实现是针对存储结构的，指出运算的具体操作步骤。

数据结构详解

1.线性表

• 线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,an-1组成的有限的序列，在数学中记作(a0,a1,…,an-1)，其中ai的数据类型可以是基本数据类型(int,float等)、字符或类。n代表线性表的元素个数，也称其为长度(Length)。若n=0，则为空表；若n > 0，则ai(0 < i < n-1)有且仅有一个前驱(Predecessor)元素ai-1和一个后继(Successor)元素ai+1，a0没有前驱元素，ai没有后继元素。

1.1 线性表的顺序存储（SeqList）

顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，如int，float或者自定义类型等，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址

线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1)，将ai(0

1.2 线性表的链式存储

• 当创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。
• 鉴于这种种原因，于是链表就出场了，链表在初始化时仅需要分配一个元素的存储空间，并且插入和删除新的元素也相当便捷，同时链表在内存分配上可以是不连续的内存，也不需要做任何内存复制和重新分配的操作。
• 线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的，逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元中都会有一个地址指向域，这个地址指向域指明其后继元素的位置。在链表中存储数据的单元称为结点(Node)，从图中可以看出一个结点至少包含了数据域和地址域，其中数据域用于存储数据，而地址域用于存储前驱或后继元素的地址。

1.2.1 单链表

1. 单链表(SingleILinkedList)
2. 带头结点的单链表(HeadSingleILinkedList)
   头结点：一个没有值的结点
3. 循环单链表(CircularHeadSILinkedList)
   链表中的最后一个结点的next域指向了头结点head，形成环形的结构

详细讲解：顺序表与单链表详细讲解与实现

1.2.2 双链表

• 在单链表分析中，我们可以知道每个结点只有一个指向后继结点的next域，倘若此时已知当前结点p，需要查找其前驱结点，那么就必须从head头指针遍历至p的前驱结点，操作的效率很低，因此如果p有一个指向前驱结点的next域，那效率就高多了，对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表，称之为双链表。
• 双链表的主要优点是对于任意给的结点，都可以很轻易的获取其前驱结点或者后继结点，而主要缺点是每个结点需要添加额外的next域，因此需要更多的空间开销，同时结点的插入与删除操作也将更加耗时，因为需要更多的指针指向操作。

1. 双链表(HeadDoubleILinkedList)
2. 循环双链表(LoopHeadDILinkedList)
3. 排序循环双链表(SortLoopHeadDIlinkedList)
   排序循环双链表指的是在插入元素时，不再根据index标志，而是根据值的大小寻找插入位置，但是有个插入值data必须是T或者T的父类而且实现了Comoarable接口。
4. 异或高效存储双链表(XORNode)
   双链表的实现中，都是需要一个指向后继结点的正向指针和一个指向前驱结点的反向指针，我们在构造一个结点类时需要一个数据域data、一个指向后继结点的指针next以及一个指向前驱结点的指针prev。但为了设计更高效节省存储空间，一种基于指针差运算存储高效的双向链表就诞生了。这种链表的每个结点仍然与单链表一样,仅使用一个指针域来设计双向链表。
   结点中的ptrdiff字段存储了后继结点与前驱结点的地址差，指针的差通过异或运算来实现。
   pridiff=后继结点的地址⊕前驱结点的地址
   还未实现

详细讲解：双链表详细讲解与实现

1.3 改良顺序表与双链表(类似ArrayList和LinkedList)

• 改良顺序表与双链表类似ArrayList和LinkedList(Iterator迭代器与fast-fail机制)

2. 栈(Stack)

• 可以认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈。

• 栈(Stack)是一种有序特殊的线性表，只能在表的一端(称为栈顶，top，总是指向栈顶元素)执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out FILO)的线性表。

2.1 顺序栈

• 顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作。当然我们还可以采用内部数组实现顺序栈。

1. 顺序表实现(StackByArrayList)
2. 内部数组实现(SeqStack)

2.2 链式栈

• 链式栈（Linked Stack），就是采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础即可。

1. 单链表实现(LinkedStackBySingleLinkedList)
2. 结点实现(LinkedStack)

2.3 栈的应用

1. 符号匹配（CheckExpression）
   在编写程序的过程中，我们经常会遇到诸如圆括号"()"与花括号"{}"，这些符号都必须是左右匹配的，这就是我们所说的符合匹配类型，当然符合不仅需要个数相等，而且需要先左后右的依次出现，否则就不符合匹配规则
2. 中缀表达式转换为后缀表达式(CalculateExpression)

2.4 详细讲解

栈的详细详解与实现

3. 队列(Queue)

• 队列是一种特殊的线性表，其插入和删除的操作分别在表的两端进行，队列的特点就是先进先出(First In First Out)。我们把向队列中插入元素的过程称为入队(Enqueue)，删除元素的过程称为出队(Dequeue)并把允许入队的一端称为队尾，允许出的的一端称为队头，没有任何元素的队列则称为空队。

3.1 顺序队列

1. 单队列
   采用顺序表实现队列时，入队操作直接执行顺序表尾部插入操作，其时间复杂度为O(1)，出队操作直接执行顺序表头部删除操作，其时间复杂度为O(n)，主要用于移动元素，效率低，既然如此，我们就把出队的时间复杂度降为O(1)即可，为此在顺序表中添加一个头指向下标front和尾指向下标，出队和入队时只要改变front、rear的下标指向取值即可，此时无需移动元素，因此出队的时间复杂度也就变为O(1)。
   通过给顺序表添加front和rear变量记录下标后使用得出队操作的时间复杂度降为O(1)，但是却出现了另外一个严重的问题，那就是空间浪费。
   遗留下来的空间并没有被重新利用，反而是空着，出现队列已满的假现象，这种假现象我们称之为假溢出，之所以出现这样假溢出的现象是因为顺序表队列的存储单元没有重复利用机制，而解决该问题的最合适的方式就是将顺序队列设计为循环结构。

2. 循环队列（SeqQueue）
   顺序循环队列就是将顺序队列设计为在逻辑结构上收尾相接的循环结构，这样我们就可以重复利用存储单元。
   循环队列有以下计算关系

//其中front、rear的下标的取值范围是0~size-1，不会造成假溢出。
front=(front+1)%size;//队头下标
rear=(rear+1)%size;  //下一个入队元素的下标

a. front为队头元素的下标，rear则指向下一个入队元素的下标
b. 当front=rear时，我们约定队列为空。
c. 出队操作改变front下标指向，入队操作改变rear下标指向，size代表队列容量。
d. 约定队列满的条件为front=(rear+1)%size,注意此时队列中仍有一个空的位置，此处留一个空位主要用于避免与队列空的条件front=rear相同。
e. 队列内部的数组可扩容，并按照原来队列的次序复制元素数组

3.2 链式队列（LinkedQueue）

• 链式队列，将使用带头指针front和尾指针rear的单链表实现，front直接指向队头的第一个元素，rear指向队尾的最后一个元素。
• 设计链式队列

a. 分别设置front和rear指向队头结点和队尾结点，使用单链表的头尾访问时间复杂度为O(1)
b. 设置初始化空队列，使用front=rear=null，并且约定条件front==null&&rear==null成立时，队列为空。
c. 当第一个元素入队或者最后一个元素出队时，同时更新front指针和rear指针的指向。
d. 入队操作时，使插入元素的结点在rear之后并更新rear指针指向新插入元素。
e. 出队操作时，若队列不为空获取队头结点元素，并删除队头结点元素，更新front指针的指向为front=front.next

3.3 优先队列(PriorityQueue)

• 优先级队列也是一种特殊的数据结构，队列中的每个元素都有一个优先级，若每次出队的是具有最高优先级的元素，则称为降序优先级队列(总是先删除最大的元素)。若每次出队的是值最小的元素，则称为升序优先级队列(总是先删除最小的元素)，通常情况下我们所说的优先队列，一般是指降序优先级队列。
• 使用之前分析过的MyLikedList作为基底，实现一个排序的SortLinkedList继承自MyLinkedList，这里需要注意的是排序链表中的T类型必须是实现了Comparable接口的类型，在SortLinkedList中主要重写添加的add方法，插入逻辑是，通过比较元素的大小加入，而非简单下标或尾部插入。
• 接着以SortMyLinkedList为基底实现优先队列PriorityQueue

3.4 详细讲解

队列的详细讲解与实现

4. 集合(Set)

• 集合，是由一堆无序的、相关联的，且不重复的内存结构【数学中称为元素】组成的组合；
• 集合分类
  有序集合：集合里的元素可以根据 key 或 index 访问 (List、Map)
  无序集合：集合里的元素只能遍历。(Set)

4.1 Hash

• Hash（哈希），又称"散列"
• 在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。

1. 为什么要有 Hash
   我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大减少比较次数。

2. 哈希函数
   哈希的过程中需要使用哈希函数进行计算。哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。

3. 几种常见的哈希函数（散列函数）构造方法

• 直接定址法
  H(key) = key 或 H(key) = a*key + b
• 除留余数法
  H(key) = key % p, p < m
• 数字分析法
• 平方取中法
• 折叠法（叠加法）
• 随机数法

4. 哈希冲突的解决
   选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突。

• 链接法（拉链法）
  将所有关键字为同义词的结点链接在同一个单链表中。

若选定的散列表长度为 m,则可将散列表定义为一个由m个头指针组成的指针数组 T[0..m-1] 。
凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。 T 中各分量的初值均应为空指针。T 中各分量的初值均应为空指针。

• 开放定址法

4.2 哈希表（散列表）

• 哈希表是实现关联数组（associative array）的一种数据结构，广泛应用于实现数据的快速查找。

用哈希函数计算关键字的哈希值（hash value）,通过哈希值这个索引就可以找到关键字的存储位置，即桶（bucket）。在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。

查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素：

1. 哈希函数是否均匀；
2. 处理冲突的方法；
3. 哈希表的加载因子。

哈希表的加载因子和容量决定了在什么时候桶数（存储位置）不够，需要重新哈希。加载因子太大的话桶太多，遍历时效率变低；太小的话频繁 rehash，导致性能降低。所以加载因子的大小需要结合时间和空间效率考虑。

例子：
桶不是在扩容时产生的，而是一个新元素在通过哈希计算后得到的一个新位置。 哈希函数合适的情况下，当然是使用哈希函数进行计算的元素越多桶就越多喽，举个极端的例子：HashMap 默认容量的情况下，如果加载因子为 0.1 ，只能放一个 16 * 0.1 = 1 个元素，哈希计算后一定就只有一个桶。那如果加载因子是 0.75，16 * 0.75 = 12 个元素，哈希计算后的桶基本上比 加载因子为 0.1 的多喽，你看是不是。 2. 桶多了单链表长度是短一些，但是这是不发生冲突的前提，如果哈希函数选择的不够合适，太多元素经过哈希计算可能会多次冲突，这样即使桶多了，也不能避免某个链表过长的情况。

4.3 哈希表，哈希函数详细讲解

哈希表，哈希函数详细讲解