常用下载   /  加入收藏  
 
 
    欢迎访问!今天是2018年05月21日  星期一  四月初七      
更多»公告
    当前位置: 首页 » 本科生教育 » 教学大纲 » 信息与计算科学 »  《数据结构》教学大纲
 上一篇:《大学物理F》教学大纲
 下一篇:《数值分析》教学大纲
《数据结构》教学大纲
作者:管理员  来源:本站原创  发布时间:2016年5月11日  点击次数:462

《数据结构》教学大纲

Data Structure

课程编码:09A03030             学分:3.5           课程类别:专业课(必修)

计划学时:64          其中讲课: 48      实验或实践:        上机:16

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

推荐教材:严蔚敏、吴伟民. 《数据结构》(C语言版)[M]. 北京: 清华大学出版社,2009.3

参考书目:1. 严蔚敏. 《数据结构题集》(C语言版)[M]. 北京: 清华大学出版社,2009.3

2.(美)维斯著,冯舜玺译. 数据结构与算法分析:C语言描述[M]. 北京: 机械工业出版社,

2004.1

3. 李春葆. 数据结构教程[M], 4. 北京: 清华大学出版社, 2015.6

 

课程的教学目的与任务

本课程是信息与计算科学专业的必修课。通过本课程的学习,培养学生设计算法、开发程序的能力,使学生能够根据实际问题的需要,选择适当的数据结构及设计出相应的算法;通过上机实验,进一步锻炼学生的动手能力,培养学生分析和解决实际问题的能力。本课程首先从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;然后讨论了查找和排序的各种实现方法及其综合分析比较。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

 

课程的基本要求

1. 要求学生掌握基本数据结构的逻辑特点、存储方法、基本运算等。

2. 要求学生掌握常用的查找与排序的原理与技术方法。

3. 要求学生能够对具体问题选择适当的结构,并编写出结构清晰的程序。

 

各章节授课内容、教学方法及学时分配建议(含课内实验)

 

第一章:绪论                                      建议学时:2

[教学目的与要求] 了解数据结构的研究对象,理解数据结构有关概念的含义,掌握数据结构的分类及表示。熟悉类c语言的书写规范,理解算法的重要特性及算法设计的要求,掌握计算语句频度和估算时间复杂度的方法。

[教学重点与难点]  数据结构、逻辑结构、存储结构、抽象数据类型的表示与实现、估算时间复杂度的方法。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 什么是数据结构

一、数值问题与非数值问题

二、《数据结构》的发展史

第二节 基本概念和术语

一、数据、数据元素、数据对象、数据结构

二、数据结构的形式定义

三、逻辑结构、存储结构

四、数据类型、抽象数据类型

第三节 抽象数据类型的表示与实现

一、c语言

二、抽象数据类型表示与实现示例

第四节 算法和算法分析

一、算法

二、算法设计的要求

三、算法效率的度量

四、算法的存储空间需求

  第二章:线性表                                      建议学时:6+4(上机)

[教学目的与要求] 了解线性表逻辑结构的特征;重点掌握线性表的顺序存储结构和链式存储结构,它们如何表达线性表中数据元素之间的结构关系;如何用类C语言描述它们的类型定义;通过上机实验掌握线性表的顺序存储结构及基本操作算法、线性表的单链存储结构及基本操作算法。能够从时间复杂度的角度,比较线性表两类存储结构的不同特点及适用场合。

[教学重点与难点] 线性表逻辑结构的特征,线性表的顺序存储结构及基本操作算法。线性表的单链存储结构及基本操作算法。线性表的双向链表存储结构及基本操作算法。

[      ] 课堂讲授与上机实验相结合。

[      ]

第一节 线性表的类型定义

一、线性表的概念

二、抽象数据类型线性表List的定义

第二节 线性表的顺序表示和实现

一、线性表的顺序存储结构

二、顺序表的类型定义

三、顺序表的基本操作算法

四、上机实验项目1:完成顺序表的基本操作

第三节 线性表的链式表示和实现

一、线性链表

二、循环链表

三、双向链表

四、上机实验项目2:完成单链表的基本操作

第四节 一元多项式的表示及相加

一、抽象数据类型一元多项式的定义

二、抽象数据类型一元多项式的实现

三、一元多项式的相加

第三章:栈和队列                                       建议学时:4+4(上机)

[教学目的与要求] 理解掌握栈与队列的结构特征和操作特点;掌握栈与队列的顺序存储结构和链式存储结构,以及如何用C语言描述它们的类型定义;通过上机实验掌握顺序栈与链队列的基本操作。理解栈的后进先出的特点及在程序设计中的应用。掌握循环队列的入队、出队算法以及循环队列队空、队满的判别条件。

[教学重点与难点] 栈与队列的逻辑结构的特征,栈与队列的顺序存储结构及基本操作算法。栈在程序设计中的应用。队列的链式存储结构及基本操作算法。循环队列的队空和队满的判定方法。

[      ] 课堂讲授与上机实验相结合。

[      ]

第一节 栈

一、抽象数据类型栈的定义

二、栈的表示和实现

第二节 栈的应用举例

一、数制转换

二、括号匹配的检验

三、行编辑程序

四、表达式求值

五、上机实验项目3:完成顺序栈的基本操作

第三节 队列

一、抽象数据类型队列的定义

二、链队列

三、循环队列

四、上机实验项目4:完成链队列的基本操作

第四章:串                                      建议学时:2

[教学目的与要求] 了解串的基本操作,了解利用基本操作实现串的其它操作的方法;掌握在串的堆分配存储结构下,串的基本操作算法。

[教学重点与难点] 串的堆分配存储结构。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 串类型的定义

一、什么是串、串的有关术语

二、串的抽象数据类型定义

第二节 串的表示和实现

一、定长顺序存储表示

二、堆分配存储表示

第三节 串的模式匹配算法

一、求子串位置的定位函数

二、模式匹配的一种改进算法

第五章:数组和广义表                                     建议学时:6

[教学目的与要求] 了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法,学会对非空广义表进行分解的分析方法。

[教学重点与难点] 数组的顺序存储结构;数组在以行为主序的方式存储时,数组元素地址的计算方法;矩阵的两种压缩存储方法。广义表的逻辑结构;头尾链表存储广义表的方法。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 数组的定义

一、什么是数组

二、数组的抽象数据类型定义

第二节 数组的顺序表示和实现

一、以行为主序的方式数组的顺序存储结构

二、以列为主序的方式数组的顺序存储结构

第三节 矩阵的压缩存储

一、特殊矩阵

二、稀疏矩阵

第四节 广义表的定义

一、广义表的概念

二、广义表的抽象数据类型定义

第五节 广义表的存储结构

一、设定结点的结构

二、广义表的头尾链表存储表示

第六章:树和二叉树                                   建议学时:10+2(上机)

[教学目的与要求] 理解树的逻辑结构与基本概念,掌握二叉树的结构特征,熟悉二叉树的各种存储结构,掌握二叉链表存储结构。掌握各种遍历策略的递归算法,能灵活运用遍历算法实现二叉树的其他操作。通过上机实验掌握二叉树的创建与遍历操作。熟悉树的各种存储结构及其特点,掌握树和二叉树的转换方法,掌握树的遍历方法;了解哈夫曼树的特性,掌握构造哈夫曼树和哈夫曼编码的方法。

[教学重点与难点] 二叉树的结构特征;二叉链表存储结构。二叉树遍历的递归算法。树与二叉树的转换方法;树的遍历;构造哈夫曼树和哈夫曼编码的方法。

[      ] 课堂讲授与上机实验相结合。

[      ]

第一节 树的定义和基本术语

一、树的概念、树的表示、树的基本术语

二、树的抽象数据类型定义

第二节 二叉树

一、二叉树的定义

二、二叉树的性质

三、二叉树的存储结构

第三节 遍历二叉树和线索二叉树

一、遍历二叉树

二、线索二叉树

三、上机实验项目5:完成二叉链表存储结构的二叉树的创建与遍历操作

第四节 树和森林

一、树的存储结构

二、森林与二叉树的转换

三、树和森林的遍历

第五节 赫夫曼树及其应用

一、赫夫曼树

二、赫夫曼编码

第七章:图                                         建议学时:10+2(上机)

[教学目的与要求] 理解图的基本概念,掌握图的邻接表与邻接矩阵两种存储结构。掌握图的深度优先与广度优先遍历算法。通过上机实验掌握邻接表存储结构的图的创建操作。理解有向无环图有关的概念,掌握关键路径的计算方法。

[教学重点与难点] 图的邻接表与邻接矩阵存储结构。图的深度优先与广度优先遍历。关键路径的计算方法。

[      ] 课堂讲授与上机实验相结合。

[      ]

第一节 图的定义和术语

一、图的概念、图的基本术语

二、图的抽象数据类型定义

第二节 图的存储结构

一、数组表示法

二、邻接表

三、十字链表

第三节 图的遍历

一、深度优先遍历

二、广度优先遍历

三、上机实验项目6:完成邻接表存储结构的图的创建操作

第四节 图的连通性问题

一、无向图的连通分量和生成树

二、有向图的强连通分量

三、最小生成树

第五节 有向无环图及其应用

一、拓扑排序

二、关键路径

第九章:查找                                         建议学时:4+2(上机)

[教学目的与要求] 理解查找有关概念,通过上机实验掌握顺序表和有序表的查找方法,掌握二叉排序树的查找方法。掌握哈希表的构造方法和查找方法。

[教学重点与难点] 顺序表和有序表的查找方法;二叉排序树的查找方法。哈希表的构造方法和查找方法。

[      ] 课堂讲授与上机实验相结合。

[      ]

第一节 静态查找表

一、顺序表的查找

二、有序表的查找

第二节 动态查找表

一、二叉排序树

二、平衡二叉树

三、B-树和B+

第三节 哈希表

一、什么是哈希表

二、哈希函数的构造方法

三、处理冲突的方法

四、哈希表的查找及其分析

五、上机实验项目7:完成折半查找等基本查找算法

第十章:内部排序                                       建议学时:4+2(上机)

[教学目的与要求] 理解排序的概念,通过上机实验掌握插入排序、交换排序的过程,理解稳定排序和不稳定排序的含义;掌握选择排序、归并排序的过程及其依据原则。

[教学重点与难点] 插入排序、交换排序、选择排序、归并排序的过程及其依据原则。

[      ] 课堂讲授与上机实验相结合。

[      ]

第一节 概述

一、排序的定义与分类

二、稳定排序

三、待排记录存储方式

第二节 插入排序

一、直接插入排序

二、其他插入排序

三、希尔排序

第三节 快速排序

一、交换排序的基本思想

二、快速排序

第四节 选择排序

一、简单选择排序

二、树形选择排序

三、堆排序

第五节 归并排序

一、归并排序的基本思想

二、2-路归并

第六节 基本内部排序方法的比较讨论

一、分析比较基本内部排序方法

二、上机实验项目8:完成插入排序等基本排序算法

 

 

 

 

                                            撰稿人:宋玉成   审核人:靳绍礼

 

 
» 上一篇:《大学物理F》教学大纲
» 下一篇:《数值分析》教学大纲
check_website_is_ok,made by zheng_guang_yu,Do not delete
 
Copyright 济南大学数学科学学院. All rights reserved.
地址:济南市市中区南辛庄西路336号济南大学西校区第七教学楼   邮编:250022   电话(传真):0531-82767313