Список
Если у веревки есть один конец, значит, у нее должен быть и другой.
Закон Микша
(Прикладная Мерфология)
В общем случае под списком понимается линейно упорядоченная последовательность элементов данных, каждый из которых представляет собой совокупность одних и тех же полей. Упорядоченность элементов данных может быть двоякой:
- элементы списка располагаются последовательно как в структуре представления, так и в структуре хранения – список такого типа называется последовательным;
- порядок следования элементов определяется с помощью специальных указателей, которые расположены в самих элементах и определяют их соседей справа и/или слева – подобные списки называются связными.
Последовательные списки
Если количество элементов в списке постоянно, то в зависимости от их типа список вырождается в вектор, массив, структуру или таблицу. Отличие списка от этих структур данных – в длине. Для списков она является переменной. Поэтому программист, разбираясь с самими списками, должен уделить внимание тому, каким образом ему следует выделять память для хранения списка. Обычно языки высокого уровня имеют соответствующие средства в отличие от языка ассемблера. При написании программы на ассемблере программист должен уметь напрямую обратиться к операционной системе для решения проблемы динамического управления памятью.
В примерах мы будем использовать соответствующие функции API Win32 как более современные, хотя для общего случая это не принципиально. В MS DOS имеются аналогичные функции (с точки зрения цели использования) – это функции 48h, 49h, 4ah прерывания 21h. Вопрос динамического управления памятью в силу своей важности в контексте настоящего рассмотрения требует особого внимания.
Отличие последовательных списков от связных состоит в том, что добавление и удаление элементов возможно только по концам структуры. В зависимости от алгоритма изменения различают такие виды последовательных списков, как стеки, очереди и деки. Эти виды списков обычно дополняются служебным дескриптором, который может содержать указатели на начало и конец области памяти, выделенной для списка, указатель на текущий элемент.
Зачем нужен, к примеру, стек? Необходимость использования своего стека в программе вполне вероятна, хотя бы исходя из того, что элементы, для хранения которых он создается, могут иметь размер, отличный от 2/4 байта.
Важно понимать, что внутренняя структура элемента практически не зависит от типа последовательного списка. Списки отличает набор операций, которые производятся над ними. Поэтому рассмотрим их отдельно для каждого типа последовательного списка.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Стек
Стек – последовательный список, в котором все включения и исключения элементов производятся на одном его конце – по принципу LIFO (Last In First Out – последним – пришел первым ушел). Для стека определены следующие операции:
- создание стека;
- включение элемента в стек;
- исключение элемента из стека;
- очистка стека;
- проверка объема стека (числа элементов в стеке);
- удаление стека.
Создание стека должно сопровождаться инициализацией специального дескриптора стека, который может содержать следующие поля: имя стека, адреса нижней и верхней границ стека, указатель на вершину стека.
Иллюстрацию организации и работы стека произведем на примере задачи, анализирующей правильность согласования скобок в некотором тексте. Причем условимся, что скобки могут быть нескольких видов: (), {}, [ ], <>. Программа реализована в виде приложения Win32 с использованием функций API Win32 для работы с кучей (из нее выделяется память для стека).