数据结构课程的知识体系和教学实践

《数据结构课程的知识体系和教学实践》由会员分享，可在线阅读，更多相关《数据结构课程的知识体系和教学实践（5页珍藏版）》请在金锄头文库上搜索。

1、Teaching and Research 教学与研究 计算机教育 2004.2/3 第 89 页 数据结构课程的知识体系和教学实践数据结构课程的知识体系和教学实践 张铭 许卓群 杨冬青 唐世渭/文 一、数据结构知识体系一、数据结构知识体系 计算机科学已经深入应用到各个领域， 不仅有效地解决了各种工程和科学计算中的数值 计算问题，而且也有效地解决了许多文本处理、信息检索、数据库管理、图像识别、人工智 能等非数值的数据处理问题。数据结构有助于程序员更有效地组织数据、设计高效的算法、 完成高质量的程序以满足错综复杂的实际需要。 数据结构是计算机学科的重要分支研究领域。 数据结构和算法在计算机学科中

2、的地位十 分重要， 其他计算机科学领域及有关的应用软件都要使用到各种数据结构。 数据结构是算法 分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专 业基础课和专业课程的先行课程。 语言编译要使用栈、 散列表及语法树； 操作系统中用队列、 存储管理表及目录树等；数据库系统运用线性表，多链表及索引树等进行数据管理；而在人 工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索 树及各种有向图等等。 美国 IEEE 和 ACM 的教学计划 CC2001 把算法与数据结构列入计算机以及信息技 术相关学科专业的本科必修基础课程。在我国， 数据结构已

3、经作为理工科非计算机专业 必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构都非常重视，对 于从事计算机科学及其应用的科技工作者来说，数据结构更是必须透彻地掌握的重要基础。 1数据的逻辑结构、存储结构和运算数据的逻辑结构、存储结构和运算 从字面上来看，数据结构就是指数据间的相互关系。具体到计算机环境，谈到任何一 种结构时，都自然地联系着作用在这种类型的数据上的运算（即函数） ，为了在计算机上执 行这些运算，我们有必要把这些数据以某种方式存储在计算机中。因此，我们可以认为，所 谓数据结构， 就是由某种逻辑关系组织起来的一批数据， 按一定的存储方法被存储于计算机 中，并在这些数据上

4、定义了一个运算的集合。也就是说，数据结构具有三个方面：数据的逻 辑结构、数据的存储结构和数据的运算。 常见逻辑关系有：线性结构、树形结构、图结构和文件结构。其中，线性结构是最简 单的数据结构，例如，程序设计语言中往往都会介绍的线性表（包括数组和链表） 、栈、队 列、向量、字符串等。其中，字符串就是每个结点都是单个字符的线性表。实际上多维数组 和广义表也是线性结构的推广。另外，文件其本质也是线性结构，不过由于存储在外存中， 对文件数据的访问速度非常慢， 因此， 仔细研究文件结构和基于文件的外排序也是很有必要 的。二叉树和树是非常重要的数据结构，其应用十分灵活而广泛。二叉树可以看作是树的特 例。例

5、如，语言编译中要用到语法树，操作系统有目录树，数据库系统需要用索引树等进行 数据管理，而在人工智能领域，需要用到搜索树等。许多真实世界的问题都可以图来抽象地 定义。例如，一张交通图可以用数据结构的图来形象化地表示：用结点表示城市，用边表示 连接城市的高速公路；Web 网页的关系也可以表示为图：Web 网页作为结点，网页之间的 链接作为边。图是一种最通用的逻辑结构，实际上，图 树 二叉树 线性表。 常见的存储方法有：顺序方法、链接方法、索引方法、散列方法。其中，索引存储又 分为线性和树形两种。文件结构的索引则往往用树形结构。 对于一种数据结构，往往需要定义一些运算。例如，建立数据结构、清除数据结

6、构、Teaching and Research 教学与研究 计算机教育 2004.2/3 第 90 页 插入一个新数据元素、删除某个数据元素、修改某个数据元素、排序、检索等。作为最常用 的算法，排序和检索历来是数据结构讨论中的重点问题。排序算法最能够体现算法的魅力， 它对算法速度要求非常高， 其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录 交换次数，以提高排序速度。可以证明所有基于比较的排序算法的时间代价是(nlog n)， 这也是排序问题的时间代价；而外排序则考虑外存的特性，尽量减少访外操作，以提高排序 速度。检索则考虑怎样提高检索速度，这往往是与存储方法有关的。例如，我们可以利用

7、索 引存储来加快检索。散列表、B 树和 B+树等高效的数据结构都具有极好的检索性能。 2算法的效率问题算法的效率问题 每一种数据结构与其相关的算法都有时间、空间开销和效率等问题。每当面临一个新 的设计问题时，设计者都应该要权衡时间空间开销，设计出更有效的数据结构和算法，以适 应问题的需要。 基本问题包括： 对于给定的一类问题， 最好的算法是什么？需要多少存储空间和时间？ 空间与时间的折衷方案是什么？存取数据最好的方法是什么？最好算法的最坏情况是什 么？平均来说， 算法的运行好到何种程度？算法一般化到何种程度即什么类型的问题可 以用类似的方法处理？ 这就涉及到算法分析技术，许多数据结构教材都揉合

8、了一些基本的算法分析技术，这 有助于读者根据问题的性质选择合理的数据结构，并对时间空间复杂性进行必要的控制。 3抽象数据类型抽象数据类型 事实上，数据结构的三个侧面，以数据的逻辑结构和数据的运算定义更为重要。因为 很多时候人们并不关心数据的存储结构和运算的具体实现。1983 年 Aho 等人把数据结构的 存储与实现细节剥离，定义了抽象数据类型（简称“ADT” ）的概念。抽象数据类型是定义 了一组运算的数学模型。例如栈结构，栈中元素的数学特性(即逻辑结构)表现为线性表，它 们是有序的；栈的主要运算是进栈(push)、出栈(pop)、判栈空(isEmpty)等。这里我们并不涉 及栈的存储方式以及栈

9、中元素的类型等。 这种抽象的数据类型可以在较高级的算法中直接引 用， 而不用考虑它的实现细节。 这就使得设计者可以在不同的设计阶段采用不同的抽象数据 类型作为设计的基础， 在适当的抽象层次上考虑程序的结构和算法， 从而很好地支持了逻辑 设计和物理实现的分离，支持封装和信息隐蔽。 大多数教材都是以数据的逻辑结构为主线，顺序介绍线性结构、树形结构、图结构和文 件结构。在介绍每种数据结构时，再讨论其存储结构以及相关的算法。例如对于线性表，如 果考虑到存储，可以分为数组和链表；考虑到运算的特殊性，则可以分为向量、栈和队列。 对于一些比较重要的算法，再列出单独的章节来讨论，例如排序、检索、索引、存储管理

10、等。 二、数据结构的教学目的二、数据结构的教学目的 Peter JDenning 等人认为，计算机学科分为理论、抽象、设计这三个形态。我们把数 据结构课程所涉及的主要方面整理为： 1. 理论理论 (1) 算法的数学基础。例如，有关图论、组合论等，特别是递归、递推、归纳等分析 方法。 (2) 算法的时间和空间度量。 2抽象抽象 (1) 排序、检索等重要问题类的有效算法，以及最好、最差和一般性能的分析比较。 (2) 重要数据结构技术，例如分治法(二分检索、快速排序、归并排序)、贪心算法 （Huffman 编码、Prim 算法、Kruskal 算法、Dijstra 算法） 、动态规划（Prim 算法

11、、Teaching and Research 教学与研究 计算机教育 2004.2/3 第 91 页 Dijstra 算法、Floyd 算法、最佳二叉搜索树） 、栈的引用（深度优先周游） 、队列的 应用（广度优先周游） 。 3设计设计 (1) 掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法及其主 要的算法，例如线性结构（包括一维数组、链表、栈、队列、字符串等） 、二叉树、 树、图、文件； (2) 排序、检索、索引等重要问题类的算法的选择、实现和测试。例如，各种排序方 法的实验时间比较，散列、倒排索引、B 树等应用。 (3) 存储管理的实现与测试。例如可利用空间表、无用单元收集

12、、伙伴系统。 数据结构这门课程不仅仅要让学生掌握那些链表、树、图是如何实现的。设置这门课程 有三个目的：第一个目的是让学生懂得“数据结构算法程序” ；第二个目的是培养数据 抽象的能力； 第三个目的是使得学生把数据结构和算法理论与编程实践相结合， 能够在实际 的工程实践中灵活地予以应用。 在达到前两个目的时， 学生就基本具备了解决现实未知问题的能力， 再辅以必要的综合 上机项目训练，可以达到第三个目的。 总而言之，通过数据结构课程的教学，学生需要掌握以下四个方面的知识和能力： （1） 掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法、主要的算法，例 如线性结构、二叉树、树、图、文

13、件； （2）掌握并简单应用常用的排序、检索和索引算法和 方法； （3）掌握基本的算法设计和分析技术，并对自己设计的数据结构和算法进行简单的分 析； （4）在进行程序设计、调试、测试的课程项目训练（即上机实习训练）过程中，要求学 生综合应用所学到的数据结构和算法知识， 学会分析研究数据对象的特性， 以便选择合适的 数据结构和存贮结构以及相应的算法， 合理地组织数据、 有效地表示数据、 有效地处理数据， 书写的程序结构清楚、正确易读，提高程序设计的质量。 三、数据结构教材编写思路三、数据结构教材编写思路 1987 年高教社出版的许卓群等编写的数据结构被很多高校的计算机系采用为数据 结构课程主教材。

14、该书已经连续再印刷近二十次，并于 1992 获得教育部教材优秀奖和国家 教材优秀奖。在多年的使用过程中，国内很多读者建议更新部分内容，补充一些电子教案， 并希望在算法的伪代码编码风格方面，由类 PASCAL 改为类 C+语言。 我们采纳这些建议，由北京大学信息科学技术学院许卓群、杨冬青、唐世渭、张铭这四 位多年从事数据结构教学和研究的教员一起修订数据结构教材。作者围绕中国计算 机科学与技术学科教程 CCC2002 和美国 IEEE 和 ACM 的教学计划 CC2001 所规定的基本知 识点，参考国内外的最新数据结构教材，编写第二版数据结构 。 1第二版的主要修订原则第二版的主要修订原则 ? 基

15、本内容和知识点不做大的变动，不增加难度。 ? 考虑采用最广为程序员所使用的 C+语言作为算法描述语言， 从而使得抽象数据类 型(ADT)的概念得到更自然的体现，更本质地体现数据结构的思想，而且所定义的 数据结构类能够方便地被重用。 ? 为了保证教材的易读性，尽量回避 C/C+中比较麻烦的内容，例如 C 的指针的指 针的指针等折磨人的东西，C+的类的继承、虚函数等。 ? 使用参数化的模板（template） ，从而提高算法中数据类型的通用性，支持高效的代 码重用。在后面的章节中，尽量使用 STL (Standard Template Library，标准 C+类 库)所提供的栈、队列等基本数据结

16、构。 Teaching and Research 教学与研究 计算机教育 2004.2/3 第 92 页 ? 删除原来的逆转链周游二叉树、Robson 周游算法、Siklossy 周游算法、关键路径等 内容。 ? 增加了 Patricia 树、伸展树等复杂树结构，k-d 树、PR 四分树、R*树等空间数据结 构。 ? 每一章中都增补了比较多的综合上机实习题（即项目实习） 。 ? 为了配合教材的发行， 我们将编写概念清晰、 内容充实的多媒体演示讲稿以及用标 准 C+模板编写的可执行的源程序代码。 出版社可以考虑带光盘发行， 或提供网站。 2第二版新大纲的考虑第二版新大纲的考虑 第一版完全按照逻辑结构的角度来安排内容。每一种数据结构都有一些比较复杂的算 法。作者在给辅修数据结构的外系学生使用该教材时，只能选择一些比较浅显的内容，学生 们感觉跳跃性比较大。 而在使用该教材给计算机专业的学生讲课时