《数据结构》课程计算机数据结构与算法_计算机-数据结构与算法.pdf

《《数据结构》课程计算机数据结构与算法_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《《数据结构》课程计算机数据结构与算法_计算机-数据结构与算法.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构 课程 教学大纲 大连职业技术学院 2004 年 9 月 一、课程名称 数据结构 二、学分 4 学分 三、适用专业 计算机软件设计（英语）四、教学目的 数据结构是高等教育计算机信息管理专业中的一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程 的目的和任务是使学生较全面地掌握各种常用的数据结构，为学习后 续软件课程提供必要的基础，提高运用数据结构解决实际问题的能 力。五、教学要求 1.从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图等常用的数据结构。2.掌握在各种常用的数据结构上实现的排序和查找运算。3.对算

2、法的时间和空间复杂性有一定的分析能力。4.针对简单的应用问题.应能选择合适的数据结构及设计有效的算法解决之。六、教学课时数分配表 教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备

3、注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种 课时数分配 作业 备 章 次 教学内容 总课 理论 实践 习 注 时数 次数 题 第一章 绪论 2 2 第二章 线性表 14 7(6)7(8)2 第三章 栈和队列 6(8)3(4)3(4)2 第四章 串 4 2 2 1 第五章 数组和广义表 4 2 2 1 第六章 树和二叉树 8 4 4 2 第七章 图 8 4 4 2 第八章 查找 8 4 4 1 第九章 内部排序 10(8)4 6(4)1 合计 64 32 32 12 七、理论教学内容 第一章 绪论（2

4、课时）内容提要：本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。教学重点和难点：本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。1.1 基本概念和术语（1 课时）1.2 算法的描述和分析（1 课时）第二章 线性表（7 课时）内容提要：本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法

5、，解决与线性表相关的实际问题。教学重点和难点：教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概

6、念和术语以及学习数据结构的意义要求了解本章介绍的各种 本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。2.1 线性表的逻辑结构（2 课时）2.2 线性表的顺序存储结构（2 课时）2.3 线性表的链式存储结构（2 课时）2.4 顺序表和链表的比较（1 课时）第三章 栈和队列（3 课时）内容提要：本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈 和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。教学重点和难点：本章重点是掌握栈和队列在两种存储结

7、构上实现的基本运算，难点是循环队列中对边界条件的处理。3.1 栈（1 课时）3.2 队列（1 课时）3.3 栈和队列的应用（1 课时）第四章 串（2 课时）内容提要：本章目的是介绍串的逻辑结构、存储结构及其中上的基本运算，由于言及其它高级语言均已具备了较强的串处理功能。C 语 教学重点和难点：本章重点是掌握串上实现的模式匹配算法，这也是本章的难点。4.1 串及其运算（1 课时）4.2 串的存储结构（1 课时）第五章 数组和广义表 （2 课时）内容提要：教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全

8、面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种 本章目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容。教学重点和难点：

9、本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。5.1 多维数组（1 课时）5.2 矩阵的压缩存储（0.5 课时）5.3 广义表的概念（0.5 课时）第六章 树和二叉树（4 课时）内容提要：本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。教学重点和难点：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。6.1 树的概念（0.5 课时）6.2 二叉树（1 课时）

10、6.3 二叉树的遍历（1 课时）6.4 线索二又树（0.5 课时）6.5 树和森林（0.5 课时）6.6 哈夫曼树及其应用（0.5 课时）第七章 图（4 课时）内容提要：图的定义，有关术语和存贮结构，图的两种遍历算法。两个求最小生成树的算法，最短路径，拓扑排序和关键路径算法。教学重点和难点：要求学生在熟悉这些内容的基础上，重点掌握图存贮结构，图的两种遍历算法。本章难点是求最小生成树的算法，最短路径，拓扑排序和关键路径算法。教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学

11、习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种 7.1 图的基本概念和存贮结构（1 课时）7.2 最小生成树的算法（1 课时）7.3 最短路径，拓扑排序和关键路径算法（2 课时）第八章 查找（4 课时）内容提要：本

12、章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。教学重点和难点：要求学生在熟悉这些内容的基础上，重点掌握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及 B树上的插入和删除算法。9.1 基本概念（1 课时）9.2 线性表的查找（1 课时）9.3 树的查找（1 课时）9.4 散列技术（1 课时）第九章 内部排序（4 课时）内容提要：本章目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。教学重点和难点：要求学生在熟悉这些内容的基础上，

13、重点掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程。本章难点是四个排序算法的实现。9.1 插入排序（1 课时）9.2 交换排序（1 课时）9.3 选择排序（0.5 课时）9.4 归并排序（0.5 课时）9.5 分配排序（0.5 课时）教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能

14、选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种 9.6 各种排序方法的比较和选择（0.5 课时）八、实践教学内容 第一章 线性表（7 课时）内容提要：本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的

15、实际问题。教学重点和难点：本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。1.1 线性表的逻辑结构（1 课时）1.2 线性表的顺序存储结构（2 课时）1.3 线性表的链式存储结构（2 课时）1.4 顺序表和链表的比较（2 课时）第二章 栈和队列（3 课时）内容提要：本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈 和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。教学重点和难点：本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循

16、环队列中对边界条件的处理。2.1 栈（1 课时）2.2 队列（1 课时）2.3 栈和队列的应用（1 课时）教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容

17、第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种 第三章 串（2 课时）内容提要：本章目的是介绍串的逻辑结构、存储结构及其中上的基本运算，由于言及其它高级语言均已具备了较强的串处理功能。C 语 教学重点和难点：本章重点是掌握串上实现的模式匹配算法，这也是本章的难点。3.1 串及其运算（1 课时）3.2 串的存储结构（1 课时）第四章 数组和广义表 （2 课时）内容提要：本章目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容。教学重点和难点：本章重点是熟悉多维数组的存储

18、方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。4.1 多维数组（1 课时）4.2 矩阵的压缩存储（1 课时）第五章 树和二叉树（4 课时）内容提要：本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。教学重点和难点：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。5.1 二叉树（1 课时）5.2 线索二又树（1 课时）5.3 树和森林（1 课时）5.4 哈夫曼树及其应用（1 课时）教学目

19、的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种

20、 第六章 图（4 课时）内容提要：图的定义，有关术语和存贮结构，图的两种遍历算法。两个求最小生成树的算法，最短路径，拓扑排序和关键路径算法。教学重点和难点：要求学生在熟悉这些内容的基础上，重点掌握图存贮结构，图的两种遍历算法。本章难点是求最小生成树的算法，最短路径，拓扑排序和关键路径算法。6.1 图的基本概念和存贮结构（1 课时）6.2 最小生成树的算法（1 课时）6.3 最短路径，拓扑排序和关键路径算法（2 课时）第七章 查找（4 课时）内容提要：本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。教学重点和难点：要求学生在熟悉这些内容的基础上

21、，重点掌握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及 B树上的插入和删除算法。7.1 线性表的查找（1 课时）7.2 树的查找（2 课时）7.3 散列技术（1 课时）第八章 内部排序（6 课时）内容提要：本章目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。教学重点和难点：要求学生在熟悉这些内容的基础上，重点掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程。本章难点是四个排序算法的实现。8.1 插入排序（1 课时）教学目的数据结构是高等教育计算机信息管理专业中的

22、一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种 8.2 交换排序（1 课时）8.3 选择

23、排序（1 课时）8.4 归并排序（1 课时）8.5 分配排序（1 课时）8.6 各种排序方法的比较和选择（1 课时）九、使用教材：数据结构（C 语言版）严蔚敏 著 清华大学出版社 1999.6 十、参考书目：1、数据结构（C 语言版）清华大学出版社 主编：严蔚敏、吴伟民 2007.3；2、数据结构题集（C 语言版）清华大学出版社 主编：严蔚敏 1999.2；3、数据结构清华大学出版社 主编：李筠、姜学军 2008.8；4、数据结构（第二版）清华大学出版社 主编：张世和 2007.9 ；5、数据结构习题解析与实训(第 2 版)清华大学出版社 主编：张世和 2008.8 ；6、数据结构（第二版）高

24、等教育出版社 主编：陈雁 2004.11 ；7、实用数据结构基础清华大学出版社 主编：谭浩强、陈明 2005.2；8、数据结构与算法电子工业出版社 主编：熊岳山 2007.8；9、数据结构实用教程 北京交通大学出版社 主编：魏衍君 周军 2007.6 ；10、数据结构：使用 C+语言描述人民邮电出版社 主编：陈慧南 2006.10 ；11、数据结构 电子工业出版社 主编：刘清、王琼 2001.9 ；12、算法与数据结构（第二版）电子工业出版社 主编：傅清祥、王晓东 2001.8。教学目的数据结构是高等教育计算机信息管理专业中的一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据结构为学习后续软件课程提供必要的基础线性表栈队列串数组广义表树图等常用的数据结构掌握在各种常用的数据结构上实现的排序和查找运算对算法的时间和空间复杂性有一定的分析能力对简单的应用问题应能选择合适的数据结构及设计有效的算法解决之六教学课时数广义表树和二叉树图查找内部排序合计课时数分配理论实践总课时数作业备注次数习题七理论教学内容第一章绪论课时内容提要本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义要求了解本章介绍的各种