第1章数据结构绪论

Size: px

Start display at page:

Download "第1章数据结构绪论"

我抗颜
5 years ago
Views:

1 目录第 1 章数据结构绪论开场白 2 如果你交给某人一个程序, 你将折磨他一整天 ; 如果你教某人如何编写程序, 你将折磨他一辈子 1.2 你数据结构怎么学的? 3 他完成开发并测试通过后, 得意地提交了代码项目经理看完代码后拍着桌子对他说 : 你数据结构是怎么学的? 1.3 数据结构起源基本概念和术语 5 正所谓巧妇难为无米之炊, 再强大的计算机, 也要有米下锅才可以干活, 否则就是一堆破铜烂铁这个米就是数据数据数据元素数据项数据对象数据结构逻辑结构与物理结构逻辑结构物理结构抽象数据类型 11 大家都需要房子住, 但显然没钱考虑大房子是没有意义的于是商品房就出现了各种各样的户型, 有几百平米的别墅, 也有仅两平米的胶囊公寓数据类型抽象数据类型总结回顾 14 9

2 大话数据结构 1.8 结尾语 15 最终的结果一定是, 你对着别人很牛的说数据结构就那么回事第 2 章算法 17 算法实际操作数量不同算法的操作数量对比 n*n n 1 问题输入规模 n 2.1 开场白数据结构与算法关系 18 计算机界的前辈们, 是一帮很牛很牛的人, 他们使得很多看似没法解决或者很难解决的问题, 变得如此美妙和神奇 2.3 两种算法的比较 19 高斯在上小学的一天, 老师要求每个学生都计算的结果, 谁先算出来谁先回家 2.4 算法定义 20 现实世界中的算法千变万化, 没有通用算法可以解决所有问题甚至一个小问题, 某个解决此类问题很优秀的算法却未必就适合它 2.5 算法的特性输入输出有穷性确定性可行性算法设计的要求 22 求 100 个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异, 我们自然追求高效率和低存储的算法来解决问题正确性可读性健壮性时间效率高和存储量低

3 2.7 算法效率的度量方法 24 随着 n 值越来越大, 它们在时间效率上的差异也就越来越大好比有些人每天都在学习, 而另一些人, 打打游戏睡睡大觉, 毕业后前者名企争着要, 后者求职处处无门事后统计方法事前分析估算方法函数的渐近增长算法时间复杂度 29 理解大 O 推导不算难, 难的其实是对数列的一些相关运算, 这考察的更多的是数学知识和能力算法时间复杂度定义推导大 O 阶方法常数阶线性阶对数阶平方阶常见的时间复杂度 35 有些时候, 告诉你某些东西不可以去尝试, 也是一种知识的传递总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧 2.11 最坏情况与平均情况算法空间复杂度 36 事先建立一个有 2050 大的数组, 然后把所有年份按下标数字对应, 如果是闰年, 此数组项的值就是 1, 如果不是就是 0 这样, 所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题 2.13 总结回顾结尾语 38 愚公移山固然可敬, 但发明炸药和推土机, 可能更加实在和聪明第 3 章线性表 41 11

4 大话数据结构 3.1 开场白 42 门外家长都挤在大门口与门里的小孩子的井然有序, 形成了鲜明对比哎, 有时大人的所作所为, 其实还不如孩子 3.2 线性表的定义线性表的抽象数据类型 45 有时我们想知道某个小朋友 ( 比如麦兜 ) 是否是班级的同学, 老师会告诉我说, 没有, 麦兜是在春田花花幼儿园里这种查找某个元素是否存在的操作很常用 3.4 线性表的顺序存储结构 47 他每次一吃完早饭就冲着去了图书馆, 挑一个好地儿, 把他书包里的书, 一本一本的按座位放好, 长长一排, 九个座硬是被他占了顺序存储定义顺序存储方式数据长度与线性表长度区别地址计算方法顺序存储结构的插入与删除 50 春运时去买火车票, 大家都排队排着好好的, 这时来了一个美女 : 可否让我排在你前面? 这可不得了, 后面的人像蠕虫一样, 全部都得退后一步获得元素操作插入操作删除操作线性表顺序存储结构的优缺点线性表的链式存储结构 55 反正也是要让相邻元素间留有足够余地, 那干脆所有元素都不要考虑相邻位置了, 哪有空位就到哪里而只是让每个元素知道它下一个元素的位置在哪里顺序存储结构不足的解决办法线性表链式存储结构定义头指针与头结点的异同线性表链式存储结构代码描述单链表的读取单链表的插入与删除 61 本来是爸爸左牵着妈妈的手右牵着宝宝的手在马路边散步突然迎面走来一美女, 爸爸失神般地望着, 此情景被妈妈逮个正着, 于是扯开父子俩, 拉起宝宝的左手就快步朝前走去单链表的插入单链表的删除单链表的整表创建 66 12

目录 3.10 单链表的整表删除 69 3.11 单链表结构与顺序存储结构优缺点 70 3.

..75 3.12.3 静态链表优缺点... 77 3.13 循环链表 78 这个轮回的思想很有意思它强调了不管你今生是穷是富, 如果持续行善积德, 下辈子就会好过, 反之就会遭到报应 3.

5 目录 3.10 单链表的整表删除单链表结构与顺序存储结构优缺点静态链表 71 对于一些语言, 如 Basic Fortran 等早期的编程高级语言, 由于没有指针, 这链表结构, 按照前面我们的讲法, 它就没法实现了怎么办呢? 静态链表的插入操作静态链表的删除操作静态链表优缺点循环链表 78 这个轮回的思想很有意思它强调了不管你今生是穷是富, 如果持续行善积德, 下辈子就会好过, 反之就会遭到报应 3.14 双向链表 81 就像每个人的人生一样, 欲收获就得付代价双向链表既然是比单链表多了如可以反向遍历查找等的数据结构, 那么也就需要付出一些小的代价 3.15 总结回顾结尾语 85 如果你觉得上学读书是受罪, 假设你可以活到 80 岁, 其实你最多也就吃了 20 年苦用人生四分之一的时间来换取其余时间的幸福生活, 这点苦不算啥第 4 章栈与队列 87

6 大话数据结构 4.1 开场白 88 想想看, 在你准备用枪的时候, 突然这手枪明明有子弹却打不出来, 这不是要命吗 4.2 栈的定义 89 类似的很多软件, 比如 Word Photoshop 等, 都有撤消 (undo) 的操作, 也是用栈这种思想方式来实现的栈的定义进栈出栈变化形式栈的抽象数据类型栈的顺序存储结构及实现栈的顺序存储结构栈的顺序存储结构进栈操作栈的顺序存储结构出栈操作两栈共享空间 94 两个大学室友毕业同时到北京工作, 他们都希望租房时能找到独自住的一室户或一室一厅, 可找来找去发现, 实在是承受不起 4.6 栈的链式存储结构及实现栈的链式存储结构栈的链式存储结构进栈操作栈的链式存储结构出栈操作栈的作用栈的应用递归 100 当你往镜子前面一站, 镜子里面就有一个你的像但你试过两面镜子一起照吗? 如果 A B 两面镜子相互面对面放着, 你往中间一站, 嘿, 两面镜子里都有你的千百个化身斐波那契数列实现递归定义栈的应用四则运算表达式求值后缀 ( 逆波兰 ) 表示法定义后缀表达式计算结果中缀表达式转后缀表达式队列的定义 111 电脑有时会处于疑似死机的状态就当你失去耐心, 打算了 Reset 时突然它像酒醒了一样, 把你刚才点击的所有操作全部都按顺序执行了一遍 14

7 目录 4.11 队列的抽象数据类型循环队列 113 你上了公交车发现前排有两个空座位, 而后排所有座位都已经坐满, 你会怎么做? 立马下车, 并对自己说, 后面没座了, 我等下一辆? 没这么笨的人, 前面有座位, 当然也是可以坐的队列顺序存储的不足循环队列定义队列的链式存储结构及实现队列链式存储结构入队操作队列链式存储结构出队操作总结回顾结尾语 121 人生, 需要有队列精神的体现南极到北极, 不过是南纬 90 度到北纬 90 度的队列, 如果你中途犹豫, 临时转向, 也许你就只能和企鹅相伴永远可事实上, 无论哪个方向, 只要你坚持到底, 你都可以到达终点第 5 章串开场白 124 枯眼望遥山隔水, 往来曾见几心知? 壶空怕酌一杯酒, 笔下难成和韵诗途路阻人离别久, 讯音无雁寄回迟孤灯夜守长寥寂, 夫忆妻兮父忆儿可再仔细一读发现, 这首诗竟然可以倒过来读 5.2 串的定义 124 我所提到的 over end lie 其实就是 lover friend believe 这些单词字符串的子串 5.3 串的比较串的抽象数据类型 127

8 大话数据结构 5.5 串的存储结构 128 感情上发生了问题, 为了向女友解释一下, 我准备发一条短信, 一共打了 75 个字最后八个字是我恨你是不可能的, 点发送后来得知对方收到的, 只有 70 个字, 短信结尾是我恨你串的顺序存储结构串的链式存储结构朴素的模式匹配算法 131 主串为 S= , 而要匹配的子串为 T= , 在匹配时, 每次都得将 T 中字符循环到最后一位才发现, 哦, 原来它们是不匹配的 5.7 KMP 模式匹配算法 135 很多年前我们的科学家觉得像这种有多个 0 和 1 重复字符的字符串, 却需要挨个遍历的算法, 是非常糟糕的事情 KMP 模式匹配算法原理 next 数组值推导 KMP 模式匹配算法实现 KMP 模式匹配算法改进 nextval 数组值推导总结回顾结尾语 146 璇玑图共八百四十字, 纵横各二十九字, 纵横斜交互正反读或退一字迭一字读均可成诗, 诗有三四五六七言不等, 目前有人统计可组成七千九百五十八首诗听清楚哦, 是 7958 首第 6 章树

9 目录 6.1 开场白 150 无论多高多大的树, 那也是从小到大的, 由根到叶, 一点点成长起来的俗话说十年树木, 百年树人, 可一棵大树又何止是十年这样容易 6.2 树的定义 150 树的定义其实就是我们在讲解栈时提到的递归的方法也就是在树的定义之中还用到了树的概念, 这是比较新的一种定义方法结点分类结点间关系树的其他相关概念树的抽象数据类型树的存储结构双亲表示法孩子表示法孩子兄弟表示法二叉树的定义 163 苏东坡曾说 : 人有悲欢离合, 月有阴晴圆缺, 此事古难全意思就是完美是理想, 不完美才是人生我们通常举的例子也都是左高右低参差不齐的二叉树那是否存在完美的二叉树呢? 二叉树特点特殊二叉树二叉树的性质二叉树性质二叉树性质二叉树性质二叉树性质二叉树性质二叉树的存储结构二叉树顺序存储结构二叉链表遍历二叉树 174 你人生的道路上, 高考填志愿要面临哪个城市哪所大学具体专业等选择, 由于选择方式的不同, 遍历的次序就完全不同二叉树遍历原理二叉树遍历方法前序遍历算法中序遍历算法后序遍历算法推导遍历结果

10 目录 6.9 二叉树的建立线索二叉树 188 我们现在提倡节约型社会, 一切都应该节约为本对待我们的程序当然也不例外, 能不浪费的时间或空间, 都应该考虑节省线索二叉树原理线索二叉树结构实现树森林与二叉树的转换 195 有个乡镇企业也买了同样的生产线, 老板发现这个问题后找了个小工来说 : 你必须搞定, 不然炒你鱿鱼小工很快想出了办法 : 他在生产线旁边放了台风扇猛吹, 空皂盒自然会被吹走树转换为二叉树森林转换为二叉树二叉树转换为树二叉树转换为森林树与森林的遍历赫夫曼树及其应用 200 压缩而不出错是如何做到的呢? 简单的说, 就是把我们要压缩的文本进行重新编码, 以达到减少不必要的空间的技术压缩和解压缩技术就是基于赫夫曼的研究之上发展而来, 我们应该记住他赫夫曼树赫夫曼树定义与原理赫夫曼编码总结回顾结尾语 209 人受伤时会流下泪水树受伤时, 天将再不会哭希望我们的未来不要仅仅是钢筋水泥建造的高楼, 也要有那郁郁葱葱的森林和草地, 我们人类才可能与自然和谐共处 18

11 大话数据结构第 7 章图开场白 212 如果你不善于规划, 很有可能就会出现如玩好新疆后到海南, 然后再冲向黑龙江这样的荒唐决策 7.2 图的定义 213 现实中, 人与人之间关系就非常复杂, 比如我的认识的朋友, 可能他们之间也互相认识, 这就不是简单的一对一一对多的关系了, 那就是我们今天要研究的主题图各种图定义图的顶点与边间关系连通图相关术语图的定义与术语总结图的抽象数据类型图的存储结构 223 因为美国的黑夜就是中国的白天, 利用互联网, 他的员工白天上班就可以监控到美国仓库夜间的实际情况, 如果发生了像火灾偷盗这样的突发事件, 及时电话到美国当地相关人员处理邻接矩阵邻接表十字链表邻接多重表边集数组图的遍历 237 我有一天早晨准备出门, 发现钥匙不见了一定是我儿子拿着玩, 不知道丢到哪个犄角旮旯去了, 你们说, 我应该如何找? 深度优先遍历广度优先遍历

13 目录 7.6 最小生成树 245 如果你加班加点, 没日没夜设计出的结果是方案一, 我想你离被炒鱿鱼应该是不远了 ( 同学微笑 ) 因为这个方案比后两个方案一半还多的成本会让老板气晕过去的普里姆 (Prim) 算法克鲁斯卡尔 (Kruskal) 算法最短路径 257 有人为了省钱, 需路程最短, 但换乘站间距离长等原因并不省时间 ; 另一些人, 他为赶时间, 最大的需求是总时间要短 ; 还有一类人, 他们都不想多走路, 关键是换乘要少, 这样可以在车上好好休息一下迪杰斯特拉 (Dijkstra) 算法弗洛伊德 (Floyd) 算法拓扑排序 270 电影制作不可能在人员到位进驻场地时, 导演还没有找到, 也不可能在拍摄过程中, 场地都没有这都会导致荒谬的结果拓扑排序介绍拓扑排序算法关键路径 277 假如造一个轮子要 0.5 天造一个发动机要 3 天造一个车底盘要 2 天造一个外壳要 2 天, 其它零部件 2 天, 全部零部件集中到一处要 0.5 天, 组装成车要 2 天, 请问, 在汽车厂造一辆车, 最短需要多少天呢? 关键路径算法原理关键路径算法总结回顾结尾语 289 世界上最遥远的距离, 不是牛 A 与牛 C 之间狭小空隙, 而是你们当中, 有人在通往牛逼的路上一路狂奔, 而有人步入大学校园就学会放弃第 8 章查找

14 大话数据结构 8.1 开场白 292 当你精心写了一篇博文或者上传一组照片到互联网上, 来自世界各地的无数蜘蛛便会蜂拥而至所谓蜘蛛就是搜索引擎公司服务器上软件, 它把互联网当成了蜘蛛网, 没日没夜的访问上面的各种信息 8.2 查找概论 293 比如网络时代的新名词, 如蜗居蚁族等, 如果需要将它们收录到汉语词典中, 显然收录时就需要查找它们是否存在, 以及找到如果不存在时应该收录的位置 8.3 顺序表查找顺序表查找算法顺序表查找优化有序表查找 298 我在纸上已经写好了一个 100 以内的正整数请你猜, 问几次可以猜出来当时已经介绍了如何才可以最快的猜出这个数字我们把这种每次取中间记录查找的方法叫做折半查找折半查找插值查找斐波那契查找线性索引查找 306 我母亲年纪大了, 经常在家里找不到东西, 于是她用一小本子, 记录了家里所有小东西放置的位置, 比如户口本放在右手床头柜下面抽屉中, 钞票放在衣咳, 这个就不提了稠密索引分块索引倒排索引二叉排序树 313 后来老虎来了, 一人拼命地跑, 另一人则急中生智, 爬到了树上而老虎是不会爬树的, 结果爬树者改变了跑的思想, 这一改变何等重要, 捡回了自己的一条命二叉排序树查找操作二叉排序树插入操作二叉排序树删除操作二叉排序树总结平衡二叉树 (AVL 树 ) 328 平板就是一个世界, 当诱惑降临, 人心中的平衡被打破, 世界就会混乱, 最后留下的只有孤独寂寞失败这种单调的机械化的社会, 禁不住诱惑的侵蚀, 最容易被侵蚀的, 恰恰是最空虚的心灵平衡二叉树实现原理平衡二叉树实现算法

15 目录 8.8 多路查找树 (B 树 ) 341 要观察一个公司是否严谨, 看他们如何开会就知道了如果开会时每一个人都只是带一张嘴, 即兴发言, 这肯定是一家不严谨的公司树树 B 树 B+ 树散列表查找 ( 哈希表 ) 概述 353 你很想学太极拳, 听说学校有个叫张三丰的人打得特别好, 于是到学校学生处找人, 工作人员拿出学生名单, 最终告诉你, 学校没这个人, 并说张三丰几百年前就已经在武当山作古了散列表查找定义散列表查找步骤散列函数的构造方法直接定址法数字分析法平方取中法折叠法除留余数法随机数法处理散列冲突的方法 360 我们每个人都希望身体健康, 虽然疾病可以预防, 但不可避免, 没有任何人可以说, 生下来到现在没有生过一次病开放定址法再散列函数法链地址法公共溢出区法散列表查找实现散列表查找算法实现散列表查找性能分析总结回顾结尾语 369 如果我是个喜欢汽车的人, 时常搜汽车信息那么当我在搜索框中输入甲壳虫美洲虎等关键词时, 不要让动物和人物成为搜索的头条 13

16 大话数据结构第 9 章排序开场白 374 假如我想买一台 iphone4 的手机, 于是上了某电子商务网站去搜索可搜索后发现, 有 8863 个相关的物品, 如此之多, 这叫我如何选择我其实是想买便宜一点的, 但是又怕遇到骗子, 想找信誉好的商家, 如何做? 9.2 排序的基本概念与分类 375 比如我们某些大学为了选拔在主科上更优秀的学生, 要求对所有学生的所有科目总分倒序排名, 并且在同样总分的情况下将语数外总分做倒序排名这就是对总分和语数外总分两个次关键字的组合排序排序的稳定性内排序与外排序排序用到的结构与函数冒泡排序 378 无论你学习哪种编程语言, 在学到循环和数组时, 通常都会介绍一种排序算法, 而这个算法一般就是冒泡排序并不是它的名称很好听, 而是说这个算法的思路最简单, 最容易理解最简单排序实现冒泡排序算法冒泡排序优化冒泡排序复杂度分析简单选择排序 384 还有一种做股票的人, 他们很少出手, 只是在不断观察和判断, 等时机一到, 果断买进或卖出他们因为冷静和沉着, 以及交易的次数少, 而最终收益颇丰简单选择排序算法简单选择排序复杂度分析直接插入排序 386 哪怕你是第一次玩扑克牌, 只要认识这些数字, 理牌的方法都是不用教的将 3 和 4 移动到 5 的左侧, 再将 2 移动到最左侧, 顺序就算是理好了这里, 我们的理牌方法, 就是直接插入排序法直接插入排序算法直接插入排序复杂度分析

17 目录 9.6 希尔排序 389 不管怎么说, 希尔排序算法的发明, 使得我们终于突破了慢速排序的时代 ( 超越了时间复杂度为 O(n 2 )), 之后, 更为高效的排序算法也就相继出现了希尔排序原理希尔排序算法希尔排序复杂度分析堆排序 396 什么叫堆结构呢? 回忆一下我们小时候, 特别是男同学, 基本都玩过叠罗汉的恶作剧通常都是先把某个要整的人按倒在地, 然后大家就一拥而上扑了上去后果? 后果当然就是一笑了之堆排序算法堆排序复杂度分析归并排序 406 即使你是你们班级第一甚至年级第一名, 如果你没有上分数线, 则说明你的成绩排不到全省前 1 万名, 你也就基本失去了当年上本科的机会了归并排序算法归并排序复杂度分析非递归实现归并排序快速排序 417 终于我们的高手要登场了, 将来你工作后, 你的老板让你写个排序算法, 而你会的算法中竟然没有快速排序, 我想你还是不要声张, 偷偷去把快速排序算法找来敲进电脑, 这样至少你不至于被大伙儿取笑快速排序算法快速排序复杂度分析快速排序优化总结回顾 428 目前还没有十全十美的排序算法, 有优点就会有缺点, 即使是快速排序法, 也只是在整体性能上优越, 它也存在排序不稳定需要大量辅助空间对少量数据排序无优势等不足 9.11 结尾语 430 如果你有梦想的话, 就要去捍卫它当别人做不到的时候, 他们就想要告诉你, 你也不能如果你想要些什么, 就得去努力争取就这样! 附录参考文献

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378> B212CC: 数据结构与算法课程描述 0 课程基本信息课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3

第1章 数据结构绪论

第1章数据结构绪论