数据结构-复习ppt课件

1、数据构造数据构造Java版版第第3版版数据构造数据构造Java版第版第3版版第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 串串第第4章章 栈与队列栈与队列第第5章章 数组和广义表数组和广义表第第6章章 树和二叉树树和二叉树第第7章章 图图第第8章章 查找查找第第9章章 排序排序数据结构 （Java版）（第3版） 第第1章章 绪论绪论 目的：勾勒数据构造课程的轮廓。目的：勾勒数据构造课程的轮廓。 内容：数据构造概念，算法设计与分析。内容：数据构造概念，算法设计与分析。 要求：了解数据构造根本概念，了解笼统数据要求：了解数据构造根本概念，了解笼统数据 类型概念；熟习算法设计和分析方法。类

2、型概念；熟习算法设计和分析方法。掌掌 握编辑、编译、运转握编辑、编译、运转Java Application程程 序的根本技艺。序的根本技艺。 重点：数据的逻辑构造和存储构造概念。重点：数据的逻辑构造和存储构造概念。 难点：笼统数据类型，算法分析。难点：笼统数据类型，算法分析。1.1 数据构造的根本概念数据构造的根本概念1. 什么是数据、数据元素、数据项和关键字？它们什么是数据、数据元素、数据项和关键字？它们之间是怎样的关系？之间是怎样的关系？2. 什么是数据构造？数据构造概念包括哪三部分？什么是数据构造？数据构造概念包括哪三部分？3. 数据的逻辑构造主要有哪三种？各有何特点？三数据的逻辑构造主

3、要有哪三种？各有何特点？三者之间存在怎样的联络？者之间存在怎样的联络？ 4. 数据的存储构造主要有哪些？各有何特点？数据的存储构造主要有哪些？各有何特点？数据构造概念数据构造概念 1. 数据构造与数据类型的概念有什么区别？数据构造与数据类型的概念有什么区别？为什么要将数据构造设计成笼统数据类型？为什么要将数据构造设计成笼统数据类型？2. 线性构造主要有哪些？各有何特点？各采线性构造主要有哪些？各有何特点？各采用什么存储构造？为什么？用什么存储构造？为什么？ 1.2 算法算法l 什么是算法？怎样描画算法？怎样衡量算什么是算法？怎样描画算法？怎样衡量算法的性能？法的性能？ 数据结构 （Java版）

4、（第3版） 第第2章章 线性表线性表 目的：实现线性表笼统数据类型。目的：实现线性表笼统数据类型。 内容：将线性表的顺序存储构造和链式存储构造内容：将线性表的顺序存储构造和链式存储构造 实现分别封装成顺序表类、单链表类、循环实现分别封装成顺序表类、单链表类、循环 双链表类等，比较这两种实现的特点以及各双链表类等，比较这两种实现的特点以及各 种根本操作算法的效率。种根本操作算法的效率。 要求：了解线性表笼统数据类型，掌握顺序和链式要求：了解线性表笼统数据类型，掌握顺序和链式 存储构造实现线性表的方法。存储构造实现线性表的方法。 重点：顺序表、单链表、循环双链表等线性表的设重点：顺序表、单链表、循

5、环双链表等线性表的设 计训练。计训练。 难点：运用指针实现链式存储构造，经过指针操作难点：运用指针实现链式存储构造，经过指针操作 改动结点间的链接关系。改动结点间的链接关系。2.1 线性表笼统数据类型线性表笼统数据类型 1. 什么是线性表？线性表主要采用哪两种存储什么是线性表？线性表主要采用哪两种存储构造？它们是如何存储数据元素的？各有什构造？它们是如何存储数据元素的？各有什么优缺陷？么优缺陷？ 2. 为什么顺序表的插入和删除操作必需挪动元为什么顺序表的插入和删除操作必需挪动元素？平均需求挪动多少元素？素？平均需求挪动多少元素？ 3. 线性表的链式存储构造有哪几种？它们是如线性表的链式存储构造

6、有哪几种？它们是如何存储数据元素的？各有何特点？有什么优何存储数据元素的？各有何特点？有什么优缺陷？缺陷？ 线性表及其存储构造线性表及其存储构造 线性表的两种存储构造线性表的两种存储构造数据结构 （Java版）（第3版） 第第3章章 串串 目的：串作为特殊线性表的实现与运用。目的：串作为特殊线性表的实现与运用。 内容：字符串的根本概念，串笼统数据类型，顺序内容：字符串的根本概念，串笼统数据类型，顺序 和链式两种存储构造存储串的特点；采用顺和链式两种存储构造存储串的特点；采用顺 序存储构造实现串的各种操作算法；两种串序存储构造实现串的各种操作算法；两种串 的方式匹配算法及运用：的方式匹配算法及运

7、用：Brute-Force算法算法 和和KMP算法。算法。 要求：掌握顺序串类的根本操作实现方法，掌握串要求：掌握顺序串类的根本操作实现方法，掌握串 的方式匹配算法及运用。的方式匹配算法及运用。 重点：串数据类型的各种操作实现，两种串的方式重点：串数据类型的各种操作实现，两种串的方式 匹配算法及运用。匹配算法及运用。 难点：难点：KMP方式匹配算法，方式匹配算法，next数组在数组在KMP算法中算法中 的作用及产生过程。的作用及产生过程。3.1 串笼统数据类型串笼统数据类型 1. 什么是串？串和线性表在概念上有何差别？什么是串？串和线性表在概念上有何差别？串操作的主要特点有哪些？串操作的主要特

8、点有哪些？2. 串和字符的存储构造有什么不同？串的存储串和字符的存储构造有什么不同？串的存储构造有几种？串通常采用什么存储构造？构造有几种？串通常采用什么存储构造？3.3 串的方式匹配串的方式匹配 1. 什么是串的方式匹配？有哪些场所需求运什么是串的方式匹配？有哪些场所需求运用串的方式匹配？串的方式匹配主要算法用串的方式匹配？串的方式匹配主要算法有哪些，各有何特点？举例阐明，并给出有哪些，各有何特点？举例阐明，并给出最好情况和最坏情况及其时间复杂度。最好情况和最坏情况及其时间复杂度。 3.3.1 Brute-Force算法算法 1. Brute-Force方式匹配算法的主要特点是方式匹配算法的

9、主要特点是什么？算法思绪是怎样的？什么？算法思绪是怎样的？ 3.3.2 KMP算法算法 1. KMP算法方式匹配的主要特点是什么？算算法方式匹配的主要特点是什么？算法思绪是怎样的？法思绪是怎样的？next数组有什么作用？数组有什么作用？求求next数组的算法有什么特点？数组的算法有什么特点？数据结构 （Java版）（第3版） 第第4章章 栈与队列栈与队列 目的：运用栈或队列作为求解复杂运用问题的目的：运用栈或队列作为求解复杂运用问题的 有效手段和措施。有效手段和措施。 内容：栈和队列笼统数据类型及它们的实现和应内容：栈和队列笼统数据类型及它们的实现和应 用；优先队列；递归算法设计。用；优先队列

10、；递归算法设计。 要求：掌握栈和队列笼统数据类型，以及顺序和要求：掌握栈和队列笼统数据类型，以及顺序和链式存储构造实现；了解对于怎样的运用问题，链式存储构造实现；了解对于怎样的运用问题，需求运用栈或队列，以及怎样运用。需求运用栈或队列，以及怎样运用。 重点：栈和队列的设计和实现；了解递归定义，重点：栈和队列的设计和实现；了解递归定义， 设计递归算法。设计递归算法。 难点：运用栈或队列求解复杂运用问题；递归算难点：运用栈或队列求解复杂运用问题；递归算 法设计。法设计。 实验：栈和队列及其运用；递归算法。实验：栈和队列及其运用；递归算法。4.1 栈栈 1. 什么是栈？栈的特点是什么？在什么情况下什

11、么是栈？栈的特点是什么？在什么情况下需求运用栈？需求运用栈？2. 栈可以采用什么存储构造？执行插入、删除栈可以采用什么存储构造？执行插入、删除操作时需求挪动数据元素吗？为什么？操作时需求挪动数据元素吗？为什么？4.2 队列队列 1. 什么是队列？有何特点？阐明在什么情况什么是队列？有何特点？阐明在什么情况下需求运用队列。下需求运用队列。2. 什么是队列的假溢出？为什么顺序队列会什么是队列的假溢出？为什么顺序队列会出现假溢出？怎样处理队列的假溢出问题？出现假溢出？怎样处理队列的假溢出问题？3. 链式队列会出现假溢出吗？为什么？链式队列会出现假溢出吗？为什么？4. 顺序栈会出现假溢出吗？为什么？顺

12、序栈会出现假溢出吗？为什么？数据结构 （Java版）（第3版） 第第5章章 数组和广义表数组和广义表 目的：线性构造到非线性构造的过渡，了解包含子构造目的：线性构造到非线性构造的过渡，了解包含子构造的线性构造，了解链式存储构造在表达非线性数据结的线性构造，了解链式存储构造在表达非线性数据结构中的作用。构中的作用。 内容：运用二维数组表示矩阵及运算；三角矩阵、对称矩内容：运用二维数组表示矩阵及运算；三角矩阵、对称矩阵、稀疏矩阵等各种紧缩存储方法实现矩阵运算；广阵、稀疏矩阵等各种紧缩存储方法实现矩阵运算；广义表的概念、双链表示和实现。义表的概念、双链表示和实现。 要求：了解多维数组的存储构造；熟习

13、特殊矩阵的紧缩存要求：了解多维数组的存储构造；熟习特殊矩阵的紧缩存储方法；掌握稀疏矩阵三元组从顺序表、行的单链表储方法；掌握稀疏矩阵三元组从顺序表、行的单链表到十字链表等到多种存储构造的演化过程；了解广义到十字链表等到多种存储构造的演化过程；了解广义表的概念，熟习广义表的存储构造。表的概念，熟习广义表的存储构造。 重点：讨论多种由顺序存储构造和链式存储构造有机结合重点：讨论多种由顺序存储构造和链式存储构造有机结合的存储构造，以矩阵为例，研讨在一样的逻辑构造的存储构造，以矩阵为例，研讨在一样的逻辑构造 矩阵矩阵和操作要求矩阵运算情况下，根据各种和操作要求矩阵运算情况下，根据各种 矩阵的不同特矩阵

14、的不同特性，采用多种存储构造实现矩阵运算。性，采用多种存储构造实现矩阵运算。 难点：稀疏矩阵的多种存储和实现，广义表的存储和难点：稀疏矩阵的多种存储和实现，广义表的存储和 实现。实现。 实验：特殊矩阵和广义表的存储和运算。实验：特殊矩阵和广义表的存储和运算。5.1 数组数组 n 数组有什么特点？数组有什么特点？“数据构造课程中为什数据构造课程中为什么要研讨数组？么要研讨数组？n 什么是随机存储构造？分别阐明一维数组什么是随机存储构造？分别阐明一维数组和二维数组都是随机存取构造。和二维数组都是随机存取构造。5.2 特殊矩阵的紧缩存储特殊矩阵的紧缩存储 1. 采用二维数组存储矩阵能否具有随机存取特

15、采用二维数组存储矩阵能否具有随机存取特性？有哪些矩阵需求紧缩存储？为什么要紧性？有哪些矩阵需求紧缩存储？为什么要紧缩？各采用怎样的紧缩存储方式？各种紧缩缩？各采用怎样的紧缩存储方式？各种紧缩存储方式能否具有随机存取特性？存储方式能否具有随机存取特性？2. 有哪些特殊矩阵？特殊矩阵紧缩存储的根本有哪些特殊矩阵？特殊矩阵紧缩存储的根本思想是什么？思想是什么？矩阵的存储构造矩阵的存储构造 数据结构 （Java版）（第3版） 第第6章章 树和二叉树树和二叉树 目的：了解树型构造；掌握链式存储构造表达目的：了解树型构造；掌握链式存储构造表达 非线性构造，掌握递归算法设计。非线性构造，掌握递归算法设计。

16、内容：二叉树的定义、性质、存储构造，二叉链内容：二叉树的定义、性质、存储构造，二叉链表表示的二叉树类；中序线索二叉树；表表示的二叉树类；中序线索二叉树；Huffman树；树的定义、存储构造和实现。树；树的定义、存储构造和实现。 要求：了解树和二叉树概念，掌握树和二叉树的要求：了解树和二叉树概念，掌握树和二叉树的表示和实现，掌握递归算法设计。表示和实现，掌握递归算法设计。 重点：二叉链表表示的二叉树类；重点：二叉链表表示的二叉树类；Huffman树；树；树树 的定义、存储构造和构造算法。的定义、存储构造和构造算法。 难点：链式存储构造表达非线性构造；递归算法难点：链式存储构造表达非线性构造；递归

17、算法 设计。设计。 实验：树和二叉树的根本操作，链式存储结实验：树和二叉树的根本操作，链式存储结构表示树和二叉树；递归算法。构表示树和二叉树；递归算法。6.1 树及其笼统数据类型树及其笼统数据类型 1. 什么是树？树构造与线性构造的区别是什么？什么是树？树构造与线性构造的区别是什么？树与线性表有何关联？树与线性表有何关联？2. 什么是有序树？什么是无序树？什么是有序树？什么是无序树？3. 什么是结点的度？定义结点的度有何意义？什么是结点的度？定义结点的度有何意义？什么是树的度？什么是树的度？4. 树中各结点的层次是如何定义的？结点的层树中各结点的层次是如何定义的？结点的层次有何意义？什么是树的

18、高度？次有何意义？什么是树的高度？5. 树有哪几种表示方法？各有何特点？树有哪几种表示方法？各有何特点？6.2 二叉树二叉树 1. 什么是二叉树？二叉树是不是度为什么是二叉树？二叉树是不是度为2的树？的树？二叉树是不是度为二叉树是不是度为2的有序树？为什么？的有序树？为什么？2. 什么是满二叉树？什么是完全二叉树？什么是满二叉树？什么是完全二叉树？ 树和二叉树的存储构造树和二叉树的存储构造 6.5 Huffman编码与编码与Huffman树树1. Huffman编码的特点是什么？有何作用？编码的特点是什么？有何作用？2. 设一棵设一棵Huffman树有树有n0个叶子结点，该树个叶子结点，该树共

19、有多少个结点？为什么？共有多少个结点？为什么？3. 【答】【答】2n0-1。由于。由于Huffman树没有树没有1度结度结点，而点，而n0=n2+1，所以，所以n=n0+n2=2n0-1。数据结构 （Java版）（第3版） 第第7章章 图图 目的：学习非线性的复杂数据构造目的：学习非线性的复杂数据构造图。图。 内容：图的概念、笼统数据类型、存储构造；图内容：图的概念、笼统数据类型、存储构造；图 的深度和广度优先搜索遍历；最小生成树；的深度和广度优先搜索遍历；最小生成树； 最短途径。最短途径。 要求：掌握图的存储构造和操作实现。要求：掌握图的存储构造和操作实现。 重点：图的两种存储构造，两种遍历

20、算法，最小重点：图的两种存储构造，两种遍历算法，最小 生成树，最短途径。生成树，最短途径。 难点：图的存储和操作实现，最小生成树，最短难点：图的存储和操作实现，最小生成树，最短 途径。途径。 实验：图的建立与遍历，最小代价生成实验：图的建立与遍历，最小代价生成 树，最短途径。树，最短途径。7.1 图及其笼统数据类型图及其笼统数据类型7.2 图的表示和实现图的表示和实现 1. 什么是图？与线性表和树相比，图的特点是什么是图？与线性表和树相比，图的特点是什么？对图的操作主要有哪些？什么？对图的操作主要有哪些？2. 图的存储构造有什么特点？仅用顺序表或单图的存储构造有什么特点？仅用顺序表或单链表能否

21、存储一个图？为什么？图的存储构链表能否存储一个图？为什么？图的存储构造主要有哪些？造主要有哪些？ 图的存储构造图的存储构造 7.3 图的遍历图的遍历 1. 图的深度优先搜索遍历图的深度优先搜索遍历2. 图的广度优先搜索遍历图的广度优先搜索遍历7.4 最小生成树最小生成树 1. 树是怎样的图？树是怎样的图？2. 什么是图的生成树？什么是图的生成树？3. 什么是生成树的代价？什么是生成树的代价？4. 什么是图的最小生成树？什么是图的最小生成树？ 5. Prim算法算法 6. Kruskal算法算法 数据结构 （Java版）（第3版） 第第8章章 查找查找l目的：查找算法设计。目的：查找算法设计。l内容：顺序查找、折半查找、分块查找；散内容：顺序查找、折半查找、分块查找；散 列表；二叉排序树。列表；二叉排序树。l要求：掌握查找的概念和多种查找算法设要求：掌握查找的概念和多种查找算法设 计，学习根据不同情况选择适宜的查计，学习根据不同情况选择适宜的查 找算法，掌握提高查找效率采取的各找算法，掌握提高查找效率采取的各 种方法。种方法。l重点：顺序查找、折半查找、分块查找；散重点：顺序查找、折半查找、分块查找；散 列表；二叉排序树。列表；二叉排序树。l 难