Матрицы и векторы.

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

Задачи для проверки:

2.1. Заполнить матрицу символами по алфавиту.

2.2. Задана матрица 10*10, получить из нее матрицу размерности 8*8, путем вычеркивания первой и последней строки, первого и последнего столбца.

2.3. Найти в матрице элементы сумма индексов, которых четна, и заменить их нулем.

3. Геометрические задачи.

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

Задачи для проверки:

3.1. Задано 5 точек, определить периметр фигуры.

3.2. Проверить попадает ли произвольная точка в область, заданную пересечением круга с радиусом r и центром в начале координат и полуплоскости y>0.

4. Строки.

Уметь выделить слово, сосчитать его длину, сравнивать символы.

Задачи для проверки:

4.1. Сравнить первое и последнее слово строки.

4.1. Проверить является ли первое слово обращением последнего в заданной строке.

 

 

СЛОЖНЫЕ СТРУКТУРЫ ДАННЫХ.

 

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

Рассмотрим каждый из этих объектов и их программную реализацию.

 

ГРАФ.

 

Граф – это пара ( V, E), где V={ 1,2,3,4,5 } – множество вершин, а E={ (1,2),(2,3),(2,5),(2,4),(5,4) }

Множество неупорядоченных пар вершин из Е, называемых ребрами.

 

 

 


Граф может быть ориентированным, тогда пары вершин упорядочены и называются дугами.

 

 

 

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

 

Матрица смежности показывает связи между вершинами.

Наличие пути от вершины к вершине обозначается 1 либо весом ребра. В нашем примере – второе.

 

#
# 7 #
# # #
# #
# # # #

# - отсутствие пути

Матрица смежности не ориентированного графа симметрична.

Матрица инцидентности показывает связи между вершинами и ребрами(дугами).

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

 

 
# # # # #
# # # # # #
# # # # # # #
# # # # # #
# # # # # # # #

 

 

СТРУКТУРЫ.

 

Моделирование других объектов требует введения специального понятия – структура.

Структура – именованная структура данных, способная объединять объекты различных типов, каждый такой объект называется полем структуры.

Рассмотрим работу со структурой на примере. Нужно составить базу данных по результатам сессии.

 

фамилия баллы
Иванов 3 4 5 2
Петров 4 4 3 3
   

 

Сформируем шаблон структуры.

Назовем нашу структуру – stud.

struct stud { int n ; // описание первого поля структуры – номер по списку.

char name [10] ; // описание второго поля – фамилия.

int ball [4] ; // описание третьего поля – оценки.

}

Описание переменных типа stud. В разных версиях языка возможны два варианта, с использованием ключевого слова struct и без него.

struc stud a, b, c ;

stud a, b, c ;

 

Инициализация структуры.

stud a={ 1, “ Абрамов “, 3, 4, 5, 5 } ;

 

Заполнять структуру можно явно или вводить с экрана.

a.n = 1 ;

a.ball[0]= 3 ; // явное заполнение оценок.

a.ball[1]= 4 ;

a.ball[2]= 5 ;

a.ball[3]= 5 ;

gets( a..name ) ; // ввод с экрана фамилии.

 

Можно задать массив структур, т.е. список группы.

stud spis [25] ;

 

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

for ( i=0 ; i<25 ; i++ )

{

spis[i].n = i+1 ;

printf (“ \n введите фамилию “ ) ;

gets ( spis[i].name ) ;

printf (“ \n введите оценки“ ) ;

for ( k=0 ; k<4 ; k++)

scanf( “ %d”, &spis[i].ball[k]) ;

}

Переставим местами фамилии 5-го и 10-го студента. Фрагмент программы будет выглядеть так.

char x ;

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

{

x = spis[5].name[i] ;

spis[5].name[i]= spis[10].name[i] ;

spis[10].name[i] = x ;

}

 

Главные задачи с использованием структур – это задачи сортировки и поиска. Структуры являются основным «кирпичиком» формирования баз данных.

Иногда с использованием структур можно элегантно решать и простые задачи.

Сосчитать число дней от начала года до текущего. Обычно такая задача решается с использованием оператора case.

struc mouth { int n ; int k } // n – номер месяца, k – число дней в нем.

int sum, ch, mm ;

struc mouth m[12] = {1, 31, 2, 28, 3, 31 … 12, 31} ;

scanf( “%d”, &ch) ; // ввод текущей даты, ch – число, mm – месяц.

scanf( “%d”, &mm) ;

for ( i=0 , sum=0 ; i<mm-2 ; i++0

sum+= m[i].k ; // количество дней во всех месяцах до текущего

sum+= ch ;

printf ( “ %d”, sum) ;

 

 

СЛОЖНЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ.

 

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

 

СТЕК.

 

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

 

 

Адрес информация

Следующего

Верхушка стека

 

 

 

 

Пустая ссылка

Операции, определенные над стеком:

1. Если стек пуст, то создать его.

2. Добавить в стек, только наверх.

3. Извлечь из стека, если не пуст, только верхушку.

4. Ходить по стеку, иcкать, проверять внутри его – нельзя!

 

Рассмотрим задачу – создать стек и удалить из него все символы до «а».

struct st { char n ; // описание элемента стека как записи с 2 полями, информационным - n

st *next ; // и адресным – next.

}

main ()

{

st *ps, *pp=NULL ; // описание переменных указывающих на элемент стека.

char c ; // NULL – пустая ссылка, адрес.

do

{ ps= new st ; // создание новой записи ( элемента стека)

printf ( “ \n, введите информационный элемент стека “) ;

scanf ( “%c”, &c) ;

// заполнение полей записи

(*ps).n=c ; // можно эту операцию записать иначе ps->n=c ;

(*ps).next=pp ;

pp=ps ; // делаем эту запись предыдущей.

printf ( “\n, будите продолжать ? ( да=1) “) ;

}

while( getch()==’1’) ;

printf (“\n, верхушка стека %c”, (*pp).n) ;

// удаление всех символов до ‘a’.

w hile(((*ps).n!=’a’)&&((*ps).next!=NULL))

{ pp=(*ps).next ;

delete ps ;

ps=pp ;

}

printf(‘\n верхушка стека после удаления %c”, (*pp).n) ;

}

 

ОЧЕРЕДЬ.

Очереди используются при создании компиляторов, а также при обслуживании супер ЭВМ, где одновременно выполняются много программ. Очереди бывают обычные и преоритетные.

Очередь формируется и работает по принципу – первый пришел, первый ушел. Ставим очередной элемент в «хвост» очереди, а вынимаем из «головы».

 

Адрес информация

Следующего

хвост

 

 

 

голова

Пустая ссылка

Операции, определенные над очередью:

1. Если пустая, то создать очередь.

2. Добавить в очередь, т.е. в «хвост».

3. Извлечь из очереди, т.е. из «головы», если очередь не пуста.

4. Ходить по очереди, искать проверять в ней – нельзя!

 

Практические принципы работы с очередью такие же, как со стеком. Измените предыдущую программу, так чтобы она создавала очередь и извлекала из нее все элементы до «а».

 

 

ЛИНЕЙНЫЕ СПИСКИ.

 

Линейные списки широко используются при работе с БД (базами данных). Так же как стеки и очереди не требуют определения объема памяти. Списки бывают односвязные и двухсвязные.

 

ОДНОСВЯЗНЫЙ СПИСОК. ДВУХСЯЗНЫЙ СПИСОК

 

Адрес информация информация

Следующего

 

 

 

 

Пустая ссылка

 

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

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

 

Операции, определенные для списков:

1. Если пуст, то создать список.

2. Поиск в списке элемента.

3. Вставка в список элемента.

4. Удаление из списка элемента, если не пуст.

5. Только для односвязного определена операция – инвертирования списка, т.е. изменение направления адресных ссылок на противоположные.

 

Опишем структуру двухсвязного списка и создадим два первых его элемента.

struct spis {

char text [10] ;

spis *pred ;

spis *next ;

}

 

main ()

{ spis * ps, *pm ;

// создание и заполнение первого элемента.

ps = new spis ;

ps->pred=NULL ;

ps->next=NULL ;

gets ( ps->text) ;

// создание и заполнение второго элемента, и установление связей между ними.

pm = new spis ;

pm->pred = ps ;

pm->next =NULL ;

ps->next= pm ;

gets (pm->text ) ;

}

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

 

Все эти представления динамических структур – цепные. Существует и более устаревший вариант – сплошное представление динамических структур, т.е. моделирование списков через вектора. Таким образом, работали со списками на языке FORTRAN. В этом случае теряется главное достоинство динамических структур – произвольный объем памяти.

 

 

ДЕРЕВЬЯ.

 

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

считать их как ориентированными так и не ориентированными.

корень

лист поддерево

 

Операции, определенные для деревьев:

1. Если дерево пустое, то создать.

2. Обход дерева, т.е. попасть в каждую вершину, так чтобы они не повторялись. Поиск в нем.

3. Вставка вершины (поддерева).

4. Удаление поддерева, если оно не пусто.

 

Пример обхода дерева в порядке КЛП ( корень- левое поддерево – правое поддерево).

 

Цифры определяют порядок обхода.

Очевидно, что осуществить такой обход довольно трудно. Это, как правило, рекурсивная функция.

Опишем структуру дерева.

struct tree

{ char inf [10] ;

tree * left ;

tree *right ;

}

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

 

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

 

С++ И ЕГО НОВЫЕ ВОЗМОЖНОСТИ.

 

ВВОД И ВЫВОД.

 

С++ предполагает другие возможности ввода-вывода через входной поток с именем сin, и выходной поток с именем cout.

#include<iostream.h>

main()

{ cout << “ введите n “ << endl ; // переход на следующую строку.

cin >> n ;

cout << “ результат =” << n*n ;

}

Можно перенаправить входной и выходной поток в файлы.

 

ПЕРЕГРУЗКА ФУНКЦИЙ.

 

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

int max (int , int) ;

float max ( float , float) ;

main()

{ int m,n ;

float a, b ;

cin >> m>> n>>a >>b ;

cout << “максимальное целое “ << max(m, n) ;

cout << “максимальное вещественное “ << max(a, b) ;

}

int max ( int m, int n ) // функция определяющая наибольшее из 2 целых чисел.

{ if (m>=n) return m ;

else return n ;

}

float max ( float a, float b ) // функция определяющая наибольшее из 2 вещественных чисел.

{ if (a>=b) return a ;

else return b ;

}

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

 

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

 

 

gets (text) ;

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

cout << lst( text) ;

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

cout << lst( “ fjfhgjkkljll;;;njvh”) ;

int lst ( char *t)

{ for (i=0 ; *(t+i)!=’\0’ ; i++) ; return i ; }

int lst ( char tt[])

{ for (i=0 ; tt[i]!=’\0’ ; i++) ; return i ; }

Перегрузка функций очень активно используется при работе с классами.

 

УКАЗАНИЕ ПАРАМЕТРОВ ФУНКЦИИ ПО УМОЛЧАНИЮ.

 

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

Например:

int fun(int a=10, int b=5)

{ return a+b ; }

main()

{ int x=1 , y=2 ;

cout << fun() ; // распечатается 15

cout << fun(x) ; // распечатается 6

cout << fun(x , y) ; // распечатается 3

}

Примечание: опускать только первый параметр нельзя.

 

С++ обладает и многими другими интересными возможностями, о которых, по мере необходимости, можно узнать из литературы.

 

 

КЛАССЫ.

 

С++ дает возможность определять новые типы, так что их использование не будет отличаться от использования встроенных (стандартных) типов.

int a=10 , b=20 , c ;

c=a+b ;

cout << c ;

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

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

 

class cmatr /* заголовок класса

имя класса

дальше в скобках тело класса */

{

определение объектов, необходимых данных;

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

}

 

Начнем заполнение класса, не раскрывая пока его методы.

сlass cmatr { // объекты

float **m ; // адрес матрицы

int n, k ;// ее размерности

public :// методы

cmatr (int n , int k) // конструктор

{ распределение памяти на матрицу} ;

cmatr (float **m, int n, int k) // конструктор

{ распределение памяти и инициализация матрицы } ;

~cmatr() // деструктор

{ очистка памяти } ;

float det ( void ) // вычисление определителя

{ тело функциии, реализующей вычисление определителя } ;

cmatr operator = (cmatr &x) // функция оператор присваивания матриц

{ тело функциии, реализующей присваивание матриц } ;

cmatr operator + (cmatr &x) // функция оператор сложения матриц

{ тело функциии, реализующей сложение матриц } ;

void print ( void ) // печать матрицы

{ тело функциии, реализующей печать матрицы } ;

}

 

Теперь рассмотрим, как работать с классом.

main ()

{ float x[5][3]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} ,

y[5][3]={15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} ;

cmatr A(x, 5, 3), B(y, 5, 3), C(5, 3), D(x, 3, 3) ;// оператор описания объектов типа cmatr

C=A+B ; // сложение матриц

C.print() ; // печать матрицы С

сout << “определитель матрицы=” << D.det() ; //вычисление и печать определителя матицы D

~cmatr() ;

}

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

 

ОПРЕДЕЛЕНИЕ МЕТОДОВ ВНЕ КЛАССА.

 

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

 

class cmatr {

float **m ;

int n, k ;

public : // декларации методов

cmatr( int , int ) ;

cmatr( float **, int , int ) ;

~cmatr() ;

float det(void) ;

cmatr operator = ( cmatr &) ;

cmatr operator + ( cmatr &) ;

void print (void) ;

}

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

Тип результата имя класса::имя_метода_класса( параметры)

{ тело метода }

Например:

сmatr::cmatr ( int n, int k)

{ распределение памяти }

float cmatr::det( void)

{ вычисление определителя}

 

ЧАСТНЫЕ И ОБЩИЕ ДАННЫЕ.

 

private – частные данные,

public – общие.

Методы всегда общие, т.к. они должны быть доступны всем, а вот объекты могут быть и общие и частные. По умолчанию всегда берется –private,пока его не изменят на publicявно.

Вернемся к программе с классом cmatr, данные в ней –private, а методы- public. Нигде внутри main() мы не можем изменить значения объектов m, n, k, не можем присвоить им что-либо или достать их. Все наши действия только через методы (функции). Таким образом, работает принцип инкапсуляции – сокрытия информации. Класс для пользователя – «черный ящик», он не может изменять данные, не знает, как работают методы, он только представляет какой будет результат.

Программа предоставляет пользователю минимальную информацию.

Если бы объекты класса cmatr были описаны так, как это сделано ниже, то можно было бы обойтись без конструктора и в любой момент достать любой из объектов класса.

class cmatr {

public: float **m ;

int n, k ;

}

main()

{

cmatr A ;

A.m[1][1]=1 ;

A.n=5 ;

A.k=3 ;

}

Для обращения к общим данным используется оператор «точка».

В этом случае информация стала доступной из вне, и в любом месте программы можно как угодно изменять объекты класса. Практически мы пришли к работе со структурой struct. Нет смысла строить сложную закрытую структуру класса, если все можно сделать из main(). Иногда часть объектов делают общими часть частными.

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

 

 

КОНСТРУКТОР.

 

Для наглядности и упрощения процесса инициализации данных используется специальная функция – конструктор. Может ли быть класс без конструктора? – Да, но всегда будет функция выполняющая его назначение.

Конструктор – это специальная функция, которая имеет такое же имя как класс, производит

- распределение памяти и инициализацию данных (объектов класса).

- не объявляется как void, не имеет возвращаемого значения.

- каждый раз, когда main() создает переменную класса, вызывается конструктор.

Рассмотрим пример конструктора для класса векторов.

 

 

class cvec { // объекты класса

int *m ; // адрес вектора

int k ; // его размер

// методы

public: cvec( int ) ; // конструктор

}

cvec::cvec ( int d)

{ k=d ;

m=(int *)malloc(k*sizeof(int)) ; или иначе m= new int[k] ;

}

функция malloc или операция new распределяют память на вектор размерности k, но не заполняют его.

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

cvec::cvec ( int *x, int d)

{ k=d ;

m=(int *)malloc(k*sizeof(int)) ;

for (int i=0 ; i<k ; i++) // заполнение вектора.

*(m+i)=*(x+i) ;

}

При создании конструктора часто бывает удобно использовать параметры по умолчанию, например.

cc::cc (int a=10, int b=20)

{ … }

main()

{ cc x() , y(1, 2) ;

}

При создании объектов х будет использовать параметры по умолчанию 10 и 20, а у будет создаваться, используя параметры 1 и 2.

 

ДЕСТРУКТОР.

 

 

Деструктор – специальная функция, которая очищает память, используя специальную

операцию delete для очистки памяти, распределенной new,функцию free для очистки

памяти, распределенной malloc.

- имеет такое же имя как класс, со специальным символом ~ «тильда».

- не имеет возвращаемого значения и параметров, не объявляется как void.

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

~cvec::cvec ( )

{ delete m ; }

 

ПРИМЕР КЛАССА ОТРЕЗОК.

 

#include<conio.h>

#include<math.h>

#include<graphics.h>

class cline

{ // объекты

int x1, y1 ;

int x2, y2 ;

float len ;

public: cline(int, int, int, int) ; // методы

void draw() ;

void extend (int) ;

int getlen() { return len ;}

}

// конструктор

cline::cline ( int a, int b, int c, int d)

{ x1=a ; y1=b ; x2=c ; y2=d ;

int dx = x2-x1 ;

int dy = y2-y1 ;

len= sqrt(dx*dx + dy*dy) ;

}

// удлинение отрезка

void cline::extend ( int d)

{ int dx = x2-x1 ;

int dy = y2-y1 ;

float cx = dx / len ;

float cy = dy / len ;

len = len + d ;

dx = len *cx ;

dy = len *cy ;

x2 = x1 + dx ;

y2 = y1 + dy ;

}

// рисование отрезка

void cline::draw ()

{ line(x1, y1, x2, y2) ; }

// работа с классом

main()

{

cline L(100, 100, 200, 200) ; // создание отрезка с указанными координатами

 

int gdriver=DETECT, gmode ;

initgraph (&gdriver, &gmode, “”) ;

 

L.draw() ; // рисование отрезка

getch() ;

L.extend ( L.getlen() + 50) ; // удлинение его на 50

L.draw () ; // рисование удлиненного отрезка

getch() ;

closegraph() ;

}

 

ПЕРЕГРУЗКА ОПЕРАТОРОВ.

 

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

Вернемся к классу матриц, перегрузим для него операцию присваивания, в main() вызов этой функции будет выглядеть так С = А ; где А и С матрицы.

 

void operator = ( cmatr &a)

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

for ( int j=0 ;j<=k ; j++ )

m[i][j] = a.m [i][j] ;

}

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

 

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

x = t ; // для целых

C = A ; // для матриц

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

C.pr(A) ; вместо C = A ;

Перегрузка операторов упрощает понимание программ.

Описание функции, перегружающей оператор, выглядит так:

Тип_результата имя_класса::operator знак_оператора ( параметры)

{ тело функции }

С++ позволяет перегружать все операторы кроме:

 

Знак оператора Назначение Пример
. Выбор элемента a.m[i]
.* указатель (*pp).next
:: Глобальное разрешение class::cvec
?: Условный оператор сравнения c=( a>b) ? a : b
# Описание библиотеки #include<math.h>

 

Рассмотрим еще один пример перегрузки оператора для класса строка: задана строка выбросить из нее любой заданный символ. Создавать весь класс мы не будем, определим только объекты и функцию перегрузки оператора ( минус).

class string {

char *text ;

int len ;

public: …

}

void string::operator – ( char ll) // подпрограмма удалений из строки всех вхождений символа ll.

{ int i, j ;

for ( i=0 ; i<len ; i++)

if ( text[i]==ll )

{

for ( j=i+1 ; j<len ; j++ )

text[j-1] = text[j] ;

len -- ;

text[len] = NULL ;

}

}

main()

{ string data(“ любые слова “) ;

data = data – ‘a’ ;

}

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

 

НЕЯВНЫЙ УКАЗАТЕЛЬ *this.

 

Каждый объект класса имеет свою копию член-данных, например копию объектов А и С.

cmatr A(x, 5, 3) , C(5, 3) ;

А член-функции (методы) существуют только в одном экземпляре.

A.func() ; C.func() ;

Как же функция разбирается с данными какого объекта ей надо работать?

Установка соответствия член-данного и функции осуществляется при помощи неявного указателя this. При вызове функции ей передается неявный аргумент, который обозначает конкретный объект класса.

A.func() ;

Функции func() передается указатель на объект А, this - адрес А . Использовать this явно нет необходимости в большинстве случаев он нужен тогда, когда мы работаем с указателем на объект.

 

Пример функции возвращающей адрес текущего объекта.

cmatr cmatr:: operator = (cmatr &a)

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

for ( int j=0 ; j<k ; j++)

this->m[i][j]=a.m[i][j] ;

return (*this) ;

}

 

ДРУЖЕСТВЕННЫЕ ФУНКЦИИ.

 

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

 

void ff ( int a, int b)

{ … } ;

class cmatr {

float **m ; // объекты класса

int n, k ;

friend void ff ( int, int) ; // декларация дружественной функции.

public : … // методы класса

}

 

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

Мы подобрались к очень важной и серьезной теме – взаимодействие классов, построение одного класса из другого. Это будет рассмотрено в теме – Наследование, а перед ней еще один пример класса.

 

КЛАСС МНОЖЕСТВО.

 

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

 

include<conio.h>

include<stdio.h>

include<stdlib.h>

// класс целочисленное множество х из len элементов

class cset {

int *x ; // объекты

int len ;

public: cset () ; // методы

cset (int *, int ) ;

int In ( int ) ;

int Get (int num) { return x[num] ; } // выдача элемента

int Getslen () { return len ; } // количество элементов во множестве

void Put ( int n, int i) { *(x+i) = n ; } // положить элемент во множество

cset operator = ( cset &) ;

cset operator ^ ( cset &) ;

}

 

cset::cset () // конструктор пустого множества

{ len =10 ;

x = (int*) malloc ( len*sizeof( int)) ;

for ( int i=0 ; i<len ; i++)

*(x+i) = ‘\0’ ;

}

cset::cset ( int *y, int d ) // конструктор произвольного множества из d элементов

{ len =d ;

x = (int*) malloc ( len*sizeof( int)) ;

for ( int i=0 ; i<len ; i++)

*(x+i) = *(y+i) ;

}

int cset::In( int a ) // проверка принадлежности элемента а множеству

{ int i, p = 0 ;

for ( i=0 ; i<len ; i++)

if ( *(x+i) == a ) p = 1 ;

return p ;

}

cset cset::operator = ( cset &s) // перегрузка оператора присваивания

{ for ( int i=0 ; i<s.len ; i++)

(*this).x.[i] = s.x[i] ;

(*this).len = s.len ;

return (*this) ;

}

cset cset::operator ^ ( cset &s) // создание оператора пересечения множеств

{ int *sa = (int *) malloc ((*this).Getslen()*sizeof(int)) ;

int d = 0, n ;

for ( int i = 0 ; i<(*this).Getslen() ; i++)

{ n = (*this).Get(i) ;

if ( s.In (n) )

{ *(sa+d) = n ;

d++ ;

}

}

cset st ( sa, d ) ;

return st ;

}

main() // создание двух множеств s1 и s2 и нахождение их пересечения множества r

{ int sx1[] ={1, 2, 3, 4, 5} ;

int sx2[] ={2, 3, 4, 5, 6} ;

cset s1(sx1, 5) ;

cset s2(sx2, 5) ;

cset r = s1^s2 ;

for ( int i=0 ; i<r.Getsln() ;i++) // поэлементное распечатывание r

printf ( “\n%d “< r.Get( i) ) ;

getch() ;

}

 

НАСЛЕДОВАНИЕ.

 

 

Цель объектно-ориентированного программирования состоит в повторном использовании созданных классов. Это экономит время и силы.

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

Наследование – возможность на основании существующих типов порождать новые.

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

Построение такой иерархии классов осуществляется при помощи данных, доступных потомку, ключевое слово – protected, что обеспечивает доступ производного класса к объектам базового.

Рассмотрим пример наследования на классах отрезок и многоугольник. Базовый класс отрезок ничем не будет отличаться от созданного нами ранее за исключением определения его объектов как protected.Создадим новый класс.

class cline {

protected : int x1, y1, x2, y2 ;

public : …

}

class cmanyline: public: cline // класс многоугольник

{

private : int n ; // объекты

int x[10][2] ;

// методы

public : cmanyline ( int r, int y[][2]) // конструктор многоугольника

{ n=k ;

for ( int i=0 ; i<n ; i++)

for ( int j=0 ; j<2 ; j++)

x[i][j] = y[i][j] ;

for ( int d=0 ; d<n-1 ; d++)

cline ( x[d][0], x[d][1], x[d+1][0], x[d+1][1]) ; // использует конструктор

// отрезка (базового класса)

cline ( x[n-1][0], x[n-1][1], x[0][0], x[0][1]) ;

}

void drow () { …} // функция рисования многоугольника, можно создать используя

… // аналогичную функцию отрезка. Для многоугольника можно

// создать новую функцию – раскраска.

}

Создание более сложной иерархии классов осуществляется так. Возьмем в качестве базовых классов классы отрезок и круг и построим класс наследник – фигура. Можно использовать и дружественные функции. Т.о. может выстроится сложная система переплетенных классов.

 

ОБЪЕКТО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ.

 

Три ключевых принципа определяют объектно-ориентированное программирование:

- инкапсуляция данных;

- наследование данных;