Лекция 2. Списки, стеки, очереди.
Линейный список (ЛС) представляет собой последовательность n>=0 узлов x[1]...x[n],
важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно выполняться следующее условие:
если n>0 и x[1] является первым узлом, а x[n] - последним, то каждый узел x[k]
следует за x[k-1] и предшествует x[k+1] для всех 1<k<n .
Стек - это ЛС, в котором все операции вставки и удаления выполняются только на
одном из его концов.
Очередь или односторонняя очередь - это ЛС, в котором все операции вставки
выполняются на одном конце, а все операции удаления выполняются на другом
конце очереди.
Дек или двусторонняя очередь - это ЛС, в котором все операции вставки
и удаления выполняются на обоих концах.
Пример программы, строящей списки, стек, очередь в директории block2.
Лекция 3. Последовательности данных и файлы.
(Структура и особенности последовательности данных. Элементарные операции с последовательностями. Буферизованные последовательности. Стандартный ввод/вывод)
Несколько лет назад программисты в основном писали программы на ассемблере и в них при обращении к файлам использовались специальные методы доступа. При этом приходилось пользоваться разными способами буферизации данных. В настоящее время программисты в основном пишут программы на языках высокого уровня, и они часто не задумываются о том, как на самом деле происходит обращение к файлам. Но программистам надо знать, как функционируют методы доступа.
Вирт вводит тип для последовательности в языке Модула-2 следующим образом (в Pascal и Delphi их нет):
Type T = SEQUENCE OF T0;
Здесь T0 – базовый тип.
Последовательность s из n элементов – это s = (s0, s1,s2,…, sn-1).
n – длина последовательности. Последовательность очень похожа на массив
У последовательности число элементов n остается открытым (не ограничивается).
Последовательность – это какой-то аналог файла.
Предполагается, что в процессе работы программы это число n может меняться.
Хотя каждая последовательность в любой заданный момент времени имеет вполне определенную конечную длину, мы должны считать мощность последовательного типа бесконечной, поскольку на потенциальную длину переменных-последовательностей нет никаких ограничений. Поэтому для всей последовательности нельзя выделить память нужного размера.
Если надо расположить последовательность в памяти, то память надо выделять динамически, так как не знаем число членов.
Мы ограничиваемся последовательным доступом.
Буферизация предполагает, что части потока данных накапливаются в так называемых буферах, а затем при заполнении всего буфера, передаются куда надо.
Обработка файла - пример использования последовательности.
Ниже рассматривается простой пример обработки последовательности, что помогает лучше представить процессы, происходящие при обработке файлов в методах доступа.
Операции с последовательностями:
Open(s) – открывает последовательность s, определяя ее, как пустую.
Write(s,x) – записывает элемент x в последовательность s.
Reset(s) – устанавливает текущую позицию в начало s.
Read(s,x) – присваивает элементу x значение из текущей позиции, текущей позицией становится следующий элемент.
Буферизованные последовательности
Рис. 2. Круговой буфер с индексами IN и OUT.
IN - позиция для помещения в буфер
OUT - позиция для извлечения из буфера
В директории block3 приводится пример программы использования буферизованной последовательности. Сделано специальное опережение для записи в буфер по сравнению с чтением. В конце операции дочитывается остаток.
Существует много различных методов доступа для последовательной обработки файлов, для обработки с прямым доступом. Логические записи часто помещаются в блоки. Последовательные методы доступа поддерживают функции извлечения следующей логической записей из блока находящегося в оперативной памяти. Когда прочитаны все записи из блока, методами доступа читается следующий блок из файла. Для увеличения скорости обработки это часто делается заранее.
Лекция 4.