小甲鱼 发表于 2023-9-16 04:32:00

第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. 思维导图



歌者文明清理员 发表于 2023-9-16 10:54:26

加油!支持甲鱼哥!

小古比鱼 发表于 2023-10-14 15:29:16

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