Material‎ > ‎

Lists as Arrays

Dieses Programm zeigt, wie Listen als Felder implementiert werden können.  Die Datenstruktur benutzt Amortisierung, um effiziente Speicherverwaltung zu erreichen.

Das Programm kann direkt in Beanshell (www.beanshell.org) ausgeführt werden, oder es kann in "prozedurales Java" durch Hinzufügen von Klassen und "static" umgewandelt werden.

// -*- bsh -*-

// This file is written in Beanshell; you can either run this code
// by using the bsh interpreter, or you can wrap all the global functions
// below into a class.

import java.util.Random;

// The following code illustrates how "lists" are represented in
// many modern programming languages.

class Flist {
    int[] data;
    int fill;
};

Flist make(int n) {
    Flist l = new Flist();
    l.data = new int[n];
    l.fill = 0;
    return l;
}

Flist make() {
    return make(10);
}

void push(Flist l,int x) {
    if(l.fill==l.data.length) {
        int ndata = new int[2*l.data.length];
        for(int i=0;i<fill;i++) ndata[i] = l.data[i];
        l.data = ndata;
    }
    l.data[l.fill++] = x;
}

int pop(Flist l) {
    return l.data[--fill];
}

int at(Flist l,int i) {
    return l.data[i];
}

int length(Flist l) {
    return l.fill;
}

void printl(Flist l) {
    System.out.print("[");
    for(int i=0;i<length(l);i++) {
        if(i>0) System.out.print(",");
        System.out.print(l.data[i]);
    }
    System.out.println("]");
}

// Let's generate a random list.

random = new Random();

Flist l = make();
for(int i=0;i<10;i++) {
    push(l,random.nextInt()%10);
}

printl(l);

// Push the elements of the second argument onto the end of the first
// argument.

void push_list(Flist onto,Flist l) {
    for(int i=0;i<length(l);i++)
        push(onto,at(l,i));
}

// A simple recursive quicksort that does not work in-place.

Flist quicksort(Flist l) {
    // If there are 0 or 1 elements, the list is already sorted and we
    // can just return it.

    if(length(l)<2) return l;

    // Let's pick a pivot.

    int pivot = at(l,length(l)/2);

    // First, we split the input into elements that are lower than the
    // pivot, equal to it, or higher.

    Flist lo = make();
    Flist eq = make();
    Flist hi = make();

    push(eq,pivot);

    for(int i=1;i<length(l);i++) {
        int value = at(l,i);
        if(value<pivot) push(lo,value);
        else if(value>pivot) push(hi,value);
        else push(eq,value);
    }

    // Now, we sort the lo and the hi elements.

    lo = quicksort(lo);
    hi = quicksort(hi);

    // Finally, we concatenate lo, eq, and hi into the result.  We
    // just reuse the lo list for this.

    push_list(lo,eq);
    push_list(lo,hi);
    return lo;
}

// Now, let's just test this.

printl(quicksort(l));

Comments