【数据结构基础】数据结构基础概念

前言

数据结构，一门数据处理的艺术，精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美，在为信息技术打下坚实地基的同时，也令无数开发者和探索者为之着迷。

也因如此，它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持，我打算将这门课的笔记也写作系列博文，既用于整理、消化，也用于同各位交流、展示数据结构的美。

此系列文章，将会分成两条主线，一条“数据结构基础”，一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主，“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

欢迎关注博主，一起交流、学习、进步，往期的文章将会放在文末。

千里之行，始于足下。作为数据结构课程的首节内容，自然要从各种概念的定义讲起。本文将阐述数据结构的基本定义，以及组成数据结构的三方面内容——数据的逻辑结构、数据的存储结构、对数据的操作。

数据结构的定义

其实有关数据结构的定义，至今在计算机科学与技术界还未取得一致。但是这不妨碍我们通过一些已有的定义来了解数据结构的含义。

可以参考以下定义：

数据结构是指由若干数据元素按照一定方式构成的复合数据以及作用于其上的函数或运算。
数据元素及其间的数据约束关系合称为数据的逻辑结构。
数据结构从数学上可用适当的数学结构及其上的函数变换统一的定义

数据元素

在上文定义中，使用到了“数据元素”这个概念。

数据元素元素还可被称为元素、节点或定点等。他可以是一篇文稿、一本书，也可以是一个字符，一位二进制数据。数据元素的规模可大可小。

博主认为，数据元素就是一系列数据形成一个整体在结构中作为节点而存在。

数据元素可由若干数据项（也称域或字段）构成

数据的逻辑结构

在定义数据结构的过程中，使用数据元素及其数据约束关系定义了一个概念叫做数据的逻辑结构。

这个逻辑结构可以算是我们脑海中对于数据结构的常见概念了，在数学语言的描述下，数据结构不仅可以被严谨的定义，还可以使用图形生动的刻画出来。

• 数据的逻辑结构从比较抽象的角度刻画了数据结构所具有的数学性质，将数据元素抽象为节点，数据元素之间的关系作为连接节点的边。

这里的逻辑结构强调使用数学语言描述结构性质

使用二元组和关系来定义逻辑结构

那么如何使用数学语言来描述数据的逻辑结构呢？

我们可以使用集合和关系的相关知识来完成对数据结构的定义。

设逻辑结构L为一个二元组 (N,R)，即
$$L=(N,R)$$
其中，N代表节点集合，R是定义在集合N上的二元关系r的关系集合

不知道关系集合是什么也没有关系，在这里关系集合R就是节点集合N的笛卡尔集合NxN的子集。R中的元素是一系列的序偶，也就是一对一对的N中元素。如果R中存在序偶 (a,b),a,b∈N，就代表N中元素a，b满足关系r

数学定义往往是枯燥且抽象的，仅凭上面的数学定义还不足以体现多种多样的逻辑结构。我们说根据关系集合R的不同，节点集合中的元素就会呈现出很多截然不同的结构。这点很快会在下文谈到。

数据结构的组成

有些学者认为数据结构应有数据的逻辑结构、数据的存储结构及其运算三部分组成。那么不妨就暂从这三个方面来讨论数据结构的组成。

数据的逻辑结构

上文我们讨论到了数据的逻辑结构，并且给出了一个晦涩难懂的数学定义。下面就让我们更进一步的讨论下这个定义，并且根据关系性质的不同，来对数据结构分一分类

基于上面的定义，我们假设对于(a,b)∈R，定义其表示关系 “a是b的前驱节点，b是a的后继节点，a和b是相邻节点”

如果不存在b∈N且(a,b)∈R，则成b是始节点
类似的，如果不存在a∈N且(a,b)∈R，则成a为 终节点

线性结构

使用上面的已有定义对线性结构进行定义：

若节点数为1，则该节点既是始节点，又是终结点；
若节点数大于等于2，则有且仅有一个始节点和一个终结点，始节点仅有一个后继，终结点仅有一个前驱。
中间节点有且仅有一个前驱结点和一个后继节点。

举个例子，对于逻辑结构**L_线性结构 = (N,R)**有：
N = { a , b , c , d } R = { ( a , b ) , ( b , c ) , ( c , d ) } N=\left \{ a,b,c,d\right \} \\ R=\left \{ (a,b),(b,c),(c,d)\right \} N={a,b,c,d}R={(a,b),(b,c),(c,d)}

使用将它们形象的画出来就是下面的样子：

这就是一个典型的线性结构，关系r也被称为线性关系或者大小关系

树结构

树结构有且仅有一个没有前驱的节点，称为根节点。
其余节点有且仅有一个前驱结点，可以有多个后继节点也可以没有后继节点
从根到任意非根节点有且仅有一条路径

举个例子，对于逻辑结构L_树结构=(N,R)
N = { a , b , c , d } R = { ( a , b ) , ( b , c ) , ( a , d ) } N=\left \{ a,b,c,d\right \} \\ R=\left \{ (a,b),(b,c),(a,d)\right \} N={a,b,c,d}R={(a,b),(b,c),(a,d)}
图示结果如下：

这是典型的树结构，关系r也被成为层次关系或者父子关系等

图结构

图结构中任意节点的前驱和后继节点数量可以是0或多个。

图结构的约束相对较少，举个例子，对于逻辑结构L_图结构=(N,R)
N = { a , b , c , d } R = { ( a , b ) , ( b , c ) , ( c , d ) , ( d , a ) } N=\left \{ a,b,c,d\right \} \\ R=\left \{ (a,b),(b,c),(c,d),(d,a)\right \} N={a,b,c,d}R={(a,b),(b,c),(c,d),(d,a)}
图示结果：

这就是一个图结构，图结构也称为网络结构，关系r也称为相邻关系

特殊的，树结构可以看做是一个特殊的图结构，图结构的定义中包含了树结构的定义。

集合

集合的特点是结构中的数据元素之间除了“同属于一个集合” 的关系外，别无其他关系。

简单来说，对于几个中的元素，定义于其上的关系集合R为空集

举个例子，对于逻辑结构L_集合=(N,R)
N = { a , b , c , d } R = ∅ N=\left \{ a,b,c,d\right \} \\ R=∅ N={a,b,c,d}R=∅
图示结果：

线性结构与非线性结构

数据的逻辑结构也可以按照线性与非线性来进行分类，按照这个标准，只有线性结构是线性的，其余结构都是非线性的。

非线性结构的特点是结构中的节点可能有多个前驱和多个后继。

数据的存储结构

数据的存储结构是指数据的逻辑结构在计算机中所需的存储空间、空间的构成结构以及对该存储结构的访问方式等的总称。

上文提到了数据的逻辑结构，存储结构建立一种有逻辑结构向存储结构的映射：建立节点集合N到存储区域M的映射N→M。

一般的，基本的存储映射方法有顺序、链接、索引和散列4种

顺序存储

顺序存储将一组节点存放在地址相邻的存储单元内，即使用一块无空袭的存储区域存储节点数据。

数组就是典型的存储线性数据的顺序存储

开辟一个数组时就会在内存中开辟整块的空间。节点之间的线性关系是用地址单元的顺序关系自然表达的。

顺序存储的结构访问数据节点非常的便利。当节点等长时，访问特定节点只需要对地址进行简单的加减计算即可确定到该元素的位置。

例如：取a数组中的第四个元素a[3]（从0开始计数），那么只需要知道a的地址，在使其加上4个单位长度即可，a[3]的地址为:a+3 * k(k为a中元素所占字节数)

那么取第idx+1个元素或取索引值为idx的元素，只需要直接取地址 a+idx*k处k个字节中的内容即可。

另外由于c语言的语言定义，对指针与整数的增加会自动以所值类型的长度为单位

所以在C语言中，访问下标为idx的元素方法为：*(a+idx)或者直接为a[idx]

链接存储

联结存储通过在节点的存储结构中附加指针字段来存储节点间的逻辑关系。链接存储可以表达任意的逻辑关系。

其特点就是每个数据节点中需要添加指针字段用来记录后继的地址。节点中的数据字段则存储自身的数据。

链接存储一个典型的应用是用来存储线性结构：链表，用一个灵魂图画来表示

当然，他也可以用来存储树或者图结构：

此时指针字段就不仅有一个指针了，而是一个指针集合，记录该节点所有的后继。

链接存储灵活性很大，使用经常变化的结构。对他的插入删除都十分方便。但是他的缺点就是遍历或者访问不如顺序存储方便。以链表为例，访问第k个元素需要按照顺序逐个跳转到第k个元素。

索引存储

索引存储可以看作顺序存储方法的一种推广，通过定义一个有证书与映射到存储地址域的函数，把整数索引值映射到节点的存储地址。

简单来说，就是开辟整块内存使用顺序存储来存放地址。用一个灵魂绘图表示即为：

索引存储的方法也是常用的存储方法，对于非顺序存储结构来说，使用索引表是经由整数索引值快速找到其对应的数据节点的唯一方法。使用指针数组管理动态数据对象就是一个常见的实例

例如：存储n个学生的信息，其中学生节点是一个对象，每个学生的内存是动态开辟的。可以使用索引存储的方式来管理这些学生。

Student* students[N];
for(int i = 0;i < n;i++){students[i] = new Student();
}

这种存储的缺点在于其对索引查找是比较繁琐的，根据需求的不同，可能会需要遍历整个索引数组才能找到所需的索引。

散列存储

散列存储又称哈希（hash）存储。是指利用散列函数（hash functions）进行索引值的计算，然后通过索引表求出节点的指针地址，是索引方法的一种延伸和扩展。

简单来说，就是在索引存储的基础上对索引进行一次hash映射得到一个唯一的hash值，并根据这个值对索引进行存储。

这样的存储形式优点就在于其适合大数据量和快速检索的场合。对于一个数据元素，不同于索引存储可能需要遍历整个索引集合，散列存储仅需要对数据元素进行hash运算便可以直接寻找到索引值。

数据存储结构的组合使用

数据存储结构不尽可以单独出现，还可以组合起来对数据进行存储。

例如在表示一张图的时候，通常使用顺序存储来记录节点信息，而采用链接存储来记录边信息。

又例如，可以使用索引存储来记录键值对形成映射（map）结构，在存储索引时采用散列存储来优化索引的查找，形成HashMap，又或者使用树形结构表示索引，存储为链接结构，形成TreeMap

数据结构的操作

组织和存储数据不是数据结构的全部，组织和存储数据的目的在便于使用者更加便捷的控制和访问，配合算法高效完成工作。

一般来说，最常见的操作就是人们常说的老四样——增删改查。

不过在这里也可以将它们分成另外两个概念——查找和维护

查找就是按照一定需求对数据结构进行访问，是的存储的数据可以按照我们需要的格式进行显示。比如查找一个数字集合中的最大元，或者访问链表中的第k个元素，也可以是查询数据库中符合一定条件的某些记录的某些字段。

维护就是对数据本身进行操作，包括删除、插入、修改、排序等。

这里的排序是更加广义上的排序，不仅指将数据按照大小关系进行升序或降序排序，而是将数据结点按照一定的标准进行排序，这个标准依据需求而改变，有时可能需要再调用排序方法时传递比较器，有时也可以是数据元素本身可比较。但是需要注意的是，排序近改变结点的位置而不能改变结点的内容。一些对顺序不敏感或不存在顺序的结构就不需要实现排序操作，例如集合。

参考资料：

• 《数据结构》（刘大有，杨博等编著）
• 《算法导论》（托马斯·科尔曼等编著）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！