对数据结构的学习目标：

  • 掌握数据结构的基本特性。

  • 掌握数据结构的基本操作：增、删、查

    • 增、删 又区分为从什么位置删除，是否会影像后续操作。
    • 查：按照数值查找、按照位置查找。


    基于此，结合算法进行灵活运用。

线性表的增删查

线性表是 n 个数据元素的有限序列，最常用的是链式表。

链表

链表的特征：增和删的复杂度为O(1)，但是查找的复杂度位 O(n)。链表的价值在于它对数据的存储方式是按照顺序的存储。

根据结构和组合方式，除了单向链表外，还有双向链表、循环链表。

链表的常见问题：

  • 链表的翻转：使用三个变量 next、pre、curr
  • 循环链表的判断、获取中间值：使用快慢指针。

栈

栈的特征：先进后出、删除数据时，只能删除（出栈）最后一个、新增（压栈）数据时只能增加在最后。

栈的增删查和链表的复杂性一致。

根据表示方式有两种：用数组表示，即顺序栈。用链表表示即链栈。

栈的典型问题：

  • “{[()]}”
  • 浏览器历史:使用两个栈管理

队列

队列的特征：类似于栈和链表的结合，具有队头（font）和队尾（rear）。具有先进先出的特性。只能从对头删除，只能从队尾添加。

根据组织方式具有依据数组实现的顺序队列和依据链表实现的链式队列和循环队列。

循环队列具有固定长度的特性。

对于增删查的负责度则和链表一致，增删O(1),查 O(n)。

常见问题：

  • 圆桌问题：使用循环链表解决。
  • 在空间方面，要注意区分循环队列和链表队列的区别。

数组

数组的特征：固定长度、固定数据类型、可以通过索引获取。

数组的增和删的时间负责度为O(n)，查询的时间复杂度为 O(1)。

字符串

字符串特征：有序整体，字符串的操作更多是相关于子串和主串的概念。

字符串的实现有两种方式：

  • 顺序存储结构：一组连续的地址
  • 连式结构存储：用一组地址连续的存储单元来存储串中的字符序列。

链式结构在存储上更方便，但是如果涉及到增删查的操作因为子串的概念就不合适了。

对于字符串的增删其时间复杂度为 O(n)。对于子串的查找操作则是 O(nm)。

字符串的问题：

  • 子串查找：两层遍历。
  • 求两个子串的最大公共子串：三层遍历，复杂度 o(nmm)。
  • “the sky is blue” 翻转输出为： “blue is sky the”。

非线性表

树二叉树

树的特征：有点和边组成，描述一对多的关系。

二叉树的特征：每一个节点最多只能有两个子节点。

二叉树的实现方式：

  • 顺序存储法：具有节点 i 的左子节点一定是 2 i ，右子节点一定是 2 i + 1。
  • 链表存储法

二叉查找树：具有节点i 的值 大于左子节，小于右子节点的特性。

树的查找时间复杂度 O(n),增删复杂度为O(1)。

二叉查找树查找时间复杂度 O(logn),增删复杂度为O(1)。

树的主要概念：父节点、节点、叶子节点、子树

二叉树的主要概念：满二叉树、完全二叉树。

主要问题：

  • 二叉查找树的删除：两种方式
  • 字符串的匹配问题：通过构造树来优化查找时间。

哈希表

哈希表的核心思想：通过 地址 = f(关键字)的映射关系实现存储位置的管理。

如何设计哈希函数 即f(关键字) 函数：

  • 第一，直接定制法。比如H(key) = a*key + b，其中 a、b 是常数。
  • 第二，数字分析法。
  • 第三，平法取中法。
  • 第四：折叠法。
  • 第五：除留余数法。

如何解决 hash 冲突：

  • 第一：开放地址法
  • 第二：链表地址法

hash 表的特点：其增删查的时间复杂度都是 O(1)，但是 hash 表没有顺序特性。

hash 的核心在于 hash 函数的实现，以及如何解决 hash 冲突。