Информация


Programm.ws - это сайт, на котором вы можете почитать литературу по языкам программирования, а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..

Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.

Глава 2. Сложные структуры данных

Лексикографическое дерево

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

  • Чтение текстового файла и построение соответствующего ему лексикографического дерева. Для этого будем читать и проверять на предмет новизны каждое слово в анализируемом тексте. Если слово встретилось впервые, то необходимо сформировать и внести в дерево узел, который структурно состоит из двух полей: поля для хранения самого слова и поля для хранения частоты встречаемости этого слова в тексте.
  • Для вывода на экран статистики необходимо совершить левосторонний обход дерева. Если изменить условия вывода статистики, например упорядочить слова по частоте встречаемости в тексте, то необходимо выполнить перестроение дерева и его последующий правосторонний обход.

Для простоты преобразования положим, что каждое слово может встречаться в тексте не более 9 раз. Длина слова — не более 10 символов (для экономии места контроль количества вводимых символов не производится). Слова в файле разделяются одним пробелом. Также для сокращения текста программы считаем, что имя входного файла фиксировано — in.File.txt.
Программа построения лексикографического дерева prg_12_78.asm имеет достаточно большой размер, в связи с чем ее текст вынесен на дискету.
Бинарные деревья — не единственный вид деревьев, которые могут быть использованы в ваших программах. В литературе можно ознакомиться с представлениями деревьев, отличных от бинарных. Мы не будем развивать далее проблему представления деревьев, хотя, честно говоря, очень хочется. За кадром остались такие важные проблемы, как балансировка деревьев, работа с В-деревь-ями и т. д. После столь обстоятельного введения и наличия соответствующей литературы, вы сможете без особого труда решить эти и другие проблемы. Тем более, что на худой конец любое дерево можно преобразовать в бинарное и работать с ним, используя приемы, описанные в настоящем разделе.
В преддверии рассмотрения следующего материала отметим, что разработанная в этом разделе программа будет очень полезна в процессе построения различных транслирующих программ, частным случаем которых являются компиляторы. Лексикографические деревья можно с успехом использовать в процессе работы сканера, задачей которого, в частности, является выяснение принадлежности некоторого идентификатора к ключевым словам некоторого языка. Введите в файл infile.txt список ключевых слов (разделенных одним пробелом), запустите программу и в памяти вы получите лексикографическое дерево.