Уроки 71 - 73
Списки
(§41. Списки)
Содержание урока
Использование динамического массива
Использование динамического массива
В нашем случае каждый элемент списка должен содержать пару значений: слово (символьную строку) и счётчик этих слов (целое число). Поэтому элементы списка — это структуры, тип которых можно описать так:
Для организации списка будем использовать динамические массивы FreePascal.
Здесь размер массива становится известен только в конце работы программы. Поэтому требуется динамический массив, состоящий из описанных выше структур. С ним нужно выполнять следующие операции:
• искать заданное слово в списке;
• увеличивать счётчик заданного слова на 1;
• вставлять слово в определённое место списка (так, чтобы сохранить алфавитный порядок).
Как и в предыдущем параграфе, будем расширять размер массива сразу на 10 элементов 1, чтобы не выделять память слишком часто.
1 Возможны и другие варианты, например можно увеличивать размер массива в 2 раза.
Объявим структуру-список:
Напомним, что количество фактически используемых элементов массива size может быть меньше, чем количество элементов, размещённых в памяти.
Введём переменную L типа TWordList:
var L: TWordList;
В начале основной программы очистим список и установим для него нулевую длину:
SetLength(L.data,0); L.size:= 0;
Основной цикл (чтение данных из файла и построение списка) можно записать так (для последующего объяснения строки в теле цикла пронумерованы):
Здесь используются две вспомогательные переменные: символьная строка s (типа string) и целая переменная р. В строке 1 программы очередное слово читается из файла в строку s. Затем с помощью функции Find определяется, есть ли оно в списке (строка 2). Если есть (функция Find вернула существующий индекс), увеличиваем счётчик этого слова на 1 (строки 3-4) с помощью стандартной процедуры inc.
Если в списке слова ещё нет (функция Find вернула -1), нужно найти место, куда его вставить, так чтобы не нарушился алфавитный порядок. Это делает функция FindPlace, которая должна возвращать номер элемента массива, перед которым нужно вставить прочитанное слово. Вставку выполняет процедура InsertWord.
Здесь встретилось обозначение с двумя точками: L.data [р] .count. Вспомним, что L — это структура-список, у него есть поле-массив data. В этом массиве происходит обращение к элементу с номером р. Этот элемент — структура типа TPair, в составе которой есть поле count. Таким образом, L.data [р] .count означает: «Поле count в составе p-го элемента массива data, который входит в структуру L».
Когда список готов, остаётся вывести его в выходной файл:
Для каждого элемента списка в файл выводится хранящееся в нём слово и через двоеточие — сколько раз оно встретилось в тексте.
Таким образом, нам остаётся написать функции Find и FindPlace, а также процедуру InsertWord.
Функция Find принимает список и слово, которое нужно искать. Из курса 10 класса вы знакомы с двумя алгоритмами поиска: линейным и двоичным. Здесь для простоты будем использовать линейный поиск. В цикле проходим все элементы (не забывая, что их нумерация в динамическом массиве начинается с нуля). Как только очередное слово списка совпадёт с образцом, возвращаем в качестве результата функции номер этого элемента. Если просмотрены все элементы и совпадения не было, функция вернёт -1.
Функция FindPlace также принимает в качестве параметров список и слово. Она находит место вставки нового слова в список, при котором сохраняется алфавитный порядок расположения слов. Результат функции — номер слова, перед которым нужно вставить заданное. Для этого нужно найти в списке слово, которое «больше» заданного. Если такое слово не найдено, новое слово вставляется в конец списка:
Процедура InsertWord вставляет слово word в позицию k в список L:
Поскольку в список добавляется новый элемент, его размер увеличивается. Для этого введена процедура IncSize, которая вызывается в строке 1 (мы напишем её позже). Далее в цикле сдвигаем все последние элементы, включая элемент с номером k, на одну ячейку к концу массива (строки 2-3). Таким образом, элемент с номером k освобождается. В строке 4 в него записывается новое слово, а в строке 5 счётчик этого слова устанавливается равным 1.
Процедура IncSize увеличивает размер списка на 1 элемент. Когда нужный размер становится больше, чем размер динамического массива, массив расширяется сразу на 10 элементов.
Процедура IncSize в программе должна располагаться выше вызывающей её процедуры InsertWord.
Приведём окончательную структуру программы:
Блоки, выделенные серым фоном, уже были написаны ранее в этом параграфе.
Заметим, что если известно максимальное количество разных слов в файле (скажем, не более 1000), то же самое можно сделать и на основе обычного (статического) массива, в котором память выделена заранее на максимальное число элементов.
Следующая страница 
Модульность
Cкачать материалы урока
