地址:http://inmethetiger.iteye.com/blog/1707505
说明:原创是指习题答案。清单只是为了前后对应。
清单2.3
public class HighArrayApp {
public static void main(String[] args){
int maxSize = 100;
HighArray arr = new HighArray(maxSize);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display();
int searchKey = 35;
if(arr.find(searchKey)){
System.out.println("Found "+searchKey);
}else{
System.out.println("Can't Found "+searchKey);
}
arr.delete(00);
arr.delete(55);
arr.delete(99);
arr.display();
}
}
class HighArray {
private long[] a;// 数组a的引用
private int nElems;
public HighArray(int max) {
a = new long[max];
nElems = 0;
}
public boolean find(long searchKey) {
int j;
for (j = 0; j < nElems; j++) {
if (a[j] == searchKey) {
break;
}
}
if (j == nElems) {
return false;
} else
return true;
}
public void insert(long value) {
a[nElems] = value;
nElems++;
}
public boolean delete(long value) {
int j;
for (j = 0; j < nElems; j++) //遍历查询
if (value == a[j])
break;
if (j == nElems)
return false;
else {
for (int k = j; k < nElems; k++) {
a[k] = a[k + 1];
}
nElems--;
return true;
}
}
public void display(){
for(int j=0;j<nElems;j++){
System.out.print(a[j]+"\t");
}
System.out.println();
}
}
清单2.4
public class OrderedApp {
public static void main(String[] args) {
int maxSize = 100;
OrdArray arr = new OrdArray(maxSize);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display();
int searchKey = 56;
if (arr.find(searchKey) != -1) {
System.out.println("Found " + searchKey);
} else {
System.out.println("Can't Found " + searchKey);
}
}
}
class OrdArray {
private long[] a;
private int nElems;
public OrdArray(int max) {
a = new long[max];
nElems = 0;
}
public int size() {
return nElems;
}
// 采用二分查找,而不是2.3的线性查找了
public int find(long searchKey) {
int lowerBound = 0;
int upBound = nElems - 1;
int curIn;
//原著中,while条件为true。这样不行。因为如果找不到的话,会出现死循环
while (lowerBound < upBound) {
curIn = (lowerBound + upBound) / 2;
if (a[curIn] == searchKey) {
return curIn;
} else if (a[curIn] < searchKey) {
lowerBound = curIn + 1;
} else {
upBound = curIn - 1;
}
}
return -1;
}
public void insert(long value) {
int j;
for (j = 0; j < nElems; j++)
if (a[j] > value)
break;
for (int k = nElems; k > j; k--)
a[k] = a[k - 1];
a[j] = value;
nElems++;
}
public boolean delete(long value) {
int j = find(value);
if (j == nElems)
return false;
else {
for (int k = j; k < nElems; k++)
a[k] = a[k + 1];
nElems--;
return true;
}
}
public void display() {
for (int j = 0; j < nElems; j++) {
System.out.print(a[j] + "\t");
}
System.out.println();
}
}
2.1:向HighArray.java(清单2.3)的HighArray类中添加一个名为getMax()的方法,它返回数组中最大关键字的值,当数组为空时返回-1。向main()中添加一些代码来使用这个方法。可以假设所有的关键字都是正数
代码实现:
public long getMax() {
long max = -1;
for (int i = 0; i < nElems; i++) {
if (a[i] > max) {
max = a[i];
}
}
return max;
}
刚开始想复杂了,竟然想了替换。结果发现其实很简单:只需要将max和数组内的每个数比较,如果数组中的数大于max,则把max换成当前的数。
2.2:修改2.1中的方法,使之不仅能返回最大的关键字,而且还可以将该关键字从数组中删除,将这个方法命名为removeMax()
代码实现:
public void removeMax(){
delete(getMax());
}
//main方法中
// 得到最大值
System.out.println(arr.getMax());
arr.removeMax();
arr.display();
2.3:修改2.2中的方法,提供了一种通过关键字进行数组排序的方法。实现一个排序方案,要去不修改HighArray类,只需对main()中的代码进行修改。这个方法需要第二个数组,在排序结束时数组数据项是逆序排列的。(这个方法是第三章“简单排序”中选择排序的一个遍体)
待实现:
public void removeMax2() {
// 构造新数组,每次选出最大的放到新数组里面
long[] temp = new long[nElems];
/*
* 1:通过getMax()得到最大的值,放到新构造的数组中。然后移除a数组中的值。
* 注意,i小于的条件是temp.length。而不是nElems。因为removeMax()的时候nElems已经减1了
*/
for (int i = 0; i < temp.length; i++) {
temp[i] = getMax();
removeMax();
}
for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i] + "\t");
}
}
2.4:修改清单2.4.史insert(),delete()和find()方法一样都使用二分查找。
这个修改起来还真复杂。关键是这个find方法不能复用。因为如果使用二分插入的方法的话,应该根据某个值能找到他的插入位置。但是find方法貌似不行。
最后修改了一下find方法。虽然能使用二分插入了。但是还是有问题。不过先帖在这里。到时候再改。
// 采用二分查找,而不是2.3的线性查找了
public int find(long searchKey) {
int lowerBound = 0;
int upBound = nElems - 1;
int curIn;
// 原著中,while条件为true。这样不行。因为如果找不到的话,会出现死循环
while (lowerBound < upBound) {
curIn = (lowerBound + upBound) / 2;
if (a[curIn] == searchKey) {
return curIn;
} else if (a[curIn] < searchKey) {
lowerBound = curIn + 1;
} else {
upBound = curIn - 1;
}
}
//如果
if(a[lowerBound]>searchKey)
return lowerBound;
else
return lowerBound+1;
}
public void insert(long value) {
int j;
for (j = 0; j < nElems; j++)
if (a[j] > value)
break;
for (int k = nElems; k > j; k--)
a[k] = a[k - 1];
a[j] = value;
nElems++;
}
public void insert2(long value) {
// 应该用二分查找找到插入的位置,本来想服用find方法。发现那个方法不能返回位置信息
int index = find(value);
for (int k = nElems; k > index; k--)
a[k] = a[k - 1];
a[index] = value;
nElems++;
}
2.5是有序数组合并。
2.6:在清单之中加入一个noDup方法,使之可以将数组中的所有重复数据项删除。比如 数组中有三个17,则该方法会删除其中两个。不洗考虑保持数据项的顺序,一种方法是先用每一个数据项同其他数据比较,并用null(或是一个不会用在真正关键字中的特殊值)将重复的数据覆盖掉。然后将所有的null删掉。当然还要减小数组的大小。
解决办法没有细看。自己实现了一个。但是还是存在一点问题,比如如果最后几个相同的数放在一起,程序还是会保留两个重复的数。暂时没有解决
先帖出来:
public void noDup() {
for (int i = 0; i < nElems; i++) {
long temp =a[i];
for (int j = i+1; j <nElems; j++) {
if(temp==a[j])
delete(a[j]);
}
}
}
分享到:
相关推荐
Java数据结构和算法.第二版(带完整附录与习题答案) 不是平时下的那种9mb版本 part2 如果你分不够,可以去www.suzker.cn的分享页留言,我回尽快发给你。
Java语言描述的第二版更是为Java程序员提供了针对性的学习材料。书中的习题答案部分则帮助读者巩固理论知识,通过实践加深对概念的理解。 数据结构是计算机存储、组织数据的方式,它直接影响到程序的效率和可行性。...
数据结构与算法分析——Java语言描述(第二版)是普林斯顿大学Mark Allen Weiss的经典之作,但是网上很少能找到Java描述第二版的课后习题,连作者的个人主页也明确表示不提供课后习题,只能到出版商那里去索取,这个...
这个压缩包提供的第二章习题答案可以作为参考,帮助学生检查自己的理解,激发解决问题的新思路。 在学习过程中,不断练习和应用这些知识点,逐步积累经验,才能真正掌握Java程序设计和数据结构。遇到困难时,可以...
不相交集类8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 路径压缩和按秩求并的最坏情形8.7 一个应用小结练习题参考文献第9章 图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径...
这本书作为《数据结构与算法分析》第二版的配套解决方案手册,由Addison-Wesley出版社出版。主要针对使用Java编程语言的学生和专业人士。书中包含了大量课后习题的答案,旨在帮助读者深入理解数据结构与算法的概念,...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
练习题分为理论题和上机实验题两部分,理论题主要测试对基本概念的理解和理论分析,而上机实验题则需要实际编写代码来实现数据结构的操作。 以下是《数据结构教程》中可能涉及的一些关键知识点: 1. 线性结构:...
### 数据结构与算法分析Java语言描述第二版MarkAllenWeiss #### 书籍概述 《数据结构与算法分析Java语言描述》是由Mark Allen Weiss所著,是计算机科学领域中关于数据结构与算法的经典教材之一。本书的第二版进一步...
### 数据结构与算法(Java版本) ...此外,《数据结构与算法(Java版本)》还提供了大量的编程示例和练习题,有助于加深理解和提高实践能力。无论你是初学者还是有一定经验的程序员,都能从中受益匪浅。
这些题目覆盖了数据结构中的核心概念,包括抽象数据类型、字符串操作、表达式求解、排序算法、二叉树、图论、哈希表等多个方面,是全面检验Java数据结构理解与应用的好材料。通过解答这些问题,学习者能够深入理解...
《Java 数据结构第二版》是深入理解数据结构与算法在Java编程语言中的应用的重要参考资料。这本书的第二版可能包含了更新的内容、改进的示例和更深入的解释,以适应不断发展的Java技术和计算机科学领域的变化。 ...
### 数据结构(Java版)习题解答概览 #### 第0章 Java程序设计基础 **实验0.1:哥德巴赫猜想** - **题目**:实现哥德巴赫猜想,即任何大于2的偶数都可以表示为两个质数之和。 - **解答**:通过编写一个函数来检测...
不相交集类8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 路径压缩和按秩求并的最坏情形8.7 一个应用小结练习题参考文献第9章 图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法...
在本资源中,我们主要关注的是“Java语言程序设计(第二版)”一书的第三章课后习题答案,特别是那些涉及编程代码的问题。Java是一种广泛应用的面向对象的编程语言,以其平台无关性、安全性和高效性而受到赞誉。在...
第10章的主题很可能涉及了高级的数据组织和处理技术,如数组、链表、栈、队列、树等基本数据结构。课后习题通常包含了一系列编程实践题目,旨在巩固理论知识并提高实际编程技能。 "chapter10.rar"这个压缩包文件很...
这本书的中文版第二版对于中国读者来说,无疑是理解和掌握算法知识的重要资源。书中涵盖了各种基础和高级算法,包括排序、搜索、图算法、动态规划以及计算几何等。同时,附带的课后习题答案对于学习者而言,提供了...