课程简介

计算机是现代社会中用于解决问题的重要工具。利用计算机解决实际问题需要将问题抽象,并对数据进行操作,最后通过计算机程序求解问题。而本门课程主要内容就是对以上内容进行研究。

课程大纲

第一章 概论

1.1课程介绍

1.2问题求解

1.3数据结构与抽象数据类型

1.4算法特性及分类

1.5算法效率与度量

1.6补充  面向对象简介

1.7补充  类的特殊成员

1.8补充 模版函数与模版类

1.9补充 输入输出流


第二 线性表

2.1线性结构

2.2顺序表

2.3链表

2.4顺序表和链表的比较


第三 栈与队列

3.1栈

3.2栈与递归

3.3递归转非递归(选修)

3.4队列

3.5队列的应用


第四 字符串

4.1字符串基本概念  

4.2字符串的存储结构  

4.3字符串运算的算法实现

4.4字符串的快速模式匹配(选修)


第五 二叉树(上)

5.1二叉树的概念  

5.2二叉树的抽象数据类型  

5.3二叉树的搜索    

5.4二叉树的存储结构


第六 二叉树(下)

6.1二叉搜索树  

6.2堆与优先队列

6.3Huffman树及其应用


第七

7.1树的定义、树与二叉树的等价转换

7.2树的抽象数据类型及树的遍历  

7.3树的链式存储结构    

7.4树的父指针表示法  

7.5树的顺序存储和K叉树  


第八

8.1图的概念和抽象数据类型

8.2图的存储结构  

8.3图的遍历    

8.4最短路径

8.5最小生成树  


课程说明

本课程采用张铭主编的国家“十一五”规划教材《数据结构与算法》(高等教育出版社)。适合计算机以及相关理工专业的大二本科生学习,需要先修过计算概论等课程,具有结构化和面向对象的程序设计基础。


课程主要包括的内容有:线性表,栈与队列,字符串,二叉树,树,图,排序(内排序,外排序),检索,索引,高级数据结构、以及数据结构应用。课程持续16周(分为两个部分,每个8周),学习者每周在本课程上需要投入48小时。在第一部分学完了线性表、栈与队列、字符串、二叉树、树和图这些基础数据结构之后,第二部分我们将深入学习排序、检索、索引、高级数据结构以及数据结构应用等内容。涉及快速排序、外排序等各种经典排序算法,集合、散列、位图等检索方法,B/B+树、Trie树等索引结构,广义表、多维数组等高级线性结构,AVL、红黑树、伸展树等平衡二叉树。第二部分课程持续8周,学习者每周在本课程上需要投入48小时。本课程的本次开设得到Google研究经费支持。


参考资料

[1] 张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008 6月。普通高等教育十一五国家级规划教材。
Textbook: Ming Zhang, Tengjiao Wang, Haiyan Zhao, "Data Structures and Algorithms", Higher Education Press, 2008.
[2]
张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011 1月。普通高等教育十一五国家级规划教材。
[3]
张铭、赵海燕、王腾蛟,《数据结构与算法--学习指导与习题解析》,高等教育出版社,2005 10月。十五国家级规划教材配套参考书。
[4] S. Sahni
,《数据结构算法与应用—C++语言描述》 ,汪诗林等译,机械工业出版社,2000.
[5] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis,
电子工业出版社影印,20031月。
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms,
高等教育出版社影印,20025月。
[7] D. E.Knuth
著,苏运霖 译,《计算机程序设计艺术,第1卷基本算法》,国防工业出版社,2002年。
[8] J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
[9] C. A. Shaffer, Data Structures and Algorithm Analysis in C++, Third Edition, Dover Publications., 2011.
[10]
王晓东,《算法设计与分析》 ,清华大学出版社,20031月。

拓展阅读

其他

主讲教师

张铭   教授

北京大学信息科学技术学院教授,ACM Education Council惟一的中国委员兼任中国ACM教育专委会主席,ACM中国教育专委会主席,CCF教育工委会副主任。自1984年考入北京大学,分别获得学士、硕士和博士学位。研究方向为文本挖掘、社会网络分析等,目前主持国家自然科学基金和教育部博士点基金在研项目。合作发表学术论文100多篇(不乏TKDE、ICML、KDD、AAAI、ACL、WWW等A类会议和期刊),获得机器学习顶会ICML2014最佳论文奖,获得网络领域顶级会议WWW2016最佳论文提名。出版学术专著1部,获软件著作权6项,获发明专利3项。主编多部教材,其中2部教材为国家“十一五”规划教材,《数据结构与算法》获北京市精品教材奖并得到国家“十二五”规划教材支持。主持的“数据结构与算法”被评选为国家级和北京市级精品课程。

赵海燕   副教授

暂无简介

罗国杰   讲师

暂无简介

宋国杰   副教授

暂无简介

王腾蛟   教授

王腾蛟,男,北京大学信息学院教授,博士生导师。北京大学文理大数据研究中心常务副主任、先进技术研究院数据与知识工程研究中心主任。中国软件行业协会数据库及应用软件分会秘书长,中国计算机学会数据库专委会委员,大数据专委会委员。

课程助教

  • wangzhuo

  • zhujile

  • 李浩然

  • 冯雪松

  • 黄梓铭

  • dulun2834

  • 李博远

  • Seter

相关课程推荐

  • 正在进行
    操作系统与虚拟化安全
    操作系统是计算机系统的基础软件,而系统虚拟化已成为云计算平台的核心技术,没有它们提供的安全性,这些计算机系统及其上数据的安全性都将无法保障。本课程将从理论与工程实践相结合的角度,介绍操作系统(Linux)与系统虚拟化(Xen)安全相关理论、技术和方法,包括:安全概念、安全机制、安全模型、安全体系结构、安全开发方法、安全标准与评测方法等,帮助你深入学习和理解该领域的知识体系、实践技术和方法。
  • 正在进行
    算法设计与分析
    本课程的内容分成两大部分:算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识,约占20%,主要介绍算法相关的基本概念和数学基础。比如,什么是算法的伪码描述?什么是算法最坏情况下和平均情况下的时间复杂度?算法时间复杂度函数的主要性质,算法复杂度估计中常用的数学方法,如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法,主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径,并给出一些重要的应用。
  • 正在进行
    算法设计与分析(高级)
    “算法设计与分析”是计算机科学与技术专业的一门核心课程。通过学习算法不但对学习其他专业课程奠定了扎实的基础,也对培养学生的计算思维和求解问题的能力起到重要的作用。算法与计算复杂性理论一直是计算机科学研究的热点领域。面对各个应用领域的大量实际问题,最重要的是根据问题的性质选择正确的求解思路,即找到一个好的算法。特别在复杂的、海量信息的处理中,一个好的算法往往起到决定性的作用。 算法设计与分析涉及内容较多,根据MOOC课程的教学特点和需求,我们将它分成两个部分。其中“算法设计与分析(1)”主要讲授有关算法的基础知识和通用设计技术,包括算法的基本概念和数学基础、分治策略、动态规划、贪心法、回溯和分支限界等。“算法设计与分析(2)”是在上述基础上介绍两类重要问题的建模和算法设计,并进一步讨论问题难度的界定和困难问题的应对策略。这次开课的是第二部分“算法设计与分析(2)”。选修本课程的学生应该预先修过“算法设计与分析(1)”或者具有相关的基础。“算法设计与分析(1)”已经在华文慕课平台上线,网址是:http://www.chinesemooc.org/mooc/4748/,需要了解相关教学内容的同学可以访问。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

1. 试试去广告邮件、垃圾邮件目录看看

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!