1

Dictionary ADT インターフェイスを実装する Hashtable を使用した電話帳が必要なこの課題に取り組んでいます。私のファイルはエラーなしで完全に機能していますが、欠点が 1 つだけあります。ハッシュテーブルのキー値がソートされません。特定の数字の組み合わせで電話番号を検索すると、それらはソートされた順序で表示されるはずです。

このクイックソート以外にシェルソートも試してみましたが、役に立たないようです。ここに私がしようとしているものがあります:

public class KeyIterator implements Iterator<K> {
    private DictionaryNode[] nodes, n;
    private int index;
    long modCheck;
    private DictionaryNode[] quickSort(DictionaryNode array[]){         
        n=array;
        quickSort(0, n.length-1);
        return n;

    }
    private void quickSort(int left, int right){
        if(right-left<=0)
            return;
        DictionaryNode pivot=n[right];
        int partition=getPartition(left,right, pivot);
        quickSort(left,partition-1);
        quickSort(partition+1,right);
    }

    private int getPartition(int left, int right, DictionaryNode pivot){
        int lPtr=left-1;
        int rPtr=right;
        for(;;){
            while(n[++lPtr].compareTo(pivot)<0);
            while(rPtr>0 && n[--rPtr].compareTo(pivot)>0);
            if(lPtr>=rPtr)
                break;
            else swap(lPtr, rPtr);
        }
        swap(lPtr, right);
        return lPtr;
    }

    private void swap(int lPtr1, int rPtr2) {
        DictionaryNode temp=n[lPtr1];
        n[lPtr1]=n[rPtr2];
        n[rPtr2]=temp;

    }
    public KeyIterator() {
        nodes = new DictionaryNode[currentSize];
        index = 0;
        modCheck=modCount;
        int j = 0;
        for (int i = 0; i < tableSize; i++){

            for (DictionaryNode n : list[i]) 
                nodes[j++] = n;
        }

         nodes = (DictionaryNode[]) quickSort(nodes);

    }

コードに Java API を使用することは想定されていません。

4

1 に答える 1

0

デバッグを容易にするために、ループ内のプレフィックスの増分を変更する必要があります。最初にカウンターをインクリメントしてから、アルゴリズムが意図していない間に配列要素を呼び出す傾向があります。

例えば：

から while(n[++lPtr].compareTo(pivot)<0);

に

while(n[lPtr].compareTo(pivot)<0) lPtr++;

また、に変更if (;;)しwhile (rPtr <= lPrt)て取り除く

if(lPtr>=rPtr) break;

デバッグするのが混乱しているように見えるだけです。これで少しでも変化を感じていただければ幸いです。

于 2012-12-02T05:57:02.407 に答える