1. 数据结构简介

作者: 易百教程 | 来源:发表于2018-11-10 11:45 被阅读258次

数据结构可以定义为数据元素组，它提供了在计算机中存储和组织数据的有效方法，以便可以有效地使用它。数据结构的一些示例是：数组，链表，堆栈，队列等。数据结构广泛用于计算机科学的几乎每个方面，即操作系统，编译器设计，人工智能，图形等等。

数据结构是许多计算机科学算法的主要部分，因为它们使程序员能够以有效的方式处理数据。它在提高软件或程序的性能方面发挥着重要作用，因为软件的主要功能是尽可能快地存储和检索用户的数据。

基本术语

数据结构是任何程序或软件的构建块(基础块)。为程序选择适当的数据结构对于程序员来说是最困难的任务。就数据结构而言，使用以下术语 -

数据：数据可以定义为基本值或值集合，例如，学生的姓名和ID，成绩等就是学生的数据。

组项：具有从属数据项的数据项称为组项，例如，学生的姓名由名字和姓氏组成。

记录：记录可以定义为各种数据项的集合，例如，如果以学生实体为例，那么学生的名称，地址，课程和标记可以组合在一起形成学生的记录。

文件：文件是一种类型实体的各种记录的集合，例如，如果类中有60名员工，则相关文件中将有20条记录，其中每条记录包含有关每个员工的数据。

属性和实体：实体表示某些对象的类。它包含各种属性。每个属性表示该实体的特定属性。

字段：字段是表示实体属性的单个基本信息单元。

为什么需要数据结构

随着应用程序变得越来越复杂，数据量日益增加，可能会出现以下问题：

为了解决上述问题，使用数据结构。组织数据以形成数据结构，使得不需要搜索所有项目并且可以立即搜索所需数据。

效率：程序的效率取决于数据结构的选择。例如：假设有一些数据，需要执行搜索特定记录。在这种情况下，如果在数组中组织数据，则需要逐个元素地搜索。因此，在这里使用数组可能效率不高。有更好的数据结构可以使搜索过程像有序数组，二进制搜索树或哈希表一样高效。
可重用性：数据结构是可重用的，即当实现了特定的数据结构，就可以在其他地方使用它。也将数据结构的实现编译到不同客户端使用的程序库中。
抽象：数据结构由ADT指定，它提供抽象级别。客户端程序仅通过接口使用数据结构，而不涉及实现细节。

数据结构分类

image

如果数据结构的所有元素按线性顺序排列，则称为线性数据结构。在线性数据结构中，元素以非分层方式存储，除了第一个和最后一个元素，它的每个元素具有后继元素和前导元素。

线性数据结构的类型如下：

数组：数组是类似数据项的集合，每个数据项称为数组的元素。元素的数据类型可以是任何有效的数据类型，如char，int，float或double。
数组的元素共享相同的变量名，但每个元素都带有一个不同的索引号，这些索引号也称为下标。数组可以是一维的，二维的或多维的。

示例：数组age的各个元素是：

age[0], age[1], age[2], age[3],.... age[98], age[99]

链表：链表是一种线性数据结构，用于维护内存中的列表。它可以看作存储在非连续内存位置的节点集合。链表中的每个节点都包含指向其相邻节点的指针。
堆栈：堆栈是一个线性列表，其中只允许在一端插入和删除，称为顶部。
堆栈是一种抽象数据类型(ADT)，可以在大多数编程语言中实现。它被命名为堆栈，因为它的行为类似于真实世界的堆栈，例如：成堆的板块或卡片组等，只能在最顶面上操作。
队列：队列是一个线性列表，它的元素只能在一端插入(添加)，也被称为后端，而只在另一端出队(删除)，也被称为前端。

非线性数据结构不形成序列，即每个项目或元素以非线性排列与两个或更多个其他项目连接。数据元素不按顺序结构排列。

非线性数据结构的类型如下：

树：树是多级数据结构，其元素之间具有层次关系，树的元素也称为节点。层次中最底层的节点称为叶节点，而最顶层节点称为根节点。每个节点都包含指向相邻节点的指针。
树数据结构基于节点之间的父子关系。除了叶节点之外，树中的每个节点可以具有多个子节点，而除了根节点之外，每个节点可以具有最多一个父节点。树可以分为许多类别，本教程在稍后章节中将对此进行讨论。
图：图可以定义为由称为边缘的链接连接的元素集(由顶点表示)的图表示。图不同于树，图可以有循环而树不能具有循环。

遍历：每个数据结构都包含一组数据元素。遍历数据结构表示访问数据结构的每个元素，以便执行某些特定操作，如搜索或排序。示例：如果需要计算学生在6个不同科目中获得的分数的平均值，需要遍历完整的分数数组并计算总和，然后将总分数除以科目数，即6，最后得到平均值。
插入：插入是在任何位置将元素添加到数据结构的过程。如果数据结构的大小是n，那么只能在n-1个数据元素之间插入元素。
删除：从数据结构中删除元素的过程称为删除。可以在任何随机位置删除数据结构中的元素。如果要从空数据结构中删除元素，则会发生下溢。
搜索：在数据结构中查找元素位置的过程称为搜索。有两种算法可以执行搜索，即线性搜索和二进制搜索。在本教程后面讨论这两种搜索算法。
排序：按特定顺序排列数据结构的过程称为排序。有许多算法可用于执行排序，例如，插入排序，选择排序，冒泡排序等。
合并：当两个列表分别为大小为M和N的列表A和列表B时，相似类型的元素，连接产生第三个列表，列表C的大小(M + N)，则此过程称为合并。