Хочу поделиться с вами своим опытом по применению рекурсии и создании структур данных на ее основе.
Думаю, прежде всего, эта статья будет интересна новичкам. Таким же как я :)
Введение
Недавно я захотел создать для себя эдакий инструмент, который помогал бы мне (и вдруг еще кому-то) в моих рассуждениях, в разбиении чего-то большого на маленькие детали так, чтобы можно было потом увидеть эту структуру.
Я помнил, что есть такие штуки как Mind Map и есть структура данных дерево.
Тогда я задумался над тем, как ее создать, эту структуру.
К тому же мне нужен проект для демонстрации своих умений и для практики.
В моем распоряжении были HashMap, ArrayList. И все бы ничего, но что если мне потребуется писать такое количество элементов, которое я не знаю изначально.
Тогда я решил использовать рекурсию. Рекурсия вообще интересная штука, которую я не понимал. Как это функция вызывает себя, если ей для вызова себя надо вызвать функцию, которой для вызова ..... :)
В общем не сразу укладывалось в понимании.
Но я знал, что в рекурсии можно глубоко и далеко погружаться. А это было то, что надо. Я буду создавать пункты и ветки до тех пор, пока не скажу "хватит", а потом структура развернется и перейдет к следующему пункту.
В голове все рисовалось понятно.
А вот с реализацией я помучался. Проблема еще в том, что я работаю и уделять много времени не мог. Делал урывками.
И с первого раза не получилось ничего. Сходу рекурсия отказалась погружаться, да и возвращалась она не туда куда я задумывал изначально.
Тогда я стал вручную создавать HashMap, чтобы понять строение. Хватило пары веток для понимания.
Решил, что буду создавать структуру вида HashMap().
В Object я смогу спокойно поместить такую же карту, и также спокойно вытащить ее оттуда (прежде я протестировал это предположение на кусочке кода :) новичок же :) )
После этого я создал первый метод, который погружался в глубину и возвращался туда, откуда его запустили.
Если бы я был шаманом, то непременно пустился бы в пляс вокруг костра с бубном под луной :) Так я радовался :)
Все круто!
Но этого же недостаточно. А что. если у меня будет несколько вариантов, каждый из которых надо расписать "вниз"? И что, если каждый из нижних вариантов может расходиться еще в стороны? Вот это загадка.
Тут я помучался. Я столкнулся с тем, что не понимаю, что необходимо делать. И это сильно печалило. На день я забросил все это дело.
Но потом я подумал, что я уже умею создавать одиночные ветки, тогда я буду создавать их там где мне необходимо.
Тогда я создал метод, который аналогично предыдущему расширялся горизонтально до тех пор, пока я не скажу "стоп".
И получилось :)
Уже поднаторев в рекурсии я создал методы, который создавал "зримую" версию моей структуры.
Один из методов просто выводил в консоль структуру так, что была видна вложенность.
А второй метод был интересней. Я добавил HTML тегов , чтобы я мог симпатично вывести в HTML файл.
В итоге я создал основу, на которую собираюсь навесить работу в WEB. Подключить базу данных для сохранения этой всей стрктуры. Хотелось бы еще придумать функцию сохранения при заполнении, чтобы можно было возвращаться к написанию.
Уже что-то есть и это здорово.
Этим опытом я и хочу поделиться с вами, друзья Джаварашовцы.
Продолжение
Задумка в плане структуры примерно такая (не в плане визуальности).
Теперь о практической части. Алгоритм, код.
Все написано своими словами, могу и ошибиться в академических трактовках :)
Алгоритм создания "дерева":
1.создаю карту
2.добавляю в нее первый элемент, предварительно считав имя для этого первого элемента
3.спрашиваю о том, какие ветки у этого элемента
4.когда ветки кончаются (стоп-слово "no") перехожу к первому из вариантов и начинаю строить аналогичную структуру для этого элемента (пункты 1 - 3)
5.когда на последнем из элементов ставлю стоп-слово, тогда создание HashMap-ы заканчивается
Затем я строю из имен узлов дерева строку с HTML тегами.
Полученную строку вывожу в консоль.
public class Main {
static String consoleEncoding = "UTF-8"; //для корректного вывода в консоль Linux и IDEA
// static String consoleEncoding = "Cp866"; //для корректного вывода в консоль Windows
public static void main (String[] args) throws Exception {
//создал основную карту
HashMap map = new HashMap<>();
//поместил в нее первый элемент
HashMap map0 = new HashMap<>();
PrintStream systemOut = System.out;
PrintStream printStream = new PrintStream(System.out, true, consoleEncoding);
System.setOut(printStream);
//начал заполнение с корня
System.out.println("Что хочешь расписать по частям, разобрать? Что хочешь сделать?");
Scanner scanner = new Scanner(System.in);
String answer1 = scanner.nextLine();
//поместил корень в основную карту
map.put(answer1, map0);
//поехали заполнять ветками (метод для работы "в ширину")
addBranchWithDialog(map0);
String toHTML = mapToHTML(map); // строка для HTML
System.out.println(toHTML);
System.setOut(systemOut);
printMap(map, 0); // вывод на консоль
scanner.close();
}
}
В HTML вывод получается примерно такой.
Количество вложенностей зависит только от фантазии :)
ВРЕМЯ
дни недели
вторник
среда
пятница
понедельник
четверг
воскресенье
поработал - отдохни :)
суббота
времена года
осень
весна
лето
зима
время суток
вечер
день
ночь
утро
длинный текст
Стандартно обычно пишут Lorem upsum. Но я так поступать не буду:) Тут будет просто длинная строка в которой не может быть энтеров, иначе перейдем к следующему элементу. Изначально не рассчитывалось на длинные строки и большие блоки
Вывод в консоль более прозаичен
ВРЕМЯ
дни недели
вторник
среда
пятница
понедельник
четверг
воскресенье
поработал - отдохни :)
суббота
времена года
осень
весна
лето
зима
время суток
вечер
день
ночь
утро
длинный текст
Стандартно обычно пишут Lorem upsum. Но я так поступать не буду:) Тут будет просто длинная строка в которой не может быть энтеров, иначе перейдем к следующему элементу. Изначально не рассчитывалось на длинные строки и большие блоки
Методы
Метод addBranchWithDialog() начинает спрашивать имена подпунктов, и эти имена добавляет в ArrayList пока не будет стоп-слова "no"
Затем по всем элементам списка по порядку начинает создавать ветки "вниз" messageRecurs()
Метод по добавлению "вниз" сам в свою очередь сразу начинает использовать метод addBranchWithDialog(), который
/**
* static method to create branches in width. horizontal growth
* @param map where add new branches
* @throws IOException
*/
public static void addBranchWithDialog(HashMap map) throws IOException {
System.out.println("Что-то для этого надо сделать? Если надо то что? ");
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, consoleEncoding));
String data = reader.readLine();
ArrayList answers = new ArrayList<>();
while (!"no".equalsIgnoreCase(data)) {
answers.add(data);
System.out.println("Что-то еще? ");
data = reader.readLine();
}
for (String answer: answers) {
map.put(answer, messageRecurs(answer));
}
}
/**
* static method for creating HashMap, where each of all elements has into yourself another map. Uses recursion
* increase in depth
* @return HashMap
* @throws IOException
*/
public static HashMap messageRecurs(String data) throws IOException {
HashMap hashMap = new HashMap<>();
System.out.println(data + "."); //чтобы видеть для какой ветки сейчас идет добавление веток в ширину
addBranchWithDialog(hashMap);
return hashMap;
}
Методы по выводу информации
/**
* print map structure to console using custom delimiter "delim"
* @param map to print
* @param n start from
*/
public static void printMap (HashMap map, int n) {
StringBuilder builder = new StringBuilder("");
String delim = " ";
for (int i = 0; i < n; i++) {
builder.append(delim);
}
String prefix = builder.toString();
String result = "";
for (Map.Entry pair : map.entrySet()) {
String key = pair.getKey();
result = prefix + key;
HashMap value = (HashMap) pair.getValue();
System.out.println(result);
printMap(value, n + 1);
}
}
/**
* method for adding HTML tags to map's elements
* in this case that is tag
*
* now there's some problem with encoding in this method.
* need to create a html template for print out. to add "charset=utf-8"
* @param hashMap our main map
* @return String to view
*/
public static String mapToHTML(HashMap hashMap) {
StringBuilder builder = new StringBuilder();
builder.append("
");
for (Map.Entry pair: hashMap.entrySet()) {
String key = pair.getKey();
HashMap value = (HashMap) pair.getValue();
builder.append("
");
return builder.toString();
}
Еще один пример строения карты:
Хочу стать Java программистом
Изучать дополнительные материалы
делать свои проекты
начать воплощать свои идеи в жизнь.
широко открыть глаза и уши и смотреть в чем нуждаются люди (Так был создан Facebook)
Хорошо учиться на JavaRush
попасть на стажировку
дойти до 30-го уровня и решить большинство задач
More practice
решить тестовое задание
сделать в срок
купить подписку Intership + или Mentor+
вложить денежку в свое обучение
Каждый день решать задачи
выделить минимум час времени на изучение материала и решение задач
Предупредить своих. чтобы не беспокоили
зарядить наконец-то телефон
Написать всем СМС-ки
Если есть вопросы, то задавать их на портале помощи help.javarush.ru
в вопросе писать условие задачи
Зарегистрироваться на портале
пользоваться поиском
Напоследок
С удовольствием передаю свой опыт вам, друзья. Буду рад, если кому поможет. Буду рад пообщаться с умными людьми в комментах. Буду рад идеям :)
p.s. Буду продолжать трудиться над этим проектом. Уже освоил создание jar-архивов и корректный вывод в консоль виндовс ( вообще отдельная история с этим Windows o_O). Поработаю над шаблоном для вывода в HTML. Научусь сохранять объекты в файл (сейчас как раз тема сериализации)
До новых встреч!
Теперь о практической части. Алгоритм, код.
Все написано своими словами, могу и ошибиться в академических трактовках :)
Алгоритм создания "дерева":
1.создаю карту
2.добавляю в нее первый элемент, предварительно считав имя для этого первого элемента
3.спрашиваю о том, какие ветки у этого элемента
4.когда ветки кончаются (стоп-слово "no") перехожу к первому из вариантов и начинаю строить аналогичную структуру для этого элемента (пункты 1 - 3)
5.когда на последнем из элементов ставлю стоп-слово, тогда создание HashMap-ы заканчивается
Затем я строю из имен узлов дерева строку с HTML тегами.
Полученную строку вывожу в консоль.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ