没有合适的资源?快使用搜索试试~ 我知道了~
首页Java解析:数据结构与算法课后习题答案详解
《数据结构与算法分析:Java语言描述课后习题答案》是一本专为学习数据结构和算法的Java编程者设计的教材,由权威作者Greg Tobin和Michael Hirsch共同编撰。该书针对Java语言,深入剖析了各种数据结构(如数组、链表、栈、队列、树和图等)以及基础和进阶算法(排序、搜索、图算法等),通过丰富的习题帮助读者巩固理论知识并提升实践能力。 本书章节涵盖了广泛的内容,如Exercise 12.2(可能是某个特定章节的题目)可能涉及到数据结构在Java中的具体实现,比如如何使用数组或集合框架(如ArrayList、LinkedList)来实现特定的数据操作。在解答过程中,作者可能会展示如何使用循环、递归等基本控制结构来设计高效的算法,并可能涉及一些高级技巧,如动态规划或者分治策略。 在版权方面,此书受到Pearson Education Inc.的版权保护,所有内容未经许可不得复制、存储或传输。想要获取关于教材内容使用的授权,读者需要向Pearson Education提交书面请求,地址为波士顿的Pearson Education Rights and Contract Department。同时,书中还提供了Addison-Wesley出版社的全球网站链接(http://www.aw-bc.com/computing),以便读者查询最新资讯和资源。 对于想要学习数据结构和算法的Java开发者来说,这本书不仅提供了理论讲解,还有实际的编程练习,是提升编程技能和解决问题能力的重要参考资料。通过阅读和解决课后的习题,学生可以深化对Java语言在数据结构和算法中的运用理解,从而在实际项目中更高效地应用所学知识。
资源详情
资源推荐
10 Chapter 3 Lists, Stacks, and Queues
else if ( compareResult<0)
{
Result.add(itemL1);
itemL1 = iterL1.hasNext()?iterL1.next():null;
}
else
{
Result.add(itemL2);
itemL2 = iterL2.hasNext()?iterL2.next():null;
}
}
}
3.6 A basic algorithm is to iterate through the list, removing every Mth item. This can be improved by
two observations. The first is that an item M distance away is the same as an item that is only M
mod N away. This is useful when M is large enough to cause iteration through the list multiple times.
The second is that an item M distance away in the forward direction is the same as an item (M − N)
away in the backwards direction. This improvement is useful when M is more than N/2 (half the
list). The solution shown below uses these two observations. Note that the list size changes as items
are removed. The worst case running time is O(N min(M, N)), though with the improvements given
the algorithm might be significantly faster. If M = 1, the algorithm is linear.
public static void pass(int m, int n)
{
int i, j, mPrime, numLeft;
ArrayList<Integer> L = new ArrayList<Integer>();
for (i=1; i<=n; i++)
L.add(i);
ListIterator<Integer> iter = L.listIterator();
Integer item=0;
numLeft = n;
mPrime=m%n;
for (i=0; i<n; i++)
{
mPrime=m%numLeft;
if (mPrime <= numLeft/2)
{
if (iter.hasNext())
item = iter.next();
for (j=0; j<mPrime; j++)
{
if (!iter.hasNext())
iter = L.listIterator();
Weiss Java Solutions pages p. 10 (chap03) Windfall Software, PCA ZzT
E
X 12.2
Solutions 11
item = iter.next();
}
}
else
{
for (j=0; j<numLeft-mPrime; j++)
{
if (!iter.hasPrevious())
iter = L.listIterator(L.size());
item = iter.previous();
}
}
System.out.print("Removed"+item+"");
iter.remove();
if (!iter.hasNext())
iter = L.listIterator();
System.out.println();
for (Integer x:L)
System.out.print(x+"");
System.out.println();
numLeft--;
}
System.out.println();
}
3.7 O(N
2
). The trim method reduces the size of the array, requiring each add to resize it. The resize takes
O(N) time, and there are O(N) calls.
3.8
(a) Because the remove call changes the size, which would affect the loop.
(b) O(N
2
). Each remove from the beginning requires moving all elements forward, which takes
O(N) time.
(c) O(N). Each remove can be done in O(1) time.
(d) No. Since it is always the first element being removed, finding the position does not take time,
thus an iterator would not help.
3.9 public void addAll( Iterable<? extends AnyType> items )
{
Iterator<? extends AnyType> iter = items.iterator();
while ( iter.hasNext() )
{
add(iter.next());
}
}
This runs in O(N) time, where N is the size of the items collection.
Weiss Java Solutions pages p. 11 (chap03) Windfall Software, PCA ZzT
E
X 12.2
12 Chapter 3 Lists, Stacks, and Queues
3.10 public void removeAll( Iterable<? extends AnyType> items )
{
AnyType item, element;
Iterator<? extends AnyType> iterItems = items.iterator();
while ( iterItems.hasNext())
{
item = iterItems.next();
Iterator<? extends AnyType> iterList = iterator();
while ( iterList.hasNext())
{
element = iterList.next();
if ( element.equals(item) )
iterList.remove();
}
}
}
This runs in O(MN), where M is the size of the items, and N is the size of the list.
3.11
import java.util.*;
public class SingleList
{
SingleList()
{ init(); }
boolean add( Object x )
{
if (contains(x))
return false;
else
{
Node<Object> p = new Node<Object>(x);
p.next = head.next;
head.next = p;
theSize++;
}
return true;
}
boolean remove(Object x)
{
if (!contains(x))
return false;
else
{
Node<Object> p = head.next;
Weiss Java Solutions pages p. 12 (chap03) Windfall Software, PCA ZzT
E
X 12.2
Solutions 13
Node<Object> trailer = head;
while (!p.data.equals(x))
{
trailer = p;
p = p.next;
}
trailer.next = p.next;
theSize--;
}
return true;
}
int size()
{ return theSize; }
void print()
{
Node<Object> p = head.next;
while (p != null)
{
System.out.print(p.data+"");
p = p.next;
}
System.out.println();
}
boolean contains( Object x )
{
Node<Object> p = head.next;
while (p != null)
{
if (x.equals(p.data))
return true;
else
p = p.next;
}
return false;
}
void init()
{
theSize = 0;
head = new Node<Object>();
head.next = null;
}
private Node<Object> head;
private int theSize;
Weiss Java Solutions pages p. 13 (chap03) Windfall Software, PCA ZzT
E
X 12.2
14 Chapter 3 Lists, Stacks, and Queues
private class Node<Object>
{
Node()
{
this(null, null);
}
Node(Object d)
{
this(d, null);
}
Node(Object d, Node n)
{
data = d;
next = n;
}
Object data;
Node next;
}
}
3.12 import java.util.*;
public class SingleListSorted
{
SingleListSorted()
{ init(); }
boolean add( Comparable x )
{
if (contains(x))
return false;
else
{
Node<Comparable> p = head.next;
Node<Comparable> trailer = head;
while (p != null && p.data.compareTo(x) < 0)
{
trailer = p;
p = p.next;
}
trailer.next = new Node<Comparable>(x);
trailer.next.next = p;
theSize++;
}
return true;
}
Weiss Java Solutions pages p. 14 (chap03) Windfall Software, PCA ZzT
E
X 12.2
剩余104页未读,继续阅读
熊猫安
- 粉丝: 1
- 资源: 24
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 前端面试必问:真实项目经验大揭秘
- 永磁同步电机二阶自抗扰神经网络控制技术与实践
- 基于HAL库的LoRa通讯与SHT30温湿度测量项目
- avaWeb-mast推荐系统开发实战指南
- 慧鱼SolidWorks零件模型库:设计与创新的强大工具
- MATLAB实现稀疏傅里叶变换(SFFT)代码及测试
- ChatGPT联网模式亮相,体验智能压缩技术.zip
- 掌握进程保护的HOOK API技术
- 基于.Net的日用品网站开发:设计、实现与分析
- MyBatis-Spring 1.3.2版本下载指南
- 开源全能媒体播放器:小戴媒体播放器2 5.1-3
- 华为eNSP参考文档:DHCP与VRP操作指南
- SpringMyBatis实现疫苗接种预约系统
- VHDL实现倒车雷达系统源码免费提供
- 掌握软件测评师考试要点:历年真题解析
- 轻松下载微信视频号内容的新工具介绍
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功