выа. Отчёт №1. Отчет по лабораторной работе 1 по дисциплине Алгоритмы и структуры данных Тема Списки Цель работы

• Название: Отчет по лабораторной работе 1 по дисциплине Алгоритмы и структуры данных Тема Списки Цель работы
• Дата: 11.11.2022
• Размер: 52.98 Kb.
• Имя файла: Отчёт №1.docx
• Тип: Отчет; #782915

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра вычислительной техники


отчет

по лабораторной работе №1

по дисциплине «Алгоритмы и структуры данных»

Тема: Списки

Цель работы:

Реализовать объект в виде связного списка с набором методов/функций. Данные, хранящиеся в списке имеют целочисленный тип данных.

Список методов/функций, реализуемые в программе:

1. 
   добавление в конец списка
   
2. 
   добавление в начало списка
   
3. 
   удаление последнего элемента
   
4. 
   удаление первого элемента
   
5. 
   добавление элемента по индексу (вставка перед элементом, который был ранее доступен по этому индексу)
   
6. 
   получение элемента по индексу
   
7. 
   удаление элемента по индексу
   
8. 
   получение размера списка
   
9. 
   удаление всех элементов списка
   
10. 
    замена элемента по индексу на передаваемый элемент
    
11. 
    проверка на пустоту списка
    
12. 
    вставка другого списка в конец
    

Оценка временной сложности каждого метода:

1. 
   добавление в конец списка
   

Так как надо проходить через весь список (в нем нельзя обращаться по индексам как в массиве), то временная сложность зависит от кол-ва элементов в списке => O(n).

2. 
   добавление в начало списка
   

Алгоритм полностью противоположность выше упомянутого, то есть каждый раз мы обращаемся только к начальному элементу => O(1).

3. 
   удаление последнего элемента
   

Логично, что сложность 1 и 3 одинаковы => O(n).

4. 
   удаление первого элемента
   

Логично, что сложность 2 и 4 одинаковы => O(1).

5. 
   добавление элемента по индексу (вставка перед элементом, который был ранее доступен по этому индексу)
   

Сложность зависит от номера индекс, то есть чем индекс меньше тем быстрее выполнится функция, так как будет меньше хождение через список => O(x), где x – элемент, который был ранее доступен по этому индексу.

6. 
   получение элемента по индексу
   

Сложность зависит от номера индекс, то есть чем индекс меньше тем быстрее выполнится функция, так как будет меньше хождение через список => O(x), где x – элемент, который доступен по этому индексу.

7. 
   удаление элемента по индексу
   

Сложность зависит от номера индекс, то есть чем индекс меньше тем быстрее выполнится функция, так как будет меньше хождение через список => O(x), где x – элемент, который доступен по этому индексу.

8. 
   получение размера списка
   

Так как надо проходить через весь список (в нем нельзя обращаться по индексам как в массиве), то временная сложность зависит от кол-ва элементов в списке => O(n).

9. 
   удаление всех элементов списка
   

Так как надо проходить через весь список (в нем нельзя обращаться по индексам как в массиве), то временная сложность зависит от кол-ва элементов в списке => O(n).

10. 
    замена элемента по индексу на передаваемый элемент
    

Сложность зависит от номера индекс, то есть чем индекс меньше тем быстрее выполнится функция, так как будет меньше хождение через список => O(x), где x – элемент, который доступен по этому индексу.

11. 
    проверка на пустоту списка
    

Так как проверяется только начальный элемент => O(1)

12. 
    вставка другого списка в конец
    

Так как надо проходить через весь список (в нем нельзя обращаться по индексам как в массиве), то временная сложность зависит от кол-ва элементов в списке => O(n).

Пример работы:


Листинг:

#include

using namespace std;


class Node

{

public:

int index;

int data;

Node* next;

Node(int index,int flag);

};

Node::Node(int index,int flag){

int Value;

if (flag == 0) {

cout << "Enter value: ";

cin >> Value;

this->data = Value;

}

this->index = index;

this->next = nullptr;

}

class List {

public:

int Size;

Node* head;
List();
void addFirst(int i);
void deleteFirst();
void addEnd();
void deleteEnd();
void deleteIndex();
int getIndex();
void Out();
void getSize();
void deleteAll();
void changeIndex();
void isEmpty();
void addList(List lst);

};

List::List() {

head = nullptr;

}

void List::Out() {

Node* curr = head;

while (true) {

cout << curr->data << endl;

if (curr->next == nullptr) {

break;

}

curr = curr->next;

}

;

}

void List::addFirst(int i) {

int flag = 0;

Node* curr = new Node(i,flag);

curr->next = head;

head = curr;
}

void List::addEnd() {

int flag = 0;

if (head == nullptr) {

head = new Node(0,flag);

}

else {

Node* curr = head;

while (curr->next != nullptr) {

curr = curr->next;

}

int a = curr->index;

a++;

curr->next = new Node(a,flag);

}

}

void List::deleteEnd() {

Node* curr = head;

Node* end = curr;

while (curr->next != nullptr) {

end = curr;

curr = curr->next;

}

end->next = nullptr;

delete curr;

}

void List::deleteFirst() {

Node* curr = head;

head=curr->next;

delete curr;

curr = head;
while (curr->next != nullptr) {

curr->index--;

curr = curr->next;

}
}

void List::deleteIndex() {

int indexDel;

cout << "Enter Index to delete: ";

cin >> indexDel;

cout << endl;

Node* curr = head;

Node* prev = curr;
while (curr->next!=nullptr) {

if (curr->index == indexDel) {

break;

}

prev = curr;

curr = curr->next;

}

prev->next = curr->next;

delete curr;
curr = head;

while (curr->next != nullptr) {

curr->index--;

curr = curr->next;

}

curr->index = 0;

}

int List::getIndex() {

int indexGet;

cout << "Enter Index to get: ";

cin >> indexGet;

cout << endl;

Node* curr = head;
while (curr->next != nullptr) {

if (curr->index == indexGet) {

cout << "Requested: " << curr->data << endl;

return 0;

}

curr = curr->next;

}

if (curr->index == indexGet) {

cout << "Requested: " << curr->data << endl;

}

}

void List::getSize() {

Node* curr = head;

int size = 0;

while (curr->next != nullptr) {

size++;

curr = curr->next;

}

size++;

cout << "Size of list is: " << size << endl;

}

void List::deleteAll() {

Node* curr = head;

Node* tmp = curr;
while (curr != nullptr)

{

curr = curr->next;

delete tmp;

tmp = curr;

}

head = nullptr;

}

void List::changeIndex(){
Node* curr = head;

int changeIndex = 0;

int changeValue;
cout << "Enter index to change: "; cin >> changeIndex; cout << endl;

cout << "Enter value to change: "; cin >> changeValue; cout << endl;
while (curr->next != nullptr) {

if (curr->index == changeIndex) {

curr->data = changeValue;

break;

}

curr = curr->next;

}

if (curr->index == changeIndex) {

curr->data = changeValue;

}
}

void List::isEmpty() {

if (head == nullptr) {

cout << "List is empty" << endl;

}

else {

cout << "List doesn't empty" << endl;

}

}

void List::addList(List lst) {

int flag = 1;

Node* curr = head;

Node* curr2 = lst.head;

while (curr->next != nullptr) {

curr = curr->next;

}

int a = curr->index;

a++;

curr->next = new Node(a,flag);

curr->next = curr2;

}

int main() {

List lst;

List lst2;

cout << "First List: " << endl;

for (int i = 0; i < 10; i++) {

lst.addFirst(i);

}

lst.Out();
cout << "End was deleted" << endl;

lst.deleteEnd();

lst.Out();

cout << endl;
cout << "First was deleted" << endl;

lst.deleteFirst();

lst.Out();

cout << endl;
cout << "Index was deleted" << endl;

lst.deleteIndex();

lst.Out();

cout << endl;
cout << "Your Index" << endl;

lst.getIndex();

cout << endl;
lst.getSize();

cout << endl;
cout << "Index was changed" << endl;

lst.changeIndex();

lst.Out();
cout << endl << endl;

cout << "Second List: " << endl;

for (int i = 0; i < 10; i++) {

lst2.addEnd();

}
lst.addList(lst2);

cout << "New list was added" << endl;
lst.Out();

cout << endl;
lst.deleteAll();

lst.isEmpty();


return 0;

}