avatar

目录
数据结构C++版

实验环境

环境名 环境值
操作系统 Win10, Windows Subsystem for Linux(WSL)
子系统版本 Ubuntu20.04
gcc 版本 (标准) 9.3.0 (c17)
g++版本 (标准) 9.3.0 (c++17)
编辑工具 Visual Studio Code

什么是数据结构

  • 数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。
  • 数据的逻辑结构和物理结构是数据结构的两个密切相关的方面,同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构,而算法的实现依赖于指定的存储结构。
  • 数据结构的研究内容是构造复杂软件系统的基础,它的核心技术是分解与抽象。通过分解可以划分出数据的 3 个层次;再通过抽象,舍弃数据元素的具体内容,就得到逻辑结构。类似地,通过分解将处理要求划分成各种功能,再通过抽象舍弃实现细节,就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体(即具体问题)到抽象(即数据结构)的过程。然后,通过增加对实现细节的考虑进一步得到存储结构和实现运算,从而完成设计任务。这是一个从抽象(即数据结构)到具体(即具体实现)的过程。

FAQ

Q1: 为什么要学数据结构

  • 承前启后:学语言->学算法->写程序
  • 高级计算机程序设计的理论指导
  • 提升编程能力
  • 面试中经常问到

Q2:有哪些数据结构

  • 线性表、栈、(字符)串、数组、广义表、树、二叉树、图
  • 重点是线性表、二叉树
  • 对于每种数据结构会讲解其添加、更新、删除、查询、排序等操作的实现

Q3:学习境界

  • 境界一 知道理论、算法思路
  • 境界二 完成主要数据结构的基本算法实现(入门)
  • 境界三 更多数据结构,更多算法的实现(进一步提高数据结构功底)
  • 境界四 融会贯通、举一反三,在后续开发中综合应用数据结构知识

绪论

算法

algorithm 英[ˈælɡərɪðəm] 美[ˈælɡərɪðəm]

什么是算法

For Example: 求 1+2+3+…+100 = ?

  1. 依次相加
c
1
2
3
4
5
int res = 0;
for(int i = 0; i <= 100; i++){
res += i;
}
cout << res << endl;
  1. 高斯求和
c
1
2
3
4
5
6
int res = 0;
int add_max = 100;
/* 梯形面积公式算法 */
res = (1 + add_max) * add_max / 2;
/* 三角形面积公式算法 (0+1+2+...+100, h = 101)*/
res = add_max * (add_max + 1) / 2;
  1. 递归
c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
sum(100) = sum(99) + 100
sum(99) = sum(98) + 99
=>
sum(100) = sum(98) + 99 + 100
...
sum(100) = sum(1) + 2 + ... + 99 + 100
*/
int sum(int m){
if(m > 1){
return sum(m-1) + m;
}else{
return 1;
}
}
int main(int argc, char *argv[]){
cout << sum(100) << endl;
return 0;
}

以上 3 个算法显然高斯求和算法的时间复杂度及空间复杂度最优

算法特征

  1. 输入
  2. 输出
  3. 可行性
  4. 有穷性
  5. 确定性

时间复杂度(Time Complexity)定义

  • (1)时间频度:$T(n)$,$n$ 表示问题的规模。一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$。
  • (2)时间复杂度:一般情况下,算法中基本操作重复执行的次数是问题规模 n 的某个函数,用 T(n)表示,若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,$T(n)/f(n)$的极限值为不等于零的常数,则称 $f(n)$是 $T(n)$的同数量级函数。记作 $T(n)=O(f(n))$,称 $O(f(n))$ 为算法的渐进时间复杂度,简称时间复杂度。在 $T(n)=4n^2-2n+2$ 中,就有 $f(n)=n^2$,使得 $T(n)/f(n)$的极限值为 4,那么 $O(f(n))$,也就是时间复杂度为 $O(n^2)$
  • 时间复杂度一般讨论最坏的时间复杂度
  • 定义 $O$(最坏情况<=),例如 $T(n) = O(n^2)$
  • 定义 $\Omega$(最好情况>=),例如 $T(n) = Ω(n^2)$
  • 定义 $\omicron$(最好情况与最坏情况同阶),例如 $T(n) = \omicron(n^2)$

时间复杂度的计算

  1. 找出算法中的基本语句。执行次数最多的就是基本语句,通常是最内层循环的循环体
  2. 计算基本语句的执行次数的数量级
  3. 用 $O$ 表示
  • 一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$。
  • 一般情况下,算法中基本操作重复执行的次数是问题规模 $n$ 的某个函数,用 $T(n)$ 表示,若有某个辅助函数 $f(n)$,使得当 $n$ 趋近于无穷大时,$T(n)/f(n)$ 的极限值为不等于零的常数,则称 $f(n)$ 是 $T(n)$ 的同数量级函数。记作 $T(n)=O(f(n))$,称 $O(f(n))$ 为算法的渐进时间复杂度,简称时间复杂度。
  • 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为 $O(1)$,另外,在时间频度不相同时,时间复杂度有可能相同,如 $T(n)=n^2+3n+4$ 与 $T(n)=4n^2+2n+1$ 它们的频度不同,但时间复杂度相同,都为 $O(n^2)$。

时间复杂度计算例题

    1. $T(n) = 1, T(n) = O(1)$
c
1
int count = 0;

$100 个简单语句其时间复杂度仍为 O(1)$

    1. 一个循环的时间复杂度为 $O(n)$
c
1
2
3
4
int n = 8, count = 0;
for(int i = 0; i <= n; i++){
count++;
}

$T(n) = n, T(n) = O(n)$

    1. 时间复杂度为 $O(log_2(n))$
c
1
2
3
4
int n = 8, count = 0;
for(int i = 0; i <= n; i*=2){
count++;
}

$1,2,4,8,16,32,…$
$设循环 x 次,则 2^x = n => x = log_2(n)$
$T(n) = log_2(n)$
$T(n) = O(log_2(n))$

  1. 时间复杂度为 $O(n^2)$
c
1
2
3
4
int n = 8, count = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
count++;

$T(n) = n \times n$
$T(n) = O(n^2)$

  1. 时间复杂度为 $O(nlog_2(n))$
c
1
2
3
4
int n = 8, count = 0;
for(int i = 0; i <= n; i*=2)
for(int j = 0; j <= n; j++)
count++;
  1. 时间复杂度为 $O(n^2)$
c
1
2
3
4
int n = 8, count = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= i; j++)
count++;

$T(n) = n \times (1+2+3+…+n) = 0.5n + 0.5n^2$
$T(n) = O(n^2)$

常用的时间复杂度级别

常用的时间复杂度级别

空间复杂度(Space Complexity)定义

类似于时间复杂度的讨论,一个算法的空间复杂度 $S(n)$ 定义为该算法所耗费的存储空间,它也是问题规模 $n$ 的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地"进行的,是节省存储的算法,有的算法需要占用的临时工作单元数与解决问题的规模 $n$ 有关,它随着 $n$ 的增大而增大,当 $n$ 较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。

$S(n) = O(g(n))$

  1. 空间复杂度 $O(1)$ 。如果算法执行所需要的临时空间不随着某个变量 n 的大小而变化,即此算法空间复杂度为一个常量,可表示为 $O(1)$
    举例:
c
1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

  1. 空间复杂度 $O(n)$
c
1
2
3
4
5
6
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}

这段代码中,第一行 new 了一个数组出来,这个数据占用的大小为 $n$,这段代码的 2-6 行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 $S(n) = O(n)$

由此可见,递归算法效率低,体现在空间复杂度高。


线性表(linearlist)

顺序表

顺序表实现线性表(代码)

  • 基于数组
  • 表初始容量为$2$
  • 支持动态扩容,扩容策略为$2^{n+1}$, $n$为第几次扩容
  • 扩容时拷贝整块内存,效率更高
  • 扩容时计算新的容量采用移位操作,效率更高
  • 重载函数, 调用灵活
  • 算法具有更高的容错和自动纠错性

链表

静态链表

单(向)链表(无头结点)

双(向)链表(有头结点)

循环单链表(有头结点)

循环双链表(有头结点)

正在更新…

文章作者: Bill
文章链接: http://blog.webpro.ltd/2020/08/13/study-datastructure-linux-c/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Bill's blog

评论