Міністерство освіти і науки Російської Федерації
Федеральне державне бюджетне освітня установа
Вищої професійної освіти
"Комсомольський-на-Амурі державний технічний університет"
Факультет комп'ютерних технологій
Кафедра МОП ЕОМ
З дисципліни: "Функціональне і логічне програмування"
Студент групи 0ВТ3к-1
Коновалова. К.А.
Викладач Абарнікова Є.Б.
Завдання 1
Тема: списки і бінарні дерева.
Мета: вивчити основні операції роботи зі списком.
Завдання: написати програму реалізовує:
) видалення елемента зі списку перед вказаним елементом.
) сортування списку за зростанням методом швидкого сортування.
Для всіх операцій здійснити контроль введення (елементом списку можуть бути як числа, так і символи).
Теоретичне опис
Список - це бінарна структура, що є послідовність, що складається з довільного числа елементів. Списком може бути порожній список, який не містить жодного елемента, або структура, що має голову і хвіст. Голова - перший елемент списку. Хвіст - частина, що залишилася списку без першого елемента.
Список - окремий випадок бінарного дерева, тому йому притаманні всі властивості і можливі операції, які можна робити над множинами.
Списком називається набір змінних одного типу, доступ до яких здійснюють функції додавання, видалення і, можливо, пошуку елемента. Ця структура даних складається з елементів масиву або послідовності структур і має доступ до елементів через:
"голову" - перший елемент списку;
"хвіст" - елемент або послідовність елементів наступних за "головою" списку.
Опис алгоритму швидкого сортування.
Виберемо випадковим чином якийсь елемент х і переглянемо список, рухаючись зліва направо, поки не знайдемо а i більший x, а потім справа наліво, поки не знайдемо а i менший х. Поміняємо їх місцями і продовжимо процес перегляду з обміном, поки перегляди не зустрінуться десь в середині списку.
В результаті спи...
