大话数据结构学习笔记

Saturday, February 20, 2021

[TOC]

绪论

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

程序设计 = 数据结构 + 算法

数据

是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

数据其实就是符号，具备两个前提：

  1. 可以输入到计算机中
  2. 能被计算机程序处理

数据元素

是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点

数据项

一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。

数据对象

是性质相同的数据元素的集合，是数据的字集。

数据结构

是相互之间存在一种或多种特定关系的数据元素的集合。按照视点不同分为逻辑结构和物理结构。逻辑结构是面向问题的，而物理结构是面向计算机的。

逻辑结构

是指数据对象中数据元素之间的相互关系，分为四种：

  1. 集合结构：数据元素除了同属于一个集合外没有其它关系。
  2. 线性结构：数据元素之间是一对一的关系。
  3. 树形结构：数据元素之间存在一种一对多的层次关系。
  4. 图形结构：数据元素是多对多的关系。

物理结构

也叫做存储结构，是指数据的逻辑结构在计算机中的存储形式，分为两种：

  1. 顺序存储：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
  2. 链式存储：把数据元素存放在任意的存储单元里，这组存储单元可以连续也可以不连续。

数据类型

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

**抽象数据类型（Abstract Data Type，ADT）：一个数学模型及定义在该模型上的一组操作。**抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

抽象的意义在于数据类型的数学抽象特性。

抽象数据类型不仅仅指那些已经定义并实现的数据类型，还可以是计算机编程者在设计软件程序时自己定义的数据类型。

一个抽象数据类型定义了：

  1. 一个数据对象
  2. 数据对象中各数据元素之间的关系
  3. 对数据元素的操作

描述数据类型的标准格式：

ADT 抽象数据类型名
DATA
	数据元素之间逻辑关系的定义
Operation
	操作1
			初始条件
			操作结果描述
	操作2
			。。。
	操作n
			。。。
endADT

图示总结

image-20210220182040705 image-20210220182645573

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

  1. 输入：算法具有零个或多个输入。

  2. 输出：算法至少有一个或多个输出，输出的形式可以是打印输出，也可以是返回一个或多个值等。

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

  4. 确定性：算法的每一步骤都具有确定的含义，不会出现二义性。

  5. 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

image-20210220185111661

算法设计的要求

  1. 正确性：算法至少应该具有输入输出和加工处理无歧义性，能正确反应问题的需求，能够得到问题的正确答案。

    算法的正确性大部分情况下都不可能用程序来证明，而是用数学来证明，一版情况下，把下述第三层次作为算法是否正确的标准。

    • 算法程序没有语法错误
    • 算法程序对于合法的输入能够得到满足要求的输出
    • 算法对于非法的输入能够得到满足规格说明的结果
    • 算法对于精心选择甚至刁难的测试数据都有满足要求的输出结果

  2. 可读性：算法设计的另一目的是为了便于阅读、理解和交流。可读性是算法好坏很重要的标志。

  3. 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

  4. 时间效率高和存储量低

算法效率的度量方法

1. 事后统计方法

通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

这种方法明显的缺陷：

  • 必须依据算法事先编制好程序，通常需要花费大量时间和精力，如果结果显示算法糟糕，则竹篮打水一场空。
  • 时间的比较依赖计算机硬件和软件等环境因素，有时候会掩盖算法本身的优劣。
  • 算法的测试数据设计困难，并且程序的运行时间往往与测试规模有很大关系，效率高的算法在小的测试规模上得不到体现

2. 事前分析估算方法

在计算机程序编程前，依据统计方法对算法进行估算。一个用高级程序语言编写的程序在计算机上运行所消耗的时间取决于四个因素：

  • 算法采用的策略和方法：这是算法好坏的根本
  • 编译产生的代码质量：由软件支持
  • 问题的输入规模：输入量的多少
  • 机器执行指令的速度：取决于硬件性能

测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数，运行时间与这个计数成正比。在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。我们在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。

算法时间复杂度

在进行算法分析时，语句总的执行次数 $T(n)$ 是关于问题规模n的函数，进而分析 $T(n)$ 随n的变化情况并确定 $T(n)$ 的数量级。算法的时间复杂度，也就是算法的时间量度，记作 $T(n)=O(f(n))$ 。它表示随问题规模n的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 $f(n)$ 是问题规模n的某个函数。

这样用大写 $O(n)$ 来提现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着n的增大，$T(n)$ 增长最慢的算法为最优算法。

推到大O阶的方法：

  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中，只保留最高阶项。
  • 如果最高阶项存在并且其系数不是1，则去除与这个项相乘的系数。

常见的几个时间复杂度如下，耗费时间依次递增：

  1. 常数阶：$O(1)$
  2. 线性阶：$O(n)$
  3. 平方阶：$O(n^2)$
  4. 对数阶：$O(logn)$
  5. $nlogn$阶：$O(nlogn)$
  6. 立方阶：$O(n^3)$
  7. 指数阶：$O(2^n)$

最坏情况和平均情况

**平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。**但现实情况中，平均运行时间很难分析得到，往往都是通过一定的实验数据估算得到。

时间复杂度分为平均时间复杂度和最坏时间复杂度，一般在没有特殊说明的情况下，都是指最坏时间复杂度。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：$S(n)=O(f(n))$，其中，n为问题的规模，$f(n)$ 为语句关于n所占存储空间的函数。

一个小示例

使用简单的循环加法求和以及高斯公式求和的实现及性能测试。

代码：

// 简单加法，时间复杂度为O(n)
func simpleSum(max int) (sum int) {
	for i := 1; i <= max; i++ {
		sum += i
	}
	return sum
}

// 高斯算法，时间复杂度为O(1)
func gaussSum(max int) (sum int) {
	return (max + 1) * max / 2
}

性能测试：

// 最大数
var max = 100000000

// 期望结果
var wantSum = 5000000050000000

// 简单加法性能测试
func BenchmarkSimpleSum(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if gotSum := simpleSum(max); gotSum != wantSum {
			b.Errorf("gaussSum() = %v, want %v", gotSum, wantSum)
		}
	}
}

// 高斯算法性能测试
func BenchmarkGaussSum(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if gotSum := gaussSum(max); gotSum != wantSum {
			b.Errorf("gaussSum() = %v, want %v", gotSum, wantSum)
		}
	}
}

测试结果：

goos: darwin
goarch: amd64
pkg: gitlab.wcxst.com/jormin/play-with-data-structure/chapter2
BenchmarkSimpleSum
BenchmarkSimpleSum-12    	      43	  25727594 ns/op
BenchmarkGaussSum
BenchmarkGaussSum-12     	1000000000	         0.697 ns/op
PASS

线性表

线性表(List)是零个或多个数据元素的有限序列，有两点需要注意：

  1. 它是一个序列，也就是说，元素之间是有顺序的。
  2. 线性表强调是有限的。

假设当前有个线性表：$(a_1,a_2,…,a_{i-1},a_i,a_{i+1}…a_n)$，则 $a_{i-1}$ 是 $a_i$ 的直接前驱元素， $a_{i+1}$ 是 $a_i$ 的直接后继元素，直接前驱元素和直接后继元素都是最多只有一个，第一个元素没有直接前驱元素，最后一个元素没有直接后继元素。线性表元素的个数 $n(n\geq0)$ 是线性表的长度，n=0 时为空表。$i$ 是 $a_i$ 的位序。

线性表的抽象数据类型定义如下：

ADT 线性表(List)
Data
	线性表的数据对象集合为{a1,a2...an}，每个元素的类型均为 DataType。其中，除第一个元素外，每个元素都有且仅有一个直接前驱元素，除最后一个元素为，每个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(*L)：初始化操作，建立一个空的线性表L。
	ListEmpty(L)：若线性表为空返回true，否则返回false。
	ClearList(*L)：将线性表清空
	GetElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e。
	LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，查找成功返回该元素的序号表示成功，否则返回0表示失败。
	ListInsert(*L,i,e)：在线性表L的第i个位置插入新元素e。
	ListDelete(*L,i,*e)：删除线性表L的第i个位置的元素，并用e返回其值。
	ListLength(L)：返回线性表L的元素个数。
endADT

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表 $(a_1,a_2,…,a_{i-1},a_i,a_{i+1},…,a_n)$ 的顺序存储示意图如下：

image-20210222142352190

线性表的下表是从 1 开始，和编程序言中数组从 0 开始不同，对于第 $i$ 个数据元素 $a_i$ 的存储位置可以由 $a_1$ 推算得出：

$LOC(a_i) = LOC(a_1) + (i-1)*C$

因此，对于线性表中任意位置的元素的存入或者取出数据，时间复杂度都是 $O(1)$，具有这一特点的存储结构称为 随机存取结构。

线性表的顺序存储结构，在读数据时，时间复杂度为 $O(1)$，插入或者删除时，时间复杂度为 $O(n)$。

优点

  1. 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  2. 可以快速地读取表中任意位置的元素

缺点

  1. 插入或者删除操作需要移动大量元素
  2. 当线性表长度变化较大时，难以确定存储空间的容量
  3. 造成存储空间的“碎片”

线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在未被占用的任意位置。

链式存储结构中，对每一个数据元素来说，除了存储本身的信息之外，还需要存储其直接后继的存储位置。

术语

**数据域：**存储数据元素信息的域

**指针域：**存储直接后继位置的域，其中存储的信息称为指针或链

**结点(Node)：**数据域和指针域组成的存储映像

**线性存储结构：**n个结点链结成的链表

**单链表：**每个结点只包含一个指针域的链表

**头指针：**链表中第一个元素的存储位置

**头结点：**有时为了方便，会在单链表的第一个结点前增加一个数据域为空的结点来做头结点，它的数据域可以为空或者存储其它的信息

头指针和头结点的区别

头指针：

  1. 头指针式指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
  2. 头指针具有标记作用，所以常用头指针冠以链表的名字
  3. 无论链表是否为空，头指针都不为空，头指针是链表的必要元素

头结点:

  1. 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
  2. 有了头结点，对在第一元素结点前插入结点和删除地一结点，其操作与其他结点的操作就统一了
  3. 头结点不一定是链表必需要素

图示

  1. 空链表

    image-20210222163754605

  2. 不带头结点的单链表

    image-20210222165148215

  3. 带有头结点的单链表

    image-20210222165100516

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

存储分配方式

- 顺序存储结构：用一段连续存储单元依次存储数据元素
- 单链表结构：用一组任意的存储单元存储数据元素

时间性能

  • 查找：

    • 顺序存储结构：$O(1)$
    • 单链表：$O(n)$

  • 插入和删除：

    • 顺序存储结构：$O(n)$
    • 单链表：$O(n)$，如果找到位置后频繁操作，这些操作的复杂度为$O(1)$

空间性能

  • 顺序存储结构：预先分配空间，分大了浪费，分小了容易发生上溢
  • 单链表：不需要预先分配存储空间，只要有空间就可以分配，元素个数也不受限制

结论

  • 若线性表需要频繁查找，插入和删除操作较少，宜采用顺序存储结构
  • 若线性表元素个数变化较大或不知道元素个数时，宜采用单链表结构

静态链表

静态链表是用数组描述的链表，和顺序存储结构不同的是，静态链表中的数组元素都有两个数据域：data 和 cur，data 用来存放数据，cur 用来存放该元素下个元素在数组中的下标，cur 称为 游标。

备用链表：未被使用的数组元素

静态链表的首尾元素做特殊处理，不存数据。首元素的 cur 存放的是第一个备用链表的下标。尾元素的 cur 存放的是第一个有数值元素的下标，相当于单链表的头结点，当整个链表为空时，则为0。

初始化的静态链表示例图如下：

image-20210223152036767

有数据的静态链表的示例图如下：

image-20210223152519057
DataStructure DataStructure

k8s搭建ELKlinux使用speedtest测试网速