数据结构与算法-第3章.表栈队列
2021-09-07 20:35:18 37 举报
登录查看完整内容
数据结构与算法分析-java语言描述这本书的学习总结,持续学习更新中
作者其他创作
大纲/内容
本章将要讨论的这三种数据结构是ADT的最基本的例子. 我们将会看到它们中的每一种是如何以多种方法实现的.
一.介绍抽象数据类型的概念
1.1 数组在必要时进行扩容
1.2 数组的实现可以使得printList以线性时间执行
1.3 findKth操作则花费常数时间
1.4 插入和删除潜藏着昂贵的开销
1. 表的简单数组实现
2.1 结构
2.4 remove可以通过修改一个next引用来实现
2. 简单链表
java.util包中Collection接口的子集
扩展了Iterable接口. 可以拥有增强的for循环
3.1 Collection接口
3.2.1 概述
3.2.2 next 给出集合的(尚未见到的)下一项
3.2.3 hasNext 给出是否存在下一项.
3.2 Iterator接口
优点:对get和set的调用花费常数时间
3.3.1 ArrayList:List ADT的一种可增长数组的实现
3.3.2 LinkedList : List ADT的双向链表实现
在末端添加项来构造List: ArrayList和LinkedList的运行时间都是O(N)
3.3.3 两者在一些方法上的时间复杂度区别
3.3 List接口
第一种思路:通过get来删除项. ArrayList和LinkedList都是花费二次时间.
3.4 通过remove方法的使用来理解
(3) MyArrayList将提供get和set的实现.
3.5.1 主要细节
简单短例程
ensureCapacity容量的扩充
add方法
remove方法
3.5.2 基本类
版本一(有问题)
(1)这段程序确实解决了迭代器中没有数组的这个问题.
(2)问题在于theItems是MyArrayList中的私有域
版本二(有问题)
(1)这种方案是使ArrayListIterator作为嵌套类
(2)外层的MyArrayList即为外部类
(5)仍然存在问题:不能直接引用其所在的MyArrayList.
版本三(正确运行)_嵌套类版本
版本四(正确运行)_内部类版本
3.5 ArrayList类的实现(书里是自己实现了一个MyArrayList来了解它的实现方式)
3.6.1 主要细节
带有头节点和尾节点的双链表结构
空链表结构
3.6.2 头节点和尾结点
3.6.3 Node节点
beginMarker:头节点引用
endMarker:尾节点引用
size:数据大小
modeCount:代表自从构造依赖对链表所做的改变的次数.
3.6.4 数据成员
3.6.5 clear
图解:
3.6.6 add
方法
图解: 如果删除p仅需要p的前一个节点和p的后一个几点的链变动一下.
3.6.7 remove
3.6.8 getNode
3.6.9 LinkedListIterator
3.6 LinkedList类的实现(书里自己实现了一个MyLinkedList以了解它的实现方式)
3. Java Collections Api 中的表(方法及算法复杂度介绍)
二.阐述如何有效地执行表的操作
对空栈进行pop或top一般被认为是栈ADT中的一个错误.
1. 概述
2.1 栈的链表实现
这些操作以非常快的常熟时间运行.
2.2 栈的数组实现
2.实现
算法描述:
3.1 平衡符号
背景描述
过程描述
当见到一个数时就把它推入栈中
在遇到一个运算符时该运算符就作用于从该栈弹出的两个数上
再将上面的结果重新推入栈中
算法描述:这个问题最容易的方法就是使用一个栈
比如后缀表达式:6 5 2 3 + 8 * + 3 + *
现在将3压入栈中
然后+使得3和45从栈中弹出并将45+3=48压入栈中
计算过程:
举例说明:
复杂度:O(N)
3.2 后缀表达式
举例说明
3.3 中缀到后缀的转化
3.4 方法调用
3. 应用
三.介绍栈ADT及其在实现递归方面的应用
操作描述
潜在问题:
队列已满的基准情形是: (back+1)%数组大小==front
队列为空的基准情形是: back == front
队列的大小可以通过比较back和front隐式的算出: back + 数组大小 - front % 数组大小 = 队列的大小
实现如下:
2.3 循环数组实现队列
2. 队列的数组实现
四.介绍队列ADT及其在操作系统和算法设计中的应用
数据结构与算法-第3章.表栈队列-公众号:程序媛swag
0 条评论
回复 删除
下一页
