《数据结构》课程教案

课程类别：专业基础课适用专业：计算机应用技术授课学时：32学时课程学分：4学分一、课程性质、任务对数据进行组织和设计、如何编制高效率的处理程序的一门基础学科。课程任务：1、学习计算机程序编写中的数据组织和设计；2、数据的物理结构和逻辑结构；3、经典算法的设计和算法效率的分析。二、课程培养目标：（一）知识目标物理结构和逻辑结构，在重要算法的实现上逐步提高编程能力。（二）技能目标程序解决实际中的问题。（三）素质目标能力，同时让学生掌握计算机编程中数据结构的学习方法，并养成严谨、认真、仔细、踏实、上进的好习惯。三、选用教材与参考资料教材版本信息《数据结构与算法简明教程（Java叶小平陈瑛主编教材使用评价清华大学出版社本教材经过两年的使用，得到了读者一致认可，同时也在不断改进，适合高的要求。1选用的参考资料严蔚敏.吴伟民《数据结构（C年版殷人昆.《数据结构》.清华大学出版社.1999年版《C语言程序设计》.石油大学出版社《C语言程序设计》.中国石油大学出版社.2006年版四、本课程与其他课程的联系与分工先修课程后续课程与其他课程配合与取舍情况铺垫。同时《程序设计基础》课程也为学习《数据结构》打下了基础，对于本课CC语言作为的对象。本课程也与《算法设计与分析》结合得很紧密，因此在学习中我们也会引入常见算法的学习，达到两者共同促进的目的。五、课程教学内容与基本要求第一章数据结构导论第一节数据结构的基本概念一、引言二、数据结构有关概念及术语第二节算法和算法描述一、什么是算法二、算法描述工具——类C语言第三节算法评价一、时间二、空间C语言来描法效率和用函数式表示该程序的算法效率。使用这一知识点来优化自己所写程序的执行效率。2C从程序中分析算法效率和用函数式表示该程序的算法效率。第二章线性表第一节线性表的逻辑结构一、线性表的定义二、线性表的基本操作第二节线性表的顺序存储结构一、顺序存储结构二、基本操作的实现三、动态分配的顺序存储结构介绍第三节线性表的链式存储结构一、单链表二、单链表的基本操作第四节循环链表和双向链表一、循环链表二、双向链表第五节线性表的应用——多项式相加问题通过本章的学习让学生进一步了解线性表的定义、稀疏矩阵的三元组存储，掌握C存储结构、链式存储结构的实现，同时进一步掌握数组、矩阵的操作，学会编写程序实现矩阵的两种转置算法。在学完本章后，要求学生能够掌握编程实现线性表中元素的插入和删除操决多项式相加问题、运用数组实现矩阵的转置问题。算法以及稀疏矩阵的十字链表算法。第三章栈和队列第一节栈一、栈的定义及其运算二、栈的顺序存储结构三、栈的链式存储四、栈的应用举例第二节队列3一、队列的定义及运算二、队列的顺序存储结构三、队列的链式存储结构第三节栈和队列的应用实例——停车场管理和队列的基本操作，掌握栈和队列的顺序存储结构及链式存储结构的实现。敢死队问题等经典算法。操作。第四章串和数组第一节串的定义一、串的定义二、串的存储结构第二节数组的基本概念一、数组的定义二、数组的顺序存储结构第三节特殊矩阵和稀疏矩阵压缩存储一、特殊矩阵压缩存储二、稀疏矩阵压缩存储法。用数组实现矩阵的转置问题。算法。难点是编写程序实现矩阵的两种转置算法以及稀疏矩阵的十字链表算法。第五章树第一节树的定义和基本术语一、树的定义二、树的基本术语第二节二叉树4一、二叉树的定义二、二叉树的重要性质三、二叉树的存储结构四、建立二叉树的二叉链表第三节遍历二叉树一、先根遍历二、中根遍历三、后根遍历第四节线索二叉树一、线索二叉树的基本概念二、中根线索二叉树第五节二叉树、树和森林一、树的存储结构二、树与二叉树之间的转换三、森林与二叉树的转换四、树和森林的遍历第六节哈夫曼树及其应用第七节二叉树遍历算法的简单应用实例的逻辑结构和物理结构、二叉树的先根遍历、中根遍历、后根遍历和层次遍历，用，二叉树遍历算法的简单应用的程序实现。能够编程实现树的遍历、树的层数和叶子总数等等的计算。重难点分析：本章重点是掌握数据结构中树的定义和相关术语，树的性质，义和应用。难点是理解并掌握如何编程实现二叉树遍历算法的简单应用。第六章图第一节图的基本概念一、图的定义二、图的基本术语第二节图的存储结构一、邻接矩阵表示法二、邻接表5第三节图的遍历一、连通图的深度优先搜索遍历二、连通图的广度优先搜索遍历三、求图的连通分量第四节图的最小生成树一、生成树的概念二、网络的最小生成树第五节最短路径一、从某源点到其余顶点之间的最短路径二、求有向网中每一对顶点间的最短路径第六节有向无环图及其应用一、拓扑序列二、关键路径解，理解图的连通分量的求法、拓扑序列，掌握图的定义及基本术语、图的存储中邻接矩阵和邻接表的表示、最小生成树的求解法、最短路径的两种实现方式。求解图的最小生成树的算法。求解原理和编程实现。第七章排序第一节排序的基本概念第二节插入排序一、直接插入排序二、折半插入排序三、希尔排序第三节交换排序一、冒泡排序二、快速排序第四节选择排序一、简单选择排序二、堆排序第五节归并排序第六节基数排序第七节内部排序总结6第八节多路归并用于外排序的简介第九节排序应用实例通过本章的学习让学生了解排序的实质含义、常见的几种排序方式的定义，理解常见的几种排序方式的具体操作、联系及区别，掌握插入排序、交换排序、选择排序的算法效率和适用环境。作原理和效率，同时能够编程实现关键字的排序。入排序、交换排序、选择排序的算法效率和适用环境。难点是插入排序、交换排序、选择排序的算法效率和适用环境的确定。第七章查找第一节查找的基本概念第二节静态查找表一、顺序表的概念二、顺序查找三、折半查找四、索引顺序查找第三节动态查找表一、二叉排序查找树二、平衡二叉树与动态平衡技术三、B-树用于外部查找第四节哈希表及其查找一、哈希表与哈希函数二、构造哈希函数的常用方法三、解决冲突的主要方法四、哈希查找效率的分析第五节查找应用实例查找，理解索引顺序查找、平衡二叉树、动态平衡技术、哈希表、哈希函数的常造，顺序查找和折半查找的原理及操作步骤。程实现查找操作。入排序、交换排序、选择排序的算法效率和适用环境。难点是插入排序、交换排7序、选择排序的算法效率和适用环境的确定。第八章排序第一节了解排序的基本概念第二节掌握插入排序方法第三节掌握交换排序方法第四节掌握选择排序方法第五节掌握归并排序和基数排序方法通过本章的学习让学生了解排序的基本概念和基本方法。在学完本章后，要求学生能够掌握插入排序、交换排序、选择排序、归并排序和基数排序，同时能够编程实现简单的排序算法。六、教学学时分配（表格展示各章或各个模块的学时分配）课时2第二章线性表的逻辑结422第五章树及其应用，二叉树遍历算法的简单应