数据结构教学大纲.doc

甘肃民族师范学院计算机科学与技术专业课程教学大纲 数据结构教学大纲 一、说明 (一)课程性质 《数据结构》是计算科学专业中一门重要的基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，如编译原理、操作系统、数据库、人工智能等课程打下厚实的知识基础，同时也提供了必要的技能训练。另外，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。因此，《数据结构》课程在计算机专业中具有举足轻重的作用绪论线性表栈和队列串数组与广义表树和二叉树图查找内部排序　课程教学总学时数为学时，学分，各章学时分配如下： 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组与广义表 第6章 树和二叉树 第7章 图 12 第8章 查找 第9章 内部排序 (五)教学方式 以课堂讲授为主，课堂讨论和课下自学为辅。 二、本文 第一章 绪论 教学要点: 了解数据结构的研究对象，理解数据结构有关概念的含义，掌握数据结构的分类及表示。熟悉类c语言的书写规范，理解算法的重要特性及算法设计的要求，掌握计算语句频度和估算时间复杂度的方法。 教学时数：4学时 教学内容： 1.1什么是数据结构 （1学时） 一、数值问题与非数值问题 二、《数据结构》的发展史 1.2基本概念和术语（1学时） 一、数据、数据元素、数据对象、数据结构 二、数据结构的形式定义 三、逻辑结构、存储结构 四、数据类型、抽象数据类型 1.3抽象数据类型的表示与实现（1.3、1.4共1学时） 一、类c语言 二、抽象数据类型表示与实现示例 1.4算法和算法分析 一、算法 二、算法设计的要求 三、算法效率的度量 四、算法的存储空间需求（1学时） 考核要求： 数据结构的三个方面、数据结构的四种基本存储方法、算法的五个要素及算法时间、空间复杂度的运算。 第二章 线性表 教学要点: 了解线性表逻辑结构的特征；重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用类C语言描述它们的类型定义；掌握在顺序存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及适用场合。 教学时数：12学时 教学内容： 2.1 线性表的类型定义（1学时） 一、线性表的概念 二、抽象数据类型线性表List的定义 2.2 线性表的顺序表示和实现（5学时） 一、线性表的顺序存储结构 二、顺序表的类型定义 三、顺序表的基本操作算法 四、上机实验完成顺序表的基本操作 2.3 线性表的链式表示和实现（5学时） 一、线性链表 二、循环链表 三、双向链表 四、上机实验完成单链表的基本操作 2.4 一元多项式的表示及相加（1学时） 一、抽象数据类型一元多项式的定义 二、抽象数据类型一元多项式的实现 三、一元多项式的相加 考核要求： 线性表的逻辑结构特征、常见的线性表的六种基本运算，并可以根据这些基本运算组合得到更复杂的运算单链表的特征、图形表示法单链表的各种算法实现，并能运用这些算法解决一些简单问题循环链表的特征双链表的特征以及它们的主要算法实现 第三章 栈和队列 教学要点: 理解掌握栈与队列的结构特征和操作特点；掌握栈与队列的顺序存储结构和链式存储结构，以及如何用C语言描述它们的类型定义；掌握在两种存储结构下，栈与队列的基本操作的算法。理解栈的后进先出的特点及在程序设计中的应用。掌握循环队列的入队、出队算法以及循环队列队空、队满的判别条件。 教学时数：10学时 教学内容： 3.1栈（3学时） 一、抽象数据类型栈的定义 二、栈的表示和实现 3.2栈的应用举例（3学时） 一、数制转换 二、括号匹配的检验 三、行编辑程序 四、表达式求值 五、上机实验栈的基本操作 3.3队列（4学时） 一、抽象数据类型队列的定义 二、链队列 三、循环队列 四、上机实验队列的基本操作 考核要求： 理解栈的逻辑结构定义，掌握在顺序栈存储结构上如何实现栈的基本运算如入栈出栈等操作，了解链式栈上同样的操作如何实现 二、串的抽象数据类型定义 4.2 串的表示和实现（2学时） 一、定长顺序存储表示 二、堆分配存储表示 4.3串的模式匹配算法（1学时） 一、求子串位置的定位函数 二、模式匹配的一种改进算法 考核要求： 串的逻辑结构及串上的基本运算 二、以列为主序的方式数组的顺序存储结构 5.3 矩阵的压缩存储（2学时） 一、特殊矩阵 二、稀疏矩阵 5.4 广义表的定义（1学时） 一、广义表的概念 二、广义表的抽象数据类型定义 5.5 广义表的存储结构（2学时） 一、设定结点的结构 二、广义表的头尾链表存储表示