Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Реалізація видалення та додавання елементу
Звіт з практичної роботи №3
з дисципліни „ Теорія алгоритмів”
на тему:
« Порівняння реалізацій абстрактних типів даних, побудованих на базі різних структур даних »
| Перевірла: Ліхоузова Т.А. | Виконала: Студентка групи ІК-51 Бондар Єлизаветал |
Київ 2016
Постановка задачі
Однозв'язного лінійного списку за допомогою покажчиків та дослідження його аналітичної та практичної швидкодії
Реалізація видалення та додавання елементу
//Частина програми однозв'язного лінійного списку
// Написано Бондар Єлизаветою, студенткою групи ІК-51
template <class T>//елемент списку (має значення та покажчик на наступний)class ListEl{public: T value; ListEl* next; ListEl():next(nullptr){}}; template <class T>//сама реалізація спискуclass LinkedList{public: LinkedList (): head(nullptr),cur (nullptr), prev (nullptr){} ~LinkedList(); void chCur(T val); void next(); void toHead(); T readCur(); bool end(); void push(const T pushValue); void del(); //~linked_list();private: ListEl<T>* head; ListEl<T>* prev; ListEl<T>* cur; delFromPoint(ListEl<T>* del); int deletePN (ListEl<T>* prev, ListEl<T>* del); ListEl<T>* findEl (T seachValue, ListEl<T>** prevFind) const;};
template <class T>
// Функція додавання елементу
void LinkedList<T>::push(const T pushValue)
{
//створення елемету
ListEl<T>* pushNew = new ListEl<T>;
ListEl<T>* temp;
//обробка виподку, коли це перший елемент списку (вставка у голову списку)
if (this->cur == nullptr)
{
pushNew->value = pushValue;
this->head = pushNew;
this->cur = pushNew;
prev = nullptr;
}
else
{
//Обробка коли це не перший елемент (вставка між двома елементами)
pushNew->value = pushValue;
pushNew->next = this->cur->next;
this->cur->next = pushNew;
}
}
template <class T>
//Функція видалення елемента
void LinkedList<T>::del ()
{
//перевірка, чи існує єлемент, що треба видалити?
if (cur!= nullptr)
{
//обробка випадку, коли елемент у голові списку (голові присвоюється адреса другого елемента)
if(prev == nullptr)
{
this->head = cur->next;
cur->next = nullptr;
delFromPoint(cur);
cur = head;
}
else
{
//обробка загального випадка (попередньому елементу присвоюється покажчик на наступний
prev->next = cur->next;
cur->next = nullptr;
delFromPoint(cur);
cur = prev->next;
}
}
}
int main(int argc, char *argv[])
{
unsigned int startTime, endTime, time;
LinkedList<int> test;
//додавання елементів до списку
for (int i = 0; i<50000;i++)
{
test.push(1);
}
//перехід у середину списку
test.toHead();
test.next();
startTime = clock();
//видалення елементів зі списку
for (int i = 0; i<24000;i++)
{
test.del();
}
endTime = clock();
time = endTime - startTime;
//вивід результату
std::cout<<time<<std::endl;
return 0;
}
Тестові дані
На тестових даних до списку різну кількість разів додавалось число 1, як наступний елемент.
При видаленні, видалялися елементи з середини списку
Результати
Висновки:
Данна реалізація доцільна, коли треба постійно видаляти та додавати данні, що видно з дослідження. Швидкість данних операцій О(1). Але переміститися по такому списку досить складно, і недоцільно його використовувати, коли данні мають індекс (на жаль цей помент не показан в дослідженні)
| <== предыдущая | | | следующая ==> |
| Лидерство по издержкам | | | Linguistic competence and performance |
Date: 2016-05-16; view: 318; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |