WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 10 | 11 || 13 | 14 |   ...   | 17 |

отсутствие предопределенных операций присваивания массивов, выполнения над ними арифметических операций и т.д.

Создадим класс Array, являющийся формализацией концепции “одномерный массив целых“.

Для простоты предполагаем, что массив типа Array имеет тот же диапазон изменения индексов, что и обычный массив С++, а изменение его размера после создания невозможно.

Определим над типом Array операции присваивания, сложения и вывода. Чтобы обращаться к элементам такого массива, переопределим операцию [ ].

// Файл Array.cpp # include < iostream.h > # include < stdlib.h > class Array { int *pa; // Массив целых;

int sz; // размер массива.

public:

Array ( const Array &v );

Array ( const int a[ ], int s );

Array ( int s );

virtual ~Array ( ){ delete pa; } int size ( ) { return sz; } int & operator [ ] ( int );

Array & operator = ( Array& );

// Результат возвращается по ссылке для возможности // множественного присваивания типа a=b=c;

Array & operator + ( Array& );

ostream & print ( ostream& );

};

Array::Array (const int a[], int s ){ // Инициализация массива типа Array обычным массивом.

if ( s <= 0 ) { cout << “Неверный размер массива: “<< s <<“\n“;

exit (1);} if (!( pa = new int [ sz = s ] )){ cout<<“Неудача при выделении памяти \n“; exit (1); } for ( int i = 0; i

} Array::Array ( const Array &v ){ // Конструктор копирования.

if (!( pa = new int [ sz = v.sz ] )){ cout << “Неудача при выделении памяти \n“; exit(1);} for ( int i = 0; i < sz; i++) pa [ i ] = v.pa [ i ];

} Array::Array ( int s ){ // Создание неинициализированного массива размером s.

if ( s<= 0) { cout <<“Неверный размер массива \n“; exit(1); } if (!(pa = new int [ sz = s ] )) { cout <<“Неудача при выделении памяти \n“; exit (1); } } int & Array::operator [ ] ( int index ) { if ( index < 0 || index >= sz){ сout <<“Выход за границу массива!\n“; exit (1); } return pa[index];

} /* Так как результат возвращается по ссылке, то возвращается не значение элемента, а сам этот элемент и поэтому выражение вида с[i], где с – типа Array, может находиться в левой части операции присваивания. */ ostream & Array::print ( ostream& out) { out << ’\n’;

for ( int i = 0; i < sz; i++) out << pa[ i ]<<” ”;

out <<”\n”;

return out; } ostream & operator << ( ostream & out, Array & v ){ v.print ( out);

return out; } Array & Array::operator + ( Array & op2 ) { if ( sz != op.sz ){ cout << “Попытка сложить массивы разных размерностей!\n“;

exit (1);} Array & tmp = *( new Array (sz));

for ( int i = 0 ; i < sz ; i ++ ) tmp[ i ] = pa[ i ] + op2.pa[ i ];

return tmp;

} Array & Array::operator = ( Array &v ){ if ( sz !=.sz ) { cout <<”Разные размеры массивов при присваивании!\n”; exit (1);} for ( int i = 0; i < sz ; i ++ ) pa[ i ] = v[ i ];

return ( *this );

} // Конец файла Array.cpp.

Теперь можно написать следующую программу:

# include “Array.cpp“ void main ( ){ int a [ ] = { 1, 7, 3, 15, 6, 20, 7 };

Array mas (a, sizeof a / sizeof (int));

Array b (7); // Неопределенный массив.

Array c = mas; // Конструктор копирования.

b = mas + c ;

mas = b + ( c = mas );

for ( int i=0; i < 7; i ++)cout << a[i] << “ “; cout << “\n“;

cout << mas << b << c; // Сравните эти два вывода! } Создадим теперь класс Matrix, являющийся формализацией концепции двумерного массива.

// Файл matrix.cpp class Matrix { Array **pm; // Массив указателей на Array.

int r, c; // Размерности матрицы.

public:

Matrix ( int, int );

virtual ~Matrix ( );

int row( ) { return r;} int col ( ) { return c;} Array & operator [ ] (int);

Matrix & operator = (Matrix&);

Matrix & operator + (Matrix&);

Matrix & operator * (Matrix&);

ostream & print (ostream & s);

};

// Результатом операции [ ], примененной к объекту типа Matrix, // должен быть объект типа Array:

Array & Matrix::operator [ ] ( int index ){ if ( index < 0 || index >= r ) { cout << " Выход за границу массива ! \n"; exit (1);} return * pm [index];

} // Конструктор:

Matrix::Matrix (int row, int col ){ pm = new Array * [ row ];

for (int i = 0; i < row; i ++ ) pm [ i ] = new Array (col);

r = row; c = col;

} Matrix:: ~Matrix (){for ( int i = 0; i

for ( int i =0; i < r; i++ ){ Array &v = *pm [ i ];

for ( int j = 0; j < c; j++ ) s << v [ j ] <<“ “;

s << “\n“; } return s ;

} Matrix & Matrix::operator = ( Matrix & tmp ) { if ( r != tmp.r ) { cout << “Разные размеры массивов!\n“; exit (1); } for ( int i = 0; i < r; i++ ) *pm [ i ] = tmp [ i ];

return *this;

} Matrix & Matrix::operator + ( Matrix & op2 ){ if ( r != op2.r ) { cout << “Разные размеры массивов!\n“; exit (1); } Matrix & tmp = *( new Matrix ( r, c ));

for ( int i = 0; i < r ; i++ ) tmp [ i ] = *pm[ i ] + op2[ i ];

return tmp;

} Matrix & Matrix::operator *( Matrix & op2 ) { if ( c != op2.r ) { cout << “Нельзя перемножить матрицы!\n“; exit (1);} Matrix & tmp = *( new Matrix ( r, op2.c));

for ( int i = 0; i < r ; i++ ) for ( int j = 0; j

for ( int k = 0; k < c ; k++ ) tmp [ i ][ j ]+=(*this)[ i ][ k ]*op2[k ][ j ];

} return tmp;} ostream & operator << ( ostream &s, Matrix & m ){ m.print ( s );



return s;} // Конец файла Matrix.cpp Теперь можно написать программу, в которой используются новые типы данных Array и Matrix.

#include < iostream.h > #include “array.cpp“ #include “matrix.cpp“ void main ( ){ Matrix tbl ( 3, 5), tbl2( 3, 5 );

for ( int i = 0; i < 3; i++ ) for ( int j = 0; j < 5; j++ ) { tbl[ i ][ j ] = i + j;

tbl2[ i ][ j ] = ( i + j )*10;

} Matrix tbl3 = tbl + tbl2;

cout << tbl3;

Array arr (10), arr2 (10);

for ( i = 0; i < 10; i++ ) { arr[i] = i; arr2[i] = i*10; } Array arr3 = arr + arr2;

cout << arr3;

Matrix mas ( 5, arr.size ());

for ( i = 0; i < 5; i++ ) mas[i] = arr;

Matrix mas2 ( 3, arr.size ());

mas2 = tbl*mas;

cout << mas << mas2;} 23. Классы и шаблоны Шаблон семейства классов определяет способ построения отдельных классов подобно тому, как класс определяет правила построения и формат отдельных объектов. Шаблон семейства классов определяется так:

template < список параметров шаблона > определение класса В определении класса, входящего в шаблон, особую роль играет имя класса. Оно является не именем отдельного класса, а параметризованным именем семейства классов.

Определение шаблона может быть только глобальным.

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

// Файл vec.cpp template < class T > // Т – параметр шаблона;

class vector { T *pv; // одномерный массив;

int size; // размер массива.

public:

vector ( int );

~vector ( ) { delete []pv; } T & operator [ ] ( int i ) { return pv [ i ]; }...

};

template < class T > vector < T >::vector ( int n ){ pv = new T[n];

size = n;

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

имя параметризованного класса < фактические параметры шаблона > имя объекта (параметры конструктора).

В нашем случае определить вектор, имеющий 100 компонент типа double, можно так:

vector < double > x ( 100 );

Программа может выглядеть так:

#include < iostream.h > #include “vec.cpp“ void main ( ){ vector < int > x ( 5 );

vector < char > c( 5 );

for ( int i = 0; i < 5; i++ ){ x [ i ] = i; c [ i ] = ’A’ + i;} for ( i = 0; i < 5; i++ ) cout << “ “ << x [ i ] << “ “ << c [ i ];

cout << “/n“;

} Результат:

0 A 1 B 2 C 3 D 4 E В списке параметров шаблона могут присутствовать формальные переменные, не определяющие тип. Точнее, это параметры, для которых тип фиксирован:

template < class T, int size = 64 > class row { T * data;

int length;

public: row ( ) { length = size; data = new T [ size]; } ~row ( ) { delete T[] data; } T & operator [ ] ( int i ) { return data [i]; } };

void main ( ){ row < float, 7 > rf;

row < int, 7 > ri;

for ( int i = 0; i < 7; i++ ){ rf[i] = i ; ri[i] = i * i; } for ( i = 0; i < 8; i++ ) cout << “ “ << rf[i] << “ “ << ri[i];

cout << “\n“;

} Результат:

0 0 1 1 2 4 3 9 4 16 5 25 6 В качестве фактического аргумента для параметра size взята константа. В общем случае может быть использовано константное выражение, однако использовать выражения, содержащие переменные, нельзя.

24. Списки Рассмотрим структуру typedef int ETYPE;

struct elem { ETYPE data;

elem *next;

};

Назовем data – информационным элементом. У нас он – типа int, но может быть любого сложного необходимого нам типа ETYPE.

Указатель next указывает на объект типа elem. Объекты типа elem можно упорядочить с помощью указателя next следующим образом (рис. 2):

d a ta d a ta d a ta N U L L … Рис. 2. Структура односвязного списка Такая структура данных называется однонаправленным, или односвязным списком, иногда – цепочкой.

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

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

Рассмотрим методы работы с такими списками.

Пусть переменные p, q имеют тип elem*:

elem *p, *q;

Построим список из двух элементов, содержащих числа 12 и –8.

Значением переменной p всегда будет указатель на первый элемент уже построенной части списка. Переменная q будет использоваться для выделения с помощью new места в памяти под размещение новых элементов списка.

Выполнение оператора p = NULL;

приводит к созданию пустого списка. После выполнения операторов q = new elem; q->data = –8; q->next = p; p = q;

имеем список, состоящий из одного элемента, содержащего число –8 в информационной части. Переменные p, q указывают на этот элемент (рис. 3а):





p NULL -NULL q Рис. 3. Создание списка а) из одного элемента (сплошные линии);

б) из двух элементов (пунктир) Далее, выполнение операторов (рис. 3б) q = new elem; q->data = 12; q->next = p; p = q;

приводит к тому, что в начало цепочки добавляется новый элемент, одержащий число 12. В результате получится список, изображенный на рис. 4. Значением переменных p и q снова является указатель на первый элемент списка:

p 12 - NULL q Рис. 4. Список из двух элементов Фактически мы рассмотрели операцию включения нового элемента в начало, или голову списка, а формирование списка состоит в том, что начинают с пустого списка и последовательно добавляют в начало элементы.

Пример:

Построим список, элементы которого содержат целые числа 1, 2, 3,..., n.

p = NULL;

while ( n > 0 ){ q = new elem;

q->data = n; q->next = p; p = q ;

n – –;} Заметим, что при включении элемента в голову списка порядок элементов в списке обратен порядку их включения.

Основная операция при работе со списком – это проход по списку.

Предположим, что с каждым информационным элементом звена нужно выполнить некоторую операцию, которая реализуется функцией void P(ETYPE). Пусть также опять p указывает на начало списка. Тогда проход по списку осуществляется так:

q = p;

while (q) { P ( q->data );

q = q->next; } Пример. Во входном файле num.txt находится последовательность, содержащая нечетное количество целых чисел.

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

#include < fstream.h > // Для работы с файлом ввода.

#include < stdlib.h > struct elem { int data;

elem *next; };

void main ( ){ ifstream infile ( “num.txt“ );

/* Создается входной поток с именем infile для чтения данных, разыскивается файл с именем “num.txt“; если такой файл не существует, то конструктор завершает работу аварийно и возвращает для infile нулевое значение.

*/ if ( !infile ) { cout << “Ошибка при открытии файла num.txt!\n“; exit (1); } elem *p = NULL, *q;

int j = 0;

while ( infile.peek() != EOF ) { /* Функция-член peek() класса ifstream возвращает очередной символ из входного потока infile, фактически не извлекая его оттуда.

Если встретится конец файла, то будет возвращено значение EOF, то есть -1. */ q = new elem;

infile >> q->data;

q->next = p; p = q;

j ++;

} for ( int i = 1; i <= j/2; i++ ) q = q->next;

cout << q->data << “\n“;

} 24.1. Операции над односвязными списками Основных операций над списками – три.

1) Проход по списку, или переход от элемента к следующему.

Как мы уже рассмотрели, это осуществляется с помощью присвоения типа q = q -> next;

2) Включение в список.

Пусть q, r – переменные типа elem*.

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

Такое включение осуществляется следующими операторами:

r = new elem; r->data = 19;

r->next = q->next; q->next = r;

Проиллюстрируем это на рис. 5.

Рис. 5. Включение элемента в список 3) Исключение из списка.

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

r = q->next;

q->next = q->next->next;

r->next = NULL;

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

Третье присваивание выполняется для того, чтобы сделать исключение окончательным, т.е. чтобы из исключенного элемента нельзя было бы попасть в список, из которого он исключен.

Реализация списка Реализуем понятие списка через механизм классов.

// Файл ”list.cpp” #include < iostream.h > #include < stdlib.h > typedef int ETYPE;

struct elem { ETYPE data;

elem * next;

elem ( ETYPE e, elem * n ) { data = e; next = n;} };

class list { elem *h; // Адрес начала списка.

public:

list ( ) { h = NULL; } ~list ( ) {release ( ); } void create ( ETYPE ); // Добавляет элемент в начало списка.

void release ( ); // Удаляет список.

void insert (elem* q, ETYPE c); // Вставляет в список с после q.

void del0 ( ) { // Удаляет первый элемент.

elem *t = h; h = h->next; delete t;} void del ( elem * q ); // Удаляет элемент после q.

void print ( ); // Распечатывает список.

friend class iter;

elem *first ( ) { return h; } };

class iter { elem * current;

public:

iter ( list & l ) { current = l.h; } elem * operator ++ ( ); // Продвижение по списку.

};

void list::create ( ETYPE c ){ h = new elem ( с, h ); } void list::insert ( elem *q, ETYPE c ){ q->next = new elem ( c, q->next );} void list::del ( elem *q ){ if ( q->next = = NULL ){ cout << ”Конец списка! ”<< ”Удаление следующего элемента невозможно!\n”; exit (1); } elem * r = q->next; q-> next = q->next->next;

r->next = NULL;

Pages:     | 1 |   ...   | 10 | 11 || 13 | 14 |   ...   | 17 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.