课件内容：
绪论
目的：勾勒“数据结构与算法”课程的轮廓，说明课程目的、任务和主要内容。要求：① 理解数据结构概念，包含数据逻辑结构、数据存储结构和对数据的操作； ② 理解抽象数据类型概念，以及与数据结构的关系； ③ 熟悉算法概念和算法设计和分析方法。重点：数据结构概念；算法设计和分析方法。难点：抽象数据类型，链式存储结构，算法分析方法。实验要求：简单算法设计，回顾Java语言的基本语法和面向对象基本概念。掌握编辑、编译、运 行Java 应用程序的基本技能。
第1章 绪论（2+0学时）
1.1 数据结构的基本概念
1.2 算法
线性表
目的：① 线性表的特性、两种存储结构和实现； ② Java语言比较对象相等和大小的方法； ③ 面向对象程序设计中，类的封装、继承、多态和抽象特性。要求：① 理解线性表抽象数据类型； ② 掌握线性表采用顺序和链式存储结构封装实现的顺序表、单链表、循环双链表类； ③ 比较各种存储结构的特点、实现基本操作的算法及效率。重点：① 顺序表、单链表和循环双链表等线性表设计； ② 多种排序线性表类设计。难点：线性表的链式存储结构，使用Java语言的对象引用方式，改变结点间的链接关系。实验要求：① 掌握单链表和循环双链表的遍历、插入、删除、复制等操作算法； ② 掌握在MyEclipse等集成开发环境中程序的运行和调试技术。
第2章 线性表（8+2学时）
2.1 线性表的定义及抽象数据类型
2.2 线性表的顺序存储结构和实现（2学时）
2.3 线性表的链式存储结构和实现（3学时）
2.4 排序线性表的存储和实现（2学时）
2.5 线性表的应用：多项式的存储和运算（1学时）
实验1 线性表的基本操作（2学时）
字符串
目的：字符串（特殊线性表）的实现与应用。要求：① 以Java语言的String和StringBuffer两种字符串类为例，掌握采用顺序存储结构的常量字符串类和变量字符串类设计； ② 掌握字符串的两种模式匹配算法，即Brute-Force和KMP算法。重点：① 常量串和变量字符串类对子串的操作算法； ② 串的模式匹配算法及应用。难点：KMP模式匹配算法，next数组在KMP算法中的作用及产生过程。实验要求：① 常量串和变量字符串类对子串的操作算法； ② 串的模式匹配算法及应用。
第3章 字符串（6+2学时）
3.1 字符串抽象数据类型
3.2 字符串的顺序存储结构和实现（2学时）
3.3 字符串的模式匹配（4学时）
实验2 字符串的基本操作及模式匹配算法（2学时）
栈、队列和递归
目的：① 栈和队列的实现和应用。 ② 递归定义问题及求解的递归算法设计。要求：① 理解栈的概念，掌握栈的顺序和链式存储结构实现，使用栈求解复杂应用问题； ② 理解队列的概念，掌握队列的顺序和链式存储结构实现，使用队列求解复杂应用问题；熟悉优先队列； ③ 理解递归定义，掌握递归算法设计。重点：① 采用Java接口形式声明栈和队列ADT，实现栈和队列；使用栈或队列求解复杂应用问题； ② 递归算法设计。难点：① 使用栈或队列求解复杂应用问题；② 递归算法设计。实验要求：① 栈和队列设计，使用栈或队列求解复杂应用问题；② 递归算法设计。
第4章 栈、队列和递归（6+2学时）
4.1 栈（2学时）
4.2 队列（2学时）
4.3 递归（2学时）
实验3 栈和队列以及递归算法（2学时）
数组和广义表
目的：扩展线性表，介绍两种包含子结构的线性结构：数组和广义表。要求：① 理解多维数组的存储结构，掌握动态二维数组的使用方法； ② 实现两种存储结构的矩阵类及矩阵运算，为第7章图的存储结构做准备； ③ 以特殊矩阵（包括稀疏矩阵）为例，研究数据压缩存储方法； ④ 理解广义表概念，熟悉广义表的存储结构和实现。重点：稀疏矩阵采用行的单链表压缩存储，有效组合了顺序和链式存储结构。难点：① 采用行的单链表存储的稀疏矩阵及运算； ② 广义表的存储结构和实现，递归定义及递归算法设计。实验要求：采用行的单链表存储的稀疏矩阵及运算。
第5章 数组和广义表（2学时）
5.1 数组
5.2 特殊矩阵的压缩存储
5.3 广义表
二叉树和树
本章是“数据结构与算法”课程的重点一章，研究树结构及其应用，也是课程的难点所在。目的：① 两种树结构：二叉树和树。 ② 二叉树应用：Huffman树和表达式二叉树。要求：① 理解二叉树的递归定义、性质和存储结构，掌握二叉链表存储的二叉树类设计，理解和掌握递归算法设计。 ② 理解树的递归定义，掌握父母孩子兄弟存储的树类设计。 ③ 熟悉Huffman树和表达式二叉树等二叉树应用。重点：二叉树和树的递归定义、链式存储结构和实现，递归算法。难点：二叉树和树的递归定义，链式存储结构，递归算法，使用栈和队列设计。实验要求：二叉树和树的递归定义、链式存储结构和实现，递归算法。
第6章 二叉树和树（8+4学时）
6.1 二叉树（4学时）
6.2 树（2学时）
6.3 二叉树应用（2学时）
实验4 二叉树的基本操作（2学时）
实验5 树的基本操作（2学时）
图
本章是“数据结构与算法”课程的重点内容，也是课程的难点所在。目的：研究图的存储结构，图的遍历算法，图的最小生成树和最短路径问题。要求：① 理解图的定义和概念。 ② 掌握图的邻接矩阵和邻接表存储结构的基本操作算法，使用第5章实现的两种矩阵来存储图的边集合。 ③ 掌握图的深度优先遍历和广度优先遍历算法。 ④ 掌握构造最小生成树的Prim算法，了解Kruskal算法。 ⑤ 掌握求单源最短路径的Dijkstra算法，了解求每对顶点间最短路径的Floyd算法。重点：图的存储结构，深度和广度优先遍历，最小生成树，单源最短路径。难点：① 图的深度优先遍历，递归算法。 ② Prim算法，Dijkstra算法，贪心选择策略。实验要求：图的存储结构，深度和广度优先遍历，最小生成树，单源最短路径。
第7章 图（8+2学时）
7.1 图的概念和抽象数据类型
7.2 图的存储结构和实现（2学时）
7.3 图的遍历（2学时）
7.4 最小生成树（2学时）
7.5 最短路径（2学时）
实验6 图的存储结构和操作算法（2学时）
查找
目的：① 根据应用需求，设计支持快速查找的数据结构和查找算法，解决实际应用。 ② 以“Java集合框架”为参照，实现多种不同特性的集合（例1.1）以及映射。要求：① 理解查找概念，掌握提高查找效率的方法，掌握查找算法的效率分析。 ② 掌握二分法查找算法。 ③ 熟悉索引机制和分块查找算法。 ④ 掌握散列表存储集合。 ⑤ 掌握二叉排序树存储排序集合；了解平衡二叉树。 ⑥ 熟悉映射。重点和实验：二分法查找；索引；散列表；二叉排序树；映射。难点：散列表；二叉排序树；映射。
第8章 查找（6+2学时）
8.1 查找基础
8.2 索引（2学时）
8.3 散列（2学时）
8.4 二叉排序树和平衡二叉树（2学时）
8.5 映射
实验7 查找算法设计（2学时）
排序
目的：① 在线性表顺序存储结构背景下的排序操作，研究4种思路7种排序算法，理解“算法”含义。二叉树的排序见8.4.1节。 ② 将排序算法应用到线性表的链式存储结构。 ③ 通过学习多种排序算法，体会对同一种排序操作有多种不同的算法设计；通过比较各排序算法对于数据存储结构的要求，体会算法设计不依赖于数据存储结构，而算法实现依赖于数据存储结构；通过分析排序算法的效率，研究如何进一步提高算法性能的方法。要求：① 理解插入排序、交换排序、选择排序和归并排序的算法设计思路和算法实现手段，掌握排序算法时间复杂度和空间复杂度的分析方法，具备设计排序算法的能力。 ② 每种算法都有特点和巧妙之处，我们可以从中学到一些程序设计思想和技巧。重点难点和实验：① 希尔排序，快速排序，堆排序，归并排序。 ② 线性表链式存储结构的排序算法。
第9章 排序（6+2学时）
9.1 插入排序（2学时）
9.2 交换排序
9.3 选择排序（2学时）
9.4 归并排序（2学时）
9.5 线性表的排序算法
实验8 排序算法设计（2学时）
综合应用设计
教学目标：① 介绍Java集合框架，为解决实际问题提供技术基础，培养应用软件设计能力。 ② 实现Java集合框架的迭代器功能，数据结构课程一直在培养集合框架的设计能力，培养系统软件设计能力。 ③ 研究算法设计策略，为解决实际问题提供指导思想，培养软件设计能力。 ④ 给出课程设计实践环节的任务、要求和选题，系统地进行程序设计的实战训练， 将基础理论知识应用于解决实际问题，在实战中巩固所学理论知识、积累程序设计经验、提高算法分析能力与设计能力。内容要求：① Java集合框架的列表和集合接口，以及实现列表和集合接口的类。 ② 实现顺序表和单链表的迭代器；使用迭代器实现通用功能。 ③ 研究算法设计策略，包括分治法、动态规划法、贪心法和回溯法等，给出多个解决问题示例，说明建立数据结构、算法分析与设计等综合应用设计过程。
第10章 综合应用设计（4学时）
10.1 Java集合框架（2学时）
10.2 实现迭代器
10.3 算法设计策略（2学时）
《数据结构与算法》PPT课件 南京工程学院 叶核亚
资源下载
资源下载
