Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Лекція №3

Зв’язний список

Подекуди виникає необхідність у доступі до елементів структури, які не є останніми. Стек і черга не дають такої можливості: щоб дістатися до елементів цих структур, які розміщуються у середині, необхідно вилучити елементи, які їм передують.

Структура даних, яка надає можливість доступу до елементів, що розміщені не на її межах, називається зв’язним списком.

Розглянемо принцип виконання основних операцій над її елементами.

Зв’язний список є динамічною структурою, що дозволяє робити запис нових елементів у будь-яке місце вже існуючого списку і так само виконувати у будь-якому місці читання елементів.

Насправді у зв’язному списку відбуватиметься вилучення цих елементів зі списку, але за традицією надалі продовжуватимемо називати цю операцію читанням.

Читання елемента списку можна організувати шляхом зсуву вліво решти елементів, що розташовані за тим, що читається. Однак, ці дії характеризуються певним часом виконання. Ефективнішим буде шлях «не бачення» цього елемента у списку. Тобто, якщо після (k-1)-го елемента у списку йшов k-ий, а після нього ― (k+1)-ий, то після вилучення k-ого елемента за (k-1)-им буде слідувати (k+1)-ий. Схематично це можна зобразити таким чином:

 
 


(k-1) елемент   k елемент   (k+1) елемент

Запис нового елемента списку у вказане місце, наприклад після k-ого елемента, буде викликати зсув всіх елементів, що знаходяться після k-ого, на одну позицію вправо. Зрозуміло, що і такий підхід не є оптимальним. Простіше було б записати його в кінець списку, але змінити для цього послідовність перегляду елементів списку: після k-ого елемента переходити до нового елемента, записаного в кінець, а потім до (k+1)-ого:

 

 

k елемент   (k+1) елемент   ... n елемент   new елемент

 

Структуру «список» можна реалізувати на одновимірному масиві. Кожний елемент списку буде займати два сусідніх елементи масиву, тобто таку ланку: перший ― сам елемент списку, другий ― індекс масиву, що вказує на місце знаходження наступного елемента списку:

k-ий елемент списку індекс елемента масиву, який містить наступний елемент списку
аі аі+1

Однак, ефективнішим для реалізації списку є використання покажчиків, тобто розміщення списку в динамічній пам’яті, а не на статичному масиві, оскільки при вставленні усередину масиву або ж вилученні з нього елементів необхідно переміщати на сусідні місця ті елементи,що залишилися. Схематично структуру списку можна представити так:

Елемент 1
 

 


Читайте також:

  1. Вид заняття: лекція
  2. Вид заняття: лекція
  3. Вид заняття: лекція
  4. Вид заняття: лекція
  5. Вид заняття: лекція
  6. Вступна лекція
  7. Вступна лекція 1. Методологічні аспекти технічного регулювання у
  8. Клітинна селекція рослин.
  9. Колекція фонограм з голосами осіб, які анонімно повідомляли про загрозу вибуху
  10. ЛЕКЦІЯ (4): Мануфактурний період світової економіки
  11. Лекція - Геополітика держави на міжнародній арені
  12. Лекція 02.04.2013




Переглядів: 515

<== попередня сторінка | наступна сторінка ==>
Відповідальність газопостачального та газорозподільного підприємства | Зв’язним списком називається структура даних, кожний елемент якої зв’язаний з наступним (або попереднім, або з обома сусідніми) елементом за допомогою покажчиків.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.117 сек.