厦门大学：《数据结构》课程教学课件（PPT讲稿）数据结构期末复习

数据猪构期末复习

数据结构期末复习

教学任务 针对大量的信息处理对象，介绍对象信息与数据表 示的各种抽象的、基本的逻辑结构及其上的基本运 算操作。” 通过研究各种基本数据结构内在的逻辑关系和它们 在计算机中的存储表示方式，初步建立数据结构上 基本运算操作的正确性概念。 结合各种典型问题讨论其上的各种基本运算操作及 其基本算法，讲授各种数据结构的特点、/适用范围 以及对一些基本算法效率的定性和定量分析方法 为后续课程提供必要的数据结构基础。 配合实验课程的教学，学生应理论联系实际，理论 指导实践，通过规范地完成一系列数据结构实验进 一步巩固所学的相关书本知识，在知识、能力、素 质上得到进一步的提高。 2005.2xlxu

2005.zxl.xmu 教学任务  针对大量的信息处理对象，介绍对象信息与数据表 示的各种抽象的、基本的逻辑结构及其上的基本运 算操作。  通过研究各种基本数据结构内在的逻辑关系和它们 在计算机中的存储表示方式，初步建立数据结构上 基本运算操作的正确性概念。  结合各种典型问题讨论其上的各种基本运算操作及 其基本算法，讲授各种数据结构的特点、适用范围， 以及对一些基本算法效率的定性和定量分析方法， 为后续课程提供必要的数据结构基础。  配合实验课程的教学，学生应理论联系实际，理论 指导实践，通过规范地完成一系列数据结构实验进 一步巩固所学的相关书本知识，在知识、能力、素 质上得到进一步的提高

课程肉容 【重点】各种常用的数据表示抽象的逻辑结构、存储 结构及其上基本的运算操作、算法及其效率分析。 【基本要求】较好地掌握课程的主要内容，能够运用 数据结构的理论、方法与技术解决相应的、一般的 实际问题。 『说明」重点内容用白色文字标示，非重点内容用蓝色文字标 示。 2005.2xl.xu

2005.zxl.xmu 课程内容 【重点】各种常用的数据表示抽象的逻辑结构、存储 结构及其上基本的运算操作、算法及其效率分析。 【基本要求】较好地掌握课程的主要内容，能够运用 数据结构的理论、方法与技术解决相应的、一般的 实际问题。 『说明』重点内容用白色文字标示，非重点内容用蓝色文字标 示

第1章绪论 数据结构的概念；数据的逻辑结构；数据的存储结 构； 线性结构与非线性结构； 四种基本的存储映像方法：顺序、链接、索引、散 列； 数据的基本运算：检索、插入、删除、更新和排序 可支撑算法运行的计算模型 算法及其特性；算法的描述形式；数据结构的选择 和评价标准； 面向对象表示法 2005.2xlxm

2005.zxl.xmu 第1章 绪论  数据结构的概念；数据的逻辑结构；数据的存储结 构；  线性结构与非线性结构；  四种基本的存储映像方法：顺序、链接、索引、散 列；  数据的基本运算：检索、插入、删除、更新和排序；  可支撑算法运行的计算模型；  算法及其特性；算法的描述形式；数据结构的选择 和评价标准；  面向对象表示法

第2章线性表 向量及其运算；（顺序表的存储结构及其基本运算 ·在顺序表中实现插入、删除算法的思想； 求T的方法；等概率情形不，在顺序表中插入、删除算 法平均约需移动多少结点？ 单链表的存储结构及其基本运算； ·链表的特点是怎样的？（静态vs.动态） ·开始结点、头结点头指针、空表等概念 在链表中引入头结点有什么好处？ 单链表的插入、删除、查找算法的思想（前插入、后插 入、前删、后删、按值查找) 2005.2xL.xu

2005.zxl.xmu 第2章 线性表  向量及其运算；（顺序表的存储结构及其基本运算）  在顺序表中实现插入、删除算法的思想；  求T(n)的方法；等概率情形下，在顺序表中插入、删除算 法平均约需移动多少结点？  单链表的存储结构及其基本运算；  链表的特点是怎样的？（静态 vs. 动态）  开始结点、头结点、头指针、空表等概念  在链表中引入头结点有什么好处？  单链表的插入、删除、查找算法的思想（前插入、后插 入、前删、后删、按值查找）

第2章线性表(2) 循环表及其基本运算； 。头指针s.尾指针 双链表及其基本运算； ·双链表的的插入、删除、查找算法的思想（前插入、后 插入、前删、后删、按值查找 。与单链表相比较，有何特点？ 对称表及其基本运算（一般了解） 2005.2xlxu

2005.zxl.xmu 第2章 线性表（2）  循环表及其基本运算；  头指针 vs. 尾指针  双链表及其基本运算；  双链表的的插入、删除、查找算法的思想（前插入、后 插入、前删、后删、按值查找）  与单链表相比较，有何特点？  对称表及其基本运算（一般了解）；

第3章栈和队列 栈及其运算 ·栈（顺序，链栈）、栈顶、栈底空栈 栈的基本运算（主要考虑顺序栈）：进栈、退栈、空栈 取栈顶元素。 。什么是栈满？栈的上溢和下溢 栈的应用； 栈与递归的关系：递归的概念、利用栈实现递归过 程到非递归过程的转换； 2005.zxl.xmu

2005.zxl.xmu 第3章 栈和队列  栈及其运算；  栈（顺序，链栈）、栈顶、栈底、空栈  栈的基本运算（主要考虑顺序栈）：进栈、退栈、空栈、 取栈顶元素。  什么是栈满？栈的上溢和下溢。  栈的应用；  栈与递归的关系：递归的概念、利用栈实现递归过 程到非递归过程的转换；

第3章找和队列 (2) 队列及其基本运算； 。 队列、队尾、队首、空队列 。入队、出队、取队头、判队列空的运算描述 ·什么是队列的上溢（假上溢）、下溢？克服假上溢有什 么方法？ 何为循环队列？循环意义下队满、队空的条件是怎样的？ 循环队列的入队、出队算法。 其它限制存取点的表：双端队列、双栈、超队列 超栈； 栈和队列的链接存储表示及其基本运算， 何为链队列？ 2005.2xl.xu

2005.zxl.xmu 第3章 栈和队列（2）  队列及其基本运算；  队列、队尾、队首、空队列  入队、出队、取队头、判队列空的运算描述。  什么是队列的上溢（假上溢）、下溢？克服假上溢有什 么方法？  何为循环队列？循环意义下队满、队空的条件是怎样的？ 循环队列的入队、出队算法。  其它限制存取点的表：双端队列、双栈、超队列、 超栈；  栈和队列的链接存储表示及其基本运算；  何为链队列？

第4章串 串的基本概念 。串的长度、空串、空格串、子串、位置、串的相等 串的存储表示：顺序存储、索引存储及链式存储； ·顺序：定长、堆分配 ·索引：（见《许》P78~79) ·链式：块链（结点大小） ·串的基本运算及其实现 ·最小操作子集；如何用最小操作子集来实现其它操作？ 模式匹配：朴素的匹配算法、，无回溯的匹配算法 (KMP算法)； ●KMP的改进* 2005.2xl.xu

2005.zxl.xmu 第4章 串  串的基本概念；  串的长度、空串、空格串、子串、位置、串的相等  串的存储表示：顺序存储、索引存储及链式存储；  顺序：定长、堆分配  索引： （见《许》 P78～79）  链式：块链（结点大小）  串的基本运算及其实现；  最小操作子集；如何用最小操作子集来实现其它操作？  模式匹配：朴素的匹配算法、无回溯的匹配算法 （KMP算法）；  KMP的改进*

第5章数组和广义表 多维数组：多维数组的行优先和列优先顺序序列； 。多维数组的存储位置计算公式 稀疏矩阵：稀疏矩阵的顺序存储、链式存储和散列 存储；稀疏矩阵的乘法（一般了解）： ·特殊矩阵的压缩存储 广义表：广义表、再入表（共享）、递归表（递归） 的概念； 广义表的存储：广义表的单链表示法、广义表的双 链表示法； 2005.2xlxu

2005.zxl.xmu 第5章 数组和广义表  多维数组：多维数组的行优先和列优先顺序序列；  多维数组的存储位置计算公式  稀疏矩阵：稀疏矩阵的顺序存储、链式存储和散列 存储；稀疏矩阵的乘法（一般了解）；  特殊矩阵的压缩存储  广义表：广义表、再入表（共享）、递归表（递归） 的概念；  广义表的存储：广义表的单链表示法、广义表的双 链表示法；