Линейный список

Дисциплина «Алгоритмы и структуры данных» Лекция № 6 Линейный список Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Абстрактный тип данных «Список» Линейный список (с математической точки зрения) – это множество, состоящее из n > 0 узлов Х[1], Х[2], .... Х[n], структурные свойства которого по сути ограничиваются лишь линейным (в математическом смысле), т.е. одномерным относительным положением узлов, определяемыми условиями, что • если n > 0, то Х [1] является первым узлом; • если 1 < k < n, то k-му узлу Х [k] предшествует Х [k - 1] и за ним следует Х[k + 1]; • Х [n] является последним узлом. Абстрактный тип данных «Список» Линейный список (с математической точки зрения) – это множество, состоящее из n > 0 узлов Х[1], Х[2], .... Х[n], структурные свойства которого по сути ограничиваются лишь линейным (в математическом смысле), т.е. одномерным относительным положением узлов, определяемыми условиями, что • если n > 0, то Х [1] является первым узлом; • если 1 < k < n, то k-му узлу Х [k] предшествует Х [k - 1] и за ним следует Х[k + 1]; • Х [n] является последним узлом. Реализация АТД «Линейный список» Последовательность элементов (список) в памяти ЭВМ можно организовать двумя способами, используя либо последовательное, либо связанное распределение элементов. • При последовательном распределении элементы располагаются друг за другом вплотную (без пропусков), причем порядок физического следования (расположения) в памяти соответствует порядку обхода или порядковому номеру элемента в последовательности. • Если же реализовать механизм, обеспечивающий последовательный обход элементов в требуемом порядке, но расположенных физически в областях памяти произвольно, причем необязательно друг за другом, то тогда мы имеем связанное распределение. Такое название определено наличием связи между элементами, определяющей порядок следования. • По числу и особенностям связей между элементами различают однонаправленные и двунаправленные списки, а также кольцевые списки. • Заметим, что связанное распределение можно реализовать, используя как динамические структуры-списки, так и массивы. Реализация АТД «Линейный список» Последовательность элементов (список) в памяти ЭВМ можно организовать двумя способами, используя либо последовательное, либо связанное распределение элементов. • При последовательном распределении элементы располагаются друг за другом вплотную (без пропусков), причем порядок физического следования (расположения) в памяти соответствует порядку обхода или порядковому номеру элемента в последовательности. • Если же реализовать механизм, обеспечивающий последовательный обход элементов в требуемом порядке, но расположенных физически в областях памяти произвольно, причем необязательно друг за другом, то тогда мы имеем связанное распределение. Такое название определено наличием связи между элементами, определяющей порядок следования. • По числу и особенностям связей между элементами различают однонаправленные и двунаправленные списки, а также кольцевые списки. • Заметим, что связанное распределение можно реализовать, используя как динамические структуры-списки, так и массивы. Реализация АТД «Линейный список» Последовательность элементов (список) в памяти ЭВМ можно организовать двумя способами, используя либо последовательное, либо связанное распределение элементов. • При последовательном распределении элементы располагаются друг за другом вплотную (без пропусков), причем порядок физического следования (расположения) в памяти соответствует порядку обхода или порядковому номеру элемента в последовательности. • Если же реализовать механизм, обеспечивающий последовательный обход элементов в требуемом порядке, но расположенных физически в областях памяти произвольно, причем необязательно друг за другом, то тогда мы имеем связанное распределение. Такое название определено наличием связи между элементами, определяющей порядок следования. • По числу и особенностям связей между элементами различают однонаправленные и двунаправленные списки, а также кольцевые списки. • Заметим, что связанное распределение можно реализовать, используя как динамические структуры-списки, так и массивы. Реализация АТД «Линейный список» Последовательность элементов (список) в памяти ЭВМ можно организовать двумя способами, используя либо последовательное, либо связанное распределение элементов. • При последовательном распределении элементы располагаются друг за другом вплотную (без пропусков), причем порядок физического следования (расположения) в памяти соответствует порядку обхода или порядковому номеру элемента в последовательности. • Если же реализовать механизм, обеспечивающий последовательный обход элементов в требуемом порядке, но расположенных физически в областях памяти произвольно, причем необязательно друг за другом, то тогда мы имеем связанное распределение. Такое название определено наличием связи между элементами, определяющей порядок следования. • По числу и особенностям связей между элементами различают однонаправленные и двунаправленные списки, а также кольцевые списки. • Заметим, что связанное распределение можно реализовать, используя как динамические структуры-списки, так и массивы. Последовательное и связанное распределения Операция Последовательное распределение Связанное распределение Доступ к произвольному элементу (изменение) O(1) O(N) Добавление O(N) O(1) Удаление элемента из списка O(N) O(1) Объединение (разъединение) двух списков O(N+M) min{O(N), O(M)} O(1) ? Аналогично «малому» Использование «огромного» числа элемента Способы организации списков • — линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Организуется по принципу “Last In – First Out” (LIFO) • — линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце. Организуется по принципу “First In – First Out” (FIFO) • — линейный список, в котором все включения и исключения (и обычно всякий доступ) реализован на обоих концах списка. Является обобщением понятий стека и очереди. Способы организации списков • Стек (stack)— линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Организуется по принципу “Last In – First Out” (LIFO) • Очередь (queue) — линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце. Организуется по принципу “First In – First Out” (FIFO) • Дек (deque) – линейный список, в котором все включения и исключения (и обычно всякий доступ) реализован на обоих концах списка. Является обобщением понятий стека и очереди. Способы организации списков • Стек (stack)— линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Организуется по принципу “Last In – First Out” (LIFO) Аналогия с переключением железнодорожных путей, предложенная Э. Дейкстрой, помогает понять механизм стека. • стека и очереди. Способы организации списков • Стек (stack)— линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Организуется по принципу “Last In – First Out” (LIFO) Статическая реализация • стека и очереди. Стек запись i чтение i … 1 дно … i+1 вершина чтение вершина … … запись Динамическая реализация дно Указатель на вершину стека чтение запись … вершина … null дно Способы организации списков • Очередь (queue) — линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце. Организуется по принципу “First In – First Out” (FIFO) Статическая реализация Очередь … 1 n выход вход извлечение чтение начало Динамическая реализация … конец добавление запись Указатель на начало очереди Указатель на конец очереди извлечение … null начало … null конец добавление Способы организации списков • Дек (deque) – линейный список, в котором все включения и исключения (и обычно всякий доступ) реализован на обоих концах списка. Является обобщением понятий стека и очереди. Способы организации списков • Дек (deque) – линейный список, в котором все включения и исключения (и обычно всякий доступ) реализован на обоих концах списка. Дек Является обобщением понятий стека и очереди. извлечение добавление начало … конец извлечение добавление Динамическая реализация Указатель на начало дека Указатель на конец дека извлечение … nil добавление начало … nil извлечение конец добавление Способы организации списков • Стек (stack)— линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Организуется по принципу “Last In – First Out” (LIFO) • Очередь (queue) — линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце. Организуется по принципу “First In – First Out” (FIFO) • Дек (queue) – линейный список, в котором все включения и исключения (и обычно всякий доступ) реализован на обоих концах списка. Является обобщением понятий стека и очереди. АТД «Линейный список» МЕТОДЫ АТД «Линейный список» • получить значение первого элемента (на выходе) например: x=value(), x= top() • добавить элемент (на вход) например: add(x), push(x) • удалить («выпихнуть») элемент из списка (на выходе) например: del(), pop() • проверить – список пуст например: isEmpty() • обнулить (проинициализировать) список например: конструктор_класса(), init() «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные Нелинейные ? «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные Время поиска порядка O(N) Нелинейные ? «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные Пример? Нелинейные ? «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Под термином библиотека стандартных шаблонов (STL, Standard Template Library) понимают набор интерфейсов и компонентов, первоначально разработанных Александром Степановым, Менг Ли и другими сотрудниками AT&T Bell Laboratories и Hewlett-Packard Research Laboratories в начале 90-х годов (хотя и позже ещё весьма многие приложили руку к тому, что стало на сегодня стандартным компонентом C++). Линейные На примере STL: - vector - list - stack - queue - deque - set, multiset Нелинейные ? Далее библиотека STL перешла в собственность компании SGI, а также была включена как компонент в набор библиотек Boost. И наконец библиотека STL вошла в стандарты C++ 1998 и 2003 годов (ISO/IEC 14882:1998 и ISO/IEC 14882:2003) и с тех пор считается одной из составных частей стандартной библиотек C++ «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные последовательные контейнеры Нелинейные «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные Нелинейные последовательные контейнеры Время поиска менее O(N) Пример? «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные последовательные контейнеры Нелинейные • Списки со многими связями (лес, мультисписки, «слоёные» списки и т.п.) • Деревья – O(N) «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные последовательные контейнеры Нелинейные Ассоциативные На примере STL: - map - multimap «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные последовательные контейнеры Нелинейные Ассоциативные «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента) делятся на … Линейные последовательные контейнеры Нелинейные Ассоциативные «Структурность» Структуры по способу организации данных (в контексте времени поиска элемента – с целью доступа) делятся на … Линейные Нелинейные Ассоциативные последовательные контейнеры ассоциативные контейнеры Хеш-таблицы O(N) O(log(N)) O(const) Спасибо за внимание!