第002讲：数据结构的基本概念和术语讲解

小甲鱼

第002讲：数据结构的基本概念和术语讲解

知识点回顾：

0. 本节视频




1. 什么是数据结构？

最简单的说法，数据结构是计算机中存储和组织数据的方式。

具体地说，在计算机科学中，数据结构是数据值的集合，以及在这些数据上的操作。

那么，数据结构就是我们组织和存储数据的方式咯，这种方式可以使得我们能够高效地访问和修改数据，这就是数据结构的作用。

从学科定位，尤其是对于在座准备考研的同学来说，数据结构是一门综合性的课程，因为它结合了数学、计算机硬件和计算机软件这三大领域。


2. 数据结构由什么组成？

数据结构通常可以从逻辑结构、存储结构和数据运算这三个方面来理解。

其中，逻辑结构关注的是数据之间的关系，跟数据实际存储在计算机中的位置，关系不大。

逻辑结构主要有 4 种类型，分别是线性结构、树形结构、图形结构和集合结构。

• 线性结构：数据元素之间是一对一的关系，比如数组、链表、队列、栈。
• 树形结构：数据元素之间存在一对多的关系，比如二叉树、堆、B树、红黑树。
• 图状结构，也叫网状结构：数据元素之间多对多的关系，这种搞起来特别麻烦，就像旅行商问题。
• 集合结构：数据元素之间除了同属于一个集合之外，并无其他关系。
  

存储结构主要包括了顺序存储、链式存储、索引存储和散列存储。

• 顺序存储：数据元素在内存中的存储关系和逻辑关系一致，数组就是，下一个元素一定是挨着上一个元素的位置存放。
• 链式存储：数据元素在内存中的存储关系和逻辑关系不一致，它会通过一个指针链将松散的内存单元给串联起来，比如链表。
• 索引存储：数据元素和相应的索引位置分开存储，通过索引表来快速访问数据元素，就像是查询通讯录一样，先找到名字，再拨打电话。
• 散列存储：根据数据元素的关键字直接计算出存储的位置，比如哈希表就是散列存储。
  

最后一个是数据的运算。

这里是指施加在数据上的运算，咱们根据程序的需求设计了一个逻辑结构。

它可以是链表，可以是树，也可以是图，都行……

那么它们支持的操作总结起来就是增、删、改、查嘛，

然后这些操作在相应的存储结构中如何去实现，

就好比链表结构，增加一个数据应该先这样，再那样，等等，

这些合在一起就是数据的运算啦~


3. 还有几个名词需要辛苦大家稍微记一下^o^

数据（data）

数据是信息的载体。

是描述客观实物的符号，也是最终输入到计算机，

被计算机处理和存储的符号集合，

包括但不限于数字、文本、图片、音频、视频等等。


数据元素（data element）

数据元素是数据的基本单位。

数据元素具有一定的意义，在计算机中通常作为一个整体被对待，

它可以是一个单独的数据项，比如一个数字、一个字符或者一个单词。

也可以是一组相关的数据项的集合，

比如一条数据库的记录（它就包含了多个字段，像姓名、地址、电话号码之类）。


数据项（date item）

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

一个数据元素可以由一个或者多个数据项构成。

假设我们有一个学生数据库，其中每个学生的记录包含姓名、年龄、班级和成绩等信息。

在这种情况下，"张三"、"18岁"、"2班"、"85分"这些都是单一的数据项。

而整条完整的学生记录，则是一个数据元素。


数据对象（data object）

数据对象是性质相同数据元素的集合，是数据的子集。

比如所有的整数构成了整数数据对象，所有的字母字符也能构成一个数据对象。


数据结构（data structure）

因为数据元素并不是孤立无序的，它们相互存在着一种或多种关系，

为了实现高效率的算法，我们就需要将它们按照一定的数据结构进行整理，

比如整理成一对一的线性结构，或者一对多的树形结构，又或者多对多的图状结构，这就是数据结构。


4. 算法的概念

算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操。

一个算法还具有下列 5 个重要特性：

• 有穷性（finiteness）：就是说一个算法必须是能给出结果的，它的执行步骤必须是有限的，不能说我这个算法要与天地同在，与日月同辉，那不行……
• 确定性（determinism）：就是说算法中每一条指令都必须是有确切含义的，然后对于相同的输入，算法都应该始终产生相同的结果。不能朝三暮四，更不能反复无常。
• 可行性（effectiveness）：说白了就是算法设计应该足够简单，以至于可以实际执行。
• 输入（Input）：算法可以没有输入或者多个输入，但要定义清楚。
• 输出（Output）：算法至少要有一个输出，也可以是多个输出。
  

算法设计的要求：

• 正确性（correctness）：算法能够正确地解决问题。
• 可读性（readability）：算法的实现代码应该具有良好的可读性，以便其他人阅读。
• 健壮性（robustness）：也叫鲁棒性，指算法在遇到非法输入时，能够做出恰当的处理，而不是产生奇怪的结果。
• 高效率与低存储量需求：效率是指算法的执行时间，存储量需求是指算法在执行的过程中需要用到的最大存储空间。
  

5. 思维导图

歌者文明清理员

加油！支持甲鱼哥！

小古比鱼

数据结构是计算机中存储和组织数据的方式，是数值的集合以及在这些集合上的操作，其作用是使我们高效地访问和修改数据。数据结构集合了数学、计算机硬件和计算机软件三大领域的内容，包括逻辑结构、存储结构和数据运算三大要素。其中：逻辑结构关注的是数据之间的关系，包括线性结构（一对一）、树形结构（一对多）、图状结构（多对多）、集合结构（同属）四种类型；存储结构关注的是数据在计算机内存中的存储方式，主要包括顺序存储、链式存储、索引存储、散列存储；数据运算是指施加在数据上的运算，如增、删、改、查等一系列操作。视频还讲解了数据、数据元素、数据项、数据对象的概念。
算法是对特定问题求解步骤的一种描述，是指令的有限序列，具有五个重要特性——有穷性、确定性、可行性、输入和输出。一个好的算法应具有正确性、可读性、健壮性（鲁棒性）、高效率与低存储量需求。
本节所讲的这些基本的概念和术语看似有些枯燥，实则是整门课程的基础与核心，有助于我们读懂相应的算法题目，务须理解并掌握！