导学及重点难点分析.doc

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