数据结构 教学大纲

课程代码：090131110

课程英文名称：Data structure

课程总学时：48  讲课：40  实验（上机）：8

适用专业：信息与计算科学专业

大纲编写（修订）时间：2017.11

一、大纲使用说明

（一）课程的地位及教学目标

    本课程是信息与计算科学专业的一门重要的专业基础课,它较详细地阐述了使用计算机解决具体问题时所建立的数学模型的逻辑结构与存储结构的多种类型以及对数据具体进行操作的算法实现。通过本课程的学习，使学生了解和掌握使用高级语言编程时组织数据的基本理论和方法，是学生进一步学习计算机方面相关专业课程的必备基础。

（二）知识、能力及技能方面的基本要求

    1.基本知识：掌握时间效率和空间效率的概念，掌握数据结构中的线性表、树、图等基本结构。

    2.基本理论和方法：掌握线性表的基本操作，栈、队列、串、数组的基本操作，树的应用方法，图的应用方法及数据的查找、排序操作等。

3.基本技能:学生应该能够使用高级语言正确定义数据的逻辑结构和选择有效的存储结构解决具体问题，其算法实现应注重时间效率和空间效率。数据对象查找与排序操作等较常用基本操作，学生应掌握算法学会合理使用。

（三）实施说明

    1．教学方法：课堂讲授中要重点对基本概念、基本方法和解题思路的讲解；采用启发式教学，培养学生思考问题、分析问题和解决问题的能力；引导和鼓励学生通过实践和自学获取知识，培养学生的自学能力；增加讨论课，调动学生学习的主观能动性；注意培养学生提高利用标准、规范及手册等技术资料的能力。讲课要联系实际并注重培养学生的创新能力。

    2．教学手段：在教学中采用电子教案及多媒体教学系统等先进教学手段，以确保在有限的学时内，全面、高质量地完成课程教学任务。

（四）对先修课的要求

    要求学生有高级语言的基础知识与编程经验，应该学习过C语言程序设计等课程。

（五）对习题课、实验环节的要求

1.对习题课的要求 

学习完每部分内容，都要做相关的练习题，加深对课堂所学知识的理解，检验学生对所学内容的掌握程度，引导学生对所讲例题举一反三，从而达到熟练编程的能力。

2.对实验环节的要求

上机实践环节在理论课后一周左右进行。通过上机调试运行自编程序，熟练掌握程序设计、调试程序的方法。

3. 本课程的课程设计单独设课，单独考核，具体要求参见相应的课程设计教学大纲。

（六）课程考核方式

1．考核方式：考试

    2．考核目标：在考核学生对数据结构基本知识、基本方法的基础上，重点考核学生的分析能力及算法设计能力。

    3．成绩构成：本课程的总成绩由三部分组成：期末考试成绩占70%，平时成绩（包括作业情况、出勤情况、期中成绩等）和实验成绩共占30%。

（七）主要参考书目:

   《数据结构》 严蔚敏 清华大学出版社  2012年5月

《数据结构（C语言版）》 严蔚敏等  人民邮电出版社  2015年2月

《数据结构—用C语言描述》狄国华等编著 高等教育出版社2015年7月

二、中文摘要

本课程是信息与计算科学专业的一门必修课。通过本课程学习，要求学生掌握数据结构和算法的基本概念和技术，从而能够对于给定问题选择合适的数据结构，并设计相应的操作算法。掌握数组、线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及内排序、查找等重要技术。本课程将为后续课程的学习以及相关课程设计、毕业设计等奠定重要的基础。

三、课程学时总体分配表

第1部分  绪论

总学时(单位：学时):2  讲课:2  实验（上机）:0

第1.1部分 基本概念与术语

第1.2部分 算法与算法分析

具体内容:

1）了解数据结构的基本概念与术语。

2）理解算法的概念，掌握算法效率的度量。

重  点: 

有关数据结构中的基本概念。

难  点：

算法的描述方法。

习  题:

算法效率的度量。

第2部分 顺序表

总学时(单位：学时):4  讲课:2  实验（上机）:2

第2.1部分  类型定义

第2.2部分  线性表的顺序表示与实现

具体内容:

1）掌握类型定义。

2）掌握线性表的顺序表示与实现。

重  点：

线性表的顺序存储类型。

难  点：

顺序表的插入删除算法中数据元素的移动。

实验（上机）：  

顺序表示基本算法实现

习  题:

顺序表相关算法设计。

第3部分  链表

总学时(单位：学时):8  讲课:6  实验（上机）:2

第3.1部分 线性表的链式存储结构     

第3.2部分 循环链表、双向链表  

具体内容:

1）掌握线性表的链式存储结构。

2）掌握循环链表、双向链表的基本操作。

重  点：

线性表的链式存储结构。

难  点：

链表的插入与删除算法。

实验（上机）： 

链表的基本算法实现。

习  题：

链表的插入与删除算法，一元多项式的处理等。

第4部分  栈

总学时(单位：学时):2  讲课:2   实验（上机）:0 

第4.1部分 栈的表示、实现与应用    

具体内容:

1）掌握栈的表示、实现与应用 。

重  点：

弹栈与压栈操作

难  点：

栈的应用

习  题：

栈的应用程序设计

第5部分  队列

总学时(单位：学时):2  讲课:2   实验（上机）:0 

第5.1队列的表示、实现与应用

具体内容:

1）掌握队列的表示、实现与应用。

重  点：

出队、入队的实现。

习  题：

队列的应用。

第6部分  串、数组、广义表

总学时(单位：学时):4  讲课:4   实验（上机）:0 

第6.1 串、数组、广义表的基本概念、基本操作

第6.2 矩阵的压缩存储

  具体内容:

1）掌握串、数组、广义表的基本概念、基本操作  。

2）理解函矩阵的压缩存储。

重  点：

串的基本概念、基本操作。

难  点：

串的模式匹配。

习  题

串的应用。

第7部分  树和二叉树

总学时(单位：学时):12  讲课:10    实验（上机）:2 

第7.1 树的定义和基本术语  

第7.2 二叉树

第7.3 树和森林

第7.4 赫夫曼树及其应用

具体内容:

1）掌握树的定义和基本术语。

2）掌握二叉树的定义、性质。

3）掌握二叉树的存储结构、遍历二叉树。

4）理解树的存储结构、树和森林的遍历

5）了解赫夫曼树，掌握其应用。

重  点：

二叉树的定义、性质，遍历二叉树。

实验（上机）：

树相关基本算法。

习  题：

二叉排序树的应用，哈夫曼树等。

第8部分  图

总学时(单位：学时):4  讲课:4    实验（上机）:0 

第8.1 图的定义和术语  

第8.2 图的存储结构

第8.3 图的遍历

第8.4图的连通性

第8.5 有向无环图及其应用  

第8.6 最短路径

  具体内容:

1）了解图的定义和术语 。

2）掌握图的存储结构。 

3）掌握图的遍历。

4）掌握图的连通性.

5）了解有向无环图及其应用。

6）掌握最短路径

重  点：

图的存储结构，图的遍历。

习  题: 

图的遍历等。

第9部分  查找

总学时(单位：学时):4  讲课:4   实验（上机）:0 

第9.1查找 

第9.2基于线性表的查找

第9.3基于树的查找

第9.4 哈希表

具体内容:

1）掌握查找概念 。

2）掌握基于线性表的查找算法。

3）掌握基于树的查找算法。

4）了解哈希表概念，掌握哈希函数的构造方法。

重  点：

基于线性表的查找。

难  点：

基于树的查找。

习  题:

多种查找算法的实现。

第10部分  内部排序

总学时(单位：学时):6  讲课:4   实验（上机）:2 

第10.1 插入排序

第10.2 交换排序

第10.3 选择排序

第10.4 归并排序

第10.5 基数排序具体内容:

1）掌握插入排序算法。

2）掌握交换排序排序算法。

3）掌握选择排序算法。

4）掌握归并排序算法。

5）掌握基数排序算法。

重  点：

排序算法。

实验（上机）：

   查找、排序算法实现。

习  题: 

排序各种算法的实现等。