《Java数据结构跟算法》第二版 Robert lafore 编程作业 第十一章
《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 HashTableApp
import 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 table
private int arraySize;
private DataItem nonItem; // for deleted items
private int number; // DataItem数目
// -------------------------
public HashTable(int size) // constructor
{
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
number = 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() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
// -------------------------
public int hashFunc(int key) {
return key % arraySize; // hash function
}
// =====================================================
// 编程作业 11.3
public 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.4
public 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 key
int 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.1
index = 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 key
int hashVal = hashFunc1(key); // hash the key
int i = 1, index = hashVal;
while (hashArray[index] != null) // until empty cell,
{ // found the key?
if (hashArray[index].getKey() == key) {
DataItem temp = hashArray[index]; // save item
hashArray[index] = nonItem; // delete item
number--;
return temp; // return item
}
// =================================
// 编程作业 11.1
index = 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 key
int hashVal = hashFunc1(key); // hash the key
int 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.1
index = 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 sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
// make table
HashTable 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);
} else
System.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 HashTableApp
import 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 table
private 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() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
// -------------------------
// =====================================================
// 编程作业 11.2
public 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 key
int hashVal = hashFunc(key); // hash the key
// until empty cell or -1,
while (hashArray[hashVal] != null
&& !hashArray[hashVal].getKey().equals("--")) {
++hashVal; // go to next cell
hashVal %= 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 key
while (hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if (hashArray[hashVal].getKey().equals(key)) {
DataItem1 temp = hashArray[hashVal]; // save item
hashArray[hashVal] = nonItem; // delete item
return temp; // return item
}
++hashVal; // go to next cell
hashVal %= 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 key
while (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 cell
hashVal %= 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 sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
// make table
HashTable1 theHashTable = new HashTable1(size);
for (int j = 0; j < n; j++) // insert data
{
// =====================================================
// 编程作业 11.2
StringBuffer 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);
} else
System.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 TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class Node {
public int iData; // data item (key)
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public 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 root
while (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 node
newNode.iData = id; // insert data
if (root == null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node 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 left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if (current == null) // if end of the line
{ // insert on right
parent.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 it
if (current.leftChild == null && current.rightChild == null) {
if (current == root) // if root,
root = null; // tree is empty
else if (isLeftChild)
parent.leftChild = null; // disconnect
else
// from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if (current.rightChild == null)
if (current == root)
root = current.leftChild;
else if (isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if (current.leftChild == null)
if (current == root)
root = current.rightChild;
else if (isLeftChild)
parent.leftChild = current.rightChild;
else
parent.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 instead
if (current == root)
root = successor;
else if (isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.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 descendents
private Node getSuccessor(Node delNode) {
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while (current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if (successor != delNode.rightChild) // right child,
{ // make connections
successorParent.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 HashChainApp
import java.io.*;
////////////////////////////////////////////////////////////////
// ====================================================================
// 编程作业 11.5
class HashChainTable {
private Tree[] hashArray; // array of lists
private int arraySize;
// -------------------------
public HashChainTable(int size) // constructor
{
arraySize = size;
hashArray = new Tree[arraySize]; // create array
for (int j = 0; j < arraySize; j++)
// fill array
hashArray[j] = new Tree(); // with lists
}
// -------------------------
public void displayTable() {
for (int j = 0; j < arraySize; j++) // for each cell,
{
System.out.print(j + ". "); // display cell number
hashArray[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 key
if (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 key
hashArray[hashVal].delete(key); // delete link
} // end delete()
// -------------------------
public Node find(int key) // find link
{
int hashVal = hashFunc(key); // hash the key
Node theNode = hashArray[hashVal].find(key); // get link
return 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 sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
// make table
HashChainTable 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);
else
System.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
// //////////////////////////////////////////////////////////////