МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||||||||||||||||||||||||||
Лекція №3Зв’язний список Подекуди виникає необхідність у доступі до елементів структури, які не є останніми. Стек і черга не дають такої можливості: щоб дістатися до елементів цих структур, які розміщуються у середині, необхідно вилучити елементи, які їм передують. Структура даних, яка надає можливість доступу до елементів, що розміщені не на її межах, називається зв’язним списком. Розглянемо принцип виконання основних операцій над її елементами. Зв’язний список є динамічною структурою, що дозволяє робити запис нових елементів у будь-яке місце вже існуючого списку і так само виконувати у будь-якому місці читання елементів. Насправді у зв’язному списку відбуватиметься вилучення цих елементів зі списку, але за традицією надалі продовжуватимемо називати цю операцію читанням. Читання елемента списку можна організувати шляхом зсуву вліво решти елементів, що розташовані за тим, що читається. Однак, ці дії характеризуються певним часом виконання. Ефективнішим буде шлях «не бачення» цього елемента у списку. Тобто, якщо після (k-1)-го елемента у списку йшов k-ий, а після нього ― (k+1)-ий, то після вилучення k-ого елемента за (k-1)-им буде слідувати (k+1)-ий. Схематично це можна зобразити таким чином:
Запис нового елемента списку у вказане місце, наприклад після k-ого елемента, буде викликати зсув всіх елементів, що знаходяться після k-ого, на одну позицію вправо. Зрозуміло, що і такий підхід не є оптимальним. Простіше було б записати його в кінець списку, але змінити для цього послідовність перегляду елементів списку: після k-ого елемента переходити до нового елемента, записаного в кінець, а потім до (k+1)-ого:
Структуру «список» можна реалізувати на одновимірному масиві. Кожний елемент списку буде займати два сусідніх елементи масиву, тобто таку ланку: перший ― сам елемент списку, другий ― індекс масиву, що вказує на місце знаходження наступного елемента списку:
Однак, ефективнішим для реалізації списку є використання покажчиків, тобто розміщення списку в динамічній пам’яті, а не на статичному масиві, оскільки при вставленні усередину масиву або ж вилученні з нього елементів необхідно переміщати на сусідні місця ті елементи,що залишилися. Схематично структуру списку можна представити так:
Читайте також:
|
||||||||||||||||||||||||||||||||
|