超牛《数据结构》笔记 张明瑞 清华大学 计算机科学与技术专业 大_第1页
超牛《数据结构》笔记 张明瑞 清华大学 计算机科学与技术专业 大_第2页
超牛《数据结构》笔记 张明瑞 清华大学 计算机科学与技术专业 大_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、超牛数据结构笔记 张明瑞 清华大学 计算机科学与技术专业 大 授课教师：邓俊辉 教师介绍：清华xxxx年度十大优秀老师！mooc上数据结构公开课报名已超5万人！你还不来看 笔记简介：哈希表，红黑树，斐波那契二分查找，从基本到高端的数据结构全都有！有重点，有插图，还有鄙人学习感悟，看完这笔记中的战斗机你还想啥！ 20140603 adt是抽象数据类型，为一组数据模型，加上一组操作，不涉及具体的储存方式，就像是用户使用的产品（作，并且封装了许多操作，比如remove(r),sort(),search(e)无序去重,deduplicate(),uniquify()有序去重,traverse()遍历

2、search(n) 返回不大于n的元素的最后的rank put(a,b) 将rank为a的数改为b 平均复杂度：根据数据结构个操作出现概率分布进行加权平均，每个操作作为独立事件，割裂了相关性与连贯性 分摊复杂度：将数据结构连续地实施足够多的操作，所需总体成本分摊至单次操作。对一系列操作整体考量，更加精确。 vector 插入算法： 从固定插入位置开始，先扩容，然后从rank = n downto 固定位置k vectorn = vectorn-1逐个后移 最后执行插入。 vector 删除： 区间删除： 删除从lo 到 hi 的区间 则执行如下： _elemlo+ = elemhi+ 即从前向

3、后逐次移位 不能更改次序，因为如果要删除的区间与想向前移动的区间有重复区间，从后向前的话会覆盖掉重复区间的部分。 有序相向量的唯一化 低效版： 有序向量，重复的元素构成一个区间，因此每个区间保留一个即可。 于是可以从前向后依次检查来逐个删除相同元素 o(n) 高效版： 成批删除雷同元素，将他们视为一个整体。 i = j = 0 如果二者不相等，则_elem+i = _elem+j，相当于忽略了所有重复元素（没有直接显示调用删除）。 _ fabonacci查找法： 由于二分查找在大于、小于和等于的情况下比较次数不同，所以造成内部比较次数的不平均，因此为了平衡比较和查找次数，可以构建一个看起来不平衡的数列来平衡比较次数。这就是fabonacci查找法 while(lo while (hi - ol else if (ami return -1; 证明：运用递推* 二分查找的改进版： 为了隐藏比较次数，只比较一次： while(1 rank mi = (lo + hi) ； ( e 只是平均情况减少，但最好情况增加。 最优化版：如果不在其中，还可返回最近的小于此元素的坐标 冒泡排序改进：可以记录前面是否有逆序对，如果没有就证明不用再排序了

人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论