课程简介

课程简介:《数据结构与算法》是计算机科学技术等电子信息类专业的核心主干基础课程。课程依据美国最新ACM/IEEE CC2005课程体系和中国教育部CCC2006学科规范制定了先进的课程体系。设计研究启发式教学案例,培养创新意识和主动学习意识,课程以问题求解为导向,培养和提高学生理论、抽象、设计的能力,强调实践和创新能力。从逻辑、存储、运算的角度组织数据结构与算法,培养了学生独立地实现常用基本数据结构的抽象数据类型,注重实践能力和工程能力的培养,并建立起数据结构与算法设计和问题求解的知识体系。

课程采用主持教师的国家十五教材和配套的实验教材,建设了立体化的网络教学环境。课程小组在多年教学积累的基础上,新编写了国家十一五教材(20086月出版),并正在编写十一五实验教程。所出版的教材和自主开发的网络教学平台课程在国内产生了比较广泛的影响和良好的示范作用。课程采用现代化的教学手段,通过多媒体动画课件和网络教学促进了师生的交流与互动。课程的重要特色,就是实习大项目,融合当前最新理论和技术,非常有前瞻性,学生受到创新思维能力训练、工程能力训练令其在后来的研究和工作中受益良多。

课程网站为学生提供全方位的学习辅导支持,尤其是细化到知识点的课程知识体系导航。整个网站的内容十分丰富,除知识点和电子课件外,还有46小时课程全程录像、ACM在线算法测试、学生论坛等内容。

本课程在国内有很大的影响。2008518日通过Google检索,“约有137,000项符合张铭 数据结构的查询结果”,“约有34,700项符合张铭 数据结构 视频的查询结果”。

2008年数据结构实验班链接:http://db.cs.pku.edu.cn/mzhang/ds/honor/ (教育网访问)
                  讨论组链接:http://groups.google.com/group/ds2008_advanced_pkucs (实验班)
                              http://groups.google.com/group/ds2008_practice_pkucs (实习班)

1.“数据结构与算法”课程与计算机专业其他课程的关系

“数据结构与算法”是计算机专业的核心课程之一,本科教学的重中之重。如下图所示,本课程上承“计算概论”与“程序设计实习”,下启“算法分析与设计”和“计算复杂性理论”,同时是操作系统、软件工程、数据库概论、编译技术、人工智能、计算机图形学等专业课程的必修先行课。很多应用软件都要使用到各种数据结构和算法编写程序进行科学计算、模拟试验等。

 

2.数据结构与算法的知识体系

数据结构,就是由某种逻辑关系组织起来的一批数据,按一定的存储方法被存储于计算机中,并在这些数据上定义了一个运算的集合。数据结构具有三个方面:数据的逻辑结构、数据的存储结构和数据的运算。

常见逻辑关系有:线性结构、树形结构、图结构和文件结构。常见的存储方法有:顺序方法、链接方法、索引方法、散列方法。

对于一种数据结构,往往需要定义一些运算。排序、检索是最经典的运算,为了加快检索速度往往需要预先建立索引。内存索引主要用BST(二叉搜索树),外存索引常用倒排和B+树。

算法分析技术有助于根据问题的性质选择合理的数据结构,并对时间空间复杂性进行必要的控制。对于存储外存中的文件数据的访问速度,对文件的操作运算应该尽量减少访外次数。

抽象数据类型Abstract Data Type,简称“ADT”)是定义了一组运算的数学模型,这种抽象的数据类型可以在较高级的算法中直接引用,而不用其实现细节,很好地支持了逻辑设计和物理实现的分离。

数据结构课程的基本知识模块是以数据的逻辑结构为主线,顺序介绍线性结构、树形结构、图结构和文件结构。在介绍每种数据结构时,再讨论其存储结构以及相关的算法。

在介绍完基本的数据结构及其存储结构和相关的算法后,根据不同的专业,还将介绍一些扩展研究内容,涉及到外排序、广义表、稀疏矩阵、字符树、 Patricia 树、后缀树、后缀数组、AVL、红黑树和伸展树等高级数据结构,有助于拓宽知识面,提高解决实际问题的能力。

在实践训练环节,选取来自于计算机科学技术的前沿应用课题,例如XML DOM 树解析器、后缀树、搜索引擎等。激发学生的学习兴趣,培养学生的创新思维能力。

课程以问题求解为导向,培养和提高学生理论、抽象、设计的能力。通过扎实的经典基础理论训练,帮助学生灵活地运用问题抽象、数据抽象、算法抽象来分析问题,应用数据结构和算法来设计和实现相应的程序,完成创新能力和实践能力的训练。