《数据结构》教学大纲.doc

安徽工业经济职业技术学院计算机网络技术专业数据结构教学大纲一、 课程的性质和任务“数据结构”课程主要研究非数值计算机操作对象以及它们之间的相互关系和运算，是计算机专业基础课程之一。它的先修课程中除了要求有一门高级程序设计语言（一般可以是PACAL或者C语言）的课程以外，还要求有一些“离散数学”课程的知识。后继课程中主要有“操作系统”、“编译原理”、“数据库系统”等。主要任务：1. 本课程讲述数据结构的基本概念、各种常见的数据结构，包括数据的逻辑结构、数据的存储结构以及在这两种结构的基础上对数据实施的基本运算三个方面。2. 通过该课程的学习，使学生能够运用数据结构课程所讨论的概念和方法，更好地进行算法描述与程序设计，掌握计算机进行数据处理的基本原理和技巧,打好专业基础。二、 教学目的和要求1. 掌握常见的数据结构的逻辑结构、存储结构以及不同存储结构之间的差异。2. 掌握各种基本运算的实现算法。3掌握简单的算法分析方法。三、 教学内容第一章 绪论一、 概述：了解本课程的特点和基本概念，明确学习方法。二、 分类：1.数据结构的基本概念2.数据的逻辑结构3.数据的存储结构4.数据的运算（算法）三、 研究方法：1.在数据结构的基本概念方面，了解数据结构在计算机科学领域中的重要地位，掌握数据、数据元素、数据对象、数据结构、逻辑结构、存储结构等基本名词术语。2.在数据的算法方面，了解算法、算法分析的概念，会用算法描述语言编写算法。第二章 线性表一、 概述：了解线性表的顺序存储和线性表的链式存储结构。二、 分类：1.线性表及其基本运算2.线性表的顺序存储结构3.线性表的链式存储结构4.循环链表及其运算5.双向链表及其运算6.链表的应用举例三、 研究方法：1.了解线性表的基本概念和线性表的基本算法。2.了解红性表顺序结构的基本概念、构造原理和优、缺点。掌握插入算法、删除算法以及算法时间复杂度分析。3.了解线性表的链式存储结构中的线性链表、循环链表、双向链表的基本概念、构造原理和特点。掌握线性链表、循环链表、双向链表的建立、插入、删除等有关算法。第三章 数 组一、 概述：了解数组、数组的存储结构。二、 分类：1.数组的概念2.数组的存储结构3.矩阵的压缩存储4.稀疏矩阵的三元组表示5.数组的应用举例三、 研究方法1.了解数组的定义和基本操作以及一维数组、二维数组的概念。2.掌握数组的顺序存储结构，特殊矩阵的压缩存储思想，对称矩阵和对角矩阵的压缩存储方法，稀疏矩阵的三元组表存储方法，一元n阶多项式的一维数组表示，数组元素的检索以及三元数组表表示的稀疏矩阵的转置算法。 第四章 堆栈和队列一、 概述：了解堆栈、队列的存储结构和算法。二、 分类：1.堆栈的概念及其运算2.堆栈的顺序存储结构3.堆栈的链式存储结构4.堆栈的应用举例5.队列的概念及其运算6.队列的顺序存储结构7.队列的链式存储结构三、 研究方法：1.了解堆栈的基本概念和特征以及堆栈的顺序存储结构和链式存储结构的构造原理。2.掌握堆栈中顺序存储结构和链式存储结构的常见算法：插入算法、删除算法。3.了解队列的基本概念和特征以及队列的顺序存储结构、循环队列、队列的链式存储结构的构造原理。4.掌握队列中顺序存储结构、循环队列、队列的链式存储结构的常见算法：插入算法、删除算法。第五章 树与二叉树一、 概述：了解树、二叉树的存储结构和算法。二、 分类：1.树的基本概念2.树的存储结构3.二叉树4.二叉树的存储结构5.树的遍历6.线索二叉树7.二叉排序树8.哈夫曼树及其运用三、 研究方法：1.了解树的定义、基本概念和相关名词术语。了解树的有序性概念。掌握树的逻辑特征、逻辑表示方法、基本性质、存储结构。2.了解二叉树的定义以及满二叉树、完全二叉树、二叉排序树的基本概念。掌握二叉树的基本性质，二叉树的遍历、线索二叉树的构造原理。掌握二叉树的前序遍历、中序遍历、后序遍历以及按层次遍历等算法，利用线索二叉树进行遍历算法（如中序线索二叉树），查找算法。第六章 图一、 概述：了解图、图的存储方法、图的应用于问题。二、 分类：1.图的基本概念2.图的存储方法3.图的遍历4.最小生成树5.最短路径问题6. AOV网与拓扑问题三、 研究方法：1.了解图的定义、图的分类、图的基本概念和基本术语、图的基本操作。掌握图的存储方法、图的邻接矩阵存储方法与邻接表（包括逆邻接表）存储方法的构造原理和特点、图的深度优先搜索算法与图的广度优先搜索算法。2.对于图的运用问题要掌握以下几种： 最小生成树的算法 最短路径算法 拓扑排序 第七章 内排序一、 概念：了解排序的基本概念及各种排序方法二、 分类：1.概述2. 2.插入排序3.选择排序4.冒泡排序5.希尔排序6.快速排序7.堆排序8.二路归排序算法的比较三、 研究方法：1.了解排序的基本概念、排序的分类。2.掌握插入排序法、选择排序法、谢尔排序法、快速排序法、堆积排序法、二路归并排序法的基本原理和特点（包括排序趟数（快速排序法除外）、排序稳定性），各种排序方法比较。四、 本教程和其它课程的关系 数据结构的研究涉及到计算机硬件的研究范围,特别是编码理论、存储装置、和存取方法，还涉及到计算机软件的范围，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题，在研究信息检索时，也必须考虑 数据的组织方式，所以数据结构是介于数学、计算机软件和计算机硬件三者之间的一门计算机科学专业的核心课程。序号章节教学内容讲授学时实践学时合计学时1第1章绪论4262第2章线性表和数组126183第3章栈和队列126184第4章树126185 第5章图126186第6章排序126187第7章查找12618合计7638114五、 教学时数分配六、 考核方法教学方法：本课程以面授和上机实践为主。考核方式：包括:理论部分与实验部分,分别计分,成绩比例:70%+30%(其中之一不及格,即为不及格)；理论部分：课堂教学,按时交作业,课程结束后闭卷考试；实验部分：能够完成课程中的实验部分。七、 教材及参考书1. 推荐教材数据结构作者：陈燕出版社：高等教育出版社版本：2003年9月第5版2. 参考书目书名作者出版社版本C语言程序设计教程徐新