Лекции по информатике (984119)
Текст из файла
своеобразные технические приемы вставки и удаления элементов списка: вместо работы с элементами списка производятся манипуляции со значениями элементов (перестановка). Удаление элемента из списка обычно предваряется его поиском, занимаюгцим в среднем Л72 шагов. Цена самого удаления обычно невелика и пропорциональна 0(1). Зеимечание. Вставка и удаление элемента очереди и стека обходится всего лишь в 0(1), что существенно дешевле среднесписочной 0(Х). Это плата за произвольность места, вставки и удаления. 5.6.1 Функциональная спецификация Полная функциональная спецификация двусвязного линейного списка 1 т объектов типа, Х достаточно длинна (72~: В левой части спецификации операции ВСТАВКА находится декартово произведение трех множеств: всевозможных списков, в которые должна быть проведена вставка, всех элементов перед которыми необходимо ее произвести и различных вставляемых элементов.
Помимо тривиальных свойств типа: 1. ПУСТО(СОЗДАТЬ) =- багие 2. ПУС'1'О(ВСТАВКА(1, 1, 1) -- 1а1ае можно отметить следующие: 1. ПРЕДЫДУЩИЙ(СЛЕДУЮЩИЙ(1)) -- 1 2. СЛЕДУЮЩИЙ(ПРЕДЫДУЩИЙ(1)) -- 1 Эти записи следует читать справа налево: каждый элемент является предыдущим к следующему за ним или следующим за предшествующим ему. 3.
1: — СОЗДАТЬ 1: — ВСГАВКА(1, 12, .1а) 1: — ВСТАВКА(1, 1ь 1,) ПЕРВЫЙ(!)-- ПОСЛЕДНИЙ(1) 242 СОЗДАТЬ: ПУСТО: ДЛИНЛ: ПЕРВЫЙ: ПОСЛЕДНИЙ: СЛЕДУЮЩИЙ: ПРЕДЫДУЩИЙ: ВСТАВКА: УДАЛЕНИЕ: УНИЧТОЖИТЬ: 1 т — ~ Ьоо1енн ~'т Ьт-т 7т--Т 1тхт- 7' 1тхт — ~7" 1т х7'х Т вЂ” «1т 1т х 1 — '1т 1т — '~ Это свойство сохранения порядка двух элементов может быть по индукции обобщено на произвольное чис:к> элементов. При этом, в отличие от очереди и стека, картину могут испортить произвольные вставки и удаления элементов. Для кольцевых списков верно также 1.
ПРЕДЫДУЩИЙ(ПЕРВЫЙ© --- ПОСЛЕДНИЙ(1) 2. СЛЕДУЮЩИЙ(ПОСЛЕДНИЙ(1)) ПЕРВЫЙ® 5.6.2 Логическое описание В отличие от очередей и стеков списковые структуры. хотя и не входят в стандартные языки программирования„но хоргнпо реализованы в альтерна,тинных достаточно распространенных языках Лисп [50[ и Пролог [58[. Ьолсе того, в языке Лисп это основная структура,.
Рассмотрим сначала как списки реализованы в Прологе. По определению, пустой список является списком, он обозначается символом [[. Функтор «.» (точка) образует новый список путем добавления нового элемента в начало исходного списка. Так список (1>п 12~ 13~ Г4, 1з) может быть записан на Прологе как .(гм .Рг, (>з, .(>«, (4 [[))))) Однако Пролог не настолько консервативный язык. В нем существует более простой и практичный сгк>соб задания списка явным перечислением: [1п, Г~, Гз, Г ., 1 [ Логическое ог>исание списков на Прологе базируется на встроенном предикате отделения головы списка «[» и реализованных на самом Прологе ггредикатах (программных единицах этого языка), более или менее соответствующих выше>>риведенной функциональной спецификации: проверка членства элемента или подсписка в заданном списке, вычисление длины, конкатенация, геперапия перестановок элементов списка.
Остальное может быть легко дописано на Прологе. Примеры: [Т1, Т2, Т3 [ Та11[» Отделение от списка трех первых элементов. В результате переменные Т1, Тй и ТЗ получают значения первых трех элементов списка, а Тагу становится остатком списка» % Определение длины про вводится рекурсивно 1епфЬ([[., О). 1епфЬ([ [ Та11 [, Х): — 1епдФЬ(Та11, х11), Х 1в Х1 — 1. Ознакомление со списками в „"[испе мы предоставляем читателю [50[. Задача проецирования списков на обычные языки программирования уже давно интересовала программистов: уже в 1963 году Дж.
Вейценбаумом в САСМ был опубликован фортрановский код для В11Р (гугш>>егг1с 11зГ, Ргосеззог), который явился еще одним конструктивным доказательством эквивалентности а>ггоритмических систем. 243 Обсудим возможные варианты реализации списков на Паскале и Си. Поскольку в Паскале и в Си встроенных списков пет, а есть только библиотечные (э1(1з1>а1 в ЯТ1.), их логическое описание тесно переплетено с их физическим представлением. Хотя в простых файловых системах типа 1гАТ файл представляется логическим списком физических блоков, мы не ра,ссматриваем реализацию списков на фа,Илах, поскольку это плохо согласуется с сугубой последовательностностьк> файлов Паскаля. 5.6.3 Физическое представление Пока список не меняется, его удобно отображать на сплошной участок памяти (вектор).
Сплошное представление списков обладает преимуществами для представления фиксированных списков или хронологических, добавление в которых всегда идет в конец: обращение к элементу списка может быть осуп>ествленс> за постоянное время за счет вычисления его адреса. При удалении элементов из сплоппюго списка образуются «дырки» (неиспользуемые 4>рагменты). Нс существует простого способа пометить удаленные элементы, кроме сдвига всех элементов, начи~ая с удаленного, за Л;~'2 п>агов. '1'ак же высока и цена вставки в сплошном представлении. Если мы хотим удел>свить вставку и удаление элемента в список на сплошном представлении, то к>ы можем надстроить над вектором хранения списка управляющий индексный вектор, суррогат ссылочной структуры ~85~, с.
202 206, п. 11.3. Целочисленными значениями компонент вектора можно указывать на следующие элементы списка и регулировать выделение и освобождение элементов массива. Можно предложить различные стратегии дефрагментации и сборки мусора: ведение списка свободных элементов памяти, ленивые либо трудоголические чистки, учет фактического использования ооластей памяти. Как известно, динамические структуры, ценой некоторого расхода машинных ресурсов, освобождают нас от вышеупомянутых недостатков. Точнее, они перекладывают соответствующую работу на плечи среды языка и ядра операционной системы.
Но мы все-таки рассмотрим впоследствии и более совершенную реализацию списка на массиве. 5.6.3.1 Итераторы Для реализации сложных динамических структур данных цепного или сплошного характера принято использовать т. н. итераторы. Перед реализацией списка по его функциональной спецификации обсудим вопрос о навигации по списку. Спецификация утвержает, что всегда непосредственно доступны первый и последний элементы списка. Кроме того, в ней отражена возможность получения предыдущего и следующего элемента относителын> любого данного элемента.
Для удобства организации списка и обеспечения единообразия досту>та к нему определим объекты, обладающие функциями перехода. от данного элемента списка к соседним. Зададим для них отношения равенства и неравенства. Два таких объекта равны тогда и только тогда, когда они указывают на один и тот же элемент списка. Также предоставим возможность чтения и записи элемента списка посредством введенных объектов. '!акис об ьекты принято называть итерпторилт, и, конечно же, для них надо определить соответствующий тип данных.
Итак, итератор предназначен для навигации по списку, чтения и перезаписи элементов списка. Но остается открытым вопрос об инициализации итератора. Сугцествует несколько способов сделать это. Во-первых, итератор в результате обычного присваивания может 244 получить значение другого, ранее созданного итсратора. Во-вторых, это может быть сделано функпиями работы со списком ПЕРВЫЙ и ПОСЛЕДНИЙ. Возвращаемым значением функции ПЕРВЫЙ будет не сам элемент, а итсратор, который на него указывает.
А вот функция ПОСЛЕДНИЙ в этом случае будет выдавать не последний элемент списка, а итератор, указыва>опций на, фиктивный злелгзнлт после конца ешаска терминатор. Введенные таким образом итераторы дан>т более учобный доступ к элементам списка,. Например, для обхода массивов (посещения всех элементов в определенном порядке по одному разу) в Си используется такая идиома: 1п Гог(1 ..
О; > < 1еп; 1-'-+) ,'~'Дейсгпвие с .лгассивоги Эта идиома, работает в любом случае правильно, .даже тогда., когда в массиве вовсе нет элементов. Часто используется другой вариант этой идиомы ("Г тип элемента массива!): Т агг1МАХ]; Т» >; Гог(1 — аьагг10~; 1 1=- вгагг1МАХ~; 1 — +) ,'~ Действие с массивом. Последний вариант хорош еще и тем, что вместо цикла, по счетчику дискретного времени г, используемому для выборки элементов пространства, явно повторяются операции с элементами массива, образующими некоторый его фрагмент. Это позволяет обрабатывать части массива таким же способом, как и целые массивы. Универсальность идиомы позволит записать обход элементов списка в той же манере: ;У Пусть 1 — некоторый, возможно пустой, список 1легагог >, 1аз1 -= Ьав1(Й11; ~~' Эаеменгп после конца Гог(1 — Г1гэ1(ес1); 14о1Ес1па1(1, 1авГ ); Хех1(Й111 ( ,',У Действие со списком Богатство языка Си позволяет «сочинить песню племени девятью и егце шестидесятью спосог>ами» (Р.
Киплинг). В Паскале вьппеприведенные примеры теряк>т свою эстетичность, но сохраняется другое достоинство принятой схемы с концевым маркером: ее простота, универсальность и скорость работы. Простота и универсальность схемы, использующей терминатор, состоит в том, что один и тот же код работает и тогда, когда, в списке есть элементы, и тогда, когда он пуст. Отказ от нее приведет к потребности рассматривать два случая при всяком обходе списка, что ведет как к увсличенин> размера, исходного кода, так и к ошибкам при его написании. Скорость работы проявляется в функциях модификации списка: отказ от рассмотрения 245 двух случаев позволяет сократить код проГраммы и однов1)сменно сэкономить на Оделой инструкции проверки. Правда, та,кой подход усложняет код функций СОЗДА'ГЬ и УНИ- л1ТО?КИТЬ, но поскольку эти функции вызываются гораздо реже функций ВСТАВИТЬ и УДАЛИТЬ, то описанная схема приведет к увеличению быстродействия программы.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
