图片来源于网络
导读
本节主要描述数据结构与算法的相关基础概念，下面就我在学习上的问题与大家做一个简短分享。
起先学习会有这样的疑惑，基础概念有必要掌握吗？放大一点或许就是理论和实践学习的困惑，因为这不是本文的重点便不再展开，不过，从我的学习和实践经历来看，理论的学习是有必要的。
在以上观点的基础上，又有了问题，那理论掌握到什么程度呢？这个描述起来确实困难，不过单单就“数据结构与算法”而言，掌握常见的基本概念我认为准是没错的，尤其是一些后面学习中时刻包含的内容，理解后，大有裨益。
或许有的同学和我一样不能马上掌握所有的概念，我认为记住或者暂且存下来，在后面的学习实践中再返回来咀嚼也无大碍，不过有一些概念的不明确会影响到后面的理解，我会在本文中重点记录。
程序=数据结构+算法（尼古拉斯·沃斯）
基础概念
-
数据（data）：对客观事物的符号化表示，是信息、概念与知识的载体。
数据项：从数据的属性角度对数据进行描述。
数据元素：从数据的组成元素角度对数据进行描述。
数据对象：性质相同的数据元素的集合。
理解：描述一个班的学生，姓名、性别、年龄、身高等即为数据项，张三、李四（指每一个学生个体，并不单指名字）即为数据元素，五年级三班，学生组成的一个班级（集合），即为数据对象。 -
数据类型:具有相同性质的数据的抽象，定义了一个值域及在这个值域上可以进行的一组操作。
基本数据类型：比如整型、字符等。
派生的数据类型：比如，我们创建的学生类、日期类等均属于派生的，以及数组、结构等程序给定的，也属于此。
抽象数据类型（Abstract Data Type，ADT）：指一个数学模型以及定义在该模型上的一组操作，与计算机的内部定义和实现无关。
理解：这里的ADT应该是重中之重，表示为：ADT=（D，S，P），D为数据对象，S是D中数据的关系集合，P是对D的操作集合。
例如，一个班级，每个学生个体是数据对象，学生之间的座次是数据关系，对这个班级整体的调整（操作），班级同学换座位（改）、新生进入班级（增）等，即为操作集合。
由此，ADT之所以重要，我认为这个概念将数据结构和算法在逻辑层面上实现了结合和统一。 -
数据结构：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
表示为：DataStructure=（D，S），D是数据元素的有限集，S是D上关系的有限集。简单来说，其实就是ADT中的数据、数据之间关系的描述。
分类：逻辑结构、物理结构。
逻辑结构：是数据元素之间的逻辑关系。
理解：以家族为例，家族中的所有人在一起不考虑之间的关系，就是一个集 合（集合结构），常看到的族谱，就是树型结构。</br>
物理结构：是一个萝卜一个坑的事情，那么坑位的关系就是所谓的存储，主要指的是数据在计算机内部的实际存储。顺序指数据在物理地址上是依次存放，而链式则是分散存放的。
理解：如下图中，“今天天气晴朗”，一句话用两种物理结构实现表示，说明了两种存储方式在物理上的区别，当然在具体的实现中远远要复杂于此。
顺序存储和链式存储
- 算法：一组完成特定任务的有限指令序列。
设计算法的准则：
输入：提供给算法的输入数据；
输出：算法执行后的结果；
确定性：算法每一步语义明确，无二义性；
有限性：算法步骤、时间有限；
有效性：算法可实现。
理解：算法便是ADT中对数据不同操作的集合，这样的操作有我们常做的增删改查，也有再进一步的查找、排序等。
算法性能分析与度量：
时间复杂度：算法执行时花费CPU时间的度量；
空间复杂度：算法执行时占用计算机存储空间的度量。
理解：算法设计出来，我们如何比较算法的优劣，需要有定量的评测，那么这就是时空复杂度的由来，这个拿出来单独学习也可以再出来一个系列，所以暂时计划明白其概念即可，后续再进行细致地学习。
小结
本文围绕数据与数据类型、数据结构和算法，三个大的概念进行阐述，主要明确了一些需要了解和掌握的基本概念，并在文中将一些较为通俗的理解穿插，以方便学习记忆，有不当和错误的地方还请大家多多批评指正，谢谢！
网友评论