来自清华大学邓俊辉教授的数据结构讲义

绪论

  1. 计算

Computer science should be called computing science, for the same reason why surgery is not called knife science. —— E. Dijkstra

  1. 计算模型

To measure is to know. If you can not measure it,you can not improve it. —— Lord Kelvin

  1. 大O记号

Mathematics is more in need of good notations than of new theorems. —— Alan Turing

好读书不求甚解 每有会意，便欣然忘食 —— 陶渊明

  1. 算法分析

He calculated just as men breath, as eagle sustain themselves in the air. —— Francois Arago

  1. 迭代与递归

迭代乃人工，递归方神通 To iterate is human, to recurse, divine.

凡治众如治寡，分数是也 The control of a large force is the same principle as the control of a few men: it is merely a question of dividing up their numbers.

  1. 局限

不学诗，何以言 不学礼，何以立 —— 《论语》

  1. 排序与下界

两个吃罢饭，又走了四五十里，却来到一市镇上，地名唤做瑞龙镇，却是个三岔路口。宋江借问那里人道：“小人们欲投二龙山、清风镇上，不知从那条路去？” —— 《水浒传》

不怕不识货，就怕货比货

向量

  1. 有序向量：唯一化

Everybody is different. Everybody has different styles. Just do the best way you know how. —— Vince Carter

  1. 有序向量：二分查找

群猴道：“自从爷爷去后，这山被二郎菩萨点上火，烧杀了大半。我们蹲在井里，钻在涧内，藏于铁板桥下，得了性命。及至火灭烟消，出来时，又没花果养赡，难以存活，别处又去了一半。我们这一半，捱苦的住在山中，这两年，又被些打猎的抢了一半去也。” —— 《西游记》

  1. 归并排序

I think there is a world market for about five computers. —— T.J.Watson, 1943

天下大势，分久必合，合久必分 —— 《三国演义》

列表

  1. 接口与实现

Don’t lose the link. —— Robin Milner

  1. 选择排序

当下又选了几样果菜与凤姐送去，凤姐儿也送了几样来 —— 《红楼梦》

  1. 插入排序

一语未了,只见宝玉笑嘻嘻了一枝红梅进来,众丫鬟忙已接过,插入瓶内 —— 《红楼梦》

  1. 归并排序

四牡孔阜,六辔在手 骐骝是中,騧骊是骖 龙盾之合,鋈以觼軜 —— 《国风·秦风·小戎》

曰两美其必合兮,孰信修而慕之？ 思九州之博大兮,岂惟是其有女？ —— 《离骚》

栈与队列

  1. 栈接口与实现

陛下用群臣，如积薪耳，后来者居上 —— 《史记·汲郑列传》

  1. 栈应用：进制转换

Hickory,Dickory,Dock The mouse ran up the clock —— Nursery Rhyme Medly

  1. 栈应用：中缀表达式求值

知实而不知名，知名而不知实，皆不知也 —— 王夫之

  1. 逆波兰表达式

将欲去之，必固举之 将欲夺之，必固予之 将欲灭之，必先学之 —— 《老子》

  1. 试探回溯法：迷宫寻径

When all else fails, try brute-force. —— Anonymous

No matter where they take us, we’ll find our way back. —— “No matter what”, Boyzone

二叉树

  1. 树

Two roads diverged in a yellow wood And sorry I could not travel both —— Robin Frost, 1915

  1. 先序遍历

真君曰：“昔吕洞宾居庐山而成仙，鬼谷子居云梦而得道，今或无此吉地么？” 璞曰：“有！但当遍历耳。” —— 《警世通言》

  1. 后序遍历

大宗百世不迁，小宗五世则迁 —— 《礼记·大传》

二叉搜索树

  1. 概述

here’s nothing hidden in your head The Sorting Hat can’t see, So try me on and I will tell you Where you ought to be. —— Harry Potter and The Sorcecer’s Stone

待续