【数据结构与算法】数据结构（Data Structure）的基本概念及其研究对象

什么是程序

算法+数据结构=程序 —— Nicklaus Wirth(尼古拉斯·沃斯)

Niklaus Wirth是一位著名的计算机科学家，他提出了"程序=算法+数据结构"的观点。他认为，程序不仅仅是执行特定任务的一段代码，而是由算法和数据结构两部分组成的。算法定义了程序如何操作数据以达到预期的结果，而数据结构则定义了程序如何存储和组织数据。

什么是数据结构

数据结构是计算机科学中的一个核心概念，它是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构定义了数据的组织、管理和存储格式，它使得数据可以高效地被访问和修改。数据结构也可以看作是数据对象在计算机中的存储方式以及在这个对象上的一组操作。

数据结构是算法的基础，不同的数据结构适合于不同的算法。通过选择和设计合适的数据结构，可以提高算法的效率。常见的数据结构包括数组、链表、栈、队列、树、图、哈希表等。

数据结构相关的基本概念

• 数据（data）：数据是描述客观事物的符号，是能被计算机识别，并输入给计算机处理的符号集合。
• 数据元素（data element）：数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。
• 数据项（data item）：一个数据元素可以由若干个数据项组成。数据项是数据的不可分割的最小单位。
• 数据对象（data object）：性质相同的数据元素的集合，是数据的子集。
• 数据结构（data structure）：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
• 逻辑结构：数据对象中数据元素之间的相互关系。
• 存储结构：数据结构在计算机中的表示（也称物理结构）。
• 抽象数据类型（Abstract Data Type，ADT）：是一个数学模型以及定义在该模型上的一组操作。ADT定义了数据类型的行为，但并没有给出数据类型的具体实现。

数据结构的研究对象

• 逻辑结构：数据元素之间的逻辑关系，这种关系是与数据的集合方式无关的。主要有四种逻辑结构：线性结构、树形结构、图形结构和集合结构。
• 存储结构：数据在计算机内存中的存储方式，也称为物理结构。主要有顺序存储、链式存储和索引存储等方式。
• 数据操作：定义在数据上的一些操作（增删改查）。

例子

1. 城市网络铺设：

   • 逻辑结构：在逻辑层面上，城市网络铺设可以被看作是一个图结构，其中顶点代表城市，边代表网络连接。这个图可以是无向的（如果网络连接是双向的），也可以是有向的（如果网络连接是单向的）。
   • 存储结构：在存储层面上，这个图可以用邻接矩阵或者邻接表等方式存储。邻接矩阵是一个二维数组，其中的元素表示对应的两个城市之间是否有网络连接；邻接表则是一个一维数组，其中的每个元素是一个列表，表示对应的城市连接到的所有城市。
   • 逻辑结构和存储结构的关系在于，逻辑结构定义了城市之间的网络连接，而存储结构则决定了如何在计算机内部表示这些连接。

2. 计算机文件系统：

   • 逻辑结构：在逻辑层面上，文件系统通常被组织成一个层次化的结构，也就是我们常说的目录（文件夹）和文件。每个目录可以包含其他目录或文件，每个文件都位于某个目录下。
   • 存储结构：在物理存储层面上，文件系统的存储结构可能会依赖于特定的文件系统类型和底层的存储设备。例如，文件可能会被分割成多个块（block）存储在磁盘的不同位置，而目录则存储了文件名到这些块的映射。
   • 逻辑结构和存储结构的关系在于，逻辑结构定义了用户如何与文件系统交互，而存储结构则决定了文件系统如何在底层设备上实现这种交互。

3. 课程安排：

   • 逻辑结构：在逻辑层面上，课程安排可以看作是一个二维的表格，其中行代表时间（如一周内的每一天、每一天的每一个时段），列代表地点（如教室）。表格中的每个单元格则代表一个课程。
   • 存储结构：在存储层面上，这个表格可以用一个二维数组来存储。数组的每个元素代表一个课程，元素的位置对应于课程的时间和地点。
   • 逻辑结构和存储结构的关系在于，逻辑结构定义了课程的时间和地点，而存储结构则决定了如何在计算机内部表示这些信息。

4. 成绩单：

   • 逻辑结构：在逻辑层面上，成绩单可以看作是一个二维的表格，其中行代表学生，列代表课程，表格中的每个单元格代表一个成绩。
   • 存储结构：在存储层面上，这个表格可以用一个二维数组来存储。数组的每个元素代表一个成绩，元素的位置对应于学生和课程。
   • 逻辑结构和存储结构的关系在于，逻辑结构定义了学生的成绩，而存储结构则决定了如何在计算机内部表示这些成绩。