Предложение от Steven, R. Bates

Ниже простой класс LinkList поддерживающий любые объекты:

import java.lang.Object;

class LinkList extends Object {
private LinkList therest;
private Object value;

public LinkList(Object obj) {
therest=null;
value=obj;
}

public LinkList cons(Object obj) {
LinkList newnode;

newnode=new LinkList(obj);
newnode.value=value;
newnode.therest=therest;
therest=newnode;
value=obj;
return this;
}

public Object first() {
return value;
}

public LinkList rest() {
return therest;
}

public String toString() {
StringBuffer out;
LinkList list;

out=new StringBuffer();
out.append("LinkList Object: ["+value.toString());
list=therest;
while(list!=null) {
out.append(","+list.first().toString());
list=list.rest();
}
out.append("]");
return out.toString();
}
}

class test extends Object {
public static void main(String argv[]) {
LinkList foo;

foo=new LinkList("This is the End");
foo.cons(new Integer(5));
foo.cons(new Boolean(true));
foo.cons(new LinkList(new Integer(7)));
System.out.println(foo.toString());
System.out.println((foo=foo.rest()).first().toString());
System.out.println((foo=foo.rest()).first().toString());
System.out.println((foo=foo.rest()).first().toString());
}
}

Предложение от Alexander N. Spitzer

Действительно простой пример есть здесь: http://pork.cybercom.net/java/sLinkedList.java


2. Как построить бинарное дерево?

Предложение от Paul Phillips

Ссылка на исходный текст - http://www.cerf.net/~paulp/java/btree/

Предложение от Alexander N. Spitzer

Действительно легкий пример здесь - http://pork.cybercom.net/java/binaryTree.java


3. Как выполнить пузырьковую сортировку? А быструю?

Предложение от Kiran Kumar Cherukuri

В пузырьковой сортировке основная идея заключается в замене элементов немедлено до того, как выясняется, что этот элемент нам не подходит. С этим методом нам необходимо совершить н-1 итераций на массиве размером н. Во время первого сравнения сравниваются первый и второй элементы и если они не упорядочены, то они меняются местами. Таким образом сравниваются все элементы в массиве со своимим предыдущими элементами и меняются местами по необходимости. После выполнения первого прохода наибольший элемент находиться на н-цатом месте. После выполенния нескольких итераций (равных н-1 или меньше) все элементы будут размещены в их соответствующих позициях (другими словами отсортируются).

В коде представленном ниже, во воермя выполнения каждого прохода если происходит хотя бы одно перемещение элементов, то происходит увеличение счетчика, что означает, что произошел обмен во время этого прохода. Если счетчик равен нулю или количество проходов равно н-1 это означает, что сортировка закончена и программа прерывает свое исполнение.

Для более полной информации о пузырьковой сортировке можно прочитать на странице номер 541 в книге "An Introduction to Datastructures With Applications" написаной Jean-Paul Tremblay и Paul G.Sorensen.

class bubblesort {
public static void main (String args[]) {

int sort[] = {42,23,74,11,65,58,94,36,99,87}; // values to be sorted
int temp;
int count; // for checking whether interchanges are done or not
int n; // for counting number of passes
n=0;
count=1;
while (n < sort.length-1 || count != 0) {
count = 0;
for(int j=0;j sort[j+1]) {
temp = sort[j];
sort[j] = sort[j+1];
sort[j+1] = temp;
count++;
}
}
n++;
}
for(int i=0; i < sort.length;i++) {
System.out.println(sort[i]);
}
}
}

Предложение от Jon. M. Madison

Пример с java.sun.com


4. Как имплемецировать стек?

Предложение от Cliff Berg

Вот пример создания класса стека который расширяет API Stack class. В этом примере, новый класс NameStack, поддерживает помещение строк в стек и предотвращает помещение дублирующих строк в стек.

/**
* The stack class, which extends the API Stack class, adding
* behavior which prevents duplicate String values from being pushed
* onto the stack.
*/
class NameStack extends Stack {

/**
* Overloads Stack.push()
* Pushes an item onto the stack.
* @param item the item to be pushed on.
* Checks that the item value (a String) is unique.
*/
public String push(String item) {
for (int i = 0; i < size(); i++) {
String s = (String)(elementAt(i));
if (s.equals(item)) {
// duplicate: not allowed
return null;
}
}

// no duplicates found; add item to stack
addElement(item);
return item;
}

}


5. Как имплемецировать очередь?

Предложение от Jeff Johnson

Ниже представлена цикличная очередь:

import java.util.Vector;
import java.util.Enumeration;
import java.util.NoSuchElementException;

/** A fixed size circular queue.
Adding a new element overwrites the oldest one.
*/

public class CircularQueue extends Vector {
int size = 0; // # of elements the queue can contain
int count = 0; // # of elements currently in the queue
int head;

public CircularQueue ( int s ) {
if ( s = 2");
}
size = s; // (should throw exception if s < 2)
count = 0; // just discard existing items for now
this.setSize(size); // allocate exact amount of storage
this.trimToSize(); // using Vector methods
head = size - 2; // initialize head pointer
}

public void add ( Object obj ) {
if ( count < size ) { // update # of in-use elements
count++;
}

head++; // update head pointer
if (head == size ) {
head = 0; // wrap at the end
}

this.setElementAt( obj, head ); // replace object at this location
}

public int count() {
return count; // return the # of in-use elements
}

// Returns an enumeration of the elements. Use the Enumeration methods on
// the returned object to fetch the elements sequentially.

public final synchronized Enumeration enumeration() {
return new CircularQueueEnumerator(elementData, count, head);
}

} // end CircularQueue


/** Supporting class for CircularQueue to allow enumeration of the contents.
Elements are returned in the reverse order of entry (i.e., newest to oldest).
*/

final class CircularQueueEnumerator implements Enumeration {
Object data[]; // data array
int count; // # of objects returned so far
int actualCount; // # of objects in-use
int head; // head pointer
int current; // current enumeration position pointer

CircularQueueEnumerator( Object d[], int ac, int h) {
data = d;
count = 0;
actualCount = ac;
head = h;
current = head; // initialize pointer to return first element
}

public boolean hasMoreElements() {
return count < actualCount;
}

public Object nextElement () {
if ( count 0) { // not first one?
current--; // walk down list
if (current < 0) { // wrap around
current = data.length - 1;
}
}
count++;
return data[current];
}
throw new NoSuchElementException("CircularQueueEnumerator");
}
} // end CircularQueueEnumerator

А вот программа, которая тестирует эту очередь:

// Sample code to test CircularQueue class

import java.applet.Applet;
import java.lang.String;
import java.util.Enumeration;

public class someClass extends Applet {

CircularQueue cq;
int size = 4;

public void init() {
cq = new CircularQueue( size ); // instantiate queue of a given size

String s1 = "12:00";
String s2 = "12:01";
String s3 = "12:02";
String s4 = "12:03";
cq.add( s1 ); // add items to the queue
cq.add( s2 );
cq.add( s3 );
cq.add( s4 );

// list elements in reverse order of entry (newest-to-oldest)

for (Enumeration e = cq.enumeration(); e.hasMoreElements(); ) {
String s = (String) e.nextElement();
System.out.println( s );
}
System.out.println();

String s5 = "12:04";
cq.add( s5 ); // overwrite oldest item

// list elements in reverse order of entry (newest-to-oldest)

for (Enumeration e = cq.enumeration(); e.hasMoreElements(); ) {
String s = (String) e.nextElement();
System.out.println( s );
}
}
}

Предложение от Joydeep Tripathy

Вот простенький класс очереди с программой его тестирующей:

import java.awt.*;
import java.applet.*;
import java.util.Vector;

class Queue extends Vector {

Queue(int initialCapacity, int capacityIncrement) {
super(initialCapacity, capacityIncrement);
}

// Now add methods to insert and remove from the queue

void insert(Object o) {
addElement(o);
}

Object remove() {
if (isEmpty()) return null;
Object o = firstElement();
removeElement(o);
return o;
}

Object peek() {
if (isEmpty()) return null;
return firstElement();
}
}

public class QueueTest extends Applet {
Queue queue;
Button bi;
Button br;
static int uniqueId = 0;

public void init() {
queue = new Queue(10, 10);
add(bi = new Button("Insert"));
add(br = new Button("Remove"));
}

public void start() {}

public void stop() {}

public boolean handleEvent(Event e) {
if (e.id == Event.WINDOW_DESTROY) {
System.exit(0);
}
if (e.target == bi) {
// insert an object into queue
String s = String.valueOf(uniqueId++);
queue.insert(s);
System.out.println("Inserted: " + s);
}
else if (e.target == br) {
// remove an object from queue
Object o = queue.remove();
if (o == null) o = "";
System.out.println("Removed: " + (String)o);
}

return false;
}

public static void main(String args[]) {
// Create a Frame
MainFrame f = new MainFrame("QueueTest");

// Instantiate the Applet
QueueTest queueTest = new QueueTest();

// Init and start the Applet
queueTest.init();
queueTest.start();

// Add the Applet to the Frame
f.add("West", queueTest);

// Resize and show the Frame
f.resize(300, 300);
f.show();
}
}


class MainFrame extends Frame {
public MainFrame(String s) {
super(s);
}

// Handle close events by simply exiting
public boolean handleEvent(Event e) {
if (e.id == Event.WINDOW_DESTROY)
{
System.exit(0);
}
return false;
}
}


6. Как разобрать вещественные числа из строки?

Предложение от Tim Farnum

/** getDoubles class is a class into which a string is placed. After that,
* repeated invocation of the next() method will return either the next
* double in the string or Double.POSITIVE_INFINITY if there are no more
* doubles in the string. White space is ignored. Numbers followed by letters
* are translated, but numbers directly preceded by letters are not. Scientific
* notation is handled correctly, but only if the exponent is signed: a number
* like 1.546e78 will not be parsed correctly (the exponent is lost). Luckily
* the String translation functions of Java generate numbers with signed
* exponents, even when the exponent is positive.
*
* This file Copyright (c) 1996 by Tim Farnum (tfarnum@rpa.net). THERE IS NO
* WARRANTY OF MERCHANTIBILITY OR FITNESS FOR ANY PURPOSE AND THE AUTHOR
* ACCEPTS NO LIABILITY FOR ANY USE OF THIS SOFTWARE. ANYONE USING THIS
* SOFTWARE USES IT AT THEIR OWN RISK.
*
* Constructor
* public getDoubles(String inString)
* inString is inserted into a StreamTokenizer for processing by the
* methods of the class.
*
* Methods
*
* public double next()
* throws IOException
* This is the workhorse method which parses the next double in the string
* if there is one, skipping over white space, newlines, and text. It will
* not convert numbers directly preceded by text, and it will convert
* numbers followed by text if they are preceded by a space. It will
* convert numbers in scientific notation, if the exponent is signed. With
* an unsigned exponent, only the mantissa is converted.
*
* When the scan reaches the end of the string without finding a double to
* translate, this method returns Double.POSITIVE_INFINITY.
*
* The IOException can be thrown by the nextToken() method of the
* StreamTokenizer.
*
* public static void main(String argv[])
* throws IOException
*
* This is a test module which exercises some of the cases this software
* might be expected to find in text. This is not a complete or exhaustive
* test, but it does demonstrate the ability of the code to translate
* well-formed numbers from text to numeric format. In production code,
* this method (and the 'import doubleArray' associated with it) should
* be commented out, mostly to avoid importing doubleArray, which you
* may or may not have, since it is not part of this package. (It may
* become part of a package at some point, but I haven't done that yet.)
* If you want a copy of the source for doubleArray class, I plan to post
* it on my web page: http://www2.rpa.net/~tfarnum/my_java_page.html, and
* it is also posted on the java developers' FAQ at the Java Developer:
* http://www.digitalfocus.com/digitalfocus/faq/howdoi.html. (Search under
* my name or the phrase 'dot product'.) *
*
*/

import java.io.*;
import java.lang.*;
import doubleArray;

public class getDoubles {
private StreamTokenizer ST;

public getDoubles(String inString) {
ST = new StreamTokenizer(new StringBufferInputStream(inString));
ST.resetSyntax();
ST.whitespaceChars("\t".charAt(0), " ".charAt(0));
ST.wordChars("-".charAt(0), "d".charAt(0)); //'e' and '+' are special chars
ST.wordChars("f".charAt(0), "z".charAt(0)); //so we can handle them explicitly
ST.parseNumbers();
}

public double next()
throws IOException { //in nextToken()
int aType = 0;
boolean converted = false;
double tempdbl = Double.POSITIVE_INFINITY;

while(! converted && aType != StreamTokenizer.TT_EOF) {
aType = ST.nextToken();
if(aType == StreamTokenizer.TT_NUMBER) { //this token is a number
tempdbl = ST.nval;
converted = true;
aType = ST.nextToken(); //get next token to check for
if(aType == "e".charAt(0)) { //scientific notation
aType = ST.nextToken();
if(aType == "+".charAt(0)) { //number parser doesn't handle plus
aType = ST.nextToken();
}
if(aType == StreamTokenizer.TT_NUMBER) {
tempdbl = tempdbl * Math.pow(10, ST.nval);
} else {
ST.pushBack();
}
} else {
ST.pushBack();
}
}//if(aType == StreamTokenizer.TT_NUMBER)
}//while(! converted && aType != StreamTokenizer.TT_EOF)
if(converted) {
return tempdbl;
}
return Double.POSITIVE_INFINITY;
}//public double next()


public static void main(String argv[])
throws IOException { //in getD.next()
double temp = 3.4e-25;
doubleArray da = new doubleArray(10);
StringBuffer tempsb;
int i;
for(i = 0; i < 10; i++) {
da.getDoubleArray()[i] = temp;
temp = temp * Math.pow(10, i);
}
tempsb = new StringBuffer(da.toString());
tempsb.append("1234.5678 123eats456 789is234 6.745e+50 1.2867e3 -167.8 +876.1");
String something = tempsb.toString();
System.out.println(something);
getDoubles getD = new getDoubles(something);
while(temp != Double.POSITIVE_INFINITY) {
temp = getD.next();
System.out.println(String.valueOf(temp));
}
}//public static void main(String argv[])
}//public class getDoubles