0

私の割り当ては、ユーザーに小文字の文字列を入力させるプログラムで、ADTリストの参照ベースの実装とADTスタックの配列ベースの実装を使用することでした。文字列を調べて、各文字をリストとスタックの両方に格納してから、スタックとリストの内容を使用して、文字列が回文であるかどうかを判断しました。元の文字のシーケンス、文字のシーケンスを逆の順序で表示し、最後に、回文であるかどうかのステートメントを表示します。どういうわけか、回文を入力すると、例：マダミマダム、それは回文ではないことを出力します。理由がわからないので、助けてください！メソッドのコードは次のとおりです。

import javax.swing.JOptionPane;

public class PalindromeTester
{    
    public static void main (String [] args)
    {    
        Character ch;
        boolean isPalindrome = true;
        LinkedList myList = new LinkedList();
        StackArrayBased myStack = new StackArrayBased();
        String response = JOptionPane.showInputDialog ("Please enter a string of lower-case letters" ) ;

        for ( int i = 0 ; i < response.length ( ) ; i++ )
        {
            ch = new Character ( response.charAt ( i ) ) ;
            myStack.push ( ch ) ;
            myList.add ( i + 1 , ch ) ;
        }

        System.out.println ( "The original sequence of characters is: " + response ) ;
        System.out.print ( "The sequence of letters backwards is: " ) ;

        int j = 1 ;
        while ( ! myStack.isEmpty ( ) )
        {
            System.out.print ( myStack.peek ( ) ) ;
            if ( ! myList.get ( j ).equals( myStack.pop (  ) ) ) ;
            isPalindrome = false ;
        }

        if ( isPalindrome )
            System.out.println ( "\nThe string is a palindrome." ) ;
        else
            System.out.println ( "\nThe string is not a palindrome." ) ;
    }
}

ADTスタッククラスは次のとおりです。

public class StackArrayBased
{
    private static final int MAX_STACK = 15 ;
    private Object items [ ] ;
    private int top ;    

    public StackArrayBased ( )
    {
        items = new Object [ MAX_STACK ] ;
        top = -1 ;
    }

    public boolean isEmpty ( )
    {
        return top < 0 ;
    } 

    public boolean isFull ( )
    {
        return top == MAX_STACK - 1 ;
    }

    public void push ( Object newItem ) throws StackException
    {
        if ( ! isFull ( ) )
            items [ ++ top ] = newItem ;
        else
            throw new StackException ( "StackException on push: stack is full" ) ;
    }

    public void popAll ( )
    {
        items = new Object [ MAX_STACK ] ;
        top = -1 ;
    }

    public Object pop ( ) throws StackException
    {
        if ( ! isEmpty ( ) )
            return items [ top -- ] ;
        else
            throw new StackException ( "StackException on pop: stack is empty" ) ;
    }

    public Object peek ( ) throws StackException
    {
        if ( ! isEmpty ( ) )
            return items [ top ] ;
        else
            throw new StackException ( "StackException on peek: stack is empty" ) ;
    }
}

ADTリストは次のとおりです。

public class LinkedList
{
    private Node head;
    private int numItems;    

    public LinkedList ( )
    {
        head = null ;
        numItems = 0 ;
    }

    public boolean isEmpty ( )
    {
        return numItems == 0 ;
    }

    public int size ( )
    {
        return numItems ;
    }

    private Node find ( int position )
    {
        Node curr = head ;
        for ( int i = 1 ; i < position ; i ++ )
            curr = curr.getNext ( ) ;

        return curr ;
    }

    public Object get ( int position )
    {
        if ( position >= 0 && position <= numItems )
        {
            Node curr = find ( position ) ;
            Object dataItem = curr.getItem ( ) ;
            return dataItem ;
        }
        else
        {
            System.out.println ( "Error in position value during get attempt." ) ;
            return null ;
        }
    }

    public void add ( int position, Object item )
    {
        if ( position >= 1 && position <= numItems + 1 )
        {
            if ( position == 1 )
            {
                Node newNode = new Node ( item, head ) ;
                head = newNode ;
            }
            else
            {
                Node prev = find ( position - 1 ) ;
                Node newNode = new Node ( item, prev.getNext ( ) ) ;
                prev.setNext ( newNode ) ;
            }

            numItems ++ ;
        }
        else
            System.out.println ( "Position is invalid on attempted add." ) ;
    }

    public void remove ( int position )
    {
        if ( position >= 1 && position <= numItems )
        {
            if ( position == 1 )
                head = head.getNext ( ) ;
            else
            {
                Node prev = find ( position - 1 ) ;
                Node curr = prev.getNext ( ) ;
                prev.setNext ( curr.getNext ( ) ) ;
            }

            numItems -- ;
        }
        else
            System.out.println ( "Position is invalid on attempted remove." ) ;
    }

    public void removeAll ( )
    {
        head = null ;
        numItems = 0 ;
    }
}
4

3 に答える 3

0

正しく設定したい場合は 、このループでisPalindrome何かを行うべきではありませんか?:j

[...]
int j = 1 ;
while ( ! myStack.isEmpty ( ) )
{
  System.out.print ( myStack.peek ( ) ) ;
  if ( ! myList.get ( j ).equals( myStack.pop (  ) ) ) ;
        isPalindrome = false ;
}
[...]
于 2011-04-18T20:19:29.537 に答える
0

2 番目のループでは、j をインクリメントする必要があります。リンクリストのインデックスは 0 になる可能性があるため、(最初のループで) を追加するときに i+1 インデックスを実行するべきではありません。0 ベースのインデックスにする場合は、2 番目のループの前に j を 0 に初期化する必要があります。

于 2011-04-18T20:20:37.673 に答える
0

割り当ては奇妙に思えます。リストの最後の要素にアクセスできる場合（ほとんどの言語で抽象リストが許可されているため）、次のことを実行できますfor i=[0,length) {if input[i]!=input[length-1-i], return false} return true

また、遊ぶスタックがある場合は、スタックを複製して反転させ (たとえば、2 つのスタックにプッシュし、そのうちの 1 つを新しいスタックにポップして反転させる)、 for ループと同じことを行うことができます。 (2 つのスタックを要素ごとに調べて、それらが同じかどうかを確認します)。

上記の両方の線形時間アルゴリズム (リストのみを使用するアルゴリズム、またはスタックのみを使用するアルゴリズム) では、関数は 3 行程度にする必要があります。

于 2011-04-18T20:23:58.140 に答える