Песни о Паскале
Шрифт:
• Элементы списка – это записи, содержащие в числе прочих данных указатель на следующую запись в списке.
• Элементы списка помещают в кучу и связывают между собой внедренными в них указателями.
• Первый элемент доступен через голову списка (указатель в статической памяти программы). Остальные элементы доступны по цепочке указателей, встроенных в записи.
• Сортировку списка можно совместить с его вводом.
А слабо?
А) Напишите функцию для подсчета элементов списка; она должна принимать указатель на голову списка, а возвращать
Б) Начертите блок-схему вставки записи в сортированный список.
В) Напишите процедуру для удаления первого элемента списка. Или слабо?
Г) Напишите процедуру сортировки уже готового списка. Подсказка: последовательно извлекайте элементы из несортированного списка и вставляйте в сортированный (потребуется две головы для двух списков).
Задачи на темы предыдущих глав
Д) В задаче 53-Г была представлена модель «глупого» винчестера. «Умный» винчестер отличается организацией внутренней очереди и челночным движением головки, которая следует попеременно то от внутренней дорожки к внешней, то обратно, попутно выполняя все накопившиеся в очереди запросы. Направление движения переключается, когда в текущем направлении не остается запросов, поэтому головка редко достигает крайних дорожек.
Ваша программа должна подсчитать общее время обработки запросов «умным» контроллером для набора данных из входного файла, составленного по правилам для задачи 53-Г. Создайте несколько наборов таких данных и сравните время их обработки двумя типами контроллеров: «умным» и «глупым».
Подсказка: для организации внутренней очереди контроллера здесь можно применить массив чисел (счетчиков). Каждый счетчик будет хранить текущее количество запросов для своей дорожки. При постановке запроса в очередь счетчик наращивается, а при извлечении уменьшается.
Глава 55
Слова, слова, слова…
Односвязные списки подоспели как раз вовремя, – сейчас они поработают в необычном проекте.
Частотный анализ текста
Однажды разгорелся спор об известном романе «Тихий Дон», – некоторые литераторы усомнились в авторстве Михаила Шолохова. Их сомнения развеяли программисты, вычислившие частотные характеристики нескольких его произведений. Что это за характеристики такие?
Предположим, вы подсчитали, что слово «Паскаль» упомянуто в этой книге 150 раз, а всего в книге 10000 слов. Тогда относительная частота слова «Паскаль» в книге составит 150 / 10000 = 0,015 или 1,5%. Если найти частоту употребления других слов книги, и расположить эти результаты в некотором порядке, то получится картина, подобная отпечатку пальца. У разных авторов эти «отпечатки» разные, зато у одного автора в разных произведениях – очень похожи! Обработав таким частотным анализатором несколько книг Михаила Шолохова, специалисты сравнили результаты и обнаружили на романе «Тихий Дон» «пальчики» донского писателя.
Слово за слово
Итак, мы беремся за разработку слегка упрощенного частотного анализатора.
Наша программа будет читать не романы, а текстовые файлы, – возьмем файл какой-либо из наших программ, и посчитаем в нём слова, составленные из латинских букв. Для упрощения программы русские слова считать не будем, и пропустим слова, состоящие из одной буквы. Зато примем в расчет слова с цифрами и знаками подчеркивания, например, такие.
Begin, NIL, P1, q2, Words_Count, _1_
Нам предстоит выудить из текста подходящие слова, перевести их в верхний регистр, отсортировать по алфавиту и пересчитать.
Структура записи
Накапливать слова будем в списке, а потому разработку программы начнем с конструирования надлежащей записи. Очевидно, что в ней надо предусмотреть строку для слова и числовое поле для счетчика. Стало быть, структура элемента списка будет такой.
TRec = record { Тип записи для подсчета слов }
mWord : string; { Слово из текста – 256 байт }
mCount : Longint; { Счетчик слов – 4 байта }
mNext : PRec; { Указатель на следующий – 4 байта }
end;
Сколько памяти займет один такой элемент? Сейчас посчитаем: 256+4+4=264 байта, – не так уж мало! Полагаю, что для слова достаточно и тридцати символов. Но, прежде, чем окончательно выбрать длину строки, открою небольшой секрет, – он касается выделения динамической памяти. Сколько бы памяти ни запросила программа, операционная система выделит кусочек, кратный восьми байтам. То есть, часть байтов в выделяемой порции может быть лишней. Значит, предпочтительный размер записи для динамических переменных кратен восьми байтам. В нашем случае размер записи можно уменьшить до 40 байтов, если объявить её так:
TRec = record { Тип записи для подсчета слов }
mWord : string[31]; { Слово из текста – 32 байта }
mCount : Longint; { Счетчик слов – 4 байта }
mNext : PRec; { Указатель на следующий – 4 байта }
end;
С одной стороны, число 40 кратно 8, а с другой стороны, 31-го символа для слова вполне достаточно.
Алгоритм
Теперь обсудим алгоритм обнаружения и обработки слов. В чем состоит эта обработка? Найдя выделенное слово в списке, нарастим его счетчик – поле mCount, а если слова в списке ещё нет, добавим запись с этим словом и счетчиком, равным единице.
Можно придумать много способов выборки слов из файла. Один из них – построчная обработка, когда каждую строку можно обработать так.
1. Перекодировать все символы строки в верхний регистр.
2. Удалить из начала строки все символы, которые не являются латинской буквой или подчеркиванием, и, если строка стала пустой, то завершить процедуру.
3. Выделить из строки очередное слово и удалить его из строки.
4. Искать слово в списке.
5. Если слово найдено, нарастить его счетчик, а иначе вставить в список запись со счетчиком, равным единице.