数据结构(上)

随堂模式

  • 什么是随堂模式?

    随堂模式课程一般为每学期一轮次,课程每周更新,作业、考试有截止时间,由课程提供方老师、助教指导,课程完结,成绩由老师确认后,统一发放证书。

  • 什么是自主模式?

    自主模式课程常年开放加入,课件全部开放,作业、考试无截止时间,有学堂在线招募选拔的助教指导,考核通过即可自动获得证书。

来自于: 清华大学 | 分类: 计算机(415)

课程描述

本课程旨在围绕各类数据结构的设计与实现,揭示其中的规律原理与方法技巧;同时针对算法设计及其性能分析,使学生了解并掌握主要的套路与手段。

什么是认证证书?
免费学习
认证学习
名师签名
实名认证
权威性
纸质证书
付费购买
免费赠送

课程简介

数据结构是计算机科学的关键内容,也是构建高效算法的必要基础。其中涉及的知识,在相关专业的课程系统中始终处于核心位置。本课程旨在围绕各类数据结构的设计与实现,揭示其中的规律原理与方法技巧;同时针对算法设计及其性能分析,使学生了解并掌握主要的套路与手段。讲授的主题从基础的数据结构,一直延伸至新近的研究成果。

(分为上、下两部分,分别于2013年秋季学期和2014年春季学期讲授)

按照一致的ADT接口规范,介绍对种数据结构的不同实现方式:

序列:向量、列表、栈、队列

树,尤其着重于平衡二叉搜索树:AVL树、伸展树、红黑树、B-树、kd-树

优先级队列:完全二叉堆, 多叉堆, 左式堆

词典:散列表、跳转表

图结构的应用:最小生成树、最短路径、拓扑排序、双连通域

通过实例,讲解构建高效算法模块的基本方法:

查找

选取与排序

遍历

模式匹配

几何范围查找

散列

归纳典型的算法策略及模式,以及复杂度分析的基本方法:

迭代、递归、贪心

减而治之

分而治之

试探-剪枝-回溯

制表/记忆、动态规划

渐进分析

分摊分析

后向分析

递推式、递归跟踪

展开

课程章节

第零章
选课之前
考核方式与课程大纲
OJ系统说明
关于课程教材与讲义
关于讨论区
联系课程团队
PA-1a-LightHouse
第一章 绪论
本章概要
(a)计算
(b)计算模型
(c)大O记号
(d)算法分析
(e)迭代与递归
(f)动态规划
本章测验
第二章 向量
(a)接口与实现
(b)可扩充向量
(c)无序向量
(d1)有序向量:唯一化
(d2)有序向量:二分查找
(d3)有序向量:Fibonacci查找
(d4)有序向量:二分查找(改进)
(e)起泡排序
(f)归并排序
本章测验
第三章 列表
(a)接口与实现
(b)无序列表
(c)有序列表
(d)选择排序
(e)插入排序
本章测验
第四章 栈与队列
(a)栈接口与实现
(c1)栈应用:进制转换
(c2)栈应用:括号匹配
(c3)栈应用:栈混洗
(c4)栈应用:中缀表达式求值
(c5)栈应用:逆波兰表达式
(d)队列接口与实现
本章测验
第五章 二叉树
(a)树
(b)树的表示
(c)二叉树
(d)二叉树实现
(e1)先序遍历
(e2)中序遍历
(e4)层次遍历
(e5)重构
本章测验
第六章 图
(a)概述
(b1)邻接矩阵
(c)广度优先搜索
(d)深度优先搜索
本章测验
第七章 二叉搜索树
(a)概述
(b)算法及实现
(c)平衡与等价
(d)AVL树
本章测验
编程习题(PA)成绩查询
领取PA1成绩
领取PA2成绩
领取PA3成绩
加分查询

授课教师

  • 邓俊辉 清华大学 计算机系 副教授

    邓俊辉,清华大学计算机系副教授。1993、1995和1997年分别于清华大学计算机系获学士、硕士和博士学位,1997年起在清华大学任教,主要讲授“数据结构”和“计算几何”。

  • 李锐喆 清华大学 计算机系 博士生

    李锐喆,清华大学计算机系博士生,2010年起担任计算机系数据结构课程助教,现负责在线评测系统的开发和维护。

  • 王欢 清华大学 计算机系 硕士生

    王欢,清华大学计算机系硕士生,2012-2013年期间担任全校性选修C++程序设计及数据结构课助教。

  • 姜禹 清华大学 计算机系 硕士生

    姜禹,清华大学计算机系硕士生,2012-2013年期间担任全校性选修数据结构课助教。

  • 梁缘 清华大学 计算机科学与技术系 2010级本科生

    梁缘,清华大学计算机科学与技术系2010级本科生。兴趣领域:并行计算、机器学习、计算机图形。

  • 王笑尘 清华大学 计算机科学与技术系 2011级本科生

    王笑尘,清华大学计算机科学与技术系2011级本科生。清华大学美术学院艺术设计(数字娱乐设计方向)专业二学位学生。

  • 杨凯峪 清华大学 计算机系 本科生

    杨凯峪,清华大学计算机系本科生。2011年就读于清华大学电机系,2013年转入清华大学计算机系。曾任本课程教材第三版习题解析的试验读者。

  • 熊异雷 清华大学 计算机科学与技术系 2010级本科生

    熊异雷,清华大学计算机科学与技术系2010级本科生。

  • EricWu 计算机科学与技术专业 本科生

    我是Eric Wu, 2012年计算机科学与技术专业本科毕业, 现就职于一家互联网公司, 主要从事平台服务端Java开发, 对Linux也很感兴趣。

  • feichashao MOOC重度使用者

    我是MOOC重度使用者,学过十多门课程,上过计算机专业课,也上过专业无关的吉他课。

  • MrROY

精华笔记

精华笔记正在评选中,去看看全部笔记

常见问题

目前还没有常见问题哟!