MY-DATA-STRUCTURE

实现方案和规划

我会使用 python、C 以及 Cpp 来实现这些数据结构，加深对数据结构的理解，以及我的编程能力

对于 Cpp 的实现，我尽量参考 Eigen 库的代码规范，仅仅使用头文件来实现数据结构、并且学习使用一些特性（模板元编程\表达式模板\内联函数）来进行优化

数据结构一览

数据的结构有两种，一种是逻辑结构，一种是存储结构，它们相互独立。同一种逻辑结构，可以有不同的存储结构，不同的存储结构对算法的实现有不同的影响。在设计算法的时候要考虑两者的关系。

数据的逻辑结构表示数据元素之间的相互关系，由数学中的二元关系定义

  • 集合、线性表、树、图
  • 主要是面向问题时，思考选用哪种逻辑结构

数据的存储结构表示数据元素在计算机中的存储方式

  • 顺序存储、链式存储
  • 主要是面向在计算机实现算法时，思考选用哪种存储结构

顺序存储

  • 用一段地址连续的存储单元依次存储数据元素
  • 逻辑上相邻的元素在物理上也相邻，所以逻辑关系和物理关系一致

链式存储

  • 用一组任意的存储单元存储数据元素
  • 逻辑上相邻的元素在物理上不一定相邻，所以逻辑关系和物理关系不一致
  • 需要用存放元素地址的指针来表示元素之间的逻辑关系

算法设计一览

算法都可通过已实现的基本操作运算的有限次执行来实现，必须在有限步后结束，且每步必须在有限时间内完成

枚举法、分治法、贪心法、动态规划、回溯法、分支定界法

使用循环不变式来证明算法的正确性，寻找一个循环中不变的式子进行判断

  • 初始化：循环开始第一次迭代前，循环不变式为真
  • 保持：如果循环开始前循环不变式为真，那么每次迭代后循环不变式仍为真
  • 终止：循环结束时，循环终止时，这个不变式的性质可以帮助我们证明算法的正确性
  • 类似数学归纳法的思想

如何构建循环不变式

  • 观察循环目标，比如排序和查找极值
  • 找出循环中保持不变的属性，比如取出的部分序列是有序的、最大值位置
  • 用数学语言描述这个属性，比如「每次迭代之后，第 k\displaystyle k 个元素是最大值 」
  • 验证三要素，初始化、保持、终止

复杂度分析思路

特定算法的执行工作量、计算成本，受问题规模（输入数据规模 n\displaystyle n）的影响，可以是一种函数关系
于是标记为 T(n)\displaystyle T(n)，表示问题规模为 n\displaystyle n 时，算法的执行工作量或者说计算成本

实际上，计算成本 T(n)\displaystyle T(n) 的具体形式可能受算法的实现往往很复杂，是一个复杂的函数，并且我们更关心问题规模 n\displaystyle n 足够大之后，T(n)\displaystyle T(n) 的增长趋势

所以引入了渐进符号 O\displaystyle O，用 T(n)=O(… )\displaystyle T(n)=O(\dots) 来在当 n\displaystyle n 很大时，用 …\displaystyle \dots 简单表示 T(n)\displaystyle T(n)，并且在工程中我们是更关心算法最坏（也就是计算成本最大）的情况，所以这个 O(… )\displaystyle O(\dots) 通常是 T(n)\displaystyle T(n) 的渐进上界

用数学一点的话说，就是存在一个常数 c\displaystyle c，使得 c⋅(… )≥T(n)\displaystyle c·(\dots)\geq T(n)

对于 O(n)\displaystyle O(n)，最高阶项的系数可以忽略、次高阶项和常数项可以忽略

O(3n2+2n+1)\displaystyle O(3n^{2}+2n+1) --> O(n2)\displaystyle O(n^{2})

常数、对数、多项式复杂度的算法，都是可以接受的，但是指数、阶乘复杂度的算法是不可接受的

首先确定基本操作，然后看基本操作因为控制结构执行多少次

  • 基本操作，比如普通的赋值、比较和数值运算语句操作数是 O(1)\displaystyle O(1)
  • 控制结构，比如循环、递归、分支等，是控制基本操作执行次数的关键
    • 单纯的分支结构，复杂度也是 O(1)\displaystyle O(1)
    • 如果循环次数和 n\displaystyle n 无关，复杂度也是 O(1)\displaystyle O(1)

有循环先看循环，多层循环先看内层循环

  • 结合循环条件看循环的循环次数（使用极限法判断，取两端边界值）
  • 看循环内部的操作数是否和循环条件有关
    • 如果没关，就操作数直接乘循环次数
    • 如果有关就累加 n 个这样的特殊操作数
      • 判断级数类型（记忆）

常见循环内部的操作数和循环条件有关的情况（还有一个循环次数和 n\displaystyle n 无关的假情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
for (i=0; i<n; i++){
	for (j=i; j<n; j++){ 
		// 注意 j 从 i 开始，这层一共循环 n-i 次
		/* O(1) */
	}
}

for (i=0; i<n; i++){
	for (j=1; j<i; j*=2){ 
		// 取极限 j = i 判断，这层一共循环 log2(i) 次
		// j = 2^k, 2^k < i, k < log2(i)
		/* O(1) */
	}
}

for (i=0; i<n; i*=2){
	// 取极限 i = n 判断，这层一共循环 log2(n) 次
	// i = 2^k, 2^k < n, k < log2(n)

	// 下面的循环次数和 n 无关，所以还是 O(1)
	while (j < 10){
		/* O(1) */
		j++;
	}
}

{
	x = n;
	y = 1;
	while (x >= (y-1)*(y-1)){
		// 取极限 x = (y-1)^2 判断
		// 结束时 y = sqrt(n) + 1，而 y 从 1 开始
		// 所以这层一共循环 sqrt(n) + 1 次
		// O(sqrt(n) + 1) --> O(sqrt(n))
		y++;
	}
}

对一些数据结构进行操作，也会涉及到复杂度的分析，这和它们物理存储的结构相关

顺序结构，连续存储，插入时、移动时要复制已经有的元素，复杂度是 O(n)\displaystyle O(n)
但是访问元素的复杂度是 O(1)\displaystyle O(1)

链式结构，要访问未知位置的元素要用指针遍历，复杂度是 O(n)\displaystyle O(n)
但是插入、删除元素只涉及到指针赋值和交换操作，复杂度是 O(1)\displaystyle O(1)

线性表

语法学习记录

template<typename T>的作用域

在C++中，template<typename T>的作用域仅限于紧随其后的类或函数定义。每个模板类或模板函数都需要单独的template<typename T>声明，因为它们是独立的实体。

如果你在一个文件中定义多个模板类或模板函数，每个模板类或模板函数都需要自己的template<typename T>声明。它们不能共享一个template<typename T>声明，因为每个模板类或模板函数的定义需要知道它们将处理的数据类型。

例如，在你的代码中：

1
2
3
4
5
6
7
8
9
template<typename T>
class ListNode {
    // ListNode类的定义
};

template<typename T>
class DoublyLinkedList {
    // DoublyLinkedList类的定义
};

每个模板类都有自己的template<typename T>声明。如果你省略其中一个template<typename T>声明，编译器将无法解析该模板类的定义，并会产生编译错误。

如果template<typename T>不紧挨着接下来的结构定义，它将不会影响该结构。例如：

1
2
3
4
5
template<typename T>
// 这里不能有其他代码
class ListNode {
    // ListNode类的定义
};

如果在template<typename T>和类定义之间插入其他代码，编译器将无法将模板参数与类关联起来，并会产生编译错误。

总之，每个模板类或模板函数都需要自己的template<typename T>声明，并且该声明必须紧挨着类或函数定义。这样编译器才能正确解析模板参数并生成相应的代码。