Informatika_2_semestr

q = t;

if (q->left == NULL) t = q->right; else if (q->right == NULL) t = q->left; else Del_vs (q->left);

delete q;

};

};

void Del_vs (tnode *&r) {

if (r->right != NULL) Del_vs (r->right);

else {

q->inf = r->inf; q = r; r = r->left;

};

};

int main () {

tnode *r; int x, n ; r = NULL;

cout <<“введите номер вершины \t"; cin>>x; while (x!=0) {

Add_Tree (x, r);

cout <<“введите номер вершины" <<'\t'; cin >> x; cout << endl;

};

inorder (r);

cout <<“введите номер удаляемой вершины \t"; cin>>n; Del_node (n, r); cout<<"\n";

inorder(r); return 0;

}

Сильно ветвящиеся деревья

Сильно ветвящиеся деревья - это деревья, у узлов которых может быть больше двух потомков. Узел такого дерева может быть представлен с помощью величины следующего типа:

const int n = ; struct tnode {

int inf1; char inf2;

……………

tnode *a[n];

};

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

17. Понятие графа, представление графа в ЭВМ

Графы

Граф G = (V, E) состоит из конечного множества вершин V и множества ребер E.

Если ребра определяют, соединяют неупорядоченные пары вершин, т.е. E є {(x, y): x, y є V & x ≠ y}, то граф называется неориентированным. Ребро обозначают - {x, y}.

Если ребра – это направленные отрезки, соединяющие вершины, то граф называется ориентированным, или орграфом, ребра называют дугами, т.е. множество ребер

21

E є VxV - это множество упорядоченных пар вершин обозначаемых <x, y>, где x называют началом, а y – концом дуги.

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

Если в графе G(V, E) ребро {u, v} или дуга <u, v> є E, то вершины u и v называются смежными, а ребро (дуга) - (u, v) называется инцидентным вершинам u и v.

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

Вершину нулевой степени называют изолированной.

Путем в графе ориентированном или неориентированном называют последовательность ребер вида (v1,v2) (v2,v3) (v3,v4)...(vk-1,vk) или последовательность вершин v1,v2,v3....vk,

таких что v1 – начало, vk – конец, к – длина пути.

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

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

Путь называется замкнутым, если v1 = vk. Замкнутый путь, у которого все ребра различны называются циклом.

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

путь.

Cпособы представления графов

Cпособы представления графов:

1)матрица инциденции

2)матрица смежности

3)список инцидентности

4)список списков

Матрица инциденции – это матрица размерности n*m, где n – количество вершин, а m – количество ребер.

Для орграфа в столбце, соответствующем ребру <u, v>, содержится (-1) в строке, соответствующей вершине u (вершине, из которой исходит стрелка), и (1) в строке, соответствующей вершине v (вершине, в которую входит стрелка).

Для неориентированного графа обе вершины u и v кодируются единицами, в остальных cтроках нули.

22

18. Представление графа списком инцидентности, алгоритм обхода графа в глубину

Для представленного орграфа матрица инциденции:

Для представленного неориентированного графа матрица инциденции:

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

На практике ребер в графе бывает обычно больше, чем вершин. Второй способ представления графов с помощью матрицы смежности оказывается более рациональным. Это матрица, размерности n*n, где n – количество вершин, причем ее элементы ai,j =1 если ребро (i,j) существует и ai,j = 0, если такого ребра нет.

Для неориентированного графа ребро {u,v} идет как от u к v, так и от v к u, поэтому матрица смежности для такого графа всегда симметрична относительно главной диагонали. Для рассматриваемых графов матрицы смежности будут такими:

Для орграфа 2-я и 4-я строки нулевые, т.к. 2-я и 4-я вершины не имеют исходящих дуг (такие вершины называются стоками для орграфа).

Третий способ еще более удобен – это структура данных, называемая списком инцидентности, или списком смежности. Эта структура содержит для каждой вершины v є V, список всех вершин, смежных, прямо достижимых из этой вершины, т.е. таких что есть ребро (u,v). Для n вершинного графа список инцидентности состоит из n линейных связных списков, начало каждого списка хранится в специальном массиве. Так что элемент массива Nach[i] хранит указатель на начало связного списка, содержащего смежные с i-ой вершины. Графически списки инцидентности для рассматриваемых графов могут быть представлены так:

23

Снимает ограничение на количество рёбер в графе.

Матрицу инциденции и матрицу смежности можно представить двумерным массивом целых элементов:

const int n= ,m= ; int Matr_in[n][m]; Matr_sm[n][n];

Список инцидентности можно представить массивом указателей на односвязные списки:

struct tnode { int k;

next *tnode; } Sp_in[n];

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

Многие алгоритмы решения задач на графы содержат обход по всем вершинам. Существуют два способа обхода графа:

1)обход графа в глубину

2)обход графа в ширину.

Идея метода обхода графа в глубину: пусть имеем n-вершинный произвольный граф. Начинаем просмотр, поиск с произвольной фиксированной вершины v0, затем выбираем любую вершину u, смежную с v0, и повторяем рекурсивно наш процесс от вершины u. В общем случае, находясь в текущей вершине v, мы просматриваем, есть ли еще непросмотренная, новая смежная с v вершина. Если есть, просматриваем ее и полагаем ее не новой и, начиная с нее, продолжаем поиск в глубину. Если же не существует больше ни одной новой вершины, смежной с v, полагаем эту вершину v использованной и возвращаемся на шаг, в вершину, из которой мы попали в v и снова продолжаем поиск в глубину до тех пор, пока не возвратимся в v0 и уже не будет больше непросмотренных смежных вершин. Графически:

Обход графа в глубину

Существуют рекурсивный и не рекурсивный алгоритмы, реализующие этот метод. Чтобы отличить просмотренную вершину от не просмотренной, вводится вспомогательный массив размерности n, и элемент его Nov[v] = false, если вершина уже просмотрена и true в противном случае. Запишем рекурсивный алгоритм на псевдокоде: DFS – Depth First

Search:

Function DFS(v)

//величины Nov и Spisok - глобальные begin

Просмотреть v; Nov[v] = false; for (u є Spisok[v]) do

if (Nov[u]) DFS(u);

end;

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

24

//добавляем новую вершину в стек begin t = Nach[t]->k; t -> stack;

просмотреть t; Nov[t] = false;

осуществлен обращением к этой функции так:
begin
for (v є V) do Nov[v] = true;	// инициализация массива
for (v є V) do
if (Nov[v]) DFS(v);

end;

Здесь V – множество всех вершин данного графа; Spisok[v] – содержит номера вершин, смежных с v;

Просмотреть вершину – это значит выполнить некоторые операции над данными, хранящимися в информационной части;

Посещается каждая вершина только один раз, т.к. просмотреть можно только ту вершину, у которой Nov[v] = true, сразу после просмотра этому элементу массива присваивается значение false;

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

Нерекурсивный обход графа в глубину:

function DFS1 (v); begin

stack = 0; v -> stack; просмотреть v; Nov[v] = false; while (stack <> 0) do

begin t = stack[sp]; b = true;

while (spisok[t]<>0 and b) do

// поиск 1-й новой вершины в spisok[t]

	begin u=spisok[t];
	if (Nov(u))
	then b = false // найдена новая вершина
	else u= spisok[t];
end;
if (not b) then	//добавляем новую вершину в стек
begin u -> stack; просмотреть u; Nov[u] = false; end;
else	//вершина t использована
stack -> t	//удалить из стека верхний элемент

end;

end;

Посмотрим нерекурсивный обход, если граф представлен списком инцидентности или смежности:

function DFS1 (v); begin

stack = 0; v -> stack; просмотреть v; Nov[v] = false; while (stack <> 0) do

begin t = stack[sp]; b = true;

while (Nach[t]<>Null and b) do

// поиск 1-й новой вершины в spiske(t) if (Nov[Nach[t]->k])

then b = false // найдена новая вершина else Nach[t]=Nach[t]->next

if (not b) then

25

end;

else	//вершина t использована
stack -> t	//удалить из стека верхний элемент

end;

end;

Здесь граф представлен списком инцидентности Nach[t], и k – определяет информационную часть – номера вершин, а next – поле, указующее на следующий элемент в списке, b – логическая вспомогательная величина.

19. Представление графа списком списка, алгоритм обхода графа в ширину

Четвертый способ представления – список списков снимает ограничение и на количество вершин в графе:

Список списков снимает ограничение и на количество вершин в графе. Вершину можно представить величиной типа:

struct Tgraf { int k;

Tgraf *left; Tnode *right;

};

Здесь указатель left указывает на следующую вершину в графе, а right - на список вершин смежных с к –ой

struct Tnode { int k;

next *Tnode;

};

Обход графа в ширину (Breadth First Search)

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

26

Алгоритм обхода в ширину на псевдокоде можно записать так: function BFS(v)

begin Queue = 0; v ->Queue; Nov[v] = false;

while (queue <> 0) do begin

Queue -> p; просмотреть p; for ( u є Spisok[p]) do

if (Nov[u]) then

begin Nov[u] = false; u -> Queue;

end;

end;

end;

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

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

Этого недостатка лишен алгоритм поиска в ширину. Для нахождения кратчайшего пути из u в v необходимо ввести в рассмотрение глобальный массив, назовем его Pred и будем заполнять его во внутреннем цикле при просмотре очередной вершины, добавив строку

Pred[u] = p;

…………………………

for ( u є Spisok[p]) do if (Nov[u]) then

begin Nov[u] = false;

u -> Queue; Pred[u]=p;

end;

20. Технологии программирования, концепции, заложенные в ООП

Введение в ООП

ООП – это один из подходов к разработке и созданию программ.

Исторически первым реализованным подходом было процедурное структурирование программ; создание больших библиотек для решения задач из конкретной области применения вычислительной техники. Эти программы из библиотек использовались для разработки сложных программных комплексов, такой подход называется «снизу вверх». Основан на возможности модульного программирования. Основное требование для машинонезависимых языков программирования. Впервые реализовано на Fortran. Но прогресс в области вычислительной техники, внедрение её в экономику, бизнес, использование её для

27

решения задач по обработке больших объёмных данных (в том числе и нечисловой информации) привело к разработке новых языков программирования, в которых стали уделять внимание структурам данных, их типам. В языке Pascal появились типы, создаваемые программистом, а основным подходом стало структурное программирование («сверху вниз»). Но уже в языке Симула 67 появились некоторые понятия и идеи, которые в дальнейшем реализовались в новом подходе программирования, названным объектно-ориентированным программированием.

ООП – это один из подходов к разработке и созданию программ. Исторически:

1.процедурное структурирование программ, программирование «снизу-вверх»;

2.структурное программирование, программирование «сверху – вниз»;

3.ООП - Object Oriented Programming.

Структурное программирование – это структурирование на уровне действий, а ООП – это структурирование на уровне моделируемых объектов.

ООП – это результат 40 летнего опыта и практики программирования, начиная с Simula 67, затем Smalltalk, Lisp, Clu, и далее Actor, Eiffel, Objective C, Object Pascal, Java, C++, C# и

т.д.

Концепции, заложенные в ООП, это:

Моделирование объектов и действий реального мира

Наличие типов данных, определяемых пользователем

Сокрытие деталей реализации (инкапсуляция)

Возможность многократного использования программного кода, благодаря наследованию

Интерпретация вызовов функций на этапе выполнения программы – полиморфизм.

21.Основные понятия ООП: абстракция, инкапсуляция, полиморфизм

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

последние десятилетия большое влияние на технологии программирования оказывает графический интерфейс пользователя (GUI).

Универсальные среды разработки Windows-приложений объединяют в себе визуальное программирование, программирование с управлением по событиям (event driven) и программирование с управлением объектами (object driven).

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

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

Windows.

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

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

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

28

объектов.

22. Понятие объекта, его состояние и поведение, классы, определение класса и объявление класса

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

ООП в С++

Определение класса в С++ выглядит точно так же, как определение структуры, только вместо слова struct используется слово class:

class <имя_класса> { /*поля данные */ /* методы */

};

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

Поля могут быть описаны с модификатором const, но инициализируются такие поля один раз и не должны изменяться.

Имея описание, можно символическое имя - <имя_класса> использовать для описания переменных.

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

Используя идентификатор типа <имя_класса>, как любой другой, созданный пользователем или стандартный, можно создавать произвольное количество простых переменных (объектов, экземпляров этого класса), массивов объектов данного класса, или указателей на объекты данного класса.

Примеры описания классов и объектов

class Tmoney
{ /*……*/ };
TMoney t;	/* t - простая переменная, объект класса TMoney */
TMoney *p;	/* p – указатель на объект класса TMoney */
TMoney m[50];	/* m - массив объектов класса TMoney */

Эти переменные так же, как и переменные встроенных типов, подчиняются правилам видимости, и время их жизни зависит от места объявления.

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

Объявлять переменные можно и с использованием ключевого слова class (по аналогии со

структурами):
class TMoney t;	/* простая переменная */
class TMoney *p;	/* указатель */
class TMoney m[50];	/* массив */,

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

Объявления и определения

Так же, как и при описании других типов, можно одновременно при описании идентификатора типа описать и величины этого типа, например:

class Tclass1

{ /*поля и методы*/} p1,p2;

Переменные p1 и p2 – это простые переменные типа Tclass1. Однако более предпочтительным считается описание:

Tclass1 p3, p4, *s, p5[20];

Заголовок описания класса, заканчивающийся точкой с запятой, class <имя_класса>;

29

называют объявлением класса.

Класс с идентификатором типа <имя_класса> еще не определен, еще не определены его поля и методы, поэтому объявлять переменные такого класса еще нельзя, но указатели и ссылки можно. Такое объявление используется в том случае, когда один класс зависит от второго, а определение этого второго класса недоступно.

Определение класса и структуры внешне отличаются только ключевым словом в заголовке. Но главное отличие заключается в том, что все, что описано внутри класса, недоступно извне класса по умолчанию. Например, имея определение класса person_1 и структуры person_2:

class person_1	struct person_2
{string fio;	{string fio;
duble summa;	double summa;
}	}

Можно определить переменную Ivanov структурного типа person_2 с инициализацией, но

нельзя определить объект Petrov класса person_1 с инициализацией:
person_2	Ivanov = {“Иванов И.И.”, 10000.00} ;	/* можно */
person_1	Petrov = {“Петров П.П.”, 10000.00} ;	/* нельзя */

Кроме того, вне определения объекта нельзя обратиться к полям объекта Petrov.fio и Petrov.summa. В этом заключается свойство классов инкапсуляция – сокрытие информации от внешнего мира.

Для работы с полями объектов в определение классов включаются специальные функции, называемые методами. По умолчанию методы класса тоже недоступны извне класса, поэтому для управления доступом к ним используются ключевые слова public, protected и private.

public (публичный, доступный) - открывает доступ,

private (частный, закрытый) запрещает доступ,

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

Доступная часть называется интерфейсной.

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

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

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

Статические, поля и методы

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

class A {

public: static int count;

};

int A::count; ……….

int A::count=10…….

30