数据结构知识点⼤全数据结构知识点⼤全 数据结构绪论 数据结构的基本概念 数据结构是⼀门研究⾮数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作的学科。数据元素是数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑和处理。数据结构包含三个⽅⾯的含义： 逻辑结构 物理结构：数据的逻辑结构在计算机中的表⽰，称此为物理结构，或称存储结构。 数据类型：⼀个值的集合以及定义在这个值集上的⼀组操作的总称。 抽 象 数据类型：通常由⽤户定义，⽤以表⽰应⽤问题的数据模型以及定义在该模型上的⼀组操作。 算法是描述计算机解决给定问题的操作过程，即为决解某⼀特定问题⽽由若⼲条指令组成的有穷序列。 算法的效率分析：事后统计法：收集该算法实际的执⾏时间和实际占⽤空间的统计资料。事前分析估算法：在算法运⾏之前分析该算法的时间复杂度和空间复杂度，来判断算法的效率。时间复杂度分析： 常见函数的时间复杂度按数量递增排列及增长率： 线性表线性表的类型定义 线性表是n(n>0)个相同 类型数据元素构成的有限 序列，其 中n为线性表的长度。线性表的基本操作： 线性表的顺 序表⽰和实现线性表的顺 序存储结构：⽤⼀组地 址 连 续 的存储单元依 次 存储线性表的元素。线性表的顺 序存储，也 成为向 量存储，⼜ 可 以说 是⼀维 数组存储。线性表中结点存放 的物理顺 序与 逻辑顺 序完 全⼀致 ，它叫向 量存储。线性表顺序存储结构在插⼊或删除数据元素时⽐较繁琐，但是它⽐较适合存取数据元素。 线性表的插⼊操作： 在第i个元素之前插⼊⼀个元素时，需将第n⾄第i（共n-i+1）个元素向后移 动 ⼀个位置 。 线性表的删除操作： 删除第i个元素时需将从 第i+1⾄第n（共n-i）个元素⼀次向前移 动 ⼀个位置 线性表的链 式 表⽰和实现⽤⼀组任 意 的存储单元（可能 不 连续）存储线性表的数据元素。在链 式 存储结构中，每 个存储结点不 仅 包含数据元素本⾝ 的信 息 ，还 必 须 包含每 个元素之间逻辑关系的信 息 ，即包含直 接 后继 结点的地址信息 （指针 域 ）。 逻辑顺序与物理顺序有可能 不 ⼀致； 属 顺序存取的存储结构，即存取每 个元素必 须 从 第⼀个元素开 始 遍 历 ，直 到 找 到 需要 访 问的元素，所 以所 花 时间不 ⼀定相等。 链 表的创 建 ⽅式 ： 结点类的定义： 单链 表的基本操作插⼊ ...
