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