数据结构基础知识

用来学习最最最基本的数据结构,目前还在更新ing。

绪论

数据

什么是数据?

  • 数据指能输入到计算机中并能被计算机识别处理的符号。

数据的基本单位?

  • 数据的基本单位数据元素

数据元素在不同的场合也称为,记录,节点…..

构成数据元素的最小单位是?

  • 构成数据元素的最小单位是数据项

数据结构

数据结构指相互之间存在一定关系的数据元素的集合,一般分为逻辑结构和存储结构。

Tips: 随机存储结构: 计算任意一个元素的地址花费的时间相同。

逻辑结构

逻辑结构只涉及数据元素之间的逻辑关系,不负责具体数据在计算机中的存储。

一共有三种基本类型:

  • 集合结构
  • 线性结构
  • 树型结构
  • 图结构

存储结构

存储结构又叫物理结构

存储结构是将逻辑结构存入计算机中的一种存储方式。具体的描述了,数据如何存储到计算机中。

通常种:

  • 顺序存储 (同一段的地址必定连续)
  • 链式存储 (同一段的地址可能连续也可能不连续)

算法

什么是算法?

烧菜有菜谱,下棋有棋谱,那么解决问题就有一套解决问题的方法,那种方法就交错算法

算法三个特性和四种描述方式**见下表:

序号 特性 序号 描述方式
1 有穷性(不然死循环了) 1 自然语言描述
2 确定性(不能有二义性) 2 流程图
3 可行性(要能用程序设计语言书写) 3 伪代码(Pseudo-code)
none none 4 程序设计语言

算法分析

衡量算法的效率。一般有两种估计的方法:

  • 事后统计 —> 就是跑跑程序,测测数据。
  • 事前估计 —> 分析估算求复杂度。

复杂度分析

一般只对时间复杂度进行分析。

时间复杂度用$O(n)$来表示。具体求法请看书。

常见时间复杂度:

抽象数据类型(ADT)

抽象数据类型(ADT)代表一系列操作的集合,没有考虑具体的实现。就类似于Interface,这是一种美妙的抽象,因为你可以用ADT+存储结构+具体设计来实现不同的数据类型。
简单的说就是,表ADT定义表或者说线性表的所有行为,然后你就用不同的存储方式实现了顺序表单向链表双向链表…..

对于每种ADT,都可以进行自己的设计与实现,这边只提供参考。

表ADT

定义

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
38
39
40
41
42
43
44
45
46
47
48
List ADT
//数据
每个元素要求具有相同类型,相邻元素有前驱和后继
//操作
Init
输入: 无
功能: 表的初始化
输出: 一个空表
Creat
输入: 元素个数为n的数组arr
功能: 表的初始化,初始化为n个元素,每个元素都按顺序来自数组arr
输出: 无
Destory
输入: 无
功能: 销毁线性表
输出: 无
IsEmpty
输入: 无
功能: 判断表是否为空
输出: 表若为空返回false,否则返回true
GetSize
输入: 无
功能: 求表长
输出: 返回表中的元素个数
Insert
输入: 位置n,要插入的元素add
功能: 将元素add插入到位置n处
输出: 插入成功返回true,否则返回false
DeleteByPosition(const int& );
输入: 位置n
功能: 删除n处的元素
输出: 删除成功返回true,否则返回false
DeleteByValue
输入: 值del
功能: 删除第一次出现的del
输出: 删除成功返回true,否则返回false
FindByPosition
输入: 位置n
功能: 找到并返回处在位置n的元素
输出: 位置n的元素
FindByValue
输入: 元素ele
功能: 寻找元素第一次出现的位置n
输出: 如果找到返回n,否则返回-1
DisplayAllElement
输入: 无
功能: 按照顺序打印所有元素
输出: 无

题外话: 栈和队列一个共同点是只能对线性表的两端进行数据操作,类似阉割版的线性表,但是依旧被广泛使用….

栈ADT

基础结构介绍

类似汉罗塔单个柱子的玩法,遵循先入后出原则(FILO)

定义

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
Stack ADT
//数据
元素数据类型一致
//操作
Init
输入: 无
功能: 初始化栈
输出: 无
Destory
输入: 无
功能: 删除栈
输出: 无
Push
输入: 无
功能: 将元素塞入栈内
输出: 成功塞入返回true,否则返回false
Pop
输入: 无
功能: 弹出栈顶元素
输出: 如果栈顶元素被成功弹出返回true,否则返回false
IsEmpty
输入: 无
功能: 判断栈是否为空
输出: 如果栈为空返回true,否则返回false;
GetTop
输入: 无
功能: 获得栈顶的值
输出: 栈顶存在返回true,否则返回false

队列ADT

基础结构介绍

特性很像排队买汉堡,遵循先进先出原则(FIFO)

定义

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
Queue ADT
//数据
元素数据类型一致
//操作
Init
输入: 无
功能: 初始化队列
输出: 无
Destory
输入: 无
功能: 删除队列
输出: 无
Push
输入: 无
功能: 将元素塞入队列
输出: 成功塞入返回true,否则返回false
Pop
输入: 无
功能: 弹出队头元素
输出: 如果队头元素被成功弹出返回true,否则返回false
IsEmpty
输入: 无
功能: 判断队列是否为空
输出: 如果队列为空返回true,否则返回false
GetFront
输入: 无
功能: 获得队头的值
输出: 队头存在返回true,否则返回false

对上述ADT的实现

还在写ing

字符串

字符串主要介绍它的基本定义模式匹配算法

基本定义

子串: 字符串中任意连续的字符组成的字符序列。
主串: 包含子串的串。
位置: 子串的第一个字符再主串中出现的位置

模式匹配

在主串$S$中寻找$T$的过程称为模式匹配,$T$称为模式。

  • 成功 —-> 返回第一次出现的位置。
  • 失败 —-> 返回0。

BF

最朴素的暴力算法

KMP

推荐博客KMP算法(1):如何理解KMP - 刘毅

多维数组

数组到底是什么?

看书….

压缩

  • 特殊矩阵 [分类]
    • 对称矩阵
    • 三角矩阵
    • 对角矩阵
  • 稀疏矩阵 [具体方法]
    • 三元组
    • 十字链表

参考

数据结构与算法分析—C语言描述(原书第二版) [Mark Allen Weiss 冯舜玺]
数据结构—从概念到C++实现(第三版) [王红梅 王慧 王新颖编著]



--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ