《Java数据结构和算法》第二版 Robert lafore 编程作业 第十一章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第十一章
/* 编程作业 11.1 修改hash.java程序（清单11.1），改用二次探测。 11.2 实现用一个线性探测哈希表存储字符串。需要一个把字符串转换成数组下标的 哈希函数。参考本章“哈希化字符串”一节。假设字符串全是小写字母，所以26 个字符就足够了。 11.3 写一个哈希函数，实现数字折叠的方法（正如本章“哈希函数”一节描述的）。 程序应该可以适应任何数组容量和任何关键字长度。使用线性探测。存取某个 数中的一组数字比想像的要简单。如果数组容量不是10的倍数，有影响吗？ 11.4 为hash.java程序写一个rehash()方法。只要装填因子大于0.5，insert()方 法会调用它，把整个哈希表复制到比它大两倍的数组中，新的数组容量应该是 一个质数。参考本章“扩展数组”一节。不要忘记，必须处理已经“删除”的数据 项,那里的值为-1。 11.5 使用二叉搜索树，而不是使用地址法中的链表解决冲突。即创建一个树的数组 作为哈希表：可以使用hashChain.java程序（清单11.3）和第8章tree.java 程序（清单8.1）中的Tree类作为基础。为了显示这个基于树的哈希表，每棵 使用中序遍历。 */package chap11;// hash.java// demonstrates hash table with linear probing// to run this program: C:>java HashTableAppimport java.io.*;////////////////////////////////////////////////////////////////class DataItem { // (could have more data)private int iData; // data item (key)// --------------------------public DataItem(int ii) // constructor{iData = ii;}// --------------------------public int getKey() {return iData;}// --------------------------} // end class DataItem// //////////////////////////////////////////////////////////////class HashTable {private DataItem[] hashArray; // array holds hash tableprivate int arraySize;private DataItem nonItem; // for deleted itemsprivate int number;// DataItem数目// -------------------------public HashTable(int size) // constructor{arraySize = size;hashArray = new DataItem[arraySize];nonItem = new DataItem(-1); // deleted item key is -1number = 0;}// -------------------------public void displayTable() {System.out.print("Table: ");for (int j = 0; j < arraySize; j++) {if (hashArray[j] != null)System.out.print(hashArray[j].getKey() + " ");elseSystem.out.print("** ");}System.out.println("");}// -------------------------public int hashFunc(int key) {return key % arraySize; // hash function}// =====================================================// 编程作业 11.3public int hashFunc1(int key) {int hashVal = 0;int length = String.valueOf((arraySize - 1)).length(); // 分组的长度String skey = String.valueOf(key);int i = 0;for (; i + 2 < skey.length(); i += 2) {String str = skey.substring(i, i + 2);hashVal += Integer.valueOf(str).intValue();}if (i < skey.length()) {String str = skey.substring(i);hashVal += Integer.valueOf(str).intValue();}return hashVal % arraySize;}// =====================================================// 编程作业 11.4public void rehash() {int resize = getPrime(arraySize * 2);System.out.println(resize);HashTable ht = new HashTable(resize);for (int i = 0; i < arraySize; i++) {if (hashArray[i] != null && hashArray[i].getKey() != -1) {ht.insert(hashArray[i]);}}this.hashArray = ht.hashArray;this.arraySize = resize;}// =====================================================private int getPrime(int min) {for (int j = min + 1; true; j++) {if (isPrime(j)) {return j;}}}// =====================================================private boolean isPrime(int j) {for (int i = 2; i * i < j; i += 2) {if (j % i == 0) {return false;}}return true;}// =====================================================// -------------------------public void insert(DataItem item) // insert a DataItem// (assumes table not full){if (number / (float) arraySize > 0.5) {rehash();}int key = item.getKey(); // extract key// int hashVal = hashFunc(key); // hash the keyint hashVal = hashFunc1(key); // hash the key// until empty cell or -1,int i = 1, index = hashVal;while (hashArray[index] != null && hashArray[index].getKey() != -1) {// =================================// 编程作业 11.1index = hashVal + i * i;i++;// =================================index %= arraySize; // wraparound if necessary}number++;hashArray[index] = item; // insert item} // end insert()// -------------------------public DataItem delete(int key) // delete a DataItem{// int hashVal = hashFunc(key); // hash the keyint hashVal = hashFunc1(key); // hash the keyint i = 1, index = hashVal;while (hashArray[index] != null) // until empty cell,{ // found the key?if (hashArray[index].getKey() == key) {DataItem temp = hashArray[index]; // save itemhashArray[index] = nonItem; // delete itemnumber--;return temp; // return item}// =================================// 编程作业 11.1index = hashVal + i * i;i++;// =================================index %= arraySize; // wraparound if necessary}return null; // can't find item} // end delete()// -------------------------public DataItem find(int key) // find item with key{// int hashVal = hashFunc(key); // hash the keyint hashVal = hashFunc1(key); // hash the keyint i = 1, index = hashVal;while (hashArray[index] != null) // until empty cell,{ // found the key?if (hashArray[index].getKey() == key)return hashArray[index]; // yes, return item// =================================// 编程作业 11.1index = hashVal + i * i;i++;// =================================index %= arraySize; // wraparound if necessary}return null; // can't find item}// -------------------------} // end class HashTable// //////////////////////////////////////////////////////////////public class HashTableApp {public static void main(String[] args) throws IOException {DataItem aDataItem;int aKey, size, n, keysPerCell;// get sizesSystem.out.print("Enter size of hash table: ");size = getInt();System.out.print("Enter initial number of items: ");n = getInt();keysPerCell = 10;// make tableHashTable theHashTable = new HashTable(size);for (int j = 0; j < n; j++) // insert data{aKey = (int) (java.lang.Math.random() * keysPerCell * size);aDataItem = new DataItem(aKey);theHashTable.insert(aDataItem);}while (true) // interact with user{System.out.print("Enter first letter of ");System.out.print("show, insert, delete, or find: ");char choice = getChar();switch (choice) {case 's':theHashTable.displayTable();break;case 'i':System.out.print("Enter key value to insert: ");aKey = getInt();aDataItem = new DataItem(aKey);theHashTable.insert(aDataItem);break;case 'd':System.out.print("Enter key value to delete: ");aKey = getInt();theHashTable.delete(aKey);break;case 'f':System.out.print("Enter key value to find: ");aKey = getInt();aDataItem = theHashTable.find(aKey);if (aDataItem != null) {System.out.println("Found " + aKey);} elseSystem.out.println("Could not find " + aKey);break;default:System.out.print("Invalid entry\n");} // end switch} // end while} // end main()// --------------------------public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}// --------------------------public static char getChar() throws IOException {String s = getString();return s.charAt(0);}// -------------------------public static int getInt() throws IOException {String s = getString();return Integer.parseInt(s);}// --------------------------} // end class HashTableApp// //////////////////////////////////////////////////////////////
package chap11;// hash.java// demonstrates hash table with linear probing// to run this program: C:>java HashTableAppimport java.io.*;////////////////////////////////////////////////////////////////class DataItem1 { // (could have more data)private String sData; // data item (key)// --------------------------public DataItem1(String str) // constructor{sData = str;}// --------------------------public String getKey() {return sData;}// --------------------------} // end class DataItem// //////////////////////////////////////////////////////////////class HashTable1 {private DataItem1[] hashArray; // array holds hash tableprivate int arraySize;private DataItem1 nonItem; // for deleted items// -------------------------public HashTable1(int size) // constructor{arraySize = size;hashArray = new DataItem1[arraySize];nonItem = new DataItem1("--"); // deleted item key is ""}// -------------------------public void displayTable() {System.out.print("Table: ");for (int j = 0; j < arraySize; j++) {if (hashArray[j] != null)System.out.print(hashArray[j].getKey() + " ");elseSystem.out.print("** ");}System.out.println("");}// -------------------------// =====================================================// 编程作业 11.2public int hashFunc(String key) {int hashVal = 0;for (int j = 0; j < key.length(); j++) {int letter = key.charAt(j);hashVal = (hashVal * 26 + letter) % arraySize;}return hashVal; // hash function}// =====================================================// -------------------------public void insert(DataItem1 item) // insert a DataItem// (assumes table not full){String key = item.getKey(); // extract keyint hashVal = hashFunc(key); // hash the key// until empty cell or -1,while (hashArray[hashVal] != null&& !hashArray[hashVal].getKey().equals("--")) {++hashVal; // go to next cellhashVal %= arraySize; // wraparound if necessary}hashArray[hashVal] = item; // insert item} // end insert()// -------------------------public DataItem1 delete(String key) // delete a DataItem{int hashVal = hashFunc(key); // hash the keywhile (hashArray[hashVal] != null) // until empty cell,{ // found the key?if (hashArray[hashVal].getKey().equals(key)) {DataItem1 temp = hashArray[hashVal]; // save itemhashArray[hashVal] = nonItem; // delete itemreturn temp; // return item}++hashVal; // go to next cellhashVal %= arraySize; // wraparound if necessary}return null; // can't find item} // end delete()// -------------------------public DataItem1 find(String key) // find item with key{int hashVal = hashFunc(key); // hash the keywhile (hashArray[hashVal] != null) // until empty cell,{ // found the key?if (hashArray[hashVal].getKey().equals(key))return hashArray[hashVal]; // yes, return item++hashVal; // go to next cellhashVal %= arraySize; // wraparound if necessary}return null; // can't find item}// -------------------------} // end class HashTable// //////////////////////////////////////////////////////////////public class HashTable1App {public static void main(String[] args) throws IOException {DataItem1 aDataItem;int size, n, keysPerCell;String aKey;// get sizesSystem.out.print("Enter size of hash table: ");size = getInt();System.out.print("Enter initial number of items: ");n = getInt();keysPerCell = 10;// make tableHashTable1 theHashTable = new HashTable1(size);for (int j = 0; j < n; j++) // insert data{// =====================================================// 编程作业 11.2StringBuffer sb = new StringBuffer();int length = (int) (java.lang.Math.random() * 5 + 1);for (int i = 0; i < length; i++) {sb.append((char) (java.lang.Math.random() * 26 + 97));}aDataItem = new DataItem1(sb.toString());theHashTable.insert(aDataItem);// =====================================================}while (true) // interact with user{System.out.print("Enter first letter of ");System.out.print("show, insert, delete, or find: ");char choice = getChar();switch (choice) {case 's':theHashTable.displayTable();break;case 'i':System.out.print("Enter key value to insert: ");aKey = getString();aDataItem = new DataItem1(aKey);theHashTable.insert(aDataItem);break;case 'd':System.out.print("Enter key value to delete: ");aKey = getString();theHashTable.delete(aKey);break;case 'f':System.out.print("Enter key value to find: ");aKey = getString();aDataItem = theHashTable.find(aKey);if (aDataItem != null) {System.out.println("Found " + aKey);} elseSystem.out.println("Could not find " + aKey);break;default:System.out.print("Invalid entry\n");} // end switch} // end while} // end main()// --------------------------public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}// --------------------------public static char getChar() throws IOException {String s = getString();return s.charAt(0);}// -------------------------public static int getInt() throws IOException {String s = getString();return Integer.parseInt(s);}// --------------------------} // end class HashTableApp// //////////////////////////////////////////////////////////////
package chap11;// tree.java// demonstrates binary tree// to run this program: C>java TreeAppimport java.io.*;import java.util.*; // for Stack class////////////////////////////////////////////////////////////////class Node {public int iData; // data item (key)public Node leftChild; // this node's left childpublic Node rightChild; // this node's right childpublic Node() {}public Node(int key) {this.iData = key;}public void displayNode() // display ourself{System.out.print(iData);}public int getKey() {return iData;}} // end class Node// //////////////////////////////////////////////////////////////class Tree {private Node root; // first node of tree// -------------------------public Tree() // constructor{root = null;} // no nodes in tree yet// -------------------------public Node find(int key) // find node with given key{ // (assumes non-empty tree)if (root == null) {return null;}Node current = root; // start at rootwhile (current.iData != key) // while no match,{if (key < current.iData) // go left?current = current.leftChild;else// or go right?current = current.rightChild;if (current == null) // if no child,return null; // didn't find it}return current; // found it} // end find()// -------------------------public void insert(int id) {Node newNode = new Node(); // make new nodenewNode.iData = id; // insert dataif (root == null) // no node in rootroot = newNode;else // root occupied{Node current = root; // start at rootNode parent;while (true) // (exits internally){parent = current;if (id < current.iData) // go left?{current = current.leftChild;if (current == null) // if end of the line,{ // insert on leftparent.leftChild = newNode;return;}} // end if go leftelse // or go right?{current = current.rightChild;if (current == null) // if end of the line{ // insert on rightparent.rightChild = newNode;return;}} // end else go right} // end while} // end else not root} // end insert()// -------------------------public boolean delete(int key) // delete node with given key{ // (assumes non-empty list)Node current = root;Node parent = root;boolean isLeftChild = true;while (current.iData != key) // search for node{parent = current;if (key < current.iData) // go left?{isLeftChild = true;current = current.leftChild;} else // or go right?{isLeftChild = false;current = current.rightChild;}if (current == null) // end of the line,return false; // didn't find it} // end while// found node to delete// if no children, simply delete itif (current.leftChild == null && current.rightChild == null) {if (current == root) // if root,root = null; // tree is emptyelse if (isLeftChild)parent.leftChild = null; // disconnectelse// from parentparent.rightChild = null;}// if no right child, replace with left subtreeelse if (current.rightChild == null)if (current == root)root = current.leftChild;else if (isLeftChild)parent.leftChild = current.leftChild;elseparent.rightChild = current.leftChild;// if no left child, replace with right subtreeelse if (current.leftChild == null)if (current == root)root = current.rightChild;else if (isLeftChild)parent.leftChild = current.rightChild;elseparent.rightChild = current.rightChild;else // two children, so replace with inorder successor{// get successor of node to delete (current)Node successor = getSuccessor(current);// connect parent of current to successor insteadif (current == root)root = successor;else if (isLeftChild)parent.leftChild = successor;elseparent.rightChild = successor;// connect successor to current's left childsuccessor.leftChild = current.leftChild;} // end else two children// (successor cannot have a left child)return true; // success} // end delete()// -------------------------// returns node with next-highest value after delNode// goes to right child, then right child's left descendentsprivate Node getSuccessor(Node delNode) {Node successorParent = delNode;Node successor = delNode;Node current = delNode.rightChild; // go to right childwhile (current != null) // until no more{ // left children,successorParent = successor;successor = current;current = current.leftChild; // go to left child}// if successor notif (successor != delNode.rightChild) // right child,{ // make connectionssuccessorParent.leftChild = successor.rightChild;successor.rightChild = delNode.rightChild;}return successor;}// -------------------------public void traverse(int traverseType) {switch (traverseType) {case 1:System.out.print("\nPreorder traversal: ");preOrder(root);break;case 2:System.out.print("\nInorder traversal: ");inOrder(root);break;case 3:System.out.print("\nPostorder traversal: ");postOrder(root);break;}System.out.println();}// -------------------------private void preOrder(Node localRoot) {if (localRoot != null) {System.out.print(localRoot.iData + " ");preOrder(localRoot.leftChild);preOrder(localRoot.rightChild);}}// -------------------------private void inOrder(Node localRoot) {if (localRoot != null) {inOrder(localRoot.leftChild);System.out.print(localRoot.iData + " ");inOrder(localRoot.rightChild);}}// -------------------------private void postOrder(Node localRoot) {if (localRoot != null) {postOrder(localRoot.leftChild);postOrder(localRoot.rightChild);System.out.print(localRoot.iData + " ");}}// -------------------------public void displayTree() {inOrder(root);System.out.println();} // end displayTree()// -------------------------} // end class Tree// //////////////////////////////////////////////////////////////
package chap11;// hashChain.java// demonstrates hash table with separate chaining// to run this program: C:>java HashChainAppimport java.io.*;////////////////////////////////////////////////////////////////// ====================================================================// 编程作业 11.5class HashChainTable {private Tree[] hashArray; // array of listsprivate int arraySize;// -------------------------public HashChainTable(int size) // constructor{arraySize = size;hashArray = new Tree[arraySize]; // create arrayfor (int j = 0; j < arraySize; j++)// fill arrayhashArray[j] = new Tree(); // with lists}// -------------------------public void displayTable() {for (int j = 0; j < arraySize; j++) // for each cell,{System.out.print(j + ". "); // display cell numberhashArray[j].displayTree(); // display list}}// -------------------------public int hashFunc(int key) // hash function{return key % arraySize;}// -------------------------public void insert(int key) // insert a link{int hashVal = hashFunc(key); // hash the keyif (this.find(key) != null) {return;}hashArray[hashVal].insert(key); // insert at hashVal} // end insert()// -------------------------public void delete(int key) // delete a link{int hashVal = hashFunc(key); // hash the keyhashArray[hashVal].delete(key); // delete link} // end delete()// -------------------------public Node find(int key) // find link{int hashVal = hashFunc(key); // hash the keyNode theNode = hashArray[hashVal].find(key); // get linkreturn theNode; // return link}// -------------------------} // end class HashTable// ====================================================================// //////////////////////////////////////////////////////////////public class HashChainApp {public static void main(String[] args) throws IOException {int aKey;Node aDataItem;int size, n, keysPerCell = 100;// get sizesSystem.out.print("Enter size of hash table: ");size = getInt();System.out.print("Enter initial number of items: ");n = getInt();// make tableHashChainTable theHashTable = new HashChainTable(size);for (int j = 0; j < n; j++) // insert data{aKey = (int) (java.lang.Math.random() * keysPerCell * size);theHashTable.insert(aKey);}while (true) // interact with user{System.out.print("Enter first letter of ");System.out.print("show, insert, delete, or find: ");char choice = getChar();switch (choice) {case 's':theHashTable.displayTable();break;case 'i':System.out.print("Enter key value to insert: ");aKey = getInt();theHashTable.insert(aKey);break;case 'd':System.out.print("Enter key value to delete: ");aKey = getInt();theHashTable.delete(aKey);break;case 'f':System.out.print("Enter key value to find: ");aKey = getInt();aDataItem = theHashTable.find(aKey);if (aDataItem != null)System.out.println("Found " + aKey);elseSystem.out.println("Could not find " + aKey);break;default:System.out.print("Invalid entry\n");} // end switch} // end while} // end main()// --------------------------public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}// -------------------------public static char getChar() throws IOException {String s = getString();return s.charAt(0);}// -------------------------public static int getInt() throws IOException {String s = getString();return Integer.parseInt(s);}// --------------------------} // end class HashChainApp// //////////////////////////////////////////////////////////////