数据结构基础

隶属于 程序设计与算法 Fundamentals of Programming and Algorithms 专项课程 »这门课程将帮助学生学习如何运用基础的数据结构和相关算法解决实际应用问题。

北京大学

分享

  • 分类: 计算机
  • 平台: Coursera
  • 语言: 中文

课程概述

介绍视频若无法正常播放,请看这里。

本课程围绕着“算法+数据结构=程序”的思路,以问题求解为导向进行学习,帮助大家提高理论、抽象、设计的能力。主要包括的内容有:线性表,栈与队列,字符串,二叉树,树,图。学生将通过权衡时空和其他资源开销,利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。

授课大纲

第一周 概论
问题求解
数据结构与抽象数据类型
算法特性及分类
算法效率与度量

第二周 线性表
线性结构
顺序表
链表
顺序表和链表的比较

第三周 栈与队列

栈与递归
递归转非递归(选修)
队列
队列的应用

第四周 字符串
字符串基本概念
字符串的存储结构
字符串运算的算法实现
字符串的快速模式匹配(选修)

第五周 二叉树(上)
二叉树的概念
二叉树的抽象数据类型
二叉树的搜索
二叉树的存储结构

第六周 二叉树(下)
二叉搜索树
堆与优先队列
Huffman树及其应用

第七周 树
树的定义、树与二叉树的等价转换
树的抽象数据类型及树的遍历
树的链式存储结构
树的父指针表示法
树的顺序存储和K叉树

第八周 图
图的概念和抽象数据类型
图的存储结构
图的遍历
最短路径
最小生成树

先修知识

基本的C/C++编程能力

参考资料

[1] 张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011年 1月。普通高等教育“十一五”国家级规划教材。

[2] 张铭、赵海燕、王腾蛟,《数据结构与算法--学习指导与习题解析》,高等教育出版社,2005年 10月。 “十五”国家级规划教材配套参考书。

授课形式

quiz小测和课程参与40% ,POJ 算法填空20%,POJ算法题10%,期末考试30%。总成绩完成 60%以上,才能获得证书。

注释:编程作业除了在本平台发布外,也同时发布于POJ程序自动评测网站http://dsalgo.openjudge.cn/ ,同学们可以自行练习。

常见问题解答

1. 课程采用中英文教学吗?
本课程的大部分资源,包括所有字幕、课件、小测作业、编程题、考试都同时只提供中文版本。

2. 课程采用的算法语言?
本课程采用基于C++的伪代码授课和出习题。编程作业是POJ(http://dsalgo.openjudge.cn/ )自动评判的,该平台目前接受 C、C++、Java等都可以。

3.教材与参考文献
[1] 张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年 6月。普通高等教育“十一五”国家级规划教材。
[2] 张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011年 1月。普通高等教育“十一五”国家级规划教材。
[3] 张铭、赵海燕、王腾蛟,《数据结构与算法--学习指导与习题解析》,高等教育出版社,2005年 10月。 “十五”国家级规划教材配套参考书。
[4] S. Sahni ,《数据结构算法与应用—C++语言描述》 ,汪诗林等译,机械工业出版社,2000.
[5] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印,2003年1月。
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms, 高等教育出版社影印,2002年5月。
[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] 王晓东,《算法设计与分析》 ,清华大学出版社,2003年1月。

4. 参考网站
(1) 《数据结构与算法》精品课程(该网站是教育网IP,不支持国外IP访问)
“Data Structures and Algorithms” Course Website at Peking University (Only available in Mainland China)  http://www.jpk.pku.edu.cn/pkujpk/course/sjjg
(2) Berkeley course:Data Structures  http://www.cs.berkeley.edu/~jrs/61b/
(3) MIT course: Intro to Algorithms http://stellar.mit.edu/S/course/6/sp13/6.006/
(4) Stanford course https://www.coursera.org/course/algo
(5) Princeton course https://www.coursera.org/course/algs4partI
(6) 网上的术语资源(terminology resources online) http://www.nist.gov/dads/
(7) Algorithms in the Real World  http://www.cs.cmu.edu/~guyb/realworld.html
(8) Advanced Data Structures and Algorithms http://theory.stanford.edu/~rajeev/cs361.html
(9) Advanced Data Structures http://www.cs.biu.ac.il/~moshe/ds1.html

Udemy
声明:MOOC中国发布之课程均源自下列机构,版权均归他们所有。本站仅作报道收录并尊重其著作权益,感谢他们对MOOC事业做出的贡献!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc
  • 以及更多...

Copyright © 2008-2015 MOOC.CN 慕课改变你,你改变世界