Java: руководство для начинающих (ЛП) - Шилдт Герберт

Добавьте в данный класс конструктор, инициализирующий очередь данными из символьного массива, как показано ниже. // Конструирование и инициализация объекта типа Queue. Queue(char а [ ]) { putloc = 0; getloc = 0; q = new char[a.length+1]; for(int i = 0; i < a.length; i++) put(a[i]); }

В этом конструкторе создается достаточно большая очередь для хранения символов из массива а. В силу особенностей алгоритма, реализующего очередь, длина очереди должна быть на один элемент больше, чем длина исходного массива.

Ниже приведен весь код видоизмененного класса Queue, а также код класса QDemo2, демонстрирующего организацию очереди для хранения символов и обращение с ней.```// Класс, реализующий очередь для хранения символов,class Queue {private char q[]; // Массив для хранения элементов очереди,private int putloc, getloc; // Индексы размещения и извлечения // элементов очереди.

// сконструировать пустую очередь заданного размераQueue(int size) {q = new char[size+1]; // выделить память для очередиputloc = getloc = 0;

}

// сконструировать очередь из существующего объекта типа QueueQueue(Queue ob) {putloc = ob.putloc;getloc = ob.getloc;q = new char[ob.q.length];// копировать элементы в очередьfor (int i=getloc+l; i <= putloc; i++) q[i] = ob.q[i];

}

// сконструировать очередь из массива исходных значенийQueue(char а[]) {putloc = 0;getloc = 0;q = new char[a.length+1];for(int i = 0; i < a.length; i++) put(a[i]);

}

// поместить символ в очередьvoid put(char ch) {if(putloc==q.length-1) { System.out.println(" - Queue is full."); return;}putloc++;q[putloc] = ch;

}

// извлечь символ из очередиchar get() {if(getloc == putloc) { System.out.println(" - Queue is empty."); return (char) 0;}getloc++;return q[getloc];

}}

// продемонстрировать класс Queue в действииclass QDemo2 { public static void main(String args[]) { // построить пустую очередь для хранения 10 элементов Queue ql = new Queue(10); char name[] = {'Т', 'o', 'm'}; // построить очередь из массива Queue q2 = new Queue(name); char ch; int i; // поместить ряд символов в очередь ql for(i=0; i < 10; i++) ql.put((char) ('A1 + i)); // построить одну очередь из другой очереди Queue q3 = new Queue(ql); // показать очереди System.out.print("Contents of ql: "); for(i=0; i < 10; i++) { ch = ql.get(); System.out.print(ch); } System.out.println("n"); System.out.print("Contents of q2: "); for(i=0; i < 3; i++) { ch = q2.get(); System.out.print(ch); } System.out.println("n"); System.out.print("Contents of q3: "); for(i=0; i < 10; i++) { ch = q3.get(); System.out.print(ch); }}

}```Результат выполнения данной программы выглядит следующим образом:```Contents of ql: ABCDEFGHIJContents of q2: TomContents of q3: ABCDEFGHIJ```Рекурсия

В Java допускается, чтобы метод вызывал самого себя. Этот процесс называется рекурсией, а метод, вызывающий самого себя, — рекурсивным. Вообще говоря, рекурсия представляет собой процесс, в ходе которого нечто определяет самое себя. В этом отношении она чем-то напоминает циклическое определение. Рекурсивный метод отличается в основном тем, что он содержит оператор, в котором этот метод вызывает самого себя. Рекурсия является эффективным механизмом управления программой.

Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N представляет собой произведение всех целых чисел от 1 до N. Например, факториал числа 3 равен 1x2x3, или 6. В приведенном ниже примере программы демонстрируется рекурсивный способ вычисления факториала числа. Для сравнения в эту программу включен также нерекурсивный вариант вычисления факториала числа.// Простой пример рекурсии,class Factorial { // Рекурсивный метод, int factR(int n) { int result; if(n==l) return 1; // Рекурсивный вызов метода factRO . result = factR(n-l) * n; return result; } // Вариант программы, вычисляющий факториал итеративным способом, int factl(int n) { int t, result; result = 1; for(t=l; t <= n; t++) result *= t; return result; }}class Recursion { public static void main(String args[]) { Factorial f = new Factorial(); System.out.println("Factorials using recursive method."); System.out.println("Factorial of 3 is " + f.factR(3)); System.out.println("Factorial of 4 is " + f.factR(4)); System.out.println("Factorial of 5 is " + f.factR(5)); System.out.println(); System.out.println("Factorials using iterative method."); System.out.println("Factorial of 3 is " + f.factl(3)); System.out.println("Factorial of 4 is " + f.factl(4)); System.out.println("Factorial of 5 is " + f.factl(5)); }}

Ниже приведен результат выполнения данной программы.Factorials using recursive method.Factorial of 3 is 6Factorial of 4 is 24Factorial of 5 is 120Factorials using iterative method.Factorial of 3 is 6Factorial of 4 is 24Factorial of 5 is 120

Действия нерекурсивного метода fact I () не требуют особых пояснений. В нем используется цикл, в котором числа, начиная с 1, последовательно умножаются друг на друга, постепенно образуя произведение, дающее факториал.

Рекурсивный метод f actR () действует несколько сложнее. Когда метод factR() вызывается с аргументом, равным 1, он возвращает 1, а иначе —произведение, определяемое из выражения factR(n-l)*n. Для вычисления этого выражения вызывается метод factR () с аргументом п-1. Этот процесс повторяется до тех пор, пока значение переменной п не окажется равным 1, после чего из предыдущих вызовов данного метода начнут возвращаться полученные значения. Например, при вычислении факториала 2 первый вызов метода factR () повлечет за собой второй вызов того же самого метода, но с аргументом 1. В результате метод возвратит значение 1, которое затем умножается на 2 (т.е. исходное значение переменной п). В результате всех этих вычислений будет получен факториал, равный 2. По желанию в тело метода factR () можно ввести операторы println (), чтобы сообщать, на каком именно уровне осуществляется очередной вызов, а также отображать промежуточные результаты вычислений.

Когда метод вызывает самого себя, в системном стеке распределяется память для новых локальных переменных и параметров, и код метода выполняется с этими новыми переменными и параметрами с самого начала. При рекурсивном вызове метода не создается его новая копия, но лишь используются его новые аргументы. А при возврате из каждого рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и выполнение возобновляется с точки вызова в методе. Рекурсивные методы можно сравнить по принципу действия с постепенно сжимающейся и затем распрямляющейся пружиной.

Рекурсивные варианты многих процедур могут выполняться немного медленнее, чем их итерационные эквиваленты, из-за дополнительных затрат системных ресурсов на неоднократные вызовы метода. Если же таких вызовов окажется слишком много, то в конечном итоге может быть переполнен системный стек. А поскольку параметры и локальные переменные рекурсивного метода хранятся в системном стеке и при каждом новом вызове этого метода создается их новая копия, то в какой-то момент стек может оказаться исчерпанным. Если возникнет подобная ситуация, исполняющая система Java сгенерирует исключение. Но в большинстве случаев об этом не стоит особенно беспокоиться. Как правило, переполнение системного стека происходит тогда, когда рекурсивный метод выходит из под контроля.

Главное преимущество рекурсии заключается в том, что она позволяет реализовать некоторые алгоритмы яснее и проще, чем итерационным способом. Например, алгоритм быстрой сортировки довольно трудно реализовать итерационным способом. А некоторые задачи, например искусственного интеллекта, очевидно, требуют именно рекурсивного решения. При написании рекурсивных методов следует непременно указать в соответствующем месте условный оператор, например if, чтобы организовать возврат из метода без рекурсии. В противном случае возврат из вызванного однажды рекурсивного метода может вообще не произойти. Подобного рода ошибка весьма характерна для реализации рекурсии в практике программирования. Поэтому рекомендуется пользоваться операторами, содержащими вызовы метода println (), чтобы следить за происходящим в рекурсивном методе и прервать его выполнение, если в нем обнаружится ошибка.Применение ключевого слова static