高级数据结构

2024 年 8 月 28 日 | 阅读 13 分钟

高级数据结构是数据科学中最重要的一门学科之一，因为它们用于存储、组织、管理数据和信息，使其更有效、更容易访问和修改。它们是设计和开发高效软件和算法的基础。了解如何创建和构建一个不错的数据结构对于成为一名熟练的程序员至关重要。随着新信息技术和工作实践的兴起，其范围也在不断扩大。

许多算法的效率和性能直接取决于特定算法用于计算和其他数据操作的数据。数据结构在程序运行或执行期间在主内存中执行存储数据的基本操作，因此内存管理也是一个重要因素，因为它将直接影响程序或算法的空间复杂度。因此，选择合适的数据结构在程序效率和性能方面起着重要作用。

高级数据结构列表

高级数据结构已经发展出许多多样化的形式。高级数据结构可以分为以下几大类：

原始类型
复合或非原始类型
抽象数据类型
线性数据结构
树类型
基于哈希的结构
图

原始数据结构

原始数据结构是机器指令直接操作的基本结构。在不同的计算机上，原始数据结构有不同的表示方法。原始数据结构包括整数、浮点数、字符和指针。一般来说，有八种数据类型，例如：

1. 布尔数据类型： 布尔数据类型由单个比特信息组成，只能存储 true 或 false 值。此数据类型用于跟踪 true 或 false 条件，并且布尔数据类型也用于存储各种条件的结果。让我们编写一个小程序来看看它是如何工作的。

class booleanDataType
{
public static void main(String args[])
{
// Setting the values for boolean data type
boolean Java = true;
boolean Python = false;
System.out.println(Java);   // Output will be true
System.out.println(Python);  // Output will be false
}
}

2. 字节数据类型： 字节数据类型是原始数据类型的一个例子。它是一个 8 位带符号的二进制补码整数，存储从 -128 到 127 的整数。字节数据类型有助于节省大量内存。让我们编写一个小程序来看看它是如何工作的。

class ByteExample {
public static void main(String[] args) {
byte n, a;
n = 127;
a=177;
System.out.println(n); // prints 127
System.out.println(a); // throws an error because it cannot store more than 127 bits
}
}

3. 字符数据类型： 此数据类型存储单个字符，字符必须用单引号括起来，例如“E”或“e”。您也可以使用 ASCII 值来显示特定字符。让我们看一个简单的例子来了解它的工作原理。

public class PrimitiveDataType{
	public static void main(String[] args) {
		//storing a single character
		char  alpha = 'J';
 		//storing the ASCII of the respective character or alphabets
		char a = 65;
		char b = 66, 
		char c = 67;		
		System.out.println(alpha); // prints J
		System.out.println(a); // Displays 65
		System.out.println(b); // Displays 66
		System.out.println(c); // Displays 67
	}//end of main function
}//end of PrimitiveDataType class

4. 短整型数据类型： 短整型数据类型比字节数据类型大，但比整数数据类型小。它存储从 -32,768 到 32,767 的值。此数据类型的默认大小为 2 字节。让我们看一个例子来更好地理解短整型数据类型。

public class PrimitiveDataType{
	public static void main(String[] args) {
		short n= 3435,
		System.out.println(n); // prints the value present in n i.e. 3435
	}//end of main function
}//end of PrimitiveDataType class

5. 整型数据类型： 此数据类型能够存储从 -2,147,483,648 到 2,147,483,647 的整数。在创建带有数值的变量时，通常首选整型数据类型。

public class PrimitiveDataType{
	public static void main(String[] args) {
		int num = 5464564;
		System.out.println(num); // prints 5464564
	}//end of main function
}//end of PrimitiveDataType class

6. 长整型数据类型： 此数据类型是二进制补码 64 位整数。长整型数据类型的默认大小为 64 位，其值范围为 -2^63 到 2^63-1。

public class PrimitiveDataType{
	public static void main(String[] args) {		
		// a variable named num of long is created to store the long value
		long num = 15000000000L;
		// The output of the below System.out.println will print 15000000000 that is the value stored in num
		System.out.println(num); 
		// a variable named num1 of long is created to store the long value
		long num1 = 897155L;
		// The output of the below System.out.println will print 897155 that is the value stored in num1
		System.out.println(num); 
	}//end of main function
}//end of PrimitiveDataType class

7. 浮点型数据类型： 当您需要带有小数的数字时，应使用浮点型，例如 8.88 或 3.14515。此数据类型支持从 3.4e+038 到 3.4e+038 的分数。重要的是要注意，该值应以“f”结尾。让我们看一个具体的例子来更好地理解这种数据类型。

public class PrimitiveDataType{
	public static void main(String[] args) {		
		// a variable named num of float type is created to store the float value
		float num =67;
		// The output of the below System.out.println will print 897155 that is the value stored in num
		System.out.println(num); // prints the floating number value
	}//end of main function
}//end of PrimitiveDataType class

8. 双精度型数据类型： 双精度型数据类型可以存储从 1.7e-308 到 1.7e+308 的分数。请注意，您应该以“d”结尾。

public class PrimitiveDataType{
	public static void main(String[] args) {		
		// a variable named num of double type is created to store the double value
		double num = 79.678d;		
		// The output of the below System.out.println will print 79.678 that is the value stored in num
		System.out.println(num); // prints the double number value
	}//end of main function
}//end of PrimitiveDataType class

非原始或复合数据结构

非原始数据结构是通过组合原始数据结构而创建的。它有点复杂，因为它源自原始数据结构，我们也可以说它是相同或不同数据项的集合。非原始或复合数据结构的一些示例如下：

数组： 数组是一种数据结构，其中项目存储在相邻的内存位置。其思想是对相同类型的对象进行分组。这使得通过简单地将偏移量添加到基值（即数组第一个元素的内存地址，通常用数组名表示）来更快地计算每个组件的位置。
记录： 记录是一种简单的数据结构，也称为结构、struct 或复合数据。在数据库或电子表格中，行是赋予记录的名称。记录是字段的集合，这些字段可以是不同类型的数据，通常具有固定的数量和顺序。记录的字段在面向对象编程中也可能被称为成员；字段也可称为元素，但这可能会混淆集合组件。
联合： 联合是一种值，可以在相同的内存位置拥有多个表示或布局。它由一个可以保存此类数据结构的变量组成。为了定义这些值和变量，一些编程语言支持称为联合类型的特殊数据类型。换句话说，联合类型描述指定了允许的几种原始类型中的哪一种可以存储在其实例中，例如“浮点数或长整数”。与可以定义为包含浮点数和整数的记录（或结构）相反，联合在任何给定时间只有一个值。

抽象数据类型

ADT 是一种对象类型或类，其行为基于一组值和一组函数。ADT 的概念只提到了必须执行哪些操作，而没有提到如何执行这些操作。它不指定数据将在内存中如何存储，或将使用哪些算法来执行操作。它之所以称为“抽象”，是因为它提供了独立于实现的视图。抽象是一个只呈现本质而隐藏细节的过程。

数据类型的运算符不希望了解该数据类型是如何实现的。例如，我们已经使用了 int、float 和 char 数据类型等原始值来理解它们可以在不了解其实现方式的情况下进行操作和执行。因此，用户只需要知道数据类型是什么，而不需要知道它是如何实现的。让我们看一些抽象数据类型的例子：

列表数据结构： 列表或序列是一种抽象数据类型，它表示有限数量的有序值，其中相同的值可能会出现多次。列表实例是元组或有限序列的计算机表示。流是列表（可能）无限的类似物。列表是最基本类型的容器，因为它们包含其他值。如果相同的值出现一次以上，则每次出现都被视为一个单独的项目。
所有编程语言都支持列表数据类型，列表和列表操作都有自己的语法和语义。列表通常是通过在分隔符（如括号“()”、方括号“[]”、大括号“{}”或尖括号“<>”）内，以逗号、分号和/或空格分隔的序列来组合项目而形成的。在某些语言中，列表类型可以像数组类型一样被索引或切片，在这种情况下，数据类型更准确地称为数组。
队列数据结构： 队列是按顺序存储的元素集合，可以通过在序列的一端添加元素并在另一端删除元素来更改。根据约定，添加元素的序列末端称为队列的后部、尾部或末端。删除元素的序列末端称为队列的头部或前端，就像人们排队等待商品或服务一样。
队列的操作使其成为一种先进先出 (FIFO) 数据结构。在 FIFO 数据结构中，首先添加到队列的元素也是首先被移除的元素。这相当于要求在添加新元素时，必须先删除所有之前的元素，然后才能删除新元素。队列是一种线性数据结构，也称为顺序集合。队列通常在计算机程序中使用，在其中作为具有访问过程、抽象数据结构或面向对象语言中的类的数据库结构。
栈数据结构： 栈是一种抽象数据类型，它充当元素集合，并有两个主要操作：
Push 将元素添加到集合中，而 Pop 移除最近添加但尚未移除的元素。
元素从栈中移除的顺序产生了 LIFO（后进先出）的缩写。此外，peek 操作可以在不修改栈的情况下访问栈顶。由于这种结构类似于堆叠在一起的物理物品的集合，因此术语“栈”指的是这种类型的结构。

线性数据结构

如果数据结构元素形成线性模式或序列，则该数据结构为线性。

控制表： 控制程序的表称为控制表。它们没有严格的规则，可以根据您的需求轻松修改。
图像： 整个计算机系统的图形表示，可以在关闭后重新生成图像。
矩阵： 矩阵是一种二维数据结构，每个维度中的元素类型相同。数据框是二维的，不同的列包含不同的数据类型；但是，一列中的所有值必须是相同的数据类型，并且所有列的长度必须相同。
列表： 列表或序列是一种抽象数据类型，它表示有限数量的有序值，其中相同的值可能会出现多次。列表实例是元组或有限序列的计算机表示；流是列表（可能）无限的类似物。

树类型

树是一种广泛使用的数据抽象类型，它表示层次树结构，由一组链接的节点组成，其中包含根值和具有父节点的子节点子树。

树数据结构可以迭代地定义为一组节点，每个节点包含一个值和指向其他节点的引用列表。“根节点”是树的起点，“子节点”是引用节点。没有重复的引用，也没有指向根的引用。

二叉树： 二叉树可以定义为一种树，其中每个父节点最多可以添加两个子节点。子节点称为左子节点和右子节点。二叉树是最受欢迎的树之一。当我们对二叉树应用各种约束和特性时，会形成 AVL 树、BST（二叉搜索树）、RBT 树等其他树。我们将在后面的讨论中详细解释这些类型的树。换句话说，我们可以说一个泛型树，其元素最多有两个子节点，称为二叉树。由于二叉树中的每个元素最多只能有 2 个子节点，因此我们通常将它们命名为左子节点和右子节点。
决策树： 决策树是一种决策工具，它使用类似树的模型来表示决策及其潜在结果，例如可能性事件结果、资源成本和效用。它是表示仅由条件控制语句组成的算法的一种方法。决策树是机器学习中的标准工具。它们在运筹学中广泛使用，尤其是在决策分析中，以帮助我们确定最有可能实现目标的策略。
其他树类型包括 B 树、跳跃表、融合树、堆、莱昂纳多堆、基数树、后缀树、FM-索引、意大利面栈、玫瑰树、芬威克树、空间分割树、区间树、线段树、覆盖树、极小极大树、手指树、解析树、表达式树、加权平衡树。

基于哈希的结构

以下是基于哈希的结构类型：

哈希列表： 哈希列表只是与一组数据项关联的哈希值的集合，这些数据项在文件或文件夹系统或其他连接数组格式中相互链接。哈希列表用于分析数据库或其他环境中的数据、访问其中一个或多个项目、确定数组的大小或用于其他调查目的。在数据安全方面，哈希列表也非常有用。将哈希放入列表中，而不是对整个块使用单个哈希值，可以更轻松地在点对点网络或其他连接模型上检查传入输入，并确定列表中对应于哈希值的任何单个数据集是否已被泄露。使用哈希列表分析一组数据块可以分解分析，更容易检测破坏性黑客攻击。这是哈希列表在哈希加密系统中的常见应用。
双重哈希： 双重哈希是一种计算机编程技术，在哈希表中与开放寻址发生冲突时，它使用键的二次哈希作为偏移量来解决哈希冲突。开放寻址的双重哈希是表 T 上的经典数据结构。双重哈希技术使用一个哈希值作为表的索引，然后以一个间隔前进，直到找到目标值、到达空位或尝试搜索整个表；但是，该间隔由一个单独的、独立的哈希函数确定。与线性探测和二次探测的替代冲突解决方法不同，间隔由数据确定，使得映射到同一位置的值具有不同的桶模式；这最大限度地减少了重复冲突和聚类效应。

图

图数据结构由一组有限的（可能是可变的）顶点（也称为节点或点）以及一组无序对（对于无向图）或一组有序对（对于有向图）组成。这些对在无向图中被识别为边（有时称为链接或线），但在某些情况下也被称为箭头或弧。顶点可以是内部图元素或由整数索引或引用表示的外部项。

因此，根据这些节点和顶点的相对位置，存在不同类型的图。在本文中，我们将看到的图的不同类型是：空图、平凡图、无向图、有向图、连通图、不连通图、正则图、完全图、环图、有环图、无环图、有限图、无限图、二分图、平面图、简单图、多重图、伪图、欧拉图、哈密顿图。

完全图： 如果图中所有顶点的任意一对之间都存在边，则称该图为完全图。换句话说，我们可以说所有顶点都连接到图的所有其余顶点。具有“n”个顶点的完全图包含恰好 nC2 条边，并且具有“n”个顶点的完全图表示为 Kn。
正则图： 要被称为正则图，它必须满足一个主要条件：所有图的顶点都应具有相同的度。通过顶点的度，我们指的是与图的特定顶点关联的节点数。如果所有图的节点都具有相同的度值，则该图称为正则图。如果图中所有顶点的度值为六，则该图称为 6-正则图。如果图中所有顶点的度都为“k”，则称为“k-正则图”。

下一主题对 0、1 和 2 的数组进行排序

高级数据结构