Stay hungry,Stay foolish!

0%

数据结构之储论

在学习数据结构的第一步,就是需要先把相关概念理解清楚。先把理论基础打好,大概了解整个数据结构知识体系框架,一来就上手要写代码可能会走很多弯路,因此打算利用空闲时间先再把之前学过的知识梳理一下。

1 基本概念和术语

1.1 数据

我们现实生活中的绝大多数事物都可以用数据来表示,比如学生信息,一个小区内的居民数量等,这些数据能够输入到计算机中并被计算机识别和处理。

1.2 数据元素和数据项

数据元素是数据的基本单位,通常当成一个整体来处理。比如在学校中,一个学生信息就可以看成一个整体,里面包含了很多信息,如姓名,性别,学号等,这些信息就是数据项。数据项是构成数据元素的最小单位,也就是不能再分割了,又比如在登陆表中,用户名username已经不能再分割成其他数据了,它作为一个最小单元存储在计算机中。

112020-3-15-17-20-6

三者关系

122020-3-15-17-20-11

1.3 数据对象

数据对象是具有相同性质的数据元素的集合。比如A公园湖里面的所有鸭子的集合,它们是由相同性质(都是小鸭子)组成的集合。

132020-3-15-17-20-16

1.4 数据类型

数据类型是一个值的集合和定义在这个集合上的一组操作的总称。简单讲就是“值+操作集”。如常见的基本数据类型,int,float等。

1.5 抽象数据(ADT)类型

抽象数据类型只是比上面的数据类型多了一个“抽象”,这个“抽象”的意思是与具体实现无关,它是一种概念性的东西,是一个模型,它并不规定具体的实现。通常用(数据对象,数据关系,基本操作集)来表示抽象数据类型。ADT可以表示一个数据结构。

1.6 数据结构

在实际问题中,数据元素之间是存在某种关系的,比如大小关系,排列关系等。他们之间的关系就成为结构。数据结构是相互之间存在的一种或者多种特定关系的数据元素的集合。包含三个方面:
1)逻辑结构
2)存储结构
3)数据的运算
有时候比较两个数据结构是否一样,则需要比较这三个方面,只有三者都一致,才算是一样的数据结构。

数据结构的三要素

1.6.1 逻辑结构

逻辑结构是一种模型设计,跟具体的实现没有关系,可以用不同的计算机语言去实现。
逻辑结构分为两大类:线性结构和非线性结构。

插入逻辑结构图

1.6.2 存储结构

存储结构就是物理结构,它是需要将数据存储到具体的物理机上的。主要的存储结构如下4种:

1)顺序存储

逻辑上相连的物理上也相连,一个接着一个存储在存储空间中。

优点:随机存取,存储密度高。比如要取第5个元素的值,立马就能通过首地址+相对地址值找到了,也不需要存储指针等其他东西,一个存储单元就只存储要存的数据。

缺点:只能用相邻的一整块存储单元,造成了很大外部碎片。插入数据和删除数据可能会造成大量的数据移动,消耗大量时间。

如果业务场景不需要频繁的插入删除元素,更多时候使用来查询,那用这个就不错。

2)链式存储

链式存储也是为了解决顺序存储所带来的问题,有时候并不需要一整块大的空间,这对存储空间有一定的要求。如果我们只是为了维持数据的一个前后关系,可以另外增加一个信息来存储这个关系,这就是指针。前一个存储单元里面留下一点空间,存下下一个存储单元的地址。那么到时候就可以通过找地址的方式,找到下一个数据。

优点:不会产生碎片现象,增加删除一个元素不需要移动大量元素。

缺点:只能顺序存储,比如我要读取第5个数据,那么你必须从第一个数据开始找起。指针占用了额外的空间。

142020-3-15-17-20-24

3)索引存储

跟我们查字典一样,通过目录里面的偏旁部首找汉字。索引存储也是如此,它建立一个索引表,在以后的查询数据中,只需要去索引表里面找,就能找到相对应的位置。

优点:检索速度快。

缺点:增加了额外的索引表,当增删元素的时候,同样要去维护这张索引表,特别是当数据量很大的时候,比较耗时间。

152020-3-15-17-20-37

4)散列存储

在上面的三种存储结构中,地址和关键字没什么关系,而散列存储中元素的地址值是根据关键字计算得出的。设计一个散列函数,直接通过数据值来计算这个数据存放的位置。

优点:检索速度快,增加和删除也很快。

缺点:如果散列函数设计不好,会造成冲突。

1.6.3 数据的运算

数据运算的定义是针对逻辑结构的。

数据运算的实现是针对存储结构的。

2 算法和算法评价

2.1 基本概念

算法:算法是对特定问题求解步骤的一种描述。

算法的五个特性:
1)有穷性:不能有无限的解决步骤,这样是得不出问题答案的。
2)确定性:步骤不能有歧义,要能唯一确定应该怎么做,1+1就是等于2,不能1+1有时候等于2,有时候又等于3。
3)可行性:是可以通过这些步骤描述来实现一个算法的。
4)输入:算法可以不需要输入数据。
5)输出:但是算法必须至少有一个输出,没有输出的算法是没有意义的。

2.2 算法效率的度量

算法效率主要从两方面考虑:时间复杂度和空间复杂度。

基本概念:

T(n):算法中所有语句一共被执行了多少次,它是该算法问题规模 n 的函数,注意这里:问题规模一直是n。

时间复杂度不考虑细节,主要研究T(n)的数量级。即 $T(n) = O(f(n))$

算法时间复杂度不仅依赖问题规模n,还取决于输入数据的性质。

计算时间复杂度的时候常用到以下两个规则:
1)加法规则:$T(n)=T_1(n)+T_2(n)=T(max(T_1(n),T_2(n)))$
2)乘法规则:

渐进时间复杂度:

用动图展示如下(图像中显示的图像为上式由小到大)

jianjinhanshu2020-3-15-17-21-19

后面几个函数显示如下(越靠近y轴说明复杂度越高):

jianjinhanshu12020-3-15-17-21-28

3 总结

这些基本概念对于理解后续数据结构的知识尤为重要。思维导图如下:

1 储论2020-3-15-17-39-38

如有不正确的地方,还望指出!及时修改,促进学习!