数据结构教学大纲.doc

《数据结构》教学大纲
第一部分大纲说明
一、本课程的性质、目的与任务
《数据结构》是信息与计算科学、信息管理与信息系统专业必修的一门主要专业基础课,通过本课程的学习，使学生能够掌握分析、研究计算机加工的数据结构的特性，为应用涉及的数据选择适当的逻辑结构、存储结构和运算算法，初步掌握对算法的评估方法，并培养学生具有较严谨、清晰的程序设计风格，掌握较复杂的程序设计的能力，为学习后续课程和专业技术工作打下基础。
二、与其它课程的联系
本课程是计算机软件、应用专业的骨干核心课程。要求先行课为：高级语言程序设计、离散数学、概率论。通过学习该课程，为以后学习编译原理、操作系统,程序设计方法学、面向对象的程序设计、数据库原理等课程打下坚实的基础。
三、课程的特点
该课程既具有较强的理论性，又具有较强的实践性.
教学中应注重抽象数据类型和具体的数据类型相结合，注重数据的逻辑结构和存储结构的对照分析，有意识地培养学生编写高质量程序的能力和风格。
教学中除采用讲授法外，可结合投影，CAI等助教学手段，同时加强实践性环节的教学。
学生学习过程中，同样应该拿抽象数据类型和具体数据类型相结对照，加强实践性环节的训练。
四、教学总体要求
该课程包括八个方面的内容：线性表（包括操作受限的线性表、和队列）、串、数组和广义表、树和二叉树、图、动态存储管理、查找和排序、文件。
掌握数据结构中三种基本结构（线性表、树和图）的概念、存储结构与分析方法。
掌握用类C语言的语法，并掌握用类C语言来描绘数据结构和算法。
通过实验课，使学生在数据结构的逻辑特性和存贮表示、基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在课程设计方法及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练，增强动手能力，掌握必要的用类C语言来实现数据结构和算法的能力。
五、本课程的学时分配表（按各章编写）
编号教学内容课堂讲
课学时习题课
学时实验
学时自学
学时1绪论22线性表423栈和队列4224串425数组和广义表426数和二叉树847图8248动态存储管理429查找和排序82210文件211本课程发展方向概要1总学时75学分5其中：理论教学55学时，实验20学时六、教材及教学参考资料
《数据结构（C语言版）》，严蔚敏、吴伟民清华大学出版社1997
《数据结构实用教程（C/C++描述），徐孝凯清华大学出版社1999
《数据结构—用C语言描述》，宁正元中国水利水电出版社2000
《实用数据结构》，徐士良清华大学出版社2000
《数据结构》，晋良颖人民邮电出版社2002
第二部分教学内容和教学要求
第一章：概论
教学内容：
什么是数据结构
基本概念
抽象数据类型的表示与实现
算法和算法分析
教学要求：
使学生了解数据和数据结构等名词和术语的基本概念，理解数据的逻辑结构和存储结构的概念，它们各自对应的性质和两种结构之间的关系；了解算法的五个要素；理解掌握计算语句的频度和时间。空间复杂度的方法。
第二章：线性表
教学内容：
线性表的类型定义
线性表的顺序表示与实现
线性表的链式表示与实现
一元多项式的表示及相加
教学要求：
(1)了解线性表的逻辑结构和特性，及其对应的两类存储结构：顺序存储结构和链式存储结构，熟练掌握线性表的两类存储结构，
(2)熟练掌握线性表在顺序存储结构上实现基本运算：查找、插入和删除的算法；
(3)熟练掌握在各种链表结构中实现线性表运算的基本方法，并学会何时选用何种链表的方法；
(4)了解从时间和空间复杂度的角度结合比较线性表两种存储结构的不同特点及其适用场合，并了解两种结构上的其它基本操作。
教学建议：
1.线性表的两种存储结构的描述及其基本操作的实现是本章的重点
2.强调线性表的链式表示与实现
3.强调两种存储结构的区别
实验要求：
线性表的应用：熟悉线性表的两种存储结构，熟练掌握线性表的基本运算在两种存储结构上的实现，其中以链表操作作为重点。
第三章：栈和队列
教学内容：
栈的抽象数据类型的定义及表示和实现
栈的应用举例
队列的抽象数据类型的定义及表示和实现
教学要求：
(1)了解栈和队列两种数据结构的概念和特点，掌握它们的应用场合；
(2)熟练掌握在顺序和链式两种存储结构上完成栈的基本运算：判断栈空、栈满、入栈、出栈、取栈顶元素等操作。特别是注意栈满和栈空的条件及它们的描述；
(3)熟练掌握循环队列和链式队列的基本操作：判断队满、队空、入队、出队操作等。特别是注意队满和队空的描述方法。理解利用栈进行探索式程序设计和递归算法到非递归算法的转化。
教学建议：
栈和队列对应的两种存储结构的描述及其基本操作的实现是本章的重点。
利用栈进行探索式程序设计和递归算法到非递归算法的转化，有关时间和空间复杂度的分析、比较是本章的难点。
实验内容