【数据结构与算法数据结构基础】什么是数据结构？

【数据结构与算法 - 数据结构基础】什么是数据结构&＃xff1f;

• 数据&＃xff0c;data&＃xff1a;符号集合、处理对象
• 结构&＃xff1a;各个组成部分的搭配和排列
• 数据元素&＃xff1a;数据的基本单位&＃xff0c;可由若干个数据项组成

→ 数据结构 data structure&＃xff1a;数据的组织、管理和存储格式。

要与算法结合起来说的话&＃xff0c;数据结构就是我们能够执行算法的“原材料”。数据结构 &＃43; 算法 &＃61; 程序设计。

通常情况下&＃xff0c;更优的数据结构可以给程序带来更高的运行以及存储效率。

简单来说&＃xff0c;数据结构的定义就是一种程序设计优化的方法论&＃xff0c;它不仅讨论到存储的数据&＃xff0c;同时也考虑到彼此之间的关系与运算&＃xff0c;使之达到加快程序执行速度与减少内存占用空间等作用。

1 数据结构包含的三个方面

数据结构&＃xff08;data structure&＃xff09;指数据元素之间存在的关系。

主要包含以下三个方面&＃xff1a;

• 数据的逻辑结构
• 数据的存储结构
• 数据操作

1.1 数据的逻辑结构

1.1.1 线性结构

数组【Array】

数组是一种典型的线性数据结构。它是存储在连续内存位置的相似类型数据项的集合。

数组是最简单的数据结构&＃xff0c;它的每个数据元素都可以使用索引号随机访问。

链表【LinkedList】

链表是一种物理存储上非连续&＃xff0c;数据元素的逻辑顺序通过链表中的指针链接次序&＃xff0c;实现的一种线性存储结构。

Java 集合框架中的LinkList 类&＃xff0c;底层的实现就是 链表。

栈【Stack】

栈是以数组或者链表为基础&＃xff0c;封装出来的一种数据结构。

栈&＃xff08;stack&＃xff09;又名堆栈&＃xff0c;它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶&＃xff0c;相对地&＃xff0c;把另一端称为栈底。

队列【Queue】

队列是一种特殊的线性表&＃xff0c;特殊之处在于它只允许在表的前端&＃xff08;front&＃xff09;进行删除操作&＃xff0c;而在表的后端&＃xff08;rear&＃xff09;进行插入操作&＃xff0c;和栈一样&＃xff0c;队列是一种操作受限制的线性表。进行插入操作的端称为队尾&＃xff0c;进行删除操作的端称为队头。

1.1.2 树结构【Tree】

树&＃xff0c;是一种一对多的数据结构&＃xff0c;天生就非常适合用来检索。

它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树&＃xff0c;也就是说它是根朝上&＃xff0c;而叶朝下的。

Java集合框架当中有一个TreeMap类&＃xff0c;用于存储键和值的映射&＃xff0c;不但查找很高效&＃xff0c;还能保证键的有序排列。它的底层实现就是一种名为红黑树的特殊二叉树。

1.1.3 图结构【Graph】

图&＃xff0c;是一类多对多的数据结构&＃xff0c;非常适合用于表述众多对象之间的复杂关系。

堆【Heap】

堆是一种特别的完全二叉树。

其定义为&＃xff1a;给定堆中任意节点P和C&＃xff0c;若P是C的母节点&＃xff0c;那么P的值会小于等于&＃xff08;或大于等于&＃xff09;C的值。

堆最常见的作用是可以迅速找到一堆数当中的最大值或者最小值。

1.1.4 散列表【Hash】

散列表Hash table,也叫哈希表。

散列表用的是数组支持按照下标随机访问数据的特性&＃xff0c;所以散列表其实就是数组的一种扩展&＃xff0c;由数组演化而来。可以说&＃xff0c;如果没有数组&＃xff0c;就没有散列表。【散列表是一种非线性的数据结构】

树是图的特例&＃xff0c;树是连通的无回路的无向图&＃xff1b;线性表是树的特例&＃xff0c;线性表是单枝树。

1.2 数据的存储结构

1.2.1 顺序存储【Sequential Storage】

顺序存储是所有的结点元素存放在一块连续的存储区域中&＃xff0c;用存储结点的物理位置来体现结点之间的逻辑关系的存储方法。

在高级语言中&＃xff0c;一块连续的存储空间通常可用一个数组来表示。因此&＃xff0c;顺序存储通常用一个数据元素类型的数组来存储。最经典的顺序存储结构是顺序表&＃xff0c;将线性结构的元素按序存放在一个数组中 。

1.2.2 链式存储【Linked Storage】

链式存储结构&＃xff0c;又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)

它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

1.2.3 索引存储【Index Storage】

索引存储&＃xff0c;分别存放数据元素和元素间关系的存储方式。

所有的存储结点存放在一个区域。另设置一个索引区域存储结点之间的关系。

索引是为了加速检索而创建的一种存储结构。它是针对一个表而建立的&＃xff0c;是由存放表的数据页面以外的索引页面组成的。

1.2.4 哈希存储【Scatter Storage】

哈希存储亦称“散列存储”&＃xff0c;专用于集合结构的一种存储方式。

该方法的基本思想是&＃xff1a;根据结点的关键字直接计算出该结点的存储地址。

数据元素存放在一块连续的存储区域中。数据元素的存放位置是通过一个哈希函数计算而得的。哈希函数将数据元素作为自变量&＃xff0c;计算得到的函数值是数据元素的存储地址。

【应用】用于支持集合结构的动态查找。

1.3 数据操作

【1】初始化。

【2】判断是否空&＃xff08;isEmpty&＃xff09;状态。

【3】存取&＃xff0c;指获得&＃xff08;get&＃xff09;、设置&＃xff08;set&＃xff09;指定元素值。

【4】遍历&＃xff08;traverse&＃xff09;&＃xff0c;指按照某种次序访问一个数据结构中的所有元素&＃xff0c;并且每个数据元素只被访问一次。线性次序遍历。

【5】统计数据元素个数。

【6】插入&＃xff08;insert&＃xff09;、删除&＃xff08;remove&＃xff09;指定元素。

【7】查找&＃xff08;search&＃xff09;&＃xff0c;指在数据结构中寻找满足给定条件的数据元素。

【8】比较相等&＃xff08;equals&＃xff09;&＃xff0c;指两个数据结构形态相同&＃xff0c;其中各对应元素分别相等并且数据元素个数相等。

【9】复制数据结构&＃xff08;深拷贝&＃xff09;及其中所有元素。

【10】排序&＃xff08;sort&＃xff09;&＃xff0c;指对数据元素按照指定关键字值的大小递增&＃xff08;或递减&＃xff09;次序重新排列。