(据结构教学大纲南京大学.docVIP

《数据结构》课程教学大纲 课程代码 课程类型 成教必修课 学 分 3 学分学时1．培养学生综合分析能力，以便能够合理有效地表示和处理数据，提高程序设计的质量。学生能够掌握常用的数据结构抽象数据类型、各种基本存储方法以及主要的算法，例如（线性结构、二叉树、树、图等）。 学生能够掌握并应用常用的排序、检索技术。 培养学生分析问题和解决问题的能力，根据所求解问题的性质选择合理的数据结构使学生能够掌握基本的算法设计和分析技术，并能对自己设计的数据结构和算法进行简单的分析并对时间空间复杂性进行必要的控制。 栈和队列 算术表达式、应用后缀表示计算表达式的值、中缀表达式转换为后缀表达式 1、教学基本要求 （1）理解多维数组、稀疏矩阵、字符串、广义表的概念及基本操作。 （2）了解稀疏矩阵的转置算法与广义表的存储实现。 2、教学内容 （1）多维数组、稀疏矩阵、字符串、广义表的概念。 （2）稀疏矩阵的转置算法、字符串的实现。 （3）广义表的head和tail操作 第五章 树树和森林的概念树和森林的概念（3）前序（中序、后序）遍历树（森林）与二叉树的转换建立（Filterdown调整算法）、插入（FilterUp调整算法）、删除堆顶元素图 图的基本概念图的存储表示图的遍历图的图的基本概念图的存储表示图的遍历图的Kruskal、PrimDijkstra算法排序 的基本概念稳定性、算法分析插入排序排序 （3）直接插入排序、 折半插入排序、S排序冒泡排序、快速排序直接选择、 锦标赛、堆排序2-路归并算法 三、学时分配 序号 学 教 时 学 环 节 内 容 讲课 （面授） 自学 （作业） 实习 实验 小计 第一章 前言、基本概念及算法分析 顺序表的基本概念、主要操作（查找、插入、删除）、链表的基本概念、主要操作（查找、插入、删除），双向链表、链表的应用 栈的基本概念和操作（POP、PUSH）、顺序栈、链式栈、应用后缀表示计算表达式的值、中缀表达式转换为后缀表达式，栈与递归，队列的基本概念和操作（出队、入队）、循环队列、链式队列、优先级队列、稀疏矩阵的正交链表表示 数组的基本概念和操作、串的的基本概念和操作、广义表的基本概念和存储实现 树的基本概念、二叉树的定义及性质、二叉树的表示、二叉树的遍历、线索化二叉树的基本概念、树的表示、树（森林）与二叉树的转换、树的遍历图的基本概念和存储表示、图的遍历（深度优先、广度优先）、最小生成树（Kruscal和Prim算法）、最短路径（Dijstra算法）排序的基本概念、插入排序（直接插入排序、折半插入排序、shell排序）、交换排序（冒泡排序、快速排序）、布置课堂讨论内容（有关排序的问题，同学们课后准备）、选择排序、归并排序、简单介绍基数排序、安排学生讨论排序算法 教材：殷人昆，《数据结构——用面向对象方法与C++描述》，清华大学出版社，． 许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7 月张铭、赵海燕、王腾蛟，《数据结构与算法——学习指导与习题解析》，高等教育出版社，2005 年9 月 张铭、刘晓丹译, 《数据结构与算法分析——C++第二版》，电子工业出版社，2002 年6 月