10. Связные списки. Удаление элемента из списка. Сравнение с удалением из массива. Примеры.

books* poisk(books* start, intid) // функция поиска элемента списка по номеру

{

while (start != NULL)

{

if (start->nomer == id)

return start;

start = start->next;

}

return NULL;

}

//...

current = poisk(start, id);

tmp = current;

if (tmp == start) //если первый

start = current->next;

elseif (tmp->next == NULL) //если последний

{

current = start;

while (current->next->nomer != id)

current = current->next;

current->next = NULL;

}

else //не первый и не последний

{

current = start;

while (current->next->nomer != id)

current = current->next;

current->next = tmp->next;

}

deletetmp;

Для удаления элемента из массива нужно: Взять исходный массив; Выделить память под новый массив достаточного размера; Скопировать элементы старого массива в новый не копируя удаляемый элемент; Освободить память занимаемую старым массивом; Присвоить указателю на старый массив, указатель на новый.

Время выполнения операции вставки элемента в произвольную позицию массива и время удаления элемента из произвольной позиции линейно зависит от количества элементов массива. O(n).

Время выполнения операции вставки элемента в произвольную позицию списка и время удаления элемента из произвольной позиции постоянно (т.е. не зависит от количества элементов списка). O(1)

11. Связные списки. Обход списка. Сортировка списка. Примеры.

Обход с первого элемента:

books* end(books* start)

{

while (start->next != NULL) //пока есть элементы

start = start->next; //переходим к следующему элементу

returnstart;

}

Сортировка:

structbooks

{

intnomer;

string name;

string author;

int page;

int cost;

books* next;

};

//...

do

{

sortOK = false;

current = start;

while (current->next != NULL)

{

if (current->name > current->next->name)

{

swap(current->name, current->next->name);

swap(current->author, current->next->author);

swap(current->page, current->next->page);

swap(current->cost, current->next->cost);

sortOK = true;

}

current = current->next;

}

} while (sortOK);

12. Основы ооп. Различия функциональной и объектной декомпозиции. Мотивация введения ооп. Понятия класса и объекта.

Декомпозиция: Научный метод, использующий структуру задачи и позволяющий заменить решение одной большой задачи решением серии меньших задач.

Функциональная декомпозиция: Фокусировка на структурах данных и функциях их обработки. Объектная декомпозиция: Фокусируется на объектах и их отношениях друг с другом.

ООП возникло в результате развития идеологии процедурного программирования, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны.

Класс – это производный тип, введенный программистом на основе уже существующих типов. Механизм классов позволяет создавать типы, с наибольшей полнотой отображающие особенности решаемой задачи. Класс задает некоторую структурированную совокупность типизированных данных и позволяет определить набор операций над этими данными.

Объект - это конкретный экземпляр класса, располагающийся в памяти компьютера.

13. Основы ООП. Сравнение класса и структуры в С++. Модификаторы доступа private, protected, public. Примеры.

Структура	Класс
structbooks { intnomer; string name; string author; int page; int cost; books* next; };	class books { public: intnomer; string name; string author; int page; intcost; books* next; };

Модификатор доступа public (открытый): К членам класса (функциям и данным), объявленным с модификатором public можно получить доступ из любого места программы.

Модификатор доступа private (закрытый): К членам класса (функциям и данным), объявленным с модификатором private можно получить доступ только из функций самого класса (а также из функций и классов друзей).

Модификатор доступа protected (защищенный): К членам класса (функциям и данным), объявленным с модификатором protected можно получить доступ только из функций самого класса, из функций потомков класса, (а также из функций‐друзей и классов‐ друзей).

Наследование – это использование ранее определенного класса. Язык С++ позволяет классу наследовать данные и функции члены одного или нескольких других классов. Другими словами, новый класс может получать атрибуты и поведение от уже существующего класса. Новый класс называют производным классом. Класс, элементы которого наследуются производным классом, называется базовым классом.

14. Основы ООП. Понятие инкапсуляции. Способы ее реализации в С++. Перегрузка операторов.

Инкапсуляция: • Свойство языка программирования, позволяющее объединить и защитить данные и код в объект и скрыть реализацию объекта от пользователя (прикладного программиста). При этом пользователю предоставляется только спецификация (интерфейс) объекта. • Пользователь может взаимодействовать с объектом только через этот интерфейс. Реализуется с помощью директив: public, private, protected. • Пользователь не может влиять на работу объекта, кроме как через интерфейс. Реализуется с помощью использования закрытых данных и методов, значения которых берутся из открытого интерфейса при создании объекта.

Примеринкапсуляции:

class Student

{

public:

voidsetName(constchar* name)

{

if (name != NULL &&strlen(name) < 80)

{

strcpy(_name, name);

}

}

constchar* getName()

{

return _name;

}

private:

char _name[80];

};

Пример использования класса:

Student s;

s.setName("Вася");

Перегрузка функций: Перегрузка (англ. «overloading») – возможность использования функций, имеющих одинаковые имена, но отличающихся друг от друга списком параметров  (количеством и /или типом  параметров).

Перегрузка операторов: • Иногда возникает потребность описывать и применять к созданным программистом типам данных операции, по смыслу эквивалентные уже имеющимся в языке. • Классический пример — библиотека для работы с комплексными числами. Они, как и обычные числовые типы, поддерживают арифметические операции, и естественным было бы создать для  данного типа операции «плюс», «минус», «умножить», «разделить», обозначив их теми же самыми знаками операций, что и для других числовых типов.

Перегрузка оператора присваивания:

Для класса Т1 оператор присваивания из типа Т2, являющийся членом класса, может иметь следующий вид. Передача параметра по ссылке: T1&operator=(T2&source); Передача параметра по значению: T1&operator=(T2 source);

Пример:

Class MyInt

{

public:

MyInt&operator=(MyInt& source)

{

_value = source._value;

Return*this;

}

MyInt&operator=(int value)

{

_value = value;

Return*this;

}

private:

int _value;

};

MyInt a, b;

b = 25;

a = b;