《数据结构(Java版)(第3版)》复习.ppt

数据结构 Java版 第3版 数据结构 Java版 第3版 第1章绪论第2章线性表第3章串第4章栈与队列第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序 第1章绪论 目的 勾勒数据结构课程的轮廓 内容 数据结构概念 算法设计与分析 要求 理解数据结构基本概念 理解抽象数据类型概念 熟悉算法设计和分析方法 掌握编辑 编译 运行JavaApplication程序的基本技能 重点 数据的逻辑结构和存储结构概念 难点 抽象数据类型 算法分析 数据结构 Java版 第3版 1 1数据结构的基本概念 什么是数据 数据元素 数据项和关键字 它们之间是怎样的关系 什么是数据结构 数据结构概念包括哪三部分 数据的逻辑结构主要有哪三种 各有何特点 三者之间存在怎样的联系 数据的存储结构主要有哪些 各有何特点 数据结构 Java版 第3版 数据结构概念 数据结构 Java版 第3版 数据结构与数据类型的概念有什么区别 为什么要将数据结构设计成抽象数据类型 线性结构主要有哪些 各有何特点 各采用什么存储结构 为什么 数据结构 Java版 第3版 1 2算法 什么是算法 怎样描述算法 怎样衡量算法的性能 第2章线性表 目的 实现线性表抽象数据类型 内容 将线性表的顺序存储结构和链式存储结构实现分别封装成顺序表类 单链表类 循环双链表类等 比较这两种实现的特点以及各种基本操作算法的效率 要求 理解线性表抽象数据类型 掌握顺序和链式存储结构实现线性表的方法 重点 顺序表 单链表 循环双链表等线性表的设计训练 难点 使用指针实现链式存储结构 通过指针操作改变结点间的链接关系 数据结构 Java版 第3版 2 1线性表抽象数据类型 什么是线性表 线性表主要采用哪两种存储结构 它们是如何存储数据元素的 各有什么优缺点 为什么顺序表的插入和删除操作必须移动元素 平均需要移动多少元素 线性表的链式存储结构有哪几种 它们是如何存储数据元素的 各有何特点 有什么优缺点 数据结构 Java版 第3版 线性表及其存储结构 数据结构 Java版 第3版 线性表的两种存储结构 第3章串 目的 串作为特殊线性表的实现与应用 内容 字符串的基本概念 串抽象数据类型 顺序和链式两种存储结构存储串的特点 采用顺序存储结构实现串的各种操作算法 两种串的模式匹配算法及应用 Brute Force算法和KMP算法 要求 掌握顺序串类的基本操作实现方法 掌握串的模式匹配算法及应用 重点 串数据类型的各种操作实现 两种串的模式匹配算法及应用 难点 KMP模式匹配算法 next数组在KMP算法中的作用及产生过程 数据结构 Java版 第3版 3 1串抽象数据类型 什么是串 串和线性表在概念上有何差别 串操作的主要特点有哪些 串和字符的存储结构有什么不同 串的存储结构有几种 串通常采用什么存储结构 数据结构 Java版 第3版 3 3串的模式匹配 什么是串的模式匹配 有哪些场合需要使用串的模式匹配 串的模式匹配主要算法有哪些 各有何特点 举例说明 并给出最好情况和最坏情况及其时间复杂度 数据结构 Java版 第3版 3 3 1Brute Force算法 Brute Force模式匹配算法的主要特点是什么 算法思路是怎样的 数据结构 Java版 第3版 3 3 2KMP算法 KMP算法模式匹配的主要特点是什么 算法思路是怎样的 next数组有什么作用 求next数组的算法有什么特点 第4章栈与队列 目的 使用栈或队列作为求解复杂应用问题的有效手段和措施 内容 栈和队列抽象数据类型及它们的实现和应用 优先队列 递归算法设计 要求 掌握栈和队列抽象数据类型 以及顺序和链式存储结构实现 理解对于怎样的应用问题 需要使用栈或队列 以及怎样使用 重点 栈和队列的设计和实现 理解递归定义 设计递归算法 难点 使用栈或队列求解复杂应用问题 递归算法设计 实验 栈和队列及其应用 递归算法 数据结构 Java版 第3版 4 1栈 什么是栈 栈的特点是什么 在什么情况下需要使用栈 栈可以采用什么存储结构 执行插入 删除操作时需要移动数据元素吗 为什么 数据结构 Java版 第3版 4 2队列 什么是队列 有何特点 说明在什么情况下需要使用队列 什么是队列的假溢出 为什么顺序队列会出现假溢出 怎样解决队列的假溢出问题 链式队列会出现假溢出吗 为什么 顺序栈会出现假溢出吗 为什么 第5章数组和广义表 目的 线性结构到非线性结构的过渡 了解包含子结构的线性结构 理解链式存储结构在表达非线性数据结构中的作用 内容 使用二维数组表示矩阵及运算 三角矩阵 对称矩阵 稀疏矩阵等各种压缩存储方法实现矩阵运算 广义表的概念 双链表示和实现 要求 理解多维数组的存储结构 熟悉特殊矩阵的压缩存储方法 掌握稀疏矩阵三元组从顺序表 行的单链表到十字链表等到多种存储结构的演变过程 理解广义表的概念 熟悉广义表的存储结构 重点 讨论多种由顺序存储结构和链式存储结构有机结合的存储结构 以矩阵为例 研究在相同的逻辑结构 矩阵 和操作要求 矩阵运算 情况下 根据各种矩阵的不同特性 采用多种存储结构实现矩阵运算 难点 稀疏矩阵的多种存储和实现 广义表的存储和实现 实验 特殊矩阵和广义表的存储和运算 数据结构 Java版 第3版 5 1数组 数组有什么特点 数据结构 课程中为什么要研究数组 什么是随机存储结构 分别说明一维数组和二维数组都是随机存取结构 数据结构 Java版 第3版 5 2特殊矩阵的压缩存储 采用二维数组存储矩阵是否具有随机存取特性 有哪些矩阵需要压缩存储 为什么要压缩 各采用怎样的压缩存储方式 各种压缩存储方式是否具有随机存取特性 有哪些特殊矩阵 特殊矩阵压缩存储的基本思想是什么 数据结构 Java版 第3版 矩阵的存储结构 第6章树和二叉树 目的 理解树型结构 掌握链式存储结构表达非线性结构 掌握递归算法设计 内容 二叉树的定义 性质 存储结构 二叉链表表示的二叉树类 中序线索二叉树 Huffman树 树的定义 存储结构和实现 要求 理解树和二叉树概念 掌握树和二叉树的表示和实现 掌握递归算法设计 重点 二叉链表表示的二叉树类 Huffman树 树的定义 存储结构和构造算法 难点 链式存储结构表达非线性结构 递归算法设计 实验 树和二叉树的基本操作 链式存储结构表示树和二叉树 递归算法 数据结构 Java版 第3版 6 1树及其抽象数据类型 什么是树 树结构与线性结构的区别是什么 树与线性表有何关联 什么是有序树 什么是无序树 什么是结点的度 定义结点的度有何意义 什么是树的度 树中各结点的层次是如何定义的 结点的层次有何意义 什么是树的高度 树有哪几种表示方法 各有何特点 数据结构 Java版 第3版 6 2二叉树 什么是二叉树 二叉树是不是度为2的树 二叉树是不是度为2的有序树 为什么 什么是满二叉树 什么是完全二叉树 数据结构 Java版 第3版 树和二叉树的存储结构 数据结构 Java版 第3版 6 5Huffman编码与Huffman树 Huffman编码的特点是什么 有何作用 设一棵Huffman树有n0个叶子结点 该树共有多少个结点 为什么 答 2n0 1 因为Huffman树没有1度结点 而n0 n2 1 所以n n0 n2 2n0 1 第7章图 目的 学习非线性的复杂数据结构 图 内容 图的概念 抽象数据类型 存储结构 图的深度和广度优先搜索遍历 最小生成树 最短路径 要求 掌握图的存储结构和操作实现 重点 图的两种存储结构 两种遍历算法 最小生成树 最短路径 难点 图的存储和操作实现 最小生成树 最短路径 实验 图的建立与遍历 最小代价生成树 最短路径 数据结构 Java版 第3版 7 1图及其抽象数据类型7 2图的表示和实现 什么是图 与线性表和树相比 图的特点是什么 对图的操作主要有哪些 图的存储结构有什么特点 仅用顺序表或单链表能否存储一个图 为什么 图的存储结构主要有哪些 数据结构 Java版 第3版 图的存储结构 数据结构 Java版 第3版 7 3图的遍历 图的深度优先搜索遍历图的广度优先搜索遍历 数据结构 Java版 第3版 7 4最小生成树 树是怎样的图 什么是图的生成树 什么是生成树的代价 什么是图的最小生成树 Prim算法Kruskal算法 第8章查找 目的 查找算法设计 内容 顺序查找 折半查找 分块查找 散列表 二叉排序树 要求 掌握查找的概念和多种查找算法设计 学习根据不同情况选择合适的查找算法 掌握提高查找效率采取的各种方法 重点 顺序查找 折半查找 分块查找 散列表 二叉排序树 难点 散列表 二叉排序树 数据结构 Java版 第3版 查找算法与查找结构 数据结构 Java版 第3版 8 3散列 什么是散列表 其与众不同的设计思想是什么 两个关键问题是什么 好的散列函数的标准是什么 为什么说冲突是不可避免的 有哪些解决冲突的办法 第9章排序 目的 排序算法研究 对于数据逻辑结构是线性表 存储结构是顺序 操作是排序 体会各种不同算法实现 内容 介绍插入 交换 选择 归并等多种经典排序算法 讨论各种排序算法所适用的存储结构 以及比较各排序算法的性能 要求 掌握直接插入 冒泡 直接选择等排序算法及其性能 理解希尔 快速 堆 归并等排序算法的设计思想及算法实现 熟悉提高算法性能的各种手段 重点 每种排序算法设计思想 算法表达 算法分析与性能评价 难点 希尔 快速 堆 归并等排序算法 性能较高算法的共同特点 数据结构 Java版 第3版 排序算法及其适用的存储结构