Результат работы программы. Выполнена Затеваловой М.А
Связные списки
Выполнена Затеваловой М.А.
Проверил Силаев А.В.
Задание
Вариант
Блок-схемы
Код программы
List.h
struct ListNode
{
int value;
ListNode* next;
};
class List
{
private:
ListNode* last;
int size;
public:
List();
bool add(int val);
bool remove(int val);
bool removeAt(int index);
ListNode* getAt(int index);
ListNode* search(int val);
int searchMax();
void print();
void clear();
private:
void recPrint(ListNode* node, int index);
};
List.cpp
#include"List.h"
#include<iostream>
List::List ()
{
size = 0;
last = NULL;
}
bool List::add(int val)
{
if (size == 0)
{
last = new ListNode();
last->value = val;
last->next = NULL;
++size;
return true;
}
ListNode* tmp = last;
for (int i = 0; i < size; ++i)
{
if (tmp->value == val)
return false;
tmp = tmp->next;
}
tmp = new ListNode();
tmp->value = val;
tmp->next = last;
last = tmp;
++size;
return true;
}
bool List::remove(int val)
{
if (size == 0)
return false;
ListNode* tmp = last;
int i;
if (last->value == val)
{
last = last->next;
delete tmp;
--size;
return true;
}
for (i = 0; i < size - 1; ++i)
{
if (tmp->next->value == val)
break;
tmp = tmp->next;
}
if (i == size - 1)
return false;
ListNode* tmpToRemove = tmp->next;
tmp->next = tmp->next->next;
delete tmpToRemove;
--size;
return true;
}
bool List::removeAt(int index)
{
if (index >= size || index < 0)
return false;
int i;
ListNode* tmp = last;
for (i = size - 1; i > index + 1; --i)
tmp = tmp->next;
ListNode* tmpToRemove = tmp->next;
tmp->next = tmp->next->next;
delete tmpToRemove;
--size;
return true;
}
ListNode* List::getAt(int index)
{
if (index >= size || index < 0)
return NULL;
int i;
ListNode* tmp = last;
for (i = size - 1; i > index; --i)
tmp = tmp->next;
return tmp;
}
ListNode* List::search(int val)
{
int i;
ListNode* tmp = last;
for (i = 0; i < size; ++i)
{
if (tmp->value == val)
break;
tmp = tmp->next;
}
if (i == size)
return NULL;
else
return tmp;
}
int List::searchMax()
{
ListNode* tmp = last;
ListNode* max = last;
int i;
for (i = 0; i < size; ++i)
{
if (tmp->value > max->value)
max = tmp;
tmp = tmp->next;
}
tmp = last;
for (i = 0; i < size; ++i)
if (max != tmp)
tmp = tmp->next;
else
break;
return size - i - 1;
}
void List::print()
{
if (last == NULL)
{
std::cout << "Empty\n";
return;
}
recPrint(last, size - 1);
}
void List::recPrint(ListNode* node, int index)
{
if (node->next == NULL)
{
std::cout << index << ": " << node->value << "\n";
return;
}
recPrint(node->next, index - 1);
std::cout << index << ": " << node->value << "\n";
}
void List::clear()
{
ListNode* tmp;
for (int i = 0; i < size; ++i)
{
tmp = last;
last = last->next;
delete tmp;
}
size = 0;
last = NULL;
}
Main.cpp
//однонаправленный, целочисленный, 2 (запрещено), 4, 8
#include <iostream>
#include"List.h"
#include<time.h>
#include<string>
int main()
{
srand(time(0));
List* list = new List();
for (int i = 0; i < 20; ++i)
{
//пока не найдётся неповторяющийся элемент
while (!list->add(rand() % 100)) {}
}
std::cout.sync_with_stdio(false);
std::cout << "List has been created. Specify comand: ";
std::string command;
int arg;
while (true)
{
std::cin >> command;
if (command == "help" || command == "?")
{
std::cout << "Command list \n";
std::cout << "add value - adds value to the end of the list \n";
std::cout << "print - prints all the list \n";
std::cout << "clear - clears all the list \n";
std::cout << "searchMax - search maximal value in the list \n";
std::cout << "removeAt index - removes object with specified index \n";
std::cout << "exit - ends the application \n";
}
else
if (command == "exit")
{
list->clear();
delete list;
return 0;
}
else
if (command == "add")
{
std::cin >> arg;
if (list->add(arg))
std::cout << "Value " << arg << " has beed added\n";
else
std::cout << "This value has been exist\n";
}
else
if (command == "print")
{
list->print();
}
else
if (command == "clear")
{
list->clear();
std::cout << "Now list is empty\n";
}
else
if (command == "searchMax")
{
if (list->searchMax() != NULL)
std::cout << "Maximal value is " << list->searchMax() << "'th value " << list->getAt(list->searchMax())->value << "\n";
else
std::cout << "No elements in list!";
}
else
if (command == "removeAt")
{
std::cin >> arg;
if (list->removeAt(arg))
std::cout << "This value has been removed\n";
else
std::cout << "This value hasn't been exist\n";
}
else
std::cout << "Unknown command\n";
std::cout << "Specify command: ";
}
system("pause");
}
Результат работы программы
List has been created. Specify comand: ?
Command list
add value - adds value to the end of the list
print - prints all the list
clear - clears all the list
searchMax - search maximal value in the list
removeAt index - removes object with specified index
exit - ends the application
Specify command: print
0: 38
1: 51
2: 37
3: 96
4: 18
5: 71
6: 53
7: 40
8: 26
9: 8
10: 87
11: 63
12: 62
13: 41
14: 83
15: 73
16: 32
17: 84
18: 7
19: 75
Specify command: add 73
This value has been exist
Specify command: add 74
Value 74 has beed added
Specify command: removeAt 13
This value has been removed
Specify command: print
0: 38
1: 51
2: 37
3: 96
4: 18
5: 71
6: 53
7: 40
8: 26
9: 8
10: 87
11: 63
12: 62
13: 83
14: 73
15: 32
16: 84
17: 7
18: 75
19: 74
Specify command: clear
Now list is empty
Specify command: print
Empty
Specify command: add 45
Value 45 has beed added
Specify command: add 6
Value 6 has beed added
Specify command: add 3
Value 3 has beed added
Specify command: add 999
Value 999 has beed added
Specify command: add 34
Value 34 has beed added
Specify command: add 23
Value 23 has beed added
Specify command: add 5
Value 5 has beed added
Specify command: add 78
Value 78 has beed added
Specify command: print
0: 45
1: 6
2: 3
3: 999
4: 34
5: 23
6: 5
7: 78
Specify command: searchMax
Maximal value is 3'th value 999
Specify command: exit
Вывод
Связные списки — довольно удобная структура для хранений данных. Благодаря гибкости связей отношения между элементами легко изменять — например, удаление элемента из середины связного списка будет несравненно быстрее, чем такое же удаление из массива. Есть и минус — нельзя быстро обратиться к элементу списка по индексу. Потому списки удобно использовать для структур вроде стеков, очередей и т.д.