数据结构与算法实习 一数据结构设计技巧之 此京太骨信息学載木学院 主讲铭、部丹 zhang [at] net. pku. edu. cn http://www.jpk.pku,educn/pkujpk/course/sjjg/shixi/ 2011.8 张铭赵海糞王膳姣宋迄,《数据构与算法实 验永程》(家十一五舰划激材)高教社2011年1月
数据结构与算法实习 ——数据结构设计技巧之一 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实 验教程》（国家十一五规划教材），高教社2011年1月
重点火纲 口1.数据结构与算法的知识体系 口2时间空间代价分析和权衡 日3.KMP算法的灵活应用 口4. Huffman树的灵活应用 日7.观察森林的角度 8.树/森林和二叉树的顺序表示 国题量大、覆盖面广,要全面复习、透彻理解 灵活应用、快速答卷
重点大纲 1. 数据结构与算法的知识体系 2. 时间空间代价分析和权衡 3. KMP算法的灵活应用 4. Huffman树的灵活应用 5. 带返回值的二叉树递归算法 6. 二叉树与栈 7. 观察森林的角度 8. 树/森林和二叉树的顺序表示 题量大、覆盖面广，要全面复习、透彻理解、 灵活应用、快速答卷
1.数据结构的三个基本要素 口数据的逻辑结构 ■图树二又树线性表 数据的存储结构 逻 存 ■索引方法、散列方法 辑数据储 结构 ∏数据的运算 ■增、删、查、改排序、检索 运算 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 1. 数据结构的三个基本要素 数据的逻辑结构 ◼ 图树二叉树线性表 数据的存储结构 ◼ 顺序方法、链接方法 ◼ 索引方法、散列方法 数据的运算 ◼ 增、删、查、改、排序、检索 存 数据 储 结构 逻 辑 运 算
数据结构与算法体条图 前沿应用:后缀树、 XML DOM树、搜索引擎… 抽象数据类型ADT 算法分析 时空折衷 基础: 逻辑 算 存储 理论抽象设 线性(表、栈、 排序:插入、分治 顺序、链接、 队列、串) 快速、堆、基数 散列、索引 树(二叉树、森 检索:二分、散列 内存、外存 林) 图(有向、无 向、DAG) 索引:BsT、B+ 外排序 B+树,倒排 计 扩展研究:外排序,广义表,稀疏矩阵,字符树 Patricia树,AVL,红黑树,伸展树
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 索引： BST、B+ 扩展研究: 逻辑 运算 存储 线性（表、栈、 队列、串） 树(二叉树、森 林) 图（有向、无 向、DAG） 排序：插入、分治 、快速、堆、基数 检索: 二分、散列 内存、外存 外排序 B+树，倒排 理 论 前沿应用： 后缀树、 XML DOM树、搜索引擎…... 数据结构与算法体系图 抽象数据类型ADT 算法分析 时空折衷 抽 象 设 计 顺序、链接、 散列、索引 外排序，广义表，稀疏矩阵，字符树， Patricia树，AVL， 红黑树，伸展树 …… 基础:
规定财间内能解决的问题规模 口假设CPU每秒处理106个指令,则每小 时能够解决的最大问题规模 T(n)106≤3600 口对T(n)=2n2, 即2n2≤3600×106 ■n≤42,426 口T(n)= nlogn ■即nogn≤3600×10 ■n<133,000,000 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 规定时间内能解决的问题规模 假设CPU每秒处理106 个指令，则每小 时能够解决的最大问题规模 ◼ T(n)/106 3600 对T(n) = 2n2 ， ◼ 即 2n2 3600 106 ◼ n 42 , 426 T(n) = nlogn ◼ 即 nlogn 3600 106 ◼ n 133 , 000 , 000