第一章 什么是数据结构

数据结构的定义和起源

数据结构

数据结构是计算机科学中用来组织和存储数据的一种方式。它通常由数据元素、数据之间的关系以及对数据的操作三个部分组成。
数据结构可以提高程序的运行效率，减少内存占用，并且可以通过不同的数据结构选择实现不同的算法。

数据结构的来源

数据结构的概念最早可以追溯到 1940 年代。当时，计算机科学家们开始思考如何有效地存储和操作数据，以便更高效地解决问题。数据结构这一概念在这个背景下被提出。

早期的数据结构包括数组、链表、栈和队列等基本数据结构，这些数据结构被广泛应用于计算机程序设计中。1960 年代，树和图等更加复杂的数据结构也被引入计算机科学领域。

当前，数据结构已成为计算机科学中的核心概念之一，并且在各种计算机应用领域中都有重要作用。

数据：

数据是描述事物特征或属性的数字、文字、符号或图形等信息的集合。在计算机科学中，数据通常以二进制的形式存储和处理，例如0和1。

数据可以分为多种类型，包括数值型数据、字符型数据、布尔型数据等。数值型数据包括整数和浮点数等数字类型；字符型数据则包括文本字符串和单个字符；布尔型数据则只有两个取值，即真和假。

数据在计算机科学中扮演着非常重要的角色，它们是计算机程序输入、处理和输出的基础。各种数据结构和算法都是为了更好地组织和处理数据而设计的。

数据元素

数据元素是数据结构中最基本的单位，它通常指一个单独的数据项。例如，在一个整数数组中，每个整数就是一个数据元素；在一个字符串链表中，每个字符串就是一个数据元素。

一个数据元素通常包含多个数据项，每个数据项表示该数据元素的一个特定属性或特征。例如，在一个学生信息系统中，一个学生的数据元素可以包含姓名、学号、年龄、性别等多个数据项。

在数据结构中，数据元素通常被组织成不同的数据结构形式，如数组、链表、树、图等。这些数据结构通过不同的方式将数据元素相互连接起来，以便更有效地组织和处理数据。

数据项

数据项是指数据元素中的一个单独属性或特征，它通常是一个原子性的数据单元。在一个数据元素中，可能会包含多个数据项，每个数据项表示该数据元素的一个特定属性。

例如，在一个学生信息系统中，一个学生的数据元素可能包括姓名、学号、年龄、性别等多个数据项。其中，姓名、学号、年龄和性别都是不同的数据项。

数据项的类型可以是数值型、字符型、布尔型等，具体取决于它所代表的信息类型。在计算机程序设计中，数据项通常被使用来进行计算、比较、存储和检索等操作。

数据对象

数据对象是指一组具有相同性质或特征的数据元素的集合。数据对象可以是一个单独的数据元素，也可以是多个数据元素的集合。

例如，在一个学生信息系统中，所有学生数据元素的集合就构成了一个数据对象，这个数据对象包含多个数据元素，每个数据元素表示一个学生的基本信息，如姓名、学号、年龄、性别等。

数据对象通常与数据结构密切相关，不同的数据结构可以用来组织和管理不同类型的数据对象。例如，数组可以被用来存储一组具有相同数据类型的数据对象；链表可以用来存储一个动态的、大小不固定的数据对象集合；树和图则可以用来存储更复杂的数据对象关系。

数据结构

数据结构可以看作是数据对象及其之间的关系的集合，它们被用来表示和操作应用程序中的各种数据对象。数据结构可以分为线性结构和非线性结构两类。

线性结构包括数组、链表、堆栈、队列等；它们的特点是数据元素之间存在一对一的线性关系。例如，在一个整数数组中，每个元素都与相邻的元素存在一定的顺序关系。

非线性结构包括树、图等；它们的特点是数据元素之间存在多对多的非线性关系。例如，在一个文件系统中，不同的文件和目录之间存在复杂的层次关系。

数据结构是计算机程序设计的基础，它们被广泛应用于各种领域，如数据库、图形图像处理、人工智能等。

逻辑结构

实际上，逻辑结构通常被划分为三种类型：线性结构、树形结构和图形结构。下面是对每种逻辑结构的简要描述：

• 线性结构：线性结构是指数据元素之间存在一对一的相邻关系，每个元素都只有一个直接前驱和一个直接后继。常见的线性结构包括数组、链表、堆栈和队列等。

• 树形结构：树形结构是指数据元素之间存在一对多的层次关系，即每个元素都可以有多个子节点，但只有一个父节点。树形结构常用于组织具有层次结构的数据，例如文件系统、网站导航等。

• 图形结构：图形结构是指数据元素之间存在多对多的复杂关系，即每个元素可以与多个其他元素相连。图形结构可用于表示各种复杂的关系网络，例如社交网络、路线图等。

除了以上三种逻辑结构外，有些资料会将集合作为第四种逻辑结构。集合是指具有相同特征或属性的数据元素的集合，它们之间没有明显的顺序关系。但是，集合并不经常作为单独的逻辑结构来处理，而是作为其他逻辑结构的一部分来使用。

物理结构

物理结构是指数据在计算机存储器中的组织形式和存储方式。它决定了计算机如何对数据进行存取、处理和管理。

常见的物理结构包括：

• 顺序存储结构：把数据元素存放在一段连续的存储空间中，数据元素之间的物理位置与逻辑关系相同。例如，数组就是一种顺序存储结构。

• 链式存储结构：通过每个数据元素中存储下一个元素的地址，把数据元素链接起来。链表就是一种常见的链式存储结构。

• 索引存储结构：通过建立索引表，将数据元素的位置存储在索引表中，从而提高数据访问效率。例如，数据库中的索引就是一种索引存储结构。

• 散列存储结构：通过散列函数将数据元素映射为唯一的地址，然后将数据元素存储在计算机的内存或磁盘中，以提高数据的查找和存取效率。散列表是一种常见的散列存储结构。

不同的物理结构有不同的特点和适用范围，开发人员可以根据具体需求选择最合适的存储方式。

逻辑结构是面向问题的，物理结构是面向计算机的

数据类型

数据类型是指一组值的集合和定义在这些值上的一组操作，用于描述计算机程序中各种数据的形式。常见的数据类型包括整数型、浮点型、字符型、布尔型、数组、结构体等。

以下是常见的数据类型：

• 整数型：表示整数，包含有符号整型和无符号整型两种，例如int、long、short等。

• 浮点型：表示实数，包括单精度和双精度两种，例如float、double等。

• 字符型：表示单个字符，例如char。

• 布尔型：表示真或假，即逻辑值，例如bool。

• 数组：表示同一类型的多个元素按照一定顺序排列，例如int[]、char[]等。

• 结构体：表示不同类型的多个元素按照自定义格式排列，例如struct。

不同的数据类型支持不同的操作，例如整数型可以进行加减乘除等基本运算，而字符型可以进行连接等操作。正确地选择和使用数据类型对于编写高效、可维护的程序非常重要。

抽象数据类型

抽象数据类型（ADT）是一种定义在数学层次上的数据类型，它定义了数据对象、数据对象之间的关系以及对这些对象执行的操作。ADT强调的是数据类型的逻辑特性，而不是物理实现细节。

ADT包括两个部分：一是数据类型的抽象描述，即规定数据类型的一组属性和操作；二是数据类型的具体实现，即如何用编程语言来实现这些属性和操作。

ADT主要用于软件设计中，将程序的实现与数据的表示和处理解耦，提高了程序的可读性、可重用性和可维护性。常见的ADT包括向量、链表、栈、队列、树、图等。

例如，栈就是一个典型的ADT。栈的抽象描述包括它的元素集合，可以执行的操作包括入栈、出栈、判断是否为空、获取栈顶元素等。栈的具体实现可以使用数组或链表等数据结构来实现。

使用ADT可以大大简化程序设计和开发过程，使程序更加模块化、灵活和易于维护。