《数据结构》教学大纲

教学大纲

一、课程的性质、地位和任务

    该课程为核心课程。是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。本课程的任务是:在基础方面,要求学生掌握常用数据结构的基本概念及其不同的实现方法;在技能方面,通过系统学习能够在不同存储结构上实现不同的运算,并对算法设计的方式和技巧有所体会。

二、课程教学的基本要求

1、理论知识方面:要求学生掌握常用数据结构的基本概念及其不同的实现方法。
2、实验技能方面:通过系统学习能够在不同存储结构上实现不同的运算,并对算法设计的方式和技巧有所体会。

三、理论教学内容及学时分配(60学时)


第一章     概论         学时数:4

教学目的:

本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义,要求了解本章介绍的各种基本概念和术语,掌握算法描述和分析的方法。

教学重点和难点:

  • ⑴数据、数据元素、数据项;
  • ⑵逻辑结构和数据结构在概念上的联系与区别;
  • ⑶运算的概念;
  • ⑷存储结构及其三个组成部分;
  • ⑸抽象数据类型和数据抽象;
  • ⑹评价算法优劣的标准及方法。

主要教学内容及要求:

  • ⑴了解数据、数据元素和数据项的概念及其相互间的关系;
  • ⑵理解数据结构的逻辑结构、存储结构的联系与区别,以及在数据结构上施加的运算及其实现;
  • ⑶理解抽象数据类型的概念;
  • ⑷掌握进行简单算法分析的方法。

第二章    线性表        学时数:6

教学目的:

本章目的是介绍线性表的逻辑结构和各种存储表示方法,以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上,能够针对具体应用问题的要求和性质,选择合适的存储结构设计出相应的有效算法,解决与线性表相关的实际问题。

教学重点和难点:

  • ⑴线性表的定义及逻辑上的特点;
  • ⑵顺序表上插入、删除和定位运算的实现;
  • ⑶单链表的结构特点及类型说明;
  • ⑷头指针和头结点的作用及区别;
  • ⑸指针操作;
  • ⑹定位、删除、插入运算在单链表上的实现;
  • ⑺循环链表、双链表的结构特点;
  • ⑻循环链表、双链表上删除与插入运算的实现。

主要教学内容及要求:

  • ⑴理解线性表的定义及其运算;
  • ⑵理解顺序表和链表的定义、组织形式、结构特征和类型说明;
  • ⑶掌握在这两种表上实现的插入、删除和按值查找的算法;
  • ⑷了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。

第三章    栈和队列        学时数:6

教学目的:

本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上,知道在什么样的情况下能够使用栈或队列。

教学重点和难点:

  • ⑴栈的定义及逻辑特点;
  • ⑵栈上的基本运算;
  • ⑶栈的顺序存储结构及运算实现;
  • ⑷栈的链式存储结构;
  • ⑸入栈、出栈等运算在链栈上的实现;
  • ⑹队列的定义及逻辑特点;
  • ⑺队列上的基本运算;
  • ⑻队列的顺序存储结构及其上的运算实现;
  • ⑼队列的链式存储结构;
  • ⑽入队、出队等运算在链队列上的实现。

主要教学内容及要求:

  • ⑴理解栈的定义、特征及在其上所定义的基本运算;
  • ⑵掌握在两种存储结构上对栈所施加的基本运算的实现;
  • ⑶理解队列的定义、特征及在其上所定义的基本运算;
  • ⑷掌握在两种存储结构上对队列所施加的基本运算的实现。

第四章    串        学时数:4

教学目的:

本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。

教学重点和难点:

  • ⑴串的基本概念、基本运算;
  • ⑵串的两种存储方式;
  • ⑶串的模式匹配算法。

主要教学内容及要求:

  • ⑴了解串的定义;
  • ⑵理解和领会串的存储方式;
  • ⑶掌握常用的串运算。

第五章    数组、特殊矩阵和广义表        学时数:4

教学目的:

本章目的是介绍多维数组的逻辑结构特征及其存储方式,特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念,要求学生熟悉这些内容。

教学重点和难点:

  • ⑴多维数组的逻辑结构;
  • ⑵多维数组的两种顺序存储方式;
  • ⑶计算给定元素在存储区中的地址;
  • ⑷对称矩阵、三角矩阵的压缩存储方式;
  • ⑸计算给定元素在存储区中的地址;
  • ⑹稀疏矩阵的三元组表表示方法。

主要教学内容及要求:

  • ⑴理解多维数组的结构特点和在内存中的两种顺序存储方式;
  • ⑵理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算;
  • ⑶掌握稀疏矩阵的压缩方式和简单运算;
  • ⑷了解广义表的定义和基本运算。

第六章    树和二叉树        学时数:12

教学目的:

本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化,树的定义、存储结构、遍历、树和森林与二叉树的转换,哈夫曼树及哈夫曼编码等内容。

教学重点和难点:

  • ⑴二叉树的定义、逻辑特点及五种基本形态;
  • ⑵二叉树的五个性质;
  • ⑶在二叉树上定义的基本运算;
  • ⑷二叉树的链式存储结构及其类型说明;
  • ⑸二叉树的顺序存储结构及其类型说明;
  • ⑹二叉树链式存储结构的组织方式;
  • ⑺二叉树的三种遍历方法及其算法;
  • ⑻以遍历为基础在二叉树上实现的几种运算;
  • ⑼哈夫曼树和哈夫曼算法。

主要教学内容及要求:

  • ⑴深刻理解二叉树和树的定义、性质及其存储方法;
  • ⑵熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义;
  • ⑶理解并掌握二叉树的三种遍历算法;
  • ⑷掌握二叉树的线索化方法;
  • ⑸熟练掌握二叉树的遍历方法解决相关的应用问题。
  • ⑹熟练掌握森林与二叉树间的相互转换;
  • ⑺理解树和森林的遍历;
  • ⑻了解树的简单应用。

第七章    图        学时数:8

教学目的:

本章目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。

教学重点和难点:

  • ⑴图的定义、术语及其含义;
  • ⑵各种图的邻接矩阵表示法及其类型说明;
  • ⑶图的按深度优先搜索遍历方法和按广度优先搜索遍历方法;
  • ⑷生成树和最小生成树的概念;
  • ⑸由Prim算法思想构造最小生成树按Prim算法思想;
  • ⑹拓扑序列和拓扑排序的概念;
  • ⑺拓扑排序的算法思想;
  • ⑻关键路径的算法思想;
  • ⑼最短路径的算法思想。

主要教学内容及要求:

  • ⑴理解图的基本概念及术语;
  • ⑵掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法;
  • ⑶熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤,并能列出在两种存储结构上按上述两种遍历算法得到的序列;
  • ⑷理解最小生成树的概念,能按Prim算法构造最小生成树;
  • ⑸理解并掌握拓扑排序、关键路径、最短路径的算法思想。

第八章    查找        学时数:8

教学目的:

本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。

教学重点和难点:

  • ⑴查找表的基本概念及查找原理;
  • ⑵查找表的顺序存储结构、顺序表及其类型说明;
  • ⑶查找运算在查找表和有序表上的实现;
  • ⑷二叉排序树的定义、性质及各结点间的键值关系;
  • ⑸二叉排序树的查找算法和基本思想;
  • ⑹平衡二叉排序树的概念;
  • ⑺B-树和B+树的概念;
  • ⑻散列表及散列存储和散列查找的基本思想;
  • ⑼各种散列表的组织、解决冲突的方法;
  • ⑽在散列表上实现查找、插入和删除运算的算法。

主要教学内容及要求:

  • ⑴了解查找的基本思想及查找成功和不成功的概念;
  • ⑵掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法,并能求出相应的平均查找长度;
  • ⑶理解并掌握二叉排序树、平衡二叉树B-树的各种算法。

第九章    排序        学时数:8

教学目的:

本章目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。

教学重点和难点:

  • ⑴排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别;
  • ⑵插入排序的基本思想、基本步骤和算法;
  • ⑶冒泡排序的基本思想、基本步骤、算法和算法分析;
  • ⑷快速排序的基本思想、基本步骤和算法;
  • ⑸直接选择排序的基本思想、基本步骤、算法和算法分析;
  • ⑹堆排序的基本思想、基本步骤和算法;
  • ⑺归并排序的思想;
  • ⑻两个有序文件合并的方法和算法;
  • ⑼二路归并排序的算法和时空性能。

主要教学内容及要求:

  • ⑴理解排序的基本思想和基本概念;
  • ⑵理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析;
  • ⑶了解外排序的定义和基本方法。

四、实验教学内容及学时分配 (20学时)

序号 实验名称 学时 类型 实验要求
1 线性表 4 综合性 必做
2 栈、队列与递归算法设计 4 基础性 必做
3 串及其应用 4 综合性 必做
4 树、图及其应用 4 综合性 必做
5 查找和排序 4 综合性 必做

五、考试方法

考试方式为闭卷、笔试。总成绩计算时办法:平时成绩占30%,期末考试成绩占70%

六、使用教材

1、选用教材:

  • (1)理论课教材:数据结构,严蔚敏 吴伟民编著,清华大学出版社,2010
  • (2)实验课教材:数据结构习题解答与实验指导,罗文劼 王苗 石强编著,中国铁道出版社,2008

2、参考书:

  • (1)数据结构. 黄刘生 唐策善 著. 中国科学技术大学出版社,2009
  • (2)数据结构. 刘大有 著. 高等教育出版社,2002
  • (3)数据结构(面向对象语言描述). 朱振元等 著. 清华大学出版社,2004
  • (4)数据结构(C语言版)实践教程. 胡元义等著. 西安电子科技大学出版社,2008

3、推荐网站:

(1)河南农业大学精品课程展示