java中字符列表中字符的搜索方法

Question

我希望搜索添加的字符列表，并返回“是”或“否”的答案，以确定某个字符是否出现在我给定的列表中。我是新手，不太确定从哪里开始-任何帮助都将不胜感激，谢谢

class Csc2001Node
{
protected char ch;
protected Csc2001Node next;

/*
* Construct a Csc2001Node with the given character value 
* @param c - The character 
*/
public Csc2001Node (char c)
{
    this.ch = c;
    this.next = null;
}
}   

public class Csc2001LinkedListRec
{  /* A reference to the head of the list */
protected Csc2001Node head;
/*
* Construct a new empty list 
*/
public Csc2001LinkedListRec()
{
    head=null;
}

public Csc2001Node getHead()
{
    return head;
}


 /*
 * Finds the size of a list.
 * @param head The head of the current list
 * @return The Size of the Current List
 */
 private int size(Csc2001Node head) {
    if (head == null) {
        return 0;
    } else {
        return 1 + size(head.next);
    }
 }

 /*
 * Wrapper method for finding the size of a list.
 * @return The size of the list
 */
 public int size() {
    return size(head);
 }


 /*
 * Adds a new node to the end of a list.
 * @param head The head of the current list
 * @param c The character for the new node
 */
 private void add(Csc2001Node head, char c) {
    // If the list has just one character, add to it.
    if (head.next == null) {
        head.next = new Csc2001Node(c);
    } else {
        add(head.next, c); // Add to rest of list.
    }
 }

 /*
 * Wrapper method for adding a new node to the end of a list.
 * @param c The character for the new node
 */
 public void add(char c) {
    if (head == null) {
        head = new Csc2001Node(c); // List has 1 node.
    } else {
        add(head, c);
    }
 }


 /*
 *Test to see if this list is empty 
 *@returns true or false
 */ 
 public boolean isEmpty()
 {
    return (head == null);
 }


 /*
 * Replaces all occurrences of oldch with newch.
 * @post Each occurrence of oldch has been replaced by newch.
 * @param head The head of the current list
 * @param oldch The character being removed
 * @param newch The character being inserted
 */
 private void replace(Csc2001Node head, char oldch, char newch) {
    if (head != null) {
        if (oldch == head.ch) {
            head.ch = newch;
        }
        replace(head.next, oldch, newch);
    }
 }

 /*
 Wrapper method for replacing oldch with newch.
 * @post Each occurrence of oldch has been replaced by newch.
 * @param oldch The character being removed
 * @param newch The character being inserted
 */
 public void replace(char oldch, char newch) {
    replace(head, oldch, newch);
 }




 //added methods


 //method to recursively print the characters
 private String  recursePrintList(Csc2001Node head) {
    // TODO Auto-generated method stub
 if (head == null)
    return "List is empty";
 else
    while(head.next!=null){
        return head.ch+ recursePrintList(head.next);
    }
 return head.ch + " ";
 }

 /*
 * Wrapper to print out list
 *@return the list
 */

 public void recursePrintList(){
    System.out.println(recursePrintList(head));
 }




 //method to insert char d before char c
 private Csc2001Node insertBefore(char d, Csc2001Node head, char c) {
    // TODO Auto-generated method stub
     {   
            if(head==null){
                return head = new Csc2001Node(d);
            }                       
             else if(head.next.ch == c){
                 head = head.next;
                 head.next = new Csc2001Node(d);
                 head.next.next = head;
             }

        }
    return head;    

}

/*Wrapper method for inserting a char before another char
 * 
 */
public void insertBefore(char c, char d){
    head = insertBefore(c, head, d);
}

 public boolean search(char c) {


    return false;
 }


}

Answer 1

这段代码应该做到：

public boolean search(char c) {
    return search(head, c);
}


private boolean search(Csc2001Node node, char c) {
    if (node == null)
        return false;
    else if (node.ch == c)
        return true;
    else
        return search(node.next, c); 
}

更优雅但可读性较差：

public boolean search(char c) {
    return search(head, c);
}


private boolean search(Csc2001Node node, char c) {
    return node != null && (node.ch == c || search(node.next, c));
}

当然，对于非递归解决方案，可以使用循环

Answer 2

如果我理解正确的话，你是想用search()方法查看列表中是否有某个字符？如果是这样的话，你需要用一个循环遍历整个列表。检查当前值是否与传递给方法的字符匹配。如果到达列表的末尾，则返回false。应该是这样的：

public boolean search(char c) {
    Csc2001Node current = head;
    while (current is not at the end of the list) {
        if (current.character equals c) {
            return true;
        }
        current = current.next;
    }
    return false;
}

Answer 3

比如：

search(entry, ch)
    if entry == null
        return false
    if entry.ch == ch
        return true
    return search(entry.next, ch)

。。。这将是一个递归的解决方案。比如：

search(entry, ch)
    while entry != null
        if entry.ch == ch
            return true
        entry = entry.next
    return false

。。。这将是一个迭代的解决方案。我不会给你Java代码，只是伪代码，因为这看起来像是一个家庭作业