1、数据结构学位考数据结构学位考复习课复习课 (1)主要内容：主要内容：1.第一部分第一部分 概述概述2.第二部分第二部分 线性表、栈、队列线性表、栈、队列第一部分：第一部分： 数据结构与算法的基本概念数据结构与算法的基本概念考核内容及要求：考核内容及要求：n 理解算法、算法正确性、复杂性的概念；理解算法、算法正确性、复杂性的概念；n 了解算法的时间与空间复杂性级别；了解算法的时间与空间复杂性级别；n 重点掌握数据类型、数据结构和表示、实现重点掌握数据类型、数据结构和表示、实现的概念；的概念；n 掌握抽象数据类型的说明、高级语言对抽象掌握抽象数据类型的说明、高级语言对抽象数据类型的支持。数据类型的
2、支持。基本概念和术语n 数据数据 (Data)：n 数据元素数据元素 (Data Element)：q 数据的基本单位，计算机中通常作为一个整体来考虑，如数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。一棵树中的一个结点、一个图中的一个结点。q 一个数据元素可以有若干个一个数据元素可以有若干个 数据项数据项 (Data Item)组成。组成。n 数据对象数据对象 (Data Object)： 性质相同的数据元素的集合性质相同的数据元素的集合n 数据结构：数据结构： 数据元素之间的关系数据元素之间的关系 结构结构q 四种基本结构四种基本结构n 集合集合
3、线性结构线性结构 树形结构树形结构 图状图状结构结构 /网状结构网状结构q 数据结构的形式定义：数据结构的形式定义：n 一个二元组：一个二元组：Data_Structure=(D,S)其中：其中： D是数据元素的集合，是数据元素的集合， S是是 D上的关系集上的关系集合合n 数据的逻辑、物理（存储）结构数据的逻辑、物理（存储）结构q 逻辑结构：数据元素之间的逻辑关系逻辑结构：数据元素之间的逻辑关系q 物理结构：数据元素在计算机中的存储方法物理结构：数据元素在计算机中的存储方法（表现和实现）（表现和实现） n 数据结构的分类：数据结构的分类：q 按照按照 逻辑结构逻辑结构 的不同分为：集合、线性
4、结构的不同分为：集合、线性结构、树状结构、网状结构、树状结构、网状结构q 按照按照 物理结构物理结构 的不同分为：的不同分为：n 顺序结构：利用在存储器中的物理关系来表顺序结构：利用在存储器中的物理关系来表示逻辑关系。示逻辑关系。n 链式结构：用在存储器中附加指针的方式来链式结构：用在存储器中附加指针的方式来表示逻辑关系。表示逻辑关系。n 算法：对特定问题求解步骤的一种描述，是算法：对特定问题求解步骤的一种描述，是指令的有序序列指令的有序序列n 算法的五个特性：有穷性、确定性、可行性算法的五个特性：有穷性、确定性、可行性、输入、输出、输入、输出n 算法设计的要求：时间复杂度，空间复杂度算法设计
5、的要求：时间复杂度，空间复杂度n 时间复杂度：算法执行时间随规模增长而时间复杂度：算法执行时间随规模增长而增长的趋势增长的趋势T(n)=O(f(n) f(n)算法规模，算法规模， T(n)称算法复杂度称算法复杂度估算办法：以算法中重复执行的次数作估算办法：以算法中重复执行的次数作为算法时间复杂度的依据。为算法时间复杂度的依据。 三种最常见时间复杂度：三种最常见时间复杂度：O(1) 常量级常量级 O(n) 线性级线性级O(n2) 平方级平方级n 算法的空间复杂度算法的空间复杂度S(n)=O(f(n)算法执行过程中所需的最大空间算法执行过程中所需的最大空间估算方法：输入数据所占空间估算方法：输入数
6、据所占空间 +程序所占空间程序所占空间 +辅助变量所占空间辅助变量所占空间第二部分第二部分 线性表、栈、队列线性表、栈、队列n 考核内容及要求：考核内容及要求：q 熟练掌握顺序分配、链接分配的表示及实现熟练掌握顺序分配、链接分配的表示及实现方法；方法；q 熟练掌握各种链表：单链、双链、多链、循熟练掌握各种链表：单链、双链、多链、循环链表；环链表；q 理解栈、队列、双向队列的顺序、链式表示理解栈、队列、双向队列的顺序、链式表示及其算法复杂度分析；及其算法复杂度分析；q 熟练掌握表达式计算原理。熟练掌握表达式计算原理。1. 线性表的顺序表示和实现线性表的顺序表示和实现n 线性表的存储结构：顺序存储
7、、链接存储线性表的存储结构：顺序存储、链接存储n 顺序存储：用一组地址连续的存储单元依次存储线性表顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。的数据元素。a1a2aianbb+lb+(i-1)lb+(n-1)lb+nl存储地址存储地址 存储内容存储内容顺序存储结构顺序存储结构基地址：起始位置基地址：起始位置第第 i个元素的位置个元素的位置LOC(ai)=LOC(a1)+(i-1)*ll： 每个元素占用的存储单元每个元素占用的存储单元顺序表的特点顺序表的特点（ 1）利用数据元素的存储位置表示线性表中相邻数据元素）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的之间的前后关系，即线性表的 逻辑结构于存储结构逻辑结构于存储结构 （物（物理结构）理结构） 一致一致 ；（ 2）在访问线性表时，可以利用上述给出的数学公式，快）在访问线性表时，可以利用上述给出的数学公式，快速计算任何一个数据元素的存储地址。即速计算任何一个数据元素的存储地址。即 访问每个数据访问每个数据元素所花费的时间相等元素所花费的时间相等 。（ 3）这种存取元素的方法被称为）这种存取元素的方法被称为 随机存取随机存取 法。使用这种存法。使用这种存取方法的存储结构被称为随机存储结构。取方法的存储结构被称为随机存储结构。
