Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних СПИСОК
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2010
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Програмування Частина III Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних СПИСОК
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 5
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2010
Методичні вказівки до лабораторної роботи "Структура даних СПИСОК" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 16.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних списка. Набуття практичних навичок побудови списка, дослідження динаміки його вмісту та використання списків для розв'язання прикладних задач.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
Приклад 1: Динаміка вмісту списку
Порожній список
Реалізація списку на базі масиву
Схематичне зображення списків
0
0
Space[7]
List
0
Free
1
0
7
Space[6]
0
6
Space[5]
0
5
Space[4]
0
4
Space[3]
0
3
Space[2]
0
2
Space[1]
0
0
Space[0]
. data next
List
.
NULL
Free
0
(
0
(
0
(
0
(
0
(
0
(
0
NULL
data next
Виконаємо наступні операціїї над списком:
// push(elem) – додає elem в кінець списку
// pop(pos)- вилучає елемент, що знаходиться в позиції pos
push(106);
push (245);
push (317);
push (472);
pop (4);
push (808);
pop (3);
Результат виконання операцій
Реалізація списку на базі масиву
Схематичне зображення списків
List
1
Free
6
0
4
Space[7]
0
7
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
5
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
106
(
245
(
808
NULL
data next
Free
0
(
0
(
472
(
317
NULL
data next
Виконаємо операцію insert (pos , elem), яка вставляє elem в позицію pos:
insert (5 , 613 )
Було
Стало
List
1
Free
6
0
4
Space[7]
0
7
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
5
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
1
Free
7
0
4
Space[7]
613
5
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
6
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
106
(
245
(
808
NULL
data next
Free
0
(
0
(
472
(
317
NULL
data next
List
106
(
245
(
613
(
808
NULL
data next
Free
0
(
472
(
317
NULL
data next
Виконаємо операцію pop (pos), яка вилучає елемент, що знаходиться в позиції pos
pop (List )
Було
Стало
List
1
Free
7
0
4
Space[7]
613
5
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
6
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
2
Free
7
0
4
Space[7]
613
5
Space[6]
808
0
Space[5]
472
3
Space[4]
317
1
Space[3]
245
6
Space[2]
106
0
Space[1]
0
0
Space[0]
. data next
List
106
(
245
(
613
(
808
NULL
data next
Free
0
(
472
(
317
NULL
data next
List
245
(
613
(
808
NULL
data next
Free
0
(
472
(
317
(
106
NULL
data next
Розглянемо програмну реалізацію деяких основних операцій роботи з лінійним зв'язаним однонаправленим списком, представленим за допомогою вказівників:
// Структура списка
struct node
{ int data;
struct node *next;
};
typedef struct node *list;
// Додавання нового елемента в кінець списку
void push(list *head_ptr, int elem)
{
node *new_ptr;
new_ptr = new node;
new_ptr->data = elem;
new_ptr->next = NULL;
if (empty(*head_ptr))
*head_ptr = new_ptr;
else
find_last(*head_ptr)->next = new_ptr;
return ;
}
// Вставка нового елемента після заданого елемента списку
void PutAfter(list *node_prt, int elem)
{
list new_ptr = NULL;
new_ptr = new node;
new_ptr->data = elem;
new_ptr->next = (*node_prt)->next;
(*node_prt)->next = new_ptr;
return ;
}
// Пошук вузла із заданим значенням в списку
list Find(list head, infotype search_data)
{
while ((head) && (head->data != search_data)) head = head->next;
return head;
}
// Пошук вузла в списку, що знаходиться перед заданим вузлом
list find_before(list head, list node)
{
while ((head->next != node) && head) head = head->next;
return head;
}
// Пошук вузла в списку що знаходиться після заданого вузла
list find_after(list node)
{
return node->next;
}
// Пошук останнього вузла списку
list find_last(list head)
{
if (head) while (head->next) head = head->next;
return head;
}
// Вилучення заданого вузла зі списку
void Delete(list *head_ptr, list *node_ptr)
{
list tmp , save_ptr = *node_ptr;
assert(*head_ptr);
assert(*node_ptr);
if (*node_ptr == *head_ptr)
*head_ptr = (*head_ptr)->next;
else
if (!((*node_ptr)->next))
{
tmp = FindBefore(*head_ptr,*node_ptr);
tmp->next = NULL;
}
else
{
tmp = (*node_ptr)->next;
(*node_ptr)->data = tmp->data;
(*node_ptr)->next = tmp->next;
save_ptr = tmp;
};
free(save_ptr);
return ;
}
// Роздрук списку
void print_ list(list head)
{
while (head)
{
cout<<head->data;
head = head->next;
}
cout<<endl;
return;
}
В бібліотеці стандартних шаблонів STL існує клас list, що підтримує двунаправлений лінійний список. В класі list визначений конструктор list, що створює порожній список. Нижче в таблиці наведені основні функції-члени класу list:
Функція-член
Опис
begin ()
Повертає двонаправлений ітератор для першого елемента
end ()
Повертає двонаправлений ітератор для позиції за останнім елементом
insert (pos , elem)
Вставляє копію elem в позицію ітератора pos і повертає позицію нового елемента
push_back (elem)
Додає копію elem в кінець списку
push_front (elem)
Вставляє копію elem в початок списку
pop_back (elem)
Вилучає останній елемент списку (не повертаючи його)
pop_front (elem)
Вилучає перший елемент списку (не повертаючи його)
remove (val)
Вилучає всі елементи списку зі значенням val
erase (pos)
Вилучає елемент в позиції ітератора pos і повертає позицію наступного елемента списку
clear ()
Вилучає всі елементи списку (контейнер залишається порожнім)
Приклад використання класу list з бібліотеки стандартних шаблонів STL:
// В цій програмі створюється список символів. Спочатку створюється порожній список.
// Після цього в нього поміщаються десять символів (буквы от А до J включно).
// Ця операція виконується за допомогою функції push_back(), яка додає кожне наступне значення
// в кінець створенного списку.
// Далі на екран виводиться розмір списку.
// Після цього організується вивід на екран вмісту списку
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> lst;
int i;
for(i=0; i<10; i++) lst.push_back(’A’ + i);
cout << "Рoзмiр = " << lst.size () << endl;
list<char>::iterator p = lst.begin();
cout << "Вміст: ";
while (p != lst.end() ) {
cout << *p;
p++;
}
return 0;
}
3. ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
4.1. Вибір варіанта індивідуального завдання
№ варіанта = [(місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера)] % 30 + 1
4.2. Варіанти завдань
Змоделювати лінійний зв'язаний одно- або двонаправлений список, реалізований за допомогою вказівників (вибір здійснити виходячи з умови задачі). Написати основні операції для роботи зі списком і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>=10) цілих чисел (числа вводити з клавіатури). Всі додатні і нульові числа послідовно вставляти у відповідне місце списку так, щоб список весь час залишався відсортованим по зростанню (точніше по неспаданню) значень його елементів. Кожне від'ємне число має вилучати зі списку всі елементи, значення яких дорівнюють модулю цього від'ємного числа. Якщо в списку таких елементів не буде знайдено, то видавати відповідне повідомлення про відсутність цього числа у списку. Виводити на екран динаміку вмісту списку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу всіх основних операцій.
1. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності продублювати всі елементи списку, що містять парні числа (продублювати , тобто зразу після знайденого елемента створити ще один з таким самим значенням).
2. Побудувати два списки even_list i odd_list, що містять відповідно парні і непарні числа вхідної послідовності, показуючи динаміку їх вмістів. Після обробки всієї заданої вхідної послідовності створити список all_list , шляхом з'єднання кінця списку even_list з початком списку odd_list .
3. Задати дві вхідні послідовності чисел і за допомогою їх побудувати два списки, показуючи динаміку їх вмістів. Після обробки обох послідовностей створити новий список, який буде мiстити спiльнi елементи обох побудованих списків.
4. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності вилучити зі списку кожний другий елемент.
5. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності розбити побудований список на два рівних (якщо кількість елементів списку парна) або майже рівних (якщо кількість елементів списку непарна) по довжині списка.
6. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності інвертувати побудований список, тобто зробити перший елемент останнім, другий передостаннім і т.д.
7. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності створити новий список, який буде мiстити тільки ті елементи побудованого списку, значення яких повторюються.
8. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи перший елемент списку містить значення 0. Якщо це так, то додати ще один елемент зі наченням 0 в кінець списку, якщо ні – то зі списку вилучити всі елементи зі наченням 0
9. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності поміняти місцями значення кожних двух сусідніх елементів списку, тобто значення першого елемента поміняти зі значенням другого, третього з четвертим і т.д.
10. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності визначити, чи є у списку хоча б одне число, що містить тільки однакові цифри.
11. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи є в списку три елемента з однаковими значеннями, що йдуть підряд.
12. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності знайти медіану списку.
Примітка: нехай - послідовні значення елементів списку, причому . Якщо n – парне число (тобто n=2*m), то медіана рівна . Якщо n – непарне число (тобто n=2*m+1), то медіана рівна .
13. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи список містить парну кількість елементів, чи ні.
14. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи є в списку елементи з однаковими значеннями, чи ні.
15. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи буде список “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.).
16. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності визначити три різних найбільших значення, що містять елементи списку.
17. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності в отриманому списку продублювати (тобто створити ще один такий самий) кожний елемент значення якого містить цифру 9
18. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перетворити отриманий список так, щоб він не містив елементів з однаковими значеннями.
19. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи значення всіх елементів списку будуть непарними числами, чи ні.
20. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності знайти середнє арифметичне всіх парних значень елементів списку.
21. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності визначити, чи є в списку хоча б одне число менше за 5, чи немає.
22. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності знайти добуток парних значень елементів списку.
23. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності знайти найбільш довгу послідовність однакових елементів списку, що йдуть підряд.
24. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності визначити, чи кількість всіх парних чисел списку буде меншою за кількість непарних, чи ні.
25. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності збільшити в три раза значення кожного елемента списку.
26 Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки послідовності замінити всі парні числа у списку на 1, а непарні – на 0.
27. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності вилучити зі списку всі елементи, що містять непарні числа.
28. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності визначити довжину побудованого списку.
29. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності вилучити зі списку все елементи значення яких містять хоча б одну цифру 1.
30. Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності знайти кількість елементів списку зі значеннями більшими за 7.
5. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.
II. В звіті мають бути відображені наступні пункти:
1. Мета роботи
2. Постановка задачі
3. Алгоритм розв’язання задачі
4. Динаміка вмісту списку
4.1. Послідовність 10 цілих (додатніх, від'ємних, нульових, парних і непарних) чисел
4.2. Схематичне зображення списку після обробки всієї послідовності
4.3. Реалізація цього списку на базі масиву розмірністю 15
4.4. Вибрати один з варіантів у відповідності до завдання:
- схематичне зображення списку та реалізація списку на базі масиву після перетворення;
- перевірка умови (показати всі можливі варіанти);
- знаходження суми, або добутку, або кількості або довжини і т.д.;
- інше.
5. Результати виконання програми
Висновки
Додатки
IIІ. Змістовне наповнення пунктів:
Постановка задачі має містити повне завдання, тобто спільне завдання для всіх варіантів і індивідуальне завдання для свого вибраного варіанту.
В пункті алгоритм розв’язання задачі надається словесний опис основних прийомів, що використовуються для знаходження алгоритму та написання програми.
В пункті динаміка вмісту списку намалювати схематичне зображення списку та реалізацію цього списку на базі масиву до і після перетворень або для різних варіантів обчислень.
В пункті результати виконання програми показуються роздруковані копії екранів з результатами, які відображають всі зміни, що відбуваються у списку та містять всю необхідну інформацію в такому вигляді, щоб для перевірки правильності виконання програми не виникало необхідності додатково переглядати тексти програм.
В додатках розміщуються тексти програм з коментарями. Кожний додаток підписується, яка саме інформація в ньому надається.
6. КОНТРОЛЬНІ ЗАВДАННЯ
1. Задано схематичне зображення лінійного однонаправленого зв’язаного списку SP:
SP
1
1
3
3
0
data next
Намалюйте графічне зображення цього списку, представленого на базі масиву mas[7].
2. Задано однонаправлений лінійний зв’язаний список SPK, представлений за базі масиву Space[6]:
SPK
2
Free
3
44
0
Space[5]
33
1
Space[4]
22
4
Space[3]
11
5
Space[2]
10
0
Space[1]
0
0
Space[0]
data next
Перемалюйте зображення масиву Space та змінних SPK і Free після виконання такої операції:
pop (SPK)
3. Задано однонаправлений лінійний зв’язаний список BEG, представлений за допомогою вказівників i вказівник K на передостанній елемент списку :
BEG K
(
(
(
(
(
(
. . .
(
(
(
NULL
data next
3а. Напишіть оператор присвоєння, який в змінну W запише адресу останнього елемента списку.
3б. Напишіть оператор (або оператори) присвоєння, який значення інформаційного поля на який вказує змінна K запише у інформаційне поле наступного після K елемента списку.
3в. Напишіть оператор циклу, який виведе на екран монітора слово ERROR стільки раз, скільки нульових елементів зустрінеться серед елементів списку.
СПИСОК ЛІТЕРАТУРИ
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
ЗМІСТ
Мета роботи……………………………………..……………………………………………3
Теоретичні відомості..........….………………………………………………………….…. .3
Порядок виконання роботи..............………………………………………..……..………...10
Завдання на лабораторну роботу ....………………………………………..……..………...10
Вибір індивідуального завдання ...………………………………………………………… 12
Вимоги до оформлення звіту.......................……...……..………………………………….. 13
Контрольні завдання................………..……………………………………………………. 13
Список літератури ………...……….....................…………………………………………..14
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
"Структура даних СПИСОК"
з дисципліни
“Програмування. Частина IIІ. Структури даних та алгоритми"
для підготовки студентів напряму
6.050102 “Комп’ютерна інженерія”
Укладач Т.А.Лисак, ст. викладач каф.ЕОМ
Редактор
Комп’ютерне складання
Підписано до друку 2010 р.
Формат 70 х 100 1/16. Папір офсетний.
Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ......
Наклад ..... прим. Зам.
Поліграфічний центр
Видавництва Національного університету “Львівська політехніка”
вул. Колесси, 2, 79000, Львів
28.02.2016 12:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора