Алгоритми та структури даних
Електронний навчальний матеріал для студентів усіх спеціальностей факультету Прикладна інформатика Кубанського державного аграрного університету
Введіть запит для початку пошуку.
Курс розроблено на кафедрі Комп'ютерних технологій та систем Кубанського державного аграрного університету. Авторами є завідувач кафедри, доктор технічних наук, професор Лойко Валерій Іванович та доцент кафедри, кандидат фізико-математичних наук Лаптєв Сергій Володимирович.
Основні цілі сайту
Сайт призначений для максимально ефективного та швидкого доступу до всіх матеріалів курсу "Алгоритми та структури даних", що є на кафедрі комп'ютерних технологій та систем КубДАУ. Основним завданням його створення є підвищення ефективності освоєння дисципліни студентами та всіма бажаючими.
Однозв'язковий список як самостійна структура даних
Необхідно вставити існуючий масив елемент X між 5 і 6 елементами.
Для проведення цієї операції у масиві необхідно змістити “вниз” всі елементи, починаючи з X6 - збільшити їх індекси на одиницю. В результаті вставки отримуємо наступний масив:
Ця процедура може займати дуже багато часу. На противагу цьому, у зв'язаному списку операція вставки полягає у зміні значення 2-х покажчиків та генерації вільного елемента. Причому час, витрачений виконання цієї операції, є постійним і залежить від кількості елементів у списку.
Вставка та вилучення елементів зі списку
При цьому вказівник P повинен вказувати на елемент, після якого необхідно зробити вставку або видалення.
ВставкаInsAfter(P, x)
Нехай необхідно вставити новий елемент з інформаційним полем x після елемента,який вказує робочий покажчик P.
1) Потрібно згенерувати новий елемент.
2) Інформаційному полю цього елемента надати значення X.
3) Вставити отриманий елемент.
Це і є функція InsAfter(Q, X), алгоритм якої нижче
Видалення DelAfter(P)
Нехай необхідно видалити елемент списку, який слідує після елемента, на який вказує робочий покажчик P.
1) Привласнюємо Q значення покажчика на елемент, що видаляється.
2) У змінну X зберігаємо значення інформаційного поля елемента, що видаляється.
3) Змінюємо значення покажчика на елемент, що видаляється, на значення покажчика на наступний елемент і проводимо видалення .
Це і є процедура DelAfter(P, X), нижче записаний алгоритм