ИГА. Понятие базы данных
 Скачать 0.77 Mb.
|
Циклические списки.В процессе разработки может встретиться задача, где данные необходимо обрабатывать циклично, и конец цикла не зависит от конца данных, а выход из цикла контролируется внешними условиями. Примером может служить список задач, которые должны выполняться по очереди бесконечно. В этом случае может подойти список, у которого нет логического конца, т.к. последний элемент замкнут на первый (т.е. указатель следующего элемента у последнего элемента указывает на первый элемент списка). Список этого рода называется «замкнутый» или «кольцевой». Основой для замкнутого списка может быть как однонаправленный, так и двунаправленный список. На рис. 5 приведён пример логической реализации замкнутого списка на примере двунаправленного. [6]  Процесс добавления или удаления элемента между двумя другими не отличается от описанного процесса списка, на котором основан замкнутый список (однонаправленный или двунаправленный). В строгом смысле нельзя назвать какой-либо элемент замкнутого списка (если он не единственный) первым или последним, поэтому адресуя к замкнутому списку, начальный элемент считается первым (на который установлен указатель начала списка), а последним тот, который указывает на начальный элемент. Исходя из этого, добавление или удаление крайних элементов отличается от базовых списков только необходимостью замыкания последнего элемента на первый в соответствии с рис. 5. Замкнутый список наследует доступные операции, достоинства и недостатки своих базовых списков и легко реализуем на их основе. Стек и его организация.Механизм работы со стеками появился в компьютерной сфере с введением четырёхуровневого стека в процессорах Intel 4004 15 ноября 1971 года (конечно, существовали примеры стеков и до появления процессора). С тех пор стеки стали применяться и в разработке программного обеспечения [1][6]. Механизм работы стека прост – элемент, помещённый в начало стека последним должен быть извлечён первым. Добавление, извлечение и удаление элементов с конца списка не допускается. Этот принцип обозначен аббревиатурой LIFO «last-in first-out» («последним пришёл – первым ушёл»). В литературе так же встречаются отсылки к старым названиям этого списка: магазин, гнездовая память, реверсивная память, push-down list. Применительно к стекам используются следующие названия доступных операций: push (положить) и pop (извлечь). В своей основе стек содержит однонаправленный список [6][7]. На рис. 8 проиллюстрирована работа стека.  Необходимо обозначить все базовые операции, доступные при оперировании со стеком (унаследованные от базового списка и специфические). Операции со стеком [6][16]: Создание нулевого (пустого) стека Проверка на пустоту Проверка на существование первого элемента Извлечение данных первого элемента Удаление первого элемента и взятие следующего как текущего Вставка нового элемента первым Очистка стека У стека существуют следующие ограничения на операции: Добавление и удаление элемента между двумя другими запрещено. Перестановка элементов местами запрещена Реверсирование списка запрещено Сортировка запрещена Стеки очень часто применяются на практике. Самое очевидное их применение – составление списков, например, задач, где на конце стояли бы задачи, выполнение которых можно отложить. В высокоуровневых языках программирования стеки используются для передачи параметров в функции. При написании компиляторов стеки используются, в частности, для проверки синтаксиса, например расстановки скобок. Например, в стек помещается открывающаяся скобка, а если встречается следующий терминальный символ из тех, которые должны закрывать другие терминальные символы, то происходит извлечение из стека, и если это не закрывающаяся скобка – сообщается об ошибке. Так можно проверять сколь угодно глубокую вложенность конструкций. Очереди, организация очередей.Сначала важно дать определение понятию «очередь», т.к. в некоторых разделах математики уже даётся определение этому термину, которое не полностью отражает суть построения этого вида списка. В математике под очередью может пониматься любой список, в который включаются или исключаются элементы. Под это определение так же попадают рассмотренные нами ранее виды списков, но к ним с математической точки зрения должно примениться определение «очереди с различными дисциплинами» [1][3]. В данном случае, добавление или удаление элементов допустимо только с концов списка и по особым правилам, когда первый добавленный элемент удаляется первым. В литературе это правило обозначают аббревиатурой «FIFO», что расшифровывается как «First-in – First Out» (первым пришёл – первым ушёл). Поэтому, в этой работе приводится общее определение очереди: Очередь – список с методом оперирования данными по принципу «первым пришёл – первым ушёл». [8] Конечно, в реальной жизни очереди встречаются повсеместно, поэтому естественно, что в программировании потребность в реализации списков этого типа встречается часто. Наиболее очевидный пример – очередь задач на выполнение программой. Очереди в их каноническом виде реализуются на основе однонаправленного списка с разрешением добавления элементов только одного конца, а удаления только с другого. На рис. 6 приведена расширенная схема работы однонаправленного списка, чтобы проиллюстрировать приведённый принцип.  В литературе встречаются термины, которые обозначают начало и конец очереди: «голова» (head) и «хвост» (tail). Элемент, добавляемый в очередь, добавляется в хвост, в то время как первый элемент (элемент для извлечения) находится в голове очереди. Резюмируя, важно отметить, что хотя очередь представлена по своей структуре однонаправленным списком и наследует его достоинства и недостатки, работать с ней проще в силу ограничений, накладываемых принципом FIFO. Необходимо переоформить операции, которые не могут быть унаследованы от однонаправленного списка:[1][13] Проверка на существование элемента в начале очереди Выборка и извлечение данных элемента в начале очереди Удаление элемента в начале очереди и взятие предыдущего как текущего Вставка нового элемента в конец очереди Дополнительно обозначим ограничения, накладываемые принципами FIFO: Добавление и удаление элемента между двумя другими запрещено. Удаление элемента в конце очереди запрещено Добавление элемента в начало очереди запрещено Перестановка элементов местами запрещена Реверсирование списка запрещено Сортировка запрещена В практическом программировании очередь удобна свой относительной простотой реализации, т.к. за основу можно взять однонаправленный список и запретить использование операций, которые противоречат FIFO. |