Benutzer:Riemer

Wiki-Quelltext dieser Seite.

<language>Java</language>
<popup name="Verkettung">
<code id="4f6a410984ee7">
public Object Link(int d) {
	int data = d;
	Object next;

	public int getKey() {
		return data;
	}

	public void displayLink() {
		System.out.print(data + " ");
	}
        return this;
}

public Object List() {
	Object first = null;
        Object last = null;
        int steps = 0;

	public void insert(Object theLink) {
                steps = 0;

		if (first == null) {
                        steps++;
			first = theLink;
			last = first;
		} else {
                        steps++;
			last.next = theLink;
			last = last.next;
		}
                System.out.println("Einfügen von: " + theLink.getKey() + " - Schritte: " + steps);
	}

	public Object delete(int key) {
		Object previous = null;
		Object current = first;
                Object temp = null;
                steps = 0;

		while (current != null) {
			steps++;
			if (current.getKey() == key) {
				if (previous == null) {
					temp = first;
					first = first.next;
					System.out.println("Schritte: " + steps);
					return temp;
				} else {
					temp = current;
					previous.next = current.next;
					System.out.println("Schritte: " + steps);
					return current;
				}
			} else {
				previous = current;
				current = current.next;
			}
		}
		System.out.println("Schritte: " + steps);
		return null;
	}

	public Object find(int key) {
                steps = 0;
		Object current = first;
		while (current != null) {
                        steps++;						
			if (current.getKey() == key) {
                                System.out.println("Schritte: " + steps);
				return current;
                        }
			current = current.next;
		}
                System.out.println("Schritte: " + steps);
		return null;
	}

	public void displayList() {
		System.out.print("List: ");
		Object current = first;
		while (current != null) {
			current.displayLink();
			current = current.next;
		}
		System.out.println("");
	}
        return this;
}

public Object HashChain(int size) {

	private int arraySize = size;

        private Object[] hashArray = new Object[arraySize];

        for (int i = 0; i < arraySize; i++) {
		hashArray[i] = List();
	}

	public void displayTable() {
		for (int j = 0; j < arraySize; j++) {
			System.out.print(j + ". ");
			hashArray[j].displayList();
		}
	}

	public int hashFunc(int key) {
		return key % arraySize;
	}

	public void insert(theLink) {
		int key = theLink.getKey();
		int hashVal = hashFunc(key);
		hashArray[hashVal].insert(theLink);
	}

	public Object delete(int key) {
		int hashVal = hashFunc(key);
		Object theLink = hashArray[hashVal].delete(key);
                return theLink;
	}

	public Object find(int key) {
		int hashVal = hashFunc(key);
		Object theLink = hashArray[hashVal].find(key);
		return theLink;
	}
        return this;
}

public void fillHashTable(Object hashTable, int numberOfKeys){
        for (int i = 0; i < numberOfKeys; i++) {
	        key = (int) (Math.random() * 10 * size);
	        dataItem = Link(key);
	        hashTable.insert(dataItem);
        }
}
</code>

<run id="4f6a410984ee7">
size = 1;
numberOfKeys = 10;

hashTable = HashChain(size);
fillHashTable(hashTable, numberOfKeys);
hashTable.displayTable();
</run>

<run id="4f6a410984ee7">
size = 1;
numberOfKeys = 10;

hashTable = HashChain(size);
fillHashTable(hashTable, numberOfKeys);

hashTable.displayTable();

key = (int) (Math.random() * 10 * size);
dataItem = hashTable.find(key);

if (dataItem != null) {
	System.out.println(key + " wurde gefunden!");
} else {
	System.out.println(key + " konnte nicht gefunden werden!");
}
</run>

<run id="4f6a410984ee7">
size = 1;
numberOfKeys = 10;

hashTable = HashChain(size);
fillHashTable(hashTable, numberOfKeys);

hashTable.displayTable();

key = (int) (Math.random() * 10 * size);
dataItem = hashTable.delete(key);

if (dataItem != null) {
	System.out.println(key + " wurde gelöscht!");
} else {
	System.out.println(key + " konnte nicht gefunden werden!");
}

hashTable.displayTable();
</run>
</popup>

<popup name="Lineares Sondieren">
<popup name="Klassen-Definitionen">
<code id="4f6ca2b733235">
public Object Elem(int d) {
	int data = d;
	int getKey() {
		return data;
	}
        return this;
}
public Object HashTable(int size) {
	int arraySize = size;

	Object[] hashArray = new Object[arraySize];
	for(i = 0; i < arraySize; i++) {
                hashArray[i] = null;
        }

	void displayTable() {
		for (int i = 0; i < arraySize; i++) {
			if (hashArray[i] != null)
				System.out.print(hashArray[i].getKey() + " ");
			else
				System.out.print("# ");
		}
		System.out.println("");
	}

	int hashFunction(int key) {
		return key % arraySize;
	}

	void insert(elem) {
		int key = elem.getKey();
		int hashVal = hashFunction(key);

		while (hashArray[hashVal] != null) {
			++hashVal;
			hashVal %= arraySize;
		}
		hashArray[hashVal] = elem;
	}

	Object remove(int key) {
		int hashVal = hashFunction(key);

		while (hashArray[hashVal] != null)
		{
			if (hashArray[hashVal].getKey() == key) {
				return hashArray[hashVal] = null;
			}
			++hashVal;
			hashVal %= arraySize;
		}
		return null;
	}

	Object find(int key)
	{
		int hashVal = hashFunction(key);

		while (hashArray[hashVal] != null)
		{
			if (hashArray[hashVal].getKey() == key)
				return hashArray[hashVal];
			++hashVal;
			hashVal %= arraySize;
		}
		return null;
	}
        return this;
}

void fillHashTable(Object theHashTable) {

        int key;

        key = 1;
        elem = Elem(key);
        theHashTable.insert(elem);

        key = 3;
        elem= Elem(key);
        theHashTable.insert(elem);

        key = 4;
        elem = Elem(key);
        theHashTable.insert(elem);

        key = 8;
        elem = Elem(key);
        theHashTable.insert(elem);

        key = 9;
        elem = Elem(key);
        theHashTable.insert(elem);

        key = 12;
        elem = Elem(key);
        theHashTable.insert(elem);

        key = 13;
        elem = Elem(key);
        theHashTable.insert(elem);
}
</code></popup>
<run id="4f6ca2b73358e">
theHashTable = HashTable(15);

fillHashTable(theHashTable);

theHashTable.displayTable();

key = 23;
elem = Elem(key);
theHashTable.insert(elem);
theHashTable.displayTable();

theHashTable.remove(9);
theHashTable.displayTable();

elem = theHashTable.find(key);
if (elem != null) {
	System.out.println(key+ " wurde gefunden!");
} else {
	System.out.println(key + " wurde nicht gefunden!");
}
</run>
</popup>