Удаление узла

Вставка узла

Одной из типичных операций при работе со списком является вставка нового узла в определенное место связанного списка.

Если происходит вставка узла в односвязном списке, нужно выполнить следующие действия:

1. Необходимо выделить память под новый узел.

2. Записать в новый узел значение.

3. Записать в указатель на следующий узел в этом узле адрес узла, который должен располагаться после нового узла.

4. Заменить в узле, который будет располагаться перед новым узлом, записанный адрес на адрес нового узла.

Если осуществить действия в другом порядке, то мы потеряем адрес узла, который должен располагаться после нового узла. А это означает, что мы не только не найдем этот узел, но и потеряем все узлы, расположенные за ним.

Покажем добавление узла в односвязный список с помощью следующего рисунка. Нумерация действий на рисунке совпадает с приведенной выше нумерацией действий.

Второй типичной операцией со списками является удаление узла, находящегося в середине списка.

В односвязном списке для удаления узла нужно выполнить следующие действия:

1. Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел в узле, предшествующем удаляемому.

2. Удалить узел, предназначенный для удаления.

1. Виды линейных списков: стек, очередь, дек.

Линейные списки – структуры данных, в которых элементы (переменные) следуют друг за другом, и каждому можно поставить в соответствие порядковый номер.

Стек – это линейный список, в котором все операции вставки и удаления(и как правило операции доступа к данным) выполняются только на одном конце списка.

Очередь (или односторонняя очередь) – это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления(и как правило операции доступа к данным) – на другом.

Дек (или двусторонняя очередь) – это линейный список, в котором все операции вставки и удаления (и как правило операции доступа к данным) выполняются на обоих концах списка.

1. Описание структуры на языке C++. Определение переменных структурного типа. Способы доступа к элементам структур.

1. Описание объединения на языке C++. Определение переменных типа «объединение». Способы доступа к элементам объединений.

1. Сущность методологии объектно-ориентированного программирования. Инкапсуляция. Наследование. Полиморфизм.

Инкапсуляция – это принцип ООП, объединяющий в одном классе данные и методы, манипулирующие этими данными и защищающие данные класса от внешнего воздействия.

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

Класс также защищает свое состояние (значения свойств) от несанкционированного изменения, это реализуется с помощью раздела классаprivate. Включенные в private свойства доступны только этому объекту, поэтому не могут быть изменены другими объектами. Для доступа к свойствам в раздел класса public включаются методы. Методы проверяют, возможно ли такое изменение состояния объекта под влиянием других объектов, и только после этого изменяют значения переменных состояния. Если переход в новое состояние невозможен, методы оставляют объект в прежнем состоянии.

1. Определение класса на языке C++. Ограничение доступа к членам класса.

Класс предоставляет механизм для создания объектов. В

классе отражены важнейшие концепции объектно-ориентированного про-

граммирования: инкапсуляция, наследование, полиморфизм.

С точки зрения синтаксиса, класс в С++ − это структурированный

тип, образованный на основе уже существующих типов.

В этом смысле класс является расширением понятия структуры. В

простейшем случае класс можно определить с помощью конструкции:

тип_класса имя_класса{список_членов_класса};

где

тип_класса – одно из служебных слов class, struct, union;

имя_класса – идентификатор;

список_членов_класса – определения и описания типизированных

данных и принадлежащих классу функций.

Управление доступом в языке С# организуется с помощью четырех модификаторов доступа: public, private, protected и internal.

Когда член класса обозначается спецификатором public, он становится доступным из любого другого кода в программе, включая и методы, определенные в других классах. Когда же член класса обозначается спецификатором private, он может быть доступен только другим членам этого класса. Следовательно, методы из других классов не имеют доступа к закрытому члену (private) данного класса. Eсли ни один из спецификаторов доступа не указан, член класса считается закрытым для своего класса по умолчанию. Поэтому при создании закрытых членов класса спецификатор private указывать для них необязательно.

С помощью модификатора доступа protected обеспечивается создание защищенного члена класса, доступ к которому открыт в пределах иерархии классов. А модификатор internal служит в основном для сборок.

1. Дружественные функции класса.

Дружественные функции Дружественные функции – это функции, объявленные вне класса, но имеющие доступ к закрытым и защищенным полям данного класса Дружественная функция объявляется внутри класса с модификатором friend Дружественные функции не являются членами класса, поэтому им не передается указатель this Правило использования: Если нет важных доводов использовать дружественные функции – используйте вместо них члены класса Если важные доводы есть – подумайте, а действительно ли они так важны

1. Определение конструктора. Форматы вызова конструктора. Перегрузка конструкторов.

В объектно-ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) — специальный блок инструкций, вызываемый при создании объекта.

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

Термин «конструктор» также используется для обозначения одного из тегов, описывающих данные в алгебраическом типе данных. Это использование несколько отличается от описываемого в статье. Для дополнительной информации смотрите Алгебраический тип данных.

В большинстве языков конструктор может быть перегружен, что позволяет использовать несколько конструкторов в одном классе, причём каждый конструктор может иметь различные параметры.

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

Вторая задача — упростить пользование объектом. Объект — не «вещь в себе», ему часто приходится требовать какую-то информацию от других объектов: например, объект File, создаваясь, должен получить имя файла. Это можно сделать и через метод:

File file;

file.open("in.txt", File::omRead);

Но удобнее открытие файла сделать в конструкторе:^[1]

File file("in.txt", File::omRead);

[править]Виды конструкторов

Некоторые языки программирования различают несколько особых типов конструкторов:

§ конструктор по умолчанию — конструктор, не принимающий аргументов;

§ конструктор копирования — конструктор, принимающий в качестве аргумента объект того же класса (или ссылку из него);

§ конструктор преобразования — конструктор, принимающий один аргумент (эти конструкторы могут вызываться автоматически для преобразования значений других типов в объекты данного класса).

Деструктор

§ #include <iostream>

§ using namespace std;

§

§ class NameOfClass

§ {

§ private:

§ int a;

§ public:

§ NameOfClass(int m);

§ ~NameOfClass();

§ };

§

§ NameOfClass::~NameOfClass()

§ {

§ cout << this->a << endl;

§ }

§

§ NameOfClass::NameOfClass(int m)

§ {

§ a = m;

§ }

Дестру́ктор — специальный метод класса, служащий для деинициализации объекта (например освобождения памяти).

1. Наследование. Определение базового и производного классов.

Насле́дование — механизм объектно-ориентированного программирования (наряду с инкапсуляцией, полиморфизмом и абстракцией), позволяющий описать новый класс на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом.

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

C++

Наследование в C++:

class A{ //базовый класс}; class B: public A{ //public наследование}; class C: protected A{ //protected наследование}; class Z: private A{ //private наследование};

В C++ существует три типа наследования: public, protected, private.

Класс, от которого произошло наследование, называется базовым или родительским (англ. base class). Классы, которые произошли от базового, называются потомками, наследниками или производными классами (англ. derived class).

1. Полиморфизм. Виртуальные функции.

Полиморфизм (polymorphism) (от греческого polymorphos) - это свойство, которое позволяет одно и то же имя использовать для решения двух или более схожих, но технически разных задач. Целью полиморфизма, применительно к объектно-ориентированному программированию, является использование одного имени для задания общих для класса действий. Выполнение каждого конкретного действия будет определяться типом данных. Например для языка Си, в котором полиморфизм поддерживается недостаточно, нахождение абсолютной величины числа требует трёх различных функций: abs(), labs() и fabs(). Эти функции подсчитывают и возвращают абсолютную величину целых, длинных целых и чисел с плавающей точкой соответственно. В С++ каждая из этих функций может быть названа abs(). Тип данных, который используется при вызове функции, определяет, какая конкретная версия функции действительно выполняется. В С++ можно использовать одно имя функции для множества различных действий. Это называется перегрузкой функций (function overloading).

В более общем смысле, концепцией полиморфизма является идея "один интерфейс, множество методов". Это означает, что можно создать общий интерфейс для группы близких по смыслу действий. Преимуществом полиморфизма является то, что он помогает мнижать сложность программ, разрешая использование того же интерфейса для задания единого класса действий. Выбор же конкретного действия, в зависимости от ситуации, возлагается на компилятор. Вам, как программисту, не нужно делать этот выбор самому. Нужно только помнить и использовать общий интерфейс. Пример из предыдущего абзаца показывает, как, имея три имени для функции определения абсолютной величины числа вместо одного, обычная задача становится более сложной, чем это действительно необходимо.

Полиморфизм может применяться также и к операторам. Фактически во всех языках программирования ограниченно применяется полиморфизм, например, в арифметических операторах. Так, в Си, символ + используется для складывания целых, длинных целых, символьных переменных и чисел с плавающей точкой. В этом случае компилятор автоматически определяет, какой тип арифметики требуется. В С++ вы можете применить эту концепцию и к другим, заданным вами, типам данных. Такой тип полиморфизма называется перегрузкой операторов (operator overloading).

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

Дата добавления: 2015-04-24