导学及重点难点分析.doc

数据结构导学及重点难点分析课程名称：数据结构（Data Structures） 教学对象：有一定计算机基础的大学生先修课程：计算机原理与应用、C+程序设计基础参考教材：(1) 胡圣荣，周霭如等，数据结构教程与题解，北京大学出版社，2006.2。(2) 殷人昆、陶永雷、谢若阳、盛绚华，数据结构用面向对象方法与C+描述，清华大学出版， 2005。(3) 殷人昆、徐孝凯，数据结构习题解析，清华大学出版， 2006。(4) 严蔚敏等，数据结构（C语言版），北京:清华大学出版社，2002.9。(5) 汪诗林译，数据结构算法与应用（C+语言描述），机械工业出版社，2000.1。课程简介：数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。该课程的目的是帮助学生了解各种数据在计算机中的组织、存储和处理的方法，掌握数据结构和算法设计与分析的基本知识，各种基本数据结构的定义，存储结构、相应的算法以及应用，理解基本的数据结构与算法的关系，通过设计有效的数据结构和算法来建立合理的软件体系结构和程序结构。 该课程采用面向对象的方法讨论数据结构，以抽象数据类型和软件复用的观点介绍在面向对象程序设计过程中各种数据结构的表达和实现。内容包括数组、链表、顺序表、稀疏矩阵、栈、队列、递归、广义表、散列、集合、树、图以及查找、索引、排序等程序设计技巧。课程以C+语言为表述手段。课程的教学目标 一 序论 1数据结构课程介绍及相关的概念、名词和术语2数据类型、抽象数据类型ADT、数据的逻辑结构与存储结构、算法的基本概念3算法分析、算法的性能分析与度量、时间复杂度和空间复杂度、复杂度的表示 二 数组 1数组的定义及抽象数据类型、顺序表的定义和特点、顺序表的查找、插入和删除2稀疏矩阵的抽象数据类型、稀疏矩阵的压缩表示、字符串抽象数据类型和类定义、字符串操作的实现三 链表 1单链表的结构和ADT、单链表中的插入与删除、静态链表2循环链表的类定义、双向链表、稀疏矩阵四 栈和队列 1栈的定义和ADT、存贮表示及算法、顺序栈和链式栈、栈的应用示例（表达式求值）2队列的定义和ADT、循环队列和链式队列、队列的应用举例（二项式）、优先级队列五 递归 1递归的概念、递归过程与递归工作栈、递归应用举例（迷宫问题）2广义表的概念、广义表的表示及操作、广义表的存储结构与访问算法六 树与森林1树和森林的概念、术语和ADT，二叉树的定义、性质和表示；2二叉树的中序、前序和后序遍历，二叉树遍历的应用3堆的定义、建立和操作4树和森林的存贮表示、转化方法和遍历，树的应用（Huffman树）七 集合与搜索 1集合的基本概念和ADT，等价类和并查集2搜索的概念；静态搜索结构；顺序搜索；3二叉搜索树；二叉搜索树的插入和删除4AVL树；AVL树的插入和删除；AVL树的高度；八 图 1图的基本概念、术语和ADT；图的存贮表示（邻接矩阵、邻接表、邻接多重表）2图的遍历与连通性；深度优先搜索和广度优先搜索；最小生成树3最短路径；活动网络；九 排序 1排序的概念；低级排序方法（插入排序 、冒泡排序 、选择排序）2高级排序方法（快速排序）十