数据结构笔记第一章（绪论）

type

status

date

slug

summary

前言

🤨

数据结构作为计算机四大件之一，其重要性不言而喻。但这门课又对刚入计算机学习苦海没多久的小白们又是难上加难 😭所以博主在这里分享自己第一次学习数据结构时一些自己笨拙的理解，来帮助小白们更容易理解数据结构中的知识。

👉 推荐学习资料

《大话数据结构》——程杰

数据结构与算法基础（青岛大学-王卓）_哔哩哔哩

数据结构（浙江大学-陈越、何钦铭）_哔哩哔哩

📝 正文

第一章、绪论

1.1 为什么要学习数据结构？

有一句经典的话

程序设计=数据结构+算法

从这个式子中我们就知道在程序设计中数据结构时必不可少的，而学习数据结构也可以让我们更好的存储数据，以方便后期对数据的结构

“一切没有理由的数据存储方式就是在对存储空间耍流氓“——Jerry Zhu

在知道学数据结构的重要性后，我们要先知道一些概念。

1.2 一些概念与术语

1.2.1 数据

学习数据结构，我们当然需要知道数据是什么意思。

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

说白了，数据其实就是符号。但这个符号得具备两个前提：

可以输入到计算机中。

能被计算机程序处理。

对于整型、实型等数值类型，可以进行数值计算。而对于字符数据类型，就需要进行非数值的处理。而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

1.2.2 数据元素、数据项与数据对象

那么组成数据的又是什么呢？这时候就要引出数据元素了。

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。（比如在人类这个数据中，人便是数据元素）

而数据元素也有组成的东西，这个东西便是数据项（是不是很像套娃 😂）

数据项：一个数据元素可以由若干个数据项组成。（比如人这个数据元素中，心，胃，肺等器官便是数据项）

数据项也有组成的东西吗？等等等等，不能再套娃下去了，所以数据项是数据不可分割的最小单位。

1.2.3 数据对象

这时候，有人就会提问了，那人不也分好人坏人吗，那所有人都是数据元素，那如何区分好人坏人呢？这就要引出数据对象了！

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

既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们都将数据对象简称为数据。

绕来绕去讲了这么多，数据结构却还没提到。这不能忘了我们的主角啊，下面我们来介绍一下数据结构。

1.2.4 数据结构

既然讲到数据结构，那么就要先知道结构是什么概念。结构，简单的理解就是关系，是各个组成部分相互搭配和排列的方式。在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。那结构前面加个数据代表着什么呢？

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。也就是带”结构“的数据元素的集合。

而数据结构由三要素组成：逻辑结构、存储结构和运算，下面就让我们来探讨一下这三要素。

1.3 逻辑结构和存储结构

1.3.1 逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需要关注的问题。逻辑结构分为以下四种；

1.集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。而数据结构重点研究的是数据之间的关系，所以集合虽然是一种数据结构，但探讨价值不大。（如图1.1所示）

2.线性结构：线性结构中的数据元素之间是一对一的关系。之后我们要学习的线性表，栈和队列，数组，串和广义表的推广都是线性结构。（如图1.2所示）

3.树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。（如图1.3 所示）

图状结构：图状结构的数据元素是多对多的关系。（如图1.4 所示）

其中集合结构，树形结构，图状结构都属于非线性结构。从上面的例子也可以看出，逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。

1.3.2 存储结构

说完了逻辑结构，我们再来说说数据的存储结构。存储结构又称为物理结构，其概念如下：

物理结构：是指数据的逻辑结构在计算机中的存储形式。

而数据结构在计算机中的存储结构有以下四种：

1.顺序存储

顺序存储：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

其特点：

随机存取表中元素。

插入和删除操作需要移动元素。

这种结构看起来高大上，实际上就是排队问题。我们拿银行取钱为例子，顺序存储就是大家都按顺序排好，每个人占一小段空间，谁也别插谁的队，老老实实排队取钱。

2.链式存储

链式存储：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

其特点：

比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。

逻辑上相邻的节点物理上不必相邻。

插入、删除灵活 (不必移动节点，只要改变节点中的指针)。

查找结点时链式存储要比顺序存储慢。

每个结点是由数据域和指针域组成。

这种结构可以想象成取号制排队，你人到银行先取个号，之后不管你人站在那，银行都只叫号取钱。

3.散列存储

散列存储：又称为哈希（Hash）存储，是把数据元素存放在一块连续的存储空间中，由元素的关键字值来决定该元素的存储地址。用散列函数确定数据元素的存储地址与关键字值之间的对应关系。

其特点：

与链式存储最大的区别就是，加了一个计算过程。

结合了顺序存储和链式存储的优点，但占用空间略大于这俩玩意。

这种结构可以想象成银行在取号制的前提下添加了一条规则，通过这条规则来叫号取钱。

4.索引存储

索引存储：是指除存储元素信息外，还建立附加的索引表来标识元素的存储地址。索引表由若干索引项组成。若每个元素在索引表中都有一个索引项用于指示该元素所在的存储位置，则该索引表称为稠密索引。若一组元素在索引表中只对应一个索引项，该索引项指示这一组元素的起始存储位置，则该索引表称为稀疏索引。索引项的一般形式是关键字、地址。

其特点：

优点是检索速度快。

缺点是增加了附加的索引表,会占用较多的存储空间。

这种结构可以想象成这个时候银行让每个人都登记信息在一张表上，之后银行叫人取钱就通过这张表格来叫人取钱。

1.4 数据类型与抽象数据类型

1.4.1 数据类型

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

在 C 语言中，按照取值的不同，数据类型可以分为两类：

原子类型：是不可以再分解的基本类型，包括整型、实型、宇符型等。

结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据组成的。

1.4.2 抽象数据类型

我们在了解了数据类型的概念后，在数据类型前加上一个抽象代表着什么呢？首先让我们了解以下抽象的概念：

抽象是指抽取出事物具有的普遍性的本质。

它是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。

那么抽象数据类型代表着什么呢？

抽象数据类型：是指一个数学模型及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辊特性，而与其在计算机内部如何表示和实现无关，即数据对象、基本操作的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。

简而言之，抽象数据类型独立于具体实现，它只是描述数据对象和基本操作“做什么”，并不涉及“怎么做”的问题。这种描述方法与面向对象的思想是一致的，将数据和操作封装在一起，对于需要调用这些操作的用户而言，只需要按照事先规定的接口调用，并不需要知道操作内部具体是怎么实现的，从而实现了数据封装和信息隐藏。这也就意味着，无论操作内部的具体实现如何改变，只要对外描述的接口不变，就不影响使用，实现“接口与实现相分离”的设计原则。

📎 参考文章

《大话数据结构》——程杰

《数据结构》——陈志贤

💡

欢迎大佬指正笔记中的错误或者不足，对于文中例题有更好的解法也欢迎大佬留言！