数据结构与算法自学笔记
需积分: 42 86 浏览量
2016-02-21
20:27:21
上传
评论 7
收藏 8.8MB PDF 举报
1 章概论 .......................................................................................................................................... 6
1.1 什么是数据结构 ................................................................................................................ 6
1.1.1 数据逻辑结构 ......................................................................................................... 6
1.1.2 数据的存储结构 ..................................................................................................... 8
1.1.3 数据的运算 ............................................................................................................. 9
1.2 抽象数据类型 ADT (abstruct data structure) ................................................................. 9
1.3 算法的特性及分类 .......................................................................................................... 10
1.4 算法的效率度量 .............................................................................................................. 11
1.4.1 计算复杂性 ........................................................................................................... 11
1.4.2 算法的效率 ........................................................................................................... 11
1.4.3 大 O 表示法 .......................................................................................................... 12
1.4.4 大 Ω 表示法 .......................................................................................................... 13
1.4.5 大 Θ 表示法 .......................................................................................................... 13
1.4.6 渐进分析实例 ....................................................................................................... 13
1.5 最佳、最差和平均情况 .................................................................................................. 14
1.5.1 最佳、最差的作用 ............................................................................................... 14
1.5.2 时间和空间的折衷 ............................................................................................... 14
1.5.3 求解问题时对数据结构的选择和评价 ............................................................... 14
2 章线性表、栈和队列 ................................................................................................................. 14
2.1 线性表(linear list) ............................................................................................................ 14
2.1.1 线性表的逻辑结构 ............................................................................................... 15
2.1.2 线性表的存储结构 ............................................................................................... 16
2.2 顺序表—向量(sequential list - vector) ............................................................................ 16
2.2.1 定义....................................................................................................................... 16
2.2.2 检索....................................................................................................................... 17
2.2.3 插入算法执行时间 ............................................................................................... 17
2.2.4 删除算法 ............................................................................................................... 17
2.3 链表(linked list) ................................................................................................................. 17
2.3.1 单链表................................................................................................................... 18
2.3.2 双链表(double linked list) ..................................................................................... 21
2.3.3 循环链表(circularly linked list) ............................................................................. 22
2.3.4 几种主要链表比较 ............................................................................................... 23
2.4 线性表实现方法的比较 .................................................................................................. 23
2.5 栈(STACK) ......................................................................................................................... 24
2.5.1 定义....................................................................................................................... 24
2.5.2 抽象数据结构 ....................................................................................................... 24
2.5.3 栈的实现 ............................................................................................................... 24
2.5.4 顺序栈................................................................................................................... 24
2.5.5 链式栈................................................................................................................... 25
2.6 栈的应用........................................................................................................................... 27
2.6.1 栈的应用—计算表达式的值 ............................................................................... 27
2.6.3 递归到非递归的转换—背包问题 ....................................................................... 31
2.7 队列(queue) ..................................................................................................................... 38
剩余314页未读，继续阅读
资源评论
