Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПОБУДОВА АБСТРАКТНОГО ТИПУ ДАНИХ. СПИСОК
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
З лабораторної роботи №1.3
На тему:
«ПОБУДОВА АБСТРАКТНОГО ТИПУ ДАНИХ. СПИСОК »
з дисципліни:
«Обчислювальний практикум»
Львів – 2013
Мета роботи:
Вивчити побудову та застосування до розв’язання прикладних задач динамічних структур даних.
Теоретична частина
Абстрактний тип даних
Абстрактний тип даних (АТД) - це тип даних, який надає для роботи з елементами цього типу певний набір функцій, а також можливість створювати елементи цього типу за допомогою спеціальних функцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення - в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних звичайно представляються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних стараються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не по швидкості) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Список
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
Завдання
Побудова АТД
Змоделювати абстрактний тип даних (АТД) , який використати в Завданні 4. Оформити АТД у вигляді класа. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Алгоритм розв’язання задачі:
Код програми:
list.cpp
#include <iostream>
#include <stdio.h>
using namespace std;
template<class item> class List
{
private:
//Вузол елемента списку
struct node
{
item data;
struct node *next;
};
node *end; //кінець списку
node *head; //початок списку
public:
List()//Конструктор
{
//Список не визначений
head = NULL;
end = NULL;
}
//Деструктор
~List()
{
node *tmp = head; //Видалення всіх елементів списку
while(head)
{
tmp = head;
head = head->next;
delete tmp;
}
}
//Виведення списку на екран
void print(char *fs)
{
node *tmp = head;
//список не поржній
cout << "список:";
while(tmp)
{
cout << tmp->data;
if (tmp->next)
cout << fs;
tmp = tmp->next;
}
//Список порожній
if (!head)
cout << "порожнiй";
cout << endl;
}
//Додати елемент в кінець списку
void push_back(item it)
{
node *tmp;
if (!head)
{
end = head = tmp = new node;
end->data = it;
end->next = NULL;
}
else
{
end->next = tmp = new node;
end = end->next;
end->data = it;
end->next = NULL;
}
}
//Додати елемент на початок списку
void push_front(item it)
{
node *tmp = new node;
tmp->next = head;
tmp->data = it;
head = tmp;
}
//Видалити елемент з початку
void pop_front()
{
node *tmp;
if (head)
{
tmp = head->next;
delete head;
head = tmp;
}
}
//Видалити елемент з кінця
void pop_back()
{
if (head)
{
node *tmp = head;
while (tmp->next != end)
tmp = tmp->next;
delete end;
end = tmp;
end->next = NULL;
}
else
{
delete end;
end = NULL;
head = NULL;
}
}
//Занесення в список даної послідовності
void push(item it)
{
if (it >= 0)
sort_insert(it);
else
remove(-it);
}
//Видалити всі елементи значення яких рівне it
bool remove(item it)
{
int k = 1;
node *tmp = head;
node *temp = head;
if(head == NULL)
return 1;
while(tmp)
{
if(tmp->data == it)
{
if(tmp == head)
{
head = head->next;
delete tmp;
k = 0;
tmp = head;
temp = head;
continue;
};
temp->next = tmp->next;
delete tmp;
k = 0;
tmp = temp->next;
}
else{
if(tmp != head)
temp = temp->next;
tmp = tmp->next;
}
}
return 0;
}
//Вставка елементу за зростанням
void neparni()
{
node *tmp = head;
bool b = 1;
if (head){
while(tmp)
{
b = b && (tmp->data % 2 == 1);
tmp = tmp->next;
}
if (b)
cout << "Bсi елементи непарнi." << endl;
else
cout << "Є парнi елементи." << endl;
}
}
//Вставка елементу за зростанням
bool sort_insert(item it)
{
node *tmp = head;
node *temp = new node;
temp->data = it;
node *prev = head;
if(!head)
{
head = temp;
temp->next = NULL;
return 0;
}
else{
while(tmp->data < it)
{
if(tmp->next == NULL)
{
tmp->next = temp;
temp->next = NULL;
return 0;
}
if(tmp != head)
prev = prev->next;
tmp = tmp->next;
}
if(tmp == head)
{
temp->next = head;
head = temp;
return 0;
}
prev->next = temp;
temp->next = tmp;
return 0;
}
}
};
main.cpp
#include "list.cpp"
#include <iostream>
#include <stdio.h>
void main()
{
setlocale(0,""); //Ввімкнення кирилиці
int i,a;
List<int> lst;
//Занесення даних в список з клавіатури
lst.print(", ");
for(i = 0; i <= 15; i++)
{
cout << "a="; cin >> a;
lst.push(a);
lst.print(", "); //Виведення списку
}
lst.neparni(); //Виведення результату обробки списку
getchar();
getchar();
}
Результат виконання програми:
/
Рис1. Ескіз вікна з результатом виконання програми
Висновок: Виконавши дану лабораторну роботу, я зрозумів що собою являє абстрактний тип даних, а також як працює і реалізовується АТД "Список" .
14.04.2015 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора