新版（数据构造）教学大纲.docx

新版（数据构造）教学大纲一、课程名称（数据构造）二、教学目的数据构造是高等教育计算机信息管理专业中的一门专业基础课，在计算机软件的各个领域中均会使用到数据构造的有关知识。本课程的目的和任务是使学生较全面地把握各种常用的数据构造，为学习后续软件课程提供必要的基础，提高运用数据构造解决实际问题的能力。三、教学要求1.从数据构造的逻辑构造、存储构造和数据的运算三个方面去把握线性表、栈、队列、串、数组、广义表、树、图等常用的数据构造。2.把握在各种常用的数据构造上实现的排序和查找运算。3.对算法的时间和空间复杂性有一定的分析能力。4.针对简单的应用问题.应能选择适宜的数据构造及设计有效的算法解决之。四、教学课时数分配表五、理论教学内容第一章绪论2课时内容提要：本章的目的是介绍数据构造中常用的基本概念和术语以及学习数据构造的意义，要求了解本章介绍的各种基本概念和术语，把握算法描绘和分析的方法。教学重点和难点：本章重点是了解数据构造的逻辑构造、存储构造及数据的运算三方面的概念及互相关系，难点是算法复杂度的分析方法。§1.1基本概念和术语1课时§1.2算法的描绘和分析1课时第二章线性表7课时内容提要：本章目的是介绍线性表的逻辑构造和各种存储表示方法，以及定义在逻辑构造上的各种基本运算及其在存储构造上怎样实现这些基本运算。要求在熟悉这些内容的基础上，能够针对详细应用问题的要求和性质，选择适宜的存储构造设计出相应的有效算法，解决与线性表相关的实际问题。教学重点和难点：本章重点是熟练把握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。§2.1线性表的逻辑构造2课时§2.2线性表的顺序存储构造2课时§2.3线性表的链式存储构造2课时§2.4顺序表和链表的比拟1课时第三章栈和队列3课时内容提要：本章目的是介绍栈和队列的逻辑构造定义及在两种存储构造上怎样实现栈和队列的基本运算。要求在把握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。教学重点和难点：本章重点是把握栈和队列在两种存储构造上实现的基本运算，难点是循环队列中对边界条件的处理。§3.1栈1课时§3.2队列1课时§3.3栈和队列的应用1课时第四章串2课时内容提要：本章目的是介绍串的逻辑构造、存储构造及其中上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能。教学重点和难点：本章重点是把握串上实现的形式匹配算法，这也是本章的难点。§4.1串及其运算1课时§4.2串的存储构造1课时第五章数组和广义表2课时内容提要：本章目的是介绍多维数组的逻辑构造特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容。教学重点和难点：本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。§5.1多维数组1课时§5.2矩阵的压缩存储0.5课时§5.3广义表的概念0.5课时第六章树和二叉树4课时内容提要：本章目的是介绍二叉树的定义、性质、存储构造、遍历、线索化，树的定义、存储构造、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。教学重点和难点：重点把握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。§6.1树的概念0.5课时§6.2二叉树1课时§6.3二叉树的遍历1课时§6.4线索二又树0.5课时§6.5树和森林0.5课时§6.6哈夫曼树及其应用0.5课时第七章图4课时内容提要：图的定义，有关术语和存贮构造，图的两种遍历算法。两个求最小生成树的算法，最短途径，拓扑排序和关键途径算法。教学重点和难点：要求学生在熟悉这些内容的基础上，重点把握图存贮构造，图的两种遍历算法。本章难点是求最小生成树的算法，最短途径，拓扑排序和关键途径算法。§7.1图的基本概念和存贮构造1课时§7.2最小生成树的算法1课时§7.3最短途径，拓扑排序和关键途径算法2课时第八章查找4课时内容提要：本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。教学重点和难点：要求学生在熟悉这些内容的基础上，重点把握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及B树上的插入和删除算法。§9.1基本概念1课时§9.2线性表的查找1课时§9.3树的查找1课时§9.4散列技术1课时第九章内部排序4课时内容提要：本章目的是介绍五类内部排序方法的基本思想、排序经过、算法实现、时间和空间性能的分析以及各种排序方法的比拟和选择。教学重点和难点：要求学生在熟悉这些内容的基础上，重点把握快速排序、堆排序、归并排序和基数排序的基本思想及排序经过。本章难点是四个排序算法的实现。§9.1插入排序1课时§9.2交换排序1课时§9.3选择排序0.5课时§9.4归并排序0.5课时§9.5分配排序0.5课时§9.6各种排序方法的比拟和选择0.5课时八、实践教学内容第一章线性表7课时内容提要：本章目的是介绍线性表的逻辑构造和各种存储表示方法，以及定义在逻辑构造上的各种基本运算及其在存储构造上怎样实现这些基本运算。要求在熟悉这些内容的基础上，能够针对详细应用问题的要求和性质，选择适宜的存储构造设计出相应的有效算法，解决与线性表相关的实际问题。教学重点和难点：本章重点是熟练把握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。§1.1线性表的逻辑构造1课时§1.2线性表的顺序存储构造2课时§1.3线性表的链式存储构造2课时§1.4顺序表和链表的比拟2课时第二章栈和队列3课时内容提要：本章目的是介绍栈和队列的逻辑构造定义及在两种存储构造上怎样实现栈和队列的基本运算。要求在把握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。教学重点和难点：本章重点是把握栈和队列在两种存储构造上实现的基本运算，难点是循环队列中对边界条件的处理。§2.1栈1课时§2.2队列1课时§2.3栈和队列的应用1课时第三章串2课时内容提要：本章目的是介绍串的逻辑构造、存储构造及其中上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能。教学重点和难点：本章重点是把握串上实现的形式匹配算法，这也是本章的难点。§3.1串及其运算1课时§3.2串的存储构造1课时第四章数组和广义表2课时内容提要：本章目的是介绍多维数组的逻辑构造特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容。教学重点和难点：本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。§4.1多维数组1课时§4.2矩阵的压缩存储1课时第五章树和二叉树4课时内容提要：本章目的是介绍二叉树的定义、性质、存储构造、遍历、线索化，树的定义、存储构造、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。教学重点和难点：重点把握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。§5.1二叉树1课时§5.2线索二又树1课时§5.3树和森林1课时§5.4哈夫曼树及其应用1课时第六章图4课时内容提要：图的定义，有关术语和存贮构造，图的两种遍历算法。两个求最小生成树的算法，最短途径，拓扑排序和关键途径算法。教学重点和难点：要求学生在熟悉这些内容的基础上，重点把握图存贮构造，图的两种遍历算法。本章难点是求最小生成树的算法，最短途径，拓扑排序和关键途径算法。§6.1图的基本概念和存贮构造1课时§6.2最小生成树的算法1课时§6.3最短途径，拓扑排序和关键途径算法2课时第七章查找4课时内容提要：本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。教学重点和难点：要求学生在熟悉这些内容的基础上，重点把握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及B树上的插入和删除算法。§7.1线性表的查找1课时§7.2树的查找2课时§7.3散列技术1课时第八章内部排序6课时内容提要：本章目的是介绍五类内部排序方法的基本思想、排序经过、算法实现、时间和空间性能的分析以及各种排序方法的比拟和选择。教学重点和难点：要求学生在熟悉这些内容的基础上，重点把握快速排序、堆排序、归并排序和基数排序的基本思想及排序经过。本章难点是四个排序算法的实现。§8.1插入排序1课时§8.2交换排序1课时§8.3选择排序1课时§8.4归并排序1课时§8.5分配排序1课时§8.6各种排序方法的比拟和选择1课时九、使用教材：（数据构造）C语言版严蔚敏著清华大学出版社1999.6十、参考书目：1、（数据构造C语言版）清华大学出版社主编：严蔚敏、吴伟民2007.3；2、（数据构造题集C语言版）清华大学出版社主编：严蔚敏1999.2；3、（数据构造）清华大学出版社主编：李筠、姜学军2020.8；4、（数据构造第二版）清华大学出版社主编：张世和2007.9；5、（数据构造习题解析与实训(第2版)）清华大学出版社主编：张世和2020.8；6、（数据构造第二版）高等教育出版社主编：陈雁2004.11；7、（实用数据构造基础）清华大学出版社主编：谭浩强、陈明2005.2；8、（数据构造与算法）电子工业出版社主编：熊岳山2007.8；9、（数据构造实用教程）北京交通大学出版社主编：魏衍君周军2007.6；10、（数据构造：使用C+语言描绘）人民邮电出版社主编：陈慧南2006.10；11、（数据构造）电子工业出版社主编：刘清、王琼2001.9；12、（算法与数据构造第二版）电子工业出版社主编：傅清祥、王晓东2001.8。