Akiq2016/blog

《大话数据结构》 读书笔记

Opened this issue · 5 comments

Akiq2016 commented

大话数据结构

  • 数据结构绪论
  • 算法
  • 线性表
  • 栈与队列
  • 串
  • 树
  • 图
  • 查找
  • 排序
Akiq2016 commented

数据结构

相互之间存在 一种或多种特定关系的 数据元素 的集合

逻辑结构

  1. 集合结构。
# 数据元素除了同属于一个集合外，彼此之间没有其他关系。
[1, 2, 3, 4, 5]
  1. 线性结构。
# 数据元素是一对一关系。
1->2->3->4->5->6
  1. 树形结构。
# 数据元素存在一对多关系。
         A
    /    |    \
   B     C     D
 / | \   |     / \
E  F  G  H    I   J
  1. 图形结构。
# 数据元素多对多关系。
         1
      /     \
     2 - 5 - 3
   / \   | \   \
  4 - 8  |  7 - 6
   \   \ |  /  /
         9

物理结构(存储结构)

数据的逻辑结构在计算机中的存储形式。（顺序存储、链式存储）

  • 顺序存储
    把数据元素存放在地址连续的存储单元。数据间的逻辑关系和存储关系一致。
  • 链式存储
    把数据元素存放在任意的存储单元。这组存储单元可以是连续或不连续的。数据间的存储关系不能反映逻辑关系。需要指针存放数据元素地址。

数据类型

一组性质相同的值的集合及定义在此集合上的一些操作的总称。

抽象数据类型 (Abstract Data Type, ADT)

一个数学模型及定义在该模型上的一组操作。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。

Akiq2016 commented

算法

解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。

输入输出：0个或多个输入，至少有1个或多个输出

有穷性：指算法在执行有限步骤后，自动结束，不会出现无限循环，且每个步骤在可接受时间范围完成。

确定性：每个步骤都具有明确含义。

可行性：每步骤必须是可行的。

设计算法应该尽量满足时间效率高和存储量低的需求

算法效率的度量方法

抛开计算机硬件、软件的因素，一个程序的运行时间，依赖于算法的好坏 和 问题的输入规模。（问题输入规模是指输入量的多少）

举个例子：假设输入规模n为100000

// 算法1
// 运算时间平均约6ms
// 核心代码执行量n次 f(n) = n
console.time()
var sum = 0, n = 100000
for (let i = 0; i <= n; i++) {
  sum = sum + i
}
console.log(sum)
console.timeEnd()
// 算法2
// 运算时间约0.3ms
// 核心代码执行量1次 f(n) = 1
console.time()
var sum = 0, n = 100000
sum = (n + 1) * n / 2
console.log(sum)
console.timeEnd()
// 算法3
// 运算时间约????ms 浏览器炸了
// 核心代码执行量n^2次 f(n) = n^2
console.time()
var sum = 0, x = 0, n = 100000
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    x++
    sum = sum + x
  }
}
console.log(sum)
console.timeEnd()

随着n值的增大，以上不同的算法在时间效率上的差异也越来越大。

函数的渐进增长：给定两个函数f(n) g(n)，如果存在一个整数N，使得对于所有 n > N，f(n) 总是比
g(n) 大，则 f(n) 的增长渐近快于 g(n)。

最高次项相乘的常数并不重要。
最高次项的指数大的，函数随着n的增长，结果也会变得增长特别块
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

次数 算法C (4n+8) 算法C1 (n) 算法D (2n^2+1) 算法C1 (n^2)
n = 1 12 1 3 1
n = 2 16 2 9 4
n = 3 20 3 19 9
n = 10 48 10 201 100
n = 100 408 100 20001 10000
n = 1000 4008 1000 2000001 1000000

算法时间复杂度

算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。

算法执行时间随输入规模n的增大而增大。算法执行时间的增长率和 f(n) 的增长率相同。

推导大 O 阶方法

  1. 用常数 1 取代运行时间中的所有加法常数
  2. 在以上基础修改的函数中，只保留最高阶项
  3. 如果最高阶存在且不为1，去除与该项相乘的常数

得到的结果就是大 O 阶

常数阶

以下运行次数函数是f(n) = 3，根据大 O 阶推导，则有T(n) = O(f(n)) = O(3) = O(1)

var sum = 0, n = 100
sum = (1 + n) * n / 2
console.log(sum)

以下运行次数函数是f(n) = 6，根据大 O 阶推导，则有T(n) = O(f(n)) = O(6) = O(1)

var sum = 0, n = 100
sum = (1 + n) * n / 2
sum = (1 + n) * n / 2
sum = (1 + n) * n / 2
sum = (1 + n) * n / 2
console.log(sum)

以上这样与输入n的规模大小无关，执行时间恒定的算法，我们称为具有O(1)的时间复杂度，即常数阶。

线性阶

我们要分析算法的复杂度，关键就是要分析循环结构的运行情况

以下时间复杂度T(n) = O(n)
简单例子1:

var i
for (i = 0; i < n; i++) {
  // T(n) = O(1) 的程序步骤序列
}

简单例子2:
遍历块可以理解为$\frac{n}{2}$，而递归块是$f(\frac{n}{2})$。而递归块又可以继续拆成具体的 $\frac{n}{4}$ 、 $f(\frac{n}{4})$，以此类推。最后如以下公式：
$$
f(n) = \frac{n}{2} + f(\frac{n}{2})
$$
$$
f(n) = \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + ... <= n
$$

function onFunc(n) {
  if (n <= 1) return;
  let mid = n / 2;

  [...Array(n - mid - 1)].forEach((_) => {
    let a = 1;
  })

  onFunc(mid);
}

对数阶

有x个2相乘后大于n则退出循环，即$2^x = n$ => $x = log_2n$。所以T(n) = O(log n)

var count = 1
while (count < n) {
  count = count * 2
}

平方阶

循环的时间复杂度等于循环体的复杂度 * 该循环运行的次数

以下为$O(n^2)$

// example 1
var i, j
for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    // O(1)
  } 
}

以下例子中，当i = 0，内循环执行n次，i = 1，内执行n - 1 …… i = n - 1，内执行1次。则总执行次数为
$$
n + (n - 1) + (n - 2) + ... + 1 = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}
$$
则T(n) = O(n^2)

// example 2
var i, j
for (i = 0; i < n; i++) {
  for (j = i; j < n; j++) { // 注意：j = i
    // O(1)
  } 
}

以下例子的推导为
$$
f(n) = n + n^2 + \frac{n(n+1)}{2}
$$
$$
T(n) = O(n^2)
$$

function test (count: number): void {
  for (let j = 0; j < count; j++) {
    // O(1)
  }
}

test(n) // 1, 执行n
let i, j
for (i = 0; i < n; i++) { // 2. 执行 n^2
  test(n)
}
for (i = 0; i < n; i++) { // 3. 执行 n(n + 1) / 2
  for (let j = i; j < n; j++) {
    // O(1)
  }
}

指数阶

以下为$O(2^n)$

function recursive(n) {
  if (n <= 1) return n;
  return recursive(n - 1) + recursive(n - 1);
}

参考常见复杂度：

执行次数函数 阶
$12$ $O(1)$
$2n+3$ $O(n)$
$3n^2+2n+1$ $O(n^2)$
$5log_2n+20$ $O(log n)$
$2n+3n log_2n+19$ $O(n log n)$
$6n^3+2n^2+3n+4$ $O(n^3)$
$2^n$ $O(2^n)$

从小到大耗时排序：
$$
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
$$

算法的空间复杂度通过计算算法所需的存储空间实现。S(n) = O(f(n))。n为输入规模，f(n)为语句关于n所占存储空间的函数。

Akiq2016 commented

线性表

零个或多个数据元素的有限序列

线性表的数据对象集合为 {a1, a2, ......, an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每个元素有且只有一个直接前驱元素，除了最后一个元素an外，每个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

  1. 是个序列：元素之间有顺序
  2. 是有限的：计算机中处理的对象都是有限的

线性表元素的个数n（n >= 0）定义为线性表的长度。n = 0 时，称为空表。

顺序存储结构的插入与删除

// 操作结果：在arr中第index个位置之前插入新的元素ele，arr的长度加1
function insertArrayItem ({arr, maxLength, index, ele}) {
  // 顺序线性表已满
  if (arr.length >= maxLength) return false

  // 当index不在范围内
  if (index < 0 || index > maxLength - 1) return false

  // 若插入数据位置不在表尾
  if (index !== maxLength - 1) {
    // 将要插入的位置后数据元素向后移动一位
    for (let j = arr.length; j > index; j--) {
      arr[j] = arr[j-1]
    }
  }
  arr[index] = ele
  return arr
}

// 删除的demo省略

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)，而插入或删除时，时间复杂度都是O(n)。这说明它比较适合元素个数不太变化，而更多是存取数据的应用。

链式存储结构

顺序存储在插入和删除时需要移动大量的元素，耗费时间。链式存储结构可以解决这个问题。链式结构中，除了存储数据元素信息的域（数据域），还要存储它的后继元素的存储地址（相对的域为指针域，指针域中存储的信息成为指针或链）。

// 单链表的插入
// 在顺序线性表L中的第i个位置之前插入新的数据元素e，L的长度加1
// 瞎写
function DistInsert (L, i, ele) {
  let j = 0
  let p = L[j]

  // 寻找第i个节点
  while(p && j < i) {
    ++j
    p = L[j]
  }

  // 第i个元素不存在
  if(!p || j > i) {
    throw new Error
  }

  // 将p的后继赋给新元素的后继
  ele.next = p.next
  // 将新元素赋值给p的后继
  p.next = ele

  return true
}
// 删除的demo省略

单链表的插入和删除算法由两部分组成：第一部分就是遍历查找第i个元素O(n)，第二部分就是插入或删除元素O(1)。从整个算法来说，他的时间复杂度是O(n)。对于插入或删除数据越频繁的操作，单链表的效率优势越是明显。

单链表结构和顺序存储结构的优缺点

存储分配方式

  1. 顺序存储用一段连续的存储单元一次存储线性表的数据元素
  2. 单链表采用链式存储结构，有一组任意的存储单元存放元素

时间性能 - 查找

  1. 顺序存储O(1)
  2. 单链表O(n)

时间性能 - 插入删除

  1. 顺序存储结构需要平均移动表长一半的元素O(n)
  2. 单链表找出具体位置指针后，删除或插入时间O(1)

空间性能

  1. 顺序存储需要预分配存储空间，分大了浪费，分小了溢出
  2. 单链表不需要预分配存储空间，元素个数也不受限制

总结

  • 线性表
    • 顺序存储结构
    • 链式存储结构
      • 单链表
      • 静态链表
      • 循环链表
      • 双向链表
Akiq2016 commented

栈与队列

栈 (stack) 是限定仅在表尾进行插入和删除操作的线性表。(Last In First Out)

顺序栈与链栈

栈是栈顶来做插入和删除。这使得栈底是固定的。最先进栈的只能在栈底。

栈的顺序存储结构。下标为0的一段作为栈底。栈的插入——进栈。栈的删除——出栈。

顺序栈和链栈的时间复杂度是一样O(1)。顺序栈需要事先确定固定长度。可能会内存空间浪费。但存去定位方便。链栈要求每个元素有指针域，增加内存开销，但对栈长度没有限制。

如果栈的使用过程元素变化不可预料，用链栈。反之，变化在可控范围，用顺序栈。

斐波那契数列

栈很重要的应用是实现了递归。经典递归例子：斐波那契数列(Fibonacci)

假设一对兔子出生两个月后，每个月生一对兔子。假设所有兔子不死，一年后可以繁殖多少对兔子。

所经月数 1 2 3 4 5 6 7 8 9 10 11 12
兔子对数 1 1 2 3 5 8 13 21 34 55 89 144

前面相邻两项之和，构成后一项。

// 常规的迭代写法
function main1 () {
  let arr = []
  for (let i = 0; i < 40; i++) {
    if (i < 2) arr[i] = i == 0 ? 0 : 1
    else arr[i] = arr[i-2] + arr[i-1]
    console.log(arr[i])
  }
}
// 递归写法
function main2 () {
  let Fbi = (i) => {
    if (i < 2) return i == 0 ? 0 : 1
    return Fbi(i - 2) + Fbi(i - 1)
  }
  for (let i = 0; i < 40; i++) {
    console.log(Fbi(i))
  }
}

我们把一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称作递归函数。

写递归最怕无穷递归，所以每个递归定义必须至少有一个条件，满足时递归不再进行，即不再继续引用自身，而是返回值退出。

大量递归调用会建立函数副本，耗费时间和内存；迭代不需要反复调用函数和占用额外内存。

队列(queue)是只允许在一端进行插入操作、在另一端进行删除操作的线性表。(First In First Out)

允许插入的一端叫队尾，允许删除的一端叫队头。

队列的顺序存储

入队列操作，即队尾追加一个元素，不需要移动任何元素。时间复杂度O(1)

队列元素的出列在队头，即下标为0的位置，删除元素，其他元素全部向前移动。时间复杂度O(n)

如果不限制队列元素必须存储在数组前n个单元中，也就是队头不需要一定在下标为0的位置。使用front指针指向队头元素，rear指针指向队尾元素的下一个位置。(为空队列时，front等于rear。)此时出列入列的时间复杂度都为O(1)。但是由于出列后，后面的元素没有向前移动，导致入列可能会产生数组越界的情况。称为“假溢出”。

循环队列

假溢出的解决办法就是，后面满了就再从头开始，也就是头尾相接的循环。

队列的这种头尾相接的顺序存储结构称为循环队列。

但是循环队列还是会面临数组溢出的问题。

队列的链式存储

就是线性表的单链表，但是只能尾进头出，简称为链队列。

Akiq2016 commented

串

串(string)是由零个或多个字符组成的有限序列，又称字符串。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。
串中常见操作比如：查找子串位置、得到指定位置子串、替换子串等操作。

串的比较

串的比较是通过组成串的字符之间的编码来进行的。字符的编码指的是字符在对应字符集中的序号。

串的存储结构

顺序存储结构 链式存储结构