Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних СПИСОК
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних СПИСОК
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 6
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напрямку
6.0915 “Комп’ютерна інженерія”
Львів – 2008
Методичні вказівки до лабораторної роботи "Структура даних СПИСОК" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2008 – 27 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Опир Ю.М., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних списка. Набуття практичних навичок побудови списка, дослідження динаміки його вмісту та використання списків для розв'язання прикладних задач.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщатися вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщатися по списку вперед та назад.
Вставка і видалення вузлів списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів. Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
Приклад 1: Приклад динаміки вмісту списку, реалізованого на базі масиву:
Функція InitList(List);
Реалізація списку на базі масиву
Схематичне зображення списків
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
Результат виконання функцій AddEnd (List , 106);
AddEnd (List , 245);
AddEnd (List , 317);
AddEnd (List , 472);
Delete (List , 4);
AddEnd (List , 808);
Delete (List , 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
Free
0
(
0
(
472
(
317
NULL
Функція PutBefore (List , 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
Free
0
(
0
(
472
(
317
NULL
List
106
(
245
(
613
(
808
NULL
Free
0
(
472
(
317
NULL
Функція Delete ( List , 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
Free
0
(
472
(
317
NULL
List
245
(
613
(
808
NULL
Free
0
(
472
(
317
(
106
NULL
Розглянемо програмну реалізацію структури даних список, представленої за допомогою вказівників та застосування її для тестової демонстрації роботи зі списком:
// Інтерфейс обробки списків
#define infotype int
#define printfspec "%d "
/*
Нагадаемо символи форматування для основних типів даних:
----------------+-----------------------------
| %c | char |
|---------------+----------------------------|
| %d | int, short |
|---------------+----------------------------|
| %ld | long |
|---------------+----------------------------|
| %f | float, double |
|---------------+----------------------------|
| %s | arrays of type of char |
|---------------+----------------------------|
| %u | unsigned int,unsigned short|
|---------------+----------------------------|
| %lu | unsigned long |
----------------+-----------------------------
*/
struct node
{ infotype data;
struct node *next;
};
typedef struct node *list;
void Init(list *head_list_ptr);
int Empty(list head_list);
void AddStart(list *head_list_ptr, infotype new_data);
void AddEnd(list *head_list_ptr, infotype new_data);
void PutAfter(list *node_prt, infotype new_data);
void PutBefore(list *node_prt, infotype new_data);
void Change(list *node1_ptr, list *node2_ptr);
list Find(list head_list, infotype search_data);
list FindBefore(list head_list, list node_ptr);
list FindAfter(list node_ptr);
list FindLast(list head_list);
void Delete(list *head_list_ptr, list *node_ptr);
void PrintStraight(list head_list);
void PrintReverse(list head_list);
// Реалізація інтерфейсу обробки списків
#include <stdlib.h>
#include <assert.h>
#include "plist.h"
// Ініціалізація списку
void Init(list *head_list_ptr)
{
*head_list_ptr = NULL;
return;
}
// Перевірка чи список порожній
int Empty(list head_list)
{
return head_list == NULL;
}
// Додавання нового вузла на початок списку
void AddStart(list *head_list_ptr, infotype new_data)
{
list new_node;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = *head_list_ptr;
*head_list_ptr = new_node;
return ;
}
// Додавання нового вузла в кінець списку
void AddEnd(list *head_list_ptr, infotype new_data)
{
list new_node;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = NULL;
if (Empty(*head_list_ptr)) *head_list_ptr = new_node;
else
FindLast(*head_list_ptr)->next = new_node;
return ;
}
// Вставка нового вузла після заданого вузла списку
void PutAfter(list *node_prt, infotype new_data)
{
list new_node = NULL;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*node_prt)->next;
(*node_prt)->next = new_node;
return ;
}
// Вставка нового вузла перед заданим вузлом списку
void PutBefore(list *node_prt, infotype new_data)
{
PutAfter(node_prt,new_data);
Change(node_prt,&((*node_prt)->next));
return ;
}
// Обмін інформаційних полів двух заданих вузлів списку
void Change(list *node1_ptr, list *node2_ptr)
{
infotype tmp = (*node1_ptr)->data;
(*node1_ptr)->data = (*node2_ptr)->data;
(*node2_ptr)->data = tmp;
}
// Пошук вузла із заданим значенням в списку
list Find(list head_list, infotype search_data)
{
while ((head_list) && (head_list->data != search_data)) head_list = head_list->next;
return head_list;
}
// Пошук вузла в списку, що знаходиться перед заданим вузлом
list FindBefore(list head_list, list node)
{
while ((head_list->next != node) && head_list) head_list = head_list->next;
return head_list;
}
// Пошук вузла в списку що знаходиться після заданого вузла
list FindAfter(list node)
{
return node->next;
}
// Пошук останнього вузла списку
list FindLast(list head_list)
{
if (head_list) while (head_list->next) head_list = head_list->next;
return head_list;
}
// Вилучення заданого вузла зі списку
void Delete(list *head_list_ptr, list *node_ptr)
{
list tmp , save_ptr = *node_ptr;
assert(*head_list_ptr);
assert(*node_ptr);
if (*node_ptr == *head_list_ptr)
*head_list_ptr = (*head_list_ptr)->next;
else
if (!((*node_ptr)->next))
{
tmp = FindBefore(*head_list_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 PrintStraight(list head_list)
{
while (head_list)
{
printf(printfspec,head_list->data);
head_list = head_list->next;
}
printf("\n");
return;
}
// Роздрук списку в зворотньому порядку
void PrintReverse(list head_list)
{
if (head_list)
{
PrintReverse(head_list->next);
printf(printfspec,head_list->data);
}
return;
}
// Приклад тестової демонстрації роботи зі списком
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include "plist.h"
list MergeLists(list list1, list list2);
void main()
{
list l2 , fl;
infotype x = 0;
struct node a={3,NULL}, b={2,&a}, c={1,&b}, *l1 = &c;
Init(&l2);
printf("\nEnter elements in the second list:\n");
do {
printf("Enter the new element(zero - break inputing elements): ");
scanf("%d",&x);
if (x)
AddEnd(&l2,x);
}
while (x);
PrintStraight(l1);
PrintStraight(l2);
x=l2->next->next->data;
printf("%d " , x);
PutBefore(&(l1->next),4);
PrintStraight(l1);
AddStart(&l1,6);
PrintStraight(l1);
AddEnd(&l1,5);
PrintStraight(l1);
Delete(&l1,&l1);
PrintStraight(l1);
scanf("%d",&x);
fl = Find(l1,x);
Delete(&l1,&fl);
PrintStraight(l1);
Change(&l1,&(l1->next));
PrintStraight(l1);
printf("\nMerged lists:\n");
PrintStraight(MergeLists(l1,l2));
printf("\nPrinted merged lists in back order:\n");
PrintReverse(MergeLists(l1,l2));
getch();
return;
}
list MergeLists(list list1, list list2)
{
list mlist = NULL;
while (list1)
{
AddEnd(&mlist,list1->data);
list1 = list1->next;
};
while (list2 )
{
AddEnd(&mlist,list2->data);
list2 = list2->next;
};
return mlist;
}
В бібліотеці стандартних шаблонів 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. ЗМІСТ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій вказати назву лабораторної роботи, її номер та номер варіанту.
II. В звіті мають бути відображені наступні пункти:
1. Мета роботи.
2. Завдання 1.
2.1. Постановка задачі.
2.2. Словесний алгоритми розв’язання задачі.
2.3. Система тестів зі схематичними зображеннями всіх списків
2.4. Результати виконання програми.
3. Завдання 2.
3.1. Постановка задачі.
3.2. Динаміка вмісту списку.
3.3. Результати виконання програми.
Висновки.
Додаток 1: Текст програми до завдання 1 (обов’язково відображати на екрані всі зміни, що будуть відбуватись у списку).
Додаток 2: Текст програми до завдання 2 (обов’язково відображати на екрані всі зміни, що будуть відбуватись у списку).
5. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
І. Завдання 1: Використати для розв’язання задач клас list зі стандартної бібліотеки шаблонів STL .
1. Многочлен виду , де представити у вигляді зв’язаного списку в якому кожний вузол має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний вузол списку. Для описаного представлення многочленів програмно реалізувати такі операції:
А) Додавання двох многочленів.
Б) Множення многочлена на одночлен.
В) Диференціювання многочлена.
2. Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання таких операцій над ними:
А) Додавання двох поліномів.
Б) Обчислення полінома по заданим значенням X , Y , Z .
3. Написати програму для роботи з розрідженими матрицями, представленими у вигляді зв’язаних списків:
А) Транспонування розрідженої матриці, заданої у формі списків.
Б) Додавання двох матриць, заданих у формі списків.
4. Написати програму роботи з довгими числами (довгі числа – це числа, що виходять за діапазон допустимих значень будь-якого стандартного цілого або дійсного типу). Структура збереження довгих чисел повинна забезпечувати ефективну роботу з довільними (додатними і від’ємними) довгими цілими числами. Реалізувати роботу з довгими числами:
А) Додавання двох довгих чисел.
Б) Порівняння двох довгих чисел (дорівнює, не дорівнює, більше, менше).
В) Обчислення значення n!, де n > 12.
ІІ. Завдання 2: Побудувати динамічну структуру даних список, реалізований за допомогою вказівників.
1. Написати програму, яка будує лінійний зв’язаний список, що містить N випадкових цілих чисел з проміжку [100; 200], де N – випадкове число з проміжку [1 ; 20], а після цього переглядає список і дублює в списку всі вузли, що містять в інформаційному полі парні числа (Примітка.: дублює , тобто зразу після знайденого вузла створює ще один такий самий вузол).
2. Написати програму, яка будує лінійний зв’язаний список, що містить N великих літер латинського алфавіту, які вводяться з клавиатури, і перевіряє, чи будуть вузли списку впорядковані за алфавітом. (Примітка.: великі літери латинського алфавіту в таблиці ASCII мають номери від 65 до 90 ).
3. Написати програму, яка будує два лінійних зв’язаних списка SP1 i SP2, що містять відповідно по N1 i N2 випадкових дійсних чисел з проміжку [130; 310] і створює новий список SP3, який мiстить спiльнi елементи списків SP1 i SP2.
4. Написати програму, яка будує лінійний зв’язаний список, що містить N випадкових цілих чисел з проміжку [111 ; 222] і вилучає з нього кожний другий елемент.
5. Написати програму, яка вводить з клавіатури послідовність ненульових дійсних чисел (ввід числа 0 – признак кінця введення послідовності), будує лінійний зв’язаний список, що містить елементи цієї послідовності і розбиває побудований список на два рівних або майже рівних (якщо кількість елементів списку - непарне число) по довжині списка.
6. Написати програму, яка будує лінійний зв’язаний список, що містить N випадкових дійсних чисел з проміжку [1; 50] і інвертує побудований список, тобто робить перший елемент останнім, другий передостаннім і т.д. Виводити на екран монітора всі зміни, що будуть відбуватись у списку.
7. Написати програму, яка будує лінійний зв’язаний список List , що містить N випадкових цілих чисел з проміжку [100; 500] і створює новий список, який мiстить вузли побудованого списку List , інформаційні поля яких повторюються.
8. Написати програму, яка вводить послідовність з N випадкових цілих чисел, що належать проміжку [-10; 10], де N – випадкове число з проміжку [1 ; 20]. Всі додатні числа цієї послідовності додаються в лінійний зв’язаний список, а кожне від’ємне число вилучає зі списку відповідне додатнє число. Якщо такого числа немає у списку, то виводиться повідомлення про відсутність числа у списку. Виводити на екран монітора всі зміни, що будуть відбуватись у списку.
9. Написати програму, яка будує лінійний зв’язаний список, що містить N великих букв латинського алфавіту, які задаються випадковим чином, і перевіряє, чи перший елемент списку містить букву “А”, якщо це так, то додається ще одна буква “А” в кінець списку, якщо ні – то зі списку вилучаються всі букви “А”. Вивести отриманий результат. (Примітка: великі букви латинського алфавіту в таблиці ASCII мають номери від 65 до 90 ).
10. Написати програму, яка будує лінійний зв’язаний список, що містить N випадкових дійсних чисел з проміжку [30; 80] і міняє місцями значення кожних двох сусідніх елементів списку, тобто значення першого елемента міняється зі значенням другого, третього з четвертим і т.д.
6. ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
Перша літера прізвища
Номер студента в списку групи
А, І, С
Б, Ї, Т
В, Й, У
Г, К, Ф
Д, Л, Х
Е, М, Ц
Є, Н, Ч
Ж,О,Ш,Щ
З, П, Ю
И, Р, Я
10, 20, 30
І 1 А
ІІ 1
І 1 А
ІІ 2
І 1 А
ІІ 3
І 1 А
ІІ 4
І 1 А
ІІ 5
І 1 А
ІІ 6
І 1 А
ІІ 7
І 1 А
ІІ 8
І 1 А
ІІ 9
І 1 А
ІІ 10
9, 19, 29
І 2 А
ІІ 1
І 2 А
ІІ 2
І 2 А
ІІ 3
І 2 А
ІІ 4
І 2 А
ІІ 5
І 2 А
ІІ 6
І 2 А
ІІ 7
І 2 А
ІІ 8
І 2 А
ІІ 9
І 2 А
ІІ 10
8, 18, 28
І 3 А
ІІ 1
І 3 А
ІІ 2
І 3 А
ІІ 3
І 3 А
ІІ 4
І 3 А
ІІ 5
І 3 А
ІІ 6
І 3 А
ІІ 7
І 3 А
ІІ 8
І 3 А
ІІ 9
І 3 А
ІІ 10
7, 17, 27
І 4 А
ІІ 1
І 4 А
ІІ 2
І 4 А
ІІ 3
І 4 А
ІІ 4
І 4 А
ІІ 5
І 4 А
ІІ 6
І 4 А
ІІ 7
І 4 А
ІІ 8
І 4 А
ІІ 9
І 4 А
ІІ 10
6, 16, 26
І 1 Б
ІІ 1
І 1 Б
ІІ 2
І 1 Б
ІІ 3
І 1 Б
ІІ 4
І 1 Б
ІІ 5
І 1 Б
ІІ 6
І 1 Б
ІІ 7
І 1 Б
ІІ 8
І 1 Б
ІІ 9
І 1 Б
ІІ 10
5, 15, 25
І 2 Б
ІІ 1
І 2 Б
ІІ 2
І 2 Б
ІІ 3
І 2 Б
ІІ 4
І 2 Б
ІІ 5
І 2 Б
ІІ 6
І 2 Б
ІІ 7
І 2 Б
ІІ 8
І 2 Б
ІІ 9
І 2 Б
ІІ 10
4, 14, 24
І 3 Б
ІІ 1
І 3 Б
ІІ 2
І 3 Б
ІІ 3
І 3 Б
ІІ 4
І 3 Б
ІІ 5
І 3 Б
ІІ 6
І 3 Б
ІІ 7
І 3 Б
ІІ 8
І 3 Б
ІІ 9
І 3 Б
ІІ 10
3, 13, 23
І 4 Б
ІІ 1
І 4 Б
ІІ 2
І 4 Б
ІІ 3
І 4 Б
ІІ 4
І 4 Б
ІІ 5
І 4 Б
ІІ 6
І 4 Б
ІІ 7
І 4 Б
ІІ 8
І 4 Б
ІІ 9
І 4 Б
ІІ 10
2, 12, 22
І 1 В
ІІ 1
І 1 В
ІІ 2
І 1 В
ІІ 3
І 1 В
ІІ 4
І 1 В
ІІ 5
І 1 В
ІІ 6
І 1 В
ІІ 7
І 1 В
ІІ 8
І 1 В
ІІ 9
І 1 В
ІІ 10
1, 11, 21
І 4 В
ІІ 1
І 4 В
ІІ 2
І 4 В
ІІ 3
І 4 В
ІІ 4
І 4 В
ІІ 5
І 4 В
ІІ 6
І 4 В
ІІ 7
І 4 В
ІІ 8
І 4 В
ІІ 9
І 4 В
ІІ 10
24.03.2013 13:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора