核心课程教学实施方案-（科学型）

数据结构与算法课程教学实施方案

数据结构与算法课程教学实施方案

4.1总体描述

4.1.1 课程基本描述 ..................................................................... 错误！未定义书签。 4.1.2 课程的分层次教学基本定位和设计思路 ......................... 错误！未定义书签。 4.1.3 实施方案的写作安排 ......................................................... 错误！未定义书签。

4.2数据结构与算法教学实施方案（科学型）

4.2.1 基本描述 .......................................................................................................... - 2 - 4.2.2 内容大纲 .......................................................................................................... - 2 - 4.2.3 讲授提示 .......................................................................................................... - 6 - 4.2.4 基础实验内容和要求 .................................................................................... - 18 - 4.2.5 课程综合实验设计 ........................................................................................ - 27 - 4.2.6 考试基本要求和成绩评定建议 .................................................................... - 29 - 4.2.7 教材写作建议 ................................................................................................ - 30 -

4.3 数据结构与算法效字实施方案(工程型)

4.3.1基本描述 .............................................................................. 错误！未定义书签。 4.3.2内容大纲 .............................................................................. 错误！未定义书签。 4.3.3讲授提示 .............................................................................. 错误！未定义书签。 4.3.4 基础实验内容和要求 ......................................................... 错误！未定义书签。 4.3.5课程设计 .............................................................................. 错误！未定义书签。 4.3.6考试基本要求和成绩评定建议 .......................................... 错误！未定义书签。 4.3.7 教材写作建议 ..................................................................... 错误！未定义书签。

4.4 数据结构与算法教学实施方案（应用型）

4.4.1 基本描述 ........................................................................... 错误！未定义书签。 4.4.2 内容大纲 ........................................................................... 错误！未定义书签。 4.4.3 讲授提示 ........................................................................... 错误！未定义书签。 4.4.4 基础实验内容和要求 ....................................................... 错误！未定义书签。 4.4.5 课程设计 ............................................................................. 错误！未定义书签。 4.4.6 考试基本要求和成绩评定建议 ....................................... 错误！未定义书签。 4.4.7 教材写作建议 ................................................................... 错误！未定义书签。

第 - 1 - 页 共 31 页

数据结构与算法课程教学实施方案

4.2数据结构与算法教学实施方案（科学型）

科学型人才的基本要求是扎实的计算机基础理论和对核心技术的良好掌握，以及较强的创新意识和创新能力。培养学生从广度和深度上把握课程的知识体系，了解基本数据结构和经典算法，掌握理论、抽象和设计方法。注重实践能力和工程能力的培养，使得学生遵从软件开发的规范性，根据实际问题选择合适的数据模型，设计合适的算法，运用所学理论知识实现问题求解。

应该注意结合计算机科学技术的现代前沿研究课题，设计研究启发式教学案例，扩展学生知识体系，提供更多的讨论机会，进行更有挑战性的综合实习训练，培养主动学习、研究和创新意识，以实现“研究”特色，培养卓越的创新人才。

4.2.1 基本描述

面向科学型计算机人才的数据结构与算法课程的主要目的是使学生较

全面地理解数据结构的概念，掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。

课程以问题求解为主线，从问题抽象、数据抽象和算法抽象的角度来组织数据结构与算法的设计，知道学生建立数学模型，使用不同的数据结构，不同的算法分别去解决问题，最后去探讨各种数据结构和算法的优缺点，同时让学生学会如何根据实际问题来取舍数据结构和算法，并且在时间复杂度和空间复杂度之间进行平衡。通过学习，使学生能够提高利用计算机解决实际问题的能力。

4.2.2 内容大纲

本大纲定位于科学型的数据域算法课程，因此加大了课程的深度和广度。除了基础篇、数据结构篇和运算篇三大知识体系，还增加了高级数据结构篇。为了区分，在表4.1中将数据结构篇称为基础数据结构篇。

多维数组、广义表、字符树、平衡二叉树（AVL）等数据结构，在很多教材中是在线性表、树结构等章节予以介绍。在多年的教学实践中，我们发现这些内容作为扩展内容更好。这样做可以使前面的内容更加经典和紧凑，讲究后就可以布置课程的期末综合实习，最后可以将高级数据结构的内容根据学生的接受程度安排讲座，不用安排上机训练。

Patricia树、后缀树是目前热点研究的字符树、伸展树、红黑树是比平衡二叉树（AVL）更为实用的二叉搜索树（BST），应该向学生介绍这些学科前沿的数据结构。

1. 知识矩阵

科学型数据结构与算法课程的知识单元及掌握程度如表4.1所示。

表4.1 数据结构与算法课程的知识单元（科学型）

知识篇 知识领域 知识点 二级知识点 第 - 2 - 页 共 31 页

掌握程度 数据结构与算法课程教学实施方案

数据 数据结构定义 基本数据类型（整型、实型、布尔型、字符型、指针类型），复合数据类型 逻辑结构，存储结构，运算 信息封装，数学模型 通用性，有效性，确定性，有穷性 穷举法，回潮法。分治法，递归法和贪心法 大O表示法，渐进分析，最好、最差和平均时间复杂度，时间和空间的折中 大Ω，大θ表示法 掌握 数据结构 抽象数据类型 算法概念 熟练掌握 掌握 掌握 了解 基础篇 算法设计 算法与问题求解 掌握 算法分析 了解 掌握 掌握 熟练掌握 了解 掌握 问题求解 线性表 问题抽象，数据结构抽象，算法抽象，数据结构和算法设计，系统实现 向量（数组），链表，单链表，双链表，循环表 顺序栈，链接栈，栈的应用（表达式求值和转换），用栈来生成序列 利用栈进行递归到非递归的转换 栈 线性结构 队列 顺序队列，链接队列，循环队列的实现，利用队列进行问题求解 字符串的存储，字符串运算，字符串的快速模式匹配算法 二叉树递归定义，结点，根，子结点，父结点，分支结点，叶结点，边，路径，深度，高度，层数 前序周游，中序周游，后序周游，广度优先周游 基础数据结构篇 字符串 掌握 二叉树的概念 掌握 树形结构 熟练掌握 初步掌握 掌握 了解 掌握程度 二叉树周游 非递归深度优先周游 二叉链表，三叉链表 二叉树存储 穿线二叉树 知识篇 基础数据结构 知识领域 知识点 二叉树应用 二级知识点 二叉搜索树（BST）、BST结点的插入与删除，Huffman树（贪心法构造）、利用Huffman树进行编码解码，堆 树形结构 熟练掌握 第 - 3 - 页 共 31 页

数据结构与算法课程教学实施方案

优先队列 树与森林的递归定义，结点和边的概念，森林与二叉树的对应 K叉树 森林的周游 树的链式存储 树的顺序存储 先根周游、后根周游，广度优先周游 二叉链表，父指针表示法，等价类和并查算法的应用 带右链的先根次序表示，带双标记的先根次序表示，带度数的后根次序表示，带双标记的层次次序表示 顶点，边，权，入度，出度，有向图，无向图，稀疏图，密集图，子图，路径，简单路径，简单回路，无环图，有向无环图（DAG），连通图，强连通，网络 相邻矩阵，邻接表（节点表一边表） 图的深度优先周游，图的宽度优先周游，图的生成树，生成树林 根据入度进行选择的拓扑排序 拓扑排序 逆深度优先周游的拓扑排序，关键路径 最小生成树 最短路径 Prim算法（贪心法），Kruskal算法（贪心法） 了解 掌握 了解 熟练掌握 树与森林 掌握 掌握 图的概念 掌握 图的存储方法 图的周游 熟练掌握 图 熟练掌握 掌握 初步掌握 掌握 Dijkatra算法（贪心法），Floyd算法（贪心法） 数据记录，关键码，排序码，正序，逆序，稳定性 直接插入排序，Shell排序 二级知识点 冒泡排序，快速排序（分治法） 直接选择排序，堆排序 二路归并（分治法） 桶排序，链式基数排序 第 - 4 - 页 共 31 页

熟练掌握 基本概念 运算篇 内排序 插入排序 知识篇 知识领域 知识点 交换排序 选择排序 运算篇 内排序 归并排序 分配排序 掌握 熟练掌握 掌握程度 熟练掌握 掌握 掌握 熟练掌握 数据结构与算法课程教学实施方案

地址排序 数组整理 时间代价；记录的比较和移动次数 初步掌握 排序算法分析 空间代价：辅助数据空间大小 排序问题的下限 掌握 文件组织 外排序 算法设计 检索基本概念 二分法检索 分块检索 检索 集合检索 主存储器，外存储器，缓冲区，索引文件，顺串 置换选择排序，多路归并（赢者树、败方树，最佳归并树，多路归并的读盘和写盘次数） 查找某个结点的比较次数，平均检索长度 掌握 初步掌握 二分法检索 索引表，二级检索 位向量运算 散列表，同义词，碰撞，堆积二分法检索的判定树散列函数（除余法、平方取中法、折叠法）冲突处理方法（分离同义词子表、线性探测、双散列函数）散列算法（查找、插入、删除，对墓碑的处理） 顺序文件，散列文件（桶、基桶、溢出桶），倒排文件（属性、辅码），索引文件 多分树 初步掌握 熟练掌握 散列检索 概念 静态索引结构 位索引 知识篇 知识领域 知识点 B树/B+树动态索引结构 索引技术 了解 位图索引、签名文件 二级知识点 B树/B+树的定义，B树/B+树的插入删除操作，读盘和写盘次数分析，索引效率分析 VSAM 多维数组的顺序存储，特殊矩阵（三角矩阵、对称矩阵、对角矩阵、稀疏矩阵） 了解 掌握程度 掌握 掌握 了解 初步掌握 运算篇 索引技术 ★高级数高级线性结据结构篇 构 多维数组 第 - 5 - 页 共 31 页

数据结构与算法课程教学实施方案

冲突解决技术可分为两大类，即开散列方法和闭方法。两者的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，闭散列把发生 冲突的关键码存储在表中另一个槽内。闭散列方法中有以下几种常见的形成探 査的方法，即线性探查法、二次探查法、伪随机数序列探查、双散列探测等，注重 分析各种方法的对于基本聚集和二次聚集各种情况的散列效率。

在讲解闭散列的插入、检索和删除算法的实现时，需要保持探查序列不“断链”，注意分析使用“墓碑”的必要性及其对插入和检索算法的影响。 开散列方法非常简单，易于实现，删除也极为方便;经过精心设计的闭散列效率比开散列稳定。开散列方法的效率最好，实际系统中大多使用开散列方法。 讲授中应使学生理解冲突解决方法的基本原理，注意开散列方法（包括拉链法和桶式散列）和闭散列方法的空间需求和平均检索长度，引导学生思考 其各自的效率、特点和适用的条件。注意分析负载因子对检索效率的影响。 除了要求学生对基于线性表和集合的检索方法，散列表和散列方法、各种散列函数和散列探查方法的基本思想的理解之外，还需提醒学生注意实际应用，在 实际应用中分析检索效率。例如，可以根据应用规模的大小、应用的特点（如是 否是范围检索）、应用的时间和空间限制等，权衡检索的算法复杂度与效率，选择最合适的数据结构和检索算法。

11.索引 重点

基于磁盘的索引文件组织方式，索引、主码、辅码的基本概念;线性索引的基 本概念及优缺点、二级线性索引；B/B+树动态索引技术；基于属性正文文件的 倒排索引的基本概念。位图索引技术以及文本信息检索中的签名文件索引?内 存索引结构红黑树的基本概念。

难点

B/B+气的査找、插人、ji除、访外次数分析;红興_插人删除算法。 授课提示

数据结构设计的重要目标之一是提高操作速度对数据库而言主要是检索速度。实际上索引是为检索服务的,而排序又是为索引服务的。散列方法其实是对关键码的索引，与关键码对应的记录表述可能存放在其他地方；局部平衡的红黑树、平很的AVL树、自组织的伸展树等二叉搜索树具有良好的检索性能，非常适合于基于内存的索引。

索引（Indexing）这一部分的内容训练学生预处理数据的思维方法，以及数据结构的平衡四项。防止树形结构退化为线性结构。

除了上述教学注意事项之外。还需要提醒学生注意在数据库、搜索引擎等现实系统中，索引得到了广发应用。可以安排对B、B+数的插入、删除算法的实际运用和红黑树的具体问题的应用。

在实际应用中，需要按照记录中的属性记录项来查找记录，这样就需要按属

第 - 16 - 页 共 31 页

数据结构与算法课程教学实施方案

性值建立索引。而随着电子数据的高速增长，为了更好地利用越来越来的文本数据，对文本数据的检索和管理变得越发重要。正文索引就是处理对文本内容的快速检索的方法。

B、B+数是动态的索引结构（B+数是B树的一种变形），允许动态地插入或删除记录，索引结构本身也可能发生改变。改变索引结构的目的是为了保持较好的性能，例如较高的检索效率。

B树、B+树的插入与删除都要特别注意保持其平衡性质，特别是高、子结点个数、关键码个数的上下界限制。由于B树和B+树本身具有相似性，又略微不同，因此他的操作过程类似，但有一些差别。

红黑树也是一种二叉搜索树，它没有ACL树那样完全平衡的特性，而是利用对树中结点红黑着色的要求降低了平衡性的条件，达到局部平衡，从而既能提高红黑树增删记录的性能，又能达到高效率的检索要求。红黑树的插入、删除算法比AVL树更简单而易于实现，而且它的统计性能要好于AVL树。因此，红黑树是一种很好的索引结构。

12.高级数据结构 重点

多维数组的概念、存储表示、基本运算，特殊矩阵和稀疏矩阵的计算；广义的概念、存储表示、基本运算、存储管理技术；Trie树和Patricia树；二叉搜索树的变体；平衡二叉搜索树AVL的几种旋转变换，最佳二叉搜索树的动态规划算法伸展树的调整。

难点

Trir树和Patricia树的构造及其应用；平衡二叉搜索树AVL的几种旋转变换；最佳二叉搜索树的动态规划算法，伸展树的调整。

授课提示

为妈祖一些特定需要，人们可以对简单数据结构进行扩展，实现一些功能更为强大、具有更多操作的高级数据结构。

多维数组是向量的扩充。广义表是线性表的一种推广，可以采用数组存储或者链表存储。广义表在文本处理、人工只能和计算机图形学等领域都得到了广泛的应用。了解多维数组和广义表的使用，遗迹常用存储管理技术。

Trie和Patricia树结构被广泛地运用于字符串存储，存储和检索字符串都有很高的效率。Trie结构广泛地运用于信息检索、大规模英文词典中。Patricia是Trie结构的变体。Patricia不是对关键码大小范围的划分，而是根据关键码每一个二进制位的编码来划分。Patricia结构是一颗满二叉树，一次检索不会用超过关键码位数的比较。PatriciaTrie是izhong比较好的中文字典组织方式。 最佳二叉搜索树是平均检索长度最短的二叉树。介绍最佳二叉搜索树的构造可以深化对递归算法的理解。同时可以介绍动态规划的算法复杂度分析。

AVL树是一种平衡的二叉搜索树，适用于组织较小的、内存中的目录。为了

第 - 17 - 页 共 31 页

数据结构与算法课程教学实施方案

维护AVL树的平衡，在插入和删除结点时要进行旋转。旋转的方法比较复杂，很多细节容易被忽略，应该结合动画进行讲解。对AVL树的小绿和高度进行计算。 伸展树在搜索过程中自动调整结构，但是不能保证树的高度。伸展树的旋转分为：单旋转、一字型旋转和之字型旋转。旋转的目的是使访问最频繁的结点靠近树结构的根，从而减少访问代价。

4.2.4 基础实验内容和要求

计算机作为一个解决实际问题的工具，在学习理论的同时，需要结合实践进行上机练习。

1. 配合理论课程的实验 实验1 法雷序列

对任意给定的一个自然树n,将分母小于或等于n的不可约的真分数按上升的次序排列，并且在第一个分数前加上数0/1，而在最后一个分数后加上树1/1，这个序列被称为n级法雷序列，以Fn表示。例如，F8为：

0/1，1/8，1/7，1/6，1/5 ，1/4， 2/7 ，1/3， 3/8， 2/5， 3/7 ，1/2，4/7，3/5，5/8，2/3 ，5/7 ，3/4，4/5，5/6，6/7 ，7/8 ，1/1 如果将这些数在数轴上表示出来，他们的分布是不规则的。

请编写一个用链表来求任意n级法雷序列Fn的算法，并在机器上测试实现。 实验目的 训练线性表操作。 实验提示

不能直接比较实属的等与不等。法雷序列是非常经典的序列，有很多有趣的性质，因此在做法雷序列的时候，完全不需要通过分数的排序就能实现，且效率有很大的提高，而其性质又如此之多，以至于利用不同的性质能得到很多不同的算法。

实验2 火车栈式调度问题

编号为1，2，?，n的n辆火车车厢顺序开进栈式结构的站台Station,可以利用栈进行车厢调度，如图4.3所示。禁止将车厢从缓冲铁轨移动至入轨，也禁止从出轨移动车厢至缓冲铁轨。编写算法：

（1）给定一个序列，判断该序列是否为合法出栈序列。例如，3，1,2不是合法序列；1,2,3和3,2,1都是合法序列。

（2）编写算法生成这n个所有合法的出站序列。

第 - 18 - 页 共 31 页

数据结构与算法课程教学实施方案

实验目的 加深对栈的理解 实验提示

对问题1，利用合法的重构找冲突以判断合法序列。对问题2，回溯生成所有合法的出站序列，在回溯的过程中利用合法序列判断作为约束函数。

实验3 双端队列

双端队列是指在队列的前端和后端支持插入与删除操作的队列。

栈和队列都是特殊的双端队列，对存取加了限制。双栈是一种加限制的双端队列，它规定从end1插入的元素只能从end1端删除，而从end2插入的元素只能从end2端删除，在大部分的插入和删除运算发生在队列的一端时，可以用双端队列提高效率，这是它的时间复杂度为常量级。

请实现初始化，插入，删除，判队列空、列端等算法。 实验目的

拓展知识，裂解标准模块库STL中双端队列的实现方式。 实验提示

用一堆数组V【m】存储，两个端点设为end1和end2，组织成循环队列来实现。

实验4 简单行编辑程序

编写一个简单行编辑程序，对文本文件进行插入、删除等修改操作。可以是类似于UNIX Vi或DOS Edlin的简单行编辑，要求实现以下功能：

（1）行插入。 （2）行删除。 （3）改变当前行指针。

（4）对于超过一屏的长文件，进行分页显示。 （5）基于模式匹配算法进行查找和替换。

第 - 19 - 页 共 31 页

数据结构与算法课程教学实施方案

实验目的

字符串综合训练，尤其是KMP算法的实际应用；兼带文本文件操作的联系。 实验提示

（1）必须实现查找字符串的操作（用KMP或其他模式匹配算法），不允许用编程环境所提供的查找算法（可以用函数重载）。

（2）有能力的学生可以支持“*”、“？”等通配符。

（3）本题不要求做图形界面，建议大部分学生实现普通的字符界面编辑器，注意界面简单又好；也允许实现为Word或UltraEdit那样的全屏幕编辑程序。

（4）允许使用变成环境提供的图形包、字符串类（例如，MFC\\CEditview）。 （5）可以研究网上开源代码包，但最好不要直接采用，可以在详细说明自己引用了哪些包中哪些代码的情况下局部引用。

实验5 表达式二叉树

表达式可以用图4.4那样的表达式二叉树来表示。对于简单的四则运算表达式，请实现以下功能：

（1）对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一颗表达式二叉树，并且图示出来（字符图或图形的形式）。 （2）对于构造好的内部表达式二叉树，按照用户的要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括号）或后缀表达式（不带括号）。所谓中缀表达式中的冗余括号，就是去掉该括号不影响表达式的计算顺序。例如“（c+b）+a”中的括号是冗余的，可以表达成不冗余的“c+b+a”。

图4.4 表达式二叉树

实验目的

练习二叉树的各种深度周游算法框架，深入理解深度优先周游中栈的作用。 实验提示

问题1：表达式转二叉树，利用栈来处理表达式并同时构造二叉树。问题2：二叉树输出表达式，前缀、后缀表达式分别按照前序、后序周游即可；输出中缀

第 - 20 - 页 共 31 页

数据结构与算法课程教学实施方案

图结构和文件结构。在介绍每种逻辑结构时，都从其数学特性入手，先介绍抽象数据类型，然后在讨论不同的存储方法，并且研究不同存储方法的可能算法（增、删、查、改等基本运算）。例如对于线性表，如果考虑到存储，可以分为数组和链表；考虑到运算的特殊性，则可以分为向量、栈和队列。结合算法分析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法，这样能够调动读者思维并可从中学到考虑问题的方法，使读者在今后设计和应用数据结构时能够全面地考虑各种因素，选择最佳方案。

比较重要的算法，许列出单独章节来讨论。排序、检索是最经典的运算，为了加快检索速度，往往需要预先建立索引。排序算法最能够体现算法分析的魅力，它的算法速度要求非常高，其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数来提高排序速度；而外排序则需要考虑外存的特性，尽量减少防外操作，以提高排序速度。检索则需要考虑怎样提高检索速度，这往往是与高效索引存储方法有关的。散列表、倒排表、B树和B+树等都是高效的索引结构，具有极好的检索性能。内存索引主要用二叉搜索树，外存索引常用倒排和B+树。散列由于其“关键码—地址”对的高效索引面达到了常量级的检索效率，其检索效率与数据规模无关，只与负载因子（即存储密度）有关。索引和散列是特殊的存储方法。

最后可以介绍数据结构的应用与一些高级主题。例如，广义表和稀疏距离等更复杂的线性结构，Trie结构、AVL树、伸展树、后缀树等复杂结构，科学型人才在将来的科学研究和工程项目实践中会广泛地应用到这些实践的数据结构与算法技术。

在上述内容的写作中需要贯穿算法分析技术，这有助于引导读者数据问题的性质选择合理的数据结构，并对时间和空间复杂性进行必要的控制。

在编写教材的过程中需要注意摒弃一些过时的技术。某些内容可以作为例题讲解但要注意提醒学生采用前沿实用的主流技术。例如，需要注意提醒学生.线索化以便充分利用空间的思想以及基于三元组的稀疏矩阵算法，都属于被淘汰的算法。那种基于节省内存思想的琐碎算法，效率低下，没有通用性。现在存储空间不成问题，而算法可读性、可维护性更加重要。三元组只适合于处理图或稀疏矩阵的输人输出，稀疏矩阵算法的主流存储方法是基于十字链表或者类似于图邻接表。

教材应该精心设计供学生课后练习的习题和综合上机实验题目，最好辅以习题提示或实验指导书.并提供电子课件、教学网站等相关教学资源。

第 - 31 - 页 共 31 页

数据结构与算法课程教学实施方案

表达式时采用中序周游框架，注意结点操作符的优先级高于其左或右子数时的操作：在打印相应的子树之前先打印开括号，再打印相应的子树，最后还需要打印一个闭括号。输出中缀表达式也可以采用非递归的后序周游框架，上述操作在相应的访问点进行。前访问点打印开括号，中序访问点再打印相应的子树，后序访问点打印一个闭括号。

实验6 输出树形文件结构

UNIX的文件/目录结构如下图4.5（a）所示，*表示目录，括号内的数字是文件或目录的大小。

（1）试设计一种数据结构表达这种关系。

（2）设计一种算法，输出如图4.5（b）所示的结果（请注意次序和数字）。

实验目的

深刻理解树的二叉链表表示以及树形结构的应用。 实验提示

题中的输出时对树进行后序遍历的结构，括号内的数字代表文件大小：原文件（*.c和*.txt）是叶节点，其大小按照原来的大小输出，子目录文件的大小事其本身大小和其目录下的文件大小之和。采用二叉链后序周游框架，在后序点计算文件总大小，在中序点打印文件名。

本题可以进一步扩展，真正读取文件系统中的目录结构，并按照规定输出结果。

实验7 真实地图的最短路径问题

每年秋天新生入学，来自全国各地的学生怀揣梦想来到美丽的校园。然而大学校园占地庞大，景点复杂，让很多新生一开始都很迷茫。他们需要一个指导，告诉他们如何尽快地熟悉学习和生活环境。

请依据Google earth（http：//earth.google.com/download – earth.html）

第 - 21 - 页 共 31 页

数据结构与算法课程教学实施方案

上面本校主要景点的经纬度，采用适当的存储结构建立校区主要景点的地图，并支持最短路径查询。

实验要求

（1）根据经纬度，将其转化为地图坐标。至少选择12个以上的建筑（景点），作为程序提供给用户查询的结点。作业报告中应说明使用的转化方法，并包含所选择的地标截图和对各点的命名（或编号）。 （2）本题目涉及图的建立和最短路径问题，不要求坐标点的绝对精确，但应当基本与实际情况相符合。

（3）用户提供两个建筑（经典）的名称或编号之后，程序输出者两点之间的最短路径。

（4）应采用校园主干道作为两建筑（景点）之间的路径。注意，不得为了运算的简便而虚构 或者采用极偏僻的小路（例如，从小山上直接过去）。 （5）展示界面可以尽可能的漂亮和人性化，不要求图形化界面，可以用字符界面实现。鼓励有计算机图形处理技术的小组采用图形化界面展示结果。 （6）本题目涉及图的建立和最短路径问题，不要求坐标点的绝对精确，但应当基本与实际情况相符合。

实验目的

练习图数据结构，尤其是Dijkstra最短路径算法。同时，锻炼解决实际问题的能力，有很大的创造空间。

实验提示

本题目的有趣点之一，就是学生可以选择自己感兴趣的地标。例如，某个学生想查询自己的宿舍和哪个食堂最近，该宿舍的坐标只能他自己标注才能获得。

实验8 排序算法的性能测试

编写一个程序，计算出教材中介绍的所有算法的运行时间，并进行性能比较。 输入规模分别为：

10 100 1000 1000 30000 100000 正序 逆序

其中，正序和逆序测试的是长度为10000的序列分别为正序（已排序）及逆序（逆排序）时的情形。

实验目的

熟悉各种经典排序算法的实现，练习时间性能测试。也可以测试自己实现的各种趣味排序算法。

实验提示

可以字节用教材提供的源程序，但摘取程序的工作请自己亲自完成，不能直接拿别人调好的结果。严禁抄袭。鼓励根据算法思想自己亲自实现，也鼓励测试

第 - 22 - 页 共 31 页

数据结构与算法课程教学实施方案

其他有趣的排序算法。测试小序列算法的时间，如果直接统计，可能得到0ms。可以重复实验若干次，取平均值。

实验9 外部文件排序

海量的文件排序需要采用外排序来实现。首先通过置换选择、内排序（快速排序、堆排序和基数排序）等内排序形成顺串，然后对这些顺串采用多路归并排序，最后形成排序文件。

（1）对于参数相同（归并的路数、一个缓冲区大小等参数都相同。归并的路数请学生自己通过实验探索。缓冲区大小可用512B、4096B等）的外排序，分别用置换选择、快速排序、堆排序和基数排序作为内排序方法，比较各种内排序方法对整个外排序的影响。请给出实验结果，并对结果进行理论分析。 （2）固定用一种内排序方法（例如用快速排序），比较两个文件总长度相当的文件的排序时间。其中一个文件是大记录文件，即一个记录中数据内容很多，但文件的总记录数目相对比较小；另一个是小记录文件，记录较小，但记录数目相对比较多。

（3）实现一个关键码排序的外排序算法（先对关键码建立索引文件，如果索引文件比较小，可以直接内排序，则直接进行内排序处理；否则用上面实现的置换-选择和多路归并外排序算法来对索引文件进行排序，最后根据索引文件的结果对原文件中的记录进行重排）。对各种大小的记录进行实验，发现你的算法对多大的记录用关键码排序最合适？

实验目的

理解初始顺串的作用，掌握归并排序的过程。通过实验对比，发现访外次数对外排序操作的影响。建立对海量数据的处理能力。

实验提示

不同操作系统环节的磁盘块调用方式不一样，可以采用小文件来模拟外部磁盘块。

实验10 LZW文件压缩

为了节约空间，常常需要把文本文件采用压缩编码方式存储。例如，一个包含1000个X的字符串和2000个Y字幕的字符串的文本文件在不压缩时占用的空间为3002B（每个X或Y占用一个字节，2个字节用来表示串的结尾）。同样是1000x2000y,仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可表示的最大游程长度为216，这样上例中的字符串只需用8个字节来存储。当要读取编码文件时，需对其进行解码。由压缩器对文件进行编码，由解压器进行解码。 Lempe、Ziv和Welch所开发的LZW压缩方法，把文本的字符串映射为数字编码。首先，为该文本文件中所有可能出现的字母分别分配一个代码。例如，要压缩的文本文件为：

aaabbbbaabaaba

第 - 23 - 页 共 31 页

数据结构与算法课程教学实施方案

字符串由a和b组成。为a分配代码0，为b分配代码1。字符串和编码的映射关系存储在字典中。每个字典的入口有2个域：key和code。由code表示的字符串存在域key中。

例如，初始字典由下面的前两列给出（也就是代码0和1）。 Code 0 1 2 3 4 5 6 7

Key A b aa aab bb bbb bbba Aaba

LZW压缩器不断地在输入文件中寻找在字典中出现的最长的前缀p，并输出其相应的代码。若输入文件中下一个字符为c，则为pc分配下一个代码，并插入字典。这种策略称为LZW规则。

用LZW方法来压缩上例字符串。文件中第一个在字典中出现的最长前缀为a，输出其编码0。然后为字符串aa分配代码2，并插入到字典中。余下字符串中在字典内出现的最长前缀为aa，输出aa对应的代码2，同时为字符串aab分配代码3，并插入到字典中。注意，虽然为aab分配的代码是3。但仅输出aa的代码2。后缀b将作为下一个代码组成部分。不输出3是因为编码表不是压缩文件的组成部分。相反，在解压时，编码表由压缩文件重新构造。只要采用LZW规则，这种重建就是可能的。紧接2之后，输出b对应的代码。为bb分配6.并插入字典中。然后输出bb的编码，为bbb分配代码5并插入字典中。输出5，并为bbba分配编码6，然后插入字典中。接下来输出aab的代码为3，同时为aaba分配代码7并插入字典。因此上例中字符串的编码为0214537。

请根据上述原理，编写LZW压缩和解压算法。 实验目的

灵活运用散列和字典 实验提示

可以采用散列方法来实现。把文本的字符串映射为数字编码，字符串和编码的映射关系存储在字典中。LZW压缩器不断地在输入文件中寻找在字典中出现的最长前缀p，并输入其相应的代码。若输入文件中下一个字符为c，则为pc分配下一个代码，并插入字典。解压时输入压缩生成的代码，然后用代码所便是的文本替换这些代码，恢复原始文本。

实验11 红黑树检索

采用红黑树，编写一个小型的英汉词典索引，并实现简单的索引功能。 可以尝试与同学合作，分别建立红黑树（树中的关键码不能重复），然后在进行合并。

实验目的

掌握红黑树这种应用最广泛的BST内存索引结构。 实验提示

词典可以自己手动建立，或从网上寻找。词典以英文单词作为关键码索引，

第 - 24 - 页 共 31 页

数据结构与算法课程教学实施方案

中文监视作为结点的数据域。

合并红黑树的操作，主要是实现T1中的关键码都比T2中的关键码小的情况。首先，先将T1中值最大的结点取出作为新结点z，将其从T1中删除。将T1、T2和z合并成一棵新的红黑树T3。要根据T1、T2的阶的情况，进行操作。

实验12 半伸展树存储文件中的单词词频

可以利用半伸展树来存储文件中单词词频。图4.6显示了一个短文件的结点树。

扫描一个文本文件，并计算出这一文件中每个词的词频。为简化起见，略去标点符号，按照字典排列的顺序对单词排序，并忽略大小写。例如,man's 将被当成man和s。类似地，分隔符也被忽略，如 pre - existence 被当作 pre 和existence。

用一棵BST作为一个文件中单词的存储结构，并用semisplay技术对这棵进辅助维护，以使输人流中的下一个单词出现在树比较接近于根的位置的几率较大。半伸展技术构造一棵自调整词频BST的方法如下:

(1)如果在文件中第一次遇到一个词，把这个单词插人 BST 树。否则，从与该单词对应的结点处开始处理，这一单词的词频增加1。

（2）向根结点的移动是通过改变所涉及结点的链接来完成的。如果单词没有在树中找到，将创建一个新的叶子结点，然后插入树中。

(3）通过一个指向父亲结点的指针来保存结点的前驱。因此，从每一个结点都可以访问该结点的任何前驱，直到树根结点。

作业要求 ：自己创建一个较长的测试文件，使用半伸展技术来组织一棵BST。在所在单词都处理完之后，要求对数进行一次中序周游，将所有结点的词频数分别打印。

实验目的

第 - 25 - 页 共 31 页

数据结构与算法课程教学实施方案

应用自组织数据结构。 实验提示

注意旋转与否只取决于是否被访问（包括查找、插入等）。跟词本身的词频没有必然联系。但是可以想象，访问频率越高（只要不都是连续访问），那么它被旋转到根结点的机会就越多，那么相对而言，它会比其他较少访问的结点更接近根结点。

2. POJ在线评测的相关实验

北京大学的ACM/ICPC在线提交评测系统（http://acm.pku.edu.cn/JudgeOnline/）给学生创造了一个良好的上机实践环境，辅助学生进行自测、考试和竞赛。使用系统进行程序设计类相关课程教学时，一方面可以在网上布置作业题目，学生随时完成作业并提交获得评测结果，减轻了教师批改作业的负担同时增强了批改的准确性；另一方面教师亦可在网上监督学生的作业完成情况，并就存在的问题进行解答。网上实时的编程考试更能考察出学生的动手能力，同时有助于威慑和杜绝作弊现象。

下面的扩张联系选自POJ系统的部分ACM/ICPC实习题，这些题目主要体现了经典数据结构与算法的技术实践内容，培养学生算法和程序设计的基本实践能力。根据学生程度，在以下的POJ在线测试题目中，选择6-8道题目，覆盖经典数据结构域算法，总实习实践控制在30小时-50小时。

线性结构

（1）双端队列的应用（2823，http://acm.pku.edu.cn/JudgeOnline/problem?id=2823,下面的题目均用题目替代）

（2）串（1035,3080,1936）

（3）KMP算法（1961,2406） 二叉树

（1）二叉树（1240,1463） （2）二叉搜索树（2482,2352） （3）哈夫曼树（3253） （4）堆（2424,1877,1445） 树

（1）树（1383,1760）

（2）并查集的应用（1703,2492） （3）后缀树（3415,3294） 图

(1)深度优化搜索（2488,3083,3009,1321,2251） （2）广度优先搜索（3278,1426,3126,3087,3414）

第 - 26 - 页 共 31 页

数据结构与算法课程教学实施方案

（3）最短路劲算法（1860,3259,1062,2253,1125,2240） （4）最小生成树算法（Prim,Kruskal）（1789,2485,1258,3026） （5）拓扑排序（1094） 排序和检索

（1）排序（快排、归并排、堆排）（2388,2299）

（2）散列表和二分查找等高效查找法（数的散列、串的散列）（3349,3274,2151,1840,2002,2503）

基本算法

（1）枚举（2179,1411） （2）回溯（2438,1020） （3）贪心（1328,2109，2586） （4）递归和分治法（2104,2084） （5）动态规划（1080,1404）

4.2.5 课程综合实验设计

1. 综合实验基本要求

课程综合实习题目需要设定若干提交和检查点，以便督促学生分阶段划分任务并按期完成。例如：

阶段1 初步设计报告和工作进度计划表，含小组分工说明； 阶段2 详细设计报告及工作计划调整说明； 阶段3 项目源码包及实习总结报告； 阶段4 面测检查。

在规定的时间限制之内提交所要求的程序和报告。正确实现所要求的功能，并且界面友好，适当考虑算法与界面的创意。程序注释的比例为15%以上，以助教能读懂为必要的注释要求。

上机作业提交时打一个zip包，包中含有：

（1）readme.txt文件，包括程序运行环境、编译运行步骤、程序功能等简单说明一下。

（2）附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。例如，VC++中的.dsw、.dsp文件，re目录中的图像资源文件；Jbuilder中的.jpr或.jpx文件，特殊的Java包，等等。

（3）上机实习总结报告内容：

第 - 27 - 页 共 31 页

数据结构与算法课程教学实施方案

①设计思想：重要数据结构的ADT，存储结构（主要的类型及变量说明），主要算法的基本思想（不要写具体算法，也不要画框图）。 ②主要算法的框架（可用类Pascal语言、类C/C++语言或类Java语言表示），算法应该有必要的注释。

③实现注释：各项功能的实现程度，在完成基本要求的基础上有何创新。 ④调试报告：调试过程中遇到的主要问题是如何解决的，对设计和编码的回顾讨论和分析以及对主要算法的改进设想。

⑤经验和体会。

助教检查作业，给出详细评语和成绩，并总结典型算法、典型错误。在习题课上，引导学生交流各种不同类型的解题方案，并且进行深入的数据结构和算法时间、空间效率讨论与实践水平共同提高的目的。

2.综合实验题型 实验 例句搜索

在写英文文章时，遇到生词可能会借助于一些字典或者字典类工具，用来查找某个词的词义、词性。但是如果仅仅根据这些还不是太容易掌握其地道的用法，很有可能造出中国式的英语来，所以直接借鉴别人的使用方法是一种比较可靠的途径。该作业的目的就是做一个很好用的根据英语单词查找相应例句的搜索程序。

实验要求

输入某一个（或若干个）英语单词，要求返回相应的英语例句。 可以按下列3个步骤来运行：

（1）准备语料。寻找英语文章，例如托福、GRE的文章等，或者下载一些英语新闻。目前也提供了一个大学英语的语料，包括带有词性标注的语料。 （2）处理语料。对语料进行清理、分句、索引、生成字典。需要做一些取词干（Stemming）的操作，后面会给一些相关资料。分句可以用最简单的直接根据标点符号处理，也可以根据提供的资料进行处理。

（3）根据索引进行查询。支持一个或多个查询，需要进行取词干的处理。例如，查read、reading等单词也要能够返回。

实验提示

（1）索引功能是最基本的功能，而且需要物化到外存。不能每次机械地从原始语料中去匹配字符串，也不能每次都是在内存里面建立好索引，下次启动程序时又重新建立一次索引。

（2）索引的粒度可以自己根据实际情况调整，由于查询的结果是语句。如果按照词与文章的关系建立倒排索引，每次去查询时可能需要太多的匹配操作。而且如果只是针对原始预料进行索引，最后还需要从文档中找出句子，导致查询比较慢。

第 - 28 - 页 共 31 页

数据结构与算法课程教学实施方案

（3）可以针对一些特殊类型的单词做一些处理，例如一些常用词，这些词可能导致索引膨胀的比较厉害，可以进行一些删减。

（4）可以预先定义一个词典，这个词典可以扩充。需要保证在语料中的词都能够被索引到。预先定义的词典可以包含其他内容，例如单词的中文翻译等。

（5）查询的最基本要求是给一个单词，找出这些单词对应的例句。 加分功能

（1）支持解释单词的意思，中英文解释皆可。可能需要学生自己找词库。当然如果能够根据语料库的内容来自动生成解释可以加更多的分（如网络上的新词，一些特殊用法等）。

（2）支持不断增加的语料库。

（3）支持一些复杂的查询，例如布尔查询。支持中文查询（如如中文词语，查询对应的英语单词的语句），或者一些拼音检查的功能、近义词、相关查询等。 （4）支持一些相关信息查询，例如同义、反义词，词形变化，固定搭配、相关搭配（例如一个名词前常用的形容词等）。

（5）其他更多的先进功能，例如例句的好坏评价、语法分析等。 参考资料

（1）取词干算法可以参考以下资源：

①http://www.comp.lancs.ac.uk/computing/research/stemming/index.hem ②http://tartarus.org/~martin/porterstemmer/

③http://www.comp.lancs.ac.uk/ computing/research/stemming/general/ ④http://en.wikipedia.org/wiki/stemming （2）语料：大学英语教材。

（3）参考网站：http://www.jukuu.com/index.php。

该网站做的工作与本课程实验类似，其搜索结果的右侧有许多可以改进的功能。

4.2.6 考试基本要求和成绩评定建议

数据结构与算法课程的考核主要包括如下几个部分。 （1）平时（书面作业、课堂测试），占学期成绩的20%。 （2）上机实习（+实习报告），占学期成绩的15%。 （3）期中考试，占学期成绩的20%。 （4）期末考试，占学期成绩的40%。

第 - 29 - 页 共 31 页

数据结构与算法课程教学实施方案

（5）考勤和态度，占学期成绩的5%。

期中、期末采用闭卷考试，共占60%。习题作业和上机考察动手解决实际问题的实践能力，占35%。另外，对课程的参与度、学习态度、对他人的帮助等过程性评价也作为考核的内容。

4.2.7 教材写作建议

本课程是计算机学科最重要的核心基础课，计算机科学各领域及各种应用软件都要使用相关的数据结构和算法。当面临一个新的设计问题时，设计者需要选择适当的数据结构并设计出满足一定时间和空间限制的有效算法。

教材写作中，应该注意建立数据结构的逻辑结构与存储结构的运算之间的有机联系，将经典数据结构和算法分析有机地揉合在一本教材中，引导读者根据问题的性质选择合理的数据结构，并对时间空间复杂性进行必要的控制。 抽象数据类型ADT是定义了一组运算的数据模型，这种抽象的数据类型可以在较高级的算法中直接引用，而不用其实现细节，很好地支持了逻辑设计和物理实现的分离。

尽管数据结构和算法设计本质上还是很底层的东西，并不像软件工程大型项目设计对面向对象方法具有直接的依赖性，有人认为并不需要采用面向对象的高级技术来描述底层的算法，但是采用C++语言能够更好地体现抽象数据类型的概念，从而更本质地描述数据结构和算法。

例如，栈结构，栈中元素的数学特性（即逻辑结构）表现为线性表，它们是有序的。栈的主要运算是进栈（Push）、出栈（Pop）、判栈空（Empty）等。通过带模板的C++类定义，可以不涉及栈的存储方式以及栈中元素的类型而定义一个通用的栈的ADT。这种抽象的数据类型可以在较高级的算法中直接引用，而不用考虑栈的实现细节。程序员可以随意地切换底层对栈的支持，而不需要修改上层算法中对栈的定义和操作语句。这就使得设计者可以在不同的设计阶段采用不用的抽象数据类型作为设计的基础，在适当的抽象层次上考虑程序的结构和算法，更好的支持封装和信息隐藏。

目前主流的数据结构与算法教材强调抽象数据类型的思想，因此，建议教材的描述算法采用面向对象的C++或Java。为了使得数据结构和算法清晰易懂。尽量回避C/C++中比较麻烦的内容，例如C++的类的继承，虚函数等。使用参数化的模板（template),可以提高算法中数据类型的通用性，支持高效的代码重用。在后面的章节中，尽量使用STL所提供的栈，队列等基本数据结构。

有些教材采用C语言描述抽象数据类型，会引起教师教学和学生学习的困惑。如果一定要采用C语言，注意不要生般ADT的描述。例如，采用C语言描述栈，对于顺利和链接栈应该有不同的定义和相应的不同实现；在上层算法中调用顺序栈和链接栈一定要采用不同的定义语句调用不同的函数。不要生硬地封装ADT，而且在后面关于栈的应用中，要固定调用顺序栈或链接栈其中的一种实现，一面导致学生编写上层算法调用栈操作时产生困惑。

教材写作中，建议以数据的逻辑结构为主线，顺序介绍线性结构,树形结构，

第 - 30 - 页 共 31 页

数据结构与算法课程教学实施方案

图结构和文件结构。在介绍每种逻辑结构时，都从其数学特性入手，先介绍抽象数据类型，然后在讨论不同的存储方法，并且研究不同存储方法的可能算法（增、删、查、改等基本运算）。例如对于线性表，如果考虑到存储，可以分为数组和链表；考虑到运算的特殊性，则可以分为向量、栈和队列。结合算法分析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法，这样能够调动读者思维并可从中学到考虑问题的方法，使读者在今后设计和应用数据结构时能够全面地考虑各种因素，选择最佳方案。

比较重要的算法，许列出单独章节来讨论。排序、检索是最经典的运算，为了加快检索速度，往往需要预先建立索引。排序算法最能够体现算法分析的魅力，它的算法速度要求非常高，其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数来提高排序速度；而外排序则需要考虑外存的特性，尽量减少防外操作，以提高排序速度。检索则需要考虑怎样提高检索速度，这往往是与高效索引存储方法有关的。散列表、倒排表、B树和B+树等都是高效的索引结构，具有极好的检索性能。内存索引主要用二叉搜索树，外存索引常用倒排和B+树。散列由于其“关键码—地址”对的高效索引面达到了常量级的检索效率，其检索效率与数据规模无关，只与负载因子（即存储密度）有关。索引和散列是特殊的存储方法。

最后可以介绍数据结构的应用与一些高级主题。例如，广义表和稀疏距离等更复杂的线性结构，Trie结构、AVL树、伸展树、后缀树等复杂结构，科学型人才在将来的科学研究和工程项目实践中会广泛地应用到这些实践的数据结构与算法技术。

在上述内容的写作中需要贯穿算法分析技术，这有助于引导读者数据问题的性质选择合理的数据结构，并对时间和空间复杂性进行必要的控制。

在编写教材的过程中需要注意摒弃一些过时的技术。某些内容可以作为例题讲解但要注意提醒学生采用前沿实用的主流技术。例如，需要注意提醒学生.线索化以便充分利用空间的思想以及基于三元组的稀疏矩阵算法，都属于被淘汰的算法。那种基于节省内存思想的琐碎算法，效率低下，没有通用性。现在存储空间不成问题，而算法可读性、可维护性更加重要。三元组只适合于处理图或稀疏矩阵的输人输出，稀疏矩阵算法的主流存储方法是基于十字链表或者类似于图邻接表。

教材应该精心设计供学生课后练习的习题和综合上机实验题目，最好辅以习题提示或实验指导书.并提供电子课件、教学网站等相关教学资源。

第 - 31 - 页 共 31 页

本文来源：https://www.bwwdw.com/article/rryd.html