3/14/24数据结构、线性表

 

目录

 数据结构

数据结构三要素

逻辑结构

存储结构

 数据运算

时间复杂度

空间复杂度

线性表

线性表定义

静态分配

动态分配

线性表插入

线性表删除

---

 十天的时间学完了C语言督学课程，最后终于是可以投入到408的科目学习当中。关于数据结构和算法的学习很多部分在督学课中都对逻辑结构以及物理结构进行了解析并进行了实战。接下来就是不断复习巩固，到最后再回看数据结构当做复习吧。

 数据结构

数据元素是数据段基本单位，通常作为一个整体。由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据结构强调数据元素集合之间的关系。

数据对象强调数据元素的相同性质。

数据结构三要素

1. 逻辑结构
2. 物理结构
3. 数据运算

逻辑结构

1. 集合。数据元素之间没有直接的关系。
2. 线性结构。数据元素之间是一对一的关系。
3. 树形结构。数据元素之间是一对多的关系。
4. 图形结构(网状结构)。数据元素之间是多对多的关系。

存储结构

用计算机表示数据关系的逻辑关系。

1. 顺序存储。把逻辑上相邻的元素存储在物理位置也相邻的存储单元，元素之间的关系由存储单元的邻接关系体现。
2. 链式存储。逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
3. 索引存储。在存储信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项一般是关键字或地址。
4. 散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。

 顺序存储各个数据元素在物理上必须是连续的；非顺序存储各个数据元素在物理上可以是离散的。数据的存储结构会影响存储空间的分配速度。影响对数据运算的速度。

 数据运算

施加在数据上的运算包括运算的定义和实现。数据段定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

算法的特性：

有穷性、确定性(对于相同的输入具有相同的输出)、可行性、输入(零个或多个)、输出(一个或多个)。

好算法的特质：

正确性、可读性、健壮性(适当处理非法数据)、高效率与低存储需求(时间复杂度与空间复杂度)。

时间复杂度

只保留最高阶数项，只考虑阶数

顺序执行的代码只会影响常数项，可以忽略。

只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。

如果有多层嵌套循环，只需要关注最深层循环即可。

空间复杂度

递归调用注意深度

线性表

具有相同数据类型的n个数据元素的有限序列。

每个数据元素所占空间一样大；有次序。

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后驱。

基本操作：

线性表定义

静态分配

动态分配

顺序表特点：随机访问、存储密度高、拓展容量不方便、插入删除数据元素不方便。

线性表插入

线性表删除