13003数据结构与算法全书框架

之前学习过的内容

一、数组与矩阵

二、线性表

三、广义表

四、数与二叉树

五、图

六、排序与查找

考试题型的分值分布如何？

本次内容概述

之前学习过的内容有

二、线性表

顺序表

链表，包括单链表，循环链表，双向链表

绪论

第一节概览

之前学过的有

顺序存储方法（结构），链式存储方法（结构）

另外两种存储方法没学

• 原来存储方法，是从存储角度来考虑的数据结构，之前学的确实有欠缺

见，Day11-【软考】稀疏矩阵考试中如何计算？以及线性表的分类有哪些？，中：什么是线性表？线性结构中顺序表和链表

这一天学习的内容，有好多要深化的

什么是数据、数据元素，数据项，数据项的值？

• 每一名学生的，学号，姓名，各科目成绩；每一本图书的，书名，作者名，出版社名，书号，出版日期，这一条记录，就是一个数据元素

  表中共30个数据元素，因为一共有30个学生，也就是有30行，30个数据元素

  图中，每个椭圆都表示一个数据元素

  • 这个怎么理解，看图知道就行

    要一层层看，特别是下层，每一层的椭圆，确实就是一个个数据元素，并且每一层元素之间，居然构成了树结构，这就是数据元素之间的关系

  这30个数据元素，居然是一种线性结构的数据元素集合，也就是说，学号这一栏的顺序不可改变

• 学号，姓名；书名，作者名，就是数据项

​ 表中每个数据元素，有5个数据项，分别是学号，姓名，性别，出生日期，籍贯

​ M202210300，王义平，山东，都是数据项的值，学号的值，一定不同，有特殊含义，与学生一一对应，其他的值，可以相同

​ 在数据结构中，数据的最小不可分割的单位是数据项

• 全部学生的记录；全部图书的记录，构成了数据

  数据元素作为一个完整的对象(整体)是构成数据的基本单位。

​

什么是数据结构？分哪两种集合形式（逻辑和存储）？

带有结构特性的数据元素集合构成数据结构。

数据结构又分为逻辑结构和存储结构

也就是说，数据元素集合，有两种集合形式

逻辑结构有哪4类？每一类涉及哪些操作？

从逻辑角度来看，基本的数据结构包括4类，分别是集合、线性结构、图结构和树结构。

1、集合由元素构成，是数学中最基本的概念之一。集合中各元素之间没有次序关系

涉及集合的操作包括：

将新元素加入集合、从集合中删除指定元素

判定某元素是否属于集合等

判定集合是否为空、

求两个集合的并集、求两个集合的交集、求一个集合的补集等

• 是不是不存在关系

集合的操作可以借用线性结构的操作来完成，一般不单独讨论集合。

当然，如果还有其他的需求，则也可以使用树结构来完成。；原来集合，特殊情况下，也可以使用树结构来操作

2、线性结构是数据元素之间存在着先后次序关系的结构，每个元素都对应着一个唯一的次序，这个次序决定着元素的位置。

表1-1某班30名学生的基本信息，就是一种线性结构

包含“M2022103001”的记录是第一个元素，包含“M2022103030”的记录是第30个元素。

也就是说，头，和尾，是固定的，第一个，和最后一个，是固定的数据元素

排在每个数据元素前面的元素是唯一的，称为直接前驱。

同样地，排在每个数据元素后面的元素也是唯一的，称为直接后继

当然，第一个和最后一个元素是例外的，第一个元素没有直接前驱，最后一个元素没有直接后继。

• 存在关系的元素个数：数据元素之间是一对一的关系

3、图结构是一种网状结构

• 存在关系的元素个数：多对多关系

4、树结构可以被看作图的特例

图 1-1一本书的目录构成的树，就是一个树结构

• 存在关系的元素个数：一对多关系；看来特例，就是把多对多，变成一对多关系；

• 这不就是数据库中的“联系”的联系类型么，看来最好是把一对多，转成多对多关系，才方便存储和计算

树结构和图结构都是比线性结构更复杂的结构，它们属于非线性结构。

原来线性结构（集合，线性结构），非线性结构（图结构，树结构），都是只是从逻辑角度，来对数据结构进行的分类

之前的学习，有点不全面，见，Day11-【软考】稀疏矩阵考试中如何计算？以及线性表的分类有哪些？，中：数据结构有哪几种？线性结构和非线性结构

算法的设计主要基于数据的逻辑结构，关注的是哪些数据元素之间存在相互关系，以及算法中要按照什么样的次序对哪些数据元素进行何种操作。

存储结构有哪4类？每一类和逻辑存储有何关联？

为何还要从存储角度去考虑？

因为具体实现算法时要依赖于相应的存储结构，只有知道了数据元素的存储方式，才能实际访问数据元素和对其进行具体的操作。

数据元素及其关系在计算机内的存储方式，称为数据的存储结构，也称为物理结构。

数据结构常用的存储方法有以下4种。

1、顺序存储方法，是和线性结构关联的

逻辑上相邻的数据元素，存储到物理位置相邻的存储单元中，这样的存储方法称为顺序存储方法。

在使用程序设计语言中的一维数组保存线性结构中的数据元素时，采用的就是顺序存储方法。

相应的存储结构称为顺序存储结构。

什么是一维数组？

见，Day11-【软考】数据结构与算法中，如何计算一维数组、二维数组？，中：一、数组与矩阵

2、链式存储方法

逻辑上相邻的数据元素，不要求其存储的物理位置也相邻，通常借助于程序设计语言中的指针来指示数据元素间的逻辑关系。

这样的存储结构称为链式存储结构。

3、索引存储方法

索引存储方法针对数据元素建立索引表。

索引表由索引项组成，索引项指示数据元素所在的物理位置。通过索引项，可以加快查找数据元素的速度。

• 好像之前学习过这个索引，一时半会又找不到了

4、散列(哈希)存储方法

它根据数据元素的关键字计算出该元素的物理存储位置。

• 好像之前学习过这个关键字，一时半会又找不到了

  见，Day13-【软考】长文！什么是散列表查找？以及所有的排序算法是怎样的？如何进行堆排序（重点！）？，中：查找数据时，无需查表，根据规则进行计算即可

通常，使用称为散列表的一维数组作为保存元素的结构。

类型和数据项的值的关系是什么？什么是数据类型？

类型即值的一个集合。

也就是数据项的值，的一个集合

比如，整型就是整数的集合。可以为这些类型定义运算，使用相应的运算符表示对应的操作。

例如，对于整数集合，定义的运算有加法、减法、乘法整除和取模等，由此确定了允许对整数进行的操作。

​ 对于布尔类型(逻辑类型)，可以进行的操作包括逻辑与、逻辑或和逻辑非等。

类型加上允许对该类型数据进行的一组操作，称为数据类型。

基本类型有哪两种？

所有程序设计语言都会提供基本类型。

• 若一个类型所表示的值不可再分解，则该类型称为原子类型，

如C语言中的整型、实型等都是原子类型。

• 与之相对的是结构类型。结构类型的值可以再细分，即它是由若干个分量按某种结构组成的。

例如，C语言中的结构体、数组都是结构类型。

构成结构的分量可以是原子类型的，也可以是结构类型的。

抽象类型是什么？

除了程序设计语言中提供的基本类型以外，还可以定义抽象意义下的类型

并为该类型定义一组相关的操作

这样定义的数据类型称为抽象数据类型(ADT)。

抽象数据类型的定义包括类型的名字及对各个操作的刻画，也就是要明确“做什么”。

对于每个操作，要规定操作的名字、操作执行的前提条件、输入和输出分别是什么等。

每个操作通常表示为一个函数或方法。

抽象数据类型通常都是程序设计语言中没有提供的类型。

在给出抽象数据类型的定义时，尚未明确所定义类型的数据元素的存储方式，；用顺序，还是链式等等不知道

在实现环节，才会给出所定义的类型中涉及的数据元素使用哪种方式保存及如何保存。

有了存储结构，才能具体实现各操作，也就是实现“如何做”。

意思就是，在实现环节，才会进行明确，明确存储结构

再明确函数，或方法