数据结构学习笔记1——概述

开始新的学习之旅了，朋友们准备好了吗？下面的一段时间笔者将和大家一起复习以下数据结构这门基础的课程。

不知道大家有没有跟笔者一样的情况，一直在说数据结构，数据结构，那什么是数据结构呢？

一 概念

先卖个关子，我们来看一个开发中常见的场景：

一个用户在使用我们系统的时候，注册了一个账号，我们在业务处理中根据注册信息，通过一系列处理生成一个User对象。

然后通过save方法保存到数据库中，这样以后我们就可以直接从这个表中读取用户信息了。

好，现在我们来看一下数据结构的概念：

1. 数据结构，英文是data structure，其实名字已经很清晰了。

这是一门专门处理数据的学科，数据元素相互之间的关联称为结构，描述的是存储和组织数据的方式。

按照书中的说法，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

下面我们就继续明确几个概念。

2. 数据：对客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

上面场景中的注册信息，就是数据。数据库中存储的用户记录，那也是数据没跑了。

3. 数据项：数据项是数据的不可分割的最小单位。

这个不用太困惑，如上图所示的用户表中的id，accont，password等每一个字段，都是一个数据项。

4. 数据元素：数据的基本单位，在计算机中作为一个整体进行考虑和处理。一个数据元素由多个数据项组成。

那就比较好理解了，用户表中的每一条User记录就是一个数据元素。

5. 数据对象：性质相同的数据元素的集合，是数据的一个子集。

这里要记住集合这个概念，所有的用户组合到一起是数据对象，所有的女性用户也是一组数据对象。

二 数据结构和数据类型

通常数据结构有四种结构：

1. 集合

2. 线性结构

3. 树形结构

4. 图（网）状结构

上面说都是数据的逻辑关系，数据结构中的物理结构（存储结构）有两种：

1. 顺序存储结构

2. 链式存储结构

下面再介绍一个概念，数据类型——一个值的集合和定义再这个值集上的一组操作的总称。

注意：这个概念中说的，不只包含值的集合，还包含对值集的操作。

数据类型又分为两类：

1. 原子类型：值不可再分割。比如Java中的int，char，String等。

2. 结构类型：由若干成分按某种结构组成，可以被分解。比如一个整型数组，可以循环分割成多个整型元素。

还有两种不太常见的数据类型

1. 抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作，或者我们可以把它理解成我们开发过程中自己定义的数据类型。

笔者认为它与基本数据类型的并没有本质的区别，主要在于抽象数据类型更贴近于实际的使用。

2. 多形态数据类型：指其成分不确定的数据类型，笔者认为这个不太重要，了解一下就可以了。

三 算法和算法分析

算法是对特定问题求解步骤的一种描述，说白了就是我们通过解决问题的程序代码，就可以说是算法。

算法具有以下5个特征：

1. 有穷性：算法必须在执行有限个步骤之后终止。

2. 确定性：算法的每一步骤必须有确切的定义，相同的输入只能得出相同的输出。

3. 可行性：或者叫有效性，每个计算步都可以在有限时间内完成。

4. 输入：一个算法由零个或多个输入。

5. 输出：一个算法有一个或多个输出。

好的算法的评判标准：

1. 正确性：满足具体问题的需求。

2. 可读性：容易被人所理解。

3. 健壮性：对输入的非法数据，能偶适当的进行处理。

4. 效率与低存储量需求：尽量使算法的执行时间越短，运行时占用的空间更小。

算法效率的度量：

1. 事后统计的方法：对运行结果进行统计分析，得出执行效率。

2. 事前分析估算：估算算法的时间复杂度——算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述，如O(1),O(n),O(n²)等，不包括这个函数的低阶项和首项系数。

一般我们最常用的办法是讨论算法在最坏情况下的时间复杂度。

喜欢文章或想一起学习的朋友可以关注我，给我点赞，我将会持续更新，有什么疑问或文中有不当之处请给我留言，真诚地希望能与大家一起交流探讨，学习进步！