基本数据结构

• 基本数据结构

  • TODO:

  • 栈

    • 栈的实现

    • 栈要记录的数据

    • 栈的操作

    • 栈的应用

  • 队列

    • 队列的实现

    • 队列要记录的数据

    • 队列的操作

  • 链表

    • 链表种类

    • 链表节点（Node）记录的数据

    • 链表（LinkedList）记录的数据

    • 链表的操作

    • 哨兵（sentinel）

    • 指针和对象的实现

  • 树

    • 树的种类

    • 术语

  • 堆

    • 堆需要存储的数据

    • 堆中元素通过坐标来确定父节点、左右子节点，具体来说

    • 堆的分类

    • 堆的操作

  • 树结构与Java实现

  • 参考文献

TODO:

• [ x ] 优先队列

• [ x ] 堆

栈

栈是一种动态集合，它是一种LIFO（last in first out后进先出）结构

栈的实现

1. 数组

2. 链表

栈要记录的数据

1. 栈顶位置top

   注意这个top有两种理解方式，一种是表示栈的最后一个数据的位置，另一种是表示栈的最后一个数据的下一个位置，这两种理解对栈的操作代码有一定的影响

2. 栈最大大小size

栈的操作

1. STACK_EMPTY（）：判断栈是否为空

2. PUSH（X）：向栈中添加一个值，注意栈是否为满的

3. POP（）：从栈中弹出一个值，注意栈是否为空

栈的应用

1. 括号匹配问题

队列

与栈不同，它是一种FIFO（first in first out先进先出）结构

队列的实现

1. 数组

2. 链表

队列要记录的数据

1. 队首位置head：第一个元素位置

2. 队尾位置tail：下一个元素要插入的位置（最后一个元素的下一个位置）

3. 队列最大大小size

队列的操作

1. ENQUEUE（x）：入队

2. DEQUEUE（）：出队

3. EMPTY（）：队列为空，head=tail

4. FULL（）：队列为满，head=（tail+1）%size

链表

与数组中元素地址连续不同，链表中两个元素地址不一定连续，而是由专门的一个指针指明该元素的后一个（前一个）元素的地址

链表种类

1. 单向链表：只有指向后一个元素的指针

2. 双向链表：有指向后一个和前一个元素的指针

3. 循环链表：链表内存在一个环

链表节点（Node）记录的数据

1. 要存储的数据data

2. 下一个节点地址Node* next

3. 若是双向链表还要存储前一个节点地址Node prev

链表（LinkedList）记录的数据

1. 链表的头指针Node head

2. 可能还记录链表的尾指针 Node* tail

链表的操作

1. SEARCH(x)：链表的搜索

2. INSERT(i,x)：链表的插入，在第i个位置插入x

3. DELETE（x）:链表的删除

哨兵（sentinel）

为了减少边界条件的判断（是否为空链表等等），引入哨兵，使得链表永远不为“空”

指针和对象的实现

1. 用二维数组表示指针

   我们可以设置一个n*3的数组记录n个节点，那个3就表示存储的数据、前一个元素的坐标（index）和后一个元素的坐标

2. 用一维数组表示指针

树

树的种类

1. 二叉树

   二叉树要存储4个数据，分别是节点携带的信息和其父节点、左右子节点的指针

2. 分支无限制的有根树

   左孩子右兄弟表示法，这种方法每个节点设置3个指针：父指针、从左数第一个孩子的指针、其右侧相邻的兄弟指针

术语

• 路径

  从某个节点依次到达另外一个节点所经过的所有节点，就是这两个节点之间的路径

• 根

  树顶端的节点被称为根。从根出发到达任意一个节点只有一条路径

• 父节点

  除了根节点之外，每个节点都可以向上找到一个唯一的节点，这个节点就是当前节点的父节点。相应的，父节点下方的就是子节点

• 叶子节点

  没有子节点的“光杆司令”就被称为叶子节点

• 子树

  每个子节点作为根节点的树都是一个子树

• 层

  一个树结构的代数就是这个树的层

• 度

  一棵树中，最大的节点的度称为树的度

• 兄弟节点

  具有相同父节点的节点互称为兄弟节点

堆

堆实际上是以数组形式存储的二叉树

堆需要存储的数据

1. 数组的大小max-size

2. 堆元素个数size，这里size要小于max-size

堆中元素通过坐标来确定父节点、左右子节点，具体来说

一个节点i的父节点：[i/2] 一个节点i的左子节点：[i2] 一个节点i的右子节点：[i2+1]

堆的分类

1. 最大堆

   满足所有节点都比其父节点值小（小于等于）的堆

   A[i/2]>=A[i]

2. 最小堆

   满足所有节点都比其父节点值大（大于等于）的堆

   A[i/2]<=A[i]

堆的操作

1. 维护堆的性质（HEAPIFY）

   这里指维护最大堆或最小堆的性质。假设一个数组中下标为i的节点的子节点满足最大（小）堆性质，但自身不一定满足这个性质，这时就需要HEAPIFY，具体来说是要比较这个节点和其两个子节点的大小，将其中的大（小）的和该节点位置交换，这样这个节点及其两个子节点就满足最大（小）堆的性质了，但是可能交换后子节点不满足堆的性质，所以这里要递归调用HEAPIFY，直到达到最下层节点，这样就维护了堆的性质。

   HEAPIFY耗时O（lgn）

2. 建堆（BUILD-HEAPIFY）

   从中间那个元素开始到第一个元素，逐一调用HEAPIFY函数，即可完成建堆。

   逐一从中间那个元素开始递减而不是从第一个元素递增，这时为了保证每次调用HEAPIFY都能保证该节点的子节点都满足最大（小）堆的性质，否则无法调用HEAPIFY。中间那个元素是第一个可能不满足最大（小）堆性质的节点，所以从这里开始维护（HEAPIFY）。

   建堆的期望时间为O（n）

树结构与Java实现

• 数组特点: 查询迅速,根据index可以快速定位到一个元素

• 对于插入和删除操作频繁的数据，不建议采用有序数组

• 链表的查询效率很低，每次都要从头开始找，依次访问链表的每个数据项

• 对于查找频繁的数据，不建议使用链表

参考文献

• 基本数据结构
• 树结构与Java实现