数据结构复习资料 概述： 数据(数值和非数值)>数据对象（数据元素的集合，数据的子集）>数据元素（数据基本单位也称节 点或记录）≧数据项（数据基本单位） 数据类型(data type)：是指程序设计语言中允许的变量类型。 物理结构(存储结构)：数据的物理结构是逻辑结构在计算机中的映象，也就是具体实现。 逻辑结构(数据结构)：同一数据对象中数据元素的关系，数据结构分线性和非线性两种。数据结构 的选择对数据处理的效率起着至关重要的作用。 算法：算法是解决某一特定类型问题的有限运算序列。特征：有穷性、确定性、可执行性，且须有 0个或多个输入，一个或多个输出。要求：正确性、可读性、健壮性，效率与低储存需求。 算法分析：通常用计算机执行时在时间（时间复杂度）和空间（空间复杂度）两方面的消耗多少作 为评价该算法优劣的标准，一般时间复杂度考虑的较多。 时间复杂度: 方法分为事后统计和事前分析估算。频度：指一条语句重复执行的次数，记作：F(n)。 时间复杂度：T(n)=O(F(n)) 它以算法中频度最大的语句来度量的。 空间复杂度：空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间 （因为这些单元与算法无关），记作：S(n)。 线性结构（线性表、栈、队、串、数组） 逻辑结构 非线性结构（树、图） 顺序结构 链式结构 索引结构 数据结构 散列结构 插入运算 删除运算 数据运算 修改运算 查找运算 排序运算 线性表： 结构： ), . . .,,, . . .,(1121niiiaaaaaa 线 性 起 点 a[i]的直 接 前 趋 a[i]的直 接 后 继 线 性 终 点 n=0时线性表为空表 物理（储存）结构 逻辑结构唯一 储存结构不唯一 下标：是元素的 序号，表示元素 在表中的位置。 n为元素总个 数，即表长。 类型：若线性表中的数据元素相互之间可以比较，且niiiaa,...3,2,11则称该线性表为有序表，否则称为无序表。 储存结构： 地址计算：iLaaddraaddri)()(1（L为单位元素长度） 特点：这种存储结构只要知道元素的序号，就很容易找到第 i个数据元素， 且无论序号 i为何值，找到第 i个元素所需时间相同。所以，这种 存储结构亦称为随机存储结构。 运算时间：设 pi是将一个元素插入在第 i个位置的概率。 顺序储存结构 分析：无论是插入或删除一个元素，平均需要移动表中一半的元素，这表 长 n较大时是相当可观的，因此这种存储结构仅适用于不...
