数据结构与算法数据结构应用教学设计

数据结构与算法“数据结构应用”教学设计。

北京大学信息科学技术学院。

高军。1.数据结构应用在课程中的定位和前测知识点。

数据结构应用将运用所学习的数据结构的知识，解决实际问题，其目的是加深学生对数据结构基本理论的认识和理解，综合运用所学的知识，增强学生分析问题、解决问题的能力。

数据结构应用一章主要介绍关系数据库连接算法和xml数据查询算法。希望学生能够理解两种数据模型，掌握数据模型之上的核心操作，进行代价分析，并学会实验性能比较方法。根据数据分布特点和处理要求，编写合适的排序算法。

前测知识点要求如下，可以根据需要给学生补充。

1）b+树、hash表概念；

2）缓存管理的概念；

3）xpath查询的概念；

4）dom树、sax解析的概念；

2．学习目标。

1）提高根据客观需求，综合运用多种数据结构解决客观问题的能力；

2）熟悉数据库连接操作各种算法，比较他们在最坏、最好、平均情况下的复杂度；

3）熟悉xml数据解析的两种主要技术，熟悉两种解析方式下的查询处理算法。

3.知识点和学时分配。

理论授课2学时，建议安排实验4学时。

以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉猎面。

各知识点建议授课时间如下：

数据库连接算法。

1小时。xml数据查询算法。

1小时。4．重点和难点。

数据结构应用的重点如下：

数据库中的块嵌套连接算法。

数据库中的哈希连接算法。

数据库中的归并连接算法。

数据库中的索引嵌套连接算法。

xml的dom树解析和xpath的执行算法。

xml的sax解析和xpath的执行算法。

内排序难点如下：

索引连接算法。

各种连接算法的稳定性和时间复杂度。

dom树中递归执行xpath的算法。

sax解析模型中的xpath查询执行算法；

5．授课提示。

开展研究型教学，挖掘知识背后的内容，通过提出问题、**方法、研究思想、比较性能，培养学生的创新意识、创新能力。

下面是数据库应用的重点和难点内容的讲授注意事项。

1）数据库的连接算法。

数据库的连接算法是数据库运算过程中代价较高的操作。目前，已经提出了多种经典算法。

块嵌套连接循环调入外关系中数据块，通过循环访问内关系中的每一数据块，判定连连接条件成立，输出连接结果。

索引嵌套连适应等值连接或自然连接；索引嵌套连接需要在内关系的连接属性上存在索引，或者动态为连接操作而构造一个索引；对外关系r的每个元组tr ,利用索引查找内关系s的与tr满足连接条件的元组。

归并连接将两个关系在连接属性上排序，其连接步骤类似于排序-归并算法的归并阶段；主要不同在于连接属性中重复值的处理；归并连接只能用于等值连接和自然连接；每个块只需要读一次。

哈希连接适合等值连接和自然连接；hash函数h用来划分参与连接的两个关系；h

的输入是joinattrs,输出。

0, 1, .n},其中joinattrs表示参与连接关系的属性；r0, r1, .rn

表示。r元组的划分，i = h(tr[joinattrs])，元组。

trr属于划分ri；

s0, s1. .sn

表示s元组集合的划分，i = h(ts[joinattrs])，元组。tss

属于划分si；在分组之上实现连接操作。

连接操作的执行代价需要考虑内外存数据交换的次数。选择合适的连接算法需要考虑数据的分布情况。

2) xml数据解析的dom解析。

文档对象模型dom (document object model)是由w3c制定的xml树状结构模型和标准操作接口规范。dom解析根据xml文档的结构将其转换为树状结构的文档对象模型。用户通过对该对象模型的访问，可以动态地创建文档，遍历文档结构，对xml文档中的数据进行修改、移动、删除和插入等操作。

dom解析器提供了基于文档对象模型的api来解析和操纵xml文档。它把xml文档内容看作树，而每个元素(element)用结点表示，称为dom node。程序可以从根结点开始以一种导航的方式来访问文档的组成部分。

基于dom解析的优点：支持通过dom接口实现xml文档的数据和结构的更改；支持在任何时候在树中做任意方向的导航；支持简单有效地实现xml查询。

基于dom解析的缺点：由于dom解析需要在内存中表示xml文档中元素、文本、属性等，所以dom解析的时间和空间代价昂贵。

3) xml数据解析的dom解析。

sax是基于事件的xml文档顺序访问的一组api接口。相对于dom解析方式，sax是读取和操作。

xml数据的更快速、更轻量的方法。sax的api基于事件处理程序的概念构建，是由与语法分析实际相关联的用户指定函数构成。语法分析事件对应文档组成部分的识别：

例如，当找到一个元素的开始标签的时候产生一个事件，而当找到结束标签时又产生一个事件，对这些事件的响应由用户指定函数进行处理。一个文档的不同片段总是可以按照从开始到结束的顺序找出。具体的事件有文档的开始和结束、元素的开始和结束、文本内容的读取等。

例如，给定一个xml文档片断。

databaseprincipleullman 。sax解析器处理文档的结果如下：starteelement(book)、startelement(title)、text(“databaseprinciple”)、endelement(title)、startelement(author)、text(“ullman”)、endelement(author)、endelement(book)。

基于sax解析的优点：sax解析的时间代价和空间代价较低，sax解析支持高效的xml顺序访问；sax解析支持xml文档的部分解析，可以提前终止解析过程。

基于sax解析的缺点：sax解析不能支持对xml文档的随机访问；sax解析不能支持xml文档的修改；sax解析实现xml查询需要应用程序的支持。

4）xpath查询。

xpath是w3c所提出的一种路径查询语言(pathlanguage)，支持通过路径表达式来定位xml文档的部分内容。xpath中的路径表达式是一串通过”/”隔开的定位步骤的序列。路径表达式的查询结果是一个xml子树的集合。

xpath路径表达式是从一个xml结点(即当前的上下文结点)到另外一些结点的定位步骤序列。每个定位步骤包含以下三个部分：轴描述、结点测试和谓词。

xpath路径表达式中的轴描述指从上下文结点在xml数据树中进行访问的方向，具体包括child (子结点)、attribute (属性)、descendant(子孙结点)、descendant-or-self (自身或子孙结点)、parent (父结点)、ancestor (祖先结点)、ancestor-or-self (自身或祖先结点)、following (下文结点)、preceding (前文结点)、following-sibling (后一个同级结点)、preceding-sibling (前一个同级结点)、self (自己)、namespace（命名空间）。

xpath路径表达式中的结点测试检验满足轴描述的结点，如果该结点与限定的元素名称或元素类型相匹配，则保留在结果集合中，否则该结点被丢弃。

xpath路径表达式中的谓词筛选一个结点集以生成新的结点集。对于结点集中的每一个结点，谓词表达式将此结点作为当前上下文结点进行求值。基于当前上下文结点，计算谓词表达式中的值，并将结果转换为布尔值。

如果结果为true，该上下文结点保留；否则被丢弃。

在dom树中实现xpath查询需要在树结构中根据xpath的特性来递归执行。鼓励同学实现xml的索引减少xpath的搜索空间。在sax解析器中实现xpath查询需要利用将xpat转换为自动机，将xpath的查询转换为sax事件对自动机的驱动。

6．课后练习和实习。

融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合应用型的习题和上机题，通过数据库连接操作算法和xml数据查询算法提高学生综合各种数据结构来解决实际问题的能力，训练学生的创新思维能力训练、工程实践能力。

数据结构应用可以安排2道综合上机实习题。安排2次习题讲评。

7．总结。数据结构应用是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践能力的重要环节，同时，扩展数据结构应用领域的知识，使学生理解关系数据处理和xml数据处理的基本算法。参考文献：

张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2023年6月。——普通高等教育“十一五”国家级规划教材。

张铭、赵海燕、王腾蛟、宋国杰。

高军，北京大学“数据结构与算法”教学设计，《计算机教育》2008第20期。获得“英特尔杯2023年全国计算机教育优秀**评比”一等奖。

北京大学《数据结构与算法》精品课程**（2023年北京市“精品课程”暨国家“精品课程”），蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。

张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计算机教育》，2023年月合刊，pp89-91。

数据结构与算法数据结构应用教学设计

数据结构常用算法数据结构算法

数据结构与算法

算法与数据结构

其他用户还读了