пользователей: 21211
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

I семестр:
» прг

Динамические типы данных

Списочные структуры данных обычно понимаются как структуры, где каждый элемент указывает, как правило, на другие элементы структуры. К таким структурам относят списки, однонаправленные и двунаправленные, стеки, очереди, деревья, графы. Для многих типов списков определены понятия текущего, предыдущего, следующего элемента. Типы списков различаются конфигурацией (на какие элементы ссылается каждый конкретный элмент) и набором базисных операций, которые выполняются над списками. К базисным операциям над списками обычно относят следующие операции: 

  • создание пустого списка,
  • проверка списка на пустоту,
  • выборка значения текущего элемента,
  • удаление текущего элемента из списка,
  • замена текущего элемента,
  • выбор нового текущего элемента (предыдущего или последующего),
  • добавление нового элемента в список (после текущего или перед текущим элементом),

Таким образом, каждый элемент списочной структуры должен содержать информационную часть и один или более указателей на другие элементы структуры. В примерах которые будут рассматриваться ниже, списочные структуры будут изменяться, т.е. будут изменяться значения указателей. Поэтому с целью упрощения указатели на списочные структуры будут передаваться в функции как глобальные переменные.

6.1 Очереди и стеки

Ограничивая набор базисных операций над списками можно получить такие структуры, как очереди и стеки. Очередь реализует дисциплину обработки элементов списка "first in - first out"(первый вошел - первый вышел), когда добавление элементов осуществляется в один конец очереди, а удаление - из другого конца. Очередь можно представить следующим образом:

    Element * Left  = NULL;
    Element * Right = NULL;

Указатель Left - начал очереди, т.е указывает на первый элемент, доступный для обработки или удаления. Указатель Right - конец очереди, адрес последного элемента, после которого могут добавляться новые элементы. Нулевые значения указателей соответствуют пустой очереди.Таким образом, при удалении элемента из очереди будет изменяться указатель Left, а при добавлении - указатель Right. Набор базисных операций обычно включает четыре операции: 

  • создание пустой очереди,
  • проверка очереди на пустоту,
  • выборка первого элемента очереди с одновременными удалением его из очереди,
  • занесение нового (последнего) элемента в очередь.

В отличие от очереди стек реализует дисциплину "first in - last out"(первым вошел, последним выщел) , стек имеет единственную точку входа, используемую как для добавления, так и для удаление элементов. Объявить стек можно очень просто

    Element * Top  = NULL; 

Указатель Top - адрес первого элемента списка, доступного для обработки и удаления. Добавление и удаление элементов изменяют значение указателя Тор. Набор базисных операций обычно включает пять операций: 

  • создание пустого стека,
  • проверка стека на пустоту,
  • выборка последнего (верхнего) элемента стека с одновременными удалением его из
  • выборка последнего (верхнего) элемента стека без удаления его из стека,
  • занесение нового (последнего) элемента в стек.

20.08.2015; 01:14
хиты: 40
рейтинг:0
Гуманитарные науки
изобразительные искусства
каллиграфия
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь