《Java数据结构跟算法》第二版 Robert lafore 编程作业第二章

《Java数据结构和算法》第二版 Robert lafore 编程作业第二章

/* 编程作业 2.1 向highArray.java程序（清单2.3）的HighArray类添加一个名为getMax()的方法，它返回数组中最大关键字的值，当数组为空时返回-1。向main()中添加一些代码来使用这个方法。可以假设所有关键字都是正数。 2.2 修改编程作业2.1中的方法，使之不仅返回最大的关键字，而且还将该关键字从数组中删除。将这个方法命名为removeMax()。 2.3 编程作业2.2中的removeMax()方法提供了一种通过关键字值进行数组排序的方法。实现一个排序方案，要求不修改HighArray类，只需对main()中的代码进行修改。这个方法需要第二个数组，在排序结束时数组数据项是逆序排列的。（这个方法是第3章“简单排序”中选择排序的一个变体。） 2.4 修改orderedArray.java程序（清单2.4）使insert()、delete()与find()方法一样都使用二分查找，正如书中所建议的那样。 2.5 向orderedArray.java程序（清单2.4）的OrdArray类加入一个merge()方法，使之可以将两个有序的源数组合并成一个有序的目的数组。在main()中添加代码，向两个源数组中插入随机数，调用merge()方法，并将结果目的数组显示出来。两个源数组的数据项个数可能不同。在算法中需要先比较源数组中的关键字，从中选出最小的一个数据项复制到目的数组。同时还要考虑如何解决当一个源数组的数据项已经取完而另一个还剩一些数据项情况。 2.6 向highArray.java程序（清单2.3）的HighArray类中加入一个noDup()方法，使之可以将数组中的所有重复数据项删除。即如果数组中有三个数据项的关键字为17，noDup()方法会删除其中的两个。不必考虑保持数据项的顺序。一种方法是先用每一个数据项同其他数据项比较，并用null (或是一个不会用在真正的关键字中的特殊值)将重复的数据项覆盖掉。然后将所有的null删除，当然还要缩小数组的大小。 */package chap02;// highArray.java// demonstrates array class with high-level interface// to run this program: C>java HighArrayApp////////////////////////////////////////////////////////////////class HighArray {private long[] a; // ref to array aprivate int nElems; // number of data items// -----------------------public HighArray(int max) // constructor{a = new long[max]; // create the arraynElems = 0; // no items yet}// -----------------------public boolean find(long searchKey) { // find specified valueint j;for (j = 0; j < nElems; j++)// for each element,if (a[j] == searchKey) // found item?break; // exit loop before endif (j == nElems) // gone to end?return false; // yes, can't find itelsereturn true; // no, found it} // end find()// -----------------------public void insert(long value) // put element into array{a[nElems] = value; // insert itnElems++; // increment size}// -----------------------public boolean delete(long value) {int j;for (j = 0; j < nElems; j++)// look for itif (value == a[j])break;if (j == nElems) // can't find itreturn false;else // found it{for (int k = j; k < nElems; k++)// move higher ones downa[k] = a[k + 1]; // 这里不是多移了一次当k=nElems-1时, a[nElems-1] = a[nElems]; 此时a[nElems]为空nElems--; // decrement sizereturn true;}} // end delete()// -----------------------public void display() // displays array contents{for (int j = 0; j < nElems; j++)// for each element,System.out.print(a[j] + " "); // display itSystem.out.println("");}// -----------------------// ==========================================================// p50(69) 编程作业2.1public long getMax() {long max = -1;// 最大元素的值for (int j = 0; j < nElems; j++) {if (a[j] > max) {max = a[j];}}return max;}// ==========================================================// p50(69) 编程作业2.2public long removeMax() {long max = -1; // 最大元素的值int index = -1; // 最大元素的索引号for (int j = 0; j < nElems; j++) {if (a[j] > max) {max = a[j];index = j;}}if (index != -1) { // 找到最大元素for (int i = index + 1; i < nElems; i++) {a[i - 1] = a[i];}nElems--;}return max;}// ==========================================================// p50(69) 编程作业2.6// 第一种方法public void noDup() {int NULL = -1; // 用-1作特殊值for (int j = 0; j < nElems; j++) {for (int i = j + 1; i < nElems; i++) {if (a[j] != NULL && a[j] == a[i]) {a[i] = NULL;}}}for (int i = 0; i < nElems;) {if (a[i] == NULL) {// 注意:移动完成后不要i++，再次检查当前位置是否为NULLfor (int j = i + 1; j < nElems; j++) {a[j - 1] = a[j];}nElems--;} else {i++; // 不是NULL，直接i++;}}}// 第二种方法public void noDup1() {int NULL = -1; // 用-1作特殊值，假设用户不会输入负的元素for (int j = 0; j < nElems; j++) {for (int i = j + 1; i < nElems; i++) {if (a[j] != NULL && a[j] == a[i]) {a[i] = NULL;}}}int order = 0;for (int temp = 0; temp < nElems; temp++) {if (a[temp] != NULL) {// 因为a[0]不可能等于NULL所以才可以用这种方法if (temp > order) {a[order] = a[temp];}order++;}}nElems = order;}// ==========================================================} // end class HighArray// //////////////////////////////////////////////////////////////public class HighArrayApp {public static void main(String[] args) {int maxSize = 100; // array sizeHighArray arr; // reference to arrayarr = new HighArray(maxSize); // create the arrayarr.insert(77); // insert 10 itemsarr.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(); // display itemsint searchKey = 35; // search for itemif (arr.find(searchKey))System.out.println("Found " + searchKey);elseSystem.out.println("Can't find " + searchKey);arr.delete(00); // delete 3 itemsarr.delete(55);arr.delete(99);arr.display(); // display items again// =======================================================// p50(69) 编程作业2.1long max = arr.getMax();System.out.println("Found max is " + max);// =======================================================// p50(69) 编程作业2.2arr.removeMax();arr.display();// =======================================================// p50(69) 编程作业2.3HighArray sortedArr = new HighArray(maxSize);int i = 0;max = arr.removeMax();while (max != -1) {sortedArr.insert(max);max = arr.removeMax();}System.out.println("逆序排列:");sortedArr.display();// =======================================================arr.insert(77); // insert 10 itemsarr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);// 重复值arr.insert(44);arr.insert(77);arr.insert(44);arr.insert(66);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);System.out.println("加入重复值后：");arr.display();// arr.noDup();arr.noDup1();System.out.println("去掉重复值后：");arr.display();// =======================================================} // end main()} // end class HighArrayApp

package chap02;// orderedArray.java// demonstrates ordered array class// to run this program: C&gt;java OrderedApp////////////////////////////////////////////////////////////////class OrdArray {private long[] a; // ref to array aprivate int nElems; // number of data items// -----------------------public OrdArray(int max) // constructor{a = new long[max]; // create arraynElems = 0;}// -----------------------public int size() {return nElems;}// -----------------------public int find(long searchKey) {int lowerBound = 0;int upperBound = nElems - 1;int curIn;while (true) {curIn = (lowerBound + upperBound) / 2;if (a[curIn] == searchKey)return curIn; // found itelse if (lowerBound &gt; upperBound)return nElems; // can't find itelse // divide range{if (a[curIn] &lt; searchKey)lowerBound = curIn + 1; // it's in upper halfelseupperBound = curIn - 1; // it's in lower half} // end else divide range} // end while} // end find()// -----------------------public void insert(long value) // put element into array{int j;for (j = 0; j &lt; nElems; j++)// find where it goesif (a[j] &gt; value) // (linear search)break;for (int k = nElems; k &gt; j; k--)// move bigger ones upa[k] = a[k - 1];a[j] = value; // insert itnElems++; // increment size} // end insert()// -----------------------// ========================================================// 编程作业2.4 p50(69)public void insert1(long value) {if (nElems == 0) { // 没有元素，直接插入a[0] = value;nElems++;return;}int lowerBound = 0;int upperBound = nElems - 1;int curIn;while (true) {curIn = (lowerBound + upperBound) / 2;if (lowerBound &gt; upperBound) {break;}if (a[curIn] == value)break; // found itelse if (a[curIn] &lt; value) // divide range{if (curIn == nElems - 1) {curIn = curIn + 1;break;} else if (a[curIn + 1] &gt;= value) {curIn = curIn + 1;break;} else {lowerBound = curIn + 1; // 注意这里是+1}} else {if (curIn == 0) {break;} else if (a[curIn - 1] &lt;= value) {break;} else {upperBound = curIn - 1; // 注意这里是-1;}}}for (int k = nElems; k &gt; curIn; k--)// move bigger ones upa[k] = a[k - 1];a[curIn] = value; // insert itnElems++; // increment size}// ========================================================// p50(69) 编程作业2.4 delete()已经用到了二分查找// ========================================================public boolean delete(long value) {int j = find(value); // delete()已经用到了二分查找if (j == nElems) // can't find itreturn false;else // found it{for (int k = j; k &lt; nElems; k++)// move bigger ones downa[k] = a[k + 1];nElems--; // decrement sizereturn true;}} // end delete()// -----------------------public void display() // displays array contents{for (int j = 0; j &lt; nElems; j++)// for each element,System.out.print(a[j] + " "); // display itSystem.out.println("");}// -----------------------// ==================================================// p50(69) 编程作业2.5public OrdArray merge(OrdArray orderArr) {// 假设数组空间总是足够OrdArray dist = new OrdArray(this.nElems + orderArr.nElems);int index = 0;for (int i = 0; i &lt; orderArr.size(); i++) {dist.insert(orderArr.a[i]);}for (int i = 0; i &lt; this.size(); i++) {dist.insert(this.a[i]);}return dist;}// ==================================================} // end class OrdArray// //////////////////////////////////////////////////////////////public class OrderedApp {public static void main(String[] args) {int maxSize = 100; // array sizeOrdArray arr; // reference to arrayarr = new OrdArray(maxSize); // create the arrayarr.insert(77); // insert 10 itemsarr.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);int searchKey = 55; // search for itemif (arr.find(searchKey) != arr.size())System.out.println("Found " + searchKey);elseSystem.out.println("Can't find " + searchKey);arr.display(); // display itemsarr.delete(00); // delete 3 itemsarr.delete(55);arr.delete(99);arr.display(); // display items again// ============================// 编程作业2.4 p50(69)arr = new OrdArray(maxSize); // create the arrayarr.insert1(4); // insert 10 itemsarr.insert1(3);arr.insert1(2);arr.insert1(1);arr.display(); // display items again// 编程作业2.5 p50(69)System.out.println("第二个数组:");OrdArray arr1 = new OrdArray(maxSize); // create the arrayarr1.insert(10);arr1.insert(20);arr1.insert(30);arr1.insert(40);arr1.insert(50);arr1.insert(60);arr1.insert(70);arr1.display();System.out.println("合并两个数组，生成新的数组:");OrdArray arr2 = arr.merge(arr1);arr2.display();// ============================} // end main()} // end class OrderedApp

《Java数据结构跟算法》第二版 Robert

热点推荐