数据结构教学大纲

《数据结构》教学大纲

执笔人：张力 审核人：周枫

课程名称：数据结构 Data Structure 专业： 计算机科学与技术 课程编码：

总学时： 80=64（授课）+16（上机）

选用教材：《数据结构》 唐策善 等编著 高等教育出版社 先行课程：《程序设计方法与C语言》、《离散数学》

一、 地位、任务及目的

本课程是各计算机类专业的核心课程，也是许多非计算机专业的必修课或选修课。它是设计和实现编译程序、操作系统、数据库系统以及其他系统程序和应用程序的重要基础。其主要的任务通过对计算机处理对象——数据的逻辑结构（关系）、存储结构（关系）及在数据这些结构(关系)上进行的各种操作的算法，在线性、非线性结构上的分析、讨论与研究，达到在利用计算机解决实际问题时，如何分析数据的逻辑结构、有效地选择和设计数据的存储结构及其在此基础上实现对数据运算的算法的目的。同时也达到增强学生软件设计及编程的能力的目的。

二、 基本内容及学时分配

（一） 教学内容

第一篇 概念 （ 4 学时） ? 教学内容

第1章 概论

1．1 数据结构的概念

1．2 数据结构学习的重要性 1．3算法分析

? 教学要求

本章从人当前面临用计算机解决实际问题的需求，引出用计算机解决实际问

题的基本过程，简要地介绍数据、数据结构等基本概念；阐述数据结构是包含数据的逻辑结构、数据的存储结构和实现数据的运算算法等三个方面的内容；简单讨论线性结构和非谈性结构的逻辑特征，数据存储的四种基本方法以及数据运算的涵义。同时引进了算法的概念及评价算法的方法，讲解如何分析程序的时间复杂度和空间复杂度的方法。要求学习这些内容和例子后，希望能对《数据结构》课程的基本实质具有初步的认识和理解。

第二篇 线性结构 12 学时 ? 教学内容

第2章 线性表 8学时

2.1线性表的逻辑结构

2.2线性表的顺序存储结构及其操作 2.3线性表的链式存储结构及其操作 2.4线性循环链表和双向链表 2.5多项式相加 2.6静态链表

? 教学要求

线性表是一种最基本、最常用的数据结构，本章要求介绍线性表的定义、运

算和各种存储结构的描述方法。重点讨论了线性表的两种存储结构——顺序表和链表，以及在这沟种存储结构上实现的基本运算。

顺序表是用数组实现的，链表是用指针或游标实现的，用指针来实现的链表，

因为它的结点空间是动态分配的，故称之为动态链表；用游标摸拟指针实现的链表，由于其结，点空间是静态分配的，所以称之为静态链表。这两种链表又可按链接形式的不同，区分为单链表、双链表和循环链表。

在实际应用中，对线性表采用哪种存储结构，要视实际问题的要求而定，主

要考虑求解算法的时间和空间的复杂度。因此，要求熟练掌握在顺序表和链表上实现的各种基本运算及其时间、空间特性。

? 教学内容

第3章 栈和队列 4 学时 3.1栈 3.2队列 ? 教学要求

栈和队列是两种常见的数据结构，它们都是运算受限的线性表。栈的插入和

删除均是在栈顶进行，它是后进先出的线性表；队列的插入在队尾，删除在队头，它是先进先出的线性表。在具有后进先出（或先进先出）特性的实际问题中，我们可以使用栈（或队列）这种数据结构来求解。

和线性表类似，依照存储表示的不同，栈有顺序栈和链栈之分，队列有顺序

队列和链队列两种，而实际中使用的顺序队列是循环队列。本章分别介绍顺序栈、循环队列和链队列的五种基本运算，对链栈则讨论了它的插入和删除运算，要求掌握。

另外，栈和队列“上溢”和“下溢”概念及其判别条件应重点领会，要求正

确判别栈或队列的空间满而产生的溢出，正确使用栈空或队列空来控制返回。

第三篇 非线性结构 28 学时

? 教学内容

第4章 树 12 学时 5.1树的基本概念 5.2二叉树 5.3遍历二叉树 5.4线索二叉树 5.5树和森林

5.6哈夫曼树及其应用

? 教学要求

树和二又树是一类具有层次或嵌套关系的非线性结构，被广泛地应用于计算

机领域，尤其是二叉树最重要、最常用。本章要求着重介绍了二又树的概念、性质和存储表示；二叉树的三种遍历操作；线索二叉树的有关概念和运算。同时介绍了树、森林与二叉树之间的转换；树的三种存储表示法；树和森林的遍历方法。最后讨论了最优二叉树（哈夫曼树）的概念及其应用。

这一章是本课程的重点之一，要求熟练掌握5.2、5.5各节的内容；熟悉树和

二叉树的定义和有关术语；理解和记住二又树的性质；熟练掌握二叉树的顺序存储和链式存储结构．遍历二又树是二叉树中各种运算的基础，能灵活运用各种次序的遍历算法,实现二叉树的其它运算。二又树的线索化，目的是加速遍历过程和有效利用存储空间，熟练掌握在中序线索树中，查找给定结点的中序前趋和后继的方法。并能掌握树和二叉树之间的转换方法，存储树的双亲链表法、孩子链表法和孩子兄弟链表法，最后，对树和森林的遍历、最优二叉树的特性要理解。 ? 教学内容

第5章 图 12 学时

6.1图的基本概念 6.2图的存储结构 6.3图的遍历 6.4图的连通性

6.5无向无环图及其应用 6.6有向无环图及其应用 6.7最短路径及其应用

? 教学要求

图是一种复杂的非线性结构，具有广泛的应用背景。本章要求介绍图的基本概念和两种常用的存储结构，对图的遍历、最小生成树、拓扑排序及关键路径、最短路径等问题做了较详细的讨论，给出了相应的求解算法，并理解它们。

相对而言之，图这一章内容较难，只要求理解本章所介绍的算法实质，掌握图的有关术语和存储表示，面对实际问题时，学会引用本章的有关内容。

第四篇 查找与排序 16 学时 ? 教学内容

第6章 查找 8 学时 8.1顺序表的查找 8.2二分查找 8.3分块查找 8.4树表查找

8.5 HASH查找技术

? 教学要求

查找和排序一样，是数据处理中经常使用的一种运算。关于线性表的查找，本章介绍须序查找、二分查找和分块查找三，种方法。若线性表是有序表，则二分查找是一种最快的查找法。关于树表的查找，介绍二叉排序树，AVL树B-树的方法，分别讨论了这三种树表的基本概念、插入和删除操作以及它们的查找过程。 上述方法都基子关键字比较进行的查找。而散列表方法则是直接计算出结点

的地址，介绍散列表的概念、散列函数和处理冲突的方法。叙述各种查找方法的平均查找长度。

要求能够灵活应用顺序查找，二分查找和分块查我的方法；熟练掌握二叉排

序树的构造方法和查找过程；了解AVL树和B-树的建树过程；熟练掌握散列表的建表方法及其查找过程；掌握各种查找的平均查找长度计算方法；学会根据实际问题的要求，选取合适的查找方法及其所需的存储结构。

? 教学内容

第7章 排序 8 学时 9.1插入排序 9.2交换排序 9.3选择排序 9.4两路合并排序 9.5基数排序

? 教学要求

排序是数据处理中经常运用的一种重要运算。要求介绍排序的概念和有关知

识。对插入排序、交换排序、选择排序、归并排序和分配排序等五类内部排序方法进行讨论，分别介绍了各种排序方法的基本思想、排序过程和实现算法；简要地分析了各种算法的时间复杂度和空间复杂度，在对比各种排序方法的基础上，提出供选择时的参考建议。最后，对外部排序作了简单介绍。

由于排序运算在计算机应用中所处的重要地位，建议深刻理解各种内部排序

法的基本思想和特点，熟悉内部排序法的排序过程，记住各种算法的时间复杂度分析结果及其分析方法，以便在实际应用中，根据实际问题的要求，选用合适的排序方法。

（二） 实践环节

《数据结构》实验大纲

一、上机实践环境要求：

基本微机硬件系统（80台）；

Windows 98 以上操作系统及VC++ 6.0语言环境。

二、上机实践题（16机时 注： *为选作）： 题目 目的 要求 机时 一、程序功能： 1.(菜单)主程序； 1.掌握线性表顺序2.表的建立及初始化； 存储结构的C语言3.表的数据插入； 描述 4.表的数据删除； 2.体会last域在算5.表的数据输出； 法实现所起的作用 二、实验报告： 3.理解合理的存储1.上机通过的程序（清单）； 结构设计与算法实2.分析程序的空间复杂度现的存在的关系 和插入和删除的时间复杂度； 1 线性表顺序存储运算的算法实现 2 3.说明last域在算法实现所起的作用； 4.总结合理的存储结构的设计与算法实现存在的关系。 一、程序功能： 1.掌握线性表链式1.(菜单)主程序； 存储结构的C语言2.链表的建立； 描述及运算算法的3.链表的数据插入； 实现； 4.链表的数据删除； 2.分析算法的空间5.链表的数据输出； 复杂度和插入和删二、实验报告 除的时间复杂度； 1.上机通过的程序（清单）； 3.总结比较线性表2.分析插入和删除的时间顺序存储存储与链复杂度； 式存储的各自特3.总结比较线性表顺序存点。 储存储与链式存储的各自特点。 一、程序功能： 1.(菜单)主程序； 2.多项式数据存储的建立； 3.两多项式相加； 4.多项式的数据输出； 二、实验报告 1.上机通过的程序（清单）； 2 线性表链式存储运算的算法实现 2 *3 单链表多项式加法算法实现 2 *4 约瑟夫问题的算法实现 结合实际问题掌握线性表链式存储结构的C语言描述及一、程序功能： 运算算法的实现。 1.(菜单)主程序； 2.建立数据存储； 3. ?????； 4.数据输出； 二、实验报告 1.上机通过的程序（清单）； 结合堆栈入栈出栈的特点解决实际问题。 利用栈入栈出栈的特点进行探索式程序设计解决实际问题。 利用队列原理设计打印杨辉三角算法思想。 2 5 中缀表达式转化为后缀表达式算法及后缀表达式计算算法的实现 同上 2 *6 背包问题 同上 2 *7 杨辉三角 同上 2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构教学大纲在线全文阅读。