#java
#java
Вопрос:
Я пытаюсь подсчитать с помощью рекурсии количество индексов в очереди. Очередь — это список, и он состоит из функций, которые находятся в классе «Queue». Сейчас у меня есть функция, которая подсчитывает индексы, но также удаляет их. Я перепробовал ВСЕ и до сих пор безуспешно, поэтому я прошу вас, ребята, помочь мне. Я должен добавить, что если вы видите функцию, которая начинается с заглавной буквы, ИГНОРИРУЙТЕ ее и, пожалуйста, ведите себя так, как будто она не с заглавной буквы, Спасибо! 🙂
public class Queue<T>
{
private Node<T> first;
private Node<T> last;
public Queue()
{
this.first = null;
this.last = null;
}
public void Insert(T x)
{
Node<T> temp = new Node<T>(x);
if (first == null)
first = temp;
else
last.setNext(temp);
last = temp;
}
public T Remove()
{
T x = first.getValue();
first = first.getNext();
if (first == null)
last = null;
return x;
}
public T Head()
{
return first.getValue();
}
public boolean IsEmpty()
{
return first == null;
}
public String toString()
{
String s = "[";
Node<T> p = this.first;
while (p != null)
{
s = s p.getValue().toString();
if (p.getNext() != null)
s = s ",";
p = p.getNext();
}
s = s "]";
return s;
}
}
public class Node<T>
{
private T value;
private Node<T> next;
public Node(T value)
{
this.value = value;
this.next = null;
}
public Node(T value, Node<T> next)
{
this.value = value;
this.next = next;
}
public T getValue()
{
return value;
}
public Node<T> getNext()
{
return next;
}
public void setValue(T value)
{
this.value = value;
}
public void setNext(Node<T> next)
{
this.next = next;
}
public String toString()
{
return this.value " " next;
}
}//Class
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new Queue<Integer>();
q.Insert(1);
q.Insert(2);
q.Insert(3);
q.Insert(4);
System.out.println("Queue: " q);
countIndex(q);
System.out.println("Queue after the function: " q);
}
public static int countIndex(Queue<Integer> q) {
if(q.Head() == null) return 0;
q.Insert(q.Remove());
return 1 countIndex(q);
}
}//class
Комментарии:
1. Хотя я знаю ответ в глубине души, я просто должен спросить: обязательно ли вам использовать рекурсивный алгоритм для определения размера очереди? Почему бы просто не отслеживать размер по мере добавления и удаления элементов и иметь
getSize()
метод?2. К вашему ответу, ДА, я должен использовать рекурсию. Итак, можете ли вы, плз, сказать мне ответ?
Ответ №1:
Я не знаю, почему вы должны использовать рекурсию, но вот пара методов для вашего класса Queue, которые используют рекурсию и возвращают количество узлов в вашем связанном списке (очереди):
private int rsize(Node<T> p) {
if (p == null)
return 0;
return rsize(p.getNext()) 1;
}
public int size() {
return rsize(first);
Ответ №2:
Никаких гарантий, но что-то вроде этого должно это сделать:
public static int countIndex(Queue<Integer> q) {
return countIndex(q, new Queue<Integer>());
}
private static int countIndex(Queue<Integer> q,
Queue<Integer> temp)
{
int size = 0;
if(q.Head() != null) {
temp.Insert(q.Remove());
size = 1 countIndex(q, temp);
q.Insert(temp.Remove());
}
return size;
}
Комментарии:
1. Вы, ребята, используете функции, которых нет в отделе очередей или узле…
2. Что вы имеете в виду? Я использую только
Head()
,Insert(T)
иRemove()
, которые все являются частьюQueue
.