Параметризованный класс двухсвязного списка

Реализация двусвязного списка

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

Вот как выглядит общая форма объявления параметризованного (обобщенного) класса.

template <class Tтип_данных> class имя_класса {

//....описание класса.......

};

Рассмотрим это объявление. Здесь Tтип_данных представляет собой имя типа шаблона, которое в каждом случае конкретизации будет замещаться фактическим типом данных. При необходимости, можно определить более одного параметризованного типа данных, используя список с разделителем-запятой, т.е. параметризованные классы могут иметь несколько аргументов шаблона. Заметим, что в пределах определения класса имя Tтип_данных можно использовать в любом месте. Когда создан параметризованный класс, Вы можете создать конкретную реализацию этого класса, используя следующий синтаксис:

имя_класса <тип_данных> объект;

В приведенном синтаксисе тип_данных представляет собою имя типа данных, над которыми фактически оперирует класс, и заменяет собой переменную Tтип_данных

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

template <class data_t> class list {
data t data;
list *next;

list *prev;
public:

list (data_t d);

void add(list *node) { node->next = this; next = 0; }
list *getnext() { return next; }
data_t getdata() { return data: }

}

Также внутри тела класса мы можем создать шаблоны-функций для работы с элементами двусвязного списка.в них в основном входят

Вставка узла

Вставка узла в двусвязном списке происходит следующим образом:1Выделить память под новый узел.2Записать в новый узел значение.3.В указатель на предыдущий узел записать адрес узла, который должен располагаться перед новым узлом.4.Записать в указатель на следующий узел адрес узла, который должен быть расположен после нового узла.

После этого уже не имеет значения, в каком узле (предыдущем или следующем) первым поменять значение адреса на адрес нового узла. 5В предыдущем узле заменяем значение указателя на следующий узел на адрес нового узла.6. В следующем узле заменяем значение указателя на предыдущий узел на адрес нового узла.

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

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

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

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

54. Перегрузка методов класса.

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

Когда одинаковые по смыслу операции применяются к операндам различных типов, их вынужденно приходится называть по-разному. Невозможность применять для разных типов функции с одним именем приводит к необходимости выдумывать различные имена для одного и того же, что создаёт путаницу, а может и приводить к ошибкам. Например, в классическом языке Си существует два варианта стандартной библиотечной функции нахождения модуля числа: abs() и fabs() — первый предназначен для целого аргумента, второй — для вещественного. Такое положение, в сочетании со слабым контролем типов Си, может привести к труднообнаруживаемой ошибке: если программист напишет в вычислении abs(x), где x — вещественная переменная, то некоторые компиляторы без предупреждений сгенерируют код, который будет преобразовывать x к целому путём отбрасывания дробной части и вычислять модуль от полученного целого числа!

55. Перегрузка операторов new и delete
Для перегрузки new следует использовать прототип функции вида: void * operator new(size_t size); В дальнейшем обращение к оператору new для выделения памяти объектам класса будут перенаправлены замещающей функции. Функция должна возвращать адрес памяти, выделенной объекту. Вместо кучи можно выделять память из статического буфера, на диске или другом запоминающем устройстве.
// Программа 6
#include <iostream.h>

class DemoNew {
private:
int x;
public:
DemoNew();
void * operator new(size_t size);
};
char buf[512];
int index;
void main()
{
cout << endl << “Creating local instance”;
DemoNew b1;
cout << endl << “Allocating space via new”;
DemoNew *b2 = new DemoNew;
DemoNew *b3 = new DemoNew;
DemoNew *b4 = new DemoNew;
DemoNew *b5 = new DemoNew;
}
DemoNew::DemoNew()
{
cout << endl << “Inside constructor”;
x = index;
}
void *DemoNew::operator new(size_t size)
{
cout << endl << “Inside overloaded new. Size == “<< size;
if ( index >=512 – sizeof(DemoNew)) //Проверка наличия
return 0; //пространства в buf
else {
int k = index;
index+= sizeof(DemoNew);
return &buf[k];
}
}
Оператор delete служит для удаления объектов, адресованных указателями. Прототип функции перегрузки оператора delete должен иметь вид: void operator delete(void *p); , где р ссылается на удаляемый объект.
void operator delete(void *p);
void DemoNew::operator delete(void *p)
{
cout << endl << “Deleting object at “<< p;
}
Поскольку объекты не запоминаются в куче, то перегру-женный оператор ничего не освобождает.

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

Ниже приведено определение класса, создающее класс string. Этот класс содержит один элемент данных, который представляет собой собственно символьную строку. Кроме того, этот класс содержит несколько различных методов и пока не определяет каких-либо операторов:

class string

{
public:
string(char *); // Конструктор
void str_append(char *);
void chr_minus(char);
void show_string(void);
private:
char data[256] ;
};

Как видите, класс определяет функцию str_append, которая добавляет указанные символы к содержимому строки класса. Аналогичным образом функция chr_minus - удаляет каждое вхождение указанного символа из строки класса.

57. Перегрузка оператора состоит в изменении смысла оператора (например, оператора плюс (+), который обычно в C++ используется для сложения) при использовании его с определенным классом. В данном уроке вы определите класс string и перегрузите операторы плюс и минус. Для объектов типа string оператор плюс будет добавлять указанные символы к текущему содержимому строки. Подобным образом оператор минус будет удалять каждое вхождение указанного символа из строки. К концу данного урока вы изучите следующие основные концепции:

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

· Для перегрузки операторов программы используют ключевое слово C++ operator.

· Переопределяя оператор, вы указываете функцию, которую C++ вызывает каждый раз, когда класс использует перегруженный оператор. Эта функция, в свою очередь, выполняет соответствующую операцию.

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

· C++ позволяет перегружать большинство операторов, за исключением четырех, перечисленных в таблице 24, которые программы не могут перегружать.

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

Перегрузка операций

В языке С++ определены множества операций над переменными стандартных типов, такие как +, -, *, / и т.д. Каждую операцию можно применить к операндам определенного типа.

К сожалению, лишь ограниченное число типов непосредственно поддерживается любым языком программирования. Например, С и С++ не позволяют выполнять операции с комплексными числами, матрицами, строками, множествами. Однако, все эти операции можно выполнить через классы в языке С++.

Рассмотрим пример.

Пусть заданы множества А и В:
А = { а1, а2, а3 };
В = { a3, a4, a5 },
и мы хотим выполнить операции объединения (+) и пересечения (*) множеств.

А + В = { a1, a2, a3, a4, a5 }
А * В = { a3 }.

Можно определить класс Set - "множество" и определить операции над объектами этого класса, выразив их с помощью знаков операций, которые уже есть в языке С++, например, + и *. В результате операции + и * можно будет использовать как и раньше, а также снабдить их дополнительными функциями (объединения и пересечения). Как определить, какую функцию должен выполнять оператор: старую или новую? Очень просто – по типу операндов. А как быть с приоритетом операций? Сохраняется определенный ранее приоритет операций. Для распространения действия операции на новые типы данных надо определить специальную функцию, называемую "операция-функция" (operator-function). Ее формат:

тип_возвр_значения operator знак_операции(специф_параметров)

{операторы_тела_функции}

При необходимости может добавляться и прототип:

тип_возвр_значения operator знак_операции(специф_параметров);

Если принять, что конструкция operator знак_операции есть имя некоторой функции, то прототип и определение операции-функции подобны прототипу и определению обычной функции языка С++. Определенная таким образом операция называется перегруженной (overload).

Чтобы была обеспечена явная связь с классом, операция-функция должна быть либо компонентом класса, либо она должна быть определена в классе как дружественная и у нее должен быть хотя бы один параметр типа класс (или ссылка на класс). Вызов операции-функции осуществляется так же, как и любой другой функции С++: operator @. Однако разрешается использовать сокращенную форму ее вызова: a @ b, где @ - знак операции.

Перегрузка для труктур

Приведем еще один пример, демонстрирующий перегрузку операций извлечения и вставки в поток, на этот раз для структуры:

struct info {

char *name;

double val;

char *units;

info(){

val=0;

name = new char [30];

units = new char [30];

name[0]=units[0]=0;

}};

ostream& operator << (ostream& s, info &m){ // Вывод info в s

s << m.name << " "<< m.val <<" "<< m.units<< "\n";

return s;}

Oперация >> может быть перегружена следующим образом:

istream& operator >> (istream& s, info &m){ // Ввод в info

s.width(30); s >> m.name;

char c;

while((c = s.get())!= ' ' && c!='\t' && c!='\n');

s.putback©;

s.width(30);

s >> m.val;

s.width(30);

s >> m.units;

return s;

}

Для считывания строки ввода, такой как "Resistance 300 Ohm", можно использовать следующую запись:

void main(){

clrscr();

info m;

cout<< "Введите наименование величины, ее значение \n";

cout<< " и единицу измерения (и нажмите Enter.):\n";

cin >> m; // Переопределенная операция >>

cout << m; // Переопределенная операция <<

}

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

Введите наименование величины, ее значение

и единицу измерения (и нажмите Enter.):

Resistance 300 Ohm

Resistance 300 Ohm [/spoiler]

60. Перегрузка функций позволяет вашим программам определять несколько функций с одним и тем же именем и типом возвращаемого значения. Например, следующая программа перегружает функцию с именем add_values. Первое определение функции складывает два значения типа int. Второе определение функции складывает три значения. В процессе компиляции C++ корректно определяет функцию, которую необходимо использовать:

#include <iostream.h>

int add_values(int a,int b){
return(a + b);
)

int add_values (int a, int b, int c)

(
return(a + b + c);
)

void main(void){
cout << "200 + 801 = " << add_values(200, 801) << endl;
cout << "100 + 201 + 700 = " << add_values(100, 201, 700) << endl;
}

Как видите, программа определяет две функции с именами add_values Первая функция складывает два значения типа int, в то время как вторая складывает три значения. Вы не обязаны что-либо предпринимать специально для того, чтобы предупредить компилятор о перегрузке, просто используйте ее. Компилятор разгадает, какую функцию следует использовать, основываясь на предлагаемых программой параметрах.

Шаблонные функции: Объявление:

template <class T> // или template <typname T>;

T max(T val1, T val2, T val3){

T max = val1;

if(val2 > max) max=val2;

if(val3 > max) max=val3;

return max; }

Использование:

int rez = max(1,10,3);

float rez = max(0.5,9.99,6.78);

Шаблоны и друзья:

friend void f1(); //друг любого класса

friend void f2(x<T> &); //друг конкретного класса

friend void A::f4(); //друг любого класса

friend void C<T>::f5(x<T> &); //друг конкретного класса

friend class Y; //класс Y дружественен любому классу

friend class Z<T>; //класс Y дружественен конкретному классу