清华大学邓俊辉数据结构讲义.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：8.89M 资料格式：pdf 举报版权申诉

draco_mystack-8653011-4744302542969818105.pdf-第1页.png

第1页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第2页.png

第2页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第3页.png

第3页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第4页.png

第4页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第5页.png

第5页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第6页.png

第6页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第7页.png

第7页 / 共738页

draco_mystack-8653011-4744302542969818105.pdf-第8页.png

第8页 / 共738页

TOC

0.A.Syllabus.pdf

0. 绪论

FAQ：教师

FAQ：选修，还是不选修

FAQ：考评及要求

FAQ：学习资料

FAQ：学习资源

FAQ ：讲义与代码

FAQ：作业

0.B.Introduction.pdf

0. 绪论

绳索计算机及其算法

尺规计算机及其算法

计算机与算法

什么是好的算法

数据结构：为何要学？学什么？学习目标？

数据结构：内容纵览

抽象数据类型与数据结构

0.C.Big-o.pdf

0. 绪论

算法分析

问题规模 vs. 计算成本

算法 vs. 计算效率

RAM

渐进分析

O(1)

O(logcn)

O(nc)

O(2n)

2-Subset

增长速度

复杂度层次

课后

0.D.Algorithm_analysis.pdf

0. 绪论

主要方法

级数和

循环 vs. 级数和

数组求和：迭代

数组求和：递归

找最大元素：迭代

找最大元素：递归

取非极端元素

Fib()

起泡排序

起泡排序：复杂度

幂函数

a98765

a10110b

幂函数

课后

0.X.Sorting+Lower Bound.pdf

0. 绪论

难度与下界

排序

算法分类

时空性能、稳定性

最坏情况最优 + 基于比较

判定树

代数判定树

下界：(nlogn)

课后

1.Sequence.A.Adt+Interface.pdf

1. 序列

序列

向量 + 列表 = 序列

接口/实现/应用

接口：LinearList.H

重载

遍历

合并

归并

接口测试

各种实现纵览

1.Sequence.B.Vector.pdf

1. 序列

类型实现

构思

结构

操作实现——O(1)

操作实现——O(n)

自动插入

综合评价——时间

综合评价——空间

扩容

课后

1.Sequence.C.List.pdf

1. 序列

类型实现

构思与定义

逻辑结构

存储结构

操作实现——O(1)

操作实现——O(n)

综合评价

双向链表

双向链表：实现

双向链表：插入节点

双向链表：删除节点

常见错误

循环链表

课后

1.Sequence.D.Cursor.pdf

1. 序列

动机与构思

原理与例子

游标实现

课后

1.Sequence.E.Application.pdf

1. 序列

构思

表示与实现

1.Sequence.F.Ordered Vector.pdf

1. 序列

查找与查找表

操作及分类

评价指标

顺序查找：原理&实现

顺序查找：性能分析

折半查找

折半查找实例：成功

折半查找实例：失败

折半查找：性能分析

Fibonacci查找

Fibonacci查找：性能比较

插值查找

插值查找：例子

插值查找：性能比较

课后

1.Sequence.G.Insertionsort.pdf

1. 序列

直接插入：构思

直接插入：算法

直接插入：复杂度与性能

二分插入：复杂度与性能

直接插入：平均性能

综合分析

1.Sequence.X.Java Implementation.pdf

1. 序列

Interface：定义

Interface：实现

向量接口：Vector.java

向量实现1：Vector_Array.java

向量实现2：Vector_ExtArray.java

序列接口及实现

1.Sequence.Y.Skiplist.pdf

1. 序列

动机与思路

结构

查找：算法

查找：实例

空间性能

层高

查找：时间性能

插入：算法

插入：实例

删除：算法

删除：实例

课后

2.Stacks+Queues.A.Stack.pdf

2. 栈与队列

定义&ADT

基于序列的实现

独立实现

操作实例

栈混洗：过程与定义

栈混洗：计数

栈混洗：判定

课后

2.Stacks+Queues.B.Applications.pdf

2. 栈与队列

进制转换

括号匹配：递归

括号匹配：迭代+栈

表达式求值

优先级表

RPN

RPN栈式计算

0 ! 1 23 + 4 - 56 - 7 * 8 * - 9 -

0 ! 1 + 2 3 ^ 4 ! - 5 ! 6 / - 7 * 8 * - 9 -

infix到postfix转换

PostScript

课后

2.Stacks+Queues.C.Recursion.pdf

2. 栈与队列

分治算法

括号匹配

Hanoi塔

Hanoi塔：递归跟踪

Hanoi塔：时间复杂度

递归，还是不递归？

尾递归及递归消除

2.Stacks+Queues.D.Probe-Backtrack.pdf

2. 栈与队列

构思

八皇后

八皇后：蛮力搜索

八皇后：剪枝

八皇后：试探/回溯

八皇后

迷宫寻径

课后

2.Stacks+Queues.E.Queue.pdf

2. 栈与队列

定义/ADT

链式表示及实现

顺序表示及实现

离散事件模拟

课后

3.String.A.Representation+Implementation.pdf

3. 串

定义

定义 & ADT

实现：定长的顺序存储

实现：堆分配存储

实现：块链存储

操作：串匹配

3.String.B.Pm.pdf

3. 串

串匹配

算法性能的评测方法

Brute-force：构思

Brute-force：实现

Brute-force：实现#1

Brute-force：实现#2

Brute-force：复杂度

课后

3.String.C.Kmp.pdf

3. 串

Brute-force：改进

KMP：算法

KMP：next[ ]表的作用

KMP：next[j]的含义：避免回溯

KMP：next[j]的含义：不致遗漏

KMP：next[ ]表的构造：思路

KMP：next[ ]表的构造：理解

KMP：next[ ]表的构造：算法

KMP：next[ ]表的构造：实例

KMP：String-Search Compiler

KMP：复杂度

KMP：再改进：思路

KMP：再改进：方法

KMP：再改进：实例

KMP：小结

3.String.D.Bm.pdf

3. 串

匹配算法

BM：算法

BM：Bad-Character Shift

BM：Bad-Character Shift：性能分析

BM：Bad-Character Shift：不足

BM：Good-Suffix Shift

BM：性能分析

课后

4.Trees.A.Introduction.pdf

4. 树

应用

递归定义

拓扑定义

ADT

存储结构：父节点表示法

存储结构：孩子节点表示法

存储结构：父节点 + 孩子节点表示法

存储结构：孩子 + 兄弟表示法

4.Trees.B.Binary Tree.pdf

4. 树

定义 & ADT

满二叉树

完全二叉树

一般二叉树：基数

一般二叉树：实现

链式存储结构

生成 & 销毁

4.Trees.C.Preorder Traversal.pdf

4. 树

遍历

递归

迭代：思路

迭代：实现

迭代：实例

迭代：分析

迭代：另一思路

迭代：实现

4.Trees.D.Inorder Traversal.pdf

4. 树

递归

迭代：难点

迭代：首先访问谁

迭代：利用栈结构的实现

迭代：实例

迭代：正确性

迭代：效率

4.Trees.E.Postorder Traversal.pdf

4. 树

递归

迭代：难点

迭代：首先访问谁

迭代：找到应最先访问的节点

迭代：利用栈结构的实现

迭代：实例

迭代：正确性

迭代：效率

课后

4.Trees.F.Breadth-First Traversal.pdf

4. 树

迭代：实现

迭代：实例

迭代：分析

应用：表达式树

4.Trees.G.Huffman Tree.pdf

4. 树

问题

二叉编码树

编码长度

最优编码树

带权编码长度

最优编码树

Huffman编码：策略与算法

Huffman编码：实现

Huffman编码：正确性

Huffman树：双子性

Huffman树：不唯一性

Huffman树：层次性

Huffman编码：正确性

Huffman编码：效率

Huffman编码：改进

5.BST.A.Binary Search Tree.pdf

5.查找树

动态查找

有序表 vs. 查找树

BST：定义

BST：例子与反例

BST：数据结构

BST：查找

BST：插入

BST：删除

BST：性能：评价标准

BST：性能：高度

BST：失衡 vs. 平衡

5.BST.B.Avl Tree.pdf

5.查找树

为何要平衡

如何才算平衡

AVL = 平衡

平衡的恢复

插入：重新平衡：单旋

插入：重新平衡：双旋

实现

插入：统一算法

插入：正确性

删除：叶子

删除：内部节点

删除：可能的情况

综合评价

5.BST.C.Splay Tree.pdf

5. 查找树

局部性

初步的构思：Zig & Zag

最坏例子：Insert(0, 1, 2, 3, 4)

最坏例子：Find(0, 1, 2, 3, 4)

初步的构思：效率

伸展：构思

伸展：Zig-Zig

伸展：Zig-Zag

伸展：Zig / Zag

插入：Burte-force

插入：实现

删除：实现

Splay树：分摊复杂度

Splay树：最坏情况

Splay树：局部性

Splay树：综合评价

5.BST.D.B-Tree.pdf

5. 查找树

越来越小的内存

高速缓存

B-Tree

定义

简单的B-树

查找

复杂度

最大树高

最小树高

查找树，究竟会长多高？

插入&分裂：算法与实现

插入&分裂：实例

删除&合并：算法

删除&合并：底层节点

删除&合并：非底层节点

课后

5.BST.E.Red-Black Tree.pdf

5. 查找树

红 vs. 黑

(2,4)树 vs. 红黑树

红黑树  BBST

插入 + 双红

双红修正(1)：u->color == B

双红修正(2)：u->color == R

双红修正：复杂度

删除 + 双黑

双黑修正(1)：s 为黑，且至少有一个红孩子 t

双黑修正(2R)：s 为黑，且两个孩子均为黑；p 为红

双黑修正(2B)：s 为黑，且两个孩子均为黑；p 为黑

双黑修正(3)：s 为红（其孩子均为黑）

双黑修正：复杂度

java.util.TreeMap

5.BST.X.Kd-Tree.pdf

5. 查找树

区域查找

Brute-force

计数法

平面

平衡二叉查找树：结构

平衡二叉查找树：查找

平衡二叉查找树：效率

kd-Tree：构思

kd-Tree：构思实例

kd-Tree：构造

kd-Tree：构造实例

kd-Tree：性质

kd-Tree：查找

kd-Tree：查找实例

kd-Tree：效率

kd-Tree：高维空间

课后

6.Hashing.A.Hashing.pdf

6. 散列

85001

映射 + 词典 = 符号表

Tsinghua

IP Dictionary

原理

实例

时空效率

冲突

冲突 vs. 装填因子

冲突 vs. 散列函数

散列策略：模余法

散列策略：更多方法

散列策略：（伪）随机数法

6.Hashing.B.Collision.pdf

6. 散列

生日悖论

普遍存在的冲突

解决冲突：多槽位法

解决冲突：链地址法

解决冲突：公共溢出区法

解决冲突：开放定址策略

解决冲突：线性试探法

解决冲突：平方试探法

解决冲突：双向平方试探法

解决冲突：（伪）随机探测法

解决冲突：再散列法

开放定址 & 懒惰删除

预防冲突：重散列

6.Hashing.C.Karp-Rabin.pdf

6. 散列

凡物皆数

串亦为数

数位溢出

Karp-Rabin：散列压缩

Karp-Rabin：散列冲突

Karp-Rabin：快速指纹计算

6.Hashing.D.Bucketsort+Radixsort.pdf

6. 散列

桶排序：简单情况

桶排序：一般情况

MaxGap

基数排序：策略与算法

基数排序：正确性与性能

整数排序

6.Hashing.X.Md5.pdf

6. 散列

MD5

散列指纹

MD5算法

课后

6.Hashing.Y.Languages.pdf

6. 散列

Java : hashCode()

Java : HashMap + Hashtable

Perl : %Hash Type

Python : Dictionary Class

Ruby : Hash Table

课后

7.Pq.A.Basic Implementation.pdf

7. 优先队列

优先队列

应用、算法与特点

向量实现

列表实现

更好的实现

7.Pq.B.Binary Heap.pdf

7. 优先队列

二叉堆：结构性

二叉堆：堆序性

插入与上滤：算法

插入与上滤：效率

删除与下滤：算法

删除与下滤：效率

堆的构造：自顶而下的上滤

堆的构造：自底而上的下滤

课后

7.Pq.C.Selectionsort.pdf

7. 优先队列

构思

算法

性能

7.Pq.D.Tournamentsort.pdf

7. 优先队列

锦标赛树

算法

实例

实现与效率

课后

7.Pq.E.Heapsort.pdf

7. 优先队列

堆排序

堆的创建

堆的调整

就地堆排序

实例：建堆

实例：选取+调整

堆排序：综合评价

7.Pq.X.Leftist Heap.pdf

7. 优先队列

堆合并

单侧倾斜

空节点距离

左倾性 & 左式堆

右侧链长度 vs. 节点数

合并算法

实例：递归

实例：左右交换

Merge(A, B)

课后

8.Graph.0.Introduction.pdf

8. 图

术语

无向图 / 有向图

路径 / 回路

树 / 森林

有向无环图

生成树 / 带权网络 / 最小生成树

抽象数据类型

8.Graph.A.Implementation.pdf

8. 图

邻接矩阵

邻接矩阵：例子

邻接矩阵：优点

邻接矩阵：缺点

邻接表

邻接表：例子

邻接表：空间复杂度

邻接表：复杂度

十字链表：实现

十字链表：例子

十字链表：算法

十字链表：复杂度

取舍原则

8.Graph.B.BFS.pdf

8. 图

算法概要

迭代实现

BFS(Graph G)

实例（无向图）

树边 & 跨边

BFS树/森林

复杂度

可达性

最短路径

最短路径：算法&实现

8.Graph.C.DFS.pdf

8. 图

算法概要

全局标志

DFSearch(Graph G, void (*Visit)(int v))

DFS(Graph G, int u)

无向图

有向图

复杂度

DFS树/森林

时间标签

边分类

8.Graph.D.GenericSearch.pdf

8. 图

栈式遍历

通用算法

应用

8.Graph.E.Topological sorting.pdf

8. 图

有向无环图

拓扑排序

存在性

算法

实现与复杂度

另一算法

8.Graph.F.Bi-connectivity.pdf

8. 图

关节点 & 双连通分量

Brute-Force

根顶点

内顶点

DFS()的扩展

DFS_BiconnectedComponent(Graph G)

DFS_BC(Graph G, int v)

DFS_BC(Graph G, int u)

实例

复杂度

8.Graph.G.Mst.pdf

8. 图

生成树 & 最小生成树

MST

Brute-force

Prim：原理

Prim：算法

Prim：实现

Prim：复杂度

Kruskal：贪心策略

Kruskal：框架

Kruskal：正确性

Kruskal：排序

Kruskal：回路检测

Kruskal：树合并

Kruskal：Union-Find

Kruskal：复杂度

其它算法

更新结果

8.Graph.H.Sp.pdf

8. 图

问题描述

问题分类

E. W. Dijkstra

单源点：SPT

单源点：SPT  MST

单源点：s1

单源点：s2

单源点：sk

单源点：Dijkstra：构思

单源点：Dijkstra：实例

单源点：Dijkstra：实例：SPT0

单源点：Dijkstra：实例：SPT1

单源点：Dijkstra：实例：SPT2

单源点：Dijkstra：实例：SPT3

单源点：Dijkstra：实例：SPT4

单源点：Dijkstra：实例：SPT5

单源点：Dijkstra：实例：SPT6

单源点：Dijkstra：实现

单源点：Dijkstra：复杂度

多起点：从 Dijkstra 到 Floyd-Warshall

多起点：问题特点

多起点：递归

多起点：Floyd-Warshall：动态规划

多起点：Floyd-Warshall：算法

多起点：Floyd-Warshall：例子&实现

多起点：Floyd-Warshall：复杂度

8.Graph.X.Maxflow.pdf

8. 图

网络流

最大流

残余图

增强路径

残余图：性质

Ford-Fulkerson

Ford-Fulkerson：实例

Ford-Fulkerson：复杂度

Edmonds-Karp

9.Sorting.A.Quicksort.pdf

9. 排序

快速排序

轴点

构造轴点：思路

构造轴点：实现

子序列的排序

复杂度

改进

9.Sorting.B.Mergesort.pdf

9. 排序

归并排序

实现

复杂度

综合评价

9.Sorting.C.Selection+Median.pdf

9. 排序

Median & Selection

QuickSelect(A[],n,k)

SeqSelect(S,k)

Sequential Select: Analysis

Parallel Select: Problem

ParallelSelect(S, k)

Parallel Select: Analysis

9.Sorting.D.Shellsort.pdf

9. 排序

Shellsort

Implementation

Complexity: Basic

Complexity: Orderedness

Upper Bound - PS Sequence

Upper Bound - Pratt's Sequence

Step Sequences: Pros & Cons

0.A.syllabus................................................................[1] 3.String.a.representation+implementation .......... [214] 0.B.introduction.........................................................[9] 3.String.b.pm......................................................... [221] 0.C.big‐o...................................................................[17] 3.String.c.kmp ....................................................... [231] 0.D.algorithm_analysis ............................................[34] 3.String.d.bm......................................................... [251] 0.X.sorting+lower Bound .........................................[56] 4.Trees.a.introduction........................................... [266] 1.Sequence.a.adt+interface.....................................[66] 4.Trees.b.binary Tree ............................................ [283] 1.Sequence.b.vector ................................................[79] 4.Trees.c.preorder Traversal ................................. [291] 1.Sequence.c.list......................................................[90] 4.Trees.d.inorder Traversal ................................... [300] 1.Sequence.d.cursor ..............................................[105] 4.Trees.e.postorder Traversal ............................... [308] 1.Sequence.e.application ......................................[110] 4.Trees.f.breadth‐first Traversal............................ [319] 1.Sequence.f.ordered Vector.................................[114] 4.Trees.g.huffman Tree ......................................... [324] 1.Sequence.g.insertionsort....................................[131] 5.Bst.a.binary Search Tree..................................... [341] 1.Sequence.x.java Implementation .......................[138] 5.Bst.b.avl Tree...................................................... [353] 1.Sequence.y.skiplist .............................................[145] 5.Bst.c.splay Tree .................................................. [371] 2.Stacks+queues.a.stack ........................................[158] 5.Bst.d.b‐tree ........................................................ [390] 2.Stacks+queues.b.applications.............................[167] 5.Bst.e.red‐black Tree ........................................... [411] 2.Stacks+queues.c.recursion .................................[185] 5.Bst.x.kd‐tree ....................................................... [431] 2.Stacks+queues.d.probe‐backtrack......................[196] 6.Hashing.a.hashing .............................................. [450] 2.Stacks+queues.e.queue ......................................[208] 6.Hashing.b.collision.............................................. [465]

6.Hashing.c.karp‐rabin...........................................[480] 8.Graph.x.maxflow ................................................ [684] 6.Hashing.d.bucketsort+radixsort .........................[488] 9.Sorting.a.quicksort ............................................. [695] 6.Hashing.x.md5 ....................................................[497] 9.Sorting.b.mergesort ........................................... [704] 6.Hashing.y.languages ...........................................[503] 9.Sorting.c.selection+median................................ [709] 7.Pq.a.basic Implementation .................................[510] 9.Sorting.d.shellsort .............................................. [723] 7.Pq.b.binary Heap ................................................[516] 7.Pq.c.selectionsort ...............................................[527] 7.Pq.d.tournamentsort ..........................................[531] 7.Pq.e.heapsort .....................................................[537] 7.Pq.x.leftist Heap..................................................[546] 8.Graph.0.introduction ..........................................[557] 8.Graph.a.implementation ....................................[565] 8.Graph.b.bfs .........................................................[580] 8.Graph.c.dfs .........................................................[593] 8.Graph.d.genericsearch........................................[612] 8.Graph.e.topological Sorting................................[618] 8.Graph.f.bi‐connectivity .......................................[625] 8.Graph.g.mst ........................................................[638] 8.Graph.h.sp ..........................................................[657]

0. 绪论 (a) 课程简介邓俊辉 deng@tsinghua.edu.cn 2010年6月14日星期一 - 1 -

FAQ：教师主讲：邓俊辉，deng@tsinghua.edu.cn 助教 00240074 于泽，fish266@gmail.com 30240184 李锐喆，liruizhe@gmail.com 白彦冰，yanbing.bai@gmail.com Data Structures & Algorithms (Spring 2010), Tsinghua University 1 - 2 -

FAQ：选修，还是不选修目标定位——是否需要选修数据结构程序设计语言：编写出合法的程序数据结构与算法：实现高效处理大规模数据的算法软件工程：参与团队编写大规模、复杂、鲁棒和高效的软件基本条件——可否选修数据结构已修C语言程序设计，有一定的编程基础通过作业0进一步自我测试更多条件——能否学好数据结构对计算机科学与应用的兴趣目标明确，心态平和多思考、多动手、多讨论的习惯投入落实，持之以恒 Data Structures & Algorithms (Spring 2010), Tsinghua University 2 - 3 -

FAQ：考评及要求考核形式 = 编程实验 + 测验/考试 + 加分 //00240074、30240184 根据实际情况，期末可能做总体微调编程实验在提供的范围内选做，积分累计在线试测，限时提交 //特殊情况须提前寄出MD5或请假白盒、黑盒测试结合，结果正确性兼顾代码质量测验/考试基本知识点的掌握基本方法和技巧的灵活运用加分课堂参与 + 课后交流 + 作业创意 + 独立思考 //比如，发现讲义、教参、示例程序中的实质性问题学术诚信：题分倒扣，双方同论；丑话在先，请勿试法 Data Structures & Algorithms (Spring 2010), Tsinghua University 3 - 4 -

FAQ：学习资料以讲义为主：善于笔记，独立思考 //期末让我看看你的笔记？以参考书为辅 DSC ‐ 数据结构（C语言版），严蔚敏等，清华大学出版社 ISBN: 7‐302‐02368‐5（￥22）或 7‐302‐14751‐0（￥30附CD）数据结构：数据结构与算法分析，M. A. Weiss原著，陈越改编人民邮电出版社，2005年8月, ISBN: 7‐115‐13984‐9 数据结构基础（C语言版）第2版，E. Horowitz等著，朱仲涛译清华大学出版社，ISBN: 9787‐302‐18696‐0 面向对象：数据结构与算法（Java描述），邓俊辉机械工业出版社，2006年2月, ISBN: 7‐111‐18204‐9 Data Structures & Algorithms (Spring 2010), Tsinghua University 4 - 5 -

FAQ：学习资源网络学堂课程信息与通知讲义、示例代码讨论组 //认真阅读，对比体会，扩充改进 //多参与，多受益演示程序 http://vis.cs.tsinghua.edu.cn/~deng/ds/demo/ http://java.com 同一结构和算法，具体实现不尽相同，要融会贯通 //Java Runtime Environment 在线资源 http://www.cs.hope.edu/alganim/ccaa http://www2.hig.no/~algmet//animate.html http://www.noi.cn http://www.topcoder.com google(“data structures & algorithms”) //算法演示总汇 //R. Sedgewick //中学生程序设计竞赛，不可小视 //编程？从爱好者到高手！ //... Data Structures & Algorithms (Spring 2010), Tsinghua University 5 - 6 -

分享到：

赞收藏

资料库

清华大学邓俊辉数据结构讲义.pdf

相关推荐

课程资源

热门标签

最新资料