СодержаниеСписок с внешней адресациейСписок с внутренней адресациейСписок литературыШтанюк А. А. (Нгту ирит)
 Скачать 289.52 Kb.
|
Алгоритмы и структуры данных Лекция 9. Связанные списки Антон Штанюк (к.т.н, доцент апреля 2021 г. Нижегородский государственный технический университет им. РЕ. Алексеева Институт радиоэлектроники информационных технологий Кафедра Компьютерные технологии в проектировании и производстве Содержание Список с внешней адресацией Список с внутренней адресацией Список литературы Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Понятие связанного списка Списковая структура представляет собой способ организации данных, в котором физический порядок следования элементов в памяти может не совпадать с логическим порядком. Списковые структуры данных основаны наследующем принципе элементы связаны друг с другом при помощи явного использования их адресов. Списки являются линейными СД, поскольку сохраняется определенный порядок следования элементов первый, второй, третий и т.д. Списковая структура может быть реализована как с внешней адресацией (адреса следующих или предыдущих элементах хранятся отдельно от полезных данных) и внутренней адресацией (адреса хранятся рядом с полезными данными). Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список с внешней адресацией Список с внешней адресацией Рассмотрим пример реализации такого списка на примере широко известной файловой системы FAT Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список с внешней адресацией Все пространство памяти делится на блоки фиксированного размера. Каждый блок пронумерован и имеет свой адрес. В отдельной области памяти мы храним массив адресов, повторяющих структуру основных блоков. Если основной блок пустой, то элемент массива хранит 0. Если блок заполняется данными, принадлежащими новому файлу, в элемент массива записывается адрес блока, хранящего продолжение файла. Если все содержимое файла помещается в один блок, тов элементе массива помещается специальная метка 0xFFF (конец файла. В результате, в массиве адресов мы получаем цепочку, пройдя по которой можно считать содержимое файла. Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список с внешней адресацией Несомненным достоинством такой организации является простота, атак- же возможность работы в условиях фрагментации, когда файлы занимают не смежные участки памяти. Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список с внутренней адресацией Список с внутренней адресацией Список с внутренней адресацией состоит из элементов (звеньев, в каждом из которых мы храним полезные данные и адрес следующего (и предыдущего элемента). В соответствии с характером связей, мы можем выделить несколько видов списка. Односвязный список. Двусвязный список. Кольцевой список Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Односвязный список В таком списке каждый элемент хранит адрес следующего элемента Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Двусвязный список В таком списке каждый элемент хранит адрес следующего элемента и адрес предыдущего Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Кольцевой список Кольцевой список может быть и односвязными двусвязным, главное, чтобы он позволял перейти с последнего элемента на первый (и/или спер- вого на последний). Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка Основу программной реализации простого односвязного списка составляет класс, который хранит указатели на головной и хвостовой элементы. Список состоит из звеньев, которые описываются вложенным классом. В каждый элемент мы помещаем экземпляр данных типа T и указатель наследующее звено i n c l u d e < cassert > template < t y p e n a m e T > class LList { st r uc t ITEM { T data ; ITEM * next ; }; pu b li c : Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка () : head ( n u l l p t r ) , tail ( n u l l p t r ) {} LList ( const T &) ; LList ( const LList &) ; LList () ; void a d d T a i l ( const T &) ; void a d d H e a d ( const T &) ; T r m He a d () ; void print () const ; p r i v a t e : LList :: ITEM * c re a t e ( const T &) ; ITEM * head ; ITEM * tail ; }; Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка В качестве программного интерфейса мы используем create() - метод для создания нового звена addTail() - метод добавления нового звена в хвост списка addHead() - метод добавления нового звена в голову списка rmHead() - метод удаления головного элемента rmtail() - метод удаления хвостового элемента. Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка Опишем реализацию стандартных методов класса (конструкторов и де- структора) template < t y p e n a m e T > LList { head = c r ea t e ( data ) ; tail = head ; } template < t y p e n a m e T > LList { while ( head ) rm H ea d () ; } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка Напишем реализацию метода создания нового звена < t y p e n a m e T > t y p e n a m e LList { ITEM * item = new ITEM ; item −>data= data ; item −>next= nullptr ; re t ur n item ; } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка Теперь напишем методы добавления нового элемента в голову и хвост списка < t y p e n a m e T > void LList { if ( tail && head ) { tail −>next = create ( data ); tail = tail −>next ; } else { head = c r ea t e ( data ) ; tail = head ; } } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка < t y p e n a m e T > void LList { if ( tail && head ) { ITEM * temp = c r ea t e ( data ) ; temp −>next = head ; head = temp ; } else { head = c r ea t e ( data ) ; tail = head ; } } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка Теперь приведем в качестве примера метод удаления головного элемента списка < t y p e n a m e T > T LList { if ( head ) { ITEM * temp = head −>next ; T data = head −>data ; de l et e head ; head = temp ; re t ur n data ; } else { re t ur n ( T ) 0; } } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Программная реализация односвязного списка Для того, чтобы можно было распечатывать список, напишем метод print: template < t y p e n a m e T > void LList { ITEM * temp = head ; while ( temp ) { std :: cout < < temp −>data <<"␣"; temp = temp −>next ; } std :: cout < < std :: endl ; } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Пример использования односвязного списка i n c l u d e " tlist . h " int main () { int i ; LList < int > list ; for ( i =1; i <10; i ++) { list . a d d T a i l ( i ) ; list . print () ; } for ( i =10; i <15; i ++) { list . a d d H e a d ( i ) ; list . print () ; } while ( list . r m He a d () ) list . print () ; re t ur n 0; } Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Пример использования односвязного списка 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 11 10 1 2 3 4 5 6 7 8 9 12 11 10 1 2 3 4 5 6 7 8 9 13 12 11 10 1 2 3 4 5 6 7 8 9 14 13 12 11 10 1 2 3 4 5 6 7 8 9 13 12 11 10 1 2 3 4 5 6 7 8 9 12 11 10 1 2 3 4 5 6 7 8 9 11 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9 Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список литературы Список литературы i Кормен Т.,Лейзерсон Ч, Ривест Р. Алгоритмы: построение и анализ МЦНМО, Москва, 2000 Кормен Т, Лейзерсон Ч, Ривест Р, Штайн К. Алгоритмы: построение и анализе изд. — М «Вильямс», 2006 Википедия Алгоритм http://ru.wikipedia.org/wiki/Алгоритм Википедия Список алгоритмов http://ru.wikipedia.org/wiki/Список_алгоритмов Традиция Задача коммивояжёра http://traditio.ru/wiki/Задача Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список литературы ii Википедия NP-полная задача http://ru.wikipedia.org/wiki/NP-полная Серджвик Р. Фундаментальные алгоритмы на С. Части 1-4 Diasoft,2001 Седжвик Р. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск СПб.: ДиаСофтЮП, 2003 Седжвик Р. Фундаментальные алгоритмы на C. Алгоритмы на графах СПб.: ДиаСофтЮП, 2003 Ахо А, Хопкрофт Д, Ульман Д. Структуры данных и алгоритмы. Издательский дом «Вильямс», 2000 Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список литературы Кнут Д. Искусство программирования, том 1. Основные алгоритмы 3-е изд. — М «Вильямс», Кнут Д. Искусство программирования, том 2. Получисленные методы 3-е изд. — М «Вильямс», Кнут Д. Искусство программирования, том 3. Сортировка и поиске изд. — М «Вильямс», Кнут Д. Искусство программирования, том 4, выпуск 3. Генерация всех сочетаний и разбиений М.: «Вильямс», 2007 Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных Список литературы Кнут Д. Искусство программирования, том 4, выпуск 4. Генерация всех деревьев. История комбинаторной генерации М.: «Вильямс», 2007 Штанюк А.А. (НГТУ::ИРИТ) Алгоритмы и структуры данных |