close

Вход

Забыли?

вход по аккаунту

?

22Хижняк

код для вставкиСкачать
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ им. Р.Е.АЛЕКСЕЕВА
Курсовая работа
по дисциплине
"Информационные технологии"
22 вариант
Выполнил:
студент гр. 27-АСВ
Хижняк Е.
Проверил:
Пашковский А.И.
Нижний Новгород
2011
Определение графов
В математической теории графов и информатике граф - это совокупность непустого множества вершин и множества пар вершин.
Теория графов не обладает устоявшейся терминологией. Приводимые ниже определения - наиболее часто встречаемые.
Граф или неориентированный граф G - это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
* V это непустое множество вершин или узлов,
* E это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.
Известно несколько способов представлений графа G=(V, Е) в памяти компьютера.
1. Матрица смежности.
Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений. Матрица смежностей графа G=(V, Е) есть |V|×|V| - матрица A=[aij], в которой aij =1, если в G существует ребро, идущее из i-й вершины в j-ю, и aij =0 в противном случае.
2. Массив ребер.
Массив ребер - это массив, в котором ребра хранятся парами вершин, которые они соединяют. Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс - при таком способе представления легко вводить дополнительные характеристики ребер. 3. Cписки инцидентности.
Для каждой вершины графа создаются три списка:
- только неориентированные ребра, инцидентные вершине;
- исходящие ребра;
- входящие ребра.
4. Матрица инцидентности.
Матрица инцидентности - M задает граф : mij=1 если ребро j выходит из вершины i, mij=-1, если ребро j входит в вершину i, и mij=0 в остальных случаях.
5. Списки смежности.
Представляет собой структуру данных, которая для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.
Архитектура учебного приложения
Архитектура приложения, основана на поведенческом шаблоне MVC. При реализации шаблона MVC обычно используются следующие компоненты.
Model. Этот компонент содержит один или более классов и интерфейсов, отвечающих за обслуживание модели данных. Состояние модели сохраняется в атрибутах и реализации методов. В программе реализован классом MyModel.
View. Классы и интерфейсы представления обеспечивают презентацию данных, хранящихся в компоненте-модели. В программе реализован классом MyView.
Controller. Этот компонент управляет изменениями модели. Он хранит ссылку на компонент-модель, который отвечает за осуществление изменений, и сам в свою очередь отвечает за вызов одного или нескольких методов обновления. Запрос на изменения может поступать от компонента-представления. В программе контроллер реализован классом MyController.
Внутреннее представление графа в программе
В программе граф хранится в виде двух отдельных структур, хранящих информацию о вершинах и ребрах графа.
Для хранения вершин используется java-коллекция HashSet. Такая структура хранит не повторяющиеся элементы данных, поиск и выборка элементов происходят по значению хеш-функции, что позволяет минимизировать время выборки элемента и сделать его независимым от размерности множества. Хеш-функция вычисляется на основе идентификационного номера вершины, причем алгоритм создания вершины обеспечивает уникальность идентификационного номера. Для хранения ребер графа использована java-коллекция ArrayList. Время доступа к элементу такой структуры линейно зависит от размерности, как и редактирование списка. Структура списка позволяет хранить повторяющиеся элементы, что позволяет оперировать мульти-графами.
Задание к курсовой работе Удалить самый высокий лист в дереве
Код алгоритма
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import project.model.MyModel;
import project.model.figures.MyEdge;
public class DelClass {
private MyEdge mEdge;
private boolean mResult = false;
private LinkedList<MyEdge> mList = new LinkedList();
public MyEdge delete(MyEdge edge){
mEdge = edge;
if(mEdge.isLoop()){
MyEdge edge = MyModel.getModel().get(0).remove();
return edge;
}
mList.addLast(mEdge);
recursion();
for(MyEdge item:MyModel.getModel().getEdges()){
if(item.isChecked()){
item.setInited();
}
}
if(true == mResult){
return edge;
}
return null;
}
private void recursion(){
if(mResult == true){
return;
}
System.out.println(Arrays.toString(mList.toArray()));
MyEdge edge = findEdgeByIdFrom(mList.get(mList.size()-1).getOvalTo().getId());
if(null == edge){
if(mList.size()>1){
MyEdge deleted = mList.removeLast();
deleted.setChecked(true);
recursion();
} else {
return;
}
} else {
if(edge.getOvalTo().getId() == mEdge.getOvalFrom().getId()){
mList.addLast(edge);
mResult = true;
return;
} else{
mList.addLast(edge);
recursion();
}
}
}
}
Документ
Категория
Рефераты
Просмотров
13
Размер файла
51 Кб
Теги
22хижняк
1/--страниц
Пожаловаться на содержимое документа