Разработка программ с использованием динамической памяти
Введение1. Постановка задачи2. Использование динамических структур при работе с графами2.1. Способы представления графов2.2. Операции над графами2.3. Описание программной реализации2.3.1. Описание процедур и функций языка2.3.2. Описание функций работы с динамической памятью, графамиВыводыПриложение А Экранные формыПриложение Б Листинг программы1 ПОСТАНОВКА ЗАДАЧИЗадача.Найти все источники ориентированного графа.Исходные данные:- номер вершины (цел типа), вводимый пользователем;- дуга графа, задается двумя вершинами источником и стоком, вводимая пользователем.Промежуточные данные:Head:TUk – указатель на голову списка смежности графа;n,m:цел – номера вершин;c:сим – клавиша события.Результаты:V:массив байт – массив вершин источников;Ограничения:max=10 – максимальное количество вершин;V:массив [1..max*max].2. Использование динамических структур при работе с графами2.1 Способы представления графовСпособы задания графов:матрица смежности;матрица инцидентности;список смежности;список дуг (ребер);и др.Список смежности – для вершины v есть список концов дуг, исходящих из вершины v, в случае орграфа, или список смежных с v вершин, в случае неориентированного графа.Список дуг – это список, в котом каждой дуге ставится в соответствие пара , где x – начало дуги, а y – ее конец. Для нагруженных графов – тройка ,где x – начало дуги, y – конец дуги, z – вес дуги.Матрица смежности – это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0. Для неориентированных графов матрица смежности является симметричной относительно главной диагонали. Т.е. для получения информации о графе достаточно знать верхнюю или нижнюю треугольную матрицу смежности. Для ориентированных графов матрица смежности не является симметричной.Матрица инцидентности – это матрица, строки которой – список вершин, а столбцы – список ребер. Элемент матрицы инциденций (i,j) равен 1, если вершина i инцидентна соответствующему ребру.Для неориентированных графов:Для ориентированных графов:Например, дан граф G (см.рис. .1)Рисунок 2.1 – Граф GПредставление графа списком смежности отображено на рисунке 2.2Рисунок 2.2 – Список смежности графа GПредставление графа с помощью списка дуг имеет вид отображено на рисунке .3Рисунок 2.3 – Список дуг графа GПредставление графа с помощью матрицы смежности показано в таблице 2.1Таблица 2.1 – Матрица смежностиПредставление графа с помощью матрицы инцидентности показано в таблице 2.2Таблица 2.2 – Матрица инцидентности 2.2 Операции над графамиПри решении поставленной задачи для представления графа был выбран список смежности.type TUk1=^TEl1; //элемент списка вершин TEl1=record Next:TUk1; Inf:integer; end; TUk=^TEl; TEl=record //элемент списка смежности Left:TUk1; Inf:integer; Down:TUk; end;Head:TUk; //указатель на начало спискаСхематичное пр...
