《数据结构》课程教案课程类别：专业基础课适用专业：计算机应用技术授课学时：32学时课程学分：4学分一、课程性质、任务课程性质：《数据结构》是计算机应用技术专业的必修课程，也是研究如何对数据进行组织和设计、如何编制高效率的处理程序的一门基础学科。

课程任务：1、学习计算机程序编写中的数据组织和设计；2、数据的物理结构和逻辑结构；3、经典算法的设计和算法效率的分析。

二、课程培养目标：（一）知识目标通过理论学习和程序的编写，使学生系统地掌握程序中数据的组织、数据的物理结构和逻辑结构，在重要算法的实现上逐步提高编程能力。

（二）技能目标通过课程的学习，让学生掌握重要的数据结构，对数据的逻辑结构和物理结构有深入的理解，同时能编写出使用重要算法知识的程序，并运用所学知识编写程序解决实际中的问题。

（三）素质目标通过课程的学习，让学习学会自学，培养学生的自学能力、克服学习困难的能力，同时让学生掌握计算机编程中数据结构的学习方法，并养成严谨、认真、仔细、踏实、上进的好习惯。

三、选用教材与参考资料教材版本信息《数据结构与算法简明教程（Java语言版）》清华大学出版社叶小平陈瑛主编教材使用评价本教材经过两年的使用，得到了读者一致认可，同时也在不断改进，适合高职高专教学使用，内容基础、重难点突出，符合高职高专“理论够用、注重实践”的要求。

选用的参考资料严蔚敏.吴伟民《数据结构（C语言版）》.清华大学出版社.2009年版殷人昆.《数据结构》.清华大学出版社.1999年版《C语言程序设计》.石油大学出版社《C语言程序设计》.中国石油大学出版社.2006年版四、本课程与其他课程的联系与分工先修课程《离散数学》、《程序设计基础》后续课程《面向对象技术》、《操作系统》与其他课程配合与取舍情况《数据结构》与《离散数学》知识点结合较多，《离散数学》讲求逻辑思维能力的培养和训练，《数据结构》中逻辑结构的学习也需要逻辑思维能力做铺垫。

同时《程序设计基础》课程也为学习《数据结构》打下了基础，对于本课程的教材，我们采用C语言来描述数据结构，因此程序设计基础也是以C语言作为的对象。

本课程也与《算法设计与分析》结合得很紧密，因此在学习中我们也会引入常见算法的学习，达到两者共同促进的目的。

五、课程教学内容与基本要求第一章数据结构导论（一）、教学内容第一节数据结构的基本概念一、引言二、数据结构有关概念及术语第二节算法和算法描述一、什么是算法二、算法描述工具——类C语言第三节算法评价一、时间二、空间（二）、教学目的要求通过本章的学习让学生了解数算法的基本概念，理解如何运用类C语言来描述算法，掌握据结构的概念和相关术语、算法的描述方法，学会从程序中分析算法效率和用函数式表示该程序的算法效率。

在学完本章后，要求学生对数据结构的涉及领域有大体的认识，同时了解数据结构的作用，明确数据结构和程序开发的关系。

通过对算法效率的分析，学会使用这一知识点来优化自己所写程序的执行效率。

重难点分析：本章重点是据结构的概念和相关术语，特别是数据的逻辑结构和物理结构的含义，顺序存储和链式存储的含义，类C语言的表示。

难点是学会从程序中分析算法效率和用函数式表示该程序的算法效率。

第二章线性表（一）、教学内容第一节线性表的逻辑结构一、线性表的定义二、线性表的基本操作第二节线性表的顺序存储结构一、顺序存储结构二、基本操作的实现三、动态分配的顺序存储结构介绍第三节线性表的链式存储结构一、单链表二、单链表的基本操作第四节循环链表和双向链表一、循环链表二、双向链表第五节线性表的应用——多项式相加问题（二）、教学目的要求通过本章的学习让学生进一步了解线性表的定义、稀疏矩阵的三元组存储，掌握C语言中指针知识的运用和链表的实现方式，掌握线性表的基本操作和顺序存储结构、链式存储结构的实现，同时进一步掌握数组、矩阵的操作，学会编写程序实现矩阵的两种转置算法。

在学完本章后，要求学生能够掌握编程实现线性表中元素的插入和删除操作，对于双向链表的插入和删除操作要操作熟练，同时能编程实现运用线性表解决多项式相加问题、运用数组实现矩阵的转置问题。

重难点分析：本章重点是线性表的基本操作和顺序存储结构、链式存储结构的实现，数组、矩阵的操作，编写程序实现多项式相加问题（应用线性表）、矩阵的两种转置算法。

难点是链式存储结构的实现、编写程序实现矩阵的两种转置算法以及稀疏矩阵的十字链表算法。

第三章栈和队列第一节栈一、栈的定义及其运算二、栈的顺序存储结构三、栈的链式存储四、栈的应用举例第二节队列一、队列的定义及运算二、队列的顺序存储结构三、队列的链式存储结构第三节栈和队列的应用实例——停车场管理（二）、教学目的要求通过本章的学习让学生进一步了解线性栈和队列的定义和常见用途，掌握栈和队列的基本操作，掌握栈和队列的顺序存储结构及链式存储结构的实现。

在学完本章后，要求学生能够掌握编程实现栈和队列中的元素插入和删除操作，，同时能够运用栈和队列的知识编写程序实现停车场管理、划分子集问题、敢死队问题等经典算法。

重难点分析：本章重点是栈和队列的基本操作，掌握栈和队列的顺序存储结构及链式存储结构。

难点是编写程序实现栈和队列的链式存储结构及插入和删除操作。

第四章串和数组第一节串的定义一、串的定义二、串的存储结构第二节数组的基本概念一、数组的定义二、数组的顺序存储结构第三节特殊矩阵和稀疏矩阵压缩存储一、特殊矩阵压缩存储二、稀疏矩阵压缩存储（二）、教学目的要求通过本章的学习让学生进一步了解线性表中数组的定义、稀疏矩阵的三元组存储，同时进一步掌握数组、矩阵的操作，学会编写程序实现矩阵的两种转置算法。

在学完本章后，要求学生能够编程实现运用线性表解决多项式相加问题、运用数组实现矩阵的转置问题。

重难点分析：本章重点是数组的基本操作和顺序存储结构，矩阵的两种转置算法。

难点是编写程序实现矩阵的两种转置算法以及稀疏矩阵的十字链表算法。

第五章树第一节树的定义和基本术语一、树的定义二、树的基本术语第二节二叉树一、二叉树的定义二、二叉树的重要性质三、二叉树的存储结构四、建立二叉树的二叉链表第三节遍历二叉树一、先根遍历二、中根遍历三、后根遍历第四节线索二叉树一、线索二叉树的基本概念二、中根线索二叉树第五节二叉树、树和森林一、树的存储结构二、树与二叉树之间的转换三、森林与二叉树的转换四、树和森林的遍历第六节哈夫曼树及其应用第七节二叉树遍历算法的简单应用实例（二）、教学目的要求通过本章的学习让学生了解树和森林的遍历，树在计算机编程中的应用，理解树的性质、线索二叉树的含义，掌握数据结构中树的定义和相关术语、二叉树的逻辑结构和物理结构、二叉树的先根遍历、中根遍历、后根遍历和层次遍历，二叉树和非二叉树的一般树的转换，二叉树和森林的转换，哈夫曼树的含义和应用，二叉树遍历算法的简单应用的程序实现。

在学完本章后，要求学生能够运用树的性质解决常见的树的求解问题，同时能够编程实现树的遍历、树的层数和叶子总数等等的计算。

重难点分析：本章重点是掌握数据结构中树的定义和相关术语，树的性质，二叉树的逻辑结构和物理结构、二叉树的先根遍历、中根遍历、后根遍历和层次遍历，二叉树和非二叉树的一般树的转换，二叉树和森林的转换，哈夫曼树的含义和应用。

难点是理解并掌握如何编程实现二叉树遍历算法的简单应用。

第六章图第一节图的基本概念一、图的定义二、图的基本术语第二节图的存储结构一、邻接矩阵表示法二、邻接表第三节图的遍历一、连通图的深度优先搜索遍历二、连通图的广度优先搜索遍历三、求图的连通分量第四节图的最小生成树一、生成树的概念二、网络的最小生成树第五节最短路径一、从某源点到其余顶点之间的最短路径二、求有向网中每一对顶点间的最短路径第六节有向无环图及其应用一、拓扑序列二、关键路径（二）、教学目的要求通过本章的学习让学生了解图在计算机中的常见用途、关键路径的定义和求解，理解图的连通分量的求法、拓扑序列，掌握图的定义及基本术语、图的存储中邻接矩阵和邻接表的表示、最小生成树的求解法、最短路径的两种实现方式。

在学完本章后，要求学生能够掌握图的存储的编程实现，同时能够编程实现求解图的最小生成树的算法。

重难点分析：本章重点是图的定义及基本术语、图的存储中邻接矩阵和邻接表的表示、最小生成树的求解法、最短路径的两种实现方式。

难点是关键路径的求解原理和编程实现。

第七章排序第一节排序的基本概念第二节插入排序一、直接插入排序二、折半插入排序三、希尔排序第三节交换排序一、冒泡排序二、快速排序第四节选择排序一、简单选择排序二、堆排序第五节归并排序第六节基数排序第七节内部排序总结第八节多路归并用于外排序的简介第九节排序应用实例（二）、教学目的要求通过本章的学习让学生了解排序的实质含义、常见的几种排序方式的定义，理解常见的几种排序方式的具体操作、联系及区别，掌握插入排序、交换排序、选择排序的算法效率和适用环境。

在学完本章后，要求学生能够掌握插入排序、交换排序、选择排序的具体操作原理和效率，同时能够编程实现关键字的排序。

重难点分析：本章重点是常见的几种排序方式的具体操作、联系及区别，插入排序、交换排序、选择排序的算法效率和适用环境。

难点是插入排序、交换排序、选择排序的算法效率和适用环境的确定。

第七章查找第一节查找的基本概念第二节静态查找表一、顺序表的概念二、顺序查找三、折半查找四、索引顺序查找第三节动态查找表一、二叉排序查找树二、平衡二叉树与动态平衡技术三、B-树用于外部查找第四节哈希表及其查找一、哈希表与哈希函数二、构造哈希函数的常用方法三、解决冲突的主要方法四、哈希查找效率的分析第五节查找应用实例（二）、教学目的要求通过本章的学习让学生了解查找的实质含义、顺序表的概念、B-树用于外部查找，理解索引顺序查找、平衡二叉树、动态平衡技术、哈希表、哈希函数的常见构造方法和解决冲突的方法，哈希查找效率的分析，掌握二叉查找排序树的构造，顺序查找和折半查找的原理及操作步骤。

在学完本章后，要求学生能够掌握二叉查找排序树的构造方法，同时能够编程实现查找操作。

重难点分析：本章重点是常见的几种排序方式的具体操作、联系及区别，插入排序、交换排序、选择排序的算法效率和适用环境。

难点是插入排序、交换排序、选择排序的算法效率和适用环境的确定。

第八章排序第一节了解排序的基本概念第二节掌握插入排序方法第三节掌握交换排序方法第四节掌握选择排序方法第五节掌握归并排序和基数排序方法（二）、教学目的要求通过本章的学习让学生了解排序的基本概念和基本方法。

在学完本章后，要求学生能够掌握插入排序、交换排序、选择排序、归并排序和基数排序，同时能够编程实现简单的排序算法。

重难点分析：本章重点是几种基本排序的方法，难点是编程实现排序的算法。