本笔记依据《数据结构（c语言版）》（第二版）殷人昆和《数据结构精讲与习题详解》整理

第一章绪论

1.1数据结构的概念及分类

1.1.2与数据结构相关的基本术语

7.抽象数据类型ADT

思考题：系统开发中数据设计三视图为数据内容，数据结构和数据流其中有关数据结构的道路主要涉及数据元素之间的关系，那么数据元素内容应在什么时候考虑？

数据元素的内容应在系统开发的早期阶段考虑，并且通常是在数据设计的第一个视图——数据内容视图中进行定义和确定的。数据设计的三个视图包括数据内容视图、数据结构视图和数据流视图，这些视图通常是并行进行的，但它们之间存在着一定的依赖关系。

以下是关于何时考虑数据元素内容的一些重要考虑因素：

需求分析阶段： 在系统开发的早期，首先要进行需求分析。这一阶段涉及与项目相关的各方（包括业务用户、利益相关者等）合作，以了解他们的需求和期望。在这个过程中，要确定系统需要收集、存储和处理哪些数据。这有助于确定数据元素的内容。
数据模型设计： 在需求分析之后，您可以开始设计数据模型，其中包括定义数据元素的内容。这通常涉及到创建实体-关系图（ER图）或其他数据建模工具，以明确定义数据元素之间的关系、属性和约束。
数据字典： 创建数据字典是一种记录数据元素内容和定义的方式。数据字典包含了关于每个数据元素的详细信息，包括名称、数据类型、长度、格式、描述、取值范围等。这是确保整个开发团队对数据元素有清晰共识的重要工具。
数据结构视图： 一旦数据元素的内容确定，您可以开始考虑数据元素之间的关系和如何组织它们以满足系统的功能需求。这会涉及到定义表、字段、键和约束等。

总之，数据元素内容的考虑应该尽早进行，并与系统开发的其他阶段紧密协调。这有助于确保系统可以有效地收集、存储和处理所需的数据，同时也有助于减少后期开发中的变更和修正。在整个系统开发过程中，数据设计的三视图都需要不断协同工作，以确保数据的一致性、完整性和可用性。

1.1.3数据结构的分类

2.逻辑结构与存储结构

映射到_使用.jpg

3.逻辑结果的分类

（1）线性结构
（2）非线性结构

多维数组和广义表属于线性表的扩展，从宏观山看，不具有线性结构的一对一的特点，从可共享情况来看，又有多对多的特点

多维数组（Multidimensional Array）： 多维数组是一种扩展的线性表，它可以看作是多个一维数组的组合。多维数组中的元素是通过多个索引（通常是多维的）来访问的。这意味着每个元素可以由多个维度的索引组合来唯一确定，因此不再具有传统线性表的一对一结构。例如，在二维数组中，元素可以通过行索引和列索引来定位，这是多对多的关系。
广义表（Generalized List）： 广义表是一种更灵活的数据结构，它允许在一个表中包含多种类型的元素，包括原子元素和子表（广义表的嵌套）。这使得广义表可以表示更复杂的数据结构，如树状结构或图状结构。因为广义表可以包含多个元素，其中一些可以是子表，因此也具有多对多的特点。

从宏观角度来看，多维数组和广义表都在某种程度上扩展了线性表的概念，允许更复杂的数据结构和多对多的关系。这使它们更适合表示和处理更复杂的数据组织需求。

从可共享性的角度来看，这两种数据结构也可以包含多对多的关系。在多维数组中，多个元素可以共享相同的行或列，而在广义表中，多个元素可以共享相同的子表。这种共享性使得数据的组织更加灵活，可以更有效地表示一些复杂的数据关系。

思考题：数据的逻辑结构是否可以独立于存储结构来考虑，反制数据的特殊结构是否可以独立于逻辑结构来考虑？

数据的逻辑结构和存储结构通常是相互关联的，但在某些情况下可以独立考虑，具体取决于数据管理和操作的需求以及系统设计的目标。让我们更详细地探讨这两种情况：

逻辑结构独立于存储结构：

在某些情况下，您可以定义数据的逻辑结构，而不必关心其具体的存储方式。这通常发生在高层数据模型的设计阶段，例如在数据库设计中。您可以首先定义数据的实体、属性、关系和约束等逻辑结构，而不必考虑如何在物理存储层面实现它们。数据库管理系统会负责将逻辑结构映射到物理存储结构，以便高效地存储和检索数据。这种分离逻辑和物理结构的方法有助于数据抽象和数据独立性，使系统更易于维护和扩展。
存储结构独立于逻辑结构：

在另一方面，有些情况下，您可能需要关注数据的存储方式，而不考虑其逻辑结构。这可能出现在低层数据存储和处理的情况下，例如在编程中。在这种情况下，您可能需要考虑如何在内存或磁盘上组织和访问数据，以便实现特定的算法或性能优化。这可能涉及到数据结构的选择和数据布局的优化，而不必关心数据的逻辑关系。

总的来说，逻辑结构和存储结构的关系通常是相互关联的，但可以根据需要独立考虑。在实际应用中，合理的抽象和分离可以提高系统的可维护性、可扩展性和性能。不过，在设计和开发过程中，需要确保逻辑结构和存储结构之间的一致性，以确保数据在逻辑和物理层面的正确性和有效性。这通常需要仔细的规划和协同工作，以平衡逻辑和存储需求。

思考题：集合结构中的元素之间没有特定的联系，如图那么集合结构属于线性结构还是非线性结构？这是否意味着需要借助其他结构来表示？

1.1.4数据结构的存储结构

数据结构根据存取方法的不同，可分为3类:

(1）直接存取结构。可以按序号直接存取某一无素，如向量、多维数组、散列表等。
(2）顺序存取结构。只能从序列中第一个元素起，按逻辑顺序逐个访问元素，如各种链表结构(单链表、循环链表、双向链表、二叉或三叉链表、图的邻接表等）就属于此类。
(3）索引结构。通过关键码来识别和访问元素，如线性索引、多叉查找树等。

一般地,常用的4种存储方式如下:

(1）顺序存储方式。该存储方式把逻辑上相邻的元素存放到物理位置上相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接位置关系来体现。由此得到的存储结构称为顺序存储结构，通常，顺序存储结构可借助程序设计语言中的一维数组来描述。

(2）链接存储方式。该存储方式不要求逻辑上相邻的元素在物理位置上也相邻，元素之间的逻辑关系由附加的链接指针指示。由此得到的存储结构称为链表存储结构，通常，链表存储结构要借助程序设计语言中的指针类型来描述。

(3）索引存储方式。该存储方式在存储元素信息的同时还建立索引表。索引表中每一项称为索引项,索引项的形式是（关键码,地址)。关键码是能够标识一个元素的数据项。按照索引项是针对每个元素还是针对一组元素，可分为稠密索引和稀疏索引。此外，根据索引表是一层还是多层,可分为线性索引和多级索引。
(4）散列存储方式。该存储方式根据元素的关键码通过一个函数计算直接得到该元素的存储地址。

上述4种基本的存储结构既可以单独使用，也可以组合起来建立数据结构的存储结构。同一种逻辑结构可以有不同的存储结构。选择何种存储结构来表示相应的逻辑结构，要视不同的资源要求而定。对于数据结构的实现者来说，选择存储结构主要考虑的要素如下:

(1）访问频率。对于其内容需要经常访问但修改不频繁的数据结构,宜采取存取速度快、存储利用率高的存储结构。
(2）修改频率。对于其内容经常需要修改的数据结构,宜采用修改速度快、尽可能不移动元素的存储结构。
(3）安全保密。对于安全保密要求高的数据结构，宜采用面向对象方法，用类的继承式设计存储结构，用公有(public)、私有(private）和保护(protected）来划定访问级别。要考虑运算的时间和空间要求以及算法的简单性。

1.1.5定义在数据结构上的操作

定义在数据结构上的操作是一个操作集,它提供了操纵数据结构的各种运算。对于不同的数据结构，操作集所包含的操作也有所不同。基本的操作有以下几种:

创建。构建属于数据结构的一个实例，对其所有成分赋予初值。
销毁。撤销属于数据结构的一个实例，释放实例占用的动态分配的存储空间。
查找。按照给定值搜索数据结构的一个实例内是否有满足要求的元素或结点。
插入。把新元素按照指定位置插入到数据结构的一个实例内。
删除。删去数据结构的一个实例内指定的元素或结点。
排序。把线性结构内所有元素按照指定域的值从小到大或从大到小重新排列。

思考题为何在数据结构课程中既要讨论各种在解决问题时可能遇到的典型的逻辑结构还要讨论这些逻辑结构的存储映像(存储结构)，此外还要讨论这种数据结构的相关操作(基本运算）及其实现?
在数据结构课程中涵盖逻辑结构、存储结构以及相关操作的原因有以下几点：

理解问题和选择合适的数据结构： 数据结构是解决问题的关键。在解决现实世界的问题时，我们首先需要选择适当的数据结构，以便高效地组织和操作数据。了解不同的逻辑结构，如栈、队列、链表、树、图等，有助于学生理解何时应该使用哪种数据结构，以满足问题的需求。
存储映像和内存管理： 理解存储结构有助于学生了解数据在计算机内部的物理存储方式。这对于内存管理和性能优化至关重要。不同的存储结构会对数据的访问和操作产生不同的影响，学生需要知道如何选择适当的存储结构以及如何有效地使用内存。
操作和算法设计： 数据结构的基本操作（基本运算）包括插入、删除、查找、遍历等。学生需要了解这些操作的特点和复杂度分析，以便能够设计高效的算法。讨论这些操作还有助于学生理解数据结构的功能和用途。
实际应用和编程： 数据结构不仅仅是理论概念，它们在实际编程中起着关键作用。学生需要知道如何实现各种数据结构，以便将它们应用到编程项目中。这包括了解如何在编程语言中表示和操作数据结构。

综上所述，数据结构课程的综合性质旨在帮助学生建立解决问题的整体思维和编程能力。逻辑结构、存储结构和相关操作之间的关系密切相关，学生通过学习这些内容可以更好地理解和应用数据结构，以解决各种计算和信息处理问题。这些知识不仅对计算机科学专业的学生有价值，对于任何需要处理和组织数据的领域都具有广泛的适用性。

1.2.1 C语言的数据类型

1.构造性struct

typedef struct{
long number;
char *name;
float score;
int code;
}Examinee;

思考题：如果结构定义时没有写typedef，定义的是一个类型吗？通过Examinee s1定义的考生记录s1是否属于该类型的变量？
如果在结构定义时没有使用typedef，那么该结构定义并不会创建一个新的类型，而只会定义一个结构。这意味着Examinee只是一个结构的标签或标识符，而不是一个独立的数据类型。

当您使用Examinee s1来定义考生记录s1时，s1不会被认为是该类型的变量，因为在没有使用typedef的情况下，Examinee只是一个结构的标签，而不是数据类型。要使s1成为该类型的变量，您需要使用typedef来为结构定义创建一个新的数据类型。例如：

typedef struct {
    long number;
    char *name;
    float score;
    int code;
} Examinee;

Examinee s1; // 现在s1是Examinee类型的变量

通过这种方式，您定义了一个Examinee类型的变量s1，它可以存储一个考生记录的数据。如果没有使用typedef，s1将无法识别Examinee作为类型，因此会导致编译错误。使用typedef有助于提高代码的可读性和可维护性，因为它允许您为结构定义创建更具有意义的数据类型名称。