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

《《数据结构(Java版)(第3版)》复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（Java版）（第3版）数据结构（Java版）（第3版）第1章绪论第2章线性表第3章串第4章栈与队列第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第1章绪论目的：勾勒数据结构课程的轮廓。内容：数据结构概念，算法设计与分析。要求：理解数据结构基本概念，理解抽象数据类型概念；熟悉算法设计和分析方法。掌握编辑、编译、运行JavaApplication程序的基本技能。重点：数据的逻辑结构和存储结构概念。难点：抽象数据类型，算法分析。1.1数据结构的基本概念什么是数据、数据元素、数据项和关键字？它们之间是怎样的关系

2、？什么是数据结构？数据结构概念包括哪三部分？数据的逻辑结构主要有哪三种？各有何特点？三者之间存在怎样的联系？数据的存储结构主要有哪些？各有何特点？《数据结构（Java版）（第3版）》数据结构概念《数据结构（Java版）（第3版）》数据结构与数据类型的概念有什么区别？为什么要将数据结构设计成抽象数据类型？线性结构主要有哪些？各有何特点？各采用什么存储结构？为什么？《数据结构（Java版）（第3版）》1.2算法什么是算法？怎样描述算法？怎样衡量算法的性能？《数据结构（Java版）（第3版）》第2章线性表目的：实现线性表抽象数据类型。

3、内容：将线性表的顺序存储结构和链式存储结构实现分别封装成顺序表类、单链表类、循环双链表类等，比较这两种实现的特点以及各种基本操作算法的效率。要求：理解线性表抽象数据类型，掌握顺序和链式存储结构实现线性表的方法。重点：顺序表、单链表、循环双链表等线性表的设计训练。难点：使用指针实现链式存储结构，通过指针操作改变结点间的链接关系。2.1线性表抽象数据类型什么是线性表？线性表主要采用哪两种存储结构？它们是如何存储数据元素的？各有什么优缺点？为什么顺序表的插入和删除操作必须移动元素？平均需要移动多少元素？线性表的链式存储结构有哪几种？它

4、们是如何存储数据元素的？各有何特点？有什么优缺点？《数据结构（Java版）（第3版）》线性表及其存储结构《数据结构（Java版）（第3版）》线性表的两种存储结构《数据结构（Java版）（第3版）》第3章串目的：串作为特殊线性表的实现与应用。内容：字符串的基本概念，串抽象数据类型，顺序和链式两种存储结构存储串的特点；采用顺序存储结构实现串的各种操作算法；两种串的模式匹配算法及应用：Brute-Force算法和KMP算法。要求：掌握顺序串类的基本操作实现方法，掌握串的模式匹配算法及应用。重点：串数据类型的各种操作实现，两种串的模式匹

5、配算法及应用。难点：KMP模式匹配算法，next数组在KMP算法中的作用及产生过程。3.1串抽象数据类型什么是串？串和线性表在概念上有何差别？串操作的主要特点有哪些？串和字符的存储结构有什么不同？串的存储结构有几种？串通常采用什么存储结构？《数据结构（Java版）（第3版）》3.3串的模式匹配什么是串的模式匹配？有哪些场合需要使用串的模式匹配？串的模式匹配主要算法有哪些，各有何特点？举例说明，并给出最好情况和最坏情况及其时间复杂度。《数据结构（Java版）（第3版）》3.3.1Brute-Force算法Brute-Force模式

6、匹配算法的主要特点是什么？算法思路是怎样的？《数据结构（Java版）（第3版）》3.3.2KMP算法KMP算法模式匹配的主要特点是什么？算法思路是怎样的？next数组有什么作用？求next数组的算法有什么特点？《数据结构（Java版）（第3版）》第4章栈与队列目的：使用栈或队列作为求解复杂应用问题的有效手段和措施。内容：栈和队列抽象数据类型及它们的实现和应用；优先队列；递归算法设计。要求：掌握栈和队列抽象数据类型，以及顺序和链式存储结构实现；理解对于怎样的应用问题，需要使用栈或队列，以及怎样使用。重点：栈和队列的设计和实现；理解

7、递归定义，设计递归算法。难点：使用栈或队列求解复杂应用问题；递归算法设计。实验：栈和队列及其应用；递归算法。4.1栈什么是栈？栈的特点是什么？在什么情况下需要使用栈？栈可以采用什么存储结构？执行插入、删除操作时需要移动数据元素吗？为什么？《数据结构（Java版）（第3版）》4.2队列什么是队列？有何特点？说明在什么情况下需要使用队列。什么是队列的假溢出？为什么顺序队列会出现假溢出？怎样解决队列的假溢出问题？链式队列会出现假溢出吗？为什么？顺序栈会出现假溢出吗？为什么？《数据结构（Java版）（第3版）》第5章数组和广义表目的：线

8、性结构到非线性结构的过渡，了解包含子结构的线性结构，理解链式存储结构在表达非线性数据结构中的作用。内容：使用二维数组表示矩阵及运算；三角矩阵、对称矩阵、稀疏矩阵等各种压缩存储方法实现矩阵运算；广义表的概念、双链表示和实现。要求：理解多维数组的存储结构；熟悉特殊矩