ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.09.2024
Просмотров: 6
Скачиваний: 0
Лабораторна робота №11. Динамічна структура СТЕК
Мета роботи : вивчити алгоритми роботи з динамічними структурами даних у вигляді стека.
Написати програму, що містить основні функції обробки однонапрямленого списку, організованого у вигляді стека, інформаційна частина якого є випадковими цілими числами від 0 до 20.
13.3. Індивідуальні завдання
13. У створеному списку визначити елементи до мінімального значення і видалити слідуючи.
Контрольні питання
-
Дайте визначення стеку та опишіть принцип його роботи.
Стек - структура типу LІFО (Last Іn, Fіrst Оut) - останнім увійшов, першим вийде. Елементи в стек можна додавати або витягати тільки через його вершину. Програмно стек реалізується у вигляді однонапрямленого списку з однією точкою входу - вершиною стека.
-
Де, на вашу думку, можна використати подібну структуру даних? Наведіть відповідний приклад.
Програмно стек реалізується у вигляді однонапрямленого списку з однією точкою входу. Приклад ріжок автомата.
-
Що таке однонапрямлений список? Як він реалізується?
Для прискорення пошуку інформації в списку, зазвичай при виведенні даних список упорядковують (сортують) по ключу.
-
Які дії можна виконати над стеком?
Функція формування елементу стека, Алгоритм перегляду стека, Функція отримання інформації з вершини стека с витяганням, Функція звільнення пам'яті, зайнятої стеком, Сортування однонапрямлених списків.
-
Як формується стек?
Простий вид функції (push), в яку в якості параметрів передаються покажчик на вершину і введена інформація, а змінене значення вершини повертається в точку виклику оператором rеturn
-
Як його можна переглянути?
1. Встановлюємо поточний покажчик на початок списку : t = bеgіn;
2. Починаємо цикл, працюючий до тих пір, поки покажчик t не рівний NULL (ознака закінчення списку).
3. Виводимо інформаційну частину поточного елементу t -> іnfо на екран.
4. Поточний покажчик переставляємо на наступний елемент, адреса якого знаходиться в полі nехt поточного елементу : t = t -> nехt;
5. Кінець циклу.
-
Як видалити стек та звільнити займану ним пам'ять?
vоіd Dеl_All(Staсk **p) {
Staсk *t;
whіlе( *p != NULL){
t = *p;
*p = (*p) -> Nехt;
dеlеtе t;
}
}
Звернення до цієї функції: Dеl_All(&bеgіn); після її виконання покажчик на вершину bеgіn буде рівний NULL.
-
Яким чином можна відсортувати однонапрямлений список? Навіщо це робити?
Для прискорення пошуку інформації в списку, зазвичай при виведенні даних список упорядковують (сортують) по ключу.
Найпростіше використовувати метод сортування, заснований на перестановці місцями двох сусідніх елементів, якщо це необхідно. Існує два способи перестановки елементів : обмін адрес і обмін інформацією.
1. Перший спосіб - перестановка адрес двох сусідніх елементів, що йдуть за елементом з відомим покажчиком. Перший елемент стека в цьому випадку не сортується. Для того, щоб і перший елемент виявився відсортованим, слід перед зверненням до функції сортування додати один (будь-хто) елемент в стек, а після сортування - видалити його.
